Декодирующее устройство для исправления ошибок Советский патент 1987 года по МПК H03M13/05 

1

H3o6peTeraie относится к вычислительной технике и может быть использовано в системах передачи и обработ ки цифровой информации.

Цель изобретения - повышение помехоустойчивости устройства за счет испраЕления стертых символов.

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

Декодирующее устройство для исправления ошибок содержит запомт аю- щий блок 1, буферный накопитель 2, блок 3 сумматоров, первый 4 и второй 5 генераторы синдромов, первый 6, второй 7 и третий 8 счетчики, первый 9 и второй iO накопителиJ дешифратор II ошибки, дешифратор 12 состояний коммутатор 13, первый 14, второй 15, третий 16 и четвертый 17 вычислители. Кроме того на фиг, I обозначены первые 18 и второй 19 выХОДЬ.

Дешифратор I1 опшбки представляет

собой элемент ИЛИ с npямы и инверсным выходами, последний из которых

является вторым выходом 19 устройства.

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

Первый вычислитель 14, как и тре- ти|( 16, и четвертый 1-7 вычислители, выполнен аналогично части второго вычислителя 15, Первый вычислитель 14.содержит (фиг. 2) первый 20. и в 1 орой 21 блоки памяти,, формирователь 22 адреса, первый 23 и второй 24 коммутаторы, перемкожитель 25, группу 26 триггеров и преобразователь 27 в обратный код, На фиг, 2 обозначены информационные 28 и адресные 29 входы, первые 30, второй ЗК и третий 32 выхода вычиатителя.

Второй вычислитель 15 содержит (фиг. 3) триггер 33, элемент И 34, элемент ИЛИ 35, счетчик 36, первый 37, второй 38 .и третий 39 формирователи адреса, первый 40, второй 41 третий 42 и четвертый 43 блоки памяти, 44, второй 45 и третий 46 коммутаторы, преобразователь 47 .в обратный код, перемножитепь 48,

955312

группу 49 триггеров, группу 50 сумматоров по модулю два, первый 51, второй 52 и третий 53 элементы НЕ. На фиг. 3 обозначены первые 54, вто;; рые 55 и третьи 56 информационные входы, первый 57, второй 58, третий 59 и четвер7Ъ1й 60 управлшощие входы, первые 61, вторые 62 и третий 63 выходы .

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

20 (фиг. 5) триггер 78, элемент И 79, счетчик ВО, первый 81 и второй 82 формирователи адреса, элемент НЕ 83 первый 84 и второй 85 коммутаторы перемножитель 86, группу 87 тригге ров, первый 88, второй 89 и третий 90 блоки памяти. На фиг. 5 обозначены информационные входы 91, первый 92 и второй 93 управляющие входы, первые 94 и вторые 95 выходы.

ЗС

Формирователи 22, 37-39, 67, 81

и 82, преобразователи 27 и 47 в обратный код к блок 90 памяти вычислителей 14-17 могут быть выполнены ка

5 постояшилх запоминающих устройствах (ПЗУ),

На фиг. 3-5 показаны также тактовые входы 96 и входы 97 сброса вычислителей 15-17.

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

В предлагаемом устройстве осуществляется декодирование блока инфор45 мации, закодированного каскадным кодом, при котором ко,ссирование ос5,тце- ствляется внешним и внутренним ко- дерлми. В качестве внешнего используют кодер на основе кода Рида-Солог-io50 на. Этот кодер осуществляет кодирование ш-разрядных символов (комбинаций) , образукмщх поле Галуа GF (2) , избыточным (п, k)-кoдoм, где k - число информационных символов; п ,55 общей число символов в кодовом блоке. Внутре1ший кодер осуществляет кодирование т-разрядных символов (комбинаций) вторым избыточным кодом (т,, т), где т, - общее число разрядов второго кода. Таким образом, общая длина блока информации, закодированного каскадным кодером, равна пга

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

Закодированный избыточным (п, k)- кодом блок информации списывается из блока 1 в буферный накопитель 2, а та1сже подается в генераторы 4 и 5 синдромов. В первом генераторе 4 синдромов определяются синдромы S, S,,..., Sj, путем деления кодового блока на составные части образующего полинома g(x) (x+l) (x+d) (x+oi) . ., .. . (x+ci) , где ot - примитивный эле мент поля GF(g), При этом на генератор 5 синдромов подаются т+1-разрядные комбинации, а на генератор 4 и буферный накопитель 2 т-разрядные комбинации (без проверочных разря- дов). Синдромы S записываются в накопитель 9. На выходах накопителя 9 подключен дешифратор И ошибок, который представляет собой схему ИЖ, Если при делении получаются остатки, т.е. если S;/ О, то они содержат хотя бы одну I. Тогда на втором выходе дешифратора 1 появляется сигнал Ошибка, фиксирующий наличие ошибок стираний -ИЛИ обеих вместе. Если 8 3,...Sj, , то на первом выходе появляется сигнал Нет, обозначающий отсутствие ошибок и стираний. При появлении сигнала Нет информационная часть кодового блока выда- ется потребителю через блок 3,

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

Число сигналов ошибок (стираний) подсчитывается счетчиком 8, и если оно больше d-5, то сигналом Стирание с первого выхода стирается кодовый блок в буферном накопителе 2, В противном случае сигналом с второго выхода счетчика 8 разрешается расчет элементарных симметричесрмх функций локаторов стираний в вычислителе 17 и подсчет операций расчета вторым счетчиком 7, После приема п-й кодовой кoмбинaцm кодового блока появляется сигнал на втором выходе счетчика 6, который обеспечивает совместно с сигналом с второго выхода счетчика 8 запуск второго счетчика 7 На каждую операцию при вычислении тратится один такт. На первом такте состояние счетчика 7 выделяется дешифратором 12, сигнал с первого выхода которого попадает в вычислители 15 и 17. В вычислитель 15 переписываются локаторы стираний, а вычислитель 17 начинает расчет по формулам г, х,+Х4+Х5+. . .+XJ.S

Ог Х.. ,,. . Xj.5, d-5 J 4 5 -- d-6Xd-S о

При этом процесс расчета и преобразований принятых символов (кодовых комбинаций), каждый из которых содер- 5КИТ m бит в поле Галуа GF (2), осуществляется в нормальном базисе. Все символы поля GF (2) можно представить в виде степени примитивного элемента I/ . Если примитивный элемент oi удовлетворяет дополнительному условию - элементы oi ,oi , oi, о;,... , являются линейно независимыми- над GF (2), то они образуют нормальный- базис, В таблицах неприводимых многочленов можно выбрать примитивный многочлен соответствующей степени, корни которого ci , где ,1,2,,, ,т-1, линейно независимы. Тогда произвольный элемент Jf GF (2 ) может быть представлен как некоторая степень и в виде разложения по нормальному базису„,.,.

Г Гу;...«(У

(2)

Представление элемента у в виде разложения по нормальному базису удобно при возведеш га в степень ви5 1295531 6

да 2, Например, если элемент у стираний х,, к,, ,, ,4i. опрер(елепы

Удйб+у,Ы +... +JCm-iC вознес-раньше. Теперь остается определить

ти в квадрат, то получим J (06) + (ir, f (у.Ь -ь...) .,,„,,

Jm.,i гГоог +гГ....П п-.о

.(3)

так какй oi. Таким образом, воззначения локаторов У; опшбочных и стертых символов. Их определяют с п мощью следующего выражения: Э-1

HG

je

(11)

ведение в квадрат означает циклический сдвиг элемента на один разряд вправо. Это упрощает устройство воз ведения в квадрат и увеличивает его

быстродействие.,

С выходов вычислителя 17 полученные значения €; подаются в вычислитель 16 для определения модифициро- ванных синдоомов S, , S,., , -2 Si,. В этом блоке вычисление модифицированных синдромов производится по следуюпщм формулам:

Sj ., €, +.,+S;t,,

S., S., , +... + 5, &.5, (4)

Sa-2 .j t-, +., , oj.5 ,

Sj.3 Sj.j Sj.4 -г-, +., . . Ho модифицированным синдромам Sj; в вычислителе 14 .производится расчет симметрических функций G,, Gj от локаторов ошибок Xj, к и локаторов стираний X,, x,...,Xj.p. Сим

метрические функции Gj и G получают в вычислителе 14 по уравнениям

.§k

sj.,s., (s;,..,)

§i- §i ii§ku)l- . .3 Srf., -(Sd-. f

(5)

(6)

Следовательно, для нахождения недо- станзщих локаторов ошибок х, и к нужно решить квадратное уравнение

,.(7)

Ука: анное уравнение заменой приводится к виду

z +z . (8)

где (G;) %

2,(0,у,,у,+Уг.....Г, Um-1)

Z2.(l,n-y., i+|fi +й 2

+ +... у П)-| .) 1

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

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

(9)

- (10) ошибок

значения локаторов У; опшбочных и стертых символов. Их определяют с помощью следующего выражения: Э-1

Я

yj

HG

je

- . g ZlGjex

1 й 6 t + С, 1.

Вычисление Gi- осуще куррентнбй формуле

G; где G

j )

(12)

- элементарные симметрические функции от локаторов ошибок и стираний. Значения у; определяются также в вычислителе 15 по формулам (11) и (12).

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

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

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

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

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

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

5

t, + Х Х,

г

г

г

Х,,-+ХяХ

5

(13)

Рассмотрим работу вычислителя 17 при трех стертых символах (далее стираний и ошибок). При этом одновремен7 1

но происходит запись локаторов стираний x,j, х и х. в вычислитель 15,

Н.а первом такте после приема кодового блока расстояние счетчика 7 выделяется дешифратором 12, сигнал

с первого выхода которого попадает в вычислители 15 и 17. В вычислителе 17 сигнал попадает на С-вход триггера 78, на D-вход которого пода ранее сигнал со счетчика 8. Триггер 78 устанавливается и открп1ва- ет элемент И 79, через которьш начинают поступать тактовые импульсы. Аналогично в вычислителе 15 сигналом с дешифратора 12 устанавлив.ается в 1 триггер 33; сигнал с выхода которого разрешает прохождение тактовых импульсов через элемент И 34, В результате начинают работать счетчики 80 (фиг, 5) и 36 (фиг. 3). После- довательные состояния счетчика 80 являются адресами для формирователей 8 и 82 и бпока 90 памяти. Аналогично последовательные состояния счетчика 36 являются адресами для формиро- вателя 37, по которым н них занесены адреса элементов поля Гапуа GF (2), записываемых в блоки 42 и 43.

На первом такте на выходы блока 90 в накопитель 10 выдается сигнал считывания и адрес- локатора стираний X,. ФopмIipoвaтeль 82 подгатючает

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

Таким образом, на входы обоих перемножителей подключаются 06° 1 и х. Произведение Ы записывается на триггеры группы 87 и группы 49 и в блок 88, На втором такте локатор стираний Xj переписывается с группы 49 триггеров в блоки 42 и 43,

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

Таким же образом, на пятом такте осупшствляется выборка х и умножение 00° . Результат, т.е. х,;, складывается с х,,+Х4 на триггерах группы 87 и записывается на группу 49 триггеров,

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

С седьмого такта начинается вычисление , При этом формирователь 82 подключает через коммутатор 84 на первые входы перемножителя 86 вы- ходы блока 881 Выходы накопителя 10 остаются подключенными на вторые входы перемножителя 86, Из накопителя 10 выбирается величина х-, а из блока 88 - локатор стир аний х. Произведение х,,х записывается на триггеры группы 87, На восьмом такте XjX записывается блок 89. На девятом такте х из накопителя iO и х- из блока 88 перемножаются на перемножителе 86 и произведение складывается с Х-х на триггерах группы 87 Произведение получают на десято такте и складываьэт на тех же триггерах с ,

I

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

Для расчета используют произведение ,, записанное в блоке 89, выходы которого подключены на вторые входы перемножителя 86, На первые входы перемножителя 86 из блока 88 подается локатор х. На двенадцатом такте величина с, записывается на триггеры группы 87, с которы на 13-м такте переписывается в блок 89,

Для дальнейших расчетов неЬбходк- мо записатьw -в блок 89, Это производятся на 14-м такте путем подключения через коммутаторы 84 и 85 на входы перемножителя 86 выхода элемента НЕ 83. Таким образом, в перемножителе 86 производится перемножение oi. ori 06 и результат вначале записывается на триггеры группы 87, а на 15-м такте - в блок 89,

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

9

(фиг, 4), До этого с дешифратора 1 с входа 75 на D-вход триггера 64 подан сигнал Ошибка, поэтому триггер 64 устанавливается в I и разрешается работа вычислителя 16, При этом через элемент И 65 на счетчик 66 начинают поступать тактовые импульсы Т , Состояния счетчика 66 с выходов 77 попадет на адресные входы коммутатора 13, Число цепей А; в выходах 77 определяется количеством вычисляемых синдромов S;, Вычислени осуществляется по формулам (4), которые при исправлении двух ошибок и трех стираний принимают вид:

(,Т, +3,3 ,

4 . Sji-sj

,-C, +Si 62 +S, c3, (14

, IT, +8,- +8„Тэ .

Ha 16-M такте счетчик 66 переходит в первое состояние,- В данном случае в вычислении участвуют семь синдромов, поэтому на адресные вход коммутатора 13 со счетчика 66 подходят три цепи, которые обеспечивают получение восьми адресов, В первом состоянии счетчика 66 коммутатор 13 подключает синдром 8, который попадает через открытый сигналом Ошиб ка блок элементов И коммутатора 13 на вторые входы 73 перемножителя 68 В это время на первые входы 72 перемножителя 68 из блока 89 списывается с/ ,

На выходах перемножителя 68 получают произведение сС 8g 8 , которое записывается на триггеры группы 69, Аналогично получают произведени 8, , которое складывается с 8 на триггерах группы 69, Произведения э 3 также складываются на тех же триггерах. Полученная сумма 8g на 20-м такте переписывается параллельно в блоки 70 н 71,

Аналогично получают в соответствии с формулами (12) и записывают в блоки 70 и 71 модифицированные синдромы 85 , 8, 8з, на что тратится 15 тактов. Таким образом, работа вычислителя 16 заканчивается на 35-м такте.

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

10

.§2.§

(8;)

sksktiskll sls ,(

(1 5)

(16)

Вычисление начинается с такта, на котором формирователь 22 адреса открывает коммутаторы 23 и

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

25подключаются соответственно выходы блоков 70 и 71, Величины 84 и Sj

подаются на входы перемножителя 25 Произведение 8485 записывается в триггеры группы 26, Аналогично на 37 такте получают произведение , которое складывается с 848 на триггерах группы 26, Результат сложения записывается в блок 20 на 38-м.такте. Аналогично на 39-м такте вычисляют знаменатель выражения (15), т,е. (8)а, который на 41-м такте

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

0

:

а

1

г:

8; (8;)

Величину 1/а получают в преобразователе 27, в котором по адресу 8285(8)записана величина 1/а, Таким образом, здесь операция деления

5 заменяется операцией умножения. Для умножения выход блока 30 подключается через коммутатор 23 на первые входы перемножителя 25, а выходы преобразователя 27 - на его вторые вхо0 ды. Полученная величину G записывается в триггеры группы 26, а на 43-м такте сигнал:ом (Запись 2) с

5

выхода 31 переписывается в вычислитель 15 на блок 40 (фиг, 3), Аналогично вычисляют G

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

0 значение, записанное в блоке 21, На 49-м такте величина G с помощью сигнала 3,, (Запись) с выхода 32 переписывается на блок 41.

Недостающие локаторы ошибок х, и

5 Xj определяются по формулам (7) - (10) в вычислителе 15, где также вычисляются значения ошибок и стираний по формулам (11) и (12), Работу вычислителя 15 рассмотрим при двух

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

Счетчик 36 уже работал при записи локаторов стираний х, Хд и х в блоки 42 и 43 и остался в шестом состоянии, т.е. в состоянии, при котором осуществляется запись локатора х в блоки 42 и 43, Поэтому счетчик 36 при вторичном переходе триггера 33 в 1 и поступлении тактовых импульсов сначала переходит в седьмое состояние, для дальнейших вычислений нужно переписать в блок 43. Поэтому в седьмом состоянии счетчика 36 формирователь 39 сигналом с первых выходов через коммутатор 44 подключает на входы перемножителя 48 значение о(,° , а сигналом со вторых выходов через коммутатор 45 соединяет выходы блока 40 на вторые входы перемножителя 48, Таким образом, ла 50-м такте на выходах перемножителя 48 получают величину cj,, которая . записывается в триггеры группы 49. На 51 такте G, сигналом с формирователя 37 переписывается в блок 43,

На 52-м такте на первом выходе формирователя 38 появляется сигнал, которьй сдвигает на один разряд вправо содержимое блока 40, в качестве которого при может быть применен универсальный регистр, в котором предусмотрено считывание и запись информации в параллельном и последовательных кодах, а также циклический сдвиг данных влево и вправо, т,е,.в направлении первого или восьмого разрядов. Для сдвига т-й (последний) разряд регистра соединяется с входом первого разряда. При сдвиге вправо величина G,, записанчи которого на выходах последнего появляется записанная в нем по это адресу величина l/(Gj). Следовате но, на первых входах перемножителя I

5 появляется величина 0, а на вторы /(G.) . На этом же такте ттроисход перемножение G на 1/(G,) -и на выходах перемножителя 48 получают личину у , которая записывается в

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

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

15 бирает из блока 42 величину у , в результате преобразования которой входах элементов НЕ 52 и 53 и прям выходах сумматоров группы 50 получ ется величина Z,, которая подключа

20 ется с помощью формирователя 39 че коммутатор 44 на первые входы пере множителя 48. Одновременно формиро ватель 39 через коммутатор 45 подк чает выходы блока 43 на вторые вхо перемножителя 48. Из блока 43. сигн лом с формирователя 37 выбирается личина G, , Следовательно, на выход перемножителя 48 получен локатор O бок x,Z,Gj, который записывается триггеры группы 49. На 56 такте ло катор X, с помощью формирователя 3 переписывается в блоки 42 и 4,3,

На 57-м такте формирователь 37 снова выбирает из блока 42 величин Y , в результате преобразования ко ,торой в соответствии с формулой (1 на выходах элементов НЕ 52 и 53 и сумматоров группы 50 получается ве личина Z, которая подключается фо

С мирователем 39 через коммутатор 44 на первые входы перемножителя 48, Одновременно фор1-шрователь 39 чере коммутатор 45 подключает выходы бл ка 43 на вторые входы перемножител

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

30

35

ная в блоке 40, возводится в квадрат 50 37 переписывается в блоки 42 и 43, (GJ) , На 53-м такте формирователь 39 подключает через коммутатор 44 на первые входы перемножителя 48 выходы блока 41, а выходы 40 через коммутатор 46 и преобразовател ь 47 - 55 на вторые входы перемножителя 48, Значение (G, ), записанное в блоке 40, является адресом для ПЗУ преобразователя 47, в результате подаНа этом заканчивается определение каторов ошибок. Следовательно, в б ках 42 и 43 записаны локаторы ошиб X, и Хд и локаторы стираний х, х

и Xg.

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

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

5 появляется величина 0, а на вторых - /(G.) . На этом же такте ттроисходит перемножение G на 1/(G,) -и на выходах перемножителя 48 получают величину у , которая записывается в

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

На 55-м такте формирователь 37 вы5 бирает из блока 42 величину у , в результате преобразования которой на, входах элементов НЕ 52 и 53 и прямых выходах сумматоров группы 50 получается величина Z,, которая подключа0 ется с помощью формирователя 39 через коммутатор 44 на первые входы перемножителя 48. Одновременно формирователь 39 через коммутатор 45 подключает выходы блока 43 на вторые входы перемножителя 48. Из блока 43. сигналом с формирователя 37 выбирается величина G, , Следовательно, на выходах перемножителя 48 получен локатор OFIH- бок x,Z,Gj, который записывается на триггеры группы 49. На 56 такте локатор X, с помощью формирователя 37 переписывается в блоки 42 и 4,3,

На 57-м такте формирователь 37 снова выбирает из блока 42 величину Y , в результате преобразования ко- ,торой в соответствии с формулой (10) на выходах элементов НЕ 52 и 53 и сумматоров группы 50 получается величина Z, которая подключается форС мирователем 39 через коммутатор 44 на первые входы перемножителя 48, Одновременно фор1-шрователь 39 через коммутатор 45 подключает выходы блока 43 на вторые входы перемножителя

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

0

5

0 37 переписывается в блоки 42 и 43, 5

37 переписывается в блоки 42 и 43,

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

и Xg.

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

131

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

G,oS4 СлБл+СпЗа+Gi3S ,+Си5о /1-74

У, (.1//

Gv,G,,x,4-G,x,-bG,,,,x

G,G,, +к, , G.,G„,

, -t-x, G,2,

G,G,-)-x,G,3,(18)

G, x,- -X4+x,-t-X4+X5, , Х2+х,Хз+...+Хд Xy, ,XjXj- -x, Xj,X4+.. .+x,X4Xj,

,X,,X,jXjX5 + , . .+Х,,ХзХ4Х5

(19)

Вначале определяют G, , G, G,, G no формулам (19). При этом локаторы X, - Xj, записаны в блоках 42 и 43. Вычисление G) происходит с 59-го такта так: формирователь 39 подключает с помощью коммутатора 44 выходы блока 42 на первые входы перемножителя 48. Формирователь 37 задает адрес, по которому в блок 42 записан локатор ошибок х,, в результате с выхода блока 42 величина х, подается на первые входы перемножителя 48. Формирователь 39 подключает выход элемента НЕ 51 через коммутатор 45 на вторые входы перемножителя 48, в результате на него подается ci. 1. Результат умножения oi°x записывается в триггеры группы 49, Аналогично происходит выбор из блока 42 и умножение на ot° локатора х . Результат складывается по модулю два с х на триггерах группы 49. На следующем, 61-м такте необходимо выбрать из блока 42 локатор стираний Kg и сложить его с х,. Адрес для выбора X, из блока 42 задает формирователь 37. При этом выходы блока 42 через коммутатор 44 подключаются на первые входы перемножителя 48, на вторые входы снова подключается 4i° . Таким образом, происходит умножение х, наЫ° и сложение результата с х,+Х2 на триггерах группы 49. Аналогично производится сложение х и Xg. Результат сложения, т.е. G,, записывается в блок 42 на 64-м такте.

Также производится вычисление G G .J и G4, которые записываются в .блок 42.

95531 14

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

5 записываются с триггеров группы 49 в блок 42.

После этого приступают к определению у , при этом вначале определяют числитель, а затем знаменатель

О выражения (17). Для нахождения числителя синдромы SQ, S,,...,Sj., через коммутатор 13 считываются сигналами со счетчика 66 вычислителя 16, которые задают адреса для мульти 5 плексора в коммутаторе 13, подключа.,

кяцего SP , S ,

,Sj, на входы перемножителя 68 по сигналу с выхода триггера 33 (выход 63). Значение числителя записывается в блок 42, а

20 значение знаменателя остается на триггерах группы 49. Теперь числитель необходимо разделить на знаменатель. Значе ше числителя из блока 32 через коммутатор 44 подается на

5 первые входы перемножителя 48, а значение знаменателя через коммута- тор 46, преобразователь 47 и коммутатор 45 - на вторые входы перемножителя 48. Если значение знаменате30 ля обозначить через а , то на выходе преобразователя 47 получают . величину /а, которая и умножается на числитель. В результате на выходах перемножителя 48 получают значение у, ,

35 Величина У( записывается в триггеры группы 49, а затем в блок 43.

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

Далее величина х , являющаяся адресом искаженного элемента, с помощью формирователя 37 списывается с

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

50 списывает из блока 43 у. При сложении разрядов искаженного элемента с у, происходит исправление и исправленный элемент записывается в буферный накопитель 2 по тому же адресу.

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

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

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

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

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

счетчика соединены с информационными входами соответственно второго накопителя и второго счетчика, ВЫХОДЕЛ которых подключены к входам дещифра- тора состояний, первый выход которого соединен с вторым управляющим входом четвертого вычислителя и третьим управляющим входом второго вычислителя, второй и третий выходы дешифратора состояний соединены соответственно с четвертым управляющим входом второго вычислителя и первым управляющим входом третьего вычислителя, первые выходы которого подклю« чены к информационным входам первого вычислителя, выходы первого накопителя -подключены к соответствующим информационным входам коммутатора, первые и вторые выходы которого соединены соответственно с первыми информащ-юнными входами третьего вычислителя и вторыми информационными входами второго вычислителя, третий выход которого соединен с первым уп- равляюпщм входом коммутатора, второй

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

которого подключены к информационным входам четвертого и третьим информационным входам -второго вычислителей.

63

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