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

1

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

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

На фиг. представлена блок-схема устройства; на фиг.2 - структурная схема блока вычисления ошибок.

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

Блок 7 вычисления ошибок состоит из элемента И 9, счетчика 10, первого, второго и третьего блоков 11-13 постоянной памяти, первого, второго, третьего и четвеито- го регистров 14-17, первого, второ- го и третьего коммутаторов 18-20, дешифратора 21, перемножителя 22, группы из m триггеров 23, первого и второго блоков 24 и 25 оперативной памяти, первого, второго и третьего элементов НЕ 26-28 и группы из т-2 сумматоров 29 по модулю два. Входные и выходные шины запоминающего блока 1, буферного накопителя 2, блока 3 сумматоров по модулю два, генератора 4 синдромов, накопителя 5 синдромов, вычислителя 6 элементарных симметрических функций, блока 7 вычисления ошибок, а также регистров 14-17, коммутаторов 18-20, перемножителя 22 и блоков 24 и 25 оперативной памяти содержат по ш. цепей. Счетчик 10 имеет пять разрядов, адресные входы первого и второго коммутаторов 18 и 19 содержат по три разряда.

Особенность четвертого регистра 17 состоит в обеспечении режима сдвига в сторону последнего т-го , разряда, для чего выход этого разряда соединен с входом первого разряда этого регистра 17.

Шестые и седьмые входы первого коммутатора 18 двумя мпадшими разрядами подключены соответственно к входам и выходам элементов НЕ 27 и 28, осталыые разряды этих кодов соединены соответственно с прямыми и инверсными выходами сумматоров 29

168321

. по модулю два группы из т-2 таких сумматоров.

Устройство предназначено для работы с кодами Рида-Соломона, в 5 каждой кодовой комбинации которого имеется К информационных и п-К проверочных символов, каждый из. которых содержит m двоичных разрядов, где m - размерность поля GF(2 Га- 10 луа. Образующий полином кода для исправления двухкратньтх ошибок

g(x)(x+i)(xw )()(х+о) (1)

15 где оС - примитивный элемент поля GF(2) Галуа.

Цпкна кода 1. В запоминающем блоке 1 с помощью образуюшего полинома дСК.) запи20 сывается кодовая комбинация G(X) . При передаче по каналу связи или при записи и считывании с блока 1 на G(X) накладывается вектор ошибок Е(Х). В результате на выход блока 1

25 поступает последовательность

R(X) G(X) + Е(Х)(2)

Вектор ошибок представляет из себя полином, j-я позиция которого e(jTb , j-й локатор ошибок, обозначаем51й Х . При этом значение ошибки У является символом из поля GF(2 ). Сле- доватепьно полином ошибок имеет вид

35

Е(Х) EyjX ,

(3)

где суммирование производится по всем позициям ошибок.

Кодовая комбинация всегда делится без остатка на д(Х), т.е. G(j )0 для 0)3. Из (2) можно получить

R{o()G{o« )+E(ot )E(ot ) для

(4)

Для обнаружения и исправления ошибок необходимо полученную комбинацию символов R(X) разделить на д(Х). Из (4) видно, что это . аналогично делению Е(Х) на д(Х),Если деление произведено без остатка, то делается заключение об отсутствии ошибок. Остаток от деления является синдромом ошибок Sj. По синдромам производится отыскание и исправление ошибок. При

делении К(х) на составные множители g(x) получают. So,S 1,3, 83. При. JTOM S- . Е(« ) R(ot ) при X 0/. Отсюда имеем

Sr-E(oC )Y:yjU- ) iryiXJ (5)

По синдромам находится многочлен локаторов ошибок

0(Х) /7(Х-Х|,)Х + ...+Gp,(6)

исправляемых ошибок. При опре деляется О, по выражениям (8), где G - элементарная симметрическая функция. При определяются G 5 и функциям (9). Последовател ность работы вычислителя 6 при этом следующая. Если S, О, то и определяется G -S/ /S ; , и Зз+ ,. При 83+ 10 О и X, G, У1 So. Определе ние единственного локатора и значе ния ошибки на этом заканчивается.

Ь

где В - число ошибок;

X - i-й локатор ошибок;

Gi - элементарные симметрические

функции i-й степени от локаторовЕсли О-или и S О, то t

