Устройство для вычисления синдромов кода Рида-Соломона Советский патент 1992 года по МПК H03M13/00 H03M13/02 

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

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

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

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

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

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

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

с

VI сл

00

о о

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

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

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

5 На фиг 1 изображена блок-схема устройства для вычисления синдромов кода Рида-Соломона; на фиг 2 - функциональная схема первого блока сложения

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

0 кода Рида-Соломона (фиг 1) содержит первый-(21}-й регистры 1 1-1 (2 L)(L-возможное количество исправляемых ошибок кодом Рида-Соломона), первый - (21)-й блоки 2 1-2 (2L) сумматоров по модулю два, первый - (

5 блоки 3 1-3 (2L)умножения на постоянные коэффициенты, первый - (21)-й блоки 4 1-4 (2L) ключей, первый - (2)-й соединители 5 1- 5 (2L), первый - (2)-й блоки б 1-6.(21) свертки по модулю два,(21 +1}-й блок 6. (2L+1) свертки

0 по модулю 2, первый и второй сумматоры 7, 15 по модулю два, первый, второй и третий блоки сложения 8, 9, 10, элементы ИЛИ 11, счетчик импульсов 12, (2 +2}-й блок 13 свертки по модулю два, первый и второй триггеры

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

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

5 Нахождение синдромов S) 0 1 г) осуществляется путем вычисления по схеме Горнера значений многочлена полученного слова С(х) в корнях порождающего многочлена

Sj C(ctj) j 0r-1

где г - количество корней порождающего многочлена д(х) кода Рида-Соломона. Вычисление синдромов осуществляется с помощью первого - (21)-го регистров 1,1-1 .(2L) первого-(2 L)-ro блоков 2.1-2.(2L) сумматоров по модулю два, первого -(2L)- го блоков умножения на постоянные коэффициенты.

Нахождение знЈчений ошибок YJ и их локаторов Xi(l 1,t) в конечном поле GF(2m) при декодировании PC-кода сводится к решению системы нелинейных уравнений

Ј YiXJi S,,2t

I 1

где Sj - синдромы;

t - число ошибок в полученном слове С(х) PC-кода.

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

ошибок

V

i) a0Sj+H Sj+t.j 1,t.

ч i

PtM- V М1+1, (6)

р 1

5При выборе корней порождающего многочлена д(х) в виде следующей последовательности степеней примитивного элемента поляСР(2т) а°1а,а2, ... -оборудование устройства вычисления по схеме Горне1Q pa (регистры 1.1-1.(2L) и блоки 3.1-3,(2) умножения на постоянные коэффициенты) может быть использовано для последующего одновременного вычисления значений многочленов (a ) и Pt(a ), так

15 какдля вычисления первого многочлена по схеме Горнера требуются блоки 3.2, 3.4, 3.6, ... 3.(21) умножения на нечетные степени примитивного элемента ее. а, от, (г а для второго многочлена - блоки

2Q 3.1, 3.3, 3.53.(21) умножения на четные степени примитивного элемента a. (f,

о2, а4

Причем сумма максимальных степеней указанных многочленов Шг(а) и Pt(a )

25 не должна превышать количества г вычисляемых синдромов

deg (x) + degPt(x) r,

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

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

(3)

S,

Существует теорема, что значения t ошибок и t их локаторов определяются минорами элементов главных диаго а- лей определителей At det 5t и Л+i detSt+i матриц вида (3)

Mtpp при р 1 д и Mt-м рр при р 1 ,t+1,

если & 0, а Дг-и 0, At+2 0, At+з 0 ... Значения ошибок равны

Vice ( Xi)

(4)

(X) Ј MtpPX2p р 1

-1

(5)

а значения Xi локаторов ошибок являются корнями многочлена

t - i

30 На основании этого представляется возможным повысить эффективность использования оборудования устройства в третьем этапе декодирования по сравнению с прототипом. Вычисление значений мно- 35 гочлена локаторов ошибок Pt(x) осуществляется с помощью регистров 1, 1.3, ,,. 1.(2L-1), блоков 2.1, 2.3, ... 2.(2Ы) сумматоров по модулю два, блоков 3.1, 3.3, ,., 3.(2L-1)умножения на постоянные коэффи40 циенты, блоков 4.1, 4,3, .... 4.(2L-1) ключей и первого блока 8 сложения.

Вычисление значений многочлена ошибок ft)t(x) осуществляется с помощью регистров 1.2. 1.4, ... 1,(2L), блоков 2,2, 2,4, ,,2.(2L)

45 сумматоров по модулю два, блоков 3.2, 3,4, ..., 3.i(2L) умножения на постоянные коэффициенты, блоков 4.2, 4.4 4.(2L) ключей и

второго блока 9 сложения.

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

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

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

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

Принцип аппаратного контроля устройства для вычисления синдромов основан на методе предсказания следующего состояния содержимых регистров 1.1-1.{21) по четности, зная алгебраические правила функционирования схемы Горнера для вычисления значений многочленов в корнях порождающего многочлена PC-кода. В третьем этапе декодирования содержимое

регистров 1.1, 1.2 1 (2L-1), 1.(2L) в 1-ом

такте обозначим соответственно Rr , R2Ч ...- РГ|)2Ы, R0)2L.

Определим содержимое регистров 1.1,

содержимому в l-ом такте, зная алгебраические правила функционирования схемы Горнера

г

R1 l 1 -RtW-rf

R2

0+D RzO) .

а

R30+1) R3(0 - «2

R ibi -R M - rf8

(7)

Ra.W-R L-a 1--1,

ьм

где «°, a, a2a21 2, - значения корней

порождающего многочлена кода Рида-Соломона:

g(x)(x-t-a0)(x + a)(x + a2) (x + a2L2)(x4-«2L 1),

которые являются элементами конечного поля Галуа GF(2m) характеристики два

Используя систему формул (7), определим свертку по модулю два содержимого

регистров 1.1,1.21 .(2L-1), 1 .(2L) в (1+1)-ом

такте ( 2 условное обозначение свертки по модулю два двоичных разрядов элементов поля GF(2m)).

2 Ri(l+1)2 (Р1(1) «°) 2 R2(i+1) 2 (R2(l) «) 2 R3(M) 2 (R30) a2)

(8)

2 ( (R(l)2n a212) 2 R2L(l4l)-2 R(°2i -a21 1).

Четность содержимого всех регистров 1.1, 1.2, ... 1.() 1 (2L) определяется по следующей формуле

X

J 1

R)

.0+1)

2 Ri(l+1) 2 R2

.0+1)

2 R( +1)2L-1+2 R2L1

(1+1)

(9)

где 2 обозначение операции суммирования элементов поля GF(2m). Подставляя в правую часть выражения (9) вместо R/l+l их выражения их системы формул (8), получим

,0+D j 1

2(Rj(i) -о1-1)(10)

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

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

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

кода Рида-Соломона работает следующим образом.

Вычисление синдромов в первом этапе декодирования осуществляется по схеме Горнера.

В начале цикла содержимое регистров 1 1-1.(21) по сигналу, поступающему на установочный вход 20, устанавливается в нулевое состояние. Первый и второй триггеры 14,16 по сигналу, поступающему на установочный вход 18, устанавливаются в нулевое состояние Каждый цикл работы состоит из п тактов, где п - количество символов в кодовом слове PC-кода. На все управляющие входы блоков ключей 22.122.(2L) и управляющие входы регистров 21.1-21.(2L) подается логическая единица

В результате сдвига m-разрядных слов с входов на выходы всех двухтактных реги- строе по тактовым синхросигналам т в схеме организуется параллельное вычисление синдромов So, Si, ., 821 за п тактов.

В 1-ом (I 1 п) такте работы устройства на информационный вход 25 устройства поступает очередной символ кодового слова С . С помощью первого - 2(L)-ro блоков 3.1- 3.(2L) умножения на постоянные коэффициенты, первого - (2L)-ro блоков 2 1-2 (2L)

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

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

На информационных входах регистров 1.1-1.(2L) формируется информация о следующем состоянии этих регистров, исходя из формулы (7). С помощью соединителей 5.1-5.(21) и блоков 6.1-6.(21) свертки по модулю два на выходе первого сумматора 7 по модулю два формируется сигнал четности следующего состояния содержимого регистров 1.1-1.(21) согласно правой части формулы (10). По тактовому сигналу г, поступающему на тактовый вход 19, сигнал четности с выхода первого сумматора 7 по модулю два запоминается в первом триггере 14, и одновременно информация с входов регистров 1.1-1.(21) переписывается в данные регистры.

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

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

По истечении п тактов сдвиг информации в регистрах 1 1-1.(2L) синхросигналами

г прекращается, и в дальнейшем регистры 1.1-1.(21) могут использоваться в качестве памяти с произвольным обращением к любому из регистров, Любой из синдромов

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

0

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

В третьем этапе декодирования для ® вычисления значений многочленов Pt{o)

и (th(d), J 0,п-1 их коэффициенты Mtpp и Mt+i,pp необходимо записать в регистры 1.1-1.(21). В режиме записи на входы 22.15 22.(2L) подается логический нуль, а на один из входов 21.1-21 .(2L) загружаемого регистра - логическая единица, разрешающая прием в регистр значения соответствующего коэффициента, поступающего на вход

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

После загрузки всех значений миноров Mtpp и Mt+i,pp в регистры 1.1-1.(2L) устройство вновь переводится в ре-жим аналогичный вычислению синдромов, но при нулевых

r значениях входных переменных на входе 25. В начале цикла счетчик импульсов 12 по сигналу, поступающему на установочный вход 18, устанавливается в нулевое состояние.

Q В результате сдвигов информации в регистрах 1.1-1.(2L) по тактовым синхросигналам т последовательно вычисляются и образуются в каждом j-ом такте на выходах первого и второго блоков 8,9 сложения со5 ответственно значения многочленов PiO) и Oh(a}), j 0,п-1. Если в каком-либо j-ом

такте значения Pt(o) О, счет в счетчике импульсов 12 прекращается по управляюQ щему сигналу, образующемуся на выходе элемента ИЛИ 11.

Одновременно прекращается сдвиг информации в регистрах 1.1-1.(21) по синхросигналу г и с помощью блока 17 коммутации

5 выводится из устройства вначале номер локатора ошибки j, образующийся на выходе счет«ика импульсов 12, а затем значение

многочлена й(о) образующееся на выходе

второго блока 9 сложения. Далее вновь

продолжаются сдвиги информации посинхросигналу т до очередного обнуления значения ).

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

информационные входы которых подключены к выходам одноименных регистров, управляющие входы которых являются соответственно первым - 21-м управляющими входами устройства, управляющие входы

блоков ключей являются ()-ми управляющими входами устройства, выходы всех нечетных и всех четных блоков ключей соединены с соответствующими входами соответственно первого и второго блоков

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

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

ГЛ1ф

Wz

-i 11

TL,