Устройство для декодирования составного корректирующего кода

 

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51) 4 Н 03 М 13/02

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 3589594/24-09 (22) 04.05,83 (46) 07.05.86. Бюл. 9-17 (72) А.В.Анохин, И.М.Бояринов, А.А,Давыдов, Ю,Г.Дадаев, 10.Í.Ìåëåøкин, В.А.Мельников, Ю.И.Митропольский и В.П.Салакатов (53) 621.394.14(088.8) (56) Блок Э.А. и Зяблов B.Â. Обобщенные каскадные коды. — М,: Связь, 1976, с. 190. (54)(57) 1. УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ СОСТАВНОГО КОРРЕКТИРУЮЩЕГО

КОДА, содержащее последовательно. соединенные блок разделения кодов и вычислитель локаторов ошибок первого внешнего кода, вычислитель локатора ошибки кода Рида-Соломона и вычислитель значения ошибки кода Рида-Соломона, первый вход блока разделения кодов объединен с соответствующими входами корректора кода Рида-Соломона и вычислителя локатора ошибки кода Рида-Соломона и является первым входом устройства, а второй вход блока разделения кодов является вторым входом устройства, о тл и ч а ю щ е е с я тем, что, с целью повышения скорости декодирования, в него введены блок коммутации локатора однократной ошибки, первый сигнализатор наличия ошибок, блок коммутации первой ошибки кода

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

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

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

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

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

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

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

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

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

64 †разрядн блоках данных.

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

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

Соломона.

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

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

Г-составного кода.

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

Рида-Соломона, вычислитель 5 значения ошибки кода Рида-Соломона, блок 10

6 коммутации локатора однократной ошибки, первый сигнализатор 7 наличия ошибок, блок 8 коммутации первой ошибки кода Рида-Соломона,. вычислитель 9 четности ошибок, первый де- 15 шифратор 10, второй дешифратор 11, третий дешифратор 12, блок 13 комму.тации ошибок кода Рида-Соломона, корректор 14 смешанных разрядов, формирователь 15 значения ошибок сме-.2О шанных разрядов, формирователь 16 информационных разрядов первого внешнего кода.

Вычислитель 2 локаторов ошибок первого внешнего кода содержит пер- 25 вый,формирователь 17 первого локатора, формирователь 18 расширенного синдрома, второй формирователь 19 первого локатора, формирователь 20 дискриминанта, блок 21 управления, ЗО блок 22 коммутации первого локатора, третий формирователь 23 первого локатора, формирователь 24 второго локатора, второй сигнализатор 25 наличия ошибок, Вычислитель 4 локатора ошибок кода Рида-Соломона содержит формирователь 26 упорядоченного синдрома, первый формирователь 27 обратного элемента, первый формирователь 28 частичных произведений, первый формирователь 29 линейных функций, сум-, матор 30 по модулю два, Вычислитель 5 значения ошибки 45 кода Рида-Соломона содержит второй .формирователь 31 обратного элемента, второй Формирователь 32 частичных произведений, второй формирователь 33 линейных функций, первый формирователь 34 вспомогательных символов, третий формирователь 35 частичных произведений, третий формирователь

36 линейных функций, четвертый формирователь 37 частичных произведений, > второй формирователь 38 вспомогательных символов, третий формирователь 39 вспомогательных символов.

Для описания работы устройства введены следующие обозначения: код

Рида-Соломона — код РС, первый внешний код (код Нордстрома-Робинсона)— код HP, "+" — знак сложения по модулю два, GF(2) — .поле Галуа, содержащее 2 элементов, каждый из которых является набором из m двоичных разрядов, о = примитивный элемент поля GF(2), являющийся корнем многочлена X X+1, (N, N +,..., No) - двоичный ит-мерный вектор, сопоставляемый элементу ¹N a +

+...+Nb<+No поля GF(2 ); Q, ш

11; +1, 21,, Di, д=0,1 — элементы поля GF(23)1лву4ВРФ,fэ,qþ,К дк, hei

Sg,;k=l., 2 — элементы поля СР(2");

Ч вЂ” знак логического ИЛИ.

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

Декодируемое 80-разрядное слово

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

Структура кодового слова Г данно

ro составного кода представлена на фиг. 5. При кодировании исходное 64разрядное информационное слово а,а, ...,а разделяется на две части а,,. .,а як ад....,ац соответственно по 56 и 8 разрядов. Первая, часть кодируется (16, 14) — кодом PC над полем GF(2 ). При этом информационные разряды a,...,à g,разбиваются на наборы по четыре разряда, например: а,а,а,а,...,a@„ ...,а, каждый из которых рассматривается как элемент ноля GP(2 ). В результате кодирования кодом PC формируются проверочные разряды с, ° ° °,с кода РС.

Слово кода PC образует матрицу, состоящую из .16 столбцов (элементов поля GP(2"), каждый из которых состоит из четырех разрядов. Информационные разряды ащ ...,ац, кодируется в слово Ъ-(bo,Ъ|,...,Ъ у) кода HP, причем Ь =а@...,, Ь =а, а Ъ,bg, ° °,bö.проверочные разряды кода HP. Итоговое кодовое слово Г-составного (80, 64)-кода состоит иэ слова с

=(с,...,cg,а ...,,a 3 кода РС и слова.f (f,...,Йш) "смешанных" разрядов f которые представляют собой сумму по модулю два 0-ro разряда кода HP н четырех разрядов 4-ro столбца кода РС. На вход 1 пос.тупает 64-разрядное декодирующее сло1229969

ЬФ+Ь,=$л 3

i h»+1 h =$д

По формулам

Ь =$л+Ь во кода РС: с/=(с„,...,c а(„...а,, На вход 2 поступает 16-разрядное декодируемое слово f (fgI...Ifqg "смеII шанных разрядов. Слово f с входа 5

2 проходит в блок и корректор 14, В блоке 1 формируется декодируемое слово кода HP — Ь =(b((..,..h(g) путем реализации соотношений

/ / / (!

О

b (=К(;+c<+c и <+c(r z,+c«» n=4k+ I

1с ОI I

Ь„=Е +а(+аицл(-а,(а+а m=4k-7, k=2. 15, И II знак + в индексах означает сложение целых чисел.

/ /

Разряды Ь,...,Ь»л передаются иэ блока 1 в вычислитель 2, а разряды

/ /

Ьл... »bg в формирователь !6.

Слово с входа 1 поступает в 20 блок 1, вычислитель 4 и корректор

3. В вычислителях 2 и 4 одновременно вычисляются локаторы первой и второй ошибок кода HP — 1 =(11 1

К Ь К1 Р

i ) I k=1,2 (в блоке 2) и (первый нижний индекс в обозначениях элемента полей СР(2 ) и GF(2 ) означает порядковый номер элемента поля, а второй нижний индекс — номер компоненты элемента) локатор ошибки 30 кода РС -Я =(Я Д1, Лл,, (блок 4).

Вычислитель 2, кроме того, формирует и выдает в другие блоки сумму первого и второго локаторов i=i + и

Л Ъ двоичные управляющие сигналы Wo W

Л I,35

Wg d-(» d P, 1о 1-л здес йсг

d1I14 и P — четкость суммы соответственно старших восьми разрядов, младших восьми разрядов и всех разрядов слова Ь ; W> =1, если в слове Ь/ про- 40 .исходит ровно j ошибок j=l 2 W = з ° ю

=О в противном случае).

В вычислителе 4 дпя получения локатора Я вычисляется упорядочен.ный синдром S слова с, равный 45 (S/ I $2.) (S($»ь $и в SgrII Sz@ SzzI Ъю

Szg)=(c„,...,сg,а„,...,а/4 ) Н г (1) где H — проверочная матрица кода

РС, Т вЂ” знак транспонирования.

Матрица Нр имеет вид где /, — примитивный элемент поля

GF(2"), являющийся корнем многочле4 на Х +Х+1. Матрица Н>С составлена таким образом, что двоичное представление элемента в виде четырехК мерного вектора совпадает с номером столбца, в котором он находится. В двоичном виде проверочная матрица

Нр/приведена в табл. 1, Вычислитель

4, кроме того, вычисляет элемент

P=)+i поля GF(2"). .Первый сигнализатор 7, используя сигналы Р, d/»y

dg,1o, 1л, i S u (!», формирует- двоичные управляющие сигналы Wo ) и

Wrrrr W, з"(д =1, если в декодируемом слове Г ошибок нет, а WoT =I если

/ ( в слове Г происходит неисправимая ошибка. W -- -1, если о =О, (=О и

/оеар) ( чи„=О. В этом слУчае слово Г выДаетсЯ на выход устройства без изменений.

Если же ошибки есть, они исправляются, При этом устройство реализует следующие три случая исправления ошибок.

А. В слове b ошибок нет, т.е.

WII=I. Тогда, если S» 0, то в слове с искажен один столбец с номером/ .=

S а значение ошибки в этом столбФ це "» =("о h(zIhqqIh d=Sg °

Б, В слове Ь обнаружена одна ( ошибка, в этом случае И»=Р=1. При этом сумма локаторов i совпадает с локатором 1», а величина р совпадает с величиной /1 +1,(. если оказывается, что л=1л, т.е. У»=0, то в слове с искажен один столбец с номером i

/ и h> =$, Если P=l и il4 !л, т.е. P ФО, или, если Р=l и $» 0, то необходимо отказаться от декодирования и первый сигналиэатор 7 формирует 1 ©гн =!., В ° В слове Ь/ происходит две ошибки в позициях 1л и ig т,е. W =l. В этом случае в слове с искажены два ( столбца с номерами i» и iа. Значения ошибок Ь» и hz в этих столбцах находятся из системы уравнений над полем GF(2"):

Вычисление значения ошибки Ь по формуле (2 ) реализуется вычислите1229969 лем 5, на вход которого поступают величины i4, i и S=(S4,Sz). Формирование значения ошибки Ь4 осуще1 ствляется с учетом правил А, Б> В и формулы (3) блоком 8, испольэующим величины P, Wg, Me, $4 и h<, Блок 6 на основе правил А, Б, В формирует "ускоренный" локатор

=(ь» х, ц, io) с учетом кратности ошибок.

При этом, если Wo=l, то i = g (пра,ф вило А); если P=l, то i< =i (правило Б); если 0 =1, то Р =i (прави ло B) .

10

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

Вычислитель 9 вычисляет четности

R4 Rg ошибок h4 v.hz одновременно

/ с вычислением ошибок h4 и h< Ь вЫчислителе 5 и блоке 8, используя величины Wo, М< Р, S и промежуточные данные, полученные в вычислителе 5 при вычислении h<. Такое вычисление

R4 и RZ ускоряет декодирование, позволяя исправить слово f одновре1 менно с словом с" .

Третий 12 и второй 11 дешифраторы дешифруют.четырехразрядные величины соответственно Л и iz форми уя 16-разрядные слова е (е,...,з5

-К -a>

-й -OQ -и1 (й е и е — (е ., °,, e > (для определенности здесь принято, что выходы дешифраторов инверсные, что обычно имеет место в сериях микросхем средней степени интеграции). При этом учи40 тывается, что в силу выбора матрицы

Нк соответствие между локатором и номером lg ошибочного столбца естественное, т,е, 45 з i<=+2 1„",, J-o

Первый дешифратор 10 аналогичным образом дешифрирует 1, формируя е (å " 1,..., e(" ), 8-разрядное слово, соответствующее информационным разрядам кода HP, Третий дешифратор 12 открыт, если M О, т.е. при наличии любых (обш) ошибок в слове Г . Первый дешифратор 55

10 открыт, если Mo=0 т,е, при наличии бшибок в слове Ь кода HP второй дешифратор 11 открыт, если M =1, Благодаря такому управлению дешифраторами в блоке 13, формирователях 15 и 16 при формировании корректирующих слов учитываются именно те ошибки

h<, локаторы ig и четности R которых необходимы в случаях исправимых конфигураций ошибок, Если M =0 и правило В не должно реализоваться, то в блоке 13, формирователях

15 и 16 не учитываются значения h<

1 и К .

Блок 13 получает сигналы Ф @

h h, е ), е ) и формирует корректирующее слово Е кода РС, равное О если We(о"Э=1. Корректор 39 су . Руя по модулю два слово Е со словом с, формирует исправленное слово кода

PC с=(с4...,,с, а,„...,а и выдает его на выход 1 устройства.

Формирователь 15 получает величины R<, Rz, Wo е, е и формирует корректирующее слово F=(Fo Ру ), равное О, если Mo l =.1. Корректор

14, суммируя слово F со словом f формирует слово исправленных смешанIt ных" разрядов f=(f,...,Й,-) и выдает его на выход 2 устройства.

Формирователь 16 получает величины е и е Н и формирует корректирующее слово B=(84,...,В8) и, суммируя

I разряды b р ° уb11 со словом В ° полу чает информационные разряды кода HP

Ь,...,Ь которые проходят на выход

3 устройства.

Исправленные информационные раз-. ряды а,, °,ар Ь,...,Ь11 поступают к пользователю памяти.

Исправленное слово составного кода Г (с„,...,cg» а,,...,а fo.

Е1 ) поступает в память для перезаписи, Вычислитель 2 (фиг, 2) работает следующим образом, Декодируемое слово кода HP поступает на входы первого формирователя

17 и формирователя 18. Последний вычисляет расширенный синдром кода

HP, реализуя с помощью сумматоров по модулю два соотношения с-t т (бо < мбоо 6 6ц б д©) = (bo ° в Jbqg) H„p (А ...А ) =(Ьр...b ) H ; . 1„,-Ь,+Ь,+...,+b„;

„с <

Р 1"1н где Hgp и Н вЂ” матрицы, приведенные в табл. 2. При умножении вектора на матрицу i-й разряд произведенИя

1229969

l0 находится как сумма по модулю два трех разрядов слова Ь, номера ко/ торых соответствуют номерам единичных элементов i"é строки матрицы. ! (Например, 4oz=b((+bq+bq+bw.

Вычисленные таким образом элементы (3О, 6 поля GF(2 ) и двоичные

Ь величины А, Аь, AT, Ag поступают на выход 1 формирователя 18, отку- IÎ да проходят в формирователь 20 и второй формирователь 19. Величины

Ag, А5, А (иА поступают на выход

3 формирователя 18, откуда проходят в формирователь .20. Двоичные величи- 15 ны Й, (1м)(, и Р поступают соответственно на второй, .четвертый и, пятый выходЫ формирователя IS. Величина

Йм)(проходит во второй сигнализатор

25 и на выход 3 вычислителя 2, Вели- 20 чина P поступает на выход 5, вычислителя 2. Величина d - поступает в блок . 21, второй сигнализатор 25., блок 22, формирователь 24 и на выход

1 вычислителя 2, как старший разряд суммы локаторов.

Первый формирователь 17 с помощью сумматоров по модулю два вычисляет величину Р путем умножения слова

Ь на транспонированную матрицу Н 30 (табл. 2 - проверочные матрицы кода

Нордстрома-Робинсона) т (ji P4 f o ) = () о ъ ° ° ° э Щ Н4г р

Величина 4 поступает с выхода этого блока на входы блоков 20-25 и на первый выход вычислителя 2 образуя младшие разряды суммы локаторов i= (йд; fz, Д,Д). Величина Ь с выхода

1 вычислителя 2 поступает в блок б, 40 вычислители 4 и 5 и первый сигнализатор 7.

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

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

При этом реализуются соотношения шф Афр+бог+о()0 )41 + любо)э шо=А 8+А (+6оо+ 6) (Йг+6о А мг Gг+ (m +mo)+" 2+р г(р A+mm); мр + (m + )+мг р.

М -uW (m +m )тг.

Величина M с выхода формирователя

19 поступает в блок 22.

В формирователе 20 с помощью сумматоров по модулю два и элементов

И-НЕ вычисляется дискриминант (РрР((), который позволяет вычислить третий и четвертый варианты младших разрядов локаторов i((в третьем фор" мирователе 23 определить конфигу1 рацию ошибок в слове b . Формирование дискриминанта выполняется путем реализации соотношений

Dö D-А,+6ррр;р+ (а (7;

Do< =A)(+A 6 ++(((+ ()A );

Роо =А + о (" + д д;

D z. =А(,„ (-4Я о(Po P;;

Р(,(=А +Х + p f„+P g;

0" () =А((+ г л + gЯ

Величины D è Р,(с выхода форми-. рователя 18 поступают в третий формирователь 23 и блок 21.

В третьем формирователе 23 вычисляются третий Zo и четвертый 24 варианты младших разрядов локаторов

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

Z«=D,,С„+В С, +О„(Д+P);

2к(=Ж-(+ Д-г 1 г„;ог, + г,(+p ), м-о, (, где С(=ф+Д, Ср=ф+Д, Сз=ф+Д+Д (Величины (), с выхода третьего формирователя 23 поступают на вход блока 22.

Блок 21 формирует двоичные управляющие сигналы К4 в K» K> ° )(о ° V4 е

20, Я„, позволяющие определить конфигурацию ошибки, выбрать нужный вариант младших разрядов локатора i< и сформировать старший разряд этого локатора, Сигналы „, Х,(формируются путем сравнения дискриминанта с нулем с помощью элементов ИЛИ-ЙЕ следующим образом: (1, если 0((=0, 0, если ЭкФО, k=0D1 ° (Сигналы р и 1 с второго выхода блока 21 передаются в блок 22, второй сигналиэатор 25 и на выход 5 вычислителя 2. Ф .

1229969

Сигналы Ч и 71 формируются для выбора вариантов младших разрядов локатора i4-Zo и Z4.

V,-P„O„+ O, +D,,(+Р);

1 „= pD,„+рб;+D, (Р+р), С выхода 3 блока 21 сигналы V и 74 поступают s блок 22.

Выбор нужного варианта локатора выполняется в блоке.22 с.помощью 10

4 сигналов. Кл, Kg, К5.

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

1.: Если Р40 и 2р+Ьл=1, то происхо. дит ошибка с локатором =(Ц,II

A Д).

Если, кроме того, дат+ а=1, то еще искажен разряд bg а если p+d<+f =), щ ! то искажен разряд bp ° В этом случае.

К4=1, К2=K5-=0.

2. Если 1ш"=1ь fî=14=Ð.=Î, то проис ходят. две ошибки с локаторами .х4 и

1З, где i4=(0, N<, М4, М„), а 1 ап- 25 ределяется из выражений

i =d +Ö, im=g+i gi 1=0,1,2 (4) .В этом случае К 1, Кл=К =О.

3. Если 1о=1л =d -,=Ð=Î, .$40» то про-3{) исходят две;ошибки с локаторами где х4 =(1, Z<, Ещ Ер, если

Vy =1, либо х, =(О, Z4», Е „, Z<), если

Ч =1. ig определяется по выражениям (4}, В этом случае К =l, Кл=К =О, 4. Е Р=Е,= „=1, пр одна ошибка с локатором i -=(d -,, 0,0, О)., а Кл=К,=К =О.

5. Если Йо=f» =1 Р=О, Q !, т.о происходят две ошибки с локаторами 4О з.л и 1., где 4=(0, О, О, О), хр. определяется иэ выражений (4}, а Кл=

-Кз.=к =o.

6, Если =0, d I=d 0, .то ошибок нет. 45

7. Если ошибки есть, то не выполняется ни одно иэ декодирующих правил 1-6; или, если в правиле 1 одно-

I временно искажены разряды bg, и bg, .то необходимо отказаться от декоди" 51» рования в предположении, что произошла ошибка, кратность которой не менее трех, В соответствии с этими правилами блок 21 с помощью сумматоров по модулю два. и элементов ИЛИ-НЕ, НЕ формирует сигналы. Кл, К и Кл следующим образом:

l2

К» = . + Ц, К = 1оЧ л Ч 1с7ь

" ™ которые .с выхода 1 блока 21 поступают в блок 22. В соответствии с . ука ванными правилами второй сигнализатор 25 формирует двоичные сигналы

W об ошибках путем реализации выД р ажений

Wo=daYd V,Y

W, ddt а„, W, =31„ЧГ 1„„,Ч Р, ДДйд, с помощью элементов ИЛИ-НЕ. Сигналы

W1, j =О, 2, 1, выдаются этим блоком соответственно на выходы 6 и 4 вычислителя 2 и выход 4 устройства.

Блок 22 с:помощью управляющих сиг налов Кл Ка ° Кб ° Vg y Vg 2 4 фор мирует локатор i„

4 =Кл 2 V K3Vo Vlo iq d q

4 =К„РЧК,М,ЧК Ч,Z,„ÐK V, Z„>, 1=2,1,0 (л . с помощью элементов И"ИЛИ-НЕ, НЕ, который с выхода этого блока прохо-.

: дит.на вход формирователя 24 и на выход ? вычислителя 2 °

Формирователь 24 с помощью сумматоров по модулю два реализует выражение (4) для локатора ig, который проходит на выход 8 вычислителя 2.

Вычислитель 4 (фиг, 3) работает следующим образом, Слово с с входа 1 вычислителя 4 поступает в формирователь 26, который с помощью сумматоров по модулю два реализует умножение слова с! на транспортированную матрицу Нщ в соответствии с выражением (1), Первая четырехраэрядная часть синдрома Зл поступает на вход I, вторая четырех" разрядная часть - на выход 2, Весь восьмиразрядный синдром $= (ЯЛ5, $л, Ялл, H o,Я,Я,Я л,Д,» проходит на вы" ход 3 вычислителя 4.

Первый формирователь 27 формиру" ет обратный элемент s поле, реализуя таблицу истинности (фиг, 3), например, с помощью соотношений ь=Бл, $а ч S S Se Y Б„ДЛМ л и S«Y

Ч888лААь

Qg Se. u Sqpv SqgS zS4IЧ 8лДт8ло АФлАоЧ

"S4354a л She

55 9л = е8уиР БлДз кР 8л 8ла8Ф 4A?,Ъ Ч

v БлД Ь, 1о=В Д 8 8 Бл 8ла8л 4оЧ8лАФю Sloe"

Y SeS4 S ov-льЪ ч АА13

1229969

i=3

i=2

i=1

i=O

j=l, j=l

j=l, Д С»

4, 5, 6 (5) 45

j=O, 1, j=1, 2, j=1 2, «1=0, 1, 4, 5, 6

2, 3, 9, i=3

i=2

i=1

i=O (6) 55

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

)1г; = »,„. Spj i» j=0» 1, 2, 3 °

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

Р =riSz+i-- +i .

При этом с помощью сумматоров по модулю два и элементов НЕ реализуются соотношения .,» .ь Р»ь Уз >pq», p»g г .м 1 ЗБ "102 ")" БА г н >p>р )2

= 3 43,г "»3 Р 22 ) 4г +) p4 ю у+Р„оф, Ро = P la») » г Р Р»»0 -+ ф

Формирование суммы)<= 1+ раньше сигнала il ускоряет формирование сиг-, нала отказа до декодирования We

Сумматор 30 формирует локатор Л путем реализации поразрядного сложения по модулю два Р и к=/Ц "К» 1--=-0, Элементы /И и J) выдаются соответственно на выходы 2 и 1 вычислителя 4, Блок 6 с помощью элементов ИЛИ-НЕ формирует "ускоренный локатор путем реализации соотношений

1 =dz»+vWz з Ч1 Д, i =Pg v 1"1г i„v W„) "- k=2, 1,0.

Первый сигнализатор 7 с помощью элементов И-НЕ,HE И-ИЛИ-НЕ формирует сигналы М и Wpy< соответственно ,<ОБщ об отсутствии ошибок и об отказе от декодирования, реализуя выражения (ОБЩ), Ч =E

Я„=р,ч,у р и,ЧРм„ЧРро» 31г=Е,» Ez Wz»

Wp y, =Р, ч d lp Э 7 Ч Q > И 71

Сигнал VpT»; поступает .на выход

5 устройства. Если Woi =1, то вычислительная система, использующая устройство для декодирования, не принимает слова с выходов устройства 1, 2 и 3, считая их ошибочными.

Если Wp»„=O то вычислительная система принимает исправленные слова с выходов l, 2 и 3 через время % после ввода слова Г в устройство для декодирования, причем Ь» CV

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

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

14 лЪ »о» .8е=8 ъ8а» 8 а=81г+Sg » которые поступают в третий формирователь 35.

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

Sq В zp; "г5 гъ+ ; S =Вгг+Вг»

ВйВго+8г Ъ=S„+Sg; Ягя=яц+Вг, которые поступают во второй формирователь 32.

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

:P= т аналогично первому формирова"

35,, телю 27. Элемент Р поступает во второй 32 и третий 35 формирователи., Третий формирователь 35 с помощью элементов.И-НЕ формирует 16 частич-.

40 ных произведений »1 =pl S

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

@1г .Si) ° где значения i j следующие: и они поступают в блок 36.

1229969

Частичные произведения Кщ, Кл s К д Кго проходят на выход 3 вычислителя. 5 н поступают в вычислитель 9, Второй формирователь 33 формирует линейную функцию у ê =($4), k=

=3, 2, 1, О, реализуя с помощью сумматоров по модулю два сигналы

9,,=9„+f,„+9„+9„; 1 г = 4s+ Ь+ 1лл + ого

Ф,, = f + д+ Рлл + Рол;

1о =gy+ y+4 s+fee

Kqj =igg$S, где индексы i j.ïðèíèìàþò значения (5) и (6), 16 произведений с индексами йз (5) поступают в третий формирователь 36, а произведения Кклг, Кг, К(, К 9 проходят на выход 1 вычислителя 5 и поступают в вычислитель 9, 40

Третий формирователь 36 с помощью сумматоров по модулю два формирует линейную функцию и г = Б.л г л + Бг. путем. реализации выражений

1 г Къч К гл Клг Кй Кгг гл Клг 05

Ьгг=К„-+ йг + Ь+ Еог+ Ъ+Кгч+Клл+Ка+ Фт э

1 лл-Юс+Кгл+Кл л+Кол+КглйКггл Кллл Кл " % 1

1ггсг Кзл Кгг Кл + Йо+ зл+"=гг s p9 л

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

Блок 8 с помощью элементов И, ИЛИ.55

HE формирует значение ошибки 4< путем реализации соотношений

Ьлк=РБ Фг,Б W2h)„Sq,VM(> Блк k=O 1 2,3 которые поступают с выхода второго формирователя 33 в третий 39 и чет- 15 вертый 37 формирователи, Третий формирователь 39 с помо" щью сумматоров по модулю два формирует сигналы ф,=Ч"+Ф Ч-=Ф+Ф. 1 =9+9 . 1 = Фл+Фо 1

f 3 = 6+ 1» 1 ФЯ = Фч+Ф6 В т, = f1+ 61

-Величины ф ...,, фэ поступают в третий 36 и четвертый 37 . формирователи, величина ло проходит на выход

4 вычислителя 5 и поступает в вычислитель 9.

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

Вычислитель 9 с помощью элементов

И, ИЛИ, НЕ и сумматоров по модулю два формирует четности ошибок R4 и

Rg реализуя выражения

R(=PRgV ЫОКЗЧ(л1Л2КФ1л1г Рг Rgю

Е2 К3о+КФ» Кд+Ко9 Къо Кгт Клг КФ лгюв

Блл+Блг+Блк+ Бл

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

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

Блок 13 формирует 64-разрядное корректирующее слово Е кода PC пу" тем реализации соотношений (o69 (л), (г1, Емк л 1 л(4-лл)е к (1 г(л.ллл1ек б л (7)

m=1 ю2лЗл4; k=0þ l »15 ° Формирователь 15 с помощью элементов И, ИЛИ, НЕ формирует корректирующее слово Г путем реализации выражений

Рк =И " )(R4ФВа4, 1с=0, . ° 15, (8)

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

1 -м столбце слова с, Указанные выражения для корректирующих слов кода PC и кода HP могут быть реализованы с помощью мультиплексоРов. ДлЯ этого. сигнал Ил, к11по( дается на стробирующий вход, сигналы е"ц, е(„на адресные входы, а сигналы Ьлг4лл,1, f h q>), В.л, R2, — на информационные входы. При этом полярность сигналов e() е® может быть как пря.моф так и инверсной в зависимости

1229969!

W(abvcd)=Wv(abvcd) c„=c„ +Е 1, n=4k+m, kOý l Ill=1 2 3 4ó а!1=а<+E n=4(k-. 2)+m, k=2,3,...,I5; m=1, 2, 3, 4.

Твбливв.1

1

1

I 1

I

1 1

I 1

I 1

I

1 1

I 1

I I I ! I 1111.! I

1. 111 1

1 I

I !

1

I I 1

I I

l I

1"

1 1

I

I I

I

I

1 1

I I

1 1

I I

I 1 1

I I I ! 111

I I I I !

I 1

I I

I 1

I в», °

1 !

I вя, I

I 1

I I

I I 1 I I

I 1 1 I

1 1

1 111

1 1

1 1 I I I

I 1 1

l I I 11

1 l

I I

1 I

Таблица 2

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

jO 1 2 3 4 5 6 7 8 9 10 ll 12 13 14 150 0 0 0 1 1 1 1, 0 0 0 0 0 0 0 0

О 0 1 1 0 0 1 I 0 0 0 0 0,0 0 0

0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 от выбора адресов в мультиплексора.

Выражения (7) и (8 ) можно реализовать также на элементах -HJIH-HE ,ИЛИ-НЕ. В этом случае сигналь! е "!и () е нужно брать в прямой полярности.

Для этого используется соотношение

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

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

fI,=f1,+Fg) k=O,1

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

Ь =Ь +е е""ф k= 1,...,8.

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

1229969

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

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

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

0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1

ИИР

0 0 0 0 0 0 0 0 0 0 1 0 0 1 1

0 0 0 0 О 0 0 0 0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 1 1 1 1 1 .1 1 1

0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1. 1 1 1 0 0

0 0 0 1 1 1 1 0.0 0 0 1 0 0 0 1

0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 0

0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1

0 0 0 1 0 0 0 1 0 0 0 .1 1 i 1 0

0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 1

0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0

0 0 0 0 1 1 1 .0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1 0 0 1 1 0 О. 1 1

0 0 1 0 1 0 1 0 1 0 1 0 1 О 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1229969! ) 29()с,ч

1229969

Фиг. 4

Сто кода РийтСмеМанное споро сЮ кодод Рида -Соломона и НирдопчромдРооинсона

Pug.s. Составйтещь А.Андрианов

Редактор Е.Папп Техред Л.Олейник Корректор р

M.Ñâìáîðñêàÿ

Тираж 816 Подписное

ВНИИПИ Государственного комитета СССР . по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 3678

П оектная

Производственно-полиграфическое предприятие,.г,ужгород, ул. Проектная, 4