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

 

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

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

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

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

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

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

ПРИ ГКНТ СССР n

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4848840/24 (22) 09.07.90 (46) 15.11,92. Бюл. ¹ 42 (71) Пермский сельскохозяйственный институт им, акад, Д. Н, Прянишникова (72) А. Е, Ашихмин, С. Н, Лицын и С, Л.flopтной (56) Проблемы передачи информации, 1983, т. 19, вып. 2, с. 3 — 7.

Авторское свидетельство СССР

¹ 1568251, кл. Н 03 M 13/00, 1988. (54) ДЕКОДЕР КОДА PИДА-МАЛЛЕPA ПЕPВОГО ПОРЯДКА ПО МАКСИМУМУ ПРАВДОПОДОБИЯ

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

Известно устройство декодирования кодов Рида-Маллера первого порядка длины

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

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

Известно устройство декодирования кодов Рида-Маллера первого порядка по максимуму правдоподобия, содержащее буферный регистр, (m-1) блоков суммирования и вычитания блок попарного суммирования модулей, блок сравнения сумм пар модулей, блок ключей, блок суммирования и вычитания двух элементов, блок сравнения, . Ж 1775857 А1 (57) Изобретение относится к вычислительной технике, Его использование в аппаратуре передачи дискретной информации позволяет упростить декодер, содержащий входной буферный регистр 1, блоки сложения-вычитания, блок сравнения, блок ключей, блок сложения-вычитания двух элементов, нуль-орган и выходной буферный регистр.. Благодаря введению блоков вычисления. коэффициентов корреляции и блока определения номера максимального коэффициента корреляции в декодере сокращается число блоков сложения-вычитания. 6 ил. блок ключей m-го этапа, нуль-орган, регистр записи декодированного слова, Недостатком данного устройства является высокая сложность реализации.

Целью изобретения является упрощение устройства.

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

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

15

25

50

-1 1 1 -1

1 -1 1 -1

1 1 -1 -1

1 1 1 1

