Устройство для декодирования кодов боуза-чоудхури- хоквингема

 

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

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

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

РЕСПУБЛИК (51) 4

ОПИСАНИЕ ИЗОБРЕТ

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3515579/24-09 (22) 29.11.82 (46) 23.07.85. Бюл. № 27 (72) Ю. П. Пятошин, В. А. Тузиков, В. Г. Ивочкин, В. А. Зиновьев и И. И. Думер (53) 621.394.14 (088.8) (56) Авторское свидетельство СССР № 621092, кл. Н 03 К 13/32, 1978.

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

Галуа введены три сумматора и два блока

„„SU„„1168946 возведения в квадрат, при этом выход первого блока возведения в квадрат подключен к первым входам первого и второго блоков умножения, выходы которых подключены к первым входам первого и второго сумматоров, выходы которых подключены к первым входам третьего и четвертого блоков умножения, при этом вход первого блока возведения в квадрат объединен с вторыми входами второго, третьего и четвертого блоков умножения, а второй вход первого блока умножения объединен с вторым входом второго сумматора, выход которого через второй блок возведения в квадрат подключен к первому входу третьего сумматора, к второму входу которого подключен выход третьего блока умножения, причем вход первого <р

Я

Ъ блока возведения в квадрат, второй вход первого блока умножения и второй вход первого сумм атора являются соответственно первым, вторым и третьим входами вычис- С лителя в поле Галуа, первым, вторым, третьим и четвертым выходами которого явля- Я ются выходы второго сумматора, четвертого блока умножения, первого и третьего сумматоров.

1168946

15

25

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

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

На фиг. 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 вычисления синдромов для кода

БЧХ с исправлением трех ошибок при m=7 содержит три семиразрядных регистра сдвига с обратными связями, которые соединены с сумматорами по модулю два в соответствии с полиномами q>(x), с1,(х) и q (x). Синдром S вычисляется в первом семиразрядном регистре сдвига с обратными связями в соответствии с полиномом gq (х) = х + x + j.

Синдром $з вычисляется во втором регистре сдвига с обратными связми в соответствии с полиномом оз(х) = х" + х + х + х + 1 с учетом, что 4, = K + 1.

Синдром $к вычисляется в третьем регистре сдвига с обратными связями в соответствии с полиномом q (х) = х" + х +

+ х + х + 1 и с учетом, что хУ= сс +-1.

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

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

Работу устройства декодирования кодов

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

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

127 разрядах:

0 0 0 .......... 0 1 0 0 1 0 0 0 1

1 2 3 ......,.. 119 120 121 122 123 124

125 126 127

Блок 1 вычисления синдромов по принятому кодовому слову с ошибками С(Х) выдает синдромы

C(cd), 1 = 1, 3, 5, где с . — примитивный элемент поля Галуа.

Для данного примера на выходе блока 1 вычисления синдромов образуются синдромы S, Sз и S в соответствии с соотношениями, определяемыми полиномами:

q,(x), г1з(х) и с1,.(х) в виде двоичных семиразрядных последовательностей:

S, = (0011000};

{0011110};

Ss = {0001100} .

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

S> на первый вход, Sq на второй вход и

Ss на третий вход:

На вход первого блока 5 возведения в квадрат поступает последовательность

0011000, а с выхода этого блока последовательность 1010010, которая поступает на первые входы первого 6 и второго блоков 7 умножения. На второй вход первого блока умножения поступает синдром $з, результат умножения 0110000 поступает на первый вход первого сумматора 8. На второй вход второго блока 7 умножения поступает синдром $, на выходе второго блока? умножения образуется последовательность

{1000111} = S>, которая поступает на первый вход второго сумматора. 9. На второй вход первого сумматора 8 поступает синдром $5, с выхода первого сумматора 8 последовательность 0111100 поступает на первый вход третьего блока 10 умножения и на третий выход вычислителя 2 в поле Галуа.

На второй вход второго сумматора 9 поступает синдром $з, с выхода второго сумматора 9 сигнал в виде последовательности

1011001, поступает на первый выход вычислителя 2 в поле Галуа, а также на первый вход четвертого блока 11 умножения и на вход второго блока 13 возведения в квадрат.

На второй вход третьего блока 10 умножения поступает синдром S, произведение в виде последовательности 0000100 с выхода третьего блока 10 умножения поступает на второй вход третьего сумматора 12. С вы1168946

Фиг.2 хода второго блока 13 возведения в квадрат результат операции в виде последовательности 1100001 поступает на первый вход третьего сумматора 20, с выхода которого результат суммирования 1100101 поступает на четвертый выход вычислителя 2 в поле

Галуа. Таким образом, на выходах вычислителя 2 в поле Галуа формируются последовательности, соответствующие коэффициентам многочлена локаторов ошибок б;, б,, б, 6 . на первом выходе G, = 1011001; на втором выходе 6 — — 0100110; на третьем выходе ба = 0111100; на четвертом выходе dq — — 1100101.

Эти коэффициенты поступают в блок 3 вычисления процедуры Ченя, который определяет корни многочлена локаторов ошибок, путем последовательной подстановки всех элементов поля GF(2 ) в этот многочлен.

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

Таким образом, устройство декодирования кодов БЧХ позволяет повысить скорость декодирования кодов. Это достигается тем, что в вычислителе 2 в поле Галуа для исправления t - - 3 ошибок использованы зависимости коэффициентов б, 6„+, и б от синдромов S<, Яз и Sq найденных на первом этапе декодирования. Эти зависимости не содержат наиболее трудоемких операций деления и вычисления обратного элемента и, кроме того, позволяют сократить число операций умножения. В результате вычислитель 2 в поле Галуа GF(2 ) содержит лишь четыре блока умножения и производит вычисление многочлена локаторов ошибок за (2m+3) тактов. Кроме того, вычислитель в поле Галуа не требует дополни15

Ускорение декодирования и уменьшение числа схем умножения получены за счет использования зависимостей величин б 6, бр и О от синдромов Sf, S 3 и Sp я за счет введения в вычислитель простых

20 однотактных схем возведения в кадрат элементов поля GF(2 ).

Использование изобретения позволяет уменьшить время вычисления коэффициентов многочлена локаторов ошибок в блоке вычислителя в поле Галуа более чем в 7 раз, а это значит, что уменьшается и общее время декодирования кодового слова.

1168946 фиг4

Составитель С. Осмоловский

Редактор P. Циника Техред И. Верес Корректор Л. Бескид

3а каз 4615/43 Тираж 710 Подписное

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

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

Филиал ППП «Патент», r. Ужгород, ул. Проектная, 4