Декодер кода нордстрома-робинсона

 

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

СОЮЗ СОВГтСКИХ социАлистических

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

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4859139/24 (22) 13.08.90 (46) 23.02,93. Бюл. N 7 (71) Пермский сельскохозяйственный институт им, акад. Д. Н. Прянишникова (72) А. Е. Ашихмин, С. Н, Лицын и С, Л. Портной (56) Кодирование и передача дискретных сообщений по каналам связи, — М,: Наука, 1976, с. 74-85.

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

N 1736008, кл. Н 03 М 13/00, 1989. (54) ДЕКОДЕР КОДА НОРДСТРОМА-РОБИНСОНА (57) Изобретение относится к вычислительной технике. Его использование в системах

ЫЛ,, 1797164 А1 передачи дискретной информации позволяет расширить область применения за счет декодирования в полунепрерывном канале и упростить декодер, который содержит блоки сложения-вычитания 1, блок сравнения 3, блок ключей 4, блок сложения и вычитания двух элементов 5, нуль-орган 7 и выходной буферный регистр 8, Благодаря введению 32 блоков вычисления коэффициентов корреляции

2 и блока определения номера максимального коэффициента корреляции 6 обеспечивается значительное сокращение числа сумматоров по сравнению с прототипом. 7 ил.

1797164

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

Известно устройство декодирования кода Нордстрома-Робинсона, основанное на разбиении кода на биортогональные подкоды с помощью преобразования Уолша.

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

Нордстрома-Робинсона не является оптимальнымм.

Устройство содержит восемь блоков декодирования биортогонального кода, основанных на быстром преобразовании Уолша, и схемы выбора максимального элемента, Наиболее близким к предлагаемому устройству является устройство декодирования кода Нордстрома-Робинсона, основанное на разбиении кода Нордстрома-Робинсона на смежные классы по коду

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

Это устройство содержит семь блоков сложения с образующим смежного класса, усеченные декодеры кода Рида-Маллера, блок ключей, блок сравнения, регистр записи декодированного слова.

Целью изобретения является декодер кода Нордстрома-Робинсона.

Эта цель достигается тем, что в декодер кода Нордстрома-Робинсона, содержащий первый-третий блоки сложения-вычитания, входы первого блока сложения-вычитания являются входами декодера, блок сравнения, выходы которого соединены с управляющими входами блока ключей и первым-пятым входами выходного буфер- ного регистра, выходы которого являются выходами декодера, блок сложения и вычитания двух элементов и нуль-орган, введены первый — 32-й блоки вычисления коэффициентов корреляции и блок определения номера максимального коэффициента корреляции, выходы первого блока сложения-вычитания подключены к соответствующим входам второго и третьего блоков сложения-вычитания, выходы которых соединены с соответствующими входами всех блоков вычисления коэффициентов корреляции, первые и вторь1е выходы которых подключены соответственно ко входам блока сравнения и информационным входам

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

2-7 — возможные реализации соответствующих блоков.

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

6, нуль-орган 7, выходной буферный регистр

8, Блоки сложения-вычитания 1 (фиг, 2, 3) содержат сумматоры 10 и вычитатели 11.

Блоки вычисления коэффициентов корреляции 2 (фиг, 4, 5) 6 состоят из четырех двухвходовых элементов сравнения 12, двух сумматоров 13, вычитателя 14, двадцати элементов И 15. Инвертирование соответствующего входного сигнала обеспечивается элементами НЕ 16.

Блок сравнения 3 выполнен на элементах И, ИЛИ, НЕ и выделяет номер максимального коэффициента корреляции, Блок сложения и вычитания двух элементов 5 (фиг, 7) состоит из сумматора 17 и вычитателя 18, Блок номера максимального коэффициента корреляции 6 состоит (фиг. 7) из элемента сравнения 19 и элементов И 20.

Нуль-орган 7 представляет собой устройство определения знака числа. Выходной буферный регистр 8 представляет собой восьми разрядный буферный регистр, Идея упрощения декодера заключается в следующем. Код Нордстрома-Робинсона разбивается на 8 смежных классов по коду

Рида-Маллера первого порядка. Таким образом достаточно продекодировать восемь раз принятый вектор, к которому прибавлен очередной образующий смежного класса, и выбирать среди полученных 128 коэффициентов корреляции (no 16 коэффициентов !797164 корреляции в каждом смежном классе) максимальный коэффициент, Двоичный номер этого коэффициента даст 8 информационных символов, Но на первых двух этапах декодирования кодов Рида-Маллера первого порядка в различных смежных классах имеется значительное количество одинаковых вычислений. Таким образом можно ограничиться шестнадцатью сложениями на первом этапе и 32-мя сложениями на втором этапе декодирования. После второго этапа имеем

