Устройство для исправления ошибок в информации, закодированной циклическим кодом Советский патент 1976 года по МПК H03M13/51 G06F11/10 

g(x)gO+ gl X + ...+gn k-X коэффициенты gi с номерами от (i) до (i-/j-l-s + 2) равны нулю. На фиг. 1 не показаны цени тактовых и синхронизирующих сигналов, а также ключи, используемые обычно в декодерах циклических кодов и не имеюндие существенного значения для рассмотрения принцина работы предлагаемого устройства.

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

После ввода кодового слова ао, «ь а ... Cn-iB регистр 1 сигналы с выходов разрядов регистра поступают на сумматоры блока 3, на выходах которых вырабатываются значения начального символа UQ в соответстВИИ с системой проверок кода. В соответствии с большинством совпадающих результатов проверок мажоритарный элемент 4 принимает решение об оценке значения GO, которое является правильным, если в кодовом слове ош.ибки отсутствовали или если имелась корректируемая комбинация (конфигурация) ошибок. Сипнал с выхода мажоритарного элемента поступает на выход устройства, а также по цепи обратной связи - на входы сум.маторов 2. Так что при следующем тактовом импульсе сдвига в разряд регистра, перед которым включен сумматор, будет записан результат суммирования по модулю два сигнала с предыдущего разряда и сигнала обратной связи. После сдвига содержимого регистра 1 и до выработки значения следующего информационного символа с коммутатора 5 подается импульс, устанавливающий в нуль те разряды регистра, которые не являются необходимыми для декодирования следующнх символов. Таким образом происходит фактическое отключение некоторых разрядов регистра от блока сумматоров, в результате чего воЗ(Можные ошибки в этих разрядах не влияют более на итог декодирования. Тем самым обеспечивается изменение системы проверок в сторону повышения нх достоверности в процессе декодирования

В течение k тактов декодирования сигнал из канала связи в регистр не подается, что эквивалентно подаче комбинации 00...0.

Поясним сказанное на примере декодирования кода (15; 4), имеющего полиног/t

g(x) + Х + Х + х + Х + и COOT.

ветственно h(x). Порождающая матрица этого кода имеет вид

«14 «13 «12 «11 «10 00011

С Непорредственно из этой матрицы следует система разделенных проверок для первых четырех символов кода ао, GI, «2, 03 (в первой стрОКе каждого столбца занисан номер инфор.мационного символа ai , а в следующих стро- 65

ках под ним указаны номера СИМВОЛОР, входящих в проверки для а/ ).

«о

«3

«2

10

(2)

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

20

«2

«О

(3)

Структурная схема устройства для кода (15; 4) приведена на фиг. 2. Здесь дополнительные сумматоры но модулю два включены после разрядов регистра с номерами «И, «10, «9, «8, «6, «4, «3. Для реализации

системы проверок (3) требуется после декодирования символа QI записать «О на позицию символа а4, а после декодирования «2 - «О на позиции символов ад, «s и а. Это достигается подключением первого и второго выходов и коммутатора соответственно к входам установки «О разрядов регистра с номерами 2 и 2, 5, 7. После декодирования UQ на начальном шаге декодирования должен быть обнулен нулевой разряд регистра, однако в предлагаемом устройстве это оказывается излишним, поскольку значение символа, записанного в нулевом разряде, не используется на последующих шагах декодирования.

Предлагаемый декодер исправляет ряд

комбинаций ошибок кратности t 4, которые не исправляются в известном устройстве. К таким комбинациям огносится, например, искажение символов «4, ит, аэ и ац. В то же время, все ошибки этой кратности, исправляемые в

известном устройстве, исправляются также и в предлагаемом устройстве.

Известно, что наиболее достоверными проверками являются проверки с одним членом в

(1) правой части вида а; а . Поэтому увеличение числа таких проверок в процессе декодирования повышает достоверность результата. В общем случае декодирования циклических кодов, когда исходные проверки имеют более двух членов в правой части, происходит ностепенное сокращение числа членов в проверках, так что на последнем шаге декодирования остаются только проверки вида а,- йу .

Действие видоизмененной цепи обратной связи можно объяснить следук щим образом. Любое кодовое слово v(x) может быть представлено в виде линейной комбинации строк матрицы G

v(x)ao W©ai xg M)Q«2|x g(x)®... |V

Такое представление позволяет однозначно связать наличие единицы на начальной позиции кодового слова с наличием составляющей §(х) в v(x). Поэтому после первого щага декодирования в предлагаемом устройстве проводится исключение составляющей g(x) из принятого сообщения v(x), для чего осуществляется посимвольное суммирование по модулю два и{х)®8(х путем подачи сигнала обратной связи на сумматоры 2, встроенные в буферный регистр 1. Выполнение этой операции приводит к тому, что порождающей матрицей для оставщейся части v(x} оказывается матрица G без первой строки. На каждом щаге декодирования описанная онерация повторяется, причем па S-M щаге обнуляются разряды регистра 1 с номерами i, которым соответствуют столбцы матрицы G, не имеющие единиц в последних k-5-1-х строках, или, что то же самое, для которых в полиноме g(x) есть нулевые коэффициенты при степенях от (г) до (f-k+s + 2). Таким образом, на последнем щаге от матрицы G остается только ее последняя строка, что обусловливает наличие только одного члена в правой части проверок для символа а,. К этому моменту отключенными оказываются все разряды, соответствующие символам, имеюнщм нули в этой строке матрицы.

Предлагаемый декодер с повыщенной достоверностью вырабатывает значения а , а , . . . а в представлении кодового слова в

(4)

форме (4), по которым легко могут быть определены значения информационных символов Со, QI, . . ., а,г-1 соответствующих разделенному коду (например, для кода (15,4) имеем ао ад, ai a, а2 а2 и «3 3 ) Если же кодирование осуществляется в соогветствии с (2), то надобность в дополнительных преоперациях в декодере отпадает.

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

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

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

Сnr.,Jt..- q-El :.1 LrrT4 Lr- - r-hLJ

т-

ход

-ьгН К+

fO

2 f о

ст