Декодер кода БЧХ Советский патент 1989 года по МПК H03M13/51 

fmA.

йп

ч

(яи

Изобретение относится к вьмислч- тельной технике. Его использование в системах передачи цифровой информации позволяет повысить достоверность декодирования кодов ЁЧХ с кодовым расстоянием 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 ил.

0l/S.1

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

Коды Боуза-Чоудхури-Хоквингема (БЧХ) с з«)довь1м расстоянием d 6(Bg) строятся на основе кодов БЧХ с d 5(85) путем выбрасывания всех кодовых слов нечетного веса. Для этого порождающий многочлен g(Х) кода В домножается на (Х+1). Код В для любого m 7 4 имеет длину п 2т-1, число информационных символов,К . n-2m-lо

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

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

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

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

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

Сумматор 18 служит для вычисления трассы элемента в поле Галуа в со

т-

ii

„.- 11

ответствии с формулой Т..(р) f. р i

причем Т,.Ср) О или 1, и выполняется на программируемом ПЗУ.

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

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

Q

5

0

0

5

0

5

5

S, 0; S, 0; 83 0; i, 0; О - кодовое слово U;

So 1; S, 0; S 0; i, 0; 1 0 - однократная ошибка;

So 0; S,r 0; 83 0; , - 0; 6.37 0 двухкратная ошибка.

Область кодовых слов V четного веса кода В,, о.тличных от переданного кодового слова U, окруженных шарами радиуса 2 (соответствующие ошибки имеют кратность,, равную весу кодового сло-ва, или отличаются от него на ±1 и t2), Декодер никаким образом не может отличить эту область от области слова U. Область слова V соответствует необнаружимо- му неправильному декодированию в кодовое слово V, Комбинации синдромов при этом те же, что в области слова U.

Общей отличительной чертой областей и и V является соотношение е 3 So(mod2), где е - число импульсов исправления декодера - расстояние от ближ.айшего кодового слова.

Области кодовых слов Т нечетного веса кода Б (те кодовые слова, которые выбрасываются из кода при построении кода В)., окруженных шаром радиуса 2 (соответствующие ошибки имеют кратность, равную весу кодового слова и,, или отличаются от него на ±1 и 12). Комбинации синдромов в этой области те же, что в областях и и V, но с заменой S на S. При этом выполняется соотношение е So(mod2).

Это позволяет обнаружить весь класс неисправимьк ошибок - область Т.

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

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

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

В этих условиях квадратное уравнение 1 н- &, Z + (ii Z О не может иметь двух корней в поле Галуа GF() так как в противном случае эта ситуация сводилась бы к рассмотренным ранее. Известно,,что такое квадратное уравнение имеет два корня в поле GFCZ), если трассаT(). О при S, 0. Тогда для обнаружения ошибок.в данной области (между областями U и V) следует руководствоваться правилами:

S, 0; &, 0; .,,( VS) 1 или 8, 0; Sjj 0. .

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

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

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

Цифровой сигнал поступает также на вычислители 3, 8 и 15 синдромов S, 83 и Sg соответственно. Синдромы S , и S 5 сохраняются в блоках 4 и 16 соответственно. Вычислитедь 5 синдрома S определяет S как квадрат S,. Блок 9 деления в поле Галуа находит значение , а сумматор 11 в поле Галуа - вычисляет & S + Sj/S,.

Корректор 6 по вычисленным значениям 6, S и 61 вырабатывает импульсы коррекции ошибок, которые через элемент ЗАПРЕТ 7 поступаютна - сумматор 2. Элемент 7 запрещает кор-v рекцию ошибок, если обнаруживается неисправимая ошибка. Дешифратор 12 нуля проверяет равенство нулю коэффи1

Q

5

0

0

6 0

5 О

6

66

циента б, а элемент НЕ 19 инвертирует значение этой проверки.

Дешифратор 13 нуля проверяет равенство нулю синдрома S, а элемент НЕ 20 инвертирует значение этой проверки. Блок 10 деления в поле Галуа находит значение , а сумматор 18 квадратов элементов в поле Галуа . определяет T(). Элемент НЕ 21 инвертирует значение трассы. Блок 17 буфер1 ой памяти синдрома S, запоминает значение S,, дешифратор 14 прове-, ряет его равенство нулю, а элемент НЕ 22 инвертирует значение этой проверки. Элемент НЕ 23 инвертирует значение синдрома S.

Элемент И 24 вырабатывает сигнал обнаружения ситуации S, О и 0. Элемент И 26 формирует сигнал обнаружения неисправимой ошибки, когда S, 0; О и Tf,(cbi/S) i 0. Эле- . мент И 27 формирует сигнал для случая S, /0; 0; Т(, ) О и Зд 1. Элемент И 29- формирует сигнал обнаружения неисправимой ошибки, когда S 0; i О и 5 0. Элемент И 28 формируе-г сигнал обнаружения неисправимой ошибки, когда S О и БЗ /0. Элемент И 25 формирует сигч нал обнаружения неисправимой ошибки, когда S 0; S 3 О и 3„ 1. Элемент ИЛИ 30 формирует суммарный си.гнш обнаружения неисправимой ошибки.

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

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

Декодер кода БЧХ, содержащий буферный регистр-сдвига, вход которого объединен с входами вычислителя нулевого синдрома, вычислителя первого синдрома.и вычислителя третьего синдрома и является входом декодера, выход буферного регистра сдвига соединен с первым входом сумматора по модулю два, вьшод которого является информационным выходом декодера, выход вычислителя нулевого синдрома подключен к входу блока буферной па мяти нулевого синдрома, выход вычислителя первого синдрома соединен с входом делителя первого блока деления в поле Галуа и входом блока 6vфермой памяти первого синдрома, выход которого подключен к входу вычислителя второго синдрома и первому входу корректора ошибок, выход вычислителя третьего синдрома соединен с входом делимого .первого блока деления в поле Галуа, выход которого и выход вычислителя второго синдрома подключены к первому и второму входам сумматора в поле Галуа, выход которого соединен с входом первого дешифратора нуля и вторым входом корректора ошибок, выход которого соединен с разре10

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

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

которого подключен к второму входу сумматора по модулю два, выход первого дешифратора нуля через первьш элемент НЕ соединен с первым входом первого элемента И, отличающий с я тем, что, с целью повышения достоверности декодирования, в декодер введены сумматор квадратов элементов в поле Галуа, второй блок деления в поле Галуа, второй и третий дешифраторы нуля второй - пятый элементы НЕ, второй .- шестой элементы И, элемент РШИ к блок буферной памяти третьего синдрома, вход ко- , торого подключен к выходу вычислителя третьего синдрома,- входы делителя и делимого второго блока: деления в п поле Галуа подключены к выходам вычи сл;нтеля второго синдром;а и сумматора в поле Галуа, вход второго дешифратора нуля подключен к выходу блока буферной памяти первого синдРедактор А, Мотыль

Фиг.г

Составитель О, Ревйнский Техред М.Ходанич

Заказ 7563/58

Тираж 879

БИИИ11И Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

Корректор Л. Пилипенко

Подписное