Декодер кода бчх

 

Изобретение относится к вьмислчтельной технике. Его использование в системах передачи цифровой информации позволяет повысить достоверность декодирования кодов ЁЧХ с кодовым расстоянием d б(В). Декодер содержит буфер ый регистр 1 сдвига, сумматор 2 по модулю два, вычислители 3, 5, 8 и 15 синдромов, блоки 4 и 16 буферной памятя, корректор 6 ошибок, элемент ЗАПРЕТ 7, блок 9 деления в поле Галуа, сумматор 11 в nor ле Галуа, дешифратор 12 нуля, элемент НЕ 19 и элемент И 24. Благодаря введению блока 10 деления в поле Галуа , дешифраторов 13 и 14 нуля блока 17 буферной памяти синдрома, сумматора 18 квадратов элементов в поле Галуа, элементов НЕ 20-23, элементов И 25-29 и элемента ИЛИ 30 в декодере обеспечивается обнаружение дополнительных неисправных ошибок. 2 ил.

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

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

РЕСПУБЛИК (51)4 Н 03 М 13 02

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

ПО ИЭОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 42705 11/24-24 (22) 29.06.87 (46) 07.02,89. Бюл. М- 5 (72) Е.В. Пустыгин (53) 681.325 (088.8) (56) Авторское свидетельство СССР

1Ф 1401611, кл. Н 03 М 13/02, 1985 °

Берлекэмп Э. Алгебраическая теория кодирования. — M. Мир, 1971, с. 142-145, 175-176.

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

Р 794728, кл. Н 03 М 13/00, 1978.

Труды НИИР, 1983, Р 1, с. 48-52. (54) ДЕКОДЕР КОДА БЧХ (57) Изобретение относится к вычислительной технике. его использование в системах передачи цифрбвой информации позволяет повысить достовер„„Я0„„1457166 А 1 ность декодирования кодов БЧХ с кодовым расстоянием d = 6(B .). Декодер содержит буферный регистр 1 сдвига, сумматор 2 по модулю два, вычислители 3, 5, 8 и 15 синдромов, блоки 4 и 16 буферной памяти, корректор 6 ошибок, элемент ЗАПРЕТ 7, блок 9 де-, ления в поле Галуа, сумматор 11 в по,". ле Галуа, дешифратор 12 нуля, элемент НЕ 19 и элемент И 24. Благодаря введению блока 10 деления в поле Галуа, дешифраторов 13 и 14 нуля, блока 17 буферной памяти синдрома, сум" матора 18 квадратов элементов в поле

Галуа, элементов НЕ 20-23, элементов

И 25-29 и элемента ИЛИ 30 в декодере обеспечивается обнаружение дополнительных неисправных ошибок. 2 ил.

1457166

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

В

Коды Боуза-Чоудхури-Хоквингема (БЧХ) с кодовым расстоянием d = б(В ) строятся на основе кодов БЧХ с d

= 5(В ) путем выбрасывания всех кодовых слов нечетного веса. Для этого 10 порождающий многочлен g (Х) кода В домножается на (Х+1). Код В для любого m > 4 имеет длину п = 2m-1, число информационных символов.К =

= n-2m-1.

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

На фиг. 1 представлена функциональная схема декодера; на фиг. 2— диаграммы, поясняющие алгоритм декодирования.

Декодер кода БЧХ содержит буферный регистр 1 сдвига, сумматор 2 по модулю два, вычислитель 3 первого синдрома, блок 4 буферной памяти первого синдрома, вычислитель 5 второго синдрома, корректор .6 ошибок; элемент

ЗАПРЕТ 7, вычислитель 8 третьего синдрома, первый и второй блоки 9 и

10 деления в поле Галуа, сумматор 11 в поле Галуа, первый — третий дешиф30 раторы 12-14 нуля, вычислитель 15 нулевого синдрома, блок 16 буферной памяти нулевого синдрома, блок 17 буферной памяти третьего синдрома, сумматор 18 квадратов элементов в поле

Галуа, -первый — пятый элементы НЕ 1923, первый-шестой элементы И 24-29 и элемент ИЛИ 30. На фиг. 1 обозначены вход 31, информационный выход 32 и и выход 33 сигнала обнаружения неисправимой ошибки.

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

Вычислитель 5, блоки 9 и 10 деления выполняются с использованием программируемых ПЗУ.

Сумматор 18 служит для вычисления 50 трассы элемента в поле Галуа в соhl ° y ? t ответствии с формулой Т „() = - Р

1=1 причем Т (p) = 0 или 1, и выполняет55 ся на программируемом ПЗУ.

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

Область переданного кодового слова U кода В, окруженного шаром радиуса 2 (соответствует всевозможным однократным и двухкратным ошибкам).

Декодер любую последовательность на этой области правильно декодирует в кодовое слово U. Комбинации синдромов при этом

S-=О S=0 S=0 Ь=О о 3

Ь,= Π— кодовое слово 11;

Бо- 1; 8 ф 0; Б ф 0; Ь, ф 0; ?= 0 — однократная ошибка;

0 0 Б 0 83 0 т

6 ф 0 - двухкратная ошибка.

Область кодовых слов V четного веса кода В,, отличных от переданного кодового слова U, окруженных ???aрами радиуса 2 (соответствующие ошибки имеют кратность,. равную весу кодового слова, или отличаются от него на +1 и 1 2), Декодер никаким образом не может отличить эту область от области слова U. Область слова V соответствует необнаружимому неправильному декодированию в кодовое слово V. Комбинации синдромов при этом те же, что в области слова U, Общей отличительной чертой областей 11 и Ч является соотношение е = S (mod2), где e — число импульсов исправления декодера — расстояние от ближайшего кодового слова.

Области кодовых слов Т нечетного веса кода В (те кодовые слова, которые выбрасываются из кода В при по"

5 строении кода В ), окруженных шаром радиуса 2 (соответствующие ошибки имеют кратность, равную весу кодового слова U,.èëè отличаются от него на +1 и +2). Комбинации синдромов в этой области те же, что в областях

U и V, но с заменой S íà S,. При этом выполняется соотношение е =, Б р (шос12) °

Это позволяет обнаружить весь класс неисправимых ошибок — область

Т.

В известном декодере из всего этого класса обнаруживаются только ошиб66 4 циента Ь, а элемент НЕ 19 инвертирует значение этой проверки.

Дешифратор 13 нуля проверяет равенство нулю синдрома S„, а элемент

HE 20 инвертирует значение этой проверки. Блок 10 деления в поле Галуа находит значение Ь /S, а сумматор

18 квадратов элементов в поле Галуа . определяет Т,,(/$ ) . Элемент НЕ 21 инвертирует значение трассы. Блок 17 буферпой памяти синдрома S, запоминает значение S,, дешифратор 14 прове-, ряет его равенство нулю, а элемент

НГ 22 инвертирует значение этой проверки. Элемент НЕ 23 инвертирует значение синдрома S

Элемент И 24 вырабатывает сигнал обнаружения ситуации Я,Ф О и 6 Ф О.

Элемент И 26 формирует сигнал обнаружения неисправимой ошибки, когда

Я„р 0; & 4 0 и Т,.(Ь /Я,) Ф О. Эле-. мент И 27 формирует сигнал для случая Я„. ф 0; 4 / 0; Т(,(Ь./S<) = О и

S = 1. Элемент И 29 формирует сигнал обнаружения неисправимой ошибки, когда S, Ф О; Ь = 0 и S,= О. Элемент И 28 формирует сигнал обнаружения неисправимой ошибки, когда S„= О и Sz g О. Элемент И 25 формирует сиг", нал обнаружения неисправимой ошибки, когда S „= О; S = 0 и S,= 1, Элемент

ИЛИ 30 формирует суммарный си.-.нал обнаружения неисправимой ошибки.

Таким образом, в предлагаемом декодере кода БЧХ с кодовым расстоянием 6 обнаруживаются дополнительные классы неисправимьж ошибок, за счет чего повышается достоверность декодирования цифровых сигналов.

3 1 <571 ки, для которых S 1 и b Ф О, т.е, ошибки, лежащие на сферах радиуса 2 вокруг кодовых слов Т, В предлагаемом декодере дополнительно обнаруживаются ошибки, лежащие на сферах

6 радиуса 1 вокруг кодовых слов Т, и сами кодовые слова Т.

Область последовательностей, лежащих на расстоянии 3 до ближайшего ко- 10 дового слова кода В 5. Это еще один класс обнаружимых неисправимых ошибок.

В этих условиях квадратное уравнение 1 + b, Z + 6 2 = О не может иметь двух корней в поле Галуа GF(2 ), так как в противном случае эта ситуация сводилась бы к рассмотренным ранее.

Известно,,что такое квадратное уравнение имеет два корня в поле GF(2 ), если трасса T (ь /S ), = 0 при S Ф О.

Тогда для обнаружения ошибок в данной области (между областями U u

V) следует руководствоваться правилами: формулаизобретения

Декодер кода БЧХ, содержащий буферный регистр. сдвига, вход которого объединен с входами вычислителя нулевого синдрома, вычислителя первого синдрома.и вычислителя третьего синдрома и является входом декодера, выход буферного регистра сдвига соединен с первым входом сумматора по модулю два, выход которого является информационным выходом декодера, выход вычислителя нулевого синдрома подключен к входу блока буферной па« мяти нулевого синдрома, выход вы гнслителя первого синдрома соединен с входом делителя первого блока деления в поле Галуа и входом блока 6vКорректор 6 по вычисленным значениям Ь,= S, и 6, вырабатывает импульсы коррекции ошибок, которые через элемент ЗАПРЕТ 7 поступают на . сумматор 2. Элемент 7 запрещает кор66 рекцию ошибок, если обнаруживается неисправимая ошибка. Дешифратор 12 нуля проверяет равенство нулю коэффиS,Ф0; ЬФО; Т (Ь/Я) или $,= 0; S ô О.

В известном декодере ошибки в этой области не обнаруживаются.

Декодер кода БЧХ работает следующим образом. 30

Принятый цифровой сигнал с входа

31 поступает на буферный регистр 1 сдвига, где задерживается на время декодирования и подается на сумматор 2 по модулю два, на другой вход которого приходят импульсы исправления ошибок. С выхода сумматора 2 исправленный цифровой сигнал (в котором остались неисправимые ошибки, как об-, наружимые, так и необнаружимые) пос- 40 тупает на вход 32.

Цифровой сигнал поступает также на вычислители 3, 8 и 15 синдромов

S, S z u S соответственно. Синдромы

S, и S сохраняются в блоках 4 и 16 46 соответственно. Вычислитель 5 синдрома S определяет S как квадрат S

Блок 9 деления в поле Галуа находит значение S /$„, а сумматор 11 в поле

Галуа — вычисляет Ь = S + S /Я1. 60 рому входу третьего и третьему входу четвертого элементов И, выход блока буферной памяти третьего синдрома соединен с входом третьего дешифратора нуля, выход которого непосредственно и через четвертый эле- . мент НЕ подключен соответственно к третьему входу второго и второму входу пятого элементов И; выходы второго — шестого элементов И соединены с соответствующими входами элемента ИЛИ, выход которого подключен к запрещающему входу элемента ЗАПРЕТ и является выходом сигнала обнаружения неисправимой ошибки декодера.

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

Техред М. Ходанич Корректор Л. Пилипенко

Редактор A. Мотыль

Заказ 7563/58

Тираж 879

Подписное

ВНИИА Гасударственного комитета по изобретениям и открытиям при ГКНТ СССР

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

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

5 14571 ферной памяти первого синдрома, выход которого подключен к входу вычислителя второго синдрома и первому входу корректора ошибок, выход вычислителя третьего синдрома соединен с входом делимого, первого блока деления в поле Галуа, выход которого и выход вычислителя второго синдрома подключены к первому и второму входам сумматора в поле Галуа, выход которого соединен с входом первого дешифратора нуля и вторым входом корректора ошибок, выход которого соединен с разрешающим входом элемента ЗАПРЕТ, выход которого подключен к второму входу сумматора по модулю два, выход первого дешифратора нуля через первый элемент НЕ соединен с первым входом первого элемента И, о т л и ч а ю—

«ц и и с я тем, что, с целью повышения достоверности декодирования, в декодер введены сумматор квадратов элементов в поле Галуа, второй блок деления в поле Галуа, второй и тре- 25 тий дешифраторы нуля; второй — пятый элементы НЕ, второй — шестой. элементы И, элемент ИЛИ и блок буферной памяти третьего синдрома, вход которого подключен к выходу вычислителя третьего синдрома, входы делителя и делимого второго блока деления в пополе Галуа подключены к выходам вычислителя второго синдрома и сумматора в поле Галуа, вход второго дешифратора нуля подключен к выходу блока буферной памяти первого синд66 6 рома, выход второго дешифратора нуля соединен с первыми входами второго и пятого элементов И и входом второго элемента НЕ, выход которого под— .ключен к второму входу первого и первому входу шестого элементов И, выход первого элемента И соединен с первыми входами трегьего и четвертого эгементов И, выход блока буферной памяти нулевого синдрома подключен к вторым входам второго и четвертого элементов И и входу пятого элемента

НЕ, выход которого соединен с вторым входом шестого элемента И, третий вход которого подключен к выходу первого дешифратора нуля, выход второго блока деления в поле Галуа соединен с входом сумматора квадратов элементов в поле Галуа, выход которого подклю чен непосредственно и через третий элемент НЕ соответственно к вто-.