Декодер линейного систематического кода

(21) 4 (22) 0 (46) 0 (72) 10 (53) 6 (56) 1986,23991/24 ,04,870190М,Давыдо 1,325(08Радиоте 9 7, с.14 в и О,В,Ко8.8)хника и зл56. троник во СССР 1986,во СССР 1984ЕМАТИЧКСсвидетельст 03 М 13/02 свидетельст 03 М 13/02 КйНОГО СИСт к вычи сливязи, Егредачи относит и техник системах ОСУДАРСТВЕННЫЙ НОМИТЕТ О ИЗОБРЕТЕНИЯМ И ОТНРЫТИ ПРИ ГКНТ СССР ИСАНИЕ ИЗО 2. АвторскоеУ 1443179, кл.3АвторскоВ 1327311, кл,(54) ДЕКОДЕР ЛИКОГО КОДА(57) Изобретенительной техникиспользование дискретной информации позволяет повысить быстродействие, Декодер содержит генератор 1 тактовых импульсов,блоки 2,5 оперативной памяти, блок 3преобразования кода, блок 4 быстрогопреобразования Уолша, блок 6 выборамаксимума и блок 12 памяти коэффициентов кода. Благодаря введению блока 7 дешифрации, блока 8 определениядостоверных символов, блока 9 оперативной памяти, блока 1 О вычисленияиндексови знаков функции Уолша и регистров 11, 13 преобразование кодаосуществляется один раз, для чего используется дополнительная информация,содержащаяся в достоверно принятыхсимволах, 12 ил,3 1534756Изобретение относится к вычислительной технике и технике связи и можетбыть использовано в системах передачи дискретной информации,5Цель изобретения - повышение быстродействия,На. Фиг,1 представлена блок-схемадекодера; йа Фиг,2 - блок вычисленияиндексов и знаков функции Уолша; на 10Фиг,3-10 - примеры выполнения соответственно блока преобразования кода,блока определения достоверных символов, третьего блока оперативной памяти, блока выбора максимума, блока дешифрации, узла упорядочения по весам,узла определения-индексов и знаков,дексов и знаков Функций Уолша, первый регистр 11, блок 12 памяти коэффициентов кода и третий регистр 13,На Фиг,1 обозначены информационный 14и установочные 15 входы, 35Блок 10 вычисления индексов и знаков функций Уолша (Фиг.2) выполненна узле 16 вычисления весов, узле 17упорядочения по весам и узле 18.определения индексов и знаков Функций 40Уолша 121,Блок 3 преобразования кода (фнг,3)содержит элементы 19 сравнения, регистр 20 сдвига, группы 21 и 22 клю"чей, сумматор 23 и выходной регистр 2445Блок 8 определения достоверныхсимволов (Фиг,4) содержит регистры 25-29, компаратор 30 счетчик 31,дешифратор 32 и ключи 33-35Третий блок 9 оперативной памяти, 50(2) Пусть, 1 , 1. ц - номера позиций достоверных символов, 0 с-йп,1,И, В качестве достоверных символов берутся символы принятого сигнала максимальной амплитуды,Можно показать, что в линейном систематическом коде кодовые слова с М достоверно принятыми символами на позициях ье,1, могут быть упорядоченными и представлены в виде матрицы 8 (2 хп), где с 1 определяет размер ансамбля кодовых слов, строками которого являются кодовые слова с М определяемыми достоверными символами, а столбцы - функции . Уолша порядка 2, индексы и знаки Узел 16 упорядочения по весам(фиг,8) содержит регистры 51-56, компаратор 57, счетчик 58, дешифратор 59и ключи 60-63, Выполнение узла 16 аналогично выполнению блока 8 (фиг.4),Узел 18 определения: индексов и знаков функций Уолша (фиг,9) содержитрегистры 64-70, кодер 71., счетчик 72,сумматоры 73 и 74, элемент 75 сравнения, триггеры 76 и 77, модульныйсчетчик 78, буферный регистр 79, элемент 80 сравнения, ключ 81, элементыИ 82-86, формирователь 87 импульса иарифметический блок 88.Арифметический блок 88 (фиг.10)выполнен на сумматорах 89 и 90 по мот,дулю два и группах 91 ключей.Работа предлагаемого декодера основана на следующих свойствах линейного систематического кода,Линейный систематический (Ь,Е)код включает в себя информационныеи проверочные символы и может бытьзадан через систему линейных уравнений проверочных символов (равноеис) 11х, я .,в а, х (1)где 1 - количество информационныхсимволовх - информационные символы кодо 3вого вектораа"- коэф 4 жциент уравнений (1),,1а= 0 пли 1.11Знак . означает суммирование помодулю два, Набор коэффициентов может быть задан матрицей С(п-К)х 1 с),4756 6 быть получен вид преобразования ко-. 153 да 31Знаки У,= 1,-с, Ь, - индексы функций Уолша в Ь;-ом столбце, относительно которых разрешаются уравнения (4), определяются какз 1 яп 01 здпх.,50 а, з 1 яп Ц,р1 ьада Ы"зцп х1 3 1 ешьгде, 11,ш определяют позиции40 достоверных символов среди информационных,Декодер работает следующим образом,Исходные состояния блоков, В45,блок 12 памяти коэффициентов кода свходов 15,1 устанавливаются значенияа; коэффициентов уравнений кода(О или 1 в соответствующей ячейке).Б регистр 20 блока 3 преобразования.кода (фиг,3) записываются в каждуюиз с-разрядных ячеек последовательные значения бинарных сигналов, представляющие собой значения чисел от О,С до 2 . Остальные регистры декодераобнулены.Тактовые импульсы с выходов ГГИ 1управляют работой схемы, По тактовым .импульсам с выхода ГХИ 1, следукщим. с частотой К ,дискретный входной 1 )1 с, 1 щ ш+1,М которых определяются иэ расположениядостоверных символов и уравнении (1),В соответствии с 13определение,".индексов и знаков функций Уолша встолбцах матрицы Я однозначно опреЬделяет вид арифметического преобразования кода (с учетом значений индексов и соответствующих знаков), которое приведет матрицу кодовых слов сМ достоверными символами, а, следовательно, и конкретное декодируемоеслово к такому виду, который позволяет после выполнения операции быстрого преобразования Уолша и определения максимального коэффициента однозначно его дешифровать,Функции Уолша Ив столбцах проверочных символов (1. = 1, ис) являются линейными комбинациями функцийУолша в столбцах информационных символов как следует иэ (1), а при замене О - ф 1, 1 -" -1 знак суммированияв формулезаменяется на производные, тогда,аЫ,= ПИ; ) ) (3)1 Да уравнение дпя .индексов Ь функМФции Уолша имеют видкЬк,= Х а. Ь, =1,п, (4)ф :с 1 )где Ь Ь - значения индексовв бинарном представлении;суммирование помодулю два,Дпя позиций 3 С , соответствующих достоверным символам,можно записатьЬ;, = 0сд (5)вфаЬ; = ОВкЬ ф Г а,";фЬ; = 0вЬ =Ха "Ь = Отак как число достоверных символов Мопределяется из условия Е- с (М (и - Й+ 1- с, где Й - минимальноекодовое расстояние, то в системе (5)может быть выделено 1 в . е независимых уравнений, разрешаемых относительно Ьуф, 1 1, К-с - индексовфункций Уолша порядка 2 в столбцахинформационных символов и аналогичноопределяются знаки Я;, 1 = 1,п этихФункций, В результате этого может 1 2и5 Ь, Ь ,.Ь (б))Я Яа. Яптак как значения индексов Ькд = 1, пи знаков Я,; могут бытьопределены через значения уже известных ЬЯ в столбцах информационныхсимволов,Решение выбранных из системы (5)Е-с уравнений осуществляется по схеме Горнера, При этом с индексов .Ь , гщ ,с среди К информационныхС- о с-задаются как 2 ,2 , т,е, 2где с определяет размер быстрогопреобразования Уолша и может быть вы 20 брано в зависимости от заранее заданных требований,Одновременно с вычислением индексов функций Уолша в К информационныхстолбцах матрицы определяются их зна 25 ки по следующему правилу: ставят всоответствие знаку функцию здр 1 х,".;:1, если х;сО;э 1 упх;О, если х;О.30Знаки И дпя Ь) 2 , т = 1,срположительны,сигнал, представляющий собой дискретную последовательность отрицательныхи положительных значений, поступает ,в блок 2, где записываются его амплитудные значения и знаки 08= (Б, П), (фиг.11 а), Записанные значения амп-лйтуд анализируются в блоке 8 определения достоверных символов, где определяются положения и знаки М символов с максимальными амплитудами, Выходное значение сигнала блока 8 Представляет собой бинарную последовательность 11 рцу 8 - (0 ц э) Б 8 р.у О), где каждое из значений 08, = 15 ф Ж 8 Б 8, ,1, ) - 2 разрядное и1, если 11; - достоверный118 символ1О, если У; - недостоверныйсимвол 20 Е . д = 1,М в119 ф 11 1 - 1 1+1 ти по следующему правилу;к9(1+Ц ( чбв+1ее 1 т)1 11 Ч;1) э 25 30аа Где а; принимают значения О или 1 (фиг,11 в).В блок 9 переписываются М-в бинарных последовательностей коэффициентов длины К из блока 12 памяти коэффициентов кода, Эти последовательности записываются в М-в регпст О ров 39 блока 9 (фиг,5). Запись осуществляется по тактам с частотой 1., (управляющие импульсы с первого выхода ГТИ 1) в каждый из регистров, а очередностью записи управляют им пульсы с частотой 1 /1: с второго выхода ГТИ 1, поочередно подключающихся к каждому из регистров 391-39,М, управление записью осуществляется через коммутатор 38 блока 9По окончании М-го импульса частоты.Е/1 в М-в регистрах 39 будут записаны не нулевые последовательности, а в регистров 39 останутся нулевыми, При этом число в определяет количест"55 во достоверных символов среди К информационных, а М"в - среди проверочных символов, причем значения в определяются количеством (суммой) всех не 1, если Б - достоверный2 Ц символ со зна;ком минус;О - в других случаях,Б блоке 12 памяти коэффициентов кода хранятся записанные и-К Е-разрядных бинарных последовательностей; соответствующих наборам коэффициенГов уравнений кода, т,е,а а,нулевых значений в кольцевом регистре 28 блока 8 определения достоверных символов, а М-в - в кольцевом регистре 29 блока 8 (фиг.4),Пусть Б;13; Б; - значениядостоверных символов в принятой последовательности из и символов, при этом11, х,, 1 - номера позиций достоверных символов среди К информационных, т, е. 6 1 с, 1,д- номера позиций достоверных символов среди проверочных символов,.Значения сигнала в блоке 9 представляют собой М-в (1 с+1)-разрядныхбинарных сигналов у которых К разрядов соответствуютзначениям сигналов из блока 12 памяВ Еесли 11цО , если 11,3 1 , а значение К+1-го разряда определяется как:2 1, если 118, +Я, 6 ф 1 О, если 11 . у О81+1В блок 10 поочередно поступают сигналы с выхода блока 9 и над ними последовательно осуществляются следующие операции:вычисление весов в узле 16 вычис-; ления весов (фиг,9)к 01- ь = с -Ц(1.;1 3 = 1,М-в;уйорядочение сигналов в порядке возрастания соответствующих им весов в узле 17 упорядочения по весам, реализация которого аналогична блоку 8 определения достоверных символов (фиг,8).поэлементный анализ значений каж"дого из бинарных сигналов 01, для определения индексов Ь; и знаков Б;(с) функций Уолша, осуществляемый в узле 18 следующим образом (фиг,9),Первый анализируемый сигнал из регистра 53 узла 17 записывается в1 с-разрядный регистр 65 Ю; (1 = 1,1 с) и в 1-разрядный регистр 66 из регистра 54 узла 17, где обозначено: И - номер анализируемого сигнала.Сф.= з 1 язЯ,1) 9Ц 1, (1=1,1 с) (0=3,М-та); 1 - текущее значение номера от начала отсчетасигнала (сигнал с выхода счетчика 58рассчитанного на максимальное числон Кн)5Определяется д = х,;,для которого Ц,;Ц,дО, тогда ф;, полагается равным 1 и записывается вячейку , регистра 66 узла.18Для всех 1 = ,;11 с,для которыхцз, Ф ц 1;Ока= 1 вычисляется Ь ав2 г 1, где 1 - ., ц, что6 з 1 ъ,аносуществляется при очередномсдвиге регистра 68, Значения индексов Ь в виде бинарного сигнала Ц1записываются в узле 18 в с-ю ячейку 69 в с разрядов с с параллельныхвыходов кольцевого регистра 68 сдвига, Исходное значение регистра 68 20узла 18 - "1" в старшем разряде чтоссоответствует сислу 2 -1 степени навыходе, т.е. 1000.Вычисляетсякь, - 3 Е-цв, ць;+ т 1 тЗначения индекса Ь; . записывается в1 ъЮячейку 1,;, регистра 69 в с разрядов,Аналогично дпя второго по порядку 30сигнала ( записываемого в регистры.65и 66.узла 18 из узла 17) определяется ь = 1., для которого ц ФМ 6ГЙФЛ 2Оц,1 для всех 1., х; й сдля которых ЦЦ. . О, Ц,. = 1 35и Ь =21, где= ЕдефффвЪ,14вычисляетсяк".,ъ, =, Х цаь,ць;м 1,Ие40Аналогично операция выполняетсяпри анализе всех сигналов до тех пор,пока в регистре бб не будут записанывсе ", что эквивалентно вычислениювсех Ь;, х 1 Л.Одновременно с вычислещем индексов Ь; функций Уолша 1 = 1,1 с, т,е,значений разрядов регистра 69, опре-.деляются их знаки по следующему правилу, 501Ставят. в соответствие знаку Функцию з 18 пх; (теоретически), что соответствует записи ОЗнаки для Ь 2 , определенныедня 1 Ф 1;, М-ш положительны, т,е, с = зЦпУ 1,. 0 для1ф МЗнаки И определяются какеивйкз 1 рб 1, з 1 япхя 9 ь а з 1 рЯ;,где здпх; - знак достоверногосимвола, соответстврощего бинарному,вектору ц 1.Знаки записываются в узле 18 ввиде бинарного сигнала со значением0,1 в с+1-й разряд регистра 69 в соответствующую ячейку,Вычисление индексов в провероч-ных столбцах матрицы К+1,п по правилу, задаваемому в кодере 7Вычисленные значения записываются в регистре О узла 18На выходе блока 10 вычисления ин дексов функций Уолша и их знаков по-.лучают последовательность длиныи (с+1)-разрядных бинарных сигналов,каждое из значений сигнала соответствует:с разрядов - бинарное представление индекса функции Уолша, (с+1)-йразряд - знак функции Уолша (фиг,11).Кодер 71 узла 18 представляет собой в общем случае набор ис сумматоров по модулю два, к которым подклю"чены параллельные выходы сдвиговогорегистра 69 узла 18Далее вычисленные значения индексов перепишутся врегистр 11, а знаков - в регистр 13,После вычисления значений индексов Ь; и знаков осуществляется преобразование входного сигнала в блоке 3 преобразования кода, аналогичноописанному в 13 и показанному в приводимом ниже примере,Затем осуществляется быстрое преобразование Уолша в блоке БПУ, выбормаксимального коэффициента преобразования в блоке 6 и дешифрация в блоке 7 на выходе которого, получаетсяискомое информационное слово,Работа декодера для линейного циклического кода (15,7).П р и м е р, Линейный циклический(15,7) код с кодовым расстояниемд = 5 задан в виде проверочного полинома 8(х)х+ х + х+ 1 или систеомой уравнений для проверочных символовх = х, х.О+ хтх - х Эха 9 х О+х 6 Эхили порождающей матрицей С (7 х 8)1 1 1 О 1 О О О О 1 1 1 О 1 0 О у,+1 1 +1 +1 1 +1 1+1 где- номера дискретов сигнала и соответствующие номера ячеек регистр в блоке 2Значения сигнала О показаны на Ффг,1 а, М = п- й+ 1- с = 7 (число дЬстоверных символов).Пусть условно достоверно приняты снмволы, расположенные на позициях 3.щ 1, 1.,= 7, . = 9,з;= 10, 11.1; З 6 д 3;,/7=5 и имеют знаки, указанные в таблице, .,тогда Ь,= О, Ь = 1, Ь = 1,.Ь+ = О,Ь = О, Ь 6= О, Ь= 1 (на Фиг,11 показанй заш рихованными). Из системы (4) следуетЬ 0 Ь ЬЯ. Ь 5 Ь 6 1. 0Ь ЬФ+ ЬЗ Ь Ьб Оэ Ьй ЬЭ. Ь 4+ + Ь 6+ Ь О у Ь+ Ь.+ ЬО ф Ьа Ь 6+ +Ь= 0Учитывая, что Ь = Ь = О, .переписывают эти уравнения, что эквивалентно операции записи бинарных сигналов из блока 12 памяти коэффициентов в блок 9,Записывают эти уравнения в порядке возрастания числа ненулевых слагаемых, Эта операция эквивалентна, вычислению весов и упорядочению по весам в блоке 9:Ьч Ь 6 Ьй ЬБ Ь 6 Ьй Ь 4 Ь 5 Ь+ Ь+ Ь+ Ь 6= О Ь+ Ь+ Ь 6+ Ь 6= О, а соответствующие,бинарные сигналы имеют вид 0 0 О 1 О 1 О ОО О 1 1 О 0 1 0 1 1 0 О О 1 1 1 О0 0 1 1 О 1 1 0 где 1 - соответствует нулевому коэф" Фнциенту перед Ь в каждом уравнении. 12О О 11 0 1 О 7 Х 61 1 1 О ОО О 1 1О О 1 11 О 1 О О О. 1 Пусть с = 4 для удобства размерсБПУ = 2 (выбирают близко по значениюкп, п=2 )Принимают, что принимаемый сигналу = У;,= 1,15 представляетсятаблицей,Из первого уравнения, соответствующего достоверному символу х; , т,е,17сигналу Ц0001010, записанному врегистр Ь :, определяют Ь = 2 = 1(записывают в регистр 68 узла 18) иТак как осталось 3 неопределенныхиндекса, то, учитывая., что с = 4они могут быть последовательно заданы как 2 . = 2,с, т.е, Ь = 2,Ь = 4, Ь = 8 - все эти значения запи 3сываются в регистре 69 узла 1830 (Фиг,10) после того, как проанализировано необходимое число бинарных сиг-.налов т,е, 1+а=с-с.Как следует из условия примера,знаки функций И 1, в столбцах информа 35 ционных символов (Я.) с; с индексамиЬи Ь, те, т = 1,7., определяютсязнаками достоверных символов с,=с = Ь =Знаки функции У, с индексами Ь,40 Ь Ъи Ь 6, . 2,3,56 положительны, то есть с = с = ссО .3 Ъ %,6 фУчитывая, что знак достоверногосимвола х; отрицательный, т.е, Ь= 1,имеем с,1= Ь Юсб 9 с= 0(блок 88 уз 45 ла 18), т,е, Функции Уолша У 1, встолбцах информационных символов. = 1 с имеют следующие индексы и знакиЬ О(+), Ь - "2(+) Ьз (+)ЬФ 1(+)э, Ьу 8( )Ф Ьб 1( )ф50 Ь = О(-). Эти индексы и знаки записаны в с+1 разрядах каждой иэ К ячеек регистра 69 (фиг,11 е) в результате поэлементного. анализа сигналов вузле 18, Индексы и знаки в столбцах55 проверочных символов определяютсякак:Ь =Ь+Ь+Ь=8, се с+ с+У(,), Ь:3(.), Ь="О(-).Эти значения индексов и знаков записываются в регистр 70 узла 18 (фиг,11 е).Соответствующее арифметическое 10 преобразование сигнала у = у;1, х = х;)определяется в общем случае таблицей Блок 3 преобразования кода выполняет следующую операцию: г =, Я; у;ь;где г - Ч-е значение выходного сигнала 11 блока 3 преобразования кода,При отсутствии Ь;= Ч соответствующая координаты полагается равной О, а при совпадении 11; = Ь = Чэта координата является суммой их ссоответствующими знаками, Например,получают:го у ут у 5- 3, г,= у+ У 6= 2,г = у= 1.и т,д,г = (32 - 101110 - 20020 - 101),фиг, 12 а,Работа блока 3 иллюстрируется нафиг.3 и подробно описана в 131, .аименно, сигнал г и является выходомблока 3 преобразования кода,Затем преобразовательный сигнал гпоступает на вход блока 4 БПУ, гдеосуществляется быстрое преобразование Уолша, Значения преобразованиясигнала. (коэффициенты корреляции)отображены на фиг,12 б,Полученная последовательность коэффициентов корреляции 0записывается в блоке 5, 0 = Б50(5-5353-31-1531513553).В блоке 6 выбора максимума определяется номер Ч максимального коэффициента: Ч10, а затем осуществляется непосредственно дешифрация декодируемого сигнала в блоке 7, Декодированный вектор х =х;), 3 = 1,сопределяется по следующему правилу,у которой элементы известны послеокончания операции вычисления кндексов в узле 18:- номер позиции исходного вектора у =.О у,.1, 1 1,и- позиции преобразованного вектора сигнала оЕ = 111 г 1,01 "1,Ь - определены и хранятся в регистре 11,с;(Я;)- знаки, хранящиеся в регистре 13Дпя выбранного примера соответствующая таблица преобразования имеет вид: Номер Ч+ записывается в бинарномпредставлении и поступает на третийвход блока 7 (в виде с параллельныхсигналов). На первые и второй входыблока 7 поступает К значений индексов и соответствующих знаков с для1,1 с, также записанных в бийарномс-разрядном представлении в регистрах 11 и 13, Дискретные значения вьгходкого сигнала Узы= 1 х опРеделЯется из, услоя х щ Г Ч; Ь (+где М - значение ь-го разряда1Ь 1 Що),с - знак О 1 ), так как Ч = 10,Мт.е. в двоичном представленииЧ -1 ЧЧЧ,Ч Д= 1010, то 11 д 11г(0100 01) (фиг, 12 в),Таким образом, в декодере преобразование кода и соответственно егобыстрое преобразование Уолша выполня-ется всего один раз вследствие того,что используется дополнительная информация, содержащаяся в достовсрнопринятых символах, Это и обеспечивает повышение быстродействия,Формула и э о б р е т е н и я Декодер линейного систематического кода, содержащий блок памяти коэффициентов кода, генератор тактовых импульсов, первый выход которого подключен к тактовым входам блока преобразования кода, блока быстрого преобразования Уолша, блока выбора максимума и первого блока оперативной памяти, информационный вход которогоявляется информационным входом декодЕра, второй блок оперативной памяти, выход которбго соединен с информационным входом блока выбора максимума, первые выходы первого блока оперативнОй памяти подключены к первым информационным входам блока преобразованя кода, выход которого соединен с иформационным гходом блока быстрого преобразования Уолша, выход которого подключен к информационному входу второго блока оперативной памяти,. о т л и ч а ю щ и й с я тем, что, с целью повышения быстродействия, в декодер введены блок дешифрации, блок вычисления индексов и знаков фнкций Уолша, первый и второй регистры, третий блок оперативной памя- . т и блок определения достоверных символов, тактовый вход которого объеринен с тактовыми входами блока памя-тИ коэффициентов кода, блока дешифрации, второго блока оперативной памяти, блока вычислений индексов и зна ков функций Уолша и первым тактовым входом третьего блока оперативной памяти и подключен к первому выходу генератора тактовых импульсов, второй ыход которого соединен с вторым ЗО ,актовым входом третьего блока оперативной памяти и тактовыми входами первого и второго регистров второй выход первого блока оперативной памяти соединен с информационным вхоДом блока определения достоверныхО символов, выходы которого и выход блока памяти коэффициентов кода подключены соответственно к первым и вторым информационным входам третьего блока оперативной памяти, выход которого соединен с информационным входом блока вычисления индексов и знаков Функций Уолша, первые и вторые выходы которого подключены к информационным входам соответственно первого и второго регистров, первые выходы первого регистра соединен ны с вторыми информационными входами блока преобразования кода и первыми входами блока дешифрации, вторые выходы первого регистра подключены к третьим информационным входамблока преобразования кода, первый выход второго регистра соедйнен с четвертым информационным входом блока преобразования кода и вторым входом блока дешифрации, вторые выходы второго регистра подключены к пятым инФормационным входам блока преобразования кода, выходы блока выбора максимума соединены с третьими входами блока дешифрации, выход которого является выходом декодера, установочные входы блока памяти коэффициентов кода, блока преобразования кода, блока вычисления индексов и знаков функций Уолша, первого и второго регистров являются первым-пятым установочными входами декодера.1