Устройство для исправления ошибок Советский патент 1988 года по МПК H03M13/51 

Изобретение относится к вычислительной технике, и может быть использовано при создании устройств, корректирующих ошибки, возникающие в информационных посылках при их хранении или передаче по каналам СВЯЗИ и предназначено для работы с кодами Рида-Соломона длины -1, в каждой -кодовой комбинации которого имеется К информационных и п-К проверочных символов, каждый из которых содержит m двоичных разрядов, где tn - размерность поля GF (2 ) Галуа. Образующий полином кода для исправ- ления двухкратных ошибок 9(х) (х+1) (х+сб) (х+ ci ) (х+ cv) , где oi - примитивный элемент поля GF (2) Галуа.

Цель изобретения - повышение быст родействия устройства.

На чертеже представлена функциональная схема устройства

Устройство содержит запоминающий блок 1, буферный накопитель 2, блок 3 из m сумматоров по модулю два, генратор 4 синдромов, накопитель 5 синдромов , вычислитель 6 элементарных симметричных функций, блок 7 вычисле ния ошибок и дешифратор 8 ошибок.

Блок 7 вычисления ошибок состоит и,з элемента И 9, счетчика 10 импульсов, блоков 11-13 постоянной памяти, регистров 14-17, коммутаторов 18-20, блока 21 постоянной памяти, перемно- жнтеля 22, группы 23 из m триггеров, блоков 24 и 25 оперативной памяти, блоков 26-29 постоянной памяти, коммтаторов 30-32 и группы 33 из m триггеров,

Устройство работает следующим образом.

В запоминающем блоке 1 с помощью образующего полинома.9(х) записывает ся закодированная избыточным (п,К) кодом Рида-Соломона кодовая комбинация G(x). При передаче по каналу связи или при считьшании с блока 1 на G(K) ыакладьгоается вектор ошибок Е(х), в результате чего в буферный накопитель 2 и генератор 4 синдромов поступает в последовательность RCx-) G(x) + Е(х).

