Устройство декодирования бчх-кодов с частичным исправлением ошибок

 

Изобретение относится к вычислительной технике и технике связи. Устройство содержит входной блок 1, блок 3 вычисления расстояний и блок 4 вычисления синдромов. Благодаря введению блока 2 декодирования кода Рида-Маллера, блока 5 совпадений, элемента ИЛИ 6 и элемента И 7 взамен более сложного блока, выполняющего итеративную процедуру Берлекэмпа, обеспечивается более надежная работа устройства. 4 ил.

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

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

РЕСПУБЛИН (19) (11) (51) 4 Н 03 M 13/00

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

:В»

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

Il0 ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ П(НТ СССР

1 (21 ) 43 72805/24-24 (22) 01.02.88 (46) 15.11.89. Бюл. У 42 (71) Пермский сельскохозяйственный институт им. акад. Д.Н.Прянишникова (72) M.Ю.Житков, А.Н.Дмитриев, С.Л.Портной и С.Н.Лицын (53) 621.376.57(088.8) (56) Мак-Вильямс Ф.Дж., Слоэн Н,Дж,А.

Теория кодов, исправляющих ошибки, M.: Связь, 1979, с. 27.

Проблемы передачи информации.

1968, У 4, с. 20-25.

Блох Э.Л., Зяблов В.В. Обобщен.— . ные каскадные коды. — М. . Связь, 1976, с. 191, рис.5.6.

2 (54) УСТРОЙСТВО ДЕКОДИРОВАНИЯ БЧХКОДОВ С ЧАСТИЧНЬК ИСПРАВЛЕНИЕМ ОШИ-

БОК (57)Изобретение относится к вычислительной технике и технике связи. Устройство содержит входной блок 1, блок 3 вычисления расстояний и блок

4 вычисления синдромов. Благодаря введению блока 2 декодирования кода

Рида-Иаллера, блока 5 совпадений, элемента ИЛИ 6 и элемента И 7 взамен более сложного блока, выполняющего итеративную процедуру Берлекэмпа, .обеспечивается более надежная работа устройства. 4 ил.

1522413

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

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

На фиг.1 приведена блок-схема устройства; на фиг.2 — схема блока декодирования кода Рида-галлера; на фиг, 3 — схема блока вычисления расстояния, на фиг. 4 — схема блока вычисления синдрОмОв а

Устройство содержит входной блок

1, блок 2 декодирования кода РидаМаллера, блок 3 вычисления расстояний, блок 4 вычисления синдромов, блок 5 совпадений, элемент ИЛИ 6 и элемент И 7. На фиг.1 обозначены информационный выход 8 и выход 9 отказа от декодирования";

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

Блок 2 декодирования кода РидаМаллера (фиг.2) содержит кольцевой регистр 10 сдвига, группу 11 суммато- 30 ров по модулю два, элемент 12 задержки, мажоритарный элемент 13 и сумматор 14 по модулю два.

Блок 3 вычисления расстояний (фиг.3) содержит первый — третий ре35 гистры 15-17 сдвига, группу 18 сумматоров по модулю два, счетчик .19 импульсов,. компаратор 20 и элемент ..

21 И. На фиг.3 обозначены первый и второй входы 22 и 23 и первый и вто- 4 рой выходы 24 и 25. В состав регистра

17 входят элементы ИЛИ.

Блок 4 вычисления синдромов (фиг..4) содержит регистр 26 сдвига, вычислители 27 синдрома, элемент 28 задержки и группу 29 регистров сдвига. На фиг.4 обозначены первый и вторые выходы 30 и 31 блока. Вычислители 27 синдромов выполнены на регистрах сдвига, в цепи обратной связи

50 которых включен умножитель на элемент поля Галуа.

Блок 5 совпадений представляет собой элемент ИЛИ.

Функционирование устройства основано на следующих принципах.

Очевидно, если существует два кода

А (и, М„, da) и В (n, Мь, dz) длины и мощностей МА и Мь с кодовыми расстояниями d+ и d, причем A являет.ся ПОДХОДОМ В (т,е, а ) Е ) то бое слово, лежащее на расстоянии,не большем а

t8

2 от вектора кода А, алгоритмом декодирования кода В будет декодировано в слово, принадлежащее коду А. Пусть

К (r, m) обозначает код Рида-Маллера длины 2 r ro порядка, à R (r, m)— код К (г, ш) с одной вычеркнутой координатой.

Теорема. Код БЧХ длины 2 — 1 с. конструктивным расстоянием 6 =2 +

+ 3 является подкодом кода R (ш-З,m)

Доказательство. Рассмотрим циклический код К (ш-3,ш). Как известно

М

Ф ° э код К (m-3,ш) задается корнями вида

Ы, где .двоичное представление Б

5 имеет вес Хэмминга 1 или 2, S 2 -1.

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

2 + 1(i 1,...,I"m/2 ) и единицей.

Веса двоичных представителей чисел, лежащих в одном циклотомическом классн по:модулю 2 — 1, равны, поэтому

m все четные веса 2 лежат в классах с представителями вида 2 . +1, где i

1 ф ° ° ° 9Ш 1 ° НО (2 + 1) г (шоа. г -1)=г +1, откуда следует, что числа 2" + 1 и 2 + 1 лежат в одном циклотомическом

;классе. Таким образом, циклический код

R+(m-3,ш).задается корнями оР, где

$ = 2 +1, i=1,..., m/2j и S=0. По определению примитивный БЧХ-код с конструктивным расстоя пф-м «1=2 +

Ф 23

+ 3 задается корнями ЫУ, где ь1й1

1=1,2,...,2 - + 1, и так как корни, задающие БЧХ-код, содержат корни кода Рида-галлера, то утверждение теоремы верно, например БЧХ-код А. (63,2,11) является подходом кода

Рида-Маллера третьего порядка

В (63, 2,7).

Так же вкладываются в код R (ш-3, m) и БЧХ-коды с минимальным расстоянием, большим 2 + 3.

С 1 3

Несложно определяются и условия

Вложимости произвольных БЧХ кодов в коды Рида-Маллера.

Устройство функционирует следующим образом.

Пусть информация передается словами кода БЧХ А (2 -1, М, d 4» 2 +

Ю gm fa7

5 15224

+ 3) и требуется производить исправление до t (t <3) ошибок. Искаженное слово поступает из канала во входной блок 1, с выхода которого это слово подается на блок 3 вычисления

5 расстояний, где сравнивается со словом, получающимся в результате декодирования принятого вектора в коде

R (m-3,m) в блоке 2 декодирования I0

М. кода Рида-Маллера. В блоке 3 вычисляемое расстояние сравнивается с t и если оно больше, то на первый выход 24 выдается решение об отказе от . декодирования, в противном случае 15 слово, полученное на выходе блока

2, через второй выход 25 подается на вход блока 4 вычисления синдромов, в котором вычисляется синдром этого слова в коде А. Если произошло 20 менее t ошибок, то этот синдром равен нулю, что и определяется в блоке

5 совпадений, в противном случае с выхода элемента 6 ИЛИ получается сигнал отказа от декодирования, так 25 как с выхода блока 5 поступает единица. Если же этот сигнал равен нулю, декодированный словом, появляющимся на выходе 8, является слово, полученное на выходе блока 2 30 декодирования кода Рида-Малле— .ра.

l3 6

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

Устройство декодирования БЧХ-кодов с частичным исправлением ошибок, содержащее входной блок, вход кото» рого является входом устройства, а первый выход соединен с первым входом блока вычисления расстояний, и блок вычисления синдромов, о т л и ч а ю— щ е е с я тем, что, с целью повышения надежности функционирования, в устройство введены блок декодирова-. ния кода Рида-Маллера, блок совпадений, элемент И и элемент HJIH второй выход входного блока подключен к входу блока декодирования кода

РидаМаллера, выход которого соединен с вторым входом блока вычисления расстояний, первый и второй выходы которого подключены соответственно к первому входу элемента ИЛИ и входу блока вычисления синдромов, первый выход которого соединен с разрешающим входом элемента И, вторые входы блока вычисления синдромов подключены к соответствующим входам блока совпадений, выход которого соединен с запрещающим входом элемента И и вторым входом элемента ИЛИ, выходы которых являются соответствен- . но информационным выходом и выходом отказа от декодирования устройства.

1522413

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

Техред Л.Олийнык Корректор М.Васильева

Редактор Л.Веселовская

Заказ 6979/56 Тираж 884 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101