Декодер кодов Рида-Маллера первого порядка Советский патент 1989 года по МПК G06F17/14 H03M13/21 

llM-t)

2{т-Ы)

(Л

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

Јь

«Vj

4

00

сл

42

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

Регистр 6-(т+1)-разрядный.

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

Пусть в линию связи послан вектор длины 2 16 V (V „V п) ® ( x х V74) ®CV31V3i) ®(V41V47) (1, -1)® 0(1, D ®0, О ®(1, D (1, -1, 1,

To же, что я на 1-м этапе 2. . . .-2 .

О . . 2

2

2

4 -2

5

Q

В матрице указаны только ненулевые элементы. На остальных позициях находятся нули. Операцию умножения матрицы на кодовый вектор можно представить в виде нескольких операций сложения и вычитания (это значительно проще реализовать аппаратурно), что иллюстрирует граф-схема.

При выявлении номера позиции максимального элемента получают информационные символы, которые закодированы на передающей стороне и посланы в линию связи.

Максимальный элемент

О 2

4 6 О 2

i 1 -2

ЧБ ю

2

-2 -6 -2

32 О О

V

n

I

При прочтении справа налево получают номер позиции максимального элемента 0001. Знак максимального элемента указывает на последний (т+1)-й информационный символ

max

10

1

V

4-1

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

iv3s 1; v 0

i

0

5

0

2, Декодирование по усеченному быстрому преобразованию Уолша (УБШ1).

Сущность его заключается в том, что производятся над принятым вектором операции суммирования и вычитания в меньшем объеме. При этом на каждом этапе добавляется операция сравнения. Начиная с 2-го этапа, вычиспяют сумму модулей верхней и нижней половин и затем производят операции суммирования и вычитания только над векторами, входящими в половину, имеющую большую сумму по модулю. При этом 2-я половина векторов отбрасывается и в дальнейшем не принимает участия в вычислениях.

1

Ю б

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

При этом знак максимального элемента на последнем этапе определяет информационный символ.

Как видно из граф-схемы, уменьшается объем вычислений при декодироКак видно из граф-схемы, на пер- вьйс двух этапах декодирование осуществляется по БПУ. При этом после двух шагов определяют два информационных символа V п и Vla.

Для этого разбивают вектор на 2 m 2s 4 равные части, присваи.

5

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

Этот недостаток устраняется применением на первых этапах декодирования по БПУ, а на последних этапах - декодирования по УБПУ.

Суть его иллюстрируется граф-схемой.

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

На следующих этапах производят декодирование уже по УБПУ. Причем операции производят над векторами, входящими в блок, имеющий максимальную сумму элементов. И на каждом из последующих этапов находят остальные информационные символы V3z, V42 и V+ .

Декодер кодов Рида-Маллера первого порядка работает следующим образом.

Кодовый вектор длины 2m приходит из линии связи и записывается в буферный регистр 1, откуда элементы вектора, состоящие из 1 и -Т, подаются на вход блока 2.1, где группи-15 или разность.

руются по два и поступают на 2 сумматоров и 2 вычитателей, которые производят над этими элементами соответствующие операции. На выходе блока 2.j (j 1, ..., га-1) появляет- ся вектор длины 2т, элементы которого подаются на вход блока 2.(j+1). На выходе блока 2,(т-1) появляется векf) tn

-

элементов на

тор длины Z, элементы которого поступают группами по 2 р входы 2 т сумматоров, входящих в блок 3.1 суммирования, 2 т выходов которого подаются на 2 m входов блока 4.1 сравнения, при этом 1 выходов шифратора являются информационными и подаются на 1 первых входов регистра 6, при этом 2т выходов блока 4.1 сравнения (1 1, ..., 1) подаются на входы блока 5.1 ключей, состоящего из 2 т ключей для 1-го этапа. На другие входы блока 5.1 подаются выходы соответственно блока 2. На шход блока 2.(m-l+i) через блок 5.1 ключей записывается информация в виде

Ј

вектора длины 2 с выходов соответствующих сумматоров и вычитателей блока 2.(т-1). Элементы этого векто- 2 группируются по два и по- 2 сумматоров и 2 1

ра длины ступают на

вычитателей, которые производят с ни- ми соответствующие операции. Результаты суммирования блока 2.(m-l+i) подаются на вход первого сумматора блока 3.1. Результаты разности с блока 2.(m-l+i) подаются на вход третьего сумматора блока 3.1. В блоке 4.1 происходит сравнение сумм обоих сумматоров блока 3.1. При превышении порога в блоке 4.1, равного 2 , открывается соответствующий ключ бло.ка 5.1 ключей, пропуская на вход блока 2.(m-l+i+1) информацию сумматоров или вычитателей блока 2(m-l+i). При этом, в регистр 6 записывается 1

или -1 в зависимости от того, на каком из двух сумматоров блока 3.1 появилось большее по модулю значение. На вход блока 2.т через блок 5.1 ключей приходит вектор длины 2, компоненты которого подаются на входы сумматора и вычитателя блока 2.т. Выходы сумматора и вычитателя подаются на вход блока 4.(1+1), который, сравнивая результаты суммы и разности с порогом, равным 2 т , подает на т-й вход регистра 6 1 или -1 в зависимости от того, что больше, сумма

0

5

0

5

0

,. 0

Пбследний (т+1)-й информационный символ записывается в регистр 6 после анализа знака вектора, полученного на выходе блока 4.(1+1).

Пример. Пусть в линию связи послан вектор длины 2 16 (V1T Vfi )® ® (V Vn)® (V,,V3O ®(V4iV4)

(1, -О® (1, П® О, 1) ®(i, О

(1, -1, 1, -1, 1, -1, 1, -1, 1, -1,

1, -1, 1, 1, 1, -1), где символы V;4 (1 1, 4) и являются информационными.

На приемной стороне принимается вектор

Wo (-1, -1, 1, -1, 1, 1, 1, -1,

1,-1, -1, -1, 1, -1, 1, -1) с ошибками на 1, 6 и 11-й позициях.

Принятый вектор декодируется на первых двух этапах (tn-1 2) по БПУ, а на последних двух этапах - по усеченному БПУ.

1-й этап. На выходе блока 2.1 имеется вектор

Wn (-2, 0, 2, 0, 0, -2, О, О, О,

2,0, 2, 2, 0, 2, 2), который поступает на вход блока 2.2.

2-й этап. На выходе блока 2.2 по-. лучают вектор

Wi (WV

(4)

W ,

Д4

w1,;1) - (-2,

2, -2, 0, 2, 2, 2, 4, 2,- 2, 2, 0, -2, 2, 0), который поступает на вход блока 3.Т. На его выходе получают четыре суммы модулей

Г/1 W

fj«w

4

(1

i

W

(aii

8 1 5

W

UJl

n

/

X iw 4,

(6, 10, 6, 6), которые поаются на вход блока 4.1 сравнения, а выходе которого получают два ин

формационных символа V

и

и V

72

3-й этапо Выходным сигналом с блока 4.1 сравнения этапа через блок 5.1

ключей пропускается на вход блока 2.3

- / л

вектор W „, (2, 2, 2,4), на его выходе получают вектор W 3 (W (13, ..., W() (4, 6, 0, -2), которьй подается на вход блока 3.2, на выходе которого получают две суммы модулей

««

ной буферные регистры, первый - т-й блоки сложения-вычитания (2т - длин декодируемого кода), первый - 1-й блоки ключей (1 т), выходы которы соединены с входами соответственно (т-1+1) - т-го блоков сложения-вычи тания, выходы выходного буферного р

( /I, IL. JW ;|) (10, 2), гистра являются выходами декодера,

9

JQ отличающийся тем, что, целью повышения быстродействия и у рощения декодера, в него введены пе вый - 1-й блоки суммирования и первый - (1+1)-й блоки сравнения, вход

которые сравниваются в блоке 4.2 сравнения. На выходе блока 4.2 сравнения получают информационный сигнал V ,г 1, который записывается в регистр 6.

4-й этап. Выходным сигналом с блока 4.2 сравнения через блок 5.2 ключей пропускается на вход блока 2.4 следующий вектор W ,а (4, 6) (W(f, W1,). На выходе блока 2.4 получают вектор V 4 (10, 2), компоненты которого сравниваются в блоке 4.2 сравнения, и на аго выходе получают два информационных символа V -н 1 и V 4 1, которые записываются в регистр 6.

Предлагаемый декодер позволяет декодировать коды Рида-Маллера первого порядка с существенно меньшими аппаратурными затратами по сравнению с .устройствами на основе БПУ, так как реализация устройства на основе БПУ требует числа сумматоров, пропорционального т-2, а в предлагаемой схеме число сумматоров пропорционально (m-l-l)1. В то же время, как показало моделирование, уже при небольших ш-1 предлагаемый декодер обеспечивает помехоустойчивость, близкую к помехоустойчивости декодирования по максимуму правдоподобия. Формула изобретения

Декодер кодов Рида-Маллера первого порядка, содержащий входной и выходСоставитель О.Ревинский

Редактор А.Козориз

Техред Л.Олийнык

Заказ 1911/57Тираж 880Подписное

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

ной буферные регистры, первый - т-й блоки сложения-вычитания (2т - длина декодируемого кода), первый - 1-й блоки ключей (1 т), выходы которых соединены с входами соответственно (т-1+1) - т-го блоков сложения-вычитания, выходы выходного буферного регистра являются выходами декодера,

отличающийся тем, что, с целью повышения быстродействия и упрощения декодера, в него введены первый - 1-й блоки суммирования и первый - (1+1)-й блоки сравнения, входы

входного буферного регистра являются входами декодера, выходы входного буферного регистра соединены с входами первого блока сложения-вычитания, выходы каждого из первого - (т-1-1)-го

блоков сложения-вычитания подключены к входам последующего блока сложения- вычитания, выходы (т-1) - (т-1)-го блоков сложения-вычитания соединены с первыми входами соответственно первого - 1-го блоков ключей и первого - 1-го блоков суммирования, выходы которых подключены к входам одноименных блоков сравнения, первый - (т-1)-й выходы первого блока сравнения соединены с одноименными входами выходного буферного регистра, (m-l-fl)-e выходы первого блока сравнения соединены с вторыми входами первого блока ключей, выходы второго - 1-го блоков сравнения подключены к вторым входам одноименных блоков ключей и соответственно к (т-1)-му - (т-1)-му входам выходного буферного регистра, выходы т-го блока сложения- вычитания соединены с входами (1+1)- го блока сравнения, первый и второй выходы которого подключены к т-му и (т+1)-му входам выходного буферного регистра.

Корректор М.Пожо