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

союз совГтскихСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 97164 А 9) 1)5 Н 03 М 13/00 ЕТЕНИ ИЕИ У СВИДЕТЕЛЬСТ АВТОР яйственный инстишниковаС. Н, Лицын етных со,: Наук ьство СССР 3/00, 1989.Н ОРДСТРОМА-РО- ится к вычислителььзование в системах ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(56) Кодирование и передобщений по каналам с1976, с, 74-85.Авторское свидетелМ 1736008, кл. Н 03 М 1(57) Изобретение относной технике. Его испол передачи дискретной информации позволяет расширить область применения за счет декодирования в полунепрерывном канале и упростить декодер, который содержит блоки сложения-вычитания 1, блок сравнения 3, блок ключей 4, блок сложения и вычитания двух элементов 5, нуль-орган 7 и выходной буферный регистр 8, Благодаря введению 32 блоков вычисления коэффициентов корреляции 2 и блока определения номера максимального коэффициента корреляции 6 обеспечивается значительное сокращение числа сумматоров по сравнению с прототипом. 7 ил., Кузнецова Техред М,Моргентал Корректор С. Патрушев Реда но-издательский комбинат "Патент", г, Чжгород, ул,Гагарина, 101 изв аказ 656 ВНИИП Тираж ударственного комитета по изо 113035, Москва, Ж-З 5, РПодписноеетениям и открытиям при ГКНТ СССР ская наб., 4/5Изобретение относится к вычислительной технике, конкретно к устройствам декодирования кода Нордстрома-Робинсона.Известно устройство декодирования кода Нордстрома-Робинсона, основанное на разбиении кода на биортогональные подкоды с помощью преобразования Уолша, Данное устройство предназначено для декодирования широкого класса кодов, разбивающихся на биортогональные, и для кода Нордстрома-Робинсона не является оптимальным,Устройство содержит восемь блоков декодирования биортогонального кода, основанных на быстром преобразовании Уолша, и схемы выбора максимального элемента,Наиболее близким к предлагаемому устройству является устройство декодирования кода Нордстрома-Робинсона, основанное на разбиении кода Нордстрома-Робинсона на смежные классы по коду Ридамаллера первого порядка и проведении в каждом смежном классе усеченного быстрого преобразования Уолша. Данное устройство обеспечивает декодирование по максимуму правдоподобия лишь в дискретном канале, кроме того, оно не учитывает тождественные вычисления в различных смежных классах и следовательно не является оптимальным.Это устройство содержит семь блоков сложения с образующим смежного класса, усеченные декодеры кода Рида-Маллера, блок ключей, блок сравнения, регистр записи декодированного слова,Целью изобретения является декодер кода Нордстрома-Робинсона,Эта цель достигается тем, что в декодер кода Нордстрома-Робинсона, содержащий первый-третий блоки сложения-вычитания, входы первого блока сложения-вычитания являются входами декодера, блок сравнения, выходы которогО соединены с управляющими входами блока ключей и первым-пятым входами выходного буфер- ного регистра, выходы которого являются выходами декодера, блок сложения и вычитания двух элементов и нуль-орган, введены первый - 32-й блоки вычисления коэффициентов корреляции и блок определения номера максимального коэффициента корреляции, выходы первого блока сложения-вычитания подключены к соответствующим входам второго и третьего блоков сложения-вычитания, выходы которых соединены с соответствующими входами всех блоков вычисления коэффициентов корреляции, первые и вторь 1 е выходы которых подключены соответственно ко входам блока сравнения и информационным входамблока ключей, первые выходы которого соединены со входами блока сложения и вычитания двух элементов, выходы которого и вторые выходы блока ключей подключены к первым и вторым входам блока определения номера максимального коэффициента корреляции, первый, второй и третий выходы которого соединены соответственно со входом нуль-органа и шестым и седьмым входами выходного буферного регистра, выход нуль-органа подключен к восьмому входу буферного регистраблагодаря тому, что на первых двух этапах учитываются одинаковые операции сложения и вычитания в различных смежных классах и благодаря тому, что после второго этапа вычисляются сразу максимальные коэффициенты корреляции в группах по четыре элемента в каждой, число сумматоров уменьшается с 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 смежных классов по коду 5 10 15 20 25 30 35 40 45 50 Рида-Маллера первого порядка. Таким образом достаточно продекодировать восемь раз принятый вектор, к которому прибавлен очередной образующий смежного класса, и выбирать среди полученных 128 коэффициентов корреляции (по 16 коэффициентовкорреляции в каждом смежном классе) максимальный коэффициент, Двоичный номер этого коэффициента даст 8 информационных символов,Но на первых двух этапах декодирования кодов Рида-Маллера первого порядка в различных смежных классах имеется значительное количество одинаковых вычислений. Таким образом можно ограничиться шестнадцатью сложениями на первом этапе и 32-мя сложениями на втором этапе декодирования. После второго этапа имеем 128 элементов (по 16 элементов в восьми смехных классах), Разбиваем эти 128 элементов на группы по четыре последовательнь 1 х элемента в каждой и определяем в каждой группе максимальный коэффициент корреляции. Для нахождения максимального коэффициента корреляции в группе из четырех элементов требуется три сумматора, т,е. всего потребуется 3 32=96 сумматоров, Если же производить вычисления в полном объеме, то потребуется 512 сумматоров. Таким образом количество сумматоров значительно уменьшается,Максимальный коэффициент корреляции в группе из четырех элементов находится следующим образом. Пусть мы имеем элементы Хо, Х 1, Х 2, Хз в одной из групп после второго этапа декодирования. Для вычисления коэффициентов корреляции необходимо умножить вектор х=(хо, х 1, х 2, хз) на транспонированную матрицу Адамара Н размерности 4 х 4, Выберем в качестве этой матрицы матрицу:-1 1 1 -1Н= 1-1 1-1 1 1 -1 -1 1111 Можно заметить, что любая строка этой матрицы не совпадает с вектором к=(1, 1, 1, -1) лишь в одной позиции, причем 1-я строка матрицы Н не совпадает с вектором г о 1-ой позиции. Таким образом, если мы имеем величину у=х г=х 1+хг+хз+Х 4 и величины: 1 о=хНо=-Хо+Х 1+Х 2-Хз 11=х Н 1=ХО - Х 1+Х 2 - Хз 1 г=х Н 2=ХО+Х 1 - Х 2 - ХЗ 1 З=хНЗ=ХО+Х 1+Хг+ХЗ, где 11 это 1-й коэффициент корреляции (среди этих коэффициентов нам необходимо найти максимальный, Н это 1-я строка матрицы Н), то величину у и о, 11, 12, 13 будут связаны соотношениями; 1 о=у+2 хо 11=у+2 Х 1 12=у+2 хг 1 з= у+2(-хз) Величина у является постоянной для постоянных хо, х 1, х 2, хз, Следовательно максимальный по модулю коэффициент корреляции "вахгпах( 1 о111,12 1,1 з ) возникает там, где к величине у прибавляется лаксимальный 5 ЭЛЕМЕНТ Хвах=ГПаХ(ХО, Х 1, Х 2, -ХЗ) ИЛИ НаабОРОтминимальный элемент хвь=-гп 1 п(х, х, х, -х) (элемент хз берется со знаком л 1 инус, так как 1=у+2(-х, Таким образом Евах может появиться при умножении вектора х либо на 10 строку которая не совпадает с векторомвпозиции, где расположен элемент хвах, либо приумножении на строку, которая не совпадает съектором г в позиции, где расположен элемент Хюп. Далее если максимальный и 15 минимальный элементы имеют номера 1 вахи 1 вп, то в соответствующих выражениях дЛя КОЭффИцИЕНтОВ КОррЕЛяцИИ 11 пах, Ьв 1 п элементы хви хоп берутся с разными знаками (в этом можно убедиться при непос редственной проверке матрицы Н), а дваоставшихся элемента берутся со знаком плюс (все операции производятся над элементами (хо, х 1, х 2, -хз). Окончательно, если мы имеем элементы хо, х 1, х 2. -х 2, то для 25 нахождения 1 вах необходимо найти хвах иХвп, а таКжЕ ИХ НОМЕРавах и 1 в 1 п, ЗатЕМ ВЫЧИСЛИТЬ )=Хвах Хв 1 п, )г=хс+Х 1, С 1 вах 1 вп, С 1 фс, 1 вах, 1 в 1 п, и 1 вах=У 1+Уг.30 Поясним вышесказанное на примере.Пусть декодируется вектор Я=(1 -1 -1 1 1 1 -1 1 1-1 1 1 1-1-1 1). На выходе блока 1.1 будем иметь вектор В/=(О О 2 О О 2 О О 2-2 0, -2 2 02 2), На выходе блоков 1.2, 1.3 будем 35 иметь вектор: Я=(0 2 2 0 О -2 2 0 0 2 -2 0 4 2240244020002004-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, хз=О. Они поступают на вход первого блока вычисления коэффициента корреляции 2.1 (фиг. 3), В блоке элементы хо и х 1(хг и (-хз сравниоа 1 отся элементом сравнения 12.1 (12(2, на выходе которого появ ляется логическая единица, еслихох 1(х 2(-хз, и логический ноль о противном случае. Элемент сравнения 12.3 сравнивает больший элемент среди элементов хп и х 1 с большим элементол 1 среди элементов х 2 55 и (-хз), Таким образом на шине гпах появляЕТСЯ Хвах=П 1 ах(ХО, Х 1, Х 2;ХЗ), а На ШИНЕ П 11 П элемент хвв=в 1 п(хо, х 1, х 2, -хз), котоРые вычитаются в оычитателе 14, т.е, на шине а мы1797164 стра. получим величину у 1. Аналогичным образом на шине Ь получается величина уг. С помощью клочей, выполненных на базе элементов И 15, на шинах 1 вах формируется величина вах в двоичном коде, а на шинах 1 вп величина 1 вп, также в двоичном коде, Сумматор 13.2 осуществляет сложение модулей величин, поступающих на его входы т.Е. НаХОдИт Квах=71+ у 2В нашем примерехвах=2, хвп=О, вах=1, вп=О; /1=2, уг=-2, Ьпах=4.Таким образом на выходе блока вычисления коэффициентов корреляции 2 вычисляется вектор коэффициентов корреляций: (4 4 4 12 10226848484484844448844884 8 4 8), который поступает на вход блока сравнения 3. Блок сравнения 3 определяет двоичный номер максимального коэффициента корреляции. На выходе блока сравнения 3 имеем вектор (О 0 0 1 1), элементы которого подаются ка первый-пятый входы выходного буферного регистра 9 соответственно. Они также поступают на блок ключей 4 и определяют, для какой группы пропустить на дальнейшее декодирование вели- ЧИНЫ, 1, ф, вах вп. В НаШЕМ СЛуЧаЕ; )1=8, )г=4, 1 вах=О, вп=3.Далее необходимо установить, при умножении на какую строку матрицы Н с номером 1 вах или на строку с номером 1 вп получается элемент Квах. При умножении на нулевую строку вектора х=(4 2 2 -4) (вектор, который дал максимальный коэффициент корреляции) получаем Кс=4, при умножении на третью строку получаем 1 з=12 (элемент хз везде берется со знаком минус). Номер формула изобретен ия Декодер кода Нордстрома-Робинсона, содержащий первый-третий блоки сложения-вычитания, входы первого блока сложения-вычитания являются входами декодера, блок сравнения, выходы которого соединены с управляющими входами блока ключей и первым-пятым входами выходного буферного регистра, выходы которого являются выходами декодера, блок сложения и вычитания двух элементов и нуль-орган, о т л и ч а ю щ и й с я тем, что, с целью расширения области применения за счет декодирования в полунепрерывном канале и упрощения декодера, в него введены первый - тридцать второй блоки вычисления коэффициентов корреляции и блок определения йомера максимального коэффициента корреляции, выходы первого блока сложения-вычитания подключены к соответстроки, где получался максимальный коэффициент, даст шестой и седьмой информационные символы, Строки с номерами 1 вп и 1 вах различаются тем, что в одной из них при вычислении коэффициента корреляции у 1 берется с плюсом, а в другой с минусом. Поэтому один коэффициент будет равен 71 +уг, а другой- у 1 +уг. Данная операция осуществляется в блоке сложения и вычитания двух элементов 5. На выходе этого блока будем иметь 12 и -4, Причем если у 1+уг- у 1 + уг 1,тономер строки, дающей Квах, - это вп, В противном случае это 1 вах(последнее утверждение проверяется непосредственной проверкой), Величины у 1 +у, =12 и - у 1 +уг, =-4 с выходов блока суммирования и вычитания двух элементов 5 поступают на вход блока определения номера максимального коэффициента корреляции 6, где происходит СравнЕниЕу 1 + у 2и-у 1 + у 2 1, и в зависимости от результатов сравнения на выходной буферный регистр 9 пропускается либо вп, либо вах. В НаШЕМ ПрИМЕрЕ ПрОПуСКаЕтСя вп=01 О=Ог На шестой и седьмой входы выходного буфер- кого регистра 9. Кроме того в зависимости от сравнения на нуль-орган 7 пропускается либо у 1 +у 2 либо - 71 +уг В нашем случае пропускается у 1 +уг =12, Нуль-орган 7 определяет знак входной величины и выдает ноль в случае положительной величины и единицу в случае отрицательной величины, В нашем случае на выходе нуль-органа 7 появляется ноль, который подается на восьмой вход регистра 9. 10 15 20 25 30 35 ствующим входам второго и третьего блоков , сложения-вычитания, выходы которых соединены,с соответствующими входами всех блоков вычисления коэффициентов корреляции, первые и вторые выходы которых подключены соответственно к входам блока сравнения и информационным входам блока ключей, первые выходы которого соединены с входами блока сложения и вычитания двух элементов, выходы которого и вторые выходы блока ключей подключены к первым и вторым входам блока определения номера максимального коэффициента корреляции, первый, второй и третий выходы которого соединены соответственно с входом нуль-органа, шестым и седьмым входами выходного буферного регистра, выход нуль-органа подключен к восьлому Входу выходного буферного реги 1797164