Декодер кодов рида-маллера порядка @

 

Изобретение относится к технике связи и вычислительной технике. Цель изобретения - упрощение декодера. Декодер содержит первый регистр 1, второй регистр 14, блок 8 декодирования кода нулевого порядка и узлы 2, 3 и 5 декодирования кода, в каждый из которых входят блок 15 алгебраического суммирования и блок 18 вычитания. В каждый из узлов 2, 3, 5 вводят блок 16 вычисления модулей и блок 17 ключей, а в каждый из узлов 4, 6 и 7 декодирования кода, аналогичных узлам 2, 3 и 5, вводят блоки 9 декодирования кода нулевого порядка, блоки 10 - 12 декодирования кода и блоки 13 перемножения. 2 з.п.ф-лы, 4 ил.

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

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

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

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

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

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ (0,2)

Фиг 1

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4467641/24 (22) 29.07.88 (46) 30.06.91. Бюл. М 24 (71) Пермский сельскохозяйственный институт им. акад. Д.Н.Прянишникова (72) А.Е.Ашихмин, А.Н.Дмитриев, С,Н,Лицын и С.Л.Портной (53) 621.394.142:681;325 (088.8)

- {56) Авторское свидетельство СССР

М 1474854, кл. И 03 М 13/00, 1987.

Сагалович Ю.Л. Кодирование состояний и надежность автоматов. М.; Связь, 1975, с. 88-91, рис. 4.7.1.

{54) ДЕКОДЕР КОДОВ РИДА-МАЛЛЕРА ПОРЯДКА р

„„Я „„1660176 А1 (52) Изобретение относится к технике связи и вычислительной технике. Цель изобретения — упрощение декодера, Декодер содержит первый регистр 1, второй регистр 14, блок 8 декодирования кода нулевого порядка и узлы 2, 3 и 5 декодирования кода, в каждый из которых входят блок 15 алгебраического суммирования и блок 18 вычитания. В каждый из узлов 2, 3, 5 вводят блок

16 вычисления модулей и блок 17 ключей, а в каждый из узлов 4, 6 и 7 декодирования кода, аналогичных узлам 2, 3 и 5. вводят блоки 9 декодирования кода нулевого порядка, блоки 10-12 декодирования кода и блоки 13 перемножения. 2 з.п. ф-лы, 4 ил.

1660176

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

На фиг,1 изображена блок-схема предлагаемого декодера кодов Рида-Маллера (PM) третьего порядка, на фиг,2 и 3 — выполнение соответственно блока декодирования кода m-го порядка длины 2 и блока декодирования нулевого порядка длины 2 ; на фиг.4 — пример конкретной реализации декодера кода PM первого порядка длины 2 . з

Декодер кода PM содержит первый регистр 1, узел 2 декодирования кода r-го порядка длины 2, узлы 3 — 5, 6.1 и 6.2, 7.17,3 декодирования кода (r — I)-ro порядка (I= Or — 1) длины 2 ) (j = 1,m — r — 1) блока 8 декодирования кода нулевого порядка длины 2, блоки 9 декодирования кода нулевого порядка длины 2 ", блоки 10 — 12 декодирования кода (r — I)-ro порядка длины

2", блоки 13 перемножения и второй регистр 14.

Каждый из узлов декодирования выполнен на блоке 15 алгебраического суммирования, блоке 16 вычисления модулей, блоке

17 ключей и блоке 18 вычитания.

На фиг.1 в скобках возле каждого узла

2 — 7 или блока 8 — 12 указаны порядок кода и показатель степени двойки, характеризующий длину кода.

Каждый иэ блоков 10 — 12 декодирования кода (r — I)-ro порядка длины 2" содержит r— - I определителей 19 знака.

Каждый из блоков 8 — 9 декодирования кода нулевого порядка содержит сумматор

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

Блоки 15 включают в себя сумматоры 23 и вычитатели 24, Блоки 16 выполнены на вычислителях 25 модуля (т.е, вычислители абсолютной величины без учета знака). Блоки 18 выполнены на вычитателях 26. Блоки

17 содержат ключи 27. Блоки 13 реализуются на перемножителях 28.

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

Пусть из линии связи получен искаженный вектор W êoäà РМ порядка r и длины 2, Тогда обработка вектора W ведется в следующей последовательности, 1. Если r = m, то декодируемые векторы

Y u Z совпадают с вектором (Мц }(И!1), $!Яп(И/2), ..., 3!9п(Ф/и)).

2. Если r = О, то определяется знак велии чины, Wi который совпадает со знаком

i =1 декодируемого символа Y,Z = (Y,Y, ..., Y).

3. Принятый вектор W представляется в виде матрицы W размерности 2 х 2, содержащей две строки, в первой — элементы с нечетными, во второй — с четными номера10 ми

4. Вычисляется матрица S = НгИ размерности 2 х 2, где Нг — матрица Адамара

1 размерности два: Нг =

5. Находится вектор S размерности 2 1, равный разности модулей элементов первой и второй строк матрицы S.

6. Вектор S декодируется декодером кода (r-1)-го порядка длины 2 . Результатом

-(1) является вектора У размерности K(r-1, r — 1

m-1) =- "" С; и Z 6. R(r 1,m-1) размерноi o сти 2

7. Иэ матрицы S выбираются элементы, ° образующие вектор W = (W1, W2...., Юг»)

r / / размерности 2, причем Wi равняется iму элементу первой строки S, если Zi ) = 1 и

i-му элементу второй строки, если Zl ) -1. .(1)

8. Вектор W декодируется декодером кода. r-го порядка длины 2 . Ред льтатом декодирования является вектор «У г"размер ности „ > Cm-1 и вектор Z ) Е R(r,m-1) раз35 мерности 2"

9. Результатом деко/ ирования вектора

W является вектор Y = (Y ), Y 2) и вектор Z =

40 22 @», Z2@» х Z2 -» ) размернасти.2

Поясняем это на примере кода РМ второго порядка длины 2 . Пусть в линию связи был послан вектор:

V = /1, — 1, — 1. 1, 1, 1, 1, 1, -1, 1, 1, — 1; 1, 1, 1, 45 1,1,1,1,1. 1,1;1,—.1,— 1,-1,— 1, 1,— 1,1, 1, -1/, На приемной стороне принимается вектор

W= /1, — 1, — 1, 1, -1, 1, i, 1, — 1, — 1, 1, -1, 1, 1.

1, 1, 1, 1, 1. 1, -1, 1, 1, — 1, 1, — 1, -1, — 1, — 1, 1, 50 1, -1/ с ошибками на 5, 10 и 25 позициях.

1 — — 11 — 1 11111 — 1 1 1 — 1 — 1 1

iW=(— 1 1 11 — 1 — 11111 1 — 1 — 1 — 1 1 — 1 ) з»0 0 02-202222 000-2 00

55 з=(г-г-20 020000-ггг 0-2ã )

S = (— 2, -2, --2, 2, 2, -2, 2, 2. 2, 2, — 2, — 2, — 2,2,-2,— 2), 1660176

2. Вектор S декодируется в узле декодирования кода PM (1, 4), где 1 — порядок кода, 2 — длина кода.

2.1

„„(1г), — 2 — 2 222 — 2 — 2 — 2 ) 5 — 2 2 — 222 — 2 2 — 2 — 4 0044 — 2 Π— 4

Π— 4400 Π— 4 О

-4, 4, 4, 4, -4, 4). (г.1 ) (Я = (4 -4, Ф )- (О, О, -8, О) 2,2. Вектор Я() декодируется в блоке декодирования кода PM (О, 3)

Y() = 1, Z() = (1, 1, 1, 1, 1; 1, 1, 1) 2.3. W =(— 4, О, О. 4,4, -4, 0,4) декодируется узлом декодирования кода PM (1, 3)

20 (04 — 4 — 4 )

2.4. Вектор Р 2) декодируется блоком декодирования кода РМ (О, 2) . 30

«(1,2) (1,2)

Y = — 1 Z )={ — 1,— 1,— 1,— 1)

2.5. Вектор W = (— 4, -4, 8, 4) декодируется в узле декодирования кода PM (1, 2) гг(1.з) (48 ) (1.з) 35

4, Вектор W = (4, 2, -2, 4, 4, -4, -2, -4)

40 декодируется узлом декодирования кода

PM (2,3) (1,3) 1 (1,3) (1 Ц

Я(.3) (8 8) 2 .4 — 4 — 4

У(1"=(-1,1). (1 1"=(-1, 1)

Результат (= (1, 1, 1, — 1, 1)

Z=Z 1 3)®Z 4)=(— 1,— 1,1,1)

Е = «Z(1 2) @Z = (— 1, 1, — 1, 1, 1, — 1, 1. — 1) Z = 2() ®2 = (— 1, — 1, 1, 1, — 1, — 1, 1, 1, 1, 50

1, — 1, — 1, 1, 1, — 1, — 1) . 3. Вектор W = (2, — 2, О. 2. О, 2, 2, 2, 2, 2, -2, 2, О, — 2, — 2, 2) декодируется узлом декодирования кода PM (2, 4) 2 — 68 2

S= {4 -4 -8 4) „,(з1) (4-8

55 (з1) (0 — 4

S() =(— 8 — 8). (гг) (.— 4 40 — 4 )

S()= (О, О -8, О) 2.6, Вектор W = (-8,12) декодируется блоком декодирования кода PM (1, 1) у 20022 -2 О -2

1, — 22222 2 — 2 2

О 2 244 0 — 2 О

4-2 — 200 — 4 2 -4

S= (-4, О, О. 4, 4, -4, О, -4), 3.1, Вектор S декодируется узлом декодирования кода РМ (1, 3) щ(г.1) (— 40 4 0 ) (г1) (— 4 40 — 4 — 4 — 48 4

3.2. Вектор S() декодируется блоком декодирования кода PM (0,2)

Y(1, Р") =(-1. -1, -1, -1) 3,3, Вектор Ю = (— 4, -4, 8, 4) декодируется узлом декодирования кода PM (1, 2) (гг) (— 48

5(u) (-8 12 )

Р,г) (8 8) 3.4. Вектор S() декодируется блоком декодирования кода PM (0,1)

Y(») = 1 « Р,г) (1 1)

3.5. Вектор М/ = (-8, 12) декодируется блоком декодирования кода РМ (1,1) « (2,3) = (1 1) (2,3) = (— 1

Z = (1 1) @(— 1, 1) = (— 1, — 1. 1, 1)

Z = Z+ ) ® Z = (— 1. 1, -1, 1, 1, — 1, 1, — 1)

Y() = (-1, 1, -1, 1) 4.1; Вектор Гдекодируется узлом декодирования кода PM (1,2) 1660176

4.2, Вектор Б декодируется блоком деко(3. 1) дирования кода PM (0,1)

Y(ç 1) = -1 Z(ç 1) = (-1 — 1)

4.3. Вектор Й/= (8. -12) декодируется блоком декодирования кода PM (1,1)

7(3,2) = (1 1) P (3,2) = (1 — 1)

Y(3) = (— 1, 1, — 1)

Z=Р1)®У(зл) =(1 -1 -1 1)

5, Вектор Я = (2, -6, 8, -6) декодируется блоком декодирования кода PM (2,2)

Ж = (-1, -1, 1, — 1) 2® = (1, — 1, 1, — 1)

Результат

Y = (1, — 1, 1, — 1, 1, — 1, 1, -1, 1, — 1, 1, 1, 1, — 1, 1, — 1), Работает декодер следующим образом.

Кодовый вектор длины 2 приходит иэ линии связи и записывается в регистр 1, откуда элементы вектора (зто могут быть и действительные числа) подаются на вход блока 15 узла 2. Результаты суммирования и.вычитания подаются на входы блока 16 вычисления модулей узла 2. Полученные модули поступают на блок 18 вычитания узла

2. Результаты вычитания модулей поступают на узел 3 декодирования кода (r — 1)-го порядка длины 2, Результаты декодирования подаются на входы регистра 14. Блок

7 кл ючей и ропус кает соответствующие числа с блока 15 на узел 4 декодирования кода порядка г длины 2 1 и т.д, Обозначаем С()(г,m), С(2)(г,m), С(3)(г,m)

С()(r,m) соответственно количество требуемых сумматоров или вычитателей, блоков определения модуля числа, блоков сравнения двух чисел, блоков смены знака на противоположный.

Тогда для декодера кода PM порядка r и длины 2 сложность можно определить системой рекуррентных соотношений:

С()(г,m) = 3 2 + С()(г-1,m-1)+

+ С(1) (г,m — 1), С((r m) = 2 + С(){r — 1 m — 1) +

+ С() {r,m — 1), 1

С(3)(г,m) = C@(r — 1, m — 1) + С(3) (гл -1), С((r,m)= 2 + С()(r-1, rn-1)+

+С()(г, m-1) с краевыми условиями

С((m,m) = О = 1,4;

C(1)(0m)=-2 1

С()(О,m) = О, С(З) (О m) = 1

5 С()(О,гп) = 0

Решением системы являются соотношения

С()(r,m) (3г+ 1) 2, 10 С()(г,п1) = r 2

С(3)() С m — 1

С()(г,т) = г 2, 15 из которых следует, что сложность декодера пропорциональна произведению длины кода на его порядок.

Таким образом, предлагаемый декодер

20 имеет сложность, пропорциональную пг)оизведению длины кода на его порядок, тогда как известный декодер имеет сложность, пропорциональную nlog"n, где n — длина кода.

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

1. Декодер кодов Рида-Маллера порядка r, содержащий первый регистр, вход ко30 торого является входом декодера, второй регистр, выход которого является выходом декодера, узлы декодирования кода (r I)-ro порядка (I = О,r — 1) длины 2 (2 — длина исходного кода), каждый из которых включа35 ет в себя блок алгебраического суммирования и блок вычитания, и блок декодирования кода нулевого порядка длины 2m, выход кото рого соединен с первым входом второго регистра, выходы первого регистра подклю40 чены к входам блока алгебраического суммирования узла декодирования кода r-ro порядка длины 2, выходы блока вычитания узла декодирования кода (r-k)-го порядка (k =- Оуr) длины 2 "соединены с входами

45 блока алгебраического суммирования узла декодирования кода (r — k-1)-ro порядка длины 2 ", выходы блока вючитания узла декодирования када первого порядка длины

2m " подключены к входам блока декоди50 рования кода нулевого порядка длины 2 ", отличающийся тем, что; с целью упрощения декодера, в каждый узел декодирования кода (r I)-ro порядка длины 2, введены блок ключей и блок. вычисления.

55 модулей. выходы которого соединены с входами блока вычитания, выходы блока алгебраического суммирования подключены к соответствующим информационным входам блока ключей и входам блока вычисле1660176

10 ния модулей этого узла декодирования, кроме того, в декодер введены блоки декодирования кода нулевого порядка двины

2m г б= 1,m — r — 1), блоки декодирования кода (r — 1)-го порядка. длины 2", блоки перемножения и узлы декодирования кода (г — 1)-го порядка длины 2 "(и - 1,т — г), выполненные аналогично узлам декодирования кода (r — !)-ro порядка длины 2 выходы — I блока вычитания h-го (h = 1,Cm r 1+1) узла декодирования кода первого порядка длины 2 " соединены с входами h ro блока декодирования кода нулевого порядка длины 2 "1, выходы блока ключей h-го узла деко1дирования кода (r — 1)-го порядка длины

2" подключены к входам h-го блока декодирования кода (r — I)-ro порядка длины 2, выходы блока ключей g-го (g = 1,С

i= 0m — 3: f = О,i; для i >г f >i — r) узла декодирования кода (r-i+f)-го порядка длины 2 соединены с входами блока алгебраического суммирования g-го yaha декодирования кода (r — i+f)-ro порядка длины 2m, выходы блока вычитания g-го узла декодирования кода (r — i+f)-го порядка длины 2m подключены к входам блока алгебf — I раического суммирования (g +,, С )-ro

1=О узла декодирования кода (г — — 1 о порядка 2, выходы первого — (Cm1 )-го (tX)-целая часть Х) блоков декодирования кода первого порядка длины 2 соединены с первыми входами одноименных блоков перемножения и соответствующими входами выходного регистра, выходы блоков декодирования кода нулевого порядка длины 21 соединены с (1+1)-ми входами одноименных блоков перемножения; управляющими входами блоков ключей одноименных узлов декодирования кода первого порядка длины

2 + и соответствующими входами второго регистра, управляющий вход блока ключей узла декодирования первого порядка длины

2 и (m-r)-й вход первого блока перемножения подключены к выходу блока декодирования кода нулевого порядка; длины 2 " 1, выходы первого

m — г+ К +1.

2 (С и, —, y к -1-1 )-ro блоков декодирова / ния (r — k — 1)-ro порядка длины 2 соединены с первыми входами соответственно

r — k — 1 61 (nl " М ЛГ= - () (1+,Я с -ьг-го — (C g а2 Cm г,)5

Ф

-ro блоков перемножения и соответствующими входами второго регистра. выходы

m — r-1

1-4 первого — (,». g.--. )-го блоков перемноj

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

J-1 первого — (Cr-3+j )-го узлов декодирования кода второго порядка длины 2, выходы m — r — 1. 1 m r ) 1 (1 +,"), Сг-3+j J-rо — (, Су-3+j )-го бло= 1 j — = 1 ков перемножения соединены с.управляющими входами блоков ключей соответственно первого — (Cm-3 " )-ro уз20 лов декоуи ро ва ни я кода второго порядка длины 2 и вторыми входами соответственно (1 + g Cm-b)-го — (С -3 " ) +

Ь=1

25 " f

+ g С„b)ro блоков перемножения.

b=1 выходы которых подключены соответственно к управляющим входам блоков ключей первого — (Сг-2+13 )-го узлов декодирования кода третьего порядка длины 2 и т.д., выходы последнего блока перемножения . соединены с управляющими входами блока ключей узла декодирования кода г-го порядка длины 2"+, выходы узла декодирования кода r-го порядка длины 2" подключены к соответствующим входам выходного регистра.

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

= опрЕделителя знака являются соответствен- но входами и выходом блока. к

1660176

1660176

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

Техред М,Моргентал Корректор С. Шевкун

Редактор Т.Горячева

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

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

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

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