Устройство для декодирования кодов Боуза-Чоудхури-Хоквингема Советский патент 1985 года по МПК G06F11/08 

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

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

На фиг. 1 приведена структурная электрическая схема устройства декодирования кодов Боуза-Чоудхури-Хоквингема (БЧХ); на фиг. 2 - структурная схема блока возведения -в квадрат; на фиг. 3 - структурная схема сумматора; на фиг. 4 - структурная схема блока умножения.

Устройство декодирования кодов БЧХ содержит блок 1 вычисления синдромов, вычислитель 2 в поле Галуа, блок 3 вычисления процедуры Ченя, блок 4 задержки, вычислитель 2 в поле Галуа содержит первый блок 5 возведения в квадрат, первый и второй блоки 6 и 7 умножения, первый и второй сумматоры 8 и 9, третий и четвертый блоки 10 и 11 умножения, третий сумматор 12, второй блок 13 возведения в квадрат, блоки 5 и 13 возведения в квадрат содержат сумматоры 14-1 - 14-3 по модулю два, сумматоры 8 и 9 содержат сумматоры 15-1 - 15-7 по модулю два, блоки 6, 7, 10 и 11 умножения содержит семиразрядный регистр 16 сдвига, двухвходовые элементы И 17-1 - 17-7, трехразрядный регистр 18 сдвига, четырехразрядный регистр 19 сдвига, сумматоры 20- 1-20 - 7 21 по модулю два, триггеры 22-1 - 22-7. Блок 1 вычисления синдромов для кода БЧХ с исправлением трех ошибок при т 7 содержит три семиразрядных регистра сдвига с обратными связями, которые соединены с сумматорами по модулю два в соответствии с полиномами qj(x), Яэ(х) и (x). Синдром S( вычисляется в первом семиразрядном регистре сдвига с обратными связями в соответствии с полиномом qj (х) x +x+l Синдром Sj вычисляется во втором регистре сдвига с обратными связми в соответствии с полиномом

Чз(х) х+ х2 + X -Ь 1

с учетом, что сС 1.

Синдром Ss вычисляется в третьем регистре сдвига с обратными связями в соответствии с полиномом qj (х) х Ч-х + + х + 1 и с учетом, что ос oc-+l.

Синдромы Si, Sj и 85 в виде двоичных семиразрядных последовательностей образуются через п тактов поступления на вход блока 1 вычисления синдромов принятого кодового слова.

Блок 3 вычисления процедуры Ченя содержит три регистра сдвига с обратными связями и сумматор по модулю два, соответствующие умножению на элементы оС, ot, л, поля GF(2), четырехвходовые сумматоры по модулю два и элемент ИЛИ.

Работу устройства декодирования кодов БЧХ с предложенным блоком вычислителя в поле Галуа рассмотрим на примере кода (127, 106), позволяющего исправлять три независимых ошибки.

Без ограничения общности предположим, что на вход устройства поступает нулевой кодовый вектор с ошибками в 120, 123 и 127 разрядах:

000 010010001

1 2 3 119 120 121 122 123 124

125 126 127

Блок 1 вычисления синдромов по принятому кодовому слову с ошибками С (X) выдает синдромы Si С(ос), i 1, 3, 5,

где оС - примитивный элемент поля Галуа. Для данного примера на выходе блока 1 вычисления синдромов образуются синдромы Si, Sa и Ss в соответствии с соотношениями, определяемыми полиномами: qi(x), q3(x) и qjCx) в виде двоичных семиразрядных последовательностей:

Si (ООПООО);

Si {0011110}; S5 {0001100}.

Эти последовательности поступают в вычислитель 2 в поле Галуа соответственно:

0 Si на первый вход, Sj на второй вход и Ss на третий вход.

На вход первого блока 5 возведения в квадрат поступает последовательность ООПООО, а с выхода этого блока последовательность 1010010, которая поступает на

первые входы первого 6 и второго блоков 7 умножения. На второй вход первого блока умножения поступает синдром Sa, peзyльтaf умножения 0110000 поступает на первый вход первого сумматора 8. На второй вход второго блока 7 умножения поступает синдром Si, на выходе второго блока 7 умножения образуется последовательность {l000111} Sf, которая поступает на первый вход второго сумматора. 9. На второй вход первого сумматора 8 поступает синдром Ss, с выхода первого сумматора 8 последовательность 0111100 поступает на первый вход третьего блока 10 умножения и на третий выход вычислителя 2 в поле Галуа. На второй вход второго сумматора 9 поступает синдром Sj, с выхода второго сумматора 9 сигнал в виде последовательности 1011001, поступает на первый выход вычислителя 2 в поле Галуа, а также на первый вход четвертого блока 11 умножения и на вход второго блока 13 возведения в квадрат.

5 На второй вход третьего блока 10 умножения поступает синдром S, произведение в виде последовательности 0000100 с выхода третьего блока 10 умножения поступает на второй вход третьего сумматора 12. С выхода второго блока 13 возведения в квадрат результат операции в виде последовательности 1100001 поступает на первый вход третьего сумматора 20, с выхода которого результат суммирования 1100101 поступает на четвертый выход вычислителя 2 в поле Галуа. Таким образом, на выходах вычислителя 2 в поле Галуа формируются последовательности, соответствующие коэффициентам многочлена локаторов ошибок GO, 61, на первом выходе во 1011001; на втором выходе 6i 0100110; на третьем выходе бг. 0111100; на четвертом выходе бз 1100101. Эти коэффициенты поступают в блок 3 вычисления процедуры Ченя, который определяет корни многочлена локаторов ошибок, путем последовательной подстановки всех элементов поля GF(2) в этот многочлен. Блок 3 вычисления процедуры Ченя формирует исправляющие биты на местах, соответствуюших месту расположения найденных корней и, тем самым, происходит исправление ошибочных бит в информационной последовательности, поступающей с выхода блока 4 задержки. Таким образом, устройство декодирования кодов БЧХ позволяет повысить скорость декодирования кодов. Это достигается тем, что в вычислителе 2 в поле Галуа для исправления ошибок использованы зависимости коэффициентов б,,, GJ, , и 65 от синдромов Si , Sj и 85 , найденных на первом этапе декодирования. Эти зависимости не содержат наиболее трудоемких операций деления и вычисления обратного элемента и, кроме того, позволяют сократить число операций умножения. В результате вычислитель 2 в поле Галуа GF() содержит лишь четыре блока умножения и производит вычисление многочлена локаторов ошибок за (2т-f3) тактов. Кроме того, вычислитель в поле Галуа не требует дополнительной схемы управления. Ускорение декодирования и уменьшение числа схем умножения получены за счет использования зависимостей величин б, 6i, бг и бз от синдромов Si, Sa и S5 И за счет введения в вычислитель простых однотактных схем возведения в кадрат элементов поля GF(2). Использование изобретения Позволяет уменьшить время вычисления коэффициентов многочлена локаторов ошибок в блоке вычислителя в поле Галуа более чем в 7 раз, а это значит, что уменьшается и общее время декодирования кодового слова.

УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ КОДОВ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА, содержащее последовательно соединенные блок вычисления синдромов, вычислитель в поле Галуа и блок вычисления процедуры Ченя, а также блок задержки, вход которого объединен с входом блока вычисления синдрома, а выход блока задержки подключен к соответствующему входу блока вычисления процедуры Ченя, при этом вычислитель в поле Галуа содержит четыре блока умножения, отличающееся тем, что, с целью повышения быстродействия устройства, в вычислитель в поле Галуа введены три сумматора и два блока возведения в квадрат, при этом выход первого блока возведения в квадрат подключен к первым входам первого и второго блоков умножения, выходы которых подключены к первым входам первого и второго сумматоров, выходы которых подключены к первым входам третьего и четвертого блоков умножения, при этом вход первого блока возведения в квадрат объединен с вторыми входами второго, третьего и четвертого блоков умножения, а второй вход первого блока умножения объединен с вторым входом второго сумматора, выход которого через второй блок возведения в квадрат подключен к первому входу третьего сумматора, к второму входу которого подключен выход третьего блока умножения, причем вход первого блока возведения в квадрат, второй вход первого блока умножения и второй вход первого сумматора являются соответственно первым, вторым и третьим входами вычислителя в поле Галуа, первым, вторым, третьим и четвертым выходами которого являются выходы второго сумматора, четвертого блока умножения, первого и третьего сумматоров.