ошибок... определяется Д , G

Величины G; определяются из следую-15 ( , G.. (,)/ А

щего рекуррентного соотношения GiSi + e-i + - .&e-i Si.i+SeS; 0 (7)

Если переписать (7) для случаев исправления однократной и двух- к,ратной ошибок, то получим:

- .1 1J

S +Gi3o 0; 3.L+GiSi 0; 33+GiS О,

,

3 7.+G.| S/) 0; 3j+G, 0.

Устройство для исправления ошибок зо работает следуюшям образом.

Закодированные избыточным (п,К)- кодом данные считываются из запомина- ющего блока 1 в буферный накопитель 2 и генератор 4 синдромов, где п (8)

(9)

и D Зз+ Gt3i, Если D 0, то i- 2. Если D О или если Зд 3 О и S О, то , при эт принятьш блок информации стирается

20 Если в вычислителе 6 определено что , то с первого управляющего выхода в блок 7 вьщается сигнал на элемент И 9. Через него на счетчик 10 начинают поступать тактовые им-

25 пульсы Т. К выходам счетчика 10 под ключены входы блока 12,первые и вто рые выходы которого задают адреса с ответственно для коммутаторов 18 . и 19.

Вначале опишем процесс расчета и преобразований принятых символов, каждый из которых содержит m бит в поле GF(2) Галуа. Все символы поля GF(2) можно представить в ви- «де степени примивного элемента Of .

- - --- -f ч. . -г ff 1 v,,. л J. fU. ААj

