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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

„„$0„„1474 4 (1 Д.Ы Ж (»

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

К A8TOPCHOMV СВИДЕТЕЛЬСТВУ

2 (m-(t) Я(т-2

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

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

ПРИ ГКНТ СССР (21) 4278236/24-24 (22) 06.07.87 (46) 23.04.89, Бюл. Р 15 (71) Пермский политехнический институт (72) А.Е.Ашихмин, А.Н.Дмитриев, С.Н.Лицын и С.Л,Портной (53) 621. 394 . 142: 68 1.325(088.8) (56) Известия вузов. Сер. Радиоэлектроника. 1985, т. 28, В 1, с. 31-36.

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

1983, т. 19, Р 2, с. 3-7.

Мак-Вильямс

Теория кодов, исправляющих ошибки.

М.: Связь, 1979, с. 408-411. (54) ДЕКОДЕР КОДОВ РИДА-Г1АЛЛЕРА ПЕРВОГО ПОРЯДКА (57) Изобретение относится к вычислительной технике и технике связи.

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

Уалша (БПУ), а на последних — по усеченному БПУ. 1 ил.

1474854

1 1

1 1

1 1

1. 1

1 1

1 1

1 1

1 1

-1 — 1

1 — 1

1

1 — 1

-1

-1 — 1

-1

-1 — 1 (степень) 1-1

1-1

1-1

1-1

1-1

1-1

1-1

1 — 1

v viz

То же, на 1-м

-1 что и этапе .-г . о о о о о о о

2. . . .-2 . . . 4 о

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

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

Декодер содержит входной буферный регистр 1, блоки 2 сложения-вычита-, ния, блоки 3 суммирования, блоки 4 сравнения, блоки 5 ключей и выходной буферный регистр 6.

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

Каждый из блоков 2.1-2. (m-1) .сложения-вычитания выполнен на 2 " сумматорах и 2 " вычитателях (те же сумматоры с инвертированными сигналами на вторых входах). Каждый из бло- 20 ков 2.(m-1+1)-2.m сложения-вычитания содержит соответственно по 2 — 2 о сумматоров и вычитателей.

Блок 3.1 суммирования представляет собой набор из 2 сумматоров на 25 т-е

2 Е входов каждый. Блок 3.1 содержит два сумматора на ? входов каждый.

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

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

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

Пусть в линию связи послан вектор длины 2 =. 16 = 9 = (V„.,V, )Ю(Vг„х х V22) ®(V„V „) e(V4„V 4,) = (1, -1)e

®(1, 1) ®(1, 1) ®(1, 1) = (1, -1, 1, 1 ф 1 1, 1, 1, 1, 1, 1, 1 у

-1, 1, -1), где символы V 2 (i — 1, 4) и V, являются информационными, а (Р— знак кронекерового умножения. На приемной стороне принимается вектор Я4 = (-1, — 1, 1, — 1, 1, 1, 1 ф 1 э 1 9 1 ф 1 ф 1 ф 1 1 1 1 1 ) с ошибками на 1, 6 и 11-й позициях.

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

Сущность его состоит в том, что принятый вектор умножается ш раз на матрицу размерностью 2 х 2

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

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

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

1474854

О

0

-2

+2 о -2 г

2 г 0

1 1 1

-2 . 0 ° °

Со знаком мнну — 1

-1 22, У

П и прочтении р и справа налево полуP ксимального элее позиции мак а1 мента указывае т на последний символ информационный си

max = 10

1 7а, 25 новременным в вычи ю 1 ра с одно

"з

Х Зз 41 бок.

V2, v -1 .12

0 - б(10

1О> б

«10)б

0 ом выполняя над пр п иняТаким образом, вь ования и ом операции суммирова и следовательвычитания в объеме и по

r аф cxeMe1 p . 30 п озанной на гр он ь и ование прин водят декодиров испра влением оши1> + зl

О

О ание по усечен н" -у декодирование „ -БПу) . еобразованию уо бысTpому о заключае ается В ТОЬ1 сущность его вектося над принят™ ве производятся ирования и вычитания ром операции сумми

П и этом на каждом в меньшем объеме. р я сравнения. ляется операция этапе добавл

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

П и этом с по модулю, р большую сумму брасывается на векторов от

2-я половина т участия ивдал альнейшем не р п инимает слениях.

V

Ч„= 1 ч„= 1 vs%- =-1 г

=+6-0

+10

° °

10> 2

° ° ° ° ° ° °

-2

0 ... -2

2 ... +2

= +6-10

0 ... 2

2 ... 0

2 ... -2

0 ... -2

= +6 11

2 ... +2

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

Как видно из граф-схемы, на перI выХ двух этапах декодирование осуществляется по БПУ. При этом после двух шагов определяют два информационных символа 7,, и 7

Рря этого разбивают вектор на

2 = 2 = 4 равные части, присваи5 1474854 6

После каждого этапа есть возмож- вании принятого вектора по сравнению ность получать по одному информацион- с БПУ. В то же время декодирование ному символу. При анализе суммы мо- по УБПУ обладает невысокой корректидулей верхней и нижней половин после рующей способностью, связанной с тем, каждого i этапа однозначно определя- что она декодирует в пределах кодо5 ют Ч; информационный символ. При вого расстояния, не достигая коррекэтом, если сумма модулей максимальна тирующей способности декодера по БПУ. в верхней половине, Ч = 1, если в нижней половине сумма модулей макси- 10 Этот недостаток устраняется примемальна, то V; = -1 ° При этом rrozoaH нением на первых этапах декодирована с меньшей суммой отбрасывается и ния по БПУ, а на последних этапах— не принимает участие в дальнейших декодирования по УБПУ. вычислениях.

При »ом знак максимального эле- 1r 3. Декодирование на первых н-1. мента на последнем этапе определяет (m-1 =- 2) этапах по БПУ а на послед9

V< информационный символ. них этапах по УБПУ.

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

1474854

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

5 сумму элементов. И на каждом из последующих этапов находят остальные информационные символы V V u V

3г 6 Ф

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

Кодовый вектор длины 2 приходит из линии связи и записывается в буферный регистр 1, откуда элементы вектора, состоящие из " 1 и "-1", подаются на вход блока 2.1, где группи- 15 руются по два и поступают на 2 сумматоров и 2 " вычитателей, которые производят над этими элементами соответствующие операции. На выходе блока 2.j (j = 1, ..., m 1) появляет- 20

ITl ся вектор длины 2, элементы которого подаются на вход блока 2.(j +1).. Ha выходе блока 2.(m — 1) появляется вектор длины 2, элементы которого поступают группами по 2 элементов на" 25 в-е входы 2 сумматоров, входящих в блок

rn-I

3 ° 1 суммирования, 2 выходов кото-с рого подаются на 2 входов блока

4.1 сравнения, при этом 1 выходов шифратора являются информационными и 30 подаются на 1 первых входов регистра 6, при этом 2 выходов блока 4,i

, е сравнения (i = 1, ..., 1) подаются на . входы блока 5,i ключей, состоящего (Pw„ J з 2 ключей для i — ro этапа.

35 а другие входы блока 5.i подаются выходы соответственно блока 2. На вход блока 2.(тп-1+i) через блок 5.i ключей записывается информация в виде с вектора длины 2 с выходов соответствующих сумматоров и вычитателей блока 2.(m-1). Элементы этого векто1 ра длины 2 группируются по два и поступают на 2 С " сумматоров и 2 С вычитателей, которые производят с ни45 ми соответствующие операции. Результаты суммирования блока 2. (m-1+i) подаются на вход первого сумматора блока З.i, Результаты разности с блока

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

5.i ключей, пропуская на вход блока

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

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

tn-1 порогом, равным 2, подает на m-й вход регистра 6 "1" или "-1" в зависимости от того, что больше, сумма или разность °

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

Пример. Пусть в линию связи послан вектор длины 2 = 16 (Vll Vi )©

О (Чс1 Ч.с2) З (Чя Ч31) а(Ч41Ч41)

= (1, -1) а (1, 1) Е (1, 1) ®(1, 1) = (1, -1, 1, -1, 1, -1, 1, -1, 1,.-1, i, — 1, 1, -1 1, -1), где символы

V; (i = 1, 4) и V + являются информационными.

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

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

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

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

N„ = (2, О, 2, О, О, -2, О, О, О, 2, О, 2, 2, О, 2, 2), который поступает на вход блока 2.2.

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

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

8 f1 те - (2 Iw ."1, Е 1N ."1, Е i W,- g

С« l=5 i-9

l6

Е I N; I = (6, 10, 6, 6)., которые по» даются на вход блока 4.1 сравнения, на выходе которого получают два информационных символа V = -1 и Ч q =

1. Эти символы записываются в регистр 6 °

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

1474854

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

Техред Л. Олийнык Корректор M.Ïoæo

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

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

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

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

Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина, 101 ключей пропускается на вход блока 2.3 (ц вектор И = (2, 2, 2, 4), на его выходе получают вектор W = (W

W ) = (4, 6, О, -2), который подается на вход блока 3 ° 2, на выходе которого получают две суммы модулей

Wg = (QIW,1, с tW, l) = (10, 2), в Я

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

V, = 1, который записывается в регистр 6.

4- и этап. Выходным сигналом с блока 4.2 сравнения через блок 5.2 ключей пропускается на вход блока 2.4 следующий вектор W = (4, 6) — (sl — (,, W ) . Ha выходе блока 2. 4 олучают вектор 9 < = (10, -2), компоненты которого сравниваются в блоке

4.2 сравнения, и на его выходе получают два информационных символа V „ =

1 и Ч, = 1, которые записываются. в регистр 6.

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

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

Декодер кодов Рида-Маллера первого порядка, содержащий входной и выходной буферные регистры, первый — m-й блоки сложения-вычитания (2 — длина декодируемого кода), первый — 1-й блоки ключей (1 < m), выходы которых соединены с входами соответственно (m-1+1) — m-го блоков сложения-вычитания, выходы выходного буферного регистра являются выходами декодера, отличающийся тем, что, с целью повьппения быстродействия и упрощения декодера, в него введены первый — 1-й блоки суммирования и первый — (1+1)-й блоки сравнения, входы входного буферного регистра являются входами декодера, выходы входного буферного регистра соединены с входами первого блока сложения-вычитания, выходы каждого из первого — (m-1-1)-го блоков сложения-вычитания подключены к входам последующего блока сложениявычитания, выходы (m-1) — (m-1)-ro блоков сложения-вычитания соединены с первыми входами соответственно первого — 1-ro блоков ключей и первого—

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