В генераторе 4 деления R(x) на составные части образующего полинома 9(х) (х+1) (х+в,)(х+Ю(х+Ы) получа- ют синдромы So,S/,S,S,, которые за- письшают в накопитель 5 синдромов. На выход накопителя 5 подключен де

0

с

Q

шифратор 8, функционирующий как элемент ИЛИ. Если S,

о 2 втором выходе дешифратора 8 появляется сигнал Нет ошибки и кодовый блок выдается потребителю путем подачи сигнала Считьшание на управляющий вход буферного накопителя 2. В противном случае получают остаток от деления, содержащий хотя бы одну 1, тогда на выходе дешифратора 8 появляется сигнал Ошибка, который дает разрешение для работы вычислителя 6.

В вычислителе 6 определяют кратность 1 ошибки и значения G элементарных симметрических функций из соотношений

S,+ G,SO О; Sj+ G,S, 0;

s,+ 0;

1 1 5л

0;

G,S«+ С„5, 0.

5

д

0

Последовательностьработы вычислителя 6 следующая.

О, то 1 и

G,.S, иЕсли

G, S,/Se5

G, S,

GO Y, S 5: 2

S,+

84 f

Sj+ G,S 0,

o

в

определяют . Если 1 1 X X противном случае 3

то

и вычисляют

я

l

+ 8„5

G,- (S,S2.+ 5д8)/д;

G.

(S, S, R)/&;

D

s,+

G,S2+ G

So

Si 0 и

Если D 4 О.ИЛИ если , принятая кодовая комбинация стирается. Если D О, то 1 2 по сигналу с вычислителя 6 в блоке 7 производят определение

ошибок.

i

ДГоследовательность работы блока 7 следующая.

Локаторы ошибок находят из квадратного уравнения канонического вида

(4)

Откуда Х,

z,G,

.

z,G,

где 2 и Zj - решение уравнения (4). Так как уравнение (4) имеет ненулевые корни только при определенных значениях у , то операцию решения (4) просто реализуют табличным способом с помощью блоков 27 и 28 постоянной памяти. Для всех возможных значений у , при. которых f(4) имеет ненулевые решения, заранее определены величины z и по каждому адресу Y в блок 27 занесены соответствующая величина z, а в блок 28 При подаче на адресные входы бло 2ков 27 и 28 величины J с их выходов

считывают соответствующие величины

и г

г

После определения локаторов Х и Xj из (5) производят определение значений Y и Y« ошибок из соотношений (3), которые для кода Рида- Соломона с порождающим многочленом 9(х) (x+l)(x+6i)(x+ed) (x+oi) имеет вид .

+ У Х

0

результате на выходе блока 27 появляется величина z, которую записьгоа- ют в блок 23 группы из m триггеров, а на выходе блока 28 - Zj, которую записьтают в блок 33 и m триггеров. На втором такте с выходов блока 11 на блоки 24 и 25 оперативной памяти подаются сигналы записи и выдается адрес, по которому величина Zj записьшается в блок 24, а z - в блок 25.

На третьем такте блок 12 с помощью коммутатора 18 подключает на первые входы перемнохителя 22 выходы блока.24, блок 11 выбирает из блока 24 величину z,, которая подается на входы перемножителя 22. Одновременно блок 12 с помощью коммутатора 19 подключает выход регистра 17 на вторые входы перемножителя 22, а блок 26 с помощью коммутаторов 31

При обнаружении ошибок из блока 6 -де подключает выход перемножителя в блок 7 выдается сигнал, который от- 22 на входы групп 23 и 33 триггеров.

.у,х;

откуда

Y,

Ya

-ь Y,X,

Y,+

35

40

о

Блок 7 при работает следующим образом.

432787..

является адресом для блока 29, на входе которого появляется записанная по этому адресу величина 1/G,. Блок 21 памяти подключает с помощью коммутатора 20 выходы блока 29 на вход блока 13 памяти. Значение 1/G, является адресом для блока 13. В результате на вьпсоде блока 13 появляется Q записанная в нем по этому адресу величина 1 /G, .

Таким образом, на первых входах перемножителя 22 появляется величина G,,а на вторых - 1/G,. Одновременно блок 21 памяти подключает 15 через коммутатор 30 выход перемножителя 22 на входы блоков 27 и 28 памяти. На этом же такте происходит умно- Hl/G

жение G,

и с выхода перемно

жителя 22 полученная величина через коммутатор 30 подается на блоки 27 и 28. Величина Jj является адресом для блоков 27 и 28, по которому в них

25

записаны соответственно z , и z.

В

30

1

результате на выходе блока 27 появляется величина z, которую записьгоа- ют в блок 23 группы из m триггеров, а на выходе блока 28 - Zj, которую записьтают в блок 33 и m триггеров. На втором такте с выходов блока 11 на блоки 24 и 25 оперативной памяти подаются сигналы записи и выдается адрес, по которому величина Zj записьшается в блок 24, а z - в блок 25.

35

40

Изобретение относится к вычислительной технике и может быть использовано при создании устройства, исправляющих ошибки в хранимой или передаваемой по каналам связи информации. Целью изобретения является повьтение быстродействия устройства. Устройство содержит запоминающий блок 1, буферный накопитель 2, блок 3 сумматоров по модулю два, генератор 4 синдромов, накопитель 5 синдромов , вычислитель 6 злементарных симметрических функций, Дешифратор 8 ошибок и блок 7 вычисления ошибок, состоящий из злемента И 9, счетчика 10 импульсов, четырех регистров 14- 17, восьми блоков 11-13, 21,26-29 постоянной памяти, шести коммутаторов 18-20, 30-32, перемножителя 22, двух групп 23 и 33 из га триггеров и двух блоков 24 и 25 оперативной памяти. Введение пяти блоков постоянной памяти, группы из m триггеров и трех коммутаторов позволяет реализовать одновременное определение корней канонического квадратного уравнения локаторов, величины, используемой в последующем для вычисления значений ошибок, и сокращает количество тактов исправления двухкратных ошибок в 1,5 раза, где m - размерность поля GF (2) Галуа. 2 табл.,1 ил. а. Од N5 00

крьтает элемент И 9. Через него начинают поступать тактовые импульсы Т на счетчик 10. На выходы счетчика 10 подключены блоки 11,12,21 и 26 Постоянной памяти.

На первом такте блок 12 подключает с помощью коммутатора 18 на входы перемножителя 22 выходы регистра 16, а выходы регистра 17 через блок 29 памяти, коммутатор 20 и блок 13 памяти с помощью коммутатора 19 на вторую шину перемножителя 22. Значение G, записанное в регистре 17,

Таким образом, на вькоде перемножите ля 22 получен локатор ошибок Х, Z, Г,, который записывается в триггеры групп 23 и 33.

На четвертом такте локатор Х с помощью блока 11 с группы 23 тригге-. .ров переписывается в блок 24.

На пятом такте блок 11 выбирает из блока 25 величину z, которая с блоком 12 через коммутатор 19 подается на входы перемножителя 22. На входы перемножителя блоком 12 с помощью коммутатора 25 подается величина G, с блока 17. Блок 26 с по- гопц.ю коммутаторов 31 и 32 подключает выходы перемножителя 22 на входы групп 23 и 33 -триггеров. В результате в группу 23 триггеров записьшаетс локатор Х .B группе 33 триггеров локатор X складывается по модулю два с локатором Х, который был йаписан на третьем такте.

На шестом такте с помощью блока I1 локатор Xj с группы 23 триггеров 1|1ереписьгоается в блок 24, а ( i б группы 33 триггеров в блок 25.

На седьмом такте блок 26 с помощь Коммутатора 31 подключает выходы ре- liHCTpa 15 на входы группы 23 тригге- l|oB, в которую записьшается S. , На восьмом такте блок 11 выбирает блока 24 локатор ошибок Х. Блок 1|2 с помощью коммутатора 18 подаёт первые входЫ перемножителя 22 ло- Х|, а с помощью коммутатора 9 на вторые входы перемножителя 2|2 - синдррм Sjj. Блок 26 с помощью к;оммутатора 3 подключает выходы пе- р1емножителя 22 па входы группы 23 т|риггеров. В результате на выходе перемножителя 22 получают величину

jX, которая складьшается по модулю два с синдромом S, , записанным в т зиггерах 23 группы.

На девятом такте полученная величина S(jXj+ S, переписьгаается в блок 24.

I На десятом Факте блок 12 с по- м|эщью коммутатора 18 подключает вы- хЬды блока 24 на первые входы пере - множителя 22, а с помощью коммутаторе 19 - выходы блока 13 на вторые входы перемножителя 22. Одновременно блок 21 с помощью блока 20 коммутиру- et, подключает выходы блока 25 на в:|соды блока 13 блок 26 с помощью коммутатора 32 - выходы перемножителя 22 на входы группы 33 триггеров. Блок I1 выбирает из блока 24 величину Sj,Xj+ S, , кЬторая поступает на первые: входы Перемноткителя 22, а из блока 25 - величину Х Х, являющуюся адресом для блока 13, по которому записана величина 1/(Х,+ Х), поступающая на вторые; входы перемножителя 22. Следовательно, на выходе перемножителя получают значение оюибС V 4-

ки Y. v которое записьта- л, . А/1

ется в группу 33 триггеров.

5 0 5

0

5

0

5

На одиннадцатом такте величина YJ с помощью блока 11 переписьгоает- ся в блок 25.

На двенадцатом такте блок 26 с помощью коммутатора 32 подключает выходы регистра.14 на входы группы 33 триггеров, в которую записьгаает- ся величина S. Одновременно локатор Х, являющийся адресом искаженного элемента, подается на буферный накопитель 2, в результате разряды искаженного символа с адресом Х подаются на блок 3 сумматоров по модулю двaJ на вторые входы которых подается ощибка с помощью блока i1. При сложении разрядов искаженного символа с YJ происходит исправление и исправленный элемент вновь записывается в буферный накопитель 2 по тому же адресу.

На тринадцатом также, аналогично как и на десятом такте, на входы группы триггеров 33 подают величину YJ , которая складьгеается по модулю два с величиной , записанной на двенадцатом такте.

Полученная в результате величина Yj + БД на четырнадцатом такте переписывается в блок 25.

На пятнадцатом такте производят исправление искаженного символа с номером Xj аналогично тому, как это делают на двенадцатом такте.

Рассмотрим процесс исправления двухкратных ошибок на конкретном примере для кода Рида-Соломона длины 7 с образующим полиномом 9(х) (х+ + l)(x+oi)(x +ei)(x +oi ) длиной 7, в котором имеют 3 информационных и 5 проверочных .символов поля GF(2), каждьй из которых содержит 3 двоичных разряда в соответствии с табл.1.

Таблица 1

Т

Символ поля GF(2 )

Двоичный вид символа СГ(2Ъ

50

О О

1 d°

О о

ot

oi.

1о о

о 1 1

71432787

Продолжение та6л.1

1

О

Допустим при передаче по каналу связи слова кода Рида-Соломона OOloC ci cit u на позициях с номерами 1 произошли ошибки и в буферный накопитель 2 поступает слово ООП .

.С выходов блока 5 синдромы S,

Л S,

ui, S об

и S, 1 подают на входы блока6. Кроме того,

Sg и S| записьгааютсоответственно в

регистры 14 и 15. Свыходов блока 6 величины

G,

.SiSit-SoSj-

S, + SoSj2

.

Адресные входы блоков 27, 28

Вьйсод данных блока 27

ul,

ei

занесены двоичная последовательность DeI),D2 - 100, что соответствует z

.; ef ОО irit

oi , в блоке 28 - 101, что соответствует . Величина z

и Z,

двоичном виде записьшают соответственно в блок 23 и блок 33 группы из 3 триггеров.

На втором такте величину z(100) записьгоают в блок 24, а z (101) - в блок 25.

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

SiS3+ Si -oг.

oC

S,+ So Si

в

10

15

поступают на входы соответственно регистра 16 и регистра 17, Из блока 6 в блок 7 вьщается сигнал, открывающий элемент И 9 и через него поступают тактовые импульсы на счетчик to, выходы которого подключены к адресным входам блоков 11,12,21 и 26 постоянной памяти.

На первом такте с выхода перемножителя 22

У

Gz

S ® °

20

25

ичном виде 010 поступает на адресные входы А(, А , А блоков 27 и 28 постоянной памяти, в которых по адресу для всех возможных значений у занеЛ

сены соответствующие им значения D

Dj, Dj корней уравнения (4) z, (в блоке 27) и Zj, (в блоке 28) в соответствии с табл.2.

Таблица2 Выход данных блока 28

О О

oL

23 и 33.

На четвертом такте величину Х переписьтают в блок 24.

На пятом такте с выходов перемножителя 22 локатор Х 1 в двоичном виде 001 записьшают в группы 23 и 33 триггеров, причем в группе 33 триггеров Х и Х сумми РУЮтся по модулю два.

На шестом такте локаторов Х в двоичном виде 001 записывают в блок 24, а сумму (Х,+ Х,,) в двоичном виде 010 - в блок 25.

На седьмом такте в группу триггеров 23 записьгаают Sj в двоичном виде 111, что соот;ветствует значению et, которую на восьмом такте в группе 23 суммируют по модулю два с дво1«ной

.последовательностью - 110, соответствующей величине SpX; 1 «(,

поступающей .с выхода перемножителя 22. Полученную сумму S, Ы- -t- + ut 1 в двоичном виде 001 перепи- сьгоают в блок 24.

На десятом такте с выходов перемножителя значение ошибки

Д 4

Х,-ь X,

1

об

В ДВОИЧНОМ виде 101 записьгоают в группу 33 триггеров, которую на одиннадцатом такте переписьшают в блок 25. На двенадцатом такте в блоке 3 сум- ;маторов по модулю два проводят сло- :жение искаженного символа 1 с номером Y, ft и исправленный элемент Iсимвол имеет значение } + oi а , Тринадцатый такт аналогичен деся- |тому. При этом в группе 33 триггеров |величина Y d суммируется с вели1ЧИНОЙ S

д „ ,записанной на двенадoi

щатом такте. Полз енное значение

;Y. Y.

S, oi« +

«6 на четырнадцатом такте переписьшают в блок 25, ; На пятнадцатом такте, как и на две- |надцатом, производят исправление сими исправ-

|вола с номером Х od

ленный символ имеет значение od

Таким образом, после исправления

в буферном накопителе 2 занесено очищенное от двух ошибок слово OOld ti ui oi.

При возникновений однократных ошибок счетчик 10 устанавливается сигналом Установка с второго управляющего входа блока 6 в 16-е состояние, В этом состоянии блок 26 с по- . мощью коммутатора 31 коммутирует выходы регистра 17 на входы группы 23 триггеров, в которые записывается величина Х G,, ас помощью коммутатора 32 - выходы регистра 14 -на входы группы 33 триггеров, в которую записывается величина Y S.

На семнадцатом такте производят запись величины Х -в блок 24, а ве- Личины Y| - в блок 25. Исправление однократной ошибки осуществляют так же, как и двухкратных.

Формула

10 3 о

бретения

0

15

0

25

30

35

40

45

50

55

Устройство для исправления ошибок, содержащее запоминающий блок, вькоды которого подключены к входам . генератора синдромов и первым входам буферного на1 опителя, выходы которого подключены к третьим входам блока из m сумматоров по модулю два, где га - размерность поля (3F(2) Галуа, выходы которого подключены к вторьм входам буферного накопителя и являются информационными выходами устройства, йЬкоДы генератора синдромов подключены к входам накопителя синдромов, первые, вторые, третьи и четвертые выходы которого соединены с соответствующими входами вычислителя элементарньтх симметрических функций и входами дешифратора ошибки, первый выход которого подключен к пятому входу вычислителя элементарных симметрических функций, второй выход соединен с третьим входом буферного накопителя и является контрольным выходом устройства, блок вычисления ошибок, включающий элемент И, с четч1Ж импульсов, первый - третий коммутаторы, первьш - третий блоки постоянной памяти, перемножитель, первую группу из m триггеров, первый и второй блоки оперативной памяти и первый, второй, третий и четвертый регистры, выход элемента И подключен к счётному входу счетчика импульсов, выход которого соединен с входами первого и второго блоков постоянной памяти, вькод первого регистра подключен к первому входу второго коммутатора, выходы второго и третьего регистров подключены соответственно к первому и второму входам первого коммутатора, выход четвертого регистра подключен к третьему входу первого коммутатора и второму входу второго коммутатора, вьгходы третьего коммутатора подключены к входам третьего блока постоянной памяти, выход которого соединен с третьим входом второго коммутатора, первый и второй выходы второго блока постоянной памяти подключены к четвертым входам соответственно первого и второго коммутаторов, выходы которых соединены с соответствующими входами перемножителя, первьш и- .второй .выходы первого блока постоянной памяти подключены к первым входам соответственно первого и второго блоков оперативной памяти, выходы первой группы из m триггеров подключены к вторым входам первого блока оперативной памяти, выходы которого подключены к пятым входам первого коммутатора и четвертым входам буферного накопителя, выходы второго блока оперативной памяти соединены с . первыми входами третьего коммутатора и вторыми входами блока из m сумматоров по модулю два, первый вход элемента И и установочный вход счетчика импульсов подключены соот- ветственно к первому и второму управляющим выходам вычислителя элементарных симметрических функций, входы первого-четвертого регистров подключены соответственно к первому и вто- рому выходам накопителя синдромов и первому и второму информационным выходам вычислителя элементарных симметрических функций, второй вход элемента И является тактовым входом уст-

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

Бторы входам второго блока оператив ной памяти, выходы четвертого и пято го блоков постоянной памяти объединены и подключены к выходу счетчика импульсов, первый и второй выходы четвертого блока постоянной памяти подключены соответственно к первому входу четвертого коммутатора и второ му входу третьего коммутатора, трети вход которого соединен с выходом пятого блока постоянной памяти, вход которого объединен с первым входом пятого коммутатора и подключен к выходу четвертого регистра, первый вход гаестого коммутатора.соединен С выходом первого регистра, выходы перемножителя подключены к вторым входам, четвертого - шестого коммутаторов , первьй и второй выходы шестого блока постоянной памяти подключены к третьим входам соответственно шестого коммутатора и пятого коммутатора, четвертый вход которого соединен с выходом второго регистра, выход четвертого коммутатора подключен к входам седьмого и восьмого блоков постоянной памяти, выходы которых объединены соответственно с выходами

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

Бторы входам второго блока оперативной памяти, выходы четвертого и пятого блоков постоянной памяти объединены и подключены к выходу счетчика импульсов, первый и второй выходы четвертого блока постоянной памяти подключены соответственно к первому входу четвертого коммутатора и второму входу третьего коммутатора, трети вход которого соединен с выходом пятого блока постоянной памяти, вход которого объединен с первым входом пятого коммутатора и подключен к выходу четвертого регистра, первый вход гаестого коммутатора.соединен С выходом первого регистра, выходы перемножителя подключены к вторым входам, четвертого - шестого коммутаторов , первьй и второй выходы шестого блока постоянной памяти подключены к третьим входам соответственно шестого коммутатора и пятого коммутатора, четвертый вход которого соединен с выходом второго регистра, выход четвертого коммутатора подключен к входам седьмого и восьмого блоков постоянной памяти, выходы которых объединены соответственно с выходами