Декодер кодов Боуза-Чоудхури-Хоквингема Советский патент 1992 года по МПК H03M13/02 

VI 00

СА) О

ю

V3

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

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

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

Декодер содержит первый блок 1 вычисления элемента синдрома 5з, второй блок 2 вычисления элемента синдрома Si, третий блок 3 вычисления элемента синдрома S2, узел 4 формирования многочлена ло- каторов ошибок cr(Z), блок 5 деления, блок б формирования решений, блок 7 умножения, блок 8 сложения, дешифраторы 9,10, блок 11 коррекции ошибок, входы 12, выходы 13.

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

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

Hi-CW oV aV, o,a1VV2A14)

ч

вида

100010011010111 010011010111100 001001101011110 000100110101111

При этом

а

14,

Н2

(1 ,«2, а4 а6, а8, а1, а3,а 5, а ,а9а11,а

а10, а 13)

10101111 000 1 001 001001101011110 0101111000 10011 000100110101111

Нз (1.«3. , 9, а12,,в3,о, а9, а 1Xl,«3.a ё,а 9,а 12)

1 00011000110001 0001 1 0001 10001 1 001010010100101 011110111101111

Блоки 1,2 и 3 вычисления элементов синдрома выполняют операции:

S3 H3X;S2 HiX;S2 H2X; где X - входное кодовое слово, и выполняются каждый в виде четырех сумматоров по модулю два, реализующих функции;

512 Х1 + Х5 + Х8 + Х9 + Х11 + Х13 + Х14 4 Х15 5 + Х5 + Х6 + Х8 + ХЮ + Х11 +Х12 + Х13 S, 1 ХЗ + X + Х6 + Х9 + ХЦ + Х12 + Х13 + Х14 1 Х4 + Х7 + Х8 + ХЮ + Х12 + Х14 + Х13 + Х15

Si

ls U

X1 -f- X3 + X5 4- X6 + X7 + X8 + X12 + X15 X3 + X6 + X7 + X9 + X11 +X12 + X13+ X14

S 2 X2 + X4 + X5 + X6 + X + X11 + X15 + ХЦ S 2 X4 + X7 + X8 + X10 + X12 + X13 + X14 + X15

XI + X5 + X6 + ХЮ + X11 + X15

S3 X4 + X5 + X9 + ХЮ + X14 + X15

S 3 X3 + X5 + X8 + ХЮ + X13 + X15

S 3 X2 + X3 + X4 + X5 + X7 + X8 + X9+X10

. +X12 + X13 + ХЦ + Х15

Блок 14 деления выполняет операцию деления Зз/Si в полях Галуа GF(2). Пусть 5з

- (Ј, Si cf, где f, р 6 {0,114}, a S3, Si элементы матрицы Hi, то 5з/5г «оР х of or(p+t) mod15. Блок 14 выполняется, как показано на фиг. 2. Он содержит дешифраторы 16,17, группу из 15x15 элементов И 18 и шифратор 19 из четырех элементов ИЛИ. На входах элементов И 18 дешифрируются все сочетания значений Зз и Si, а выход каждого из них соединен с входами элементов ИЛИ шифратора 1У с номерами, равными номерам единичных разрядов в представлении Ss/Si.

Блок умножения выполняется как показано на фиг. 3. Он содержит дешифраторы 20,21,25, сумматор по модулю К 24, шифраторы 22, 23 и 26. Шифраторы 22 и 23 выполняются в виде четырех элементов ИЛИ и по единичному сигналу на выходе дешифратора 20 и 21 соответственно, соответствующему входному коду по матрице Hi формируют выходной код числа l,j. Сумматор по модулю К; в данном случае К 15, формирует код числа (i+j)mod 15 t а дешифратор 25 и шифратор 26 формируют кодовую комбинацию, соответствующую с матрицы Hi.

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

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

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

Блок 6 формирования решения осуществляет операцию умножения Bmin X, где для полинома а4 + а + 1 0110 0001

Bmin 0011 0000

a X - входной код, равный X

( х3 х2 х1

х°). В соответствии с этим блок реализуется в виде

aj x2 + x1 «2 х° aW + x°

а° 0

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

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

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

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

52 Н2Х (а2)2+(агэ)2 а4 + + + аг

Si HiX a2 + a 9 0100 + 1010 1110 а

и

По сигналам 5з, Si узел 4 формирования многочлена локаторов ошибок формирует сигнал

a(Z) S3/Si + S2- a 7 а 8+ + «7 а11.

На выходе блока деления вырабатывается сигнал

U cr(Z)/S2 cr11/«7 a 4 €011.

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

0110 О

000 1 О m BminU 0011 1 1100 о6.

0000 1

0

5

0

5

0

5

0

Сигнал с

выхода блока 6 поступает на

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

Z m a11 а17 G 0100, являющийся первым корнем, на основе ко торого дешифратор 10 формирует единичный сигнал на третьем выходе, поступающий на вход третьего сумматора по модулю два блока 11 коррекции ошибок, на первый вход которого поступает сигнал третьего разряда входного кода х2, при этом корректируется ошибка в данном разряде. Кроме того, сигнал с выхода блока умножения 7 поступает на входы блока сложения 8, на выходах которого формируется код

Z + Si

а2 + (

а + а у) а

V

1010.

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

Таким образом обе ошибки исправлены.

Исправление ошибок осуществляется в результате решения уравнения

x2 + Six + (S2i+ |3-) 0, oi

путем замены переменных x ySi при этом

S2i(y2 + у +

Ф+1)

S

Si)-о.

Решение уравнения у2 + у + U 0 осуществляется с использованием матрицы Bmin Первый корень уравнения равен

(SUf)

Xi {Bmln n - }Si

SI а второй

X2 Sl + Xi.

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

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

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

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

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

Ьии. 8,

I

f«

/4 I1

.3