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

 

Изобретение относится к вычислительной технике. Его Использоваьше в системах передачи и обработки цифровой информации обеспечивает повышение помехоустойчивости устройства за счет исправления стертых символов. Декодирующее устройство содержит запоминающий блок 1, буферный накопитель 2, блок 3 сумматоров, первый генератор 4 синдромов, первьй накопитель 9, дешифратор И ошибки, вычислители 4, 15, Введение второго генератора 5 синдромов, счетчиков 6-8, второго накопителя 10, дешифратора 12 состояний и вычислителей 16, 17 позволяет определять положение стертых символов и их исправление наряду с исправлением ошибок при работе в кодах Рида-Соломона. 5 ил. с 8 (Л

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

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

РЕСПУБЛИК (51) 4 Н 03 1 1 13/00

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

К АВТОРСКОМ,Ф СВИДЕТЕПЫ;"ГВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3837857/24-24 (22) 04.01 85 (46) 07.03,87. Бкл. У 9 (72) В. А. Зиновьев, В.. В, Зяблов, Б, А. Савельев, С. N. Додунеков, Б. N. Георгиева и Г. И. Житков (53) 62 1.. 394 (088. 8) (56) Патент США 11 4142174, кл. G Об Р 11/12, 1982.

Авторское свидетельство СССР

И 1216832 кл. Н 03 М 13/ОО, 07.О7.84. (54) ДекОДНРУюШее УстРОЙстВО для

ИСПРАВЛЕНИЯ ОШИБОК (57) Изобретение относится к вычислительной технике. Его использование в системах передачи и обработки циф" ровой информации обеспечивает повышение помехоустойчивости устройства за счет исправления стертых символов, Цекодирующее устройство содержит за" поминающий блок 1, буферный накопитель 2, блок 3 сумматоров, первый генератор 4 синдромов, первый накопитель 9, дешифратор 11 ошибки вычислители 14 15. Введение второго генератора 5 синдромов, счетчиков 6-8, второго накопителя 10, дешифратора

12 состояний и вычислителей 16, 17 позволяет определять положение стертых символов и их исправление наряду с исправлением ошибок при работе в кодах Рида-Соломона, 5 ил.

1 12955

Изобретение относится к вычислительной технике и может быть использовано в системах передачи и обработки цифровой информации, Дель изобретения — повышение помехоустойчивости устройства за счет исправления стертых символов, На фнг. 1 приведена блок-схема декодирующего устройства для исправления ошибок; на Фиг. 2-5 функ- 1О циональные схемы первого — четвертого вычислителей соответственно.

Декодирующее устройство пля исправления ошибок содержит запоминающий блок 1, буферный накопитель " 15 блок 3 сумматоров, первый 4 и второй

5 генераторы синдромов, первый 6, второй 7 и третий 8 счетчики, первый 9 и второй 10 накопители, дешиф" ратор 11 ошибки, дешифратор 12 состояний, коммутатор 13, первый 14, второй 15, третий 16 и четвертый 17 вычислители. Кроме того, на фиг,, 1 обозначены первые 18 и второй 19 выходы.

Дешифратор 11 ошибки представляет собой элемент ИЛИ с прямыМ и инверсным выходами, последний из которых является вторым выходом 19 устройства. ЗС

Коммутатор 13 представляет собой мультиплексор, коммутирующий одну из групп своих входов в соответствии с определенным адресным сигналом на входы двух групп элементов И, управляющие входы которых являются управляющими входами коммутатора 13.

Первый вычислитель 14, как и трети@ 16, и четвертый 17 вычислители, выполнен аналогично части второго щ вычислителя 15. Первый вычислитель

14.содержит (Фиг. 2} первый 20 и второй 21 блоки памяти„ формирователь 22 адреса, первый 23 и второй

24 коммутаторы, перемножитель 25, группу 26 триггеров и преобразователь 27 в обратный код, На Фиг. 2 обозначены информационные 28 и адресные 29 входы, первые 30, второй

31, и третий 32 выходы вычислителя, 0

Второй вычислитель 15 содержит (фиг. 3) триггер 33, элемент И 34, элемент ИЛИ 35, счетчик 36, первый

37, второй 38.и третий 39 формирователи адреса, первый 40, второй 41 третий 42 и четвертый 43 блоки па" мяти, первый 44, второй 45 и третий

46 коммутаторы, преобразователь 47 в обратный код, перемножитель 48, 31 2 группу 49 триггеров, группу 50 сумматоров по модулю два, первый 51, второй 52 и третий 53 элементы НЕ.

На Фиг. 3 обозначены первые 54, вторые 55 и третьи 56 информационные входы, первый 57, второй 58, третий

59 и четвертый 60 управляиицие входы, первые 61, вторые 62 и третий 63 выходы, Третий вычислитель 16 содержит (Фиг, 4) триггер 64, элемент И 65, счетчик 66, формирователь 67 адреса, перемножитель 68, группу 69 триггеров, первый 70 и второй 71 блоки памяти. На фиг. 4 обозначены первые 72 и вторые 73 информационные входы, первый 74 и второй 75 управляющие входы, первые 76 и вторые 77 выходы.

Четвертый вычислитель 17 содержит (фиг. 5) триггер 78, элемент И 79, счетчик 80, первый 81 и второй 82

Формирователи адреса, элемент НЕ 83„ первый 84 и второй 85 коммутаторы, перемножитель 861 группу 87 триггров, первый 88, второй 89 и трегий 90 блоки памяти, На фиг. 5 обозначены информационные входы 91, первый 92 и второй 93 управляющие входы, первые 94 и вторые 95 выходы. о

Формирователи 22, 37-39, 67 „81 и 82, преобразователи 27 и 47 в обратный код и блок 90 памяти вычислителей 14-17 могут быть выполнены на постоянных запоминающих устройствах (ПЗУ), На фиг. 3-5 показаны также тактовые входы 96 и входы 97 сброса вычислителей 15""17, Декодирующее устройство для исправления ошибок работает следующим образом.

В предлагаемом устройстве осуществляется декодирование блока информации, закодированного каскадным кодом, при котором кодирование осуществляется внешним и внутренним кодерами, В качестве внешнего используют кодер на основе кода Рида-Соломона, Этот кодер осуществляет копи«рование m-разрядных символов (комбинаAl ций), образующих поле Галуа GP (2 ), избыточным (и, k)-кодом, где k— число информационных символов; и— общей число символов в кодовом блоке, Внутренний кодер осуществляег кодирование m-разрядных символов (комбинаций) вторым избыточным кодом (m,, m), где tn — общее число разря3 1 2955 дов второго кода, Таким образом, общая длина блока информации, закодированногого к а ск адным кодером, р ав н à nm,, В данном устройстве внутренний код используется для обнаружения ошибок в символах и стирания их. В простейшем случае можно взять код с проверкой на четность, В этом случае второй генератор 5 синдромов осуществляет проверку на четность принимаемых, 10

m+1-разрядных комбинаций (один проверочный разряд), Если в комбинации нечетное число двоичных единиц, то на выходе генератора 5 появляется сигнал стирания, адрес (локатор) ко- 15 торого в данный момент фиксируется счетчиком 6, Число стираний, которое может исправить код Рида-Соломона, с d-2t-1. При исправлении двухкратных. ошибок с < d-5. 20

Закодированный избыточным (и, k) кодом блок информации списывается из блока 1 в буферный накопитель 2, а также подается в генераторы 4 и 5 синдромов, В первом генераторе 4 25 синдромов определяются синдромы $ о

S, $,1, путем деления кодового блока на составные части образующего полинома g(x)=(x+1)(x+d)(x+cc )... ... (x+ec)+, где Ф вЂ” примитивный эле- 30 мент поля GF(g), При этом на генератор 5 синдромов подаются m+1-разрядные комбинации, а на генератор 4 и буферный накопитель 2 m-разрядные комбинации (без проверочных разрядов). Синдромы S, -записываются в накопитель 9, На выходах накопителя 9 подключен дешифр атор 11 ошибок, который представляет собой схему ИЛИ, Если при делении получаются остатки, т,е. если $; 4 О, то они содержат хотя бы одну 1, Тогда на втором выходе дешифратора 11 появляется сигнал

"Ошибка", фиксирующий наличие ошибок, стираний или обеих вместе, Если $р= 45

=S< =...=$,1,, то на первом выходе появляется сигнал "Нет", обозначающий отсутствие ошибок и стираний, При появлении сигнала "Нет" информационная часть кодового блока выда- 50 ется потребителю через блок 3, Во время переписи кодового блока в буферный накопитель 2 производится также подсчет числа m-разрядных комбинаций первым счетчиком 6 и опреде- 55 ление синдромов ошибок в генераторе

5, Сигнал ошибки на выходе генератора 5 разрешает запись состояния счетчика 6 в накопитель 10. Это состоя31 4 ние и является адресом (локатором) стирания в (n k)-кодовом блоке, Так адресуются и другие комбинации, в которых обнаруживаются ошибки генератором 5 синдромов, Число сигналов ошибок (стираний) подсчитывается счетчиком 8, и если оно больше d-5, то сигналом "Стирание" с первого выхода стирается кодовый блок в буферном накопителе 2.

В противном случае сигналом с второго выхода счетчика 8 разрешается расчет элементарных симметрических функций локаторов стираний в вычислителе 17 и подсчет операций расчета вторым счетчиком 7. После приема и-й кодовой комбинации кодового блока появляется сигнал на втором выходе счетчика 6, который обеспечивает cosместно с сигналом с второго выхода счетчика 8 запуск второго счетчика 7.

На каждую операцию при вычислении тратится один такт, На первом такте состояние счетчика 7 выделяется дешифратором 12, сигнал с первого выхода которого попадает в вычислители

l5 и 17. В вычислитель 15 переписываются локаторы стираний, а вычислитель 17 ; по формулам с, =х,+х4+х +...+x> < +х „

Г

Х Х4 ХЗХ +åеа+Xd — 6 Хд 5У е ° в ° ° ° ° ° ° ° ° ° °

/ д 5 х х4хЯ 44х 6х 1 (1)

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

М, удовлетворяет дополнительному ус4 8 Yr3-1 ловию — элементы oC,с, М, c4 ...,,oC являются линейно независимыми над

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

1 — (2)

1=О

Представление элемента в виде разложения по нормальному базису удобно при возведении в степень ви/ ! < -х. +х +х, / (2 =Х» Х».+Х»х +Х4Х < 3=хьх4х 5 ° (13) 5 129 да 21 . Например, если элемент

= „о(.+ II,î{ + {12aL +...+ It m, o4 возвести в квадрат то получим =(оса) + (К У, У,{,)

+ О{ 2 + б 4 + < Е 8 + + {™ 2 . (3)

Я {m-<) тэк как юЕ =Ы. Таким образом, возведение в квадрат означает циклический сдвиг элемента на один разряд вправо. Это упрощает устройство возведения В квадрат и увели ивает его быстродействие., С выходов вычислителя 17 полученные значения (; подаются в вычиспитель 16 для определения модифициро-!

Ванных синдромов Б 1 Б 1 Б> z, Б(1ь. В этом блоке вычисление моди(Фициров»бинь»х синдромОВ HpОизвОдитcя

Но следующим формулам: !

Б» =БЯ »<Я,1, » +, °, +Б 5 <,{ з

Бб -! БС(-! +Бд-г .1 + ° «+ 4!g- y (»)

Б<»-г Б<»-а +8d-Э < + ° < б+Б» 1 g

Б<1 э Б»1- Б(1-4 < °, Бг б <»-

По модифицированным синдромам Б в вычислителе 14 .производится расчет ! симметрических функций G, „G от локаторов О»ш»бок х,, х, н локаторОВ стирании х < х,! < ° i e <»»Д < Сим метрические функции G, и С получают в Вычислителе 14 по уравнениям ! !

Б(1-2 Б<»-1 +8»» Б<» (5)

» б б

S>., Б „+(Б,)

С Ба-Л 8à Р»- ) (6)

G2 ! б г

Sd- 8d, +(Б )

Следовательно, для нахождения недостающих локаторов ошибок х, и хг нужно решить квадратное уравнение х +С,х+Сг=0. (7) (Указанное уравнение заменой Х=ЕС( приводится к вйду

Е +Е +) =О, (8) где II С /(G,)

E»=(0 g»,У Ьг<" ° .Ь g

+ ° ° ° +5 -). (9)

Е =(1<1+5< 1+ 1» + ге ° ° 1+7, +

+ +...+,„, ), (1О)

Вычисление лоКаторов х», хг ошибок производится в вычислителе 15 по выражениям (7) - (10).

На этом заканчивается определение локаторов ошибок х, и х . Локаторы

5531 6 стираний х, х4!. ° -, xdg определены раньше. Теперь остается определить значения локаторов у, ошибочных и стертых символов, Их определяют с.помощью слепчющего выражения:

Э-!

»t =a

3е 1-е

11

У ()

j -! - С1Е

10 е=о где 1 !й й.+ С, G = 1 °

»о

Вычисление G осуществляется по ре.»1 куррентной формуле

f5 G< = С ; -х Ср.!), (12) где G — элементарные симметрические функции от локаторов ошибок и стираний.

Значения у; определяют ся также В

Вычислителе 15 о формулам (11) и (12).

Локаторы х; ошибочных и стертых символов являются адресами искаженных символов кодового блока. Путем попачи этих адресов на буферный на-, копитель 2 производится считываниб» из него искаженных символов х;, которые подаются на блок 3 сумматоров„

ЗО

На вторые входы блока 3 из Вычислителя 15 подаются значения у; определенных локаторов. Сложение значений искаженных символов х; с соответствующими вычисленными значениями у. локаторов в блоке 3 обеспечивает !

35 их исправление, Исправленные символы снова записываются в буферный накопитель 2 по соответствующим адресам, После этого исправленный кодовый блок списывается через блок 3 сумматоров на выходе 18 потребителю информации.

На этом заканчивается процесс исправления ошибочных и стертых символов.

Рассмотрни работу блоков устройст45 ва для исправления по функциональным схемам (фиг. 2 — 5) при исправлении двух ошибочных и трех стертых символов.

При трех стертых символах формулы

5О (1) принимают вид

Рассмотрим работу вычислителя 17 при трех стертых символах (далее стираний и ошибок), Прн этом одновремен) 2955 но происходит запись локаторов стираний х, х и х . в вычислитель 15, На первом такте после приема кодового блока расстояние счетчика 7 выделяется дешифр атором 2, сигнал с первого выхода которого попадает в вычислители 15 и 17. В вычислителе 17 сигнал попадает на С-вход триггера 78, íà D-вход которого подан ранее сигнал со счетчика 8, Триггер 10

78 устанавливается B "1" и открывает элемент И 79, через который начинают поступать тактовые импульсы, Аналогично в вычислителе 15 сигналом с дешифратора )2 устанавливается в 15 1" триггер 339 сигнал с выхода которого разрешает прохождение тактовых импульсов через элемент И 34 ° В результате начинают работать счетчики 80 (фиг. 5) и 36 (фиг. 3), После- 20 довательные состояния счетчика 80 являются адресами для формирователей

8! и 82 и блока 90 памяти. Аналогично последовательные состояния счетчика 36 являются адресами для формирователя 37, по которым в них занесены адреса элементов поля Галуа GF (2 ), записываемых в блоки 42 и 43.

На первом такте на выходы блока

90 в накопитель 10 выдается сигнал считывания и адр ес локатора стир аний х, формирователь 82 подключает на первые входы перемножителя 86 через коммутатор 84 выход элемента

НЕ 83, а через коммутатор 85 на вторые входы перемножителя 86 сигнал с выходов накопителя 10. В вычислителе 15 аналогично формирователь 39 подключает выход элемента НЕ 51 через коммутатор 44 на первые входы пере- 40 множителя 48, а выходы накопителя 10 через коммутатор 45 — на вторые входы пер емножителя 48, Таким образом, на входы обоих пеРемножителей подключаются Ж =1 и х . 45

О

Произведение М х =х э записывается на триггеры группы 87 и группы 49 и в блок 88. На втором такте локатор.стираний х переписывается с группы 49 триггеров в блоки 42 и 43. 50

На третьем такте аналогично из накопителя 10 выбирается х4 и умножается на м . Результат, т,е. х4, записывается в блок 88, складывается с содержанием (х ) группы 87 триггеров и записывается на триггеры груп- пы 49, На четвертом такте переписывается локатор стираний х4 в блони

42и 43, 3) 8

Таким же образом, ца пятом такте осушествляется выборка х и умножение ь . Результат, т. е, х, складывается с х„+x4 на триггерах группы 87 и записывается на групцу 49 триг геров.

На шестом такте величина с, с триггеров группы 87 записывается в блок 89, а локатор х переписывается с группы 49 в блоки 42 и 43, На этом заканчивается запись локаторов стираний в вычислитель 15.

С седьмого такта начинается вычисление < . При этом формирователь

82 подключает через коммутатор 84 на первые входы перемножителя 86 вы- . ходы блока 88, Выходы накопителя 10 остаются подключенными на вторые входы перемножителя 86. Из накопителя

10 выбирается величин - x а из бло3 9 ка 88 — локатор стир аний х4, Произведение х х4 записывается на триггеры группы 87. На восьмом такте х х записывается блок 89, На девятом такте х> из накопителя )д и х, из блока 88 перемножаются на перемножителе 86 и произведение х х складывается с х х на триггерах группы 87.

Произведение х4х получают на десятом такте и складывают на тех же триггерах с х4х4+х,х, 1

Полученная величина о записывается на одиннадцатом такте в блок 8".

Для расчета с используют произведение х х„, записанное в блоке 89, выходы которого подключены на вторые входы перемнолжтеля 86, На первые входы перемножителя 86 из блока 88 подается локатор х 9 . На двенадцатом тахтЕ ВЕЛИЧИНа о =Х Х4Х ЗаПИСЫВается на триггеры группы 87, с которых на 13-м такте переписывается в блок 89 .

Для дальнешпих расчетов неЬбходи,о мо записать о =! в блок 89. Это производится на 14-м такте путем подключения через коммутаторы 84 и 85 на входы перемножителя 86 выхода элемента НЕ 83. Таким образом, в перемножителе 86 производится перемножение о o,о

Ы. о = ж и результат вначале записывается на триггеры группы 87, а на

15-м такте — в блок 89, На 16-м такте появляется сигнал на третьем выходе дешифратора 12, который подается в вычислитель 16 с входа 74 на С-вход триггера 64

10 ! $4$5+Бь Sc»

$ S,+($4)

$ $5 (4) 129 553! (1 5 (lб) 9 (фиг. 4). До этого с дешифратора 11 с входа 75 на D-вход триггера 64 подан сигнал "Ошибка", поэтому тригсс сс гер 64 устанавливается в "l и разрешается работа вычислителя 16, При этом через элемент И 65 на счетчик

66 начинают поступать тактовые импульсы Т, Состояния счетчика 66 с выходов 77 попадают на адресные входы коммутатора 13. Число цепей А; в выходах 77 определяется количеством вычисляемых синдромов S Вычисление осуществляется по формулам (4), которые при исправлении двух ошибок и трех стираний принимают вид:

$ Б +$%С! +$462 +$ с,з

S =S +S4 +S p с2 +$2i.9, S Б !,с ++S, с, ++S !,9

На 16-м такте счетчик 66 переходит в первое состояние.- В данном случае в вычислении участвуют семь синдромов, поэтому на адресные входы коммутатора 13 со счетчика 66 подхо-. дят три цепи, которые Обеспечивают получение восьми адресов. сВ первом состоянии счетчика 66 коммутатор 13 подключает синдром S<, который попадает через открытый сигналом "Ошиб" ка" блок элементов И коммутатора 13 на вторые входы 73 перемножителя 68, В это время на первые входы 72 перемножителя 68 из блока 89 списывается 0LÎ

На выходах перемножителя 68 поо лучают произведение с . Б =$, которое записывается на триггеры группы

69. Аналогично получают произведение

S С,, которое складывается с $< на триггерах группы 69. Произведения

S :, Бэ 9 также складываются на

4 2 1 9 тех же триггерах. Полученная сумма

S на 20-м такте переписывается па6 раллельно в блоки 70 и 71, Аналогично получают в соответствии с формулами (12) и записывают в блоки 70 и 71 модифицированные с синдромы $ ) $4 Бэ на чтО тра тится 15 тактов. Таким образом, работа вычислителя 16 заканчивается на 35-м такте. !

Расчет симметрических функций С, и С от локаторов ошибок и стираI

2. ний производят в вычислителе 14, Вычисление производят по выражениям (5) и (6), которые при исправлении двух ошибок и трех стираний прини.,мают вид:

Вычисление начинается с 36-го такта, на котором формирователь 22

10 адреса открывает коммутаторы 23 и

24 по их первым входам, Поэтому на первые и вторые входы перемножителя

25 подключаются соответственно выхо-! . ды блоков 70 и 71. Величины $4 и $

f5 подаются на входы перемножителя 25! с

Произведение S S > записывается в триггеры группы 26, Аналогично на !

37 такте получают произведение $,$, ! которое складывается с S4$ на трнг20 герах группы 26. Результат сложения записывается в блок 20 на 38-м такте.

Аналогично на 39-м такте вычисляют знаменатель выражения (15), т, е, $g S +(S4 ) =а КОторый на 41-м тBKTe

25 записывается в блок 21. На 42-м такте числитель выражения (15) умножа- ют на величину

1 l

Г Гс 2 °

S,, S, ($, )

О

Величину 1/а получают в преобразователе 27, в котором по адресу

Б Б +($ ) записана величина l/а. Таким Образом, здесь операция деления

35 заменяется операцией умножения, Для умножения выход блока 30 подключается через коммутатор 23 на первые входы перемножителя 25, а выходы преобразователя 27 - íà его вторые вхо40 ды, Полученная величина С, записывается в триггеры группы 26, а на 43-и такте сигналом 3 (" Запись 2") с выхода 31 переписывается в вычислитель 15 на блок 40 (фиг. 3).

45 АналогичнО вычисляют С2 по ð ! муле (16) на 44 — 48-м тактах. Поскольку знаменатели в формулах (15) и (16) одинаковы, вторично знаменатель не вычисляют, а используют его

5g значение, записанное в блоке 21, На

49-м такте величина С с помощью сигнала З,с (" Запись" ) с выхода 32 переписывается на блок 41, Недостающие локаторы ошибок х, и у х, определяются по формулам (7) (l0) в вычислителе 15, где также вычисляются значения ошибок и стираний по формулам (11) и (12), Работу вычислителя 15 рассмотоим при двух

1! 12 ошибках и трех стираниях, В этом случае на 50-м такте на втором выходе дешифратор а 2 появляется сигнал, который проходит через элемент ИЛИ 35 вычислителя 15 (фиг, 3) и устанавливает в "1" триггер 33, который открывает элемент И 34, На счетчик 36 начинают поступать тактовые импульсы с входа 96, Счетчик 36 уже работал при записи локаторов стираний х, х4 и х в блоки 42 и 43 и остался в шестом состоянии, т.е ° в состоянии, при котором осуществляется запись локатора х в блоки 42 и 43. Поэтому счетчик 36 при вторичном переходе триггера 33 в

"1" и поступлении тактовых импульсов сначала переходит в седьмое состояние, для дальнейших вычислений нужно переписать в блок 43, Поэтому в седьмом состоянии счетчика 36 формирователь 39 сигналом с первых выходов через коммутатор 44 подключает на входы перемножителя 48 значео ние oL, а сигналом со вторых выходов через коммутатор 45 соединяет выходы блока 40 на вторые входы перемножителя 48. Таким образом, на 50-м такте на выходах перемножителя 48 о получают величину С, = С,, которая . записывается в триггеры группы 49, I

На 51 такте G, сигналом с формирователя 37 переписывается в блок 43.

На 52-м такте на первом выходе формирователя 38 появляется сигнал, который сдвигает на один разряд вправо содержимое блока 40, в качестве которого при m=8 может быть применен универсальный регистр, в котором предусмотрено считывание и запись информации в параллельном и последовательных кодах, а также циклический сдвиг данных влево и вправо, т.е.. в направлении первого или восьмого разрядов, Для сдвига m-й (последний) разряд регистра соединяется с входом первого разряда. При

I сдвиге вправо величина G<, записанная в блоке 40, возводится в квадрат г (G< ), На 53-м такте формирователь

39 подключает через коммутатор 44 на первые входы перемножителя 48 выходы блока 41, а выходы блока 40 через коммутатор 46 и преобразователь 47— на вторые входы перемножителя 48.

Значение (С,), записанное в блоке г

40, является адресом для ПЗУ преобразователя 47, в результате пода95531

12 чи которого на выходах последнего появляется записанная в нем по этому адресу величина 1/(G, ) . Следовательно, на первых входах неремножителя 48

I появляется величина G а на вторых—

1/(G, ), На этом же такте происходит

I г перемножение Сг на 1/ (G, ) - и на выходах перемнажителя 48 получают величину, которая записывается в !

О триггеры группы 49. На 54-м такте на блок 42 подается сигнал записи и выдается адрес, по которому величина записывается в блок 42.

На 55-м такте формирователь 37 вы-!

5 бирает из блока 42 величину, в результате преобразования которой на. входах элементов НЕ 52 и 53 и прямых выходах сумматоров группы 50 получается величина Z которая подключа20 ется с помощью формирователя 39 через коммутатор 44 на первые входы перемножителя 48. Одновременно формирователь 39 через коммутатор 45 подключает выходы блока 43 на вторые входы перемножителя 48, Из блока 43. сигналом с формирователя 37 выбирается ве1 личина G . Следовательно, на выходах пер емножителя 48 получен локатор оши1 бок х, =Z,Ct, который записывается на триггеры группы 49, На 56 такте локатор х, с помощью формирователя 37 переписывается в блоки 42 и 43.

На 57-м такте формирователь 37 снова выбирает иэ блока 42 величину

35 I% в результате преобразования ко.торой в соответствии с формулой (10) на выходах элементов НЕ 52 и 53 и сумматоров группы 50 получается величина Z которая подключается фор40 мирователем 39 через коммутатор 44 на первые входы перемножителя 48, Одновременно формирователь 39 через коммутатор 45 подключает выходы блока 43 на вторые входы перемножителя

45 48. Таким образом, на выходах перемножителя 48 получен локатор ошибок ! х =Z G который записывается на группу 49 триггеров, На 58-м такте величина х с помощью формирователя.

3? переписывается в блоки 42 и 43.

На этом заканчивается определение локаторов ошибок ° Следовательно, в блоках 42 и 43 записаны локаторы ошибок х и xä и локаторы стираний х, х

55 и х

По локаторам х, и синдромам S,, используя формулы (11) и (! 2), можно найти значения ошибок и стираний у; .

13 1295531 14

Процедуру нахожде ния значений у; опишем при возникновении двух ошибок и трех стираний. В этом случае выражения (11) и (12) лри вычислении принимают вид:

С<0$4 +С< $ +С<2$2 +С1Я < +G<<$ О

4 Ъ 2

G х +С х<+G х<+G х<+С<1х (17) С, =Си +х,, +Х< С<<1

С < +x < G

Сд=С,, +х,С<, (18) С, =х, +х +х +к 4+к <

С х< xg+x

Сз -х<х х +х< х х4+ °, ° +х х4х

С =К< x x xq+x< х х х + ° в х1х х4х е (19)

Вначале определяют G,, С, G

С4 по формулам (19). При этом локаторы х, — х записаны в блоках 42 и 43. Вычисление G< происходит с

59-го такта так: формирователь 39 подключает с помощью коммутатора 44 выходы блока 42 на первые входы перемножителя 48. Формирователь 37 задает адрес, по которому в блок 42 записан локатор ошибок х<, в результате с выхода блока 42 величина х, подается на первые входы перемножителя 48, Формирователь 39 подключает выход элемента НЕ 51 через коммутатор 45 на вторые входы перемножителя 48, в результате на него подается сС = 1. Результат умножения oL x о записывается в триггеры группы 49.

Аналогично происходит выбор из блока 42 и умножение íà oL локатора xz.

Результат складывается по модулю два с х на триггерах группы 49. На следующем, 61-м такте необходимо выбрать из блока 42 локатор стираний х> и сложить его с х, +х . Адрес для выбора х> из блока 42 задает формирователь 37. При этом выходы блока 42 через коммутатор 44 подключаются на первые входы перемножителя 48, на вторые входы снова подключается М." . Таким образом, происходит умножение х насС и сложение результата с х +х на триггерах группы 49. Аналогично производится сложение Х4 и х, Результат сложения, т.е. G записывается в блок 42 на

64-м такте.

Также производится вычисление G

С и G которые записываются в блок 42.

t5

Расчет Gö«, С<, С,> и С< производится по формулам (18) с лоомощью формирователей 37 и 39, а также коммутаторов 44 и 45. Результаты расчетов записываются с триггеров группы 49 в блок 42.

После этого приступают к определению у,, при этом вначале определяют числитель, а затем знаменатель выражения (17). Для нахождения числителя синдромы $о, S ° °,,S, рез коммутатор 13 считываются сигналами со счетчика 66 вычислителя 16, которые задают адреса для мультиплексора в коммутаторе 13, подключающего S, $() . $,1 < на входы перемножителя 68 по сигналу с выхода триггера 33 (выход 63). Значение числителя записывается в блок 42, а зн ачени е з наме нат еля о с т ает ся н а триггерах группы 49. Теперь числитель необходимо разделить на знаменатель. Значение числителя из блока

32 через коммутатор 44 подается на первые входы перемножителя 48, а значение знаменателя через коммутатор 46, преобразователь 47 и коммутатор 45 — на вторые входы перемножителя 48, Если значение знаменателя обозначить через а, то на выходе преобразователя 47 получают величину 1/д, которая и умножается на числитель. В результате на выходах перемножителя 48 получают значение у,, Величина у записывается в триггеры группы 49, а затем в блок 43.

Остальные значения у; получают и записывают в блок 42 аналогично, Таким образом, локаторы х; записаны в блоке 42, а значения ошибок и стираний у, записаны в блоке 43.

Далее величина х, являющаяся ад" ресом искаженного элемента, с помощью формирователя 37 списывается с блока 42 и подается на буферный накопитель 2, В результате разряды искаженного элемента с адресом х, подаются на блок 3 сумматоров, на вторс.е входы которых формирователь 37 списывает из блока 43 у<, При сложении разрядов искаженного элемента с у, происходит исправление и исправленный элемент записывается в буферный накопитель 2 по тому же адресу.

Аналогично происходит исправление остальных искаженных элементов кодово го блока.

Таким образом, предлагаемое устройство позволяет исправлять до двух

Декодирующее устройство для исправления ошибок, содержащее запоминающий блок, первые выходы которого подключены к со ответ ствующим входам 10 первого генератора синдромов и первым информационным. входам буферного накопителя, выходы которого соединены с соответствующими первыми входами блока сумматоров, выходы которого 15 подключены к соответствующим вторым информационным входам буферного накопителя и являются первыми выходами устройства, выходы первого генератора синдромов соединены с соответст- 20 вующими входами первого накопителя, выходы которого подключены к соответствуюд1им входам дешифратора ошиб. ки, первый выход которого соединен с первым управляющим входом буферного накопителя и является вторым выходом устройства, первый вычислитель, первые, второй и третий. выходы которого подключены соответственно к первым информационным, первому и второму управляюшкм входам второго вычислителя, первые и вторые выходы которого соединены соответственно с третьими информационными входами буферного накопителя и вторыми 35 входами блока сумматоров, о т л и— ч а ю щ е е с я тем, что, с целью повышения помехоустойчивости устройства за счет исправления стертых символов, в устройство введены первый, 4 второй и третий счетчики, второй генератор синдрома, второй накопитель, третий и четвертый вычислители, дешифратор состояний и коммутатор, первые и вторые выходы запоминающего блока подключены к входам соответственно первого счетчика и второго генератора синдромов, выход которо1

15 12955 ошибок и до d-5 стираний, т,е, обеспечивает существенное повышение достоверности исправленной информации

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

31 16 го соединен с первым управляющим входом второго накопителя и входом третьеro счетчика, первый и второй выходы которого подключены соответственно к второму управляющему входу буферного накопителя и первому управляющему входу четвертого вычислителя и управляющему входу второго счетчика, первый и второй выходы первого счетчика соединены с информационными входами соответственно второго накопителя и второго счетчика, выходы которых подключены к входам дешифратора состояний, первый выход которого соединен с вторым управляющим входом четвертого вычислителя и третьим управляющим входом второго вычислителя, второй и третий выходы дешифратора состояний соединены соответственно с четвертым управляющим входом второго вычислителя и первым управляющим входом третьего вычислителя, первые выходы которого подклю-. чены к информационным входам первого вычислителя, выходы первого накопителя .подключены к соответствующим информационным входам коммутатора, первые и вторые выходы которого соединены соответственно с первыми информационными Входамн третьего вычислителя и вторыми информационными входами второго вычислителя, третий выход которого соединен с первым управляющим входом коммутатора, второй выход дешифратора ошибок соединен с управляющими входами коммутатора и третьего вычислителя, вторые выходы которого подключены к адресным входам коммутатора и первого вычислитея, первые и вторые выходы четвертого вычислителя подключены соответственно к вторым информационным входам третьего вычислителя и адресным входам второго накопителя, выходы которого подключены к информационным входам четвертого и третьим информационным входам .второго вычислителей.

12955 31

1295531

Составитель О, Ревинский

Редактор Н, Тупица Техред Л. Сердюкова Корректор Т. Колб

Заказ 628/62 Тираж 90? Подписное

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

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

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