128 элементов (по 16 элементов в восьми смех<ных классах). Разбиваем эти 128 элементов на группы по четыре последовательных элемента в каждой и определяем в каждой группе максимальный коэффициент корреляции. Для нахождения максимального коэффициента корреляции в группе из четырех элементов требуется три сумматора, т,е. всего потребуется 3 32=96 сумматоров, Если же производить вычисления в полном объеме, то потребуется 512 сумматоров. Таким образом количество сумматоров значительно уменьшается, Максимальный коэффициент корреляции в группе из четырех элементов находится следующим образом. Пусть мы имеем элементы Хо, Х1, Хг, Хз в одной из групп после второго этапа декодирования. Для вычисления коэффициентов корреляции необходимо умножить вектор x={xo, х1, хг, хз) на транспонированную матрицу Адамара H размерности 4х4, Выберем в качестве этой матрицы матрицу:

-1 1 1 -1

Н= 1-1 1-1

1 1 -1 -1

1111

Можно заметить, что любая строка этой матрицы не совпадает с вектором к=(1, 1, 1, -1) лишь в одной позиции, причем i-я строка матрицы Н не совпадает с вектором z o I-ой позиции. Таким образом, если мы имеем величину у=х г=х1+хг+хз+х4 и величины:

Мо=х Но=-Хо+Х1+Х2-Хз

k1=X Н1=ХΠ— Х1+Х2 — ХЗ

k2=x H2=Xo+X1 — Хг — Хз

1<з=х Н э=Хо+Х1+Хг+Хз, где ki это 1-й коэффициент корреляции (среди этих коэффициентов нам необходимо найти максимальный, Hi это 1-я строка матрицы Н). то величину у и ko, k1, k2, ka будут связаны соотношениями;

l

k1=y+2x1

k2=y+2x2

1 э=у+2(-хз) Величина у является постоянной для постоянных хо, х1, х2, хз, Следовательно максимальный по модулю коэффициент корреляции

" тах — mBX{Ikol, iki I, Ik21, Ik31) возникаеттам, где к величине у прибавляется л1аксимальный

5 ЭЛЕМЕНТ Xmax=maX(XO, Х1, Х2. -ХЗ) ИЛИ НаабОРОт минимальный элемент хп iп=-min(x, х, х, -x) (элемент хз берется со знаком л1инус, так как

k=y+2(-х)), Таким образом kmax может появиться при умножении вектора х либо на

10 строку которая не совпадает с вектором z в

ПОЗИЦИИ, ГДЕ РаСПОЛОжЕН ЭЛЕМЕНТ Xmax, ЛИбО приумножении на строку, которая не совпадает с BGKTopoM z в позиции, где расположен элемент Xmin. Далее если максимальный и

15 минимальный элементы имеют номера Imax и Imin, то в соответствующих выражениях дЛя КОЭффИцИЕНтОВ КОррЕЛяцИИ klmax, klmin

ЭЛЕМЕНТЫ Xmax È Xmln бЕРУтСЯ С РаЗНЫМИ ЗНаками {в этом можно убедиться при непос20 редственной проверке матрицы Н), а два оставшихся элемента берутся со знаком плюс {все операции производятся над элементами (xo, x1, хг, -хз). Окончательно, если мы имеем элементы xQ, xi, хг, -хг, то для

25 НаХО>КДЕНИЯ kmax НЕОбХОДИМО НайтИ Xmax u

Xmin а таКжЕ ИХ НОМЕРа Imax И Imin, ЗатЕМ

B ЫЧИСЛИТЬ ) =Xmax Xmin, Г г=Хс+Х<1, С

almaõ, lmin, d

l y1 +1Уг I.

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

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