длина кодового блока в элементах по- Если примитивный элемент х таков, ля GF(2), К - длина информационной что элементы of, Of; ,0 ,о(, ... , части блока. В генераторе. 4 путем деления на составные части образующего полинома g(x) (X+1)(Х+о ) / х{Х+о(), получают синдромы ошибок So, S, S, Sj, которые записываются в накопитель 5 синдромов. На выходе накопителя 5 подключен дешифратор 8 ошибок, который функционирует как элемент ИЛИ. Если при делении получается остаток, то он содержит хотя бы одну 1. Тогда на пер вом выходе дешифратора 8 появляется сигнал Ошибка. Если S S, 82. 83 О, то на втором выходе дешифратора 8 появляется сигнал Нет опшбки и кодовый блок выдается потребителю путем подачи сигнала Считывание на управляющий вход буферного накопителя 2.

Сигнал Ошибка дает разрешение для работы вычислителя 6. При этом вначале определяется кратность i.являются линейно независимыми над GF(2), то они образуют нормальный базис. В таблицах неприводимых мно гочленов можно выбрать примитивный многочлен соответствушций степени, корни которогоо( линейно независимы, где ,1,2,..., т-1. Тогда . произвольный элемент GF( 2) мо45 жет быть представлен как некоторая степень а( ив виде разложения по нормальному базису

50

т-1

т 11т,

I -О

(г)

(10)

)

Представление элементов в виде разложения по нормальному базису -, удобно при возведении .в степень вида 2, Например, если элемент

Т Г« ОС ... Y..,oC

Ю-1

16832Л

исправляемых ошибок. При определяется О, по выражениям (8), где G - элементарная симметрическая функция. При определяются G 5 и функциям (9). Последовательность работы вычислителя 6 при этом следующая. Если S, О, то и определяется G -S/ /S ; , и Зз+ ,. При 83+ 10 О и X, G, У1 So. Определение единственного локатора и значения ошибки на этом заканчивается.

Ь2

Если О-или и S О, то t

-15 ( , G.. (,)/ А

зо

и D Зз+ Gt3i, Если D 0, то i- 2. Если D О или если Зд 3 О и S О, то , при этом принятьш блок информации стирается.

20 Если в вычислителе 6 определено, что , то с первого управляющего . выхода в блок 7 вьщается сигнал на элемент И 9. Через него на счетчик 10 начинают поступать тактовые им-

25 пульсы Т. К выходам счетчика 10 под- , ключены входы блока 12,первые и вторые выходы которого задают адреса со ответственно для коммутаторов 18 . и 19.

Вначале опишем процесс расчета и преобразований принятых символов, каждый из которых содержит m бит в поле GF(2) Галуа. Все символы поля GF(2) можно представить в ви- «де степени примивного элемента Of .

j

Если примитивный элемент х таков, что элементы of, Of; ,0 ,о(, ... ,

являются линейно независимыми над GF(2), то они образуют нормальный базис. В таблицах неприводимых многочленов можно выбрать примитивный многочлен соответствушций степени, корни которогоо( линейно независимы, где ,1,2,..., т-1. Тогда произвольный элемент GF( 2) может быть представлен как некоторая степень а( ив виде разложения по нормальному базису

Если примитивный элемент х таков, что элементы of, Of; ,0 ,о(, ... ,

т-1

т 11т,

I -О

(г)

(10)

Если примитивный элемент х таков, что элементы of, Of; ,0 ,о(, ... ,

Представление элементов в виде разложения по нормальному базису удобно при возведении .в степень вида 2, Например, если элемент

Т Г« ОС ... Y..,oC

Ю-1

озвести в квадрат, то получим Y ()(ri°(....

4vH...,. - 5 if.o.;--v...o.-V ou

посколькуo f - оС . Таким , возведение в квадрат означает цикли- fo ческий сдвиг элемента на один разряд; вправо.

Для нахождения локаторов ошибок нужно решить .квадратное уравнениеt5

С(Х) {Х+Х)(Хч-Хд)Х% Ц +G, (12 У ,

-где G-, Xi+ Xj, Gi- . Корни уравнения

xV + G, О

(13)

и являются локаторами ошибок Х и Х.

Приведем уравнение (13) к каноническому виду заменой . В ре- 25 зультате получим

Z + GI/G 0..

Если обозначить , то получим. -30

, Z + Z +К о (14) Корни уравнения (14) имеют вид

,(o,l,,YnY,,...,Y,.-r,n-i).r

35

(,,..-,1,1С7 - Ы:

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

При обнаружении ошибок из блока 6 в блок 7 вьщается сигнал, который открывает элемент И 9. Через него начинают поступать тактовые им- пульсы Т на счетчик 10. На выходы счетчика 10 подключен дешифратор 21,

На первом такте срабатывает дешифратор 2, сигнал с первого выхода которого сдвигает на 1 разряд вправо ,. содержимое регистра 17. При сдвиге вправо величина G, записанная в регистр 17, возводится в квадрат (С) . На втором такте блок 12 под-j ключаёт с помощью первого коммутатора 18 на пёрйые входы перемножителя 22 выходы регистра 16, а илходы ре- гистра 17 через коммутатор 20 и блок 13 - на вторую входную шину

перёмножителя 22. Значение G, записанное в регистре 17, является адресом для блока 19. В результате на выходе блока 13 появляется запи- санная в нем по этому адресу величина I/G. Следовательно, на первых входах перемножителя 22 появляется величина 0,, а на вторых - величина 1/G., . На этом же такте происходит умножение G ра 1/G и на выходе перемножителя 22 получают величину , которая записывается в триггеры 23 группы. На третьем такте с первых вькодов блока 11 на блок 24 подается сигнал записи и вьщается первый адрес, по которому величина записывается в блок 2

На четвертом такте блок 1I выбирает из блока 24 величину , в результате преобразования которой в соответствии с (15) на входах элементов 27 я 28 к прямых выходах сумматоров 29 группы получается величина Z, которая подключается блоком 12 с помощью коммутатора 18 на первые входы перемножителя 22. Одновременно блок 12 с п омощью коммутатора 19 подключает выходы регистра 17 на вторые входы ,перемножи- тёля 22. Таким образом, на выходе последнего получен локатор ошибок Х. 2fG, которьй записывается в триггеры 23 группы. На пятом такте локатор X с помощью блока 1I переписывается в блоки 24 и 25.

На шестом такте блок II снова выбирает из блока 24 величину , в результате преобразования кото- )ой в соответствии с (16) на инверсных выходах элементов 27 и 28 и сумматоров 28 группы получается величина Z , которая подключается блоком 12 с помощью комментатора 18 на первые входы . перемножителя 22.Одновременно блок 12 с помощью коммутатора 19 подключает выходы регистра 17 на втрые входы перемножителя 22. Таким образом, на выходе последнего получен локатор ошибок X который записывается в триггеры 23 группы. На седьмом такте величина Xj с помощью блока П переписывается в блоки 24 и 25. На этом заканчивается определение локаторов ошибок. Значения ошибок легко найти по Х, Х,,, SQ и S., Дпя этого необходимо осушествить Ъреобразова,ния в соответствии с уравнениями

i

УгХг. S

У X - + S - f /

откуда

у . V t §t

- Х7 + Х|+Х,Х;

. ,(17)

Определение У начинается с восьмого такта. Блок 12 подключает с помощью коммутатора 18 на первые входы перемножителя 22 выходы регистра 14, блок 1 Г выбирает из блока 25 величину Хг, а блок 12 подклю- чает ее с помощью коммутатора 19 на.вторые входы перемножителя 22. В результате на выходе последнего получается величина SoX,, которая записывается в триггеры 23 группы. На девятом такте блок 12 подключает выходы регистра 15 с помощью коммутатора 18 на первые входы перемножителя 22,а выход элемента 26 с помощью коммутатора 19 - на вторые входы перемножителя 22. В результате на выходе перемножителя 22 получают величину of S S, которая складывается по модулю, 2 с величиной S(,X J, записанной в триггерах 23 группы. Полученная величина So Х, S на десятом такте переписывается в блок 24.

На 11-м такте блок 11 выбирает из блоков 24 и 25 локатор ошибок Х. Блок 12 с помощью коммутатора

18подклгачает этот локатор на первые, а с помощью коммутатора

19- на вторые входы перемножителя 22 о Полученная на его выходе величина Х записывается

в триггеры 23 группы. На 12-м такте;-.ёлок 1 1 выбирает из блока 24 величину X,, а из блока 25 - величину X,j. Эти локатсфы ошибок (Х, Х.) подаются с помощью блока 12 и коммутаторов 18 и 19 соответственно на периле и вторые входы перемножителя 22. На выходе его будет получена величииа Х;,Х, которая складывается по модулю 2с величиной Х, записанной в триг- геры 23 группы.

На 13-м такте блок 11 выбирает из блока 25 величину , S и блок 12 подает ее с помощью коммутатора 18 на первые входы пере-У, --:

множителя 22, Сигналом с второго выхода дешифратора 21 с помощью

коммутатора 20 величина Х -f . J хранящаяся в группе триггеров 23, подается на вход блока 13,на выходе которог9 получают величину ,Xj. На этом же 13-м такте эта величина с помощью блока 12 и ком10 мутатора 19 подается на вторые входы перемножитёля 22, на выходе которого получают значение ошибки

ц Xi хГ

На 14-м такте значение У переписывается в блок .25.

Совершенно аналогично, начиная с 15-го такта, вычисляется значение ошибки У по формуле ( I 7). На вычис- ление Уг тратится также 7 тактов

и на 21-м такте этот локатор записывается в блок 25,

Таким образом, полученные локаторы ошибок X и X - 3 аписаны в блок 24, а значения ошибок У и У - в блок 25.

На 22-м такте величина X,, являющаяся адресом искаженного элемента, подается на буферный накопитель 2, в результате разряды искаженного 0 символа с адресом Х подшотся на блок 3 сумматоров по модулю 2, на вторые входа которых подается ошибка с помощью блока 11. При сложении разрядов искаженного символа с У 5 происходит исправление и исправленный элемент вновь записывается в бу- буферный накопитель 2 по тому же адресу. Исправление элемента X происходит на 23-м такте аналогнч0 но.

1

При возникновении однократных ошибок счетчик 10 устанавливается сигналом Установка с второго уп, равляющего выхода вычислителя 6 в 24-е состояние. В этом состоянии блок 12 подключает с. помощью коммутатора 18 величину о на первые, а с помощью коммутатора 19 величину на вторые входы перемножителя 22. Величина 0 G записывается в триггеры 23 группы и на 25-м состоянии счетчика 10 переписывается :в блок 24. В данном случае Х, G;, На 26-м соСтояшш счетчика Ю блок 12 подключает на первые входы перемножителя 22 синдром S0, а на вторые входы перемно- « жителя 22 - значение oL , Значение

записывается в триггеры 23 группы и на 27-м состоянии счетчика 10 переписывается в блок 25, Здесь У Зй. Исправление однократной ошибки осуществляется так же, как и двухкратных.

Формула изобретения

Устройство для исправления ошибок, содержащее запоютнающий блок, генератор синдромов, накопитель синдромов, вычислитель элементарных симметрических функций, дешифратор ошибки, блок вычисления ошибок, буферный накопитель и блок из m сумматоров по модулю два, выходы которых соединены с выходной пшйой, а первые входы подключены к соответствующим выходам буферного накопителя, первые входы которого объединены с соответствующими входами генератора синдромов и подключены к соответствующим выходам запоминающего блока, выходы генератора синдромов соединены с соответствующими входами накопителя синдромов, первые, вторые, третьи и четвертые выходы которого соединены с соответствующими входами вычислителя элементарных симметрических функций и с входами дешифратора ошибки, первый выход которого подключен к управляющему входу вычислителя элементарных симметрических функций, второй выход дешифратора ошибки является контрольным выходом устройства, о т л и - чающееся тем, что, с целью повьш1ения быстродействия, блок вы- числения ошибок состоит из четырех регистров, счетчика, дешифратора, трех коммутаторов, трех блоков постоянной памяти, двух блоков оперативной памяти, группьь из m триггеро перемножителя, группы из т-2 сумматоров по модулю два, трех элементов НЕ и элементами, первый вход которого соединен с тактовой шиной, выход подключен к счетному входу счетчика, второй вход элемента И и установочный вход счетчика подключены соответственно к первому и второму управляющим выходам вычислителя элементарных симметрических функций, выходы разрядов счетчика соединены с соответствующими входам дешифратора, первого и второго блоков постоянной памяти, первые и

0

5

0

5

0

5

0

5

вторые выходы первого блока постоянной памяти подключены к управляющим входам соответственно первого и второго блоков оперативной памяти, входы первого и второго регистров соединены с соответствующими выходами накопителя cиндlffo- мов, входы третьего и четвертого регистров подключены соответственно к вторым и первым выходам вычислителя элементарнЁ1х симметрических функций, выходы первого, второго и третьего регистров подключены к со- отв ;тствуюш 1м входам первого коммутатора, выходы которого соединены с соответствующими первыми входами перемножителя, вторые входы которого подключены к соответствующим выходам второго коммутатора, первые входа которого соединены с выходами . третьего блока постоянной памяти, входы которого подключены к выходам третьего коммутатора, первые входы которого объединены с соответствующими вторыми входами второго коммутатора и подключены к соответствующим выходам четвертого регистра, выход последнего разряда которого соединен с входом его первого разряда, а управляюш 1Й вход подключен к первому выходу дешифратора, вто- рой выход которого соединен с управляющим входом третьего KOMNryTaTopa, вторые входы которого объединены с соответствующими информационными входами первого и второго блоков оперативной памяти и подключены к выходам соответствующих триггеров группы, инверсный выход каждого из которых соединен с его входом, синх- ронизнруюлще входы триггеров группы подключены к соответствуюшрм выходам перемножителя, выходы второго блока оперативной памяти подключены к соответствующим вторым входам блока из m сумматоров по модулю два и третьим входам второго коммута- .тора, четвертые входы которого объединены с четвертыми входами.первого коммутатора и через первый элемент НЕ соединены с шиной нулевого потенциала, выходы первого блока оперативной памяти подключены к соответству- юш;им вторым входам буферного накопителя и пятым входам первого коммутатора, адресные входы которого соединены с соответствующими первыми ; вьссодами второго блока постоянной

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

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

Фе/г

s4

Изобретение относится к вычислительной технике и может быть использовано при создании устройств, корректирующих ошибки в передаваемой или хранимой информации. Цель изобреа ния - повышение быстродействия. Устройство содержит запоминаю- пщй блок, буферный накопитель, блок из m сумматоров по модулю два, генератор синдромов, накопитель синдромов, вычислитель злементарных симметрических функций, дешифратор ошибок и блок вычисления ошибок, состоящий из элемента И, трех блоков постоянной памяти, четырех регистров, трех коммутаторов, дешифратора, перемножителя, группы из ш триггеров, двух блоков оперативной памяти, трех элементов НЕ; и Группы из т-2 сумматоров по модулю два. 1 з.п. ф-лы. 2 ил. i (Л с ю о сх 00 to