Устройство для декодирования составного корректирующего кода Советский патент 1986 года по МПК H03M13/51 

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

jC вторым входом второго деишфрато- а, выход формирователя значения

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

5

0

5.

0

5

0

5

0

5

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

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

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

4,- Устройство по п. 1 , отличающееся тем, что вычислитель значений ошибки кода Рида-Соломона содержит объединенные по входам первый формирователь вспомогательных символов, второй и третий

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

Цель изобретения - повьппение скорости декодирования.

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

На фиг, 1 приведена блок-схема устройства для декодирования составного корректирующего кода на фиг,2- блок-схема вычислителя локаторов ошибок первого внешнего кода{ на . фиг, 3 - блок-схема вычислителя локатора ошибки кода Рида-Соломона; на фиг, 4 - блок-схема вычислителя зна31229969

ения оптбки кода Рида-Соломона на фиг, 5 - структура кодового слова Г-составного кода.

Устройство содержит блок 1 разеления кодов, вычислитель 2 локато- 5 ров ошибок первого внешнего кода, корректор , 3 кода Рида-Соломона, .вычислитель 4 локатора ошибки кода Рида-Соломона, вычислитель 5 значения ошибки кода Рида-Соломона, блок Ю 6 коммутации локатора- однократной ошибки, первый сигнализатор 7 наличия ошибок, блок & коммутации, первой ошибки кода Рида-Соломона,, вычислитель 9 четности ошибок, первый да- 15 шифратор 10, второй дешифратор 11, третий, дешифратор 12, блок 13 ,комму- .тации ошибок кода Рида-Соломона, Корректор 14 смешанных разрядов,

формирователь 15 зиачения ошибок сме-20 шанных разрядов, формирователь 16 информационных разрядов первого

внешнего кода. .

Вычислитель 2 локаторов ошибок первого внешнего кода содержит пер- 25 вый.формирователь 17 первого локатора, формирователь 18 расширенного синдрома, второй формирователь 19 первого локатора, формирователь 20 дискриминанта, блок 21 управления, ЗО блок 22 коммутации первого локатора, третий формирователь 23 первого локатора, формирователь 24 второго локатора, второй сигнализатор 25

наличия ошибок.

35

. .

Вычислитель 4 локатора ошибок кода Рида-Соломона содержит формирователь 26 упорядоченного синдрома, первый формирователь 27 обратного элемента, первый формирователь 28 частичных произведений, первый формирователь 29 линейных функций, сум-, матор 30 по модулю два.

Вычислитель 5 значения ошибки кода Рида-Соломона содержит второй формирователь 31 обратного элемента, второй формирователь 32 частичных произведений, второй формирователь 33 линейных функций, первый формирова- 50 тель 34 вспомогательных символов, третий формирователь 35 частичных произведений, третий формирователь 36 линейных функций, четвертый формирователь 37 частичных произведений,55 второй формирователь 38 вспомогательных символов, третий формирователь 39 вспомогательных символов.

Для описания работы устройства введены следующие обозначения: код Рида-Соломона - код РС; первый внешний код (код Нордстрома-Робинсона) - код HPJ + - знак сложения по модулю два| GF(2 - .поле Галуа, содержащее 2 элементов, каждый из ко- торьк является набором из tn двоичных разрядов; оС- примитивный элемент поля GE(2), являющийся корнем многочлена i (Nf,, N,, .., N)) - двоичный 1ггмерный вектор, со55

20

5 О

5

0

50 55

поставляемый элементу (X. +

+ ...+N oC+No поля GF( У,. Г. М; бХ , Zj,, Di,, ,1 - элементы поля GF (2) ; Я, JU , , f , fi, gi i, Ьк, 8ц, .,., 2 - элементы поля GF(2); V - знак логического ИЛИ.

Устройство работает следуюш 1м образом,

Декодируемое 80-разрядное слово Г -составного кода поступает из памяти на входы 1 и 2 устройства, . (штрих указывает на возможные искажения в декодируемом слове).

Структура кодового слова F данно го составного кода представлена iia фиг, 5. При кодировании исходное 64- разрядное информационное слово а а.г. ...,а разделяется на две части а, .., ,а5БИ а5г,... ,afc соответственно по 56 и 8 разрядов. Первая, часть кодируется (16, 14) - кодом PC над полем GF(2). При этом информационные разряды а,... ,aj-6разбиваются на наборы по четыре разряда, например: af ,аг,аз,а/у,,. ,,а,.. .,а каждый

из которых рассматривается как элемент поля GF(2). В результате кодирования кодом PC формируются проверочные разряды с,...,с кода PC, Слово кода PC образует матрицу, состоящую из. 16 столбцов (элементов поля GF (2), каждый из которых состоит из четырех разрядов. Информационные разряды a5:fi... , кодируется в слово b-(bo,b ,.,. ,5) кода HP, причем b ,..., , а Ьд ,bg ,., , проверочные разряды кода HP. Итоговое кодовое слово Г-составного (80, 64)-кода состоит из слова с (с , ...,с/,а ,. . . ,а5«) кода PC и слова . f (fo,,. ., ) смешанных разрядов f, которые представляют собой сумму по модулю два (.-го разряда кода HP и четырех разрядов 1-го столбца кода PC, На вход 1 посту- .пает 64-разрядное декодирующее елово кода PC: с (.а , . ,. .a j

На вход 2 поступает 16-разрядное декодируемое слово f (f,..., смешанных разрядов. Слово f с входа 2 проходит в блок 1 и корректор 14, В блоке 1 формируется декодируемое слово кода HP - Ъ (Ъ о, ,.. ,) путем реализации соотношений

bl fK+c;+c,+q(,i+c;, ,

,i;

bj(f fe+a rt, , ,...,15,

знак + в индексах означает сложе- кие целых чисел.

Разряды Ъ,... передаются из блока 1 в.вычислитель 2, а разряды b,.,,,b в формирователь 16.

Слово с входа 1 поступает в блок 1, в ычислитель 4 и корректор 3. В вычислителях 2 и 4 одновременно вычисляются локаторы первой и второй ошибок кода HP - i-Ku) ,2 (в блоке 2) и (первый нижний индекс в обозначениях элемента полей GF(2) и GF(2) означает порядковый номер элемента поля, а второй нижний индекс - номер компоненты элемента локатор ошибки кода PC -Д ГЛьЛг.,1,До) (блок 4), Вычислитель 2, кроме того, формирует и выдает в другие блоки сумму вого и второго локаторов и двоичные управляющие сигналы Wo, W/f Wi, dcT, di«, P, lo, lyf здесь dff, dц/ и P - четность суммы соответственно старших восьми разрядов, младших восьми разрядов и всех разрядов слова Ь ; Wj l, если в слове Ь/ про.исходит ровно j ошибок, , 2, Wi 0 в противном случае).

В вычислителе 4 для получения локатора j вычисляется упорядочен- .ный синдром S слова с , равный

(S4, Si) (845, Sri, S25,Sj2 Sat, , S2o) (c;;,...,c ,ajJ,...,a ) H(l) где проверочная матрица кода

PC,

Т - знак транспонирования. Матрица Нр.имеет вид

. ,

где - примитивный элемент поля СР(2т), являюпшйся корнем многочле

5

5

0 5 0 5 0

5

0

на X +Х+1 . Матрица Нр(. составлена таким образом, что двоичное представление элемента сз в виде четырехмерного вектора совпадает с номером столбца, в котором он находится. В двоичном виде проверочная матрица Ирг приведена в табл. 1. Вычислитель 4, кроме того, вычисляет элемент поля GF(2). Первый сигнализатор 7, используя сигналы Р, dcj,lo, 1л , i, S иуи, формирует двоичные управляющие сигналы W и WOK ) 1, если в декодируемом слове Г ошибок нет, а если в слове г происходит неисправимая ошибка. , если,, и . В этом случае слово Г выдается на выход устройства без изменений. Если же ошибки есть, они исправляются ( При этом устройство реализует следующие три случая исправления ошибок.

A.В слове b ошибок нет, т.е. , Тогда, если , то в слове .с искажен один столбец с номеромд

- , а значение ошибки в этом столбце h (,,h,h-(.

Б. В слове 1э обнаружена одна ошибка, в этом случае . При этом сумма локаторов i совпадает с локатором if f а величина м совпадает с величиной д + 1 . Если оказывается, что ), т.е.0, то в слове с искажен один столбец с номером i и . Если и Я 1, т.е. / 0, или, если и , то необходимо отказаться от декодирования и первый сигнализатор 7 формирует Worn 1.,

B.В слове Ь происходит две ошибки в позициях i/f и ij , т.е. . В .

( этом случае в слове с искажены два

столбца с номерами и i. Значения ошибок h и hj. в этих столбцах находятся из системы уравнений над поТтем GF(2):

;

Ц h + .

По формулам

bs,l

1 1

1

i

(2)

55

.

(3)

Вычисление значения ошибки h по формуле (2) реализуется вычислите20

ем 5, на вход которого поступают еличины i, i и S(,). Формиование значения ошибки осуще- i ствляется с учетом правил А, Б. В 5 формулы (з) блоком 8, использущим величины Р, W, W, Sx| и h . Блок 6 на основе правил А, Б, В формирует ускоренный локатор i (ij, ij, i, i) с учетом кратное- 10 ти ошибок,

При этом, если , то i Я (пр&- вило А); если , то 1 (правио Б); если Wj l, то (прави- jfo В)..15

Данный алгоритм ускоряет коррек- цию однократной ошибки, так как сумма локаторов i формируется вычислителем 2 существенно быстрее, чем отдельные локаторы и ig., Этот факт учтен также в формуле (2),

Вычислитель 9 вычисляет четности R., Кг. ошибок h и.Ь одновременно с вычислением ошибок h и h b вычислителе 5 и блоке 8, используя величины WP, W, Р, S и промежуточные данные, полученные в звычислителе 5 при вычислении Ъ. Такое вычисление R и R ускоряет декодирование, позволяя исправить слово f одновременно с словом с .

Третий 12 и второй II дешифраторы дешифруют .четырехразрядные величины соответственно i и ia., формируя 16-разрядные слова ё -( j. , . , ё и е(ё .,.. ,,ёЗ (для определенности здесь принято, что выходы дешифраторов инверсные, что обычно имеет место в сериях микросхем средней степени интеграции). При этом учитывается, что в силу выбора матрицы Нр соответствие между локатором и номером IK, ошибочного .столбца естественное, т.е.

25

30

45

. У

ч

р

1

KJ

Первьй дешифратор 10 аналогичным

гхобразом дешифрирует г , формируя

м,

(ё,. .. , , 8-разрядное слово, соответствующее информационным разрядам кода HP.

Третий дешифратор 12 открыт, если , т.е. при наличии любых ошибок в слове Г . Первьй дешифратор 10 открыт, если , т,е., при нали чИи ошибок в слове Ь кода HP, второй дешифратор 11 открьГт, если W I .

Благодаря таТкому управлению дешифраторами в блоке 13, формирователях 15 и 16 при формировании коррект ируюшлх слов учитываются именно те ошибки h, локаторы IK и четности R| кото-, рых необходимы в случаях ;исправи- мых конфигураций ошибок. Если и правило В не должно реализоваться, то в блоке 13, формирователях 15 и 16 не учитываются значения hj,, . i и R2.

Блок 13 получает сигналы , h, h, s и формирует корректирующее слово Е кода PC, равное О, если . Корректор 3, суммируя по модулю двд слово В со словом с(, формирует исправленное слово кода

0

PC с(с,,..,с.

1/1

а и вьща5

0

5

0

ет его на выход 1 устройства.

Формирователь 15 получает величины К, R2, формирует корректирующее F(Fo , ... ,F) равное О, если W. 1 , Корректор 14, суммируя слово F со словом f , формирует слов.о исправленных смешанных разрядов f (f tj,. .., (ь-) и вьща- ет его на выход 2 устройства.

Формирователь 16 получает величины е - и формирует корректирующее слово В(,,. . ,В) и, суммируя разряды Ь;} ,,.. ,bg со словом В, получает информационные разряды кода HP b,,..,bjj которые проходят на выход 3 устройства.

Исправленные информационные разряды а ,.. . fas(f b, ,. .. ,b поступают к пользователю памяти.

Исправленное слово составного кода Г (с ,, .., с , а ,.,,, а f о-,..,, ) поступает в память для перезаписи.

Вычислитель 2 (фиг, 2) работает следующим образом,

Декодируемое слово кода HP поступает на входы пе рвого формирователя 17 и формирователя JВ, Последний вычисляет расширенный синдром кода HP, реализуя с помощью сумматоров по модулю два соотношения

(G oz.c,,Gi,,G;4cr) (biT:. .%U) ; (A/...Ag)Vo,..bJ5-) Hj; ..,,+b 7;

:

где Hjjp и Н - матрицы, приведенные в табл. 2, При умножении вектора на матрицу i-й разряд произведения

находится как сумма по модулю два. трех разрядов слова Ь , номера которых соответствуют номерам единичных элементов i-й строки матрицы, Например, 3 ог Ьч+Ь5 Ьб+Ь..

Вычисленные таким образом элементы (Ус,, yf поля GF(2 ) и двоичные величины А, А , AT, Ag поступают на выход 1 формирователя 18, отку- да проходят в формирователь 20 и второй формирователь 19. Величины AZf АЗ, Aif поступают на выход 3 формирователя 18, откуда проходят в формирователь 20, Двоичные величи- ны dfj-, dnn и Р поступают соответст- венйо на второй, четвертый и. пятый выходы формирователя 18, Величина d/ npoxoflHT .во второй сигнализатор 25 и на выход 3 вычислителя 2, Вели- чина Р поступает на выход 5. вычислителя 2, Величина d. поступает в блок -21, второй сигнализатор 25, блок 22, формирователь 24 и на выход 1 вычислителя 2, как старший разряд суммы t локаторов.

Первый формирова тель 17 с помощью сумматоров по модулю два вычисляет величину f путем умножения слова b на транспонированную матрицу Hv (табл, 2 - проверочные матрицы кода Нордстрома-Робинсона)

(ГгЛ/) (b o,...,b;5)нJ,

Величина поступает с выхода этого 35 блока на входы блоков 20-25 и на первый выход вычислителя 2 образуя младшие разряды суммы локаторов i (da,/J, fi,). Величина I с выхода 1 вычислителя -2 поступает в блок 6, 40 вычислители 4 и 5 и первый сигнализатор 7,

В блок 22 элемент ()f поступает в качестве первого варианта младших . разрядов локаторов i (всего форми- 45 руется четыре варианта младших разрядов локатора i),

Второй формирователь 19 с помощью сумматоров по модулю два и элементов И-НЕ формирует второй вариант 50 младших разрядов локатора i-j - элемент М поля GF(2), .

При этом реализуются соотношения

тй Аб бсг+боо ч + (3oiG:| +Go ; () +m2+intTtop-S) ; M () (mi +tn o) m г.,

Величина М с выхода формирователя 19 поступает в блок 22,

В формирова:теле 20 с помощью сумматоров по модулю два и элементов И-НБ вычисляется дискриминант (), который позволяет вычислить третий и четвертый варианты младщих раз-

рядов локаторов i в третьем формирователе 23, определить конфигу- . рацию ошибок в слове b , Формирование дискриминанта выполняется путем реализации соотношений

+ |e|7j Do A;j+A, + ); .

Deo A +6 G:y-tf:ja;

Dli . D-) г(fi+/г};

.

Величины Dp и D/i с выхода формирователя 18 поступают в третий формирователь 23 и блок 21,

В третьем формирователе 23 вычисляются третий ZQ и четвертый Z/f варианты младших разрядов локаторов i , При этом с помощью сумматоров по модулю два и элементов И-НЕ реализуются выражения

35 40

5

0

5

30

2к.,Б,,Я+В,„(7+Д); 2fcrDii M+l№l Z..c,fJ-,C(. ° где +77, Ci ,)

j

Величины Zot Z../ С выхода третьего формирователя 23 поступают на вход блока 22,

Блок 21 формирует двоичные управляющие сигналы А , Kj, Kj, VQ , V , o, }, позволяющие определить кон- фигурацию ошибки, выбрать нужный вариант младших разрядов локатора 1 и сформировать старший разряд i этого локатора,

I Сигналы fo , // формируются путем сравнения дискриминанта с нулем с помощью элементов ИЛИ-НЕ следующим ; образом:

1. (i: :s К:

,l.

Сигналы .0 и Lf с второго выхода блока 21 передаются в блок 22, второй сигнализатор 25 и на выход 5 . вычислителя. 2,

n

5

Сигналы % .и V формируются для выбора вариантов младших разрядов локатора и Z .

Ve - gOoi- УГо с+ОбгС | + г ) ; V, |5D.,+ p;,,,,(|J + J).

С выхода 3 блока 21 сигналы V и У, поступают в блок 22.

Выбор нужного варианта локатора выполняется в блоке 22 с помощью сигналов Кд, Kg., K.J,

Формирование этих сигналов, а так- же работа блока 22 и второго сигнализатора 25 основаны на следующих де- кодирующих правилах. 5

К , ,

R3 V WdcTrif«r) которые-с выхода 1 блока 21 поступают в блок 22. В соответствии с .ука занными правилами второй сигнализатор 25 формирует двоичные сигналы Wi об ошибках путем реализации выражений

10

Wo dtTVd WM W, irdM dcTVli dM cicrL

«г d«dи Vdcrdм V |i Jo..

с помощью элемен- ов ИЛИ-НЕ. Сигналы Wj, 3 0,2, 1, выдаются этим-блоком соответственно на выходы 6 и 4 вычи- - т Д flt-UU 1 05: IA: I OCnJn - О .

1. Если и o+l то происхо- 2 и вькод 4 устройства.

дит ошибка с локатором 1/ (Ь{),Д i

.П)- . , . Если, кроме того, dti+ l, то еще искажен разряд bj , а если P+d, 20 то искажен разряд Ь. В этом случае , .

2. Если , то происходят; две опшбки с локаторами .i(( и

Блок 22 с . ПОМОЩЬЮ управляющих сиг- налов Кд, Kj, Кз, Vo, V , , 1 формирует локатор 14

i,j,K,loVK3VoV olid«;

i,, J VK.MjVKiVoZ,VKjV ,

,l,Q

V, где i, (0, М„. M, M,). a 1д. on-25 помощью; элементов И-ИШ-НЕ. HE,

1 i«- который с выхода этого блока прохо; дит.на вход формирователя 24 и на вьпсод 7 вычислителя 2,

Формирователь 24 с помощью сумределяется из выражений

iiK +V .0,1,2 f (4) В случае Кг.1, .

3, Если o,,., то про-зо по модулю два реализует вы- исходят две. ошибки с локаторами , ражение. (4J для локатора 1г , который ix, где i(l, Zoi, Zofo )/ecли .проходит на выход 8 вычислителя 2. , либо i (0, 2;,i, Z, Z), если Вычислитель 4 (фиг. З) работает i, определяется по выражениям (4). В этом случае Кз 1, . 3

4i Если P,, f, l, то происходит одна ошибка с локатором i (d,.0,0, О)., а . .

5,Если to -l, , dc,, то происходят две ошибки с локаторами i и ij., где i: (0,0, О, О) , ia. определяется из выражений (4), а К .

6.Если , ,:то ошибок

. - . . .-- 45

40

нет.

следующим образом.

Слово с с входа I вычислителя 4 поступает в формирователь 26, который С помощью сумматоров по модулю два реализует умножение слова с на транспортированную матрицу соответствии с вьфажением (О, Первая четырехразрядная часть синдрома S,( поступает на вход 1, вторая четырехразрядная часть - на выход 2, Весь восьмиразрядный синдром S(, ., S, ,2,5д4,3г проходит на выход 3 вычислителя 4.

Слово с с входа I вычис поступает в формирователь С помощью сумматоров по мод реализует умножение слова с транспортированную матрицу ответствии с вьфажением (О четырехразрядная часть синд поступает на вход 1, вторая разрядная часть - на выход восьмиразрядный синдром S S, ,2,5д4,3г проходи ход 3 вычислителя 4.

Первьй формирователь 27 ет обратный элемент в поле таблицу истинности (фиг. 3

7i Если ошибки есть, то не выполняется ни одно из декодирующих пра- вил 1-6, Или, если в правиле 1 одновременно искажены разряды bj и bV, .то необходимо отказаться от декоди- jO . соотношений рованйя и предположении, что произошла ошибка, кратность которой не менее трех

s,j,.v

vS«S,iiS,

5ii 10 ,S(,

Б .соответствии с этИми правилами блок 21 с помощью сумматоров по модулю два и элементов ИЛИ-НЕ, НЕ формирует сигналы К, К и К следующим образом:

5

229969 12

К , ,

R3 V WdcTrif«r) которые-с выхода 1 блока 21 поступают в блок 22. В соответствии с .ука занными правилами второй сигнализатор 25 формирует двоичные сигналы Wi об ошибках путем реализации выражений

Wo dtTVd WM W, irdM dcTVli dM cicrL

«г d«dи Vdcrdм V |i Jo..

с помощью элемен- ов ИЛИ-НЕ. Сигналы Wj, 3 0,2, 1, выдаются этим-блоком соответственно на выходы 6 и 4 вычиt-UU 1 05: IA: I OCnJn - О .

2 и вькод 4 устройства.

Блок 22 с . ПОМОЩЬЮ управляющих налов Кд, Kj, Кз, Vo, V , , 1 мирует локатор 14

i,j,K,loVK3VoV olid«;

i,, J VK.MjVKiVoZ,VKjV ,

,l,Q

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

следующим образом.

Слово с с входа I вычислителя 4 поступает в формирователь 26, который С помощью сумматоров по модулю два реализует умножение слова с на транспортированную матрицу соответствии с вьфажением (О, Первая четырехразрядная часть синдрома S,( поступает на вход 1, вторая четырехразрядная часть - на выход 2, Весь восьмиразрядный синдром S(, ., S, ,2,5д4,3г проходит на выход 3 вычислителя 4.

Первьй формирователь 27 формирует обратный элемент в поле, реализуя таблицу истинности (фиг. 3), напри. соотношений

. соотношений

s,j,.v s,

vS«S,iiS,

5ii 10 ,S(,

, S,jSj, S,§,i V ,iS,oV S,sSiiSw V

V SeSiiStt; . г,,5,ДД s, ,jS«s;«s,«v

V 8,ь84,5,Д, .

.13. , 1229969

формирователь 28 с помощью И-НЕ реализует 16 частичедений вида

. в 5 в п дл ч в

j ij-lL S j , i,, 1,2,3.

Первый формирователь 29, используя jUcj и сумму-локаторов i, которая поступает по входу 2, формирует линейную функциюJU :

(U fjS2 + ..

При этом с помощью сумматоров по модулю два и элементов НЕ. реализуются- соотношения

. },ь +JW-« +J«j-, Язо ст; Л « з /t .i 1 ,-f fe; .M, t, o J,+(„,) t. JM H «i-f| ii+7 o +

Формирование суммы/ 1+L раньще сигнала 1( ускоряет формирование сигнайа отказа до декодирования блоке 7 в случае трехкратной неисправимой ошиб ки и тем самь1м позволяет ускорить выдачу исправленного слова Г в случае однократной ошибки.

Сумматор 30 формирует локатор Л путем реализации поразрядного сложения по модулю два JM и i.

. 1--0. 1. 2, 3.

Элементы (Ц и j) выдаются соответственно на выходы 2 и 1 вычислителя 4,

Блок 6 с помощью элементов ИЛИ-НЕ формирует ускоренный локатор i путем реализации соотношений

,daVWii, iiJ PJilvWiVYWjk, .1,0.

Первый сигнализатор 7 с помощью элементов И-НЕ, НЕ И-ИЛИ-НЕ формирует сигналы и W,7ic соответственно об отсутствии ошибок и об отказе о т декодирования, реализуя выражения

(ОЕЩ)

Wn

E vEiVEVdw ;

E 55-Jjj., , E 5KiSjiSb,SKo, k-1,2; /,PjMiVPjM VPj4,, ,

WeTK PXxVdci 1о:..,. .

Сигнал WOTX поступает на выход 5 устройства. Если WOTK 1, то вычислительная система, использующая устройство для декодирования, не .

14

принимает слова с выходов устройст- ва 1, 2 и 3, считая их ошибочными. Если , то вычислительная система принимает исправленные слова с выходов I, 2 и 3 через время Т; после ввода слова Г в устройство для декодирования, причем Lj., что соответствует-отсутствию ошибок , одной и двум ошибкам в слове Г.

Вычислитель 5 работает следующим образом (фиг. 4). Первая часть синдрома Sf поступает с входа 1 в первый формйрова тель 34, а вторая часть Si - во второй формирователь 38,

Первый формирователь 34 с помощью сумматоров по модулю два формирует двоичные сигналы

20

IJ) -и -Joi % -12

,2+S.

41

которые поступают в .третий формирователь 35.

Второй формирователь 38 с помощью сумматоров по модулю два форми- рует двоичные сигналы

82г, 5гь+52.о; 3 5 5 +522} 5 с 5гг 5а; S2r SzD+Sii; S j 52T-«-Sfc; S29 S3 j+Sz6,

которые поступают во второй формирователь 32.

Второй формирователь 3, получив с входа 3 сумму локаторов -i , формирует обратный элемент в поле GF(2 ):

:f т аналогично первому формирователю 27. Элемент f поступает во второй 32 и третий 35 формирователи. Третий формирователь 35 с помощью элементов И-НЕ формирует; J 6 частич-- ньпс произведений ij , где индексы принимают следующие значения:

,,4,5, 6

,,2,4, 5

,,2,3, 4

,,1,2, 3

(5)

Второй формирователь 32 с помо- щью элементов И-НЕ формирует 20 частичных произведений вида

gij jlSij f где значения i, j следующие:

,,1, 4,5,6

,,2, 4,5,7 (6)

,,2, 3,4,8

,,1, 2,3,9,

и они поступают в блок 36.

10

15

20

25

Частичные произведения gp,, gjo- роходят на выход 3 вычислителя 5 « оступают в вычислитель 9. ;

Второй формирователь 33 формирут линейную функцию / ф5)1;, k 3, 2, 1, О, реализуя с помощью суматоров по модулю два сигналы

j V 2i+f«+fo3;

t fj4+Mi.tfod; fo fM+i-H ei..+foo..

оторые поступают с выхода второго ормирователя 33 в третий 39 и чет- ертый 37 формирователи.

Третий формирователь 39 с помощью сумматоров по модулю два формирует сигналы

f . .+f,; .

f-t f,+fci

; .. T, ,

Величины F) ,...,% поступают в третий 36 и четвертый 37 формирователи, величина проходит на выход. А вычислителя 5 и поступает в вычислитель 9. .

Четвертьш формирователь 37 с помощью элементов И-НЕ формирует 20 частичных произведений вида

Ktj ,

где индексы 1, j. принимают значения (5) и (6), 16 произведений с индек сами из (5) поступают в третий формирователь 36, а произведения 1%о, KW. Kc,g проходят на выход 1 вычислителя 5 и поступают в вычислитель 9.

Третий формирователь 36 с помощью сумматоров по модулю два формирует линейную функцию

.S . путем,реализации выражений

hjj gir+S2(+gf2+g +Ki,+KM+K,i+Kt,+ fij, f гч f-ff + f(.t+K3r+Kei,+K +Kc2+ Рт

4 g 4+g2f+&..+Kjfe+Kir -KH +Ko,+ fo , , + + gpo+%-H 2+l4j+Kco+f9,

Значение ошибки hj. поступает на выход 1 вычислителя 5 и проходит в блоки 8 и 13.

Блок 8 с помощью элементов И, ИЛИ.55 НЕ формирует значение ощибкй h путем реализации соотношений

,, , ,l,2.S

30

35

40

45

50

0

5

0

5

5

0

5

0

5

0

Вычислитель 9 с помощью элементов И, ИЛИ, НЕ и сумматоров п о модулю два формирует четности ошибок Ry) и RJ , реализуя выражения

R4 PRsVWoRiVWtRiRsVWj RjRi;

Ri g3o+g« g 8+ go9+Kjp-t-K;,+K,,

.

Четность R поступает на выход 1, а четность R - на выход 2 вычислителя 9,

Каждый из дешифраторов 12, 10, 11 имеет че тьфехразрядньш информационный вход, на который поступает соответствующий локатор, и управляющий вход, на который поступает соответственно сигнал Wo°,, W. Дешифраторы 10-12 имеют 16-разрядный инверсный выход. В зависимости от сигнала, который поступает на управляющий вход, дешифратор может быть открыт или закрыт. Если дешифратор закрыт, то на всех разрядах выхода сигналы равны 1, В открытом дешифра- т;оре на одном разряде выхода сиг- нал равен О, а на остальных - 1, Дешифраторы 9 и 10 открыты, когда сигнал на управляющем входе равен О, дешифратор II открыт, когда сигнал на управляющем входе равен .1.

Блок 13 формирует 64-разрядное корректирующее слово Е кода PC путем реализации соотношений

E,(,b, (7) . ,2,3,4; ,l ,. .,,15.

. Формирователь 15 с помощью элементов И, ИЛИ, НЕ формирует корректирующее слово F путем реализации выражений

. F,, , . .,15, (8)

В последнем выражении учтено, что ошибка в смешанном разряде равна сумме по модулю два ошибки в k-м разряде слова Ь и четности ошибок в Н.-М столбце слова с .

Указанные выражения для корректирующих слов кода PC и кода HP могут быть реализованы с помощью мульти- плек соров. Для этого сигнал Ujj подается на стробирующий вход, сигналы е I е на адресные входы, а сигналы h., I alt-mjt 1 . - на информационные входы. При этом полярность сигналов , е может быть как пря- .МРЙА. так и.инвер сной в зависимости

от выбора адресов в мультиплексор. Выражения (7) и (8) можно реализовать также на элементах И-ИПИ-НЕ,

ИЛИ-НЕ, В этом случае сигналы /J)1

нужно брать в прямой полярности. Для этого используется соотношение

W (ab vcd ) Wv (abv cd ).

Корректор 3 с помощью сумматоров по модулю два исправляет слово с , реализуя соотношения

,+Emk, ,

,l; , 2, 3, 4 аи a n+Ert«c n (k-2 ) +m, ,315; , 2, 3, 4.

Корректор 14 с помощью сумматоро по модулю два корректирует смешанные разряды, реализуя выражения

,+Рц, ,l....,I5.

Формирователь 16 с помощью элементов И-НЕ и сумматоров по модулю два формирует информационные разряды кода HPi реализуя соотношения

III

III

I.1

IГ

I I I : 111

IIt 1 I I I I I I 1

III 1- 1111

1I I I 1

II 1 I

I II ll I I I 1

IIIII I I I I I I I I

I II I I. Ill II

II I I III I

а,.

I.

I1I

I1 II .1 1.1-1

III

11 1 I I I I I II

II1111 I II III

II I I I I I 1 111

Обозначение матрицы

Номер столбца матрицы

|0 1 2 34567 8 9 10 II 12 13 14 15 00001 1 11.000 О 000 О 001 100110 О О 00 .0 О О

010101010000 О 00 о

b,,....,8.

Таким образом, на выходах I и 2 I устройства формируется кодовое 80- разрядное слово составного корректирующего /80, 64)-кода, которое в случае исправимой конфигурации ошибок поступает на перезапись в запоминающее устройство, минуя устройство для кодирования, а на 8-разрядном выходе 3 и 56-ти разрядах выхода 1 формируется исходное исправ ленное информационное слово, которое поступает на выход запоминающего устройства для передачи пользователю. .При этом устройство для декодирования обеспечивает исправление всех независимых двойных и обнаруже-. ние всех независимых тройных ошибок, а также исправление любых двух фа- зированньпс пакетов ошибок длины пять с нечетным числом ошибок в каждом пакете и обнаружение трех фазированных пакетов оши бок длины пять с нечетным числом ошибок в каждом пакете. .

Таблиц

III

III

III

III

III I I I II J I I I

II I 1 I I I Г

1)11 I I II

%)

Таблица 2

19

1229969

. 20 Продолжение табл.2.

(риг 1

Смешанное caofo из Kodog Рида Соломона и Нирдстрома- Робцнсома.

Фиг. 5