Устройство для вычисления синдромов кода рида-соломона

 

Изобретение относится к вычислительной технике. Его использование в системах помехоустойчивого кодирования и системах коррекции ошибок во внешней памяти позволяет повысить.информативность устройства за счет параллельного вычисления синдромов, значений многочленов ошибок и их локаторов, а также повысить достоверность контроля устройства. Эта цель достигается благодаря введению дополнительных блоков, что обеспечивает более полное использование остальных блоков устройства , а также их потактовый контроль. 2 ил.

(! 9) (И) СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s Н 03 M 13/00, 13/02

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4838511/24 (22) 12.06,90 (46) 30,07.92. Бюл. № 28 (71) Курский политехнический институт (72) А.П.Типикин, О.А.Максимов, В,В.Гвоздев и Т.Э.Какурина (53) 681.326(088.8) (56) Патент США № 4584686, кл, G 06 F 11/10, опублик. 1986.

Авторское свидетельство СССР

¹ 1571773, кл. Н 03 M 13/00, 1988. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СИНДРОМОВ КОДА РИДА — СОЛОМОНА

Изобретение относится к вычислительной технике, а именно к специализированным вычислительным устройствам коррекции ошибок во внешней памяти, и может быть использовано в системах помехоустойчивого кодирования.

Известно многофункциональное устройство, содержащее набор регистров, двойной набор блоков умножения на постоянные коэффициенты,. многовходовый блок суммирования и мультиплексоры, которое позволяет вычислять синдромы в первом этапе декодирования или значения многочленов локаторов ошибок в третьем этапе декодирования помехоустойчивого кода Рида-Соломона.

К недостаткам данного устройства относятся неэффективное использование оборудования в третьем этапе декодирования при вычислении локаторов ошибок, так как при этом не используются около 50;ь регистров и блоков умножения на постоянные коэффициенты, а также отсутствие оперативного аппаратного контроля. (57) Изобретение относится к вычислительной технике. Его использование в системах помехоустойчивого кодирования и системах коррекции ошибок во внешней памяти позволяет повысить информативность устройства за счет параллельного вычисления синдромов, значений многочленов ошибок и их локаторов, а также повысить достоверность контроля устройства, Эта цель достигается благодаря введению дополнительных блоков, что обеспечивает более полное использование остальных олоков устройства, а также их потактовый контроль.

2 ил.

Наиболее близким к изобретению является устройство, содержащее набор регистров, набор блоков умножения на постоянные коэффициенты. набор блоков сумматоров по модулю два, двойной набор блоков свертки по модулю два, набор блоков соединений, три сумматора и два триггера.

Недостаток устройства — невозможность его использования в третьем этапе декодирования для вычисления значений многочлена ошибок.

Цел ь изобретения — повы ш ение информативности устройства за счет параллельного вычисления синдромов, значений многочленов ошибок и их локаторов и повышение достоверности контроля устройства, Поставленная цель достигается тем, что в устройство, содержащее первый — (2L)-й регистры (L — количество исправляемых ошибок кодом Рида-Соломона), первый (2L)-й блоки сумматоров по модулю два, первый — (2L)-й блоки умножения на постоянные коэффициенты, первый — (2L)-й соедините1751860

30

35 информационные входы которых подключе- 40 ны к выходам одноименных регистров, уп50

55 ли, первый и второй сумматоры по модулю два, первый и второй триггеры (2 +2)-й блок свертки по модулю два, тактовые входы первого и второго триггеров объединены с тактовыми входами первого — (2Ц-ro регистров и являются тактовым входом устройства, входы обнуления всех регистров объединены и являются первым установочным входом устройства, входы обнуления триггеров объединены и являются вторым установочным входом устройства, выходы каждого из первого — (2g-1о регистров подключены ко входам одноименных блока умножения на постоянный коэффициент и соединителя, выходы которого соединены с входами одноименного блока свертки по модулю деа, выходы первого — (21 )-ro блоков умножения на постоянный коэффициент подключены к первым входам одноименных блоков сумматоров по модулю два, вторые входы которых и входы (2L+1)-ro блока свертки по модулю два соответственно объединены и являются информационными входами устройства, выходы блоков сумматоров по модулю два подключены к входам одноименных регистров, (2L+2)-й блок свертки по модулю два, выходы первого — (2L+1)-го блоков. свертки по модулю два подключены к соответствующим входам первого сумматора по модулю два, выход которого соединен с информационным входом первого триггера, выход которога подключен к первому входу второго сумматора по модулю два, выход которого соединен с информацйонным входом второго триггера, выход которого является первым выходом устройства, дополнительно введены первый-третий блоки сложения, элемент ИЛИ, счетчик импульсов, блок коммутации и первый — (2 )-й блоки ключей, равляющие входы которых являются соответственно первым — 2L-ым управляющими входами устройства, управляющие. входы всех блоков ключей являются (2L+1)ми управляющими входами устройства, выходы всех нечетных и всех четных блоков ключей соединены с соответствующими входами соответственно первого и второго блоков сложения, установочный и счетный входы счетчика импульсов подключены соответственно к второму установочному и тактовому входам устройства, выходы счетчика импульсов соединены с первыми информационными входами блока коммутации, первый и второй управляющие входы которого являются (2 +2)-ым и (2(+3)-ым управляющими входами устройства, выходы первого блока сложения соединены со входами элемента ИЛИ, вторыми информационны5

15 ми входами блока коммутации и первыми входами третьего блока сложения, выходы которого подключены ко входам (2L+2)-го блока свертки по модулю два, выход элемента ИЛИ подключен к управляющему входу счетчика импульсов, выходы второго блока сложения соединены с вторыми входами третьего блока сложения и третьими информационными входами блока коммутации, выходы которого являются вторыми выходами устройства.

Информационность устройства повышена за счет применения неиспользуемых в прототипе при выполнении третьего этапа декодирования регистров и блоков умножения на постоянные коэффициенты для выполнения дополнительной функции вычисления значений многочлена ошибок.

Эффективность контроля повышена за счет охвата оперативным потактовым контролем сложных многовходовых блоков суммирования, испо..ьзуемых в третьем этапе декодирования для вычисления значений многочленов ошибок и их локаторов, На фиг. 1 изображена блок-схема устройства для вычисления синдромов кода Рида-Соломона; на фиг. 2 — функциональная схема первого блока сложения, Устройство для вычисления синдромов кода Рида-Соломона (фиг. 1) содержит первый — (2L)-й регистры 1,1-1.(2L) (L — возможное количество исправляемых ошибок кодом Рида-Соломона), первый — (2L)-й блоки 2,1-2.(21 ) сумматоров по модулю два, первый — (2L)-й блоки 3.1-3.(2 ) умножения на постоянные коэффициенты, первый — (2L)-й блоки 4,1-4.(2l ) ключей, первый — (2L)-й соединители 5.15,(2 ), первый — (2 )-й блоки 6.1-6.(2L) свертки по модулю два,(2 +1)-й блок 6. (2L+1) свертки по модулю 2, первый и второй сумматоры 7, 15 по модулю два, первый, второй и.третий блоки сложения 8, 9, 10, элементы ИЛИ 11, счетчик импульсов 12, (2 +2)-й блок 13 свертки по модулю два, первый и второй триггеры

14, 16, блок 17 коммутации, На фиг, 1 показан информационный вход 25, тактовый вход 19, первый и второй установочные входы 18, 20, управляющие входы 21,1-21.(2L) регистров, управляющие входы 22.1-22,(21 ) блоков ключей, управляющие входы 23, 24 блока коммутации, вйходы 26, 27 устройства.

Первый этап декодирования заключается в вычислении синдромов (контрольных сумм) по символам полученного слова.

Нахождение синдромов Sj (j = 1,г) осуществляется путем вычисления по схеме

Горнера значений многочлена полученного слова С(х) в корнях порождающего многочлена

Sj = С(а ). j = О,г-1, 1751860 (2) deg в((х) + degPi(x) r

53... Si

S4„. S i+i

S5 " %+2 (3) S1 S2

S2 ЗЗ

5з S4

Si=

St Яс+1 Si+2" S2i+i

50 (4) У— щах, ) блока 8; 9 сложения, 55 где r — количество корней порождающего многочлена g(x) кода Рида-Соломона. Вычисление синдромов осуществляется с помощью nepsoro — (2L)-ro регистров

1.1-1.(21 ) первого — (21 )-ro блоков 2.1-2.(21 ) сумматоров по модулю два, первого — (2L)ro блоков умножения на постоянные коэффициенты.

Нахождение значений ошибок У(и их локаторов Х((! = 1л) в конечном поле

GF(2 ) при декодировании PC-кода сводится к решению системы нелинейных уравнений где $(— синдромы;

t — число ошибок в полученном слове

С(х) РС-кода. . Из системы (1) получают систему линейных уравнений для определения коэффициентов (т многочлена локаторов ошибок

Матрица коэффициентов системы (2) является симметричной ганкелевой матрицей синдромов

Существует теорема, что значения t ошибок и t их локаторов определяются минорами элементов главных диагоналей определителей Ь = det 7i и Ь+) = detSi+1 матриц вида (3) Мррр при р = 1,с и, Mi+>,рр при р = 1 t+1, если Ь Ф О, à Ь+ = О, 4+2 = О,.Ь+з = О

Значения ошибок равны

pneee(X)= g Mrppx Р . (5) а значения Х(локаторов ошибок являются корнями многочлена

t+1

Р (х) - g М +1,ррХ ((6) р=1

При выборе корней порождающего многочлена g(x) в виде следующей последовательности степеней примитивного элемента поля G F(2 ) = ао, а, а=, cP, ...d — оборудование устройства вычисления по схеме Горнера (регистры 1.1-1.(2L) и блоки 3,1-3,(2L) умножения на постоянные коэффициенты) может быть использовано для последующего одновременного вычисления значений многочленов а((а)) и Pi(a ), так как для вычисления первого многочлена по схеме Горнера требуются блоки 3.2, 3.4, 3.6, ... 3.(21 ) умножения на нечетные степени примитивного элемента а: Q, Q, а, ..., а для второго многочлена — блоки

3,1, 3.3, 3.5, .„, 3.(21 ) умножения на четные степени примитивного элемента а; а, сР,а,„., Причем сумма максимальных степеней указанных многочленов в((а ) и Pt(d) не должна превышать количества r вычисляемых синдромов е

На основании этого представляется возможным повысить эффективность использования оборудования устройства в третьем этапе декодирования по сравнению с прототипом, Вычисление значений многочлена локаторов ошибок Pi(x) осуществляется с помощью регистров 1, 1,3, „„

"-.1.(2L-1), блоков 2.1, 2.3..., 2.(21 -1) сумматоров по модулю два, блоков 3.1, 3,3, „, 3.(2L-1) умножения на постоянные коэффициенты. блоков 4,1, 4,3, . „4.(2L-1) ключей и первого блока 8 сложения.

Вычисление значений многочлена ошибок (x) осуществляется с помощью регистров 1.2, 1,4, ... 1,(21 ), блоков 2,2,.2,4, „, 2.(23 ) сумматоров по модулю два, блоков 3.2, 3,4, ..., 3.((2 ) умножения на постоянные коэффициенты, блоков 4.2, 4,4, ..., 4.(2L) ключей и второго блока 9 сложения.

В соответствии с предложенным повышением информационности устройства для вычисления синдромов в него вводятся два

В то же время известная схема аппаратного контроля не может охватить контролем указанные блоки 8,9 сложения, Для охвата оперативным контролем блоков 8 и

9 сложения введен дополнительный блок

10 сложения и блок 13 свертки по модулю два.

1751860 (.9) 10

15 (1+1) R 1() о

2(!+1) = R2(а (7) (I+1) .R () . 2

R 2L-1 = 2L-1 и(!+1) R() „; 2 1

50 (8) Принцип аппаратного контроля устройства для вычисления синдромов основан на методе предсказания следующего состояния содержимых регистров 1,1-1.(2 ) по четности, зная алгебраические правила функционирования схемы Горнера для вычисления значений многочленов в корнях порождающего многочлена РС-кода. В. третьем этапе декодирования содержимое регистров 1,1, 1.2, ..., 1.(2L-1), 1,(2L) в !-ом такте(обозначим соответственно Ri ), R2 ), 0) (!) .. R )2,1, В(2

Определим содержимое регистров 1,1, 1.2, ..., 1.(2L-1), 1,(2L) в ()+1)-ом такте по их содержимому в I-ом такте, зная алгебраические правила функционирования схемы

Горнера где а, а, аг, ..., a2L, а= " — значения корней порождающего многочлена кода Рида-Соломона:

g(x}=(x+aо)(х+а)(х+аг)...(x+a )(х+а ), которые являются элементами конечного поля Галуа 6Г(2 ) характеристики два, Используя систему формул (7), определим свертку по модулю два содержимого регистров 1,1, 1,2, „., 1.(2! -1), 1,(2I ) в (!+1)-ом такте (- условное обозначение свертки по модулю два двоичных разрядов элементов поля ОР(2 )).

Х ) 1""=Х (Ri" )

R2(+1) = (Яг() a)

Х Кз(""= (Яз() ) 2!-1 = (2L 1 ГГ ) Вг(. -,), (R 2! u ) Четность. содержимого всех регистров

1.1, 1.2, ... I.(2! -1), 1,(2L) определяется по следующей фо рмуле:

45 р II+1) У р (3+1) р (r+1l

)=1

+ X (2 1+ g Йг!(где,, . — обозначение операции суммирования элементов поля GF(2 ). Подставляя в правую часть выражения (9) вместо R! "" их выражения их системы формул (8), получим х 2 я,()= 2 х(в,(п. -)„щ !.= !

Левую часть формулы (10) реализуют первый, второй и третий блоки 8,9,10 сложения.и. (2L+2)-й блок 13 свертки по модулю два, что позволяет охватить их оперативным контролем. Правую часть . формулы (10) реализуют первый — (2L)-й соединители 5,1-5,(2L}, первый — (2L)-й блоки

6.1-6.(2L) свертки по модулю,два, первый сумматор 7 по модулю два, первый триггер

14. Проверку равенства осуществляет второй сумматор 15 по модулю два.

Устройство для вычисления синдромов кода Рида-Соломона работает следующим образом, Вычисление синдромов в первом этапе декодирования осуществляется. по схеме

Горнера.

В начале цикла содержимое регистров

1,1-1.(2L) по сигналу, поступающему на установочный вход 20 устанавливается в нулевое состояние. Первый и второй триггеры

14,16 по сигналу, поступающему на установочный вход 18, устанавливаются в нулевое состояние, Каждый цикл работы состоит иэ n тактов, где и — количество символов в кодовом слове РС-кода. На все управляющие входы блоков ключей 22.122,(2L) и управляющие входы регистров

21.1-21.(2L) подается логическая единица, В результате сдвига m-разрядных слов с входов на выходы всех двухтактных регистров по тактовым синхросигналам т в схеме организуется параллельное вычисление синдромов SO, S1 ° «, 32! За и тактов, В )-ом (! = 1n) такте работы устройства на информационный вход 25 устройства поступает очередной символ кодового слова С ..

С помощью первого — 2(L)-ro блоков 3,13.(2L умножения на постоянные коэффициенты, первого — (2! )-го блоков 2.1-2.(2L) 1751860

10

55 сумматоров по модулю два выполняется очередной этап вычисления синдромов.

Блоки 3.1-3.(21 ) умножения на постоянные коэффициенты реализуют процедуру умножения содержимого соответствующих регистров 1.1-1.(2L) на коэффициенты сР, а.

2 (.-1

На информационных входах регистров

1.1-1.(2L) формируется информация о следующем состоянии этих регистров, исходя из формулы (7), С помощью соединителей

5,1-5.(2L).è блоков 6,1-6,(21 ) свертки по мо: дулю два на выходе первого сумматора

7 nо модулю два формируется сигнал четности следующего состояния содержимого регистров 1.1-1.(2L) согласно правой части формулы (10), По тактовому сигналу r, поступающему на тактовый вход 19, сигнал четности с выхода первого сумматора 7 по модулю два запоминается в первом триггере 14, и одновременно информация с входов регистров 1;1-1.(21 ) переписывается в данные регистры.

В следующем (i+1)-ом такте с помощью .блоков 4.1-4.(2L) ключей первого, второго и третьего блоков 8,9,10 сложения на выходе (2L+2)-го блока 13 свертки по модулю два формируется сигнал четности содер- . жимого регистров 1,1-1.(2() согласно левой части формулы (10). Сформированный с помощью этих блоков сигнал четности сравнивается путем суммирования по модулю два во втором сумматоре 15 по модулю:два с ранее сформированным в i-ом такте сиг. налом четности, хранящимся в первом триггере 14.

Если данные два сигнала четности различны, то на выходе второго сумматора 15 по модулю два формируется сигнал сбоя, который по окончании (i+1)-го такта по тактовому.сигналу r, поступающему на тактовый вход 19, запоминается во втором триггере 16. Одновременно в (i+1)-ом такте формируется с помощью блоков 6.1-6,(2L) свертки по модулю два и первого сумматора

7 по модулю два сигнал четности следующего состояния регистров 1.1-1,(2L), который по тактовому сигналу т, поступающему на вход 19 запоминается в первом триггере 14.

На информационных входах регистров 1.11.(2L) формируется информация о следую..щем состоянии этих регистров аналогично, как в i-ом такте и так далее. Сигнал сбоя, если сбой имел место, с выхода второго триггера 16 подается на выход 28 устройства.

По истечении и тактов сдвиг информации в регистрах 1.1-1.(2L) синхросигналами т прекращается, и в дальнейшем регистры

1.1-1.(2L) могут использоваться в качестве памяти с произвольным обращением к любому из регистров, Любой из синдромов может быть считан путем опроса соответствующего регистра одним из блоков 4.1-4.(2L) ключей и через блоки 8,9 сложения и блок 17 коммутации передан на выход 26 устройства.

В дальнейшем во втором этапе декодирования на основании этих значений синдромов вычисляются значения диагональных миноров М рр и М +1,рр в отдельном устрой15 стве вычисления миноров, которое не касается сущности изобретения и на фиг, 1 не показано.

В третьем этапе декодирования для вычисления значений много, членов Р (а ) и.в (а ), j = О,п-1 их коэффициенты М1рр и

М +1,рр необходимо записать в регистры

1,1-1.(2L), B режиме записи на входы 22.122.(2L) подается логический нуль, а на один из входов 21.1-21.(2L загружаемого регистра — логическая единица., разрешающая прием в регистр значения соответствующего коэффициента, поступающего на вход

30 25 устройства.

После загрузки всех значений миноров

М1рр и М +1 рр в регистры 1.1-1,(21.) устройст. во вновь переводится в режим аналогичный вычислению синдромов, но при нулевых значениях входных переменных.на входе

25. В начале цикла счетчик импульсов 12 по сигналу, поступающему на установочный вход 18, устанавливается в нулевое состояние, 40 В результате сдвигов инфдрмации в регистрах 1.1-1.(2L) по тактовым синхросигналам r пос ледавательно вычисляются и образуются в каждом j-ом такте на выходах первого и второго блоков 8,9 сложения со45 ответственно значения многочленов P (Q) и w(d), j = О,п-1. Если в каком-либо )-ом такте значения Р (а ) = О, счет в счетчике импульсов 12 прекращается по управляющему сигналу. образующемуся на выходе элемента ИЛИ 11.

Одновременно прекращается сдвиг информации в регистрах 1.1-1.(21 ) по синхросигналу хи с помощью блока 17 коммутации выводится из устройства вначале номер локатора ошибки j, образующийся на выходе счетчика импульсов 12, а затем значение многочлена &(g образующееся на выходе второго блока 9 сложения. Далее вновь продолжаются сдвиги информации по син1751860

12 хросигналу тдо очередного обнуления значения Р (й1).

Контроль правильности функционирования устройства при вычислении локаторов ошибок и значений многочлена ошибок в третьем этапе декодирования осуществляется аналогично контролю при"вйчйслении . синдромов в первом этапе декодирования, Формула изобретения

Устройство для вычисления синдромов

Рида — Соломона, содержащее первый и второй триггеры, тактовые входы которых объединены с тактовыми входами первого—

2L-ro регистров (L — количество ошибок, исправляемых кодом Рида — Соломона) и являются тактовым входом устройства, входы обнуления всех регистров объединены и являются первым установочным входом уст-. ройства, входы обнуления триггеров объединены и являются вторым установочным входом устройства, выходы каждого из первого — 2L-го регистров подключены к входам однеименных блока умножения на постоянный коэффициент и соединителя, выходы которого соединены с входами одноименного блока свертки по модулю два, выходы первого — 2L-ro блоков умножения на постоянный коэффициент подключены к первым входам одноименных блоков сумматоров по модулю два, вторые входы которых и входы (2L+1)-го блока свертки по модулю два соответственно объединены и являются информационными входами устройства, (2L+2j-й блок свертки по модулю два, выходы первого — (2L+1)-го блоков свертки по . модулю два подключены к соответствующим входам первого сумматора по модулю два. выход которого соединен с информационным входом первого триггера, выход которого подключен к первому входу второго сумматора по модулю два, выход которого соединен с информационным входом второm триггера, выход которого является первым выходом устройства, о т л и ч а ю щ е ес я тем, что, с целью повышения информативности устройства за счет параллельного вычисления синдромов, значений многочленов ошибок и их локаторов и повышения достоверности контроля устройства, в него введены первый — третий блоки сложения, элемент ИЛИ, счетчик импульсов, блок коммутации и первый — 2L-й блоки ключей, информационные входы которых подклю10 чены к выходам одноименных регистров, управляющие входы которых являются соответственно первым -2L-м управляющими входами устройства, управляющие входы блоков ключей являются (2L+1)-ми управляющими входами устройства, выходы всех нечетных и всех четных блоков ключей соединены с соответствующими входами соответственно первого и второго блоков сложения, установочный и счетный входы

20 счетчика импульсов подключены соответственно к второму установочному и тактовому входам устройства, выходы счетчика импульсов соединены с первыми информационными входами блока коммутации, первый и второй управляющие входы ко- . торого являются (2L+2)-ым и (2L+3)-ым управляющими входами устройства, выходы первого блока сложения соединены с вхо25 онными входами блока коммутации и первыми входами третьего блока сложения, выходы которого подключены к входам (21+2)-го блока свертки по модулю два, выход которого подключен к второму входу второго сумматора по модулю два, выход элемента ИЛИ вЂ” к управляющему входу счетчика импульсов, выходы второго блока сложения соединены с вторыми входами третьего блока сложения и третьими информационными входами блока коммутации, выходы.которого являются вторыми выходами устройства, 40

30 дами элемента ИЛИ, вторыми информаци1751860

1751860

Редактор Н. Швыдкая

Заказ 2697 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул,Гагарина. 101 ф5

Ф.7

Составитель Т. Какурина

Техред M,Ìoðãåíòàë Корректор M. Демчик