-1 1 1-1 1 1 1 -1 -1 1). На выходе блока 1.1 будем иметь вектор W=(0 О 2 О О 2 О 0 2 -2 0, -2 2 0 2 2). На выходе блоков 1.2, 1.3 будем иметь вектор: ЧЧ={0 2 2 О О -2 2 0 О 2 -2 О 4 2

240244020002004-200-204-220

02240-2200-2-2402200-2200-22

04-2-200-2244-2200-2200202-20

02-200-22442-20-20022002204

40 -224020-22002-2-402204220), Рассмотрим нахождение максимального коэффициента корреляции в первой группе из четырех элементов. Первые четыре элемента в данном случае: 0220, т,е. хо=О, 45 х1=2, хг=2, хз=О. Они поступают на вход первого блока вычисления коэффициента корреляции 2.1 (фиг. 3). В блоке элементы хо и х1(хг и (-хз)) сравнива1отся элементом сравнения 12.1 (12(2)), на выходе которого появ50 ляется логическая единица, если

xQ

55 и (-хз). Таким образом на шине max появляЕТСЯ Xma><=maX(xo, X1, Хг;ХЗ), а На ШИНЕ min

ЭЛЕМЕНТ Xmin=mIA{XO, X1, Хг, -X3), КОТОРЫЕ ВЫчитаются в вычитателе 14, т.е, на шине а мы

1797164 стра. получим величину у1. Аналогичным образом на шине b получается величина у2. С помощью ключей, выполненных на базе элементов И 15, на шинах 1п х формируется величина !max в двоичном коде, а на шинах

Imln ВЕЛИЧИНа Imln, таКжЕ В ДВОИЧНОМ КОДЕ.

Сумматор 13.2 осуществляет сложение модулей величин, поступающих на его входы т.е. находит Kmax= y1 + yz °

В нашем примере

xmax=2, Xmtn 0, lmax=1, Imln=0i yl=2, Q- =2 !оп ах= 4.

Таким образом на выходе блока вычисления коэффициентов корреляции 2 вычисляется вектор коэффициентов корреляций: (4 4 4 12

10226848484484844448844884

8 4 8), который поступает на вход блока сравнения 3. Блок сравнения 3 определяет двоичный номер максимального коэффициента корреляции. На выходе блока сравнения 3 имеем вектор (О 0 0 1 1), элементы которого подаются на первый-пятый входы выходного буферного регистра 9 соответственно. Они также поступают на блок ключей

4 и определяют, для какой группы пропустить на дальнейшее декодирование величины,yl, ф, !п,а),,!П,)п, В нашем случае: у1=8, >=4, Imax=0, !т(п=3.

Далее необходимо установить, при умножении на какую строку матрицы Н с номерОМ Imax ИЛИ На СтрОКу С НОМЕРОМ lmln получается элемент km». При умножении на нулевую строку вектора x=(4 2 2 -4) (вектор, который дал максимальный коэффициент корреляции) получаем kc=4, при умножении на третью строку получаем Кз=12 (элемент хз везде берется со знаком минус). Номер

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

Декодер кода Нордстрома-Робинсона, содержащий первый-третий блоки сложения-вычитания, входы первого блока сложения-вычитания являются входами декодера, блок сравнения, выходы которого соединены с управляющими входами блока ключей и первым-пятым входами выходного буферного регистра, выходы которого являются выходами декодера, блок сложения и вычитания двух элементов и нуль-орган. отличающийся тем, что, с целью расширения области применения за счет декодирования в полунепрерывном канале и упрощения декодера, в него введены первый — тридцать второй блоки вычисления коэффициентов корреляции и блок определения йомера максимального коэффициента корреляции, выходы первого блока сложения-вычитания подключены к соответстроки, где получался максимальный коэффициент, даст шестой и седьмой информацИОННЫЕ СИМВОЛЫ. СтрОКИ С НОМЕраМИ Imln И

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

Поэтому один коэффициент будет равен

y1 +p, а другой- У1 ++. Данная операция осуществляется в блоке сложения и вычитания двух элементов 5. На выходе этого блока будем иметь 12 и -4. Причем если !

y>!+!yz! > !-yl + p1,то номер

СТРОКИ, ДаЮЩЕй Kmax, - ЭТО Imln В ПРОТИВНОМ случае это lmax (последнее утверждение проверяется непосредственной проверкой).

Величины y> + p, =12 и — y> + уг, =-4 с выходов блока суммирования и вычитания двух элементов 5 поступают на вход блока определения номера максимального коэффициента корреляции 6, где происходит сравнение y< + и

+ yz I, и в зависимости от результатов сравнения на выходной буферный регистр 9 пропускается либо lmln, либо Imax В нашем примере пропускается lmin=0

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

1797164

17971 б4

1797164

1797164

1797164

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

Редактор M. Кузнецова Техред M,Mîðãåíòàë Корректор С. Патрушева

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

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

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

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