Устройство для декодирования сверточного кода

(56) Кейн Дж. Кларк Дж, Кодированиес исправлением ошибок в системахцифровой связи. - М,: Радио и связь,1987, с.235-246.Авторское свидетельство СССРР 675616, кл. Н 03 М 13/12, 1977.Авторское свидетельство СССРР 1319283, кл . Н 03 М 13/12, 1984,Авторское свидетельство СССР9 1005322, кл. Н 04 1. 17/30, 1981.(54) УСТРОЙСТВО ДЛЯ ДРКОДИРОВАНИЯСВЕРТОЧНОГО КОДА(57) Изобретение отнтельной технике и технике связи. Ег,.ЯО, 1612378 2использование в аппаратуре передачи цифровы: дашгг; позволяет упростить устройство, содержащее блок 1 вычисления метрик ветвей, сумматоры 2 блок 3 сравнения, коммутаторы 4-6, олок 7 нормированного порога, блок 8 па:.я.и мзтрик, кодеры 9, формирователь 10 адресов считывания, формирователь 11 адресов записи и блок 14 памяти путей. Благодаря введению формирователя 12 адресов памяти путей, формирователя 13 адресов прослеживания путей, блока 15 прослеживания путей, решающего блока 16 и блока 17 такчогой синхронизации в устройстве обеспечнвается одновременное сложение метрик и нормализации, а циркуляция адресов шага декодирования осуществляется в одном блоке памяти путей. 2 зп. ф-лы, 8 ил.. Изобретение относится к вычислительной технике и технике связи иможет быть использовано и аппаратурепередачи цифровых данных.Цель изобретения - упрощение устройства.На фиг.1 изображена блок-схемаустройства; на Фиг.2 вблок тактоВой синхронизации; на Фиг.З - Формирователь адресов прослеживания путей на фнг.4 - схема кодера, формирующего декодируемый устройствомсверточный код; на. Фиг, -8 . диаграммы, поясняющие работу устройства.Устройство содержит блок 1 вычисления метрик ветвей, сумматоры .2,блок 3 сравнения, первый - третийкоммутаторы 4-6, блок 7 нормированного порога, блок 8 памяти мет,рик, кодеры 9, формирователь 10 адресов считывания, Формирователь 11адресов записи, Формирователь 12адресов памяти путей, формировательацресов прослеживания путей, блок 14памяти путей, блок 15 прослежива, ния путей, решающий блок 16 и блок17 тактовой синхронизации, а такжеинформационный вход 18 н вход 19синхронизации.Блок 1 вычисления метрик ветвей,блок 7 нормированного пороге, блок 8памяти метрик, кодеры 9.1 и 9.2,Формирователь 10 адресов считывания и формирователь 11 адресов записи выполнены так же, как аналогичные блоки известного устройства,Блок 17 тактовой синхронизациисодержит (Фиг.2) генератор 20 тактовых импульсов, делитель 1 частотыпервый 22 и второй 23 триггеры нэлемент И-НЕ, а также вход 25 синхронизации, управляющие входы 26, перьый 27 и второй 28 выходы,Формирователь 12 адресов памятипутей как и формирователи 10 и 11,.представляег собой счетчик импульсовФормирователь 13 адресов прослеживания путей содержит (Фиг.3) счетчик 29 импульсов, триггер 30 и эле. мент И 31, а также установочныевходы 32, счетный 33 и управляющий34 входы первый 35 и второй 36 выйоды,с ;Блок 14 памяти путей реализованкак блок оперативной памяти. Блок 15прослеживания путей представляетсобой регистр сдвига,Решающий блок 16 служит для преобразования параллельного кода в последовательный и выполнен на регистре сдвига, установочные входы которого от последнего разряца к первому являются информационными входами блока 16 от первого разряда к последнему, вход выбора режима регистра сдвига является управляющим входом блока 16, тактовый вход и выход регистра сдвига являются соответственно тактовым входом и выходом блока 16,Кодер на передающей стороне, Формирующий сверточный код с длиной кодового ограьичения К подлежащий декодированию в предлагаемом устройстве, содержит (Фиг,4) К-разрядный регистр 37 сдвига, полусумматоры 38 и 39 и коммутатор 40, а также информационный 41 и тактовый 42 входы.Код задается связями между выходами разрядов регистра 37 сдвига и входами полусумматоров 38 и 39. Обозначая наличие связи между разрядом регистра и входом полусумматора символом "1" а отсутствие свчзи символом "0, получают коцовые генераторы (1011, 101), а представгяя кодовые генераторы в восьмеричной Форме, получают (13,15), Кпина кодового ограничения такого кода равна четырем. Информационная последовательность Т(0) поступает на вход . регистра 37 сдвига и в течение длительности одного информационного сим" вола с помощью коммутаторе 40 генери" руются два канальных символа, Таким образом скорость кода в данном случае равна 3. = 1/2. В общем случае скорость кода может бь:ть равной Е = 1 с/и, где 1 с и и - целые положительные числа, причем, 1",сп, Сверточный кодер является дискретным автоматом с конечным числом состоянийн и полностью описывается диаграммои состояний сСостоянием кодера называется, содержимое трех правых регистров сдви" га. Диаграмма состояний содержит все возможные переходы кодера из одного состояния в другое (Фиг.5), Решетчатая диаграмма сверточного кода является разверткой диаграммы состояний во времени (Фиг,6, На решетке, Ь.состояния показаны узламк а переходы - ветвями Количество узлов на одном шаге решетчатой ди-.метрики записываются в блок 8 памяти метрцк. Во избежание переполнения ячеек блока 8 про 11 звадцтся нормализация путем вычитания цх значений метрики фиксированного числа. Прц превышении метрикой одного из узлов заданного 11 арога блок 7 нормированного порога фиксирует запрос на нормализацию и выполняет ее ца следующем шаге по решетке. Поскольку вьиитанце числа эквивалентно прибавлению дополнительного кода этого числа, то для выполнения нормализации используются старшие разряды первых входов сумматоров 2 (третьи выходы), на которые блоком 7 нармцрав 11 наго порога выдается дополнительный кад числа, вычитаемаго цэ метр:1 к. На следующем после нормализации шаге па решетке запросы на нормализацию игнорируются. Такая схема, храме уме 11 ьле.1 Ил лпп 13 рс.турых затрат позволяет ус 1 ень 11 п 1 ть время необходимое на обработку ад 1 аго узла решетки, за счет одновременного сложения метрик и выполнения нормализации, Это позволяет скампенсировать потери в аыстрадействцц, вызванные отказом ат параллельной обработки дгух узлов решетки.Блок 8 памяти метрцк разделен на две части, одна цэ котарьо:. служит для хранения ц считывания 1 и 1 фармации, а другая - для за 1.иси и хр)ненця, При каждом,э;ге па ре,пет 11 е абе части абменцвг дтся своими Функциями. Для асуществленця гарвллельнага досту- Г;. К ДВУЬ. ЯЧЕПКаМ ПРЦ Сч 1:.ТЬВац 11 Ц часть блока Ь памяти метрик, служащая для хра:1 енця и считывания, разделяется на две части. На выходах первого коммутатора 4метрики ветг,ей существуют в гиде 45 логической информации а переходах( й - верхний п 5 ть, 1 - нижний)па решет-.атой диаграмме свертачнагокада, Иэ рассматре 1 гия:ррагмента решетчетой диаграммы для двоцчвь 1 х сверточных кодов са скоростями 1/11, гдеи1,3"(фцг,б), видно, чтоадреса, узлов на.предыдущем (при движении слева напарво) шаге по решетке могут быть получены цз адреса уэ ла на последующем шаге путем сдвигавправо двоичнсга кода адреса узла иподстановкой в освободившийся старший разряд информации о переходе( сйч чти и 1 ц) 5 1 б 12378саграммы равно Я=2(К). После каждого перехода из одного состояния вдругое происходит смещение на одиншаг вправо1.Устройство работает следующим образом.Из принимаемой и канала связипоследовательности Т(В) выделяютсяМдве последовательности Т 1(0) и Т 2(0)ф 10которые триадами поступают с входа18 на блок 1 вычисления метрик ветвей. Кроме того на вход 19 поступают тактовые импульсы с частотой Рв два раза ниже, чем канальная частота последовательности Т(Р), и в15фазе, соответствующей правильномуразделению последовательности Т(0)па последовательности Т 1(П) и Т 2(П),Блок 17 тактовой синхронизации в 20течение одного импульса Р 1 формирует на своем первом выходе 27 пакетиз И тактовых импульсов Р а натвтором выходе 28 в . импульс концацикла, которые используются совместно с импульсами Р 1 для синхронизации остальных блоков устройства,На входы блока 1 вычисления метрик ветвей поступают триадами решения, вынесенные демодулятором а пере-данных двух канальных символах соотФ,вественна из последовательностейд11(Э) и Т 2(0), На вторые входы блока поступают двацчнь;е триады с кодеров 9.1 и 9.2, представляющие собойзначения ветвей ресцетчатай диаграммы,задаваемые формирователем 10 адресовсчитывания, На первых выходах блока1 вычисления метрик ветвей формируются значения приращений метрцк, пропорциональные логариФмической функцииправдоподобия принятой кодовой ветви и каждой цз ветвей, соответствующей на решетчатой диаграмме поступлению нулевого символа. На вторыхвыходах блока 1 вычисления метрцк ветвей Формируются значения приращенияметрик, соответствующие поступлениюединичного инФормационного символа,Выходы блока 1 вычисления метрик ветвей подключены к входам сумматоров 2.2.1 и 2.2, вторые входы которых подключены к входам блока 8 памяти метрикеРезультаты сложения с выходов сумматоров 2,1 и 2,2 подаются на входыблока 3 сравнения, где осуществляется сравнение двух метрик, и дальшена первый коммутаторв 4. "Выжившие"161237 Продвигаясь по решетчатой диаграмме слева направо, декодер отбрасывает полонину ветвей, входящих вузел, и решетчатая диаграмма приобретает соответствующий вид (Фиг,7),йричем в каждый узел входит толькоОдна ветвь. Информация о переходахйодается на управляющий вход блока 14памяти путей,1 ОФормирователь 12 адресов памяти путей формирователь 13 памяти путеййрослеживания путей, обеспечквающиеподключение соответственно старшихи младших разрядов адреса коммутато1 ы 5 и б, блок 14 памяти путей, блок15 прослеживания, путей и решающийблок 16 образуют модуль прослеживанияпутей и обеспечивают хранение информации о переходах по решетчатой диаг- Оамме и прослеживание непрерывногоПути. Поскольку достаточным является прослеживание.на глубину Ь ==/5-6)К, танеобходимо хранение информации о переходах через И = 2 "25узлов на длине Ь шагов, Хранение информации о переходах осуществляется в блоке 14 памяти путей, адресноепространство которого организованов виде адресного кольца длинойЧ(Фиг.8), При такой организации нетнеобходимости выполнять сдвиг инфозмации на длине Ь, а модифицируется топько адрес текущего шага по решетчатойдиаграмме. 35Таким образом, блок 14 памяти путей может быть выполнен на одноймикросхеме ОЗУ, чта позволяет сократить количества микросхем по сравнению с известным устройством в Л К раз.4 ОАдрес перехода в решетчатой диаграмме состоит из адреса узла, в который выполнен переход (младшая часть),и адреса шага по решетчатой диаграмме (старшая часть) (Фиг.7), При зтамобъем памяти путей, необходимый дляхранения информации о переходах, составляет М = Ьф Б бит, При записи решений последовательно перебираются адреса узлов формирователем 11 адреса 1;Озаписи и адреса шагов по решетчатойдиаграмме Формирователем 12 адресапамяти путей, Решения записываются вблок 14 памяти путей по полученномуадресу перехода, который передаетсячерез коммутаторы 5 и 6 (старших имладших разрядов памяти путей).Прослеживание непрерывного путипроизводится справа налево по решетча 8 Ятой диаграмме. Адрес. узла, из кото- рого сделан переход к данному узлу, формируется блокам 15 прослеживания путей представляющим собой регистр сдвига, на вход которого поступает информация с выхода блока 14 памяти путей. Адрес узла на предыдущем шаге, сформированный блоком 15 прослеживания путей, подается через коммутатор 5, (младшие разряды адреса памяти путей) па первые адресные входы блокапамяти путей. Считанная с блока 14 информация поступает на вход блаха 15 прослеживания путей,. который Формирует навык адрес узла (Фиг,7), Прн прослеживании путей адреса шагов по решетчатой диаграмме перебираются Формирователем . 13 адресов прослеживания путей, начиная с текущего адреса записи, в обратном направленич, для чего в начале прослеживания текущий адрес переписывается из Формирователя 12 адресов памяти путей в формирователь 13 адресов прослеживания путей.Паскальк 7 в конце прослеживания непрерывного пути на глубину Ь шагов на выходе сдвигавога регистра блока 15 присутствует информация о Ксамых старых переходах, зта информация выдается на решающий блок 16, как решение декодера, Решающий блок ,6, выход которого является выходом устройства, в течение Кинформационных тактов Гл преобразует решение декодера из параллельного кода в паследоват ельньй.Прослеживание непрерывнога путч ведется синхронно с записью решений, причем за время обработки одного узла решетчатой диаграммы производится адин шаг прослежлвация и запись решения,Так как прслеживание ьдется в течение Кинформационных тактов Р 1,а в течение одного информационноготакта Гобрабатывается последовательно И узлов, то длина прослеживаниясоставляет Ь =- Л.(К) = (К)" 2 шагав, что удовлетворяет условию Ь(5-6) К при К ) 4.Предлагаемое устройство па сравнению с известным более простое при сохранении быстродействия что достигается аднавременньи выполнением сложения метрик и нормализации и реализации блока 14 памяти. путей на одной микросхеме ОЗУ, Указанные техничес9 161237 кие решения обеспечивают тем больший выигрыш в упрощении предлагаемого устройства по сравнению с известным чем больше длина кодового ограниче" ния используемых кодов.5Практически устройство рассчитана на использование сверточных кодов с длиной кодового ограничения в диапазоне от 4 до 8.10 Формула изобретения 1. Устройство для декодирования сверточного кода, содержащее блок вы 15 числения метрик ветвей, информационньй вход которого является информационным входом устройства, формирователь адресов считывания, первые и вторые выходы которого соединены с вхо О дами соответственно первого и второго кодеров, выходы которых подключены соответственно к первым и вторым адресным входам блока вычисления метрик, ветвей, первые и вторые выходы кото рого соединены с первыми входами соответственно первого и второго суммато- ров, выходы которых подключены соответственно к первым и вторым информационным вхопам первого коммутатора и к первым и вторым входам блока сравнения, выход которого соединен с управляющим входом первого коммутатора, формирователь адресов записи, выходы которого и третьи выходы формирователя адресов считывания подключены к первым и вторым адресным входам блока памяти метрик, первые и вторые выходы которого соединены с вторыми входами соответственно первого и второго сумматоров, блок нормированного порога, входы которого объединены с информационными входами блока памяти метрик, блок памяти путей, второй и тре- . тий коммутаторы, о т л и ч а ю щ е - е с я тем, что, с целью упрощения,45 в устройство введены формирователь адресов памяти путей, формирователь адресов прослеживания путей, блок прослеживания путей, решающий блок и блок тактовой синхронизации, вход синхронизации которого объединен с входом формирователя адресов памяти путей и входом синхронизации решающего блока и является входом синхронизации устройства, выходы первого ком 55 мутатора соединены с входами блока нормированного порога, выходы которого подключены к третьим входам сумма 8 1 Оторов, первый выход блока тактовойсинхронизации соединен со счетнымвходом формирователя адресов прослеживания путей, тактовыми входами блокапрослеживания путей, блока памяти путей, второго и третьего коммутаторови входами формирователя адресов считывания и формирователя адресов записи,второй выход блрка тактовой синхронизации подключен к. управляющему входуФормирователя адресов прослеживанияпутей, управляющие входы блока тактовой синхронизации объединены с первыми информационными входами второгокоммутатора и подключены к выходамформирователя адресов записи, выходы Формирователя адресов памятипутей соединены с первыми информационными входами третьего коммутатораи установочными входами формирователя адресов прослеживания путей, первые и вторые выходы которого подключены соответственно к вторым информационным входам третьего коммутатора иуправляющему входу решающего блока,выходы второго и третьего коммутаторов соединены с первыми и вторыми адресными входами блока памяти путей,упгавляющий вход которого подключен квыходу блока сравнения, выход блокапамяти путей соединен с информационньг". входом блока прослеживания путей,вьходы которого подключены к вторыминформационным входам второго коммутатора и информационным входам решающего блока, выход которого являетсявыходом устройства.2. Устройство по п.1, о т л и - ч а ю щ е е с я тем, что блок тактовой синхронизации содержит генератор тактовых импульсов, делитель частоты, первый и второй триггеры и элемент И-НЕ. вкоцы которого являются управляющими входами блока, выход элемента И-КЕ соединен с тактовым входом второго триггера, тактовый вход первого триггера является входом синхронизации блока, выход генератора тактовых импульсов подключен к счетному входу делителя частоты, выход которого является первым выходом блока, выход первого триггера соединен с установочньм входами делителя частоты и второго триггера, выход которого подключен к установочному входу первого триггера и является вторым выходомблока.1612378 23. Устройство по п.1, о т л и - входов формирователя, остальные разч, а ю щ е е с я тем, что формиро- ряды установочных входов счетчика имватель адресов прослеживания путей пульсов являются одноименными разсодержит триггер, элемент И и счет- рядами Установочных входов форьЩРовачик импульсов, счетный вход которого 5 теля, второй вход элемента И является объединен с тактовым входом триггера управляющим входом формирователя, выи является счетным входом формирова- ход элемента И подключен к управляющетеля, первые входы элемента И соот- му входу счетчика импульсов и установетственно объединены с младшими раз- вочному входУ триггера, выходы счет- о рядами установочных входов счетчика чика импульсов и триггера являются соимпульсов и являются соответствующн- ответственно первым и вторым выходами младшими разрядами установочных ми формирователя.Ф