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

(51) ЕТЕНИЯ ИСАН ЕТЕЛ ЬСТВУ М К АВТ нныи инстиаи С, Л.Пормации, 1983,СССР 988.ЛЛЕРА ПЕРМУМУ ПРАВГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) ДЕКОДЕР КОДА РИДА-МАБОГО ПОРЯДКА ПО МАКСИДОПОДОБИЯ Изобретение относится к вычислительной технике, конкретно к устройствам декодирования кодов Рида-Маллера, и может быть использовано при разработке аппаратуры передачи дискретной информации,Известно устройство декодирования кодов Рида-Маллера первого порядка длины 2", содержащее буферный регистр, в блоков суммирования и вычитания, (и)-1) блоков суммирования модулей, и) блоков сравнения модулей, (и)-1) блоков ключей и регистр записи декодированного слова.Недостатком указанного устройства является меньшая по сравнению с декодированием по максимуму правдоподобия помехоустойчивость.Известно устройство декодирования кодов Рида-Маллера первого порядка по максимуму правдоподобия, содержащее буферный регистр, (щ) блоков суммирования и вычитания блок попарного суммирования модулей, блок сравнения сумм пар модулей, блок ключей, блок суммирования и вычитания двух элементов, блок сравнения,2(57) Изобретение относится к вычислительной технике, Его использование в аппаратуре передачи дискретной информации позволяет упростить декодер, содержащий входной буферный регистр 1, блоки сложения-вычитания, блок сравнения, блок ключей, блок сложения-вычитания двух элементов, нуль-орган и выходной буферный регистр Благодаря введению блоков вычисления. коэффициентов корреляции и блока определения номера максимального коэффициента корреляции в декодере сокращается число блоков сложения-вычитания. 6 ил. блок ключей и)-го этапа, нудь-орган, регистрзаписи.декодированного слова,Недостатком данного устройства является высокая сложность реализации.Целью изобретения является упрощение устройства.Эта цель достигается тем, что в декодеркодов Рида-Маллера первого порядка помаксимуму правдоподобия, содержащий:последовательно соединенные входной бу-ферный регистр, первый -(Гп - 2)-й блоки сложения-вычитания, (2 - дли на кодаРида-Маллера, и) = 1,2), блок сравнения,выходы которого соединены с управляющими входами блока ключей, первые выходыкоторого подключены ко входам блока сложения-вычитания двух элементов, нуль-орган, выход которого соединен со входом(и)+1)-го разряда выходного буферного регистра. входы входного и выходы выходногобуферных регистров являются соответственно входами и выходами декодера, введены первый - (2 )-й блоки вычислениякоэффициентов корреляции и блок опреде 1775857-1 1 1 -11 -1 1 -11 1 -1 -11 1 1 1 Н= ления номера максимального коэффициента корреляции, выходы (ги)-го блока сложения-вычитания подключены ко входам и ерв о го - (2" )- го блока вычисления коэффициентов корреляции, первые и вторые выходы которых соединены соответственно со входами блока сравнения и информационными входами блока ключей, выходы блока сложения-вычитания двух элементов и вторые выходы блока ключей соединены с первыми и вторыми входами блока определения номера максимального коэффициента корреляции, первый, второй и третий выходы которого подключены соответственно ко входу нуль-органа и входам первого и второго разрядов выходного буферного регистра, входы третьего - ги-го разрядов которого подключены к выходам блока сравнения, Благодаря тому, что после (ги - 2)- го этапа вводится блок вычисления коэффициентов корреляции, достигается зкономия аппаратурных затрат: требуемое число сум 3рпматоров уменьшается на - х и = 3 х 24и кроме того в прототипе используются2 сумматоровкоторые вычисляют сумму модулей входных величин, Такой сумматор является более сложным устройством, чем сумматор, вычисляющий просто сумму двух величин, так как операция взятия модуля требует определенных аппаратурных затрат. В предлагаемом устройстве количество сумматоров ищущих сумму модулейи ивходных величин равно - , т,е, на - меньше,44 чем в прототипе.На фиг, 1 изображена структурная схема устройства декодирования. На фиг, 2 и 3 даны схемы подключения соответственно блока сложения-вычитания и блоков вычисления коэффициентов корреляции для случая ги = 4, и = 16. На фиг. 4 и 5 приведены схемы соответственно блока вычисления коэффициентов корреляции и блока определения номера коэффициента корреляции для того же случая,Декодер содержит; входной буферный регистр 1, блоки вычитания 2, блоки вычисления коэффициентов корреляции 3, блок сравнения 4, блок ключей 5, блок определения номера максимального коэффициента корреляции 6, блок сложения-вычитания двух элементов 7, нуль-орган 8, выходной буферный регистр 9.Буферный регистр 1 представляет собой 2-разрядный регистр.Блок сложения-вычитания 2 (фиг, 2) для 1-го шага ( . ги) содержит 2" сумматоров 10 и вычитателей 11. Елок вычисления коэффициентов корреляции 3 (фиг. 4), содержит элементы сравнения 12, элементы запрета И 14, сумматоры 15 и вычитатель 16, Блок сравнения 4 определяет номер максимального коэффициента корреляции,Блок ключей 5 пропускает на вход блока б элементы, давшие максимальный коэффициент корреляции в блоках 3,Блок определения номера максимального коэффициента корреляции 6 содержит элемент сравнения 19 и элементы И 20 (фиг, 5). Блок сложения-вычитания двух элементов 7 состоит (фиг, 5) из сумматора 17 и вычитателя 18.Нуль-орган 8 представляет собой блокопределения знака числа,Выходной буферный регистр 9 представляет собой (ги+1)-разрядный буферный регистр,Идея упрощения декодера заключается в следующем, Первые ги - 2 этапов декодирования совпадают с аналогичными этапами в прототипе: осуществляется попарное сложение и вычитание элементов а и а+1, ==1,3,5,и - 1. Затем полученная последовательность длины и разбивается на группы по четыре элемента в каждой. В каждой из этих подгрупп вычисляется максимальный коэффициент корреляции, среди полученных коэффициентов корреляции находится максимальный по модулю коэффициент корреляции. двоичный номер группы, в которой он получен дает (3 - ги) информационные символы. Так как по четырем элементам любой группы можно найти четыре коэффициента корреляции, то номер максимального из них, в группе пропущенной на дальнейшее декодирование, дает первый и второй информационные символы. Знак максимального по модулю коэффициента корреляции дает (щ+1)-й информационный символ,Максимальный коэффициент корреляции в группе из четырех элементов находится следующим образом, Пусть мы имеем элементы хо, х 1, х 2, хз - которые составляют одну из групп после (ги - 2) этапов декодирования, Для вычисления коэффициентов корреляции необходимо умножить вектор х = =(хо. х 1, х 2, хз) на транспонированную матрицу Адамара Н размерности 4 х 4. Выберем в качестве этой матрицы матрицу: Можно заметить, что любая строка этой матрицы не совпадает с вектором г = (1, 1, 1, -1)лишь в одной позиции, причем, 1-я строка матрицы Н не совпадает с вектором Е в 1-ой позиции, Таким образом, если мы вычислим величину у = хг = хо + х 1 + хг - хз, то величины 5ЕО = хНО .= -хО + х 1 + х 2 хЗ1(1 = хфН 1 = хо х 1+ х 2 хз1(2 = хН 2 = хо+ х 1 х 2 хз13 = хфНЗ = хо+ х 1+ х 2+ хзгде Ь - 1-й коэффициент корреляции, Н - 1-я 10 стока матриц Н; и величина у будут связаны соотношениями;1 о=у+2 хо6 =у+2 Х 11 сг=у+2 хг 15 Мз=у+2 хзВеличина у является постоянной для постоянных хо, х 1, х 2, хз, следовательно; максимальный коэффициент корреляции возникнет там, где к величине у прибавля ется максимальный элемент х 1 или наоборот минимальный элемент х 1, причем максимальный и минимальный элементы следует искать среди элементов хо, х 1, х 2, -хз, т.к, Мз= = у - 2 хз. Далее, если максимальный и 25 минимальный элементы имеют. номера вах и выл, то в выражении (1) для Ьваи Ьв 1 п элементы хваи х п берутся с разными знаками (в этом можно убедиться при непосредственной проверке матрицы Н), а два оставшихся элемента берутся со знаком плюс (все операции проводятся над элементами хо, х 1, х 2, -хз). Окончательно, если имеем элементы хо, х 1, х 2, хз, то для нахождения Кщах = ВаХ (ЕО, К 1, 12, КЗ), НЕОбХОДИМО НайтИ35 максимальный и минимальный элементы хо, Х 1, Х 2, -ХЗ И СООтВЕтСтВЕННО ИХ НОМЕРа вах И 1;и, затем вычислить величину у 1 = хвах -- хвгп и величину уг = х, - ха с твах, 1 вп, б 1 с, 1 вах 1 вп, и Кщах =1 У 11+,У 21 (во всех вычис/ 40 лениях хз берется со знаком минус).Поясним вышесказанное на примере. Пусть декодируется вектор: а = (-1 -1 -1 1 1 1 -1 1 1 -1 -1 1 1 -1 -1 1), тогда граф декодирования будет иметь вид, показанный на фиг, 6, Рассмотрим нахождение максимальных коэффициентов корреляции в каждой группе:1.хО = -2, х 1 = 2, х 2 = 2, -ХЗ = О, ИщЕм максимальные и минимальные элементы хп 1 ах = 2, хвп = -2, вп = 1, 1 щах = О, У 1 х 1 хО = 4, р - х 2 - хЗ = -2Квах =4+2=62 х О = -2, х 1 = -2, х 2 = 2, -хз = Охвах = 2, хвгп = -2, щах = 2, 1 ви = 055у 1=х 1 - хо=4, уг=х 2 хз=-2щах=4+2=613 хО =-2, Х 1= 2, х 2 =-2,-хЗ = 0хвах = 2, хппп =-2, щах =1, 1 пнп =0 у хо - х 1 = 4, уг = х 2 - хз - -21 щах=4+2 = 64. хо =2, х 1= 2, х 2 =-2, -хз =-4Хвах = 2, Хвп = -4, 1 вах = О, 1 щп = 3 У 1 = хО х 1 = 6, У 2 = х 2 + хЗ = 4, 1 вах =103Таким образом, 1 вах1 щах, 1 вах,3 О 1 к п 1 ах, и, следовательно, 3-й и 4-й информационных символа это: 1,1, Далее необходимо определить номер максимального коэффициента в своей группе, т,е. какая строка матрицы Н при умножении х Н дала максимальный коэффициент корреляции, Это может быть строка с номером 0 или 3, т.к. щах = О, 1 вп = 3, При умножении на нулевую строку будем иметь величину -6+ +4 = -2. при умножении на третью строку величину 6+ 4 = 10, следовательно, максимальный коэффициент даст третья строка, т.е. первый и второй информационные символы: 1 1. Общее правило нахождения номера максимального коэффициента корреляции (т.е, строки матрицы Н дающей максимальный коэффициент корреляции) следующее, Допустим, мы вычислили Мвах = =1 У 11 + 1 У 21, щах, 1 ви, затем вычислЯем величины д 1= -у 1+ у 2, дг = у 1+ уг, сравниваем д 1 и д 2, еслид 1д 2, то номер строки дающей максимальный коэффициент корреляции - это 1 щ 1 п, в противном случае это 1 ви, ДВОИЧНОЕ ПрЕдСтаВЛЕНИЕ 1 в 1 п ИЛИ 1 вах дают первый и второй информационные символы,Работает декодер кода Рида-Маллера следующим образом, Кодовый вектор длины и = 2 приходит из линии связи и записывается в буферный регистр 1, оттуда элементы вектора подаются на вход блока сложения- вычитания 2.1, Результаты суммирования 2 в сумматоров 10 и 2 в вычитателей 11 1-го блока сложения-вычитания 2.1( = 1, в - 3) подаются на входы (1 + 1)-го блока сложения-вычитания 2.1+ 1. Элементы с вблоков сложения-вычитания подаются на блоки вычисления коэффициентов корреляции 3, по четыре последовательных элемента на каждый блок. В блоке 3 (фиг, 4) происходят следующие действия, Элемент хз инвертируется, затем сравниваются элементы хо и х 1, х 2 и (-хз). Элемент 12 сравнения имеет на ВЫХОДЕ ЛОГИЧЕСКУЮ ЕДИНИЦУ, ЕСЛИ ХОХ 1 (х 2(-хз и логический ноль, если хох 1(х 2(-хз. Тогда посредством злементов 13, 14 на шины вах 1, вах 2 пропускаются большие из элементов хо и х 1(х 2 и (-хз, а на шины ви 1, впг соответственно меньшие элементы. Затем происходит сравнение максимального элемента среди эле;ентов хо и х 1 с максимальным элементом среди элементов х 2 и (-хЗ), сравнение максимального элемента среди (хо и х 1) с минимальнымэлементом среди (хр и (-хз, Таким образом. мы находим хгпах и хщп, которые поступают по шинам щах и ви на вычитатель 16, на выходе которого получаем величину у. По шинам с и д на сумматор 15,1 поступают хс и хд, где сщах, 1 вь, дс, 1 П, 1 юп, на выходе этого сумматора получаем величину у 2, Величины у 1, и у 2 поступаютна сумматор 15,2 на выходе которого мы имеем величину вах = =71 + 121 . Величины Мп,х поступают в блок сравнения 4, Одновременно с помощью элементов И 14 на шинах 1 тах и Ьи формируются двоичные номера величин хщах и хви 1 пах и в 1 п Затем ) и 2 щах и пи каждой группы из четырех элементов поступают на блок ключей 5. В блоке сравнения 4 происходит определение номера максимального коэффициента среди коэффициентов, пришедших со всех групп по четыре элемента каждая, Двоичный номер максимального коэффициента - это (3 - гп)-е информационные символы, они подаются в выходной буферный регистр 9, кроме того они подаются в блок ключей 5 и определяют, из какой группы пропустить на дальнейшее декодирование элементы у 1, у 2, 1 вах и Ьи, Пропущенные элементы у 1, у подаются на блок сложения и вычитания двух элементов 7 (фиг, 5), в котором определяются величины д 1 = 1 + )Ф и д 2 =- у 1 + у 2. Величины д и д 1 подаются на блок определения номера максимального коэффициента корреляции 6, туда же поступают элементы щах и ви с выходов блока ключей 5. В блоке определения номера максимального коэффициента корреляции 6 сравниваются величины 1 д 11 и д 2, еслид 1д 21, то на первый и второй входы выходного буферного регистра 9 подается величинаП 1, в противном случае величина щах, кроме того большая по модулю из величин д 1 и 1 д 2 поступает на вход нуль-органа д, где определяется 5 10 15 20 25 30 35 40 знак этой величины; если знак плюс, то выход нуль-органа д равен нулю, в противном случае он равен единице. Символ с выхода нуль-органа 8 подается на (гл + 1)-й вход выходного буферного регистра 9,Формула изобретения Декодер кода Рида-Маллера первого порядка по максимуму правдоподобия, содержащий последовательно соединенные входной буферный регистр и первый - (щ)-й блоки сложения-вычитания (2" - длина кода Рида-Маллера, в = 1,2,.), блок сравнения, выходы которого соединены с управляющими входами блока ключей, первые выходы которого подключены к входам. блока сложения-вычитания двух элементов, нуль-орган, выход которого соединен с входом (в+1)-го разряда выходного буферного регистра, входы входного и выходы выходного буферных регистров являются соответственно входами и выходами декодера, о тл и ч а ю щ и й с я тем, что, с целью упрощения декодера в него введены первый - (2 )-й блоки вычисления коэффициентов корреляции и блок определения номера максимального коэффициента корреляции, выходы (а - 2)-го блока сложения-вычитания подключены к входам первого -(2 )-гоблока вычисления коэффициентов корреляции, первые и вторые выходы которых соединены соответственно с входами сравнения и информационными входами блока ключей, выходы блока сложения-вычитания двух элементов и вторые выходы блока ключей соединены с первыми и вторыми входами блока определения номера максимального коэффициента корреляции, первый, второй и третий выходы которого подключены соответственно к входу нуль-органа и входам первого и второго разрядов выходного буферного регистра, входы третьего - пз-го разрядов которого подключены к выходам блока сравнения,1775857 ректор С, П Составитель Е, АшихминТехред М.Моргентал ушевд ак Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина,каз 4041 ВНИИПИ Тираж эрственного комитета по 113035, Москва. ЖПодписное бретениям и открытиям при ГКНТ СССРаущская наб., 4/5