Устройство для исправления ошибок

 

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

СОЮЗ ССВЕТСНИХ

ОО.И ЛЮЮ

РЕСПУБЛИН

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

ПО ДЕЛАМ ИЗОБРЕТВ1ИЙ И ОТНРЫТИЙ

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

К АВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ВСРГОИ) рщ р (21) 3765873/24-24 (22) 04.07.84 (46) 07.03.86. Бюл. 11 9 (71) Институт проблем передачи информации АН СССР и Пензенский политехнический институт (72) В.А.Зиновьев, В.В.Зяблов, Б.А.Савельев, иностранцы С.М.Додунеков и В.М.Георгиева (SG), (53) 681.325.63 088.8) (56) Авторское свидетельство СССР

У 913383, кл. G 06 F 11/08, 1978.

Патент США Р 4142174, кл. G 06 F 11/12, 27.02.79. (54) УСТРОЙСТВО ДЛЯ ИСПРАВЛЕНИЯ ОШИБОК (57) Изобретение относится к вычислительной технике и может быть ис„„SU„„1216832 A

<5р Н 03 М 13/00 пользовано при создании устройств, корректирующих ошибки в передаваемой или хранимой информации. Цель изобретения — повышение быстродействия. Устройство содержит запоминающий блок, буферный накопитель, блок из m сумматоров по модулю два, генератор синдромов, накопитель синдромов, вычислитель элементарных симметрических функций, дешифратор ошибок и блок вычисления ошибок, состоящий из элемента И, трех бло.ков постоянной памяти, четырех регистров, трех коммутаторов, дешифратора,перемножителя, группы из m триггеров, двух блоков оперативной памяти, трех элементов НЕ;и группы из ш-2 сумматоров по модулю два.

1 з.п. ф-лы. 2 ил.1 1

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

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

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

Устройство содержит запоминающий блок l, буферный накопитель 2, блок

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

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

5 синдромов, вычислителя б элеменФ тарных симметрических функций, блока 7 вычисления ошибок, а также регистров 14-17, коммутаторов 18-20„ перемножителя 22 и блоков 24 и 25 оперативной памяти содержат по ш цепей, Счетчик 10 имеет пять разрядов, адресные входы первого и второго коммутаторов 18 и 19 содержат по три разряда.

Особенность четвертого регистра

17 состоит в обеспечении режима сдвига в сторону последнего ш-го

Разряда, для чего выход этого разряда соединен с входом первого разряда этого регистра 17.

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

216832 2 (2) R(X} С (Х) + Е (Х) 30

Е(Х) = ) У„Х

40 (4) 45

Для обнаружения и исправления ошибок необходимо полученную комбинацию символов R(X) разделить íà g(X). Из (4) видно, что это . аналогично деле.нию Е(Х) íà g(X).Åñëè деление произ50 ведено без остатка, то делается зак5

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

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

g (X) = (X+1) (Х+ ) (Х+С ) (X+ ) (1) где с(— примитивный элемент поля

GF(2 ) Галуа.

Длина кода и 2 — 1.

В запоминающем блоке 1 с помощью образуюшего попинома 9(Х) записывается кодовая комбинация G(X).

При передаче по каналу связи или при записи и считывании с блока 1 на ((Х) накладывается вектор ошибок

Е(Х). В результате на выход блока поступает последовательность

Вектор ошибок представляет из себя полином, j-я позиция которого еЧть

)-й локатор ошибок, обозначаемый Х .

При этом значение ошибки У, является символом из поля GF(? ). Сле- довательно полином ошибок имеет вид где суммирование производится по всем позициям ошибок.

Кодовая комбинация всегда делится без остатка на g(X), т.е. G(j )-"0 для Оь!63. Из (2) можно получить

R(o()=6 (с )+Е(М ) =E(d. ) для 041<3 лючение об отсутствии ошибок. Остаток от деления является синдромом ошибок Б;. По синдромам производится отыскание и исправление ошибок. При делении R(X) на составные множители

g(x} получают. S S <, S z S . При, этом Я: =: Е(оЕ } = В(оС } при Х =о(.

Отсюда иа имеем

12! 6832 4

G(X) = g(X-Х;, ) =Х +G„X +... +6Р, (6!

l где 1 — число ошибок;

Х вЂ” i-й локатор ошибок, G — элементарные симметрические функции i-й степени от локаторов ошибок.

Величины G; определяются из следую щего рекуррентного соотношения

S i+e +G; S1-е-1+" +Cue-1 Si +Se ь, -О (7) . (8) 40 нормальному базису

5;= (К ) =, У„(С") = у; Х„ (5) По синдромам находится многочлен локаторов ошибок

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

Х-=1;

Si+GcSo= 0s

S +G,S„= О;

Бз+61$1= ОУ

2,-=2, Б +Gq $1+Gg o О j (9)

sÚ+G1Б,+62 $1= 0

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

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

2 и генератор 4 синдромов, где n— длина кодового блока в элементах поля GF(2 ), К вЂ” длина информационной части блока. В генераторе. 4 путем деления на составные части образующего полинома g(X)=(X+1)(X+< )

x(X+oC ), получают синдромы ошибок

Бо. Б 1 ° Бт Бз которые записываются в накопитель 5 синдромов. На выходе накопителя 5 подключен дешифратор 8 ошибок, который функционирует как элемент ИЛИ. Если при делении получается остаток, то он содержит хотя бы одну 1. Тогда на первом выходе дешифратора 8 появляется сигнал Ошибка". Если Бо

= Б, = S = S> = О, то на втором выходе дешифратора 8 появляется сигнал "Нет ошибки" и кодовый блок выдается потребителю путем подачи сигнала "Считывание" на управляющий вход буферного накопителя 2.

Сигнал "Ошибка" дает разрешение для работы вычислителя 6. При этом вначале определяется кратность Я. исправляемых ошибок. При 1 =1 определяется G, по выражениям (8), где

G — элементарная симметрическая функция. При Р=2 определяются G„ и G по функциям (9 ) . Последовательность работы вычислителя 6 при этом следующая. Если S Ф О, то Х)1 и определяется G =-$ /S ; S + 6 $, и $ + 6„$>. При Б G„S„= Бз+ 6 sz=

1p = О &1 и X <= G<, У, = So. Определение единственного локатора и значения ошибки на этом заканчивается.

Если S +Äs,ф О или S 0 и S 4 00, то f? 2 и определяется 6 = $ + $ $, G

15 (S S + Sos ) h G (1$З+$1) и D = Бэ+ G S + 6 $ . Если D =О, то . = 2. Если D g О или если S» = — S„= О и $ О, то Х)2, при этом принятый блок информации стирается.

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

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

Вначале опишем процесс расчета и преобразований принятых символов, каждый из которых содержит m бит в поле GF(2 ) Галуа. Все символы поля GF(2 ) можно представить в вивде степени примивного элемента 0(Если примитивный элемент таков, что элементы Ф,(X,N N,..., с(" " т являются линеино нЕзависимыми над

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

Представление элементов в ви де разложения по нормальному базису удобно при возведении в степень вида 2". Например. если элемент = ф .о(ф, 0(. + f 0("+ ... + g ф.

1216832 возвести в квадрат, то получим у = (g.< )+(у,<Ч ° (l < ) + ... +

+(y „а ", ) =,W+y,о +y,îñ" +

+ е+ 1(тъ- г1

3 Д ol " g о посколькуо((г о, Таким образ ом, возведение в квадрат означает цикли- 10 ческий сдвиг элемента на один разряд, вправо .

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

Х Х нужно решить квадратное уравнение !5 г. (Х) = (Х+х,) (х+х,) =Х + 6Х +6,, (I 2 >, - где G q Х+ Хг, Gz- X X .

Корни уравнения

X + G„ X + G = O

{!3) 20 и являются локаторами ошибок Х1 и

Х .

Приведем уравнение { 13) к каноническому виду заменой X=ZG >. В ре- 25 эультате получим

Z +Z+G /G =0.

Если обозначить г= G !G„, то получим ЗО

Z + Z + II - =0 (14) .й

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

2. „ (O, У„У, У„..., y„y,+ ... +У,), > (>r ) 35

Z ++(!."+, !+ Т+ М, " " +1 +" + -) (16)

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

При обнаружении ошибок из блока

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

На первом такте срабатывает дешифратор 21, сигнал с первого выхода которого сдвигает на 1 разряд вправо содержимое регистра 17. При сдвиге вправо величина G„ записанная в регистр 17, возводится в квадрат (6,!) . Ha втором такте блок 12 под-1

Х. ключает с помощью первого коммутато- ра 18 иа первые входы перемножителя

22 выходы регистра 16, а выходы регистра 17 через коммутатор 20 и блок 13 — на вторую входную шину перемножителя 22. Значение 0, записанное в регистре 17, является адресом для блока 19. В результате на выходе блока 13 появляется записанная в нем по этому адресу величина !/G„. Следовательно, на первых входах перемножителя 22 появляется величина G<, а на вторых - величина I/G„ . Ha этом же такте происходит умножение С на 1/G„и на выходе перемножителя 22 получают величину ф, которая записывается в триггеры 23 группы. На третьем такте с первых выходов блока Ii на блок 24 подается сигнал записи и выдается первый адрес, по которому величина ф записывается в блок 24 j

На четвертом такте блок 1! выбирает из блока 24 величину ф, в резупьтате преобразования которой в соответствии с (15) на входах. элементов 27 и 28 и прямых выходах сумматоров 29 группы получается величина Е„, которая подключается блоком 12 с помощью коммутатора 18 на первые входы перемножителя 22. Одновременно блок 12 с помощью коммутатора 19 подключает выходы регистра 17 на вторые входы,перемножителя 22. Таким образом, на выходе последнего получен локатор ошибок

Х„= Е,6 1, который записывается в триггеры 23 группы. На пятом такте локатор Х1 с помощью блока 11 переписывается в блоки 24 и 25.

На шестом такте блок 11 снова

Выбирает из блока 24 величину ф, в результате преобразования кото Рой в соответствии с {16) на ннверсных выходах элементов 27 и

28 и сумматоров 28 группы получается величнна 2, которая подключается блоком 12 с помощью коммутатора 18 на первые входы перемножителя 22.Одновременно блок 12 с помощью коммутатора 19 подключает выходы регистра 17 на вторые входы перемножителя 22. Таким образом, на выходе последнего получен локатор ошибок Х > = K G q> который записывается в триггеры

23 группы. На седьмом такте величина Х < с помощью блока 11 переписывается в блоки 24 и 25. На этом заканчивается определение локаторов ошибок. Значения ошибок легко найти по Х„, Х, S u S Для этого не. - Уобходимо осуществить преобразова1216832 ния в соответствии с уравнениями ( У1Х!+ У Х = Sp ъ

У. Х„+ У Х = „° откуда

SpXp+Sg SХ + S

У = — . У "- -- - ----

Х, + Х,Х, Х,+Х„Х, (17)

Определение У, начинается с восьмого такта. Блок 12 подключает с помощью коммутатора 18 на первые входы перемножителя 22 выходы регистра 14, блок !1 выбирает из блока ,25 величину Х, а блок 12 подклю чает ее с помощью коммутатора 19 на,вторые входы перемножителя 22.

В результате на выходе последнего получается величина SpX, которая записывается в триггеры 23 группы.

На девятом такте блок 12 подключает выходы регистра 15 с помощью коммутатора 18 на первые входы перемножителя 22,а выход элемента 26 с помощью коммутатора 19 — на вторые входы перемножителя 22. В результате на выходе перемножителя

22 получают величину с! S „= S, которая складывается по модулю. 2 с величиной Б„Х> записанной в триггерах 23 группы. Полученная величина 80 Х + Sq на десятом такте переписывается в блок 24.

На 11-м такте блок 11 выбирает из блоков 24 и 25 локатор ошибок

Х„. Блок 12 с помощью коммутатора

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

19 — на вторые входы перемножителя 22. Полученная íà его выходе величина Х Х„= Х„ записывается

2 в триггеры 23 группы. На 12-м такте. блок ll выбирает из блока .

2.4 величину Х, а из блока 25— величину Х . Эти локаторы ошибок (Х1, Х ) подаются с помощью блока

12 и коммутаторов !8 и !9 соответственно на первые и вторые входы перемножителя 22. На выходе его будет получена величина Х„Х, которая складывается по модулю 2 с величиной Х, записанной в триго геры 23 группы.

На 13-и такте блок 11 выбирает из блока 25: величину Б Х,+ Я и блок 12 подает ее с помощью коммутатора 18 на первые входы перемножителя ?2. Сигналом с второго выхода дешифратора 21 с помощью коммутатора 20 величина Х1 + Х Х . хранящаяся в группе триггеров 23, подается на вход блока 13, на выходе которого получают величину !

/Х„+Х„Х . На этом же 13-м такте эта величина с помощью блока 12 и коммутатора 19 подается на вторые входы персмножителя 22, на выходе которого получают значение ошибки

1О

При возникновении однократных ошибок счетчик 10 устанавливается сигналом "Установка" с второго управляющего выхода вычислителя 6 в

24-е состояние. В этом состоянии блок 12 подключает с. помощью комо мутатора 18 величину o(на первые,а с помощью коммутатора 19 величину G .— на вторые входы пере1 о множителя 22. Величинаd G записывается в триггеры 23 группы и на 25-м состоянии счетчика 10 переписывается:в блок 24. В данном случае Х,= G „. На 26-м"состоянии счетчика 1О блок 12 подключает на первые входы перемножителя 22 синдром Sp> а на вторые входы перемножителя 22 — значение о . Значение

Бб 1 S1

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

Совершенно аналогично, начиная с

15-ro такта, вычисляется значение ошибки У по формуле (17). На вычис20 ление У тратится также 7 тактов и на 21-м такте этот локатор записывается в блок 25.

Таким образом, полученные локаторы ошибок Х q и Х записаны в блок 24, 25 а значения ошибок У1 и У вЂ” в блок 25.

На 22-м такте величина Х1, являющаяся адресом искаженного элемента, подается на буферный накопитель 2, в результате разряды искаженного

ЗО символа с адресом Х подаются на блок 3 сумматоров по модулю 2, на вторые входы которых подается ошибка с помощью блока 11. При сложении разрядов искаженного символа с У„

35 происходит исправление и исправленный элемент вновь записывается в бубуферный накопитель -2 по тому же адресу. Исправление элемента Х > происходит на 23-м такте аналогич46 но. й

12 16832

ol S записывается в триггеры 23 группы и на 27-м состоянии счетчика 10 переписывается в блок 25. Здесь

У = ЯБ. Исправление однократной ошибки осуществляется так же, как и двухкратных. формула изобретения

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

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

5 J0

l5

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

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

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

5 памяти первый вход каждого из осУ тальных сумматоров по модулю два соединен с прямым выходом предыдущего, вторые входы m-2 сумматоров по модулю два подключены к выходам

1б первого блока оперативной памяти с третьего по m-Й соответственно, вы-, ходы блока из m сумматоров по модулю два подключены к соответствующим третьим входам буферного накопите15 ля, управляющий вход которого соединен с вторым выходом дешифратора ошибок м где - размерность поля G F(2 )Галуа, ВНИИПИ Заказ 1005/61 Тираж 818 Подписное

Филиал ППП "Патент", г.Ужгород, ул.Проектная, 4