Устройство для декодирования с исправлением ошибок
Изобретение относится к вычислительной технике и связи. Его использование в устройствах обнаружения и исправления ошибок позволяет повысить достоверность декодирования за счет исправления до трех пачек ошибок. Устройство содержит блок 1 задержки, формирователи 2...5 проверочных символов, блок 10 определения ошибочных позиций, блок 11 исправления ошибок, блок 12 управления, элемент И 13 и элемент ИЛИ 15. Благодаря введению формирователей 6, 7 проверочных символов , арифметического блока 8, блока 9 вычисления коэффициентов и элемента И 14 в устройстве обеспечивается решение показательного уравнения третьей степени , лё GF (2m), что и позволяет достичь цели изобретения. 7 з. п. ф-лы, 9 ил.
СОВХОЗ СОРЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)5 Н 03 M 13/02
ГОСУДАPСТВЕННОЕ ПАТЕНТНОЕ
ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4819741/24 (22) 28.04.90 (46) 23.02.93. Бюл. ¹ 7 (71) Научно-производственное объединение
"ЭЛАС" (72) А. И. Карпухин (56) Патент США ¹ 3629824, кл. G 06 Г
11/12, 1971.
Авторское свидетельство СССР
¹ 1411981, кл, Н 03 М 13/02, 1986. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ
С ИСПРАВЛЕНИЕМ ОШИБОК (57) Изобретение относится к вычислительной технике и связи. Его использование в устройствах обнаружения и исправления Ы 1797165 А1 ошибок позволяет повысить достоверность декодирования за счет исправления до трех пачек ошибок. Устройство содержит блок 1 задержки, формирователи " 2...5 проверочных символов, блок 10 определения ошибочных позиций, блок 11 исправления ошибок, блок l2 управления, элемент И 13 и элемент ИЛИ 15. Благодаря введению формирователей 6, 7 проверочных символов, арифметического блока 8, блока 9 вычисления коэффициентов и элемента И 14 в устройстве обеспечивается решение показательного уравнения третьей степени впо-. ле GF (2 ), что и позволяет достичь цели изобретения. 7 з, и. ф-лы, 9 ил.
1797165
55
Изобретение относится к вычислительной технике и связи и может быть использовано в устройствах обнаружения и исправления до трех пачек ошибок, возникающих при хранении или передаче дискретной информации.
Известно устройство для декодирования с коррекцией ошибок, содержащее блоки данных Д1,...,Дп, каждый из которых имеет 8 бит (байт) плюс два контрольных байта.
Недостатком этого устройства является большое оборудование и излишняя избыточность при обработке 2"-разрядных слов.
Из известных устройств для декодирования с коррекцией ошибок наиболее близким по технической сущности является устройство для декодирования с исправлением ошибок, которое содержит входной сдвиговый регистр, четыре формирователя проверочных символов, блок исправления ошибок, блок управления, два элемента И и элемент ИЛИ.
Недостатком этого устройства является невозможность исправления трех пачек ошибок, что приводит к снижению достоверности и ри передаче информации.
Целью изобретения является повышение достоверности декодирования за счет исправления до трех пачек ошибок.
На фиг. 1 представлена структурная схема устройства для декодирования с исправлением ошибок; на фиг. 2, 3 — функциональные схемы формирователей проверочных символов; на фиг. 4 — функциональная схема арифметического блока; на фиг, 5 — функциональная схема блока вычисления коэффициентов; на фиг, 6 — функциональная схема блока определения ошибочных позиций; на фиг. 7 — функциональная схема блока исправления ошибок; на фиг, 8 — функциональная схема блока управления; на фиг. 9 — временная диаграмма работы устройства.
Устройство для декодирования с исправлением ошибок содержит блок задержки
1 (фиг. 1), выполненный на сдвиговых регистрах. шесть формирователе проверочных символов 2, ..., 7, арифметический блок 8, блок вычисления коэффициентов 9, блок определения ошибочных позиций 10, блок исправления ошибок 11, блок управления 12, два элемента И 13 и 14, элемент ИЛИ 15, информационный вход 16, тактовый вход и вход ПУСК 17 и 18 и выход 19, Блок задержки 1 содержит (2 +5) .m разрядов, где m — степень неприводимого многочлена в поле GF(2 ). имеет последовательный информационный вход и вход тактовых импульсов (ТИ), группу параллельных
m выходов (с первого по а-й) и последовательный выход. Далее принимаем m=4. В этом случае блок задержки 1 будет иметь 84 разряда.
Формирователи 2, ..., 7 служат для формирования соответственно с первого по шестой проверочных символов. Первый из формирователей 2 включает всебя (фиг,,2) с первого по третий буферные регистры 20, 21, 22, сумматор 23, вычитатель 24 и преобразователь кода 25. На фиг, 2 обозначены также информационный вход 26, управляющие входы 27, 28, 29 с первого по третий и выход 30 формирователя, Другие формирователи (3 — 7) включают в себя (фиг. 3) с первого по четвертый буферные регистры 31, ..., 34, первый и второй сумматоры 35, 36, вычитатель 37 и преобразователь кода 38. На фиг, 3 обозначены также информационный вход 39, группа управляющих входов 40, управляющие входы 41...;, 44 с первого по четвертый соответственно и выход 45 формирователя.
Арифметический блок 8 включает в себя (фиг, 4) с первого по двадцать шестой вычитатели 46...71, с первого по тринадцатый сумматоры 72...84, первый и второй умножители на 2 85 и 86 и с первого по девятый преобразователи кода 87„.95. На фиг. 4 обозначены также с первого по шестой информационные входы 96...101 и с первого по двенадцатый выходы 102...113.
Блок 9 вычисления коэффициентов включает в себя (фиг. 5) с первого по одиннадцатый вычитатели 114...124, с первого по шестой сумматоры 125...130, с первого по шестой преобразователи кода 131...136 и первый, второй и третий регистры 137, 138, 139. На фиг. 5 обозначены также с первого по двенадцатый информационные входы
140Ä,151, с первого по третий выходы 152, 153, 154 и управляющий вход 155.
Блок 10 определения ошибочных позиций (фиг. 6) включает в себя с первого по пятый сумматоры 156...160, с первого по седьмой вычитатели 161...167, с первого по шестой преобразователи кода 168...173, схему сравнения 174, с первого по третий регистры 175, 176, 177, схему ИЛИ 178 счетчик 179 и с первого по третий вентили 180, 181, 182. На фиг. 6 обозначены также первые информационные входы 183 — 185, управляющие входы 186, 187, вторые информационные входы 188...190, первые выходы
191...193, вторые выходы 194...196.
Блок 11 исправления ошибок включает в себя (фиг. 7) три узла по числу исправляемых ошибок, каждый из которых содержит с первого по восьмой сумматоры 198...205, первый, второй и третий вычитатели 206, 1797 65
207, 208, первый второй и третий преобразователи кода 209, 210, 211. На фиг. 7 обозначены также с первого по девятый входы
212...221 и выход 221 первого узла, с первого по девятый входы 2222.„230 и выход 231 . второго узла и с первого по девятый входы
232„.240 и выход 241 третьего узла, Блок 12 управления (фиг. 8) включает в себя первый элемент И242 на два входа, счетчик 243, дешифратор 244, с первого по восемнадцатый элементы ИЛИ 245...262. первый, второй и третий элементы сравнения 263, 264, 265, со второго по седьмой элементы И266...271, девятнадцатый и двадцатый элементы ИЛИ 272, 273 на три входа каждая, На фиг. 8 обозначены также тактовый вход 274, вход 275 сигнала "ПУСК" и первый выход 276 сигналов ТИ, первая группа выходов 277...279, вторая группа выходов 280...284, третья группа выходов
285.„289, четвертая группа выходов
290...294, пятая группа выходов 295...299, шестая группа выходов 300...304, второйшестой выходы 305 — 309, информационные входы 310„.312.
Сумматоры 23, 35, 36, 72...84, 125...130, 156...160, 198...205, соответствующих блоков работают по модулю 2 -1. Если выходы регистров 20 и (или) 32 имеют во всех разрядах единицы (со), то передача суммы с сумматоров 23 и (или) 36 на регистры 21 и (или)
33 запрещается, для чего регистры 20 и (или) 32 имеют специальный выход, закрывающий входные вентили регистров 21 и (или) 33.
Вычитатели 24, 37, 46...71, 114..„124, 161, 167. 206, 207, 208 соответствующих блоков работают по модулю 2 -1. Вход уменьшаемого вычитателя 166 принудительно обнулен.
Преобразователи кода 25, 38, 87...95, 131„,136, 168...173, 209, 210, 211 осуществляют над входной величиной z преобразование сФ() =1O+ а, где а C GF(2 ),e— суммирование в поле GF(2").
На фиг.9 изображены тактовые импульсы ТИ по циклам и соответствующие управляющие сигналы. При совпадении вычисленных значений ошибочных позиций
Рв4 со значениями счетчика из блока управления v,q блок 11 выдает позиции ошибочных символов (и,ш), соответствующие примеру, приведенному в описании принципа действия устройства.
Принцип действия устройства декодирования с исправлением трех пачек ошибок заключается в следующем, Кодовые слова, поступающие на вход устройства, содержат по (2 -1) m-разрядных информационных символов Ki(!=0,1„.2 -2) и шесть проверочных символов Kg(9 =0...5), формируемых в кодирующем устройстве по формулам
10 знак,Ё, означает суммирование в поле GF(2 ), примитивный элемент а которого является корнем неприводимого многочлена f(x) степени m; f(x)=x +х+1, "+" — сложение в кольце по модулю (2 — 1).. 15 Если в информационной части кодового слова при передаче или хранении информации возникли ошибки в трех символах, то ак — сформированные в декодере проверочные символы — определяются по форму20 ле " г™-г К K Об Э о4 1ЭС Э iа--О i.jg1 gf o> ."" г, (г! где д! . др. и дф — величины ошибок на j-й, s"A, (-й позициях соответственно,о — сложение в поле GF(2 ). Формирование проверочных символов в соответствии с формулой (1) можно записать так: к, pm + (2 +2! Обозначим сумму первых, двух членов 1 а, сумму a с третьим членом — ак и т.д. Тогда: (йо х ф к, Я < g(o -ê,-Ð) 40 или К1 =К1г+9+ Р(Ко-К1 9) где (У() =1& aÐ (3) и операции сложение "+" и вычитание "-" производятся по модулю (2m-1). В общем случае будем иметь; К! =К +! 9+ у (К!-1 K1 9). Очевидно, что Ко =Ко, и 50 Kg= Кг "-1+(2 2) g +p(K3 з— Кгп -г — (2 -2) g). По проверочным символам Kg u Kg формируют синдромы ошибок Ф =а 9 а в, (4) откуда: 1797165 Аналогично откуда! I Ь<+а< Ь24а2 Ь аа 10 м Ь2+с<< h<< с»2 < сс A» »O<@ A4tO2 g A<2 Ю или Аналогично: Далее из (12) и (13): Д. а2ВМДЬ+Д.ОМ Д4.Ь. Q с,<. !33 oh < A24h, <а, сь В A» <. A2i Q2 h44h,» В « ., 2д2Q Д2+ До 2О<оьд4 д2 d Ag2h< 30 откуда: ЬЬЗ < @ Д4+да М. Г<3 OI 1 2ь», да<- о Я М A 2+ h < h»< < h <» h2> hî О<. сь ьь О<. М д д Ос< Ь Ь 2Ь2 ® „Ьз4Д< „ь ьЪ4 д2 I A4+h» Яб 2h2 hih, 411 I з с((сГ $ d »19<<((с» О с(,1 <»»<:(= 0 50 (12) (13) 55 (и) или , -de 86ij v,r) где Тогда: о СЬ )а3 СЬ h k Kc М !а<За ЭЬ" 23О К 4) К 41 дЬ <„1 (j) oh ф сЬ к »Rj К,.З) К с М К . 1 ! 3Ь -М. 6>ОЬ К;441 К,444 k +46 <3С -сь Юм . Sob ho К)45j 44 Кт+-"" Ы, 06 Ось Юсд Умножим (5) íà а) и сложим с (6), Получим: d ë 0,(ь =ак И аа )0,((А "в,() ! 42 К 64») йа 42» ка(<6)(9%o)(13 064»4 К (261924т Умножим (7) на а и сложим с (8). Получим I »3<2 < 1»@d h»(+I+d
Аналогично: 2 Е К, "(сЬ)а Ь )аь .Ь =o. 3 « (oh e Умножим (9) на а. и сложим с (10). Получим о > " »3 (0 g )2>„(-,(Д 1 !Э dд2 И аО,(д) Е,(49, Обозначим j +1+ =aoo ; а) о/@Д = ; а) +1 Е а) + Оа2 +.4 = Тогда (11) запишется так; I (»»о+ <2<» I3 +<2 Д <.(2 g g 2 < h + » ea(» 1 =. о, < < S l »32 <2»I »3д»2» (2„ »12 с»1,с I l 2Ь»<-а, Ь24A 4o2 ь2" д<»+а<(»3 d d» fhо 2 и ЬA»4A2+o2. Ь4+Д2 и сь ЯМ I < 34 d< Фс<< Ь4» <»а2 65+д< О Аналогично из (12) и (13): 4а< A» fh, A2+h04a A4+ho сь в ь, д, h»+h. ! О»», 2h2+a, „д4.+ д2@, h»»+A< i<-<2О ь д64 д» В о6 О м Ось Дъ Даю ьh4 h» Откуда: Ьъ4 Ь»» до+до д4+д2» д5сд» м eoI <К !ас a< сЬ О+ c-" h,+h, д, Ьа Ь, д, h4+d< <
»;. 2Д в сдЬ2+Д, И2в оьдъФД о! Ьз+ho ha< h2 ® д4+до Q o6 ск ЮсЬ Обозначим а1 = Л) — йо, а2 = Ь2 — Ь, аз =Аз — Ьа, а4 =Г34 — й, ац =Ье — А, Тогда с учетом (3): 42 Ь -h»!. ho ° ha <3» J3<»4 Ь24Ь Ь4+Ь Ogth< 4 g(O4-с»<3 Оrh, Ь»4Ь<, и » Lo Ь»4Ь,4(Р(а»-а,) а,4Ч(oа-о,)-q(а,-оа 1797165 Аналогично:,Ь4 Ьд(аedsбЬ об ч (о -ад)-бд(а -ад) д д Ьбб Ь4 44бЬ1 аь. „ь,. ь. бд(об-a )-cp(as-a,) -а К д,„ь, ь,, a„-ь. Юь ь, ь, Оь бб(об-об)- (о4-а4-a,)-о г д Ч(ад-а,)-g(as-a,)-aд Ч(о -а,)-<у(о,-а,-;)-о, Аналогично преобразуем аг . Получим 15 Равенство (21) распадается на три: p(v — bo) = pa, p(2v-b) — b,(р(1 — Ь,)) = оо, p(3v — b2- b1 — ь, p(v- bp) -p(2v-Ь1-Ь Ч (-b )))= или,учитывая,что p(p(b)) = Ь M p(aa) = О, получим: 1 -bo=0, (22) 21д- Ь1 — Ьо — p(1д — Ьо) = О, (23) 31- Ьг- Ь1- Ьоp(v Ь.)— p(2V — Ь1 — Ьо p(V — ba ),)) = О. (24) Уравнения (22), (23) и (24) являются уравнениями первой, второй и третьей степени соответственно. Уравнение (24) преобразуем с учетом свойства функции p(z): p (z)-ф-z)=-z. Получим Ь2 — v+p(b1 — 1д+((Ьо v)) =0 или Ьг — Ь1 —. Ь, + bp — 1д + p (Ь1 — Ьо + Ьо — )д + p (Ьо -Р)) = О. (25) Обозначим bo=v=y, b)-bo=b*, -(Ьг-Ь1)=с, тогда (25) примет вид Ь "+у+ у.(Ь "+у+ фу))=с. (26) Формула (26) позволяет представить уравнениетретьей степени(26) как функцию двух аргументов Ь и с, т,е. y=f(b, с). Составим таблицу, в которой c=f(b*, у) 5 образуют замкнутые кольца по модулю 15. Для удобства далее начало кольца будем счита.ть в ячейке с b*=0. Кольцо с началом в ячейке(0,0) обладает свойством у=с (26.1) Кольца с началом в ячейках (0,5) и (0,10) обладают свойством с),)= ф-Ь(+). (27) Остальные кольца обладают свойством: p(c-d(;)+ б — -bo*, (28) где А — величина, на которую нужно уменьшить соде окимое ячейки (Ь", у), т.е. с. чтобы кольцо имело такую же последовательность элементов, как и функция фг); Аналогично из (15) определяем ао, Получим 20 Из (12) j=ao1 — v- (; подставляя в (13), пол- 25 учим 30 откуда: 40 откуда I ,{а у,<" "= О(Из(16) и(17) 50 I или, умножая на,а" I / Тогда а1 примет вид: 1 б Ч(а4-a,) Ч(аь-а,) абб(ф(а -а ) ц(о 4- Д 6ь а 4Ь os о4бЧ(об-а,)-Ц(а,-а,) а, а,бч(а -ад)-дд(а -о ) Щф, 2 д Ьод ч(аб-о)-д4"(о -а,) asst (а4-as)-àð(as-о,) Ю4Ь 4(Ч(4- 41- б(аs ад) 044+(ag-os)-q(a4 а ) „Ч(а1" а.)-Ч (оъ-аб)-2ад (p(asa ) (, фд4 4 Ъ,ьоо -(O 1 = " или, умножая на а1 обе части: ар - Р Рб О бР g(О (Г "б E 2Р а2 Р Аналогично из (14) получим I I ао & c(аo-Р, " = c(as I 1 ((ая+Р „4(оо-Р as д откуда юЯР iадбР аосте<(4 - g Представим уравнение (18) в виде О(@ о(И "Оа (а(®д:())=О Раскрывая скобки, получим В2 2 д -p o( Из сравнения (18) и (19) вытекают соотношения; между a) u b) аг =Ьг, 1 Ь2= а12 1 а1 =Ьг+Ь1, Ь)=а) -аг, (20) ао =b2+b1+bo . bo=ao — а1 . 1 1 Из (19), используя табличную функцию р (г) (3), получим Вд В.-В.. (Р-В.) - т Р-tq-В. - y(a-E.)) 4 ц(" дд" В4 < 8<- ГР Iî)- ГОР-В Во Ф - Sô@ О Д О О об 1797165 k-Ьк* — элемент кольца с координатами (О,bk*)=bk*, по которому определяются dg и 6к. 6к — число позиций, на которое нужно сдвинуть кольцо, чтобы привести его к виду (27). После преобразования p(c-d>), в результате которого элементы кольца располагаются по порядку; 6i<- числу.позиций сдвига. После преобразования (28) в каждом столбце матрицы элементы са=-Ь*. dk= p(g) + bv, (29) 6i, = р (ЬФ) — г ЬЗ (30) - причем бк= 615 — k Подставляя в (28) значения dg и бк из (29) и (30), получим; уу (С вЂ” ух (Ь??) — bv) + ух(Ь1?) — 21,? = — bo (31) Раскроем(31) учитывая, что bv = bo — v т,K. v = Ьк — Ьо . y(c — p(bo*+v)- (b,*+v) +p(b +v)— (bo + 1?) - bo v = -bo, или сокращая на -bo*и учитывая свойство функции p(z): p(c — p(bo+v)-(Ь*+v))+р(-Ь -v) =v откуда .. с учетом (29): р(с — dv)+p(-bv) =v, (32) Уравнение (32) выполняется только в том случае, если х=у. Пример. Решить уравнение + хх ?? > х3 с(Вс Ес Ы =О В соответствии с (20): b2=11, Ь 1=13-11=2, bo=6 — 13=.8, откуда bo*=b1 — Ь2=2 — 8=9, с=Ь1 — b2-2 — 11=6. Далее для фиксированного v вычисляем dg по формуле (29}. Затем вычисляем v по формуле (32) и сравниваем с текущим. значением v ; в местах, где фиксированное и вычисленное значение совпадают, находятся корни уравнения (33): v =0: do= ф9}+9=1, у(6-1)+ ф-9)=8, 8 О; v =1: d1= ф10)+10=0, ф6)+у(-10)=8; 8 д 1 1 = 2: d2= p(11)+11=8, p(6-8)+ р(-11)=7; 7 2 v =3; бз= р(12)+12)=8, p(6-8)+ ф-.12)=5; 5 3 v =4: d4= (13)+13)=4, 1Р (6-4)+P(-13)=1; 1 4 v 5: бз= ф14)+14)=2, р(6-2)+ -14)=5, 5 5, у1=5, х1=8 — 5=3 v =6: бе= фО}1-О= оо, особый случай (см. ф-лу 26.1) 6=6, у2=6, хг=8-6=2 v =7; dye(1)+ 1)=5; ?(1 (6 — 5)+ ф-1)=7. 7=7, уз=7, хз=8-7=1. 5 Таким образом, корнями уравнения (33) являются числа 1, 2, 3. Действительно, подставляя в (33) значения 1, 2, и 3, последовательно получим: „ 3® 13, 14® 6 0 aеаоа оаб=О, . со оо а?oaoa oa =О. Условием трех ошибок является выполнение неравенства 15 а" о. rP I о e 0. Исправление ошибки заключается в замене принятого на 6-й позиции(6Я у, (}) ошибочного символа Kg = Ко+до на исправный. Обозначим: а! Е gÓ аСо . а1 Оу а аС1 Р 9 а = ac2 (34} Тогда из (9) получим КГ+с,+c,ду+i+ó (дх+ уд, х х +с д Ф Откуда I (кг (0 х
Аналогично I .K до " )-Су-о, д, C O ñ, д,-С,-С, I 35 . кх д..?-p-со-с, . д,.с,—.со-с, д,-с.-с,,(=(оЫ в VI3(4): aKg =а 9® ак или 40 кх ку Йр к? КО I с(" е с(Qic(г "g О+с(O+c(О+??(> х, К х-2j Кх+2 ?@ ("Г 45 д к?+2? .к 1 кг к1 . Умножим (35} íà а и сложим с (36), Получим: 50 Ку+Са К Х Дэ+? Дл (Ky Co Kg С< или ц" хщ ("х)р ((кГд,(кГ?- (ду ? (х Аналогично умножим (36) íà aI и сложим с (37), получим о@ Г х г х у х ?О,Гдх Гку ? о кг f cх 1797165 14 или, У сag le@g "Р е р Г 1(g Igg Умножим (38) нэ сР и сложим с (39) получим откуда, используя (34), получим или ,("P r@ Аналогично Исправленные по формулам (40 41, 42) символы заменяют испорченные символы на позициях, т и j cоoоoтTв еeтTtс:тTвBеeнHнHо©, определяемых и ри решении кубического уравнения (33). Устройство декодирования с исправлением ошибок работает следующим образом (на фиг. 10 представлена временная диаграмма работы устройства при m=4). Нэ вход 16 устройства поступают блоки информации по (15) информационных 4-разрядных символов и шесть проверочных символов, содержащих три неисправных символа. Первые 4 такта следует О-й цикл, в течение которого по сигналам ТИ заполняются первые 4 разряда блока задержки 1. Затем следует первый цикл (с 5 по 8 такты), в течение которого по сигналам bi (i=1...6) производится запись первого ин1 формационного символа Ко на регистр 20 формирователя 2 и на регистры 31 формирователей 3...7. Далее производится вычитание из содер>кимого регистра.22 (co) содержимого регистра 20 (Ко) на вычитателе 24; результат (>о ) поступает на преобразователь кода 25 и далее на сумматоре 23 формирователя 2 производится сложение символа Ко с нулем на выходе преобразователя кода 25 и запись результата на регистр 21 по сигналу Ь1 . Одновременно на суммагторах 35 формирователей 3...7 производится сложение содержимых регистров 31 с порядковыми номерами соответствующего формирователя проверочных символов (1...5) умноженными на "0" (I=O) поступающими из блока управления на контакты 40 формирователей 3„.7 с записью результата на регистры 32 по сигналам bi (I N l). Далее по сигналу Ь1 осуществляется перепись соз держимого регистра 21 на регистр 22 формирователя 2 и вычитание из содержимых 5 регистров 34 (оо 1формирователей 3...7 содержимого регистров 32 (Ко) на вычитателях 37; результаты (х> ) поступают на преобразователи 38 кода и затем на сумматорах 36 производится сложение "0" (выходы преоб10 разователей 38) с содержимым регистров 32 (K<) и запись результатов на регистры 33 по сигналам Ь! (i 1). Во втором цикле (с 9 по 12 такты) по сигналу bi производится запись на регистр 15 20 формирователя 2 второго символа К1, вычитание иэ содержимого регистра 22 (К>) содержимого регистра 20 (К1) с преобразованием разности (Ко-К1) нэ преобразователе 25, сложение полученного резуЛьтата 20 (p (Kp-К1) на сумматоре 23 с содер>кимым регистра 20(Ki) и запись результата К1 =К1+ р (Ko К1) на регистр 21 по сигналу 1 г b> . Одновременно К1 по сигналам Ь (I 1) записывается на регистры 31 формирователей 3...7 и на сумматорах 35 складывается с величиной Ig (сигналы Ь;"), поступающей нэ контакты 40 формирователей 3...7 с контактов 284, 289, 294, 299, 304 блока 12 управления; результаты записываются на 30 регистры 32 формирователей 3...„7 по сигналам bi (IA 1). Одновременно по сигнаг ° лам Ь| (I 1) производится перепись содер4 жимого регистров 33 на регистры 34. Далее на вычитателях 37 осуществляется вычитание из содержимого регистров 34 (K<) содержи мо го регистров 32 (К +19), преобразование результатов на преобразователях 38 и сложение с содержимым регистоов 32 на сумматорах 36 с ээпись1о суммы 40 К1 =К1+9+ р(Ко-Kl g) на регистры 33 по сигналам Ь (ill). Одновременно по сигналу b> осуществляется перепись содержимого регистра 21 нэ регистр 22 формирователя 2. Циклы с третьего по 15-ый аналогичны второму, при этом в 15-м цикле по сигналу Ь1 на регистр 20 формирователя 2 записы1 вается последний символ Кг — г, формируется первый проверочный символ Ко и помещается на регистр 21 формирователя 2 по сигналу b> . Одновременно по сигналам bi производится перепись предпоследних символов Кгп — 3 с регистров 33 на регистры 34 фаомирователей 3...7 и, затем, по сиг55 налам bi (i Ф 1) — запись на регистры 33 сформированных проверочных символов со второго по шестой (К1...К) и по сигналу b> — перепись символа Ко на регистр 22 3 формирователя 2. 1797165 20 30 50 B следующем 16-м цикле на регистр 20. формирователя 2 по сигналу Ь записыва1 ется первый принятый проверочный символ R производится формирование первого синдрома ошибки и по сигналу b> запись 2 результате (А,=Ко+ p(ko-Ко)) на регистр 21 формирователя 2. Одновременно, по сигналам Ь1 производится перепись провероч4 ных символов Kl(i Ф 1) с.регистров 33 на регистр 34 формирователей 3...7, В 17-м цикле на оегистр 31 формирователя 3 по сигналу b2 записывается второй принятый проверочный символ К, íà сумматоре 35 производится его сложение с "нулем (bl =О) с записью результата К> на регистр 32 по сигналу b и затем формиро? вание второго синдрому ошибки с записью результата Рц=К + р(К1-К1) на регистр 33 формирователя З.по сигналу Ьгз. Аналогично в циклах с 18 по 21 по сигналам bl (i=3, 4, 5, 6) на регистры 33 формирователей 4, 5, 6, 7 записываются сформированные на них с третьего по шестой синдромы ошибок Ь ... he соответственно. Сформированные таким образом синдромы ошибок поступают на входы 96...101 арифметического блока 8, с выходов 104, 109, 111, 105,.106, 102, 108, 107, 112, 103, 110 и 113, которых поступают на входы 140.„151 блока 9 вычисления коэффициентов соответственно, где сформированные коэффициенты Ьо, Ь и Ьг записываются на регистры 137, 138 и 139 соответственно по сигналу b> поступающему на вход 155 блока. С выходов регистров 137, 138 и 139 значения коэффициентов bO, Ь и b2 поступают на выходы 152, 153 и 154 блока соответственно и далее на входы 183, 184 и 185 блока 10 определения ошибочных позиций, где по формуле (32) вычисляется иь4 — номер очередной позиции и сравнивается с v 4, поступающей на входы 186 блока 10 с выходов 308 блока 12 управления. При равенстве ть4 и vc4 элемент сравнения 174 выдает импульсы на счетчик 179, Формула изобретения 1. Устройство для декодирования с исправлением ошибок. содержащее блок задержки, первый вход которого является информационным входом устройства, первые rn параллельных выходов подключены к соответствующим информационным входам первого, второго, третьего и четвертого формирователей проверочных символов, а соответствующий выход которого разрешает выдачу номера позиции неисправного символа с сумматора 160 через соответствующий вентиль 180, 181 или 182 на выходы 5 193, 192 или 191 блока соответственно и далее на входы 310, 311, 312 блока управления 12, и на разрешение записи исправленных в блоке 11 символов на регистры 175; 176 и 177 и на формирование символов со, с и с2, поступающих на выходы 194, 195 и 196 блока соответственно. Исправленные символы последовательно поступают на элемент ИЛИ 178 и далее с контакта 197— на первый вход элемента И14 устройства, откуда в сопровождении ТИ2 через элемент ИЛИ15 — на выход 19 устройства. С входов 310, 311 и 312 блска управления 12 номера (, v и J неисправных символов поступают на первые входы элементов сравнения 263, 264 и 265, на вторые входы которых с дешифратора 244 поступают номера четверок импульсов, При совпадении их с номерами позиций элементы сравнения разрешают выдачу ТИ2 через элементы И269, 270, 271, ИЛИ 272 на выход 305 блока для стробирования исправления символов, а при несравнении разрешают выдачу сигналов ТИ1 через элементы И266, 267, 268 и ИЛИ 273 на выход 306 блока (сигналы ТИ1). С выходов 306 блока управления сигналы ТИ1 поступают на вторые входы элемента И13 (фиг. 1), а с выходов 305 сигналы ТИ2 поступают на вторые входы элемента И14, Таким образом, применение пятого и шестого формирователей проверочных символов, арифметического блока, блока вычисления коэффициентов, блока определения ошибочных позиций, решающих совместно показательное уравнение третьей степени в 40 поле GF(2 ), позволяет определить ошибки в трех любых ошибочных символах и с помощью блоков управления, определения ошибочных позиций и блока исправления ошибок исправить их, что повышает надежность канала связи. последовательный выход подключен к первому входу первого элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого является выходом устройства, блок управления, тактовый вход и вход "Пуск" которого являются одновременными входами устройства, первый и второй выходы блока управления подключены соответственно к тактовому входу блока задержки и второму входу первого элемента И, блок исправления ошибок и блок вычисления ошибочных позиций, о т л и ч аю щ и и сятем,,что,,с целью повышения достоверности декодирования за счет исправления до трех пачек ошибок, в устройство введены блок вычисления коэффициентов, арифметический блок, второй элемент И и пятый, шестой формирователи проверочных символов, информационные входы которых подключены к первым m параллельным выходам блока задержки, выходы всех формирователей проверочных символов соединены с соответствующими первыми входами блока исправления ошибок и входами арифметического блока, выходы которого подключены к информационным входам блока вычисления коэффициентов, выходы которого подключены к первым информационным входам блока определения ошибочных позиций, первые параллельные выходы которого подключены к вторым входам блока исправления ошибок и информационным входам блока управления, вторые выходы блока определения ошибочных позиций соединены с третьими входами блока исправления ошибок, выходы которого подключены к вторым информационным входам блока определения ошибочных позиций, последовательный выход которого подключен к первому входу второго элемента И, третий выход блока управления соединен с вторым входом второго элемента И, выход которого подключен к второму входу элемента ИЛИ, выходы первой-шестой групп выходов блока управления подключены к соответствующим управляющим входам первого-шестого формирователей проверочных символов, четвертый, пятый и шестой выходы подключены соответственно к управляющему входу блока вычисления коэффициентов и первым и второму управляющим входам блока определения ошибочных позиций. 2. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что первый формирователь проверочных символов выполнен на буферных регистрах, вы читателе, сумматоре и преобразователе кода, информационные входы первого буферного регистра являются информационными входами формирователя, первые выходы первого буферного регистра подключены к входам вычитаемого вычитателя и к первым входам сумматора, выходы которого подключены к информационным входам второго буферного регистра, выходы которого подключены к входам третьего буферного регистра и являются выходами формирователя, выходы третьего буферного регистра подключены к входам уменьшаемого вычитателя, выходы котороro через преобразователь кода подключены к вторым входам сумматора. управляющий вход первого буферного регистра, первый управляющий вход второго буферного регистра и управляющий вход третьего буферного регистра являются соответственно первым, вторым и третьим управляющими входами формирователя, второй выход первого буферного регистра подключен к второму управляющему входу второго буферного регистра. 3, Устройство по и. 1, о т л и ч а ю щ е ес я тем, что каждый иэ второго-шестого формирователей проверочных символов выполнен на буферных регистрах, сумматорах, вычитателе и преобразователе кода. информационные входы первого буферного-регистра являются информационными. входами формирователя, выходы первого буферного регистра подключены к первым входам первого сумматора, выходы которого подключены к информационным входам второго буферного регистра, первые выходы которого подключены к входам вычитаемого вычитателя и к первым входам второго сумматора, выходы которого подключены к информационным входам третьего буферного регистра, выходы которого подключены к информационным входам четвертого буферного регистра и являются выходами формирователя, выходы четвертого буферного регистра подключены к входам уменьшаемого вычитателя, выходы которого через преобразователь кода подключены к вторым входам второго сумматора, управляющие входы первого и второго буферных регистров, первый управляющий вход третьего буферного регистра и управляющий вход четвертого буферного регистра являются соответственно первым, вторым, третьим и четвертым управляющими входами формирователя, вторые входы первого сумматора являются первыми управляющими входами формирователя, второй выход второго буферного регистра подключен к второму управляющему входу третьего Gyферного регистра. 4. Устройство пои. t, отл ич а ю ще ес я тем, что первый арифметический блок выполнен на вычитателях, сумматорах, умножителях на два и преобразователях кода, входы вычитаемого первого вычитателя являются первыми входами блока, входы уменьшаемого 1-го вычитателя (i=1,43 обьединены с входами вычитаемого (I+I)-го вычитателя и являются (1+1)-ми входами блока, входы уменьшаемого пятого вычитателя являются шестыми входами блока, выходы 1797165 20 первого вычитателя подключены к входам вычитаемого шестого, седьмого, восьмого и девятого вычитателей, выходы второго вы.читателя подключены к входам вычитаемого десятого, одиннадцатого вычитателей, к входам уменьшаемого шестого вычитателя и входам первого слагаемого первого, второго и третьего сумматоров и к входам первого умножителя на два, выходы третьего вычитателя подключены к входам уменьшаемого восьмого и одиннадцатого вычитателей, к входам вычитаемого тринадцатого и четырнадцатого вычитателей, к входам первого слагаемого четвертого, пятого, шестого и седьмого сумматоров. к входам второго слагаемого первого сумматора и к входам второго умножителя на два, выходы четвертого вычитателя подключены к входам уменьшаемого седьмого, десятого и тринадцатого вычитателей, к входам первого слагаемого восьмого и девятого сумматоров и к входам второго слагаемого четвертого сумматора, выходы пятого вычитателя подключены к входам уменьшаемого двенадцатого и четырнадцатого вычитателей, выходы десятого вычитателя подключены к входам уменьшаемого девятого вычитателя и к входам первого преобразователя кода, выходы шестого, седьмого, восьмого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого вычитателей подключены к входам второго, третьего, четвертого, пятого, шестого, седьмого и восьмого преобразователя кода, выходы второго преобразователя кода подключены к входам уменьшаемого пятнадцатого и шестнадцатого вычитателей и к входам вычитаемого семнадцатого и восемнадцатого вычитателей, выходы третьего преобразователя кода подключены к входам второго слагаемого пятого сумматора и первого слагаемого десятого сумматора, выходы четвертого преобразователя кода подключены к входам второго слагаемого второго сумматора и к входам вычитаемого девятнадцатого вычитателя, выходы первого преобразователя кода подключены к входам второго слагаемого третьего сумматора, к входам второго слагаемого седьмого сумматора и к входам вычитаемого двенадцатого вычитателя, выходы первого сумматора подключены к входам второго слагаемого десятого сумматора, выходы пя.того преобразователя кода подключены к входам первого слагаемого одиннадцатого сумматора, к входам вычитаемого двадцать первого, двадцать второго и двадцать третьего вычитателей и к входам уменьшаемого двадцать четвертого и двадцать пятого вычитателей, выходы четвертого сумматора соединены с входами первого слагаемого двенадцатого сумматора, выходы шестого преобразователя кода подключены к входам первого слагаемого тринадцатого сумматора и к входам вычитаемого двадцать шестого вычитателя, выходы седьмого преобразователя кода подключены к входам второго слагаемого двенадцатого и B0cbMQго сумматоров, выходы восьмого преобразователя кода подключены к входам второго слагаемого девятого сумматора, выходы девятого вычитателя подключены к входам девятого преобразователя кода, выходы которого подключены к входам второго слагаемого шестого сумматора, выходы первого умножителя на два подключены к входам второго слагаемого одиннадцатого сумматора, выходы которого подключены к входам вычитаемого пятнадцатого вычитателя, выходы пятого сумматора подключены к входам уменьшаемого девятнадцатого Bblчитателя, выходы второго сумматора подключены к входам вычитаемого шестнадцатого вычитателя и к входам уменьшаемого семнадцатого вычитателя, выходы третьего сумматора подключены к входам уменьшаемого двадцать первого вычитателя, выходы шестого сумматора подключены к входам вычитаемого двадцать четвертого вычитателя, выходы десятого сумматора подключены к входам уменьшаемого восемнадцатого вычитателя, выходы двенадцатого сумматора подключены к входам уменьшаемого двадцать второго вычитателя, выходы седьмого сумматора подключены к входам уменьшаемого двадцать третьего вычитателя, выходы восьмого сумматора подключены к входам уменьшаемого двадцатого сумматора, выходы девятого сумматора подключены к входам уменьшаемого двадцать шестого вычитателя, выходы второго умножителя на два подключены к вторым входам тринадцатого сумматора, выходы которого подключены к входам вычитаемого двадцать пятого вычитателя, выходы восемнадцатого, двадцать первого, двадцатого, шестнадцатого, двадцать второго, семнадцатого, двадцать третьего, девятнадцатого, двадцать пятого, двадцать четвертого, двадцать шестого и пятнадцатого вычитателей являются соответственно — двенадцатыми выходами блока, 5. Устройство и. 1, о т л и ч а ю щ е е с я тем, что блок вычисления коэффициентов выполнен на вычитателях, сумматорах, преобразователях кода и регистрах, входы уменьшаемого J-ro вычитателя )=1,6) являются соответственно (2j-1)-ми входами блока, входы вычитаемого j-ro вычитателя объединены с входами первого слагаемого 179 165 J-го сумматора и являются (2j)-ми входами блока, выходы /-го вычитателя через одноименный преобразователь кода соединены с входами второго слагаемого одноименного сумматора, выходы первого, третьего и пятого сумматоров подключены к входам уменьшаемого седьмого, восьмого и девятого вычитэтелей соответственно, выходы второго, четвертого шестого сумматоров подключены к входам вычитаемого седьмого, восьмого. девятого вычитателей соответственно, выходы седьмого вычитателя соединены с входами уменьшаемого десятого вычитателя, выходы которого подключены к информационным входам первого регистра, выходы восьмого вычитателя соединены с входами вычитаемого десятого вычитателя и входами умен ьшаемого одиннадцатого вычитателя, выходы которого подключены к информационным входам второго регистра, выходы девятого вычитателя соединены с входами вычитаемого одиннадцатого вычитателя и информационными входами третьего регистра, управляющие входы всех регистров объединены и являются управляющим входом блока, выходы первого-третьего регистров являются одноименными выходами блока. 6. Устройство по п. 1, о т л и ч а ю щ е ес я тем, что блок определения ошибочных позиций выполнен на вычитателях, сумматорах, преобразователях кода, элементе сравнения, счетчике, сдвиговых регистрах, вентильных элементах и элементе ИЛИ, входы вычитаемого первого вычитателя являются первой группой первых информационных входов блока, входы уменьшаемого первого и второго вычитателей объединены и являются второй группой первых информационных входов блока, входы вычитаемого второго вычи гателя являют,ся третьей группой первых информационных входов блока, информационные входы первого-третьего сдвиговых регистров являются вторыми информационными входами блока, выходы первого вычитателя подключены к входам вычитаемого третьего вычитателя, входы уменьшаемого которого обнулены, к первым входам первого сумматора и к входам первого преобразователя кода, входы которого подключены к вторым входам первого сумматора, выходы которого подключены к входам аычитаемого четвертого вычитателя, входы уменьшаемого которого подключены к выходам второго вычитателя, а выходы через второй преобразователь кода подключены к первым входам второго сумматора, вторые входы которого через третий преобразователь кода подключены к выходам третьего вычитателя, выходы второго сумматора подключены к информационным входам первого-третьего вентильных элементов и к первым входам элемента сравнения, вторые входы которого являются первыми управляющими входами блока, выход элемента сравнения соединен счетным входом счетчика, первый-третий выходы которого подключены к управляющим входам соответственно первого-третьего вентильных элементов и к входам разрешения считывания соответственно первого-третьего сдвиговых регистров, выходы которых подключены к входам элемента ИЛИ, выход которого является последовательным выходом блока, выходы первого вентильного элемента подключены к входам вычитаемого пятого и шестого вычитателей, входам первого слагаемого третьего и четвертого сумматоров и являются первой группой первых параллельных выходов блока, выходы второго вентильного элемента подключены к входам уменьшаемого пятого вычитателя, к входам вычитаемого седьмого вычитателя, входам первого слагаемого пятого сумматора и являются второй группой первых параллельных выходов блока, выходы третьего вычитателя элементов подключены к входам уменьшаемого шестого и седьмого вычитателей и являются третьей группой первых параллельных выходов блока, выходы пятого-седьмого вычитателей соответственно четвертый-шестой преобразователи кода соединены с входами второго слагаемого соответственно третьего-пятого сумматоров, выходы которых являются вторыми параллельными выходами блока, управляющих вход счетчика является вторым управляющим входом блока. 7. Устройство по и, 1, о т л и ч а ю щ е ес я тем, что блок исправления ошибок выполнен на первом-третьем узлах, каждый из которых содержит первый-восьмой сумматоры, перцый-третий вычитатели и первыйтретий преобразователи кода, выходы первого сумматора соединены с первыми входами шестого сумматора и входами вычитаемого первого вычитателя, выходы которого через первый преобразователь кода подключены к вторым входам шестого сумматора, выходы которого соединены с входами уменьшаемого второго вычитателя, выходы второго сумматора соединены с первыми входами четвертого сумматора, выходы которого подключены к первым входам седьмого сумматора и входам вычитаемого второго нычитателя, выходы которого через второй преобразователь кода подключены к вторым входам седьмого сумматора, выходы которого соединены с входами 23 1797165 дешифратора, первый, второй и третий выходы которого подключены к первым входам соответственно первого-шестого, седьмого-двенадцатого и тринадцатого-восемнадцатого элементов ИЛИ, выходы первой-третьей групп дешифратора соединены с вторыми входами соответственно первого-восемнадцатого элементов ИЛИ, выходы первого, седьмого и тринадцатого элементов ИЛИ являются первой группой выходов блока, выходы (6К+!)-го элемента ИЛИ (K=0, 1, 2; t=2,6) и (1-1)-е разряды выходов четвертой и пятой групп дешифратора являются t-ми группами выходов блока, соединены с вторыми входами соответственно первоготретьего элементов сравнения, выходы "Равно" которых подключены к вторым входам соответственно второго-четвертого элементов И, выходы которых соединены с входами девятнадцатого элемента ИЛИ, выход которого является вторым выходом блока, выходы "Не равно" первого-третьего элементовсравнения подключены к вторым входам соответственно пятого-седьмого. элементов И выходы которых соединены с входами двадцатого элемента ИЛИ, выход которого является третьим выходом блока; седьмой-девятый выходы дешифратора являются соответственно четвертым-шестым выходами блока. 3 4 5 13 14 13 1 а о 6. 1 4 7 8 8 4 0 13 2 9 12 2 1 9 7 3 1 6 о 6 1о 10 6 1О 1 2 6 12 11 4 О 12 О О 3 6 3 0 10 О 2 6 1 8 6 6 11 9 О 1 5 2 9 О 14 7 10 5 3 2 3 2 0 О 8 1г 12 0 10 11 11 7 1г 12 8 4 10 11 9 11 14 9 7 1г 4 11 8 0 8 14 10 О 14 12 7 6 8 О 3 3 9 11 .5 11 О 8 13 О 9 8 2 13 13 12 5 3 14 6 13 13 3 10 0 5 5 4 9, 13 14 2 7 4 8 5 13 14 0 г 1г 1 13 вычитаемого третьего вычитателя, выходы которого через третий преобразователь кода подключены к первым входам восьмого сумматора, выходы третьего сумматора соединены с первыми входами пятого сумматора, выходы которого подключены к входам уменьшаемого третьего вычитателя, входы уменьшаемого первого вычитателя и первые входы первого и второго сумматоров во всех узлах являются первыми входами блока, вторые входы второго и четвертого и объединенные входы второго пятого и восьмого сумматоров во всех узлах являются вторыми входами блока, вторые входы пер-, вого и первые и вторые входы третьего сумматоров во всех узлах являются третьими входами блока, выходы восьмого сумматора во всех узлах являются выходами блока. 8,Устройствопоп.1,отл ича ющеес я тем, что блок управления содержит счетчик, дешифратор, первый-седьмой элементы И, первый-двадцатый элементы ИЛИ, первый.-третий элементы сравнения, первые входы которых являются информационными входами блока, первый и второй входы первого элемента И являются тактовыми входом и входом *Пуск" блока, выход первого элемента И подключен к первым входам второго-седьмого элементов И, входу счетчика и является первым выходом блока, выходы счетчика сое инены с вхо ами О .1 4 6 8 11 1г 13 О 1 7 11 9 5 о 4 5 13 4 О 14 14 13 2 1 1 10 3 6 9 1т о 12 8 9 13 14 12 3 14 2Ь 179 7 f61 17971 б5 1797165 иб у УФl 49 170 1УГ 1797165 1797165 1797165 Редактор Заказ 656 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 ч Ъ 4) В г о М Ь» о C > Составитель A. Карпухин Техред М.Моргентал Корректор С. Патрушева