Н= ления номера максимального коэффициента корреляции, выходы (m-2)-го блока сложения-вычитания подключены ко входам первого -- (2" )-го блока вычисления коэффициентов корреляции, первые и вторые выходы которых соединены соответственно со входами блока сравнения и информационными входами блока ключей, выходы блока сложения-вычитания двух элементов и вторые выходы блока ключей соединены с первыми и вторыми входами блока определения номера максимального коэффициента корреляции, первый, второй и третий выходы которого подключены соответственно ко входу нуль-органа и входам первого и второго разрядов выходного буферного регистра, входы третьего — m-го разрядов которого подключены к выходам блока сравнения. Благодаря тому, что после (m — 2)ro этапа вводится блок вычисления коэффициентов корреляции, достигается зкономия аппаратурных затрат: требуемое число сум3 m2 маторов уменьшается на — х и = 3 х 2

4 и кроме того в прототипе используются

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

На фиг, 1 изображена структурная схема устройства декодирования. На фиг, 2 и 3 даны схемы подключения соответственно блока сложения-вычитания и блоков вычисления коэффициентов корреляции для случаяя m = 4, и =- 16. На фиг. 4 и 5 приведен ы схемы соответственно блока вычисления коэффициентов корреляции и блока определения номера коэффициента корреляции для того же случая, Декодер содержит: входной буферный регистр 1, блоки вычитания 2, блоки вычисления коэффициентов корреляции 3, блок сравнения 4, блок ключей 5, блок определения номера максимального коэффициента корреляции 6, блок сложения-вычитания двух элементов 7, нуль-орган 8, выходной буферный регистр 9. Буферный регистр 1 представляет собой 2 -разрядный регистр.

Блок сложения-вычитания 2 (фиг. 2) для

i-ro шага (i «< m 2) содержит 2" сумматоров

10 и вычитателей 11.

Елок вычисления коэффициентов корреляции 3 (фиг. 4), содержит элементы сравнения 12, элементы запрета И 14, сумматоры

15 и вычитатель 16. Блок сравнения 4 определяет номер максимального коэффициента корреляции.

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

Блок определения номера максимального коэффициента корреляции 6 содержит элемент сравнения 19 и элементы И 20 (фиг. 5).

Блок сложения-вычитания двух элементов 7 состоит (фиг. 5) из сумматора 17 и вычитателя 18.

Нуль-орган 8 представляет собой блок определения знака числа, Выходной буферный регистр 9 представляет собой (гп+1)-разрядный буферный регистр.

Идея упрощения декодера заключается в следующем. Первые m — 2 этапов декодирования совпадают с аналогичными этапами в прототипе: осуществляется попарное сложение и вычитание элементов а и ан-1, =

=1,3,5...,n — 1. Затем полученная последовательность длины и разбивается на группы по четыре элемента в каждой. В каждой из этих подгрупп вычисляется максимальный коэффициент корреляции, среди полученных коэффициентов корреляции находится максимальный по модулю коэффициент корреляции. двоичный номер группы, в которой он получен дает (3 — m) информационные символы. Так как по четырем элементам любой группы можно найти четыре коэффициента корреляции, то номер максимального из них, в группе пропущенной на дальнейшее декодирование, дает первый и второй информационные символы. Знак максимального по модулю коэффициента корреляции дает (m+1)-й информационный символ.

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

=(xQ, х, х2, x3) на транспонированную матрицу Адамара Н размерности 4 х4. Выберем в качестве этой матрицы матрицу:

Можно заметить, что любая строка этой матрицы не совпадает с вектором z = (1, 1, 1, -1) 1775857 лишь в одной позиции, причем, 1-я строка матрицы Н не совпадает с вектором Z в i-ой позиции, Таким образом, если мы вычислим величину у = х z = хо + х1 + х2 — хз, то величины 5

kp = х Hp =- -хО+ x1+ xZ — хЗ

k1 = х H1 = хо — x1 + xz — х3

k2 = х Н2 = xp+ x1 х2 х3

k3 = x H3 = xp + х1 + x2 + x3 где ki — i-й коэффициент корреляции, Hi — i-я 10 стока матриц Н; и величина у будут связаны соотношениями:

kp=y+2xp

k1= у+ 2 xl

k2 = y + 2 х2 15

k3= V+2 хз

Величина у является постоянной для постоянных хр, х1, х2, х3, следовательно; максимальный коэффициент корреляции возникнет там, где к величине у прибавля- 20 ется максимальный элемент xi или наоборот минимальный элемент xi, причем максимальный и минимальный элементы следует искать среди элементов хо, х1, х2, -x3, т.к, k3=

= у — 2 хз. Далее, если максимальный и 25 минимальный элементы имеют. номера Imax

И Imin, тО В ВЫражЕНИИ (1) дЛя kimax ia klmin элементы х п„„и х „берутся с разными знаками (в этом можно убедиться при непосредственной проверке матрицы Н), а два оставшихся элемента берутся со знаком плюс (все операции проводятся над элементами хо, х1, xz, -хз). Окончательно, если имеем элементы хо, х1, х2, хз, то для нахождения

kmax = ГлаХ (kP, k1, k2, З), НЕОбХОДИМО НайтИ

35 максимальный и минимальный элементы хо, Х1, Х2, -ХЗ И СООтВЕтСтВЕННО ИХ НОМЕРа lmax И

imin. ЗатЕМ ВЫЧИСЛИТЬ ВЕЛИЧИНУ у1 = Xmax— — Хп ; И ВЕЛИЧИНУ у2 = Х, — Xd С rimax, Imin, 6ф

С, Imax imln, И Kmax = I y1I +, yZi (ВО ВСЕХ ВЫЧИС40 лениях хз берется со знаком минус).

Поясним вышесказанное на примере.

Пусть декодируется вектор: w = (-1 -1 -1 1 1

1 -1 1 1 -1 -1 1 1 -1 -1 1), тогда граф декодирования будет иметь вид, показанный на фиг, 6. Рассмотрим нахождение максимальных коэффициентов корреляции в каждой группе:

1.хО = -2, х1 = 2, х2 = 2, -ХЗ = О. ИщЕм максимальные и минимальные элементы

Xmax=2, Xmln= 2, imin = 1, imax=Î, У1 Х1 хО = 4, p - х2 — x3 = — -2

Kmax = 4 + 2 = G

2. х о = -2, х1 = -2, xz = 2, -хз = О

Xmax = 2, Xmin = 2, Imax = 2, imin = О

y1 =xi — хо=4, у2=х2 — хз=-2

k max=4+2=6

3. хО =-2, xi=2, х2 =-2,-хЗ = О

Xmax = 2, xmin = 2, imax = 1, Imin =О у = xp — х1 = 4, ) 2 = х2 х3 — -2

k max=4+2 = 6

4. хо=2,х1=2, xz=-2,-хз=-4

Xmax = 2 Xmin = -4, imax = 0, imin = 3 у1 = хΠ— x1 = 6, yz = х2 + хЗ = 4, k » =10

Таким образом, k m», > k m», k m»,, 3 О 1

k max, и, следовательно, 3-й и 4-й информа-.

2 ционных символа это: 1,1. Далее необходимо определить номер максимального коэффициента в своей группе, т,е. какая строка матрицы Н при умножении х Н дала максимальный коэффициент корреляции.

Это может быть строка с номером О или 3, т.к. Imax = О, Imln = 3, При умножении на нулевую строку будем иметь величину -6+

+4 = -2. при умножении на третью строку величину 6+ 4 = 10, следовательно, максимальный коэффициент даст третья строка, т.е. первый и второй информационные символы: 1 1. Общее правило нахождения номера максимального коэффициента корреляции (т.е. строки матрицы Н дающей максимальный коэффициент корреляции) следующее, Допустим, мы вычислили kmax =

=!У11 + 1У21, Imax, Imin, ЗатЕМ ВЫЧИСЛЯЕМ величины д1= -yl+ yz, д2= у1+ у2, сравниваем д1и д2, еслид1 > д2, то номер строки дающей максимальный коэффициент корреляции — это Imfn, в противном случае это Imlni двоичное представление Imin или Imax дают первый и второй информационные символы, Работает декодер кода Рида-Маллера следующим образом. Кодовый вектор длины и = 2 приходит из линии связи и записывается в буферный регистр 1, оттуда элементы вектора подаются на вход блока сложениявычитания 2.1, Результаты суммирования

2 сумматоров 10 и 2 вычитателей 11

i-го блока сложения-вычитания 2.i (I = 1, m—

3) подаются на входы (i + 1}го блока сложения-вычитания 2.l + 1. Элементы с m-2 блоков сложения-вычитания подаются на блоки вычисления коэффициентов корреляции 3, по четыре последовательных элемента на каждый блок. В блоке 3 (фиг. 4) происходят следующие действия. Элемент хз инвертируется, затем сравниваются элементы хо и х1, х2 и (-хз). Элемент 12 сравнения имеет на

ВЫХОДЕ ЛОГИЧЕСКУЮ ЕДИНИЦУ, ЕСЛИ ХО < X1 (x2 < (x3)) и логический ноль, если xp > х1(х2

> (-хз)). Тогда посредством злементов 13, 14 на шины max1, maxz пропускаются большие из элементов хо и х1 (xz и (-хз)), а на шины

min1, п1 п2 соответственно меньшие элементы. Затем происходит сравнение максимального элемента среди эле ;ентов хо и х1 с максимальным элементом среди элементов х2 и (-хЗ), сравнение максимального элемента среди (хо и х1) с минимальным

1775857 элементом среди (xz и (-хз)). Таким образом. мы находим хг» и х, которые поступают по шинам max u min на вычитатель 16, на выходе которого получаем величину у . По шинам с и d на сумматор 15.1 поступают хс и xd, где Сдт», Imln, д с, Imax, !min. на выходе этого сумматора получаем величину у . Величины у, и у2поступаютна сумматор15.2 на выходе которого мы имеем величину kmax =

=lyll + !у . Величины >max поступают в блок сравнения 4, Одновременно с помощью элементов И 14 на шинах Im» и Imin формируются двоичные номера величин xmax u

xmIn Imax и !т1п. Затвм ) 1 и yZ !max u !min каждой группы из четырех элементов поступают на блок ключей 5. В блоке сравнения

4 происходит определение номера максимального коэффициента среди коэффициентов, пришедших со всех групп по четыре элемента каждая, Двоичный номер максимального коэффициента — это (3 — m)-e информационные символы, они подаются в выходной буферный регистр 9, кроме того они подаются в блок ключей 5 и определяют, из какой группы пропустить на дальнейшее декодирование элементы у1 у2, !тэх и Imln

Пропущенные элементы y>, yz подаются на блок сложения и вычитания двух элементов

7 (фиг, 5), в котором определяются величины

А = y1 + yZ и д2 =- p + у2. Величины д и д1 подаются на блок определения номера максимального коэффициента корреляции

6, туда же поступают элементы Imax u imtn c выходов блока ключей 5. В блоке определения номера максимального коэффициента корреляции 6 сравниваются величины !61 I и !дз!, если !д1! > !д !, то на первый и второй входы выходного буферного регистра 9 подается величина Imin, в противном случае величина lmax, кроме того большая по модулю из величин !01! и }дг! поступает на вход нуль-органа д, где определяется

40 знак этой величины; если знак плюс, то выход нуль-органа д равен нулю, в противном случае он равен единице. Символ с выхода нуль-органа 8 подается на (m + 1)-й вход выходного буферного регистра 9, Формула изобретения

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

1775857

Составитель Е, Ашихмин

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

Редактор

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

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

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

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