Декодер кодов боуза-чоудхури-хоквингема

 

Изобретение относится к вычислительной технике и связи. Его использование в системах передачи дискретной информации позволяет повысить быстродействие декодера . Декодер содержит блоки 1,2 вычисл ния элемента синдрома, узел 4 формирования многочлена локаторов ош бок, блок 6 формирования решений и блох 11 коррекции ошибок. Благодаря введению в декодер блок 3 вычисления синдрома, блока 5 деления, блока 7 умножения, блока 8 сложения и дешифраторов 9, 10 время исправления ошибок сокращается. 1 з.п. ф-лы, 3 ил.

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

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

РЕСПУБЛИК (я)5 Н 03 M 13/02

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР)

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

К АРТО РС КОМУ С В ИДЕТ ЕЛ Ь СТВУ (21) 4795553/24 (22) 26.02.90

° (46) 23.12.92, Бюл. % 47 (71) Ленинградский механический институт им, Маршала Советского Союза Устинова Д.Ф, (72) В.П.Лукоянов и О.Н.Музыченко (56) Авторское свидетельство СССР

М 1457166, кл. Н 03 M 13/02, 1987.

Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки. — М.:

Мир, 1979, с. 267-272, (54) ДЕКОДЕР КОДОВ БОУЗА-ЧОУДХУРИ" ХОКВИНГЕМА

5U„„1783627 А1 (57) Изобретение относится к вычислительной технике и связй. Его использование в системах передачи дискретной информации позволяет повысить быстродействие декдера. Декодер содержит блоки 1,2 вычисл-.- — ния элемента синдрома, узел 4 формирования многочлена локаторов ошибок, блок 6 формирования решений и блок

11 коррекции ошибок, Благодаря введению в декодер блок 3 вычисления синдрома, блока 5 деления, блока 7 умножения, блока 8 сложения и дешифраторов 9, 10 время исправления ошибок сокращается. 1 з.п. ф-лы, 3 ил.

1783627

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

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

На фиг. 1 показана структурная схема декодера; на фиг. 2 — схема блока деления в полях Галуа; на фиг. 3 — схема блока умножения в полях Галуа.

Декодер содержит первый блок 1 вычисления элемента синдрома $з, второй . блок 2 вычисления элемента синдрома Sj, третий блок 3 вычисления элемента синдрома $2, узел 4 формирования многочлена локаторов ошибок o(Z), блок 5 деления, блок

6 формирования решений, блок 7 умножения, блок 8 сложения, дешифраторы 9,10, блок 11 коррекции ошибок, входы 12, выходы 13.

Информационные входы 12 устройства соединены с входами блоков 1,2,3 вычисления элементов синдрома, выходы которых соединены с входами узла 4 формирования многочлена локаторов ошибок, соединенного выходами с входами делимого блока 5 деления, входы делителя которого соединены с выходами блока 3 вычисления элемента синдрома S2, а выходы — с входами блока

6 формирования решения, соединенного выходами с первой группой входов блока 7 . умножения, вторая группа входов которого соединена с выходами блока 2 вычисления элемента синдрома $1, а выходы — с входами дешифратора 10 и блока 8 сложения, соединенного второй группой входов с выходами блока 2 вычисления элемента синдрома з1, а выходами — с входами дешифратора 9, выходы которого соединены с второй группой входов блока 11 коррекции ошибок, соединенного первой группой входов с информационными входами 12 декодера, третьей группой входов — с выходами дешифратора 10, а выходами — с выходами 13 ,декодера.

Реализацию блоков и функционирование устройства рассмотрим для случае 15разрядного БЧХ-кода, порождаемого . полиномом.а + а+ 1 и имеющего проверочную матрицу

H 1- (1,а,аг,а,сг4,а"-,аб,а,а8, с 9 а10 а11 а12 а13 а14 ) ! ! ! вида

100010011010111

01 00 1 1 01 01 1 1 1 00

0001 00 1 1 01 01 1 1 1

При этом (1 2 4 6 8 10 12, 14!а 1аЗа5а7а9а11а13)

101 01 1 1 10001001

01 01 1 1 10001 001 1

000100110101111

Н2=

Нз=<1, а,,а а, а"2,1,а,а6, а, а ",1,а,а б,а,а " ) 100011000110001

000110001100011

001 0100101 001 01

011110111101111

H3=

Блоки 1,2 и 3 вычисления элементов

20 синдрома выполняют операции:

$3= H3 Х; $2 = Н1 Х; $2 = Нг Х; где Х вЂ” входное кодовое слово, и выполняются каждый в виде четырех сумматоров по

25 модулю ва еализ ю их нк и д,р у щ фу ци, 2 = Х1+ Х5+ XB+ Xg+ X11+ X13+ Х14+ Х15

2 з

1 = X2 + X5+ X6 + Х8+ X10 + X11 + X12 + X13

1 = X3 + Х7 + Х6 + Х9 + Х11 + X12 + X13 + Х14

1 = Х4+ Х7 + Х8+ Х10 + Х12 + Х14 + X13+ Х15

$1=

1

2 = Х1+ X3+ X5+ X6+ Х7+ X8+ Х12 + Х15 г

g X3+ X6+ Х7+Х9+ X11+ Х12+ X13+ Х14

S 2 = Хг+ X4+ X5+ Х6+ X7+ Х11+ Х15+ Х11 °

2 = Х4 + Х7+ Х8+ Х10 + Х12 + X 13 + X14 + Х15

35

3 = X1 + Х5+ Х6 + Х10 + Х11 + Х15 г з

3 = X4+ X5+ X9+ Х10+ Х14+ Х15

3 = ХЗ+ Х5+ Х8+ Х10+ Х13+ Х15

3 = Х2 + X3+ X4 + Х5 + Х7 + Х8 + Х9+Х10

+Х12 + Х13 + Х14 + Х15

S3=

Блок 14 деления выполняет операцию деления $3/$1 в полях Галуа 60 (2). Пусть S3- a, S1 = аР, где f, р б (0,1„....14), а $з, S1—

45 элементы матрицы Н1, то S3/$1=

"аР х aÐ = а(Р . Блок14 выполняетр +1) вод15 ся, как показано на фиг. 2. Он содержит дешифраторы 16,17, группу из 15И5 элемен50 тов И, 18 и шифратор 19 из четырех элементов ИЛИ. На входах элементов И 18 дешифрируются все сочетания значений S3 и S1, а выход каждого из них соединен с входами элементов ИЛИ шифратора 19 с номерами. равными номе рам един ич8 ых разрядов в представлении $з/$1.

Блок умножения выполняется как псказано на фиг. 3, Он содержит дешифраторы

20,21,25, сумматор по модулю К 24, ыифраторы 22, 23 и 26. Шифраторы 22 и 23 выпол1783627

m-В u-=

0001

0011

ОООО

B min= няются в виде четырех элементов ИЛИ и по единичному сигналу на выходе дешифратора 20 и 21 соответственно. соответствующему входному коду а,а jno матрице Н1 формируют выходной код числа Ц. Сумматор по модулю К; в данном случае К = 15, формирует код числа(1+!){поб15 = г, а дешифратор 25 и шифратор 26 формируют кодовую комбинацию, соответствующую {Р матрицы Н1.

Блок 7 умножения выполняется аналогичн-.1 изображенному на фиг. 3.

Блоки сложения 8 и 15 выполняются в виде четырех сумматоров по модулю два, осуществляющих поразрядное суммирование входных кодов.

Блок 5 деления выполняется аналогично изображенному на фиг. 2.

Блок 6 формирования решения осуществляв-. операцию умножения ВП1{п Х, где для полинома Q + а + 1 а X — входной код, равный Х = (х х х х ). В соответствии с этим блок реализуется в виде аз= хг+х1 а =х г 0

1- =х1+ „0

{z0-=0

Блок 11 коррекции ошибок выполняется ввиде,и сумматоров по модулю два.

Для других БЧХ-кодов конкретная схемная реализация блоков определяется матрицами Н>, Нг, Нз в соответствии с описанным выше порядком.

Работа декодера происходит следующим образом.

Пусть на входы декодера подана кодовая комбинация, имеющая ошибки в третьем (х ) и в десятом (х9) разрядах. При этом на выходах блоков 1,2,3 вычисления элементов синдрома формируются сигналы $з = Нз" х Х = (а ) + (а 9)з = а + а "г = 1100 + 1111

=0011 = а, $г= Нг Х=(а) +(а) =а" + а =0011+

+ 1000 = 1011 = а

S = Н Х = а г+ а = 0100+ 1010 = 1110.

11

По сигналам $з, S< узел 4 формирования многочлена локаторов ошибок формирует сигнал () =,$з/$) +- $г - а а 11, (z 7 а а+

+ат а

На выходе блока деления вырабатыва. ется сигнал а 7=a =0011 который поступает на входы блока 6 формирования решения, производящего операцию

0110 0

0001 О

0011 1 =1100= а6

0000 1 игнал с выхода блока 6 поступает на вход блока 7 умножения, при этом на его

10 выходе будет код

Z - m $1 = а 6 а " - а { = аг = 0100, являющийся первым корнем, на основе ко торого дешифратор 10 формирует единичный сигнал на третьем выходе, поступающий

"5 на вход третьего сумматора по модулю два блока 11 коррекции ошибок, на первый вход которого поступает сигнал третьего разряда входного кода х, при этом корректируется ошибка в данном разряде. Кроме того, сигнал с выхода блока умножения 7 поступае на входы блока сложения 8, на выходах которого формируется код

V=Z+S<=а +(а +а )= а

1010. который поступает на входы дешифратора

9, на десятом выходе которого при этом формируется единичный сигнал, поступающий на вход десятого сумматора по модулю

30 два, на первый вход которого поступает сигнал х десятого разряда входного кода, при этом корректируется ошибка в данном разряде, Таким образом обе ошибки исправлены.

Исправление ошибок осуществляется в результате решения уравнения х + $1х+($1+ — ) = О, г г $з

S1 путем замены переменных

x=yS1 при этом (y + $з)

45 $1(у +у+ " )=О, S) Решение уравнения у + у+ U = О осущеI ствляется с использованием матрицы Bmln

5р Первый корень уравнения равен (y+ $з)

X1=(Bmln ()) S)

S) а второй

55 Хг= $>+X

Таким образом в предложенном устройстве декодирование осуществляется комбинационным устройством, что обеспечивает повышение быстродействия, 1783627

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

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

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

16 2,Декодерпоп.1,отличающийся тем. что узел формирования многочле: а локаторов ошибок содержит блок сложения м блок деления, первые и вторые входы которого являются одноименными входами уз20 ла, выходы блока деления подключены к первык; входам блока сложения, вторые входы и выходы которого являются соответственно третьими входами и выходами узла.

Редактор Г.Бельская

Составитель О.Музыченко

Техред M.Moðãåí Tàë Корректор Л.Лукач

Заказ 4522 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", r. Óæioðoä, ул. Гагарина. 101