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

(11) 1839281 А 1 9) Я 11) ИСАНИЕ ИЗОБРЕТЕН ститут точны нои техх переие досвия уст ветвей, счетчик, й элеИ СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИ СУДАРСТВЕННОЕ ПАТЕНТНОЕЕДОМСТВО СССР (ГОСПАТЕНТ СССР) АВТОРСКОМУ СВИДЕТЕДЬС(54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНСВЕРТОЧНОГО КОДА(57) Изобретение относится к вычислительнике и может быть использовано в системадачи данных Цель изобретения - ловышентаверности декодирования и быстродейстройства Устройство для декодирования свного кода содержит вычислитель метрикл-входовой компаратор, элемент задержки,дешифратор, триггер, первый, второй и трет 2менты И, блок сравнения, блок памяти, блок вентилей, и каналов обработки, каждый из которых включает первый и второй сумматоры, колпаратор, регистр веса узла, мультиплексор, регистр памяти пути, информационный вход, тактовый вход вход начальной установки, тактовый выход, информационный выход, выход "Достоверно", За счет введения элемента задержки, счетчика, дешифратора, триггера блока сравнения, блока памяти, лервого, второго и третьего элементов И, блока вентилей и их взаимосвязей обеспечивается высокая достоверность выдаваемой информации за счет стробирования выхода устройства на время декод,рованил контроля процесса декодирования и выдачи лотребителю сигнала о достоверности выдаваелтой декодированной информации и сокращается интервал декодирования. 5 ил.1839281 оставитель Б,Гришиехред М.Уоргентад рректор М.Самборская едактор Т,Юрчиков Тираж НПО "Поиск" Роспатента13035. Москва, Ж, Раушская наб каз 340 писно инд 101 Производственно-издательский комбинат "Патент", г. Ужгвый, второй и третий элементы И, блок вентилей, информационные входы которого соединены с первыми входами блока сравнения и с выходом и-входооого компэратора, при этом вход устройства "Начальная установка" соединен с Й входами регистров веса узла и памяти пути в каналах обработки, с Н-входами триггера и счетчика, выходы которого соединены с входами дешифратора, управляющий вход блока вентилей соединен с первым выходом дешифратора, второй выход которого соединен с Я-входом триггера, тактовый выход устройства соединен с выходом первого 15 элемента И, первый вход которого соединенс первыми входами второго и третьего элементов И и с выходом триггера, второй вход первого элемента И соединен с тактовым входом устройства, тактовым входом счет чика и входом элемента задержки, выходкоторого соединен с тактовыми входами регистров веса узла и памяти пути в каналах обработки, выход блока памяти соединен с вторыми входами блока сравнения, выход которого соединен с вторым входом третьего элемента И, выход третьего элемента И соединен с выходом "Достоверно" устройства, информационный выход устройства соединен с выходом второго элемента И, 30 второй вход которого соединен с Ь-м разрядом (Ь =- 4-6)К) регистра памяти пути одного иэ каналов обработки, выход блока вентилей соединен с третьими входами первого и второго сумматоров в каждом канале обра 35 50 Изобретение относится к вычислительной технике и может быть использовано всистемах перед и данных,Известно устройство для декодирования сверточного кода, содержащее корреляторы, и-входооой компаратор, два регистра,элемент ИЛИ, блок синхронизации и п,каналов обработки. Каждый из которых включаетв себя первый и второй сумматоры, регистрпамяти, компаратор, реверсивный сдвиговый регистр, первый и второй элементы И,элемент ИЛИ, элемент НЕ и триггер с ихвзаимосвязью. Известное устройство имеетнизкие быстродействие и достоверностьвыдаваемой информации.Наиболее близким к изобретению является устройство для декодирования сверточного кода, содержащее корреляторы,и-входовой компаратор, элемент ИЛИ, двасдвиговых регистра и и каналов обработки,в каждый из которых входят регистр памяти,два сдвиговых регистра, два сумматора,компаратор, реверсивный регистр, доатриггера, два элемента НЕ, четыре элементаИ, два элемента ИЛИ, пять коммутаторов сих взаимосвязью. Известное устройствоимеет низкое быстродействие из-за большого интероала декодирования информации и низкую достоверность выдаваемойдекодированной информации.Цель изобретения - повышение достоверности выдаваемой информации и повышение быстродействия устройства путемсокращения интервала декодирования.Цель достигается тем, что в устройстводля декодирования соерточного кода 1 содержащее и каналов обработки (и =- 2, К -величина кодового ограничения), вычислитель метрик ветвей, вход которого соединенс информационным входом устройства; ивходовой компаратор. входы которого соединены с выходами регистров веса узлаканалов обработки, причем каждый каналобработки включает в себя первый и второйсумматоры, регистр веса узла, регистр памяти пути, компаратор, информационныйвыход которого подключен к информационному входу регистра овса узла, первый ивторой входы компаратора подключенысоответственно к выходам первого и второгосумматоров, первые входы которых соединены с выходами регистров веса узла каналов обработки в соответствии с решетчатойдиаграммой сверточного кода, выходы вычислителя метрик ветвей подключены к вторым входам сумматоров в каналахобработки в соответствии с порождающимиполиномами сверточного кода, введеныэлемент задержки, счетчик, дешифратор,триггер, блок сравнения. блок памяти, перботки, в каждый канал обработки введен мультиплексор, первые и вторые входы которого соединены с выходами первых (В) разрядов регистров памяти пути каналов обработки в соответствии с решетчатой диаграммой сверточного кода, управляющий выход компаратора соединен с управляющим входом мультиплексора, выход которого соединен с информационными (от первого до В-го) входами регистра памяти пути, нулевой информационный вход регистров памяти пути каналов обработки соединен с нулевым или единичным сигналом в соответствии с решетчатой диаграммой сверточного кода,Нэ фиг. 1 и 2 показана функциональная схема устройства для декодирования соерточного кода при кодовом ограничении К = =3; на фиг, 3 - схема кодера, формирующего используемый в рассматриваемом устройстве сверточный код, пример: нэ фиг, 4 - решетчатая диаграмма сверточнпго кода; нэ фиг. 5 - временные ди,згрлг. лы гипллов устройства,Устройства овдбр.мю Рик оетнР 1, и Г:элемент 3 задержки, счетчик 4, дешифратор 5, триггер 6, элементц И 7. 8, 9, блок 10 сравнения, блок 11 памяти, блок 12 вентилей, каналы 13 обработки, входы 14, 15, 16, выходы 17, 18, 19, сумматоры 20, 21, компараторы 22, регистры 23, мультиплексоры 24, регистры 25,Вход вычислителя 1 метрик ветвей соединен с информационным входом 14 устройства, входы и-входового компаратора 2 соединены с выходами регистров 23 веса узла каналов 13 обработки. Информационный выход компаратора 22 подключен к информационному входу регистра 23 весаузла, первый и второй входы компаратора 22 подключены соответственно к выходам первого 20 и второго 21 сумматоров, первые входы которых соединены с выходами регистров 23 веса узла каналов 13 обработки в соответствии с решетчатой диаграммойсверточного кода. Выходы вычислителя 1 метрик ветвей подключены к вторим входам первого 20 и второго 21 сумматоров в каналах обработки в соответствии с порождающими полиномами сверточного кода, Информационные входы блока 12 вентилей соединены с первыми входами блока 10сравнения и с выходом и-входового компэратора 2. Вход 16 "Начальная установка" устройства соединен с В-входами регистров23 веса узла и 25 памяти пути в каналах 13 обработки, с В-входами триггера 6 и счетчика 4, выходы которого соединены с входамидешифратора 5, Управляющий вход блока 12 вентилей соединен с первым выходом дешифратора 5, второй выход которого соединен с 3-входам триггера 6, Тактовый выход 17 устройства соединен с выходомпервого элемента И 7, первый вход которогосоединен с первцми входами второго 8 и третьего 9 элементов И и с выходом триггера 6, Второй вход первого элемента И соединен с тактовым входом 15 устройства,тактовым входом счетчика 4 и входам элемента 3 задержки, выход которого соединенс тактовыми входами регистров 23 веса узла и 25 памяти пути в каналах 13 обработки.Выход блока 11 памяти соединен с вторымивходами блока 10 сравнения, выход которого соединен с вторым входом третьего элемента И 9, Выход третьего элемента И соединен с выходом 19 "Достоверно" устройства. Информационный выход 18 устройства соединен с выходом второго элемента И 8, второй вход которого соединен с Ь-разрядом (В = 4-6 К) регистра 25 памяти пути одного из каналов обработки. Выход блока 12 вентилей соединен с третьими входами первого 20 и второго 21 сумматоров в каждом кэнале 13 обработки, Вкаждом канале обработки первые и вторые входы мультиплексора 24 соединены с выходами первых(В - 1) разрядов регистров 25 памяти пути каналов обработки л соответствии с решетчатой диаграммой сверточного 15 20 25 кода, управляющий выход компараторэ 22 соединен с управляющим входом мультиплексора 24, выход которого соединен с информационными (от первого до В-го) входами регистра 25 памяти пути, Нулевой информационный вход регистров 25 памяти пути каналов обработки соединен с нулевым или единичным сигналом в соответствии с решетчатой диаграммой сверточного кода.Сверточный код, поступающий через приемник на вход; стройства для декодирования, формируется кодером на передающей стороне канала связи, Закон формирования кодовых символов задается образующими многочленами кода, по которым строится схема кодера. Схема кодера простейшего сверточного кода с длиной кодового ограничения К = 3 и образующими многочленами О 1 = 1 + Х + Х и 02 = 1 + Х приведена на фиг. 3 Каждый многочлен определяет схему подключения с, мь;э-,оров 26 по модулю двэ к определенным раэ,:ядам регистра 27 сдвига.Процесс формирования кодовой после довэтельности сдвиговым регистоом отражается решетчатой диаграммой сверточного кода, приведенной на фиг. 4, которая используется при декодировании; На этой диаграмме каждолу узлу (А - состояние 00, В - состояние 01, С - состояние 10, Р - состояние 11) соответствует определенное состояние (К - 1) левых разрядов сдвигового регистра 27, каждому переходу из состояния в состояние (каждому информационномусимволу 1 и О) соответствует определенная комбинация из двух кодовых символов на вцходе кодера - ребро (ветвь) решетки: 00, 01, 10, 11, При движении по решетчатой диаграмме сверточнаго кода слева направо в устройстве для декодирования сверточного кода вычисляется расстояние между поступающими на вход информационными символами и всеми возможными группами символов, образующих один постоянно повторяющийся шэ решетки. На каждом шаге кодовые расстояния очередных символов складываются с накопленными до этого шага кодовыми расстояниями(метрикой или весом узла), после чего в каждом узле решетки производится сравнение кодового расстояния путей, входящих в данный узел, и выбор пути с наимвч,шим кодовым расстоянием (наименьшей метрикой или наименьшим весом узла), В 1 пэн 1839281ная метрика запоминается как метрика данного узла и используется на следующем шаге декодирования. Таким образом, накаждом шаге половина конкурирующих путей отбрасывается и при следовании по решетке на достаточную глубину В (4-6)К"выживает" один максимально правдоподобный путь с минимальной метрикой, Прослеживание выживших путей на глубину В"(4-6)К считается достаточным.Устройство для декодирования сверточного кода работает следующим образом.На вход 16 поступает сигнал "Начальная установка" (фиг. 5, Т 1), по которому устройство устанавливается в исходноесостояние, в частности в регистры веса узлов 23 И памяти путей 25 всех каналов 13обработки записывается нулевая информация, счетчик 4 и триггер б устанавливаютсяв исходное состояние, при этом запрещается через первый 7, второй 8 и третий 9 элементы И выдача всех выходных сигналов сустройства. По окончании сигнала "Начальная установка" устройство готово к приемуинформационного сообщения.Последовательность символов с информационного входа 14 синхронно с тактами навходе 15(фиг,5, Т 2) поступает на входы вычислителя 1 метрик ветвей (фиг. 5, Б, Тб), где длякаждой пары символов вычисляются метрикиветвей Л ОО,Л 10,Л 01,Л 11,Вычисленные метрики ветвей в двоичном коде подаются в и каналов 13 обработки(13,1 - канал А, 13,2 - канал В, 13.3 - каналС, 13.4 - канал О) на сумматоры 20, 21, Вкаждом канале обработки в соответствии срешетчатой диаграммой сверточного кода,изображенной на фиг. 4, переходу иэ состояния ОО в состояние 00 соответствует паравходных символов С 1 = О, С(1+1) = О, переходуиз состояния ОО в состояние 10 соответствуетпара входньх символов С 1 = 1, С(1+1) -1 и т,д.Значения С 1 и С(1+1),соответствующие переходам в решетчатой диаграмме сверточногокода, равны С 1 = (А 1 + А(1 + 1) + А(1 + 2), С(1 ++1) А 1 + А(1+ 2) (см, фиг. 3 и 4).Так как каждый канал 13 обработки соответствует одному из состояний кодера, тона входы сумматоров 20, 21 каждого канделаобработки поступают значения метрик ветвей Л ОО, Л 10, Л 01, Л 11 с вычислителя 1метрик ветвей, в котором хранятся в качестве эталонных соответствующие значения С 1и С(1+ 1),Из блока 1,1 вычислителя 1 метрик ветвейс эталоном 00(в котором С 1- О, С(1+.1) - 0)значения метрики Л ОО поступают в соответствии с обозначением ветвей решетчатойдиаграммой сверточногс кода на сумматор20 канала А и сумматор 21 канала В. Иэблока 1.2 вычислителя метрик ветвей с эталоном 01 (в котором С 1 =- 1; С(1 + 1) 0) значения метрики Л 10 поступают на сумматор 20 канала С и сумматор 21 канала О. Иэ блока 1.3 вычислителя метрик ветвей с эталоном Л 10 (в котором С 1 - О, С(1+ 1) = 1)значения метрики Л 01 поступают на сумматор 21 канала С и сумматор 20 канала О. Из блока 1.4 вычислителя метрик ветвей С эта лоном 11(в котором С 1 = 1, С 1 -1) значенияметрики. Л 11 поступают на сумматор 21 канала А и сумматор 20 канала В.В сумматорах 20 и 21 каждого канала 13обработки происходит сложение значенийЛ ОО, Л 10, Л 01. Л 11 с вычисленными значениями метрик состояний (веса узлов), поступающих из регистров 23 веса узлов каналов обработки в соответствии с решетчатой диаграммой сверточного кода. Вес узго3050 ла из регистра 23 канала А поступает насумматоры 20 каналов А и В, вес узла из регистра 23 канала В - на сумматоры 20 каналов С и О, вес узла из регистра 23 канала С - на сумматоры 21 каналов А и В, весузла из регистра 23 канала О - на сумматоры 21 каналов С и О.В каждом канале обработки вычисленные сумматорами 20 и 21 значения метрик состояний (веса узлов) поступают на компараторы 22, в которых иэ двух значений метрик выбирается меньшее, передается на информационные входы регистров 23 веса узлов и записывается в них в качестве новых метрик веса узлов по входу с тактовымисигналами, поступающими с тактового входа 14 через элемент 3 задержки (фиг. 5, ТЗ). Величина задержки тз элемента задержки должна быть Ттз1 р, где Т - длительность периода вхОдных тактовых импульсов; 1 р - .максимальное время задержки сигнала сум-, матором и компаратором в канале обработки,Соединение выходов регистров 25 памяти пути с входами мультиплексоров 24 вканалах 13 обработки соответствует связям между узлами решетчатой диаграммы сверточного кода (фиг. 4), На вход Х мультиплексора 24 канала А поступает информация с первых (В) разрядов регистра памяти пути канала обработки А, а на вход У - информация с .первых (В - 1) разрядов регистра памяти пути канала С. На вхЬд Х мультиплексора 24 канала В поступает информация с первых (В - 1) разрядов регистрапамяти пути канала А, а на вход У - информация с первых(В) разрядов регистра памяти пути канала С. На вход Х мультиплексора 24 канала С поступает информация с первых (В) разрядов регистра памяти пути канала О, а нд н,.од у - ицфор 1839281 1020 25 30 40 50 мация с первых (В) разрядов регистра памяти пути канала В, На вход Х мультиплексорэ 24 канала О поступает информация с первых (В) разрядов регистра 25 памяти пути канала О, а нэ вход У - информация с первых(В) разрядов памяти канала В. Выходы мультиплексоров 24 соединены с информационными (01-ОВ) входами регистров памяти пути каналов 13 обработки.Одновременно с выбором меньшего значения метрики состояния узла комиаратор 22 каждого канала обработки. соответствующего одному из состояния кодера,формирует управляющий сигнал, по которому мультиплексор 24 разрешает передачу на информационные входы регистра 25 памяти пути своего канала обработки информацию памяти пути стого канала обработки, из регистра 23 веса узла которого информация после суммирования одним из сумматоров 20 или 21 с вычисленными значениями метрик передана компаратором 22 в свой регистр 23 веса узла, Запись информации в регистр 25 памяти пути осуществляется тактовыми сигналами (фиг. 4, ТЗ), поступающими с тактового входа 14 через элемент 3 задержки.Регистры веса узла 23 и памяти пути 25 являются элементами памяти на один такт и в них целесообразно использовать двухступенчатые триггеры, в которых информация в вспомогательный триггер записывается по фронту сигнала, а в основной триггер -по спаду сигнала.Таким образам, на каждом такте на входах мультиплексоров 24 каждого канала 13 обработки присутствуют два пути, а записываются в регистры 25 памяти пути каждый раз только один путь с наименьшим весом узла в зависимости от сигнала на Ч-входе мультиплексора. Через каждый мультиплексор 24 проходит путь, выживший на данном этапе.В соответствии с решетчатой диаграммой сверточного кода (фиг, 4), по которой любые метрики ветвей, входящие в узел А или В и узел С, декодируются как "0", а любые метрики ветвей, входящие в узлы В и О, декодируются как "1". На каждом такте обработки узлов в первые разряды регистров 25 памяти пути каналов 13.1 (канал А) и 13.3 (канал С) записывается логический "0", а в первые разряды регистров 25 каналов 13.2 (канал В) и 13.4 (канал О) - логическая "1".Таким образом, в регистрах 25 памяти пути каналов обработки по каждому такту происходит стирание "умерших" путей и запись "выживших" путей. Через В =-(4 - 6)К входных тактов в кана-лах обработки выживают самые "старые"пути, которые являются наиболее правдоподобными по решетчатой диаграмме соерточного кода, и в каждом регистре 25 памятипутей в В-м разряде находится одинаковаяинформация. Поэтому выходную декодированную информацию можно выдавать с В-горазряда регистра 25 памяти пути. любогоканала обработки, в частности в нашем примере информация снимается с В-го разрядарегистра памяти пути канала А.Из-за искажения входной информациии связанного с нжи непрерывного роста метрик веса узлов для исключения переполнения регистров 23 веса узлов и сумматоров20, 21 в устройстве осуществляется нормализация, заключающаяся в следующем.В процессе декодирования инфо мация из регистра 23 веса узлов всех кана,;:13 обработки поступает на и-входовой ко - тпаратор 2, на выход которого передаетсяминимальная метрика веса узла с одного изп его входов. Через М входных тактов спомощью счетчика 4 и дешифратора 5 вы ,батывается длительностью, равной перио,цтвходных тактовых импульсов, строб нормирования(фиг,5, 17), который разрешаетпрохождение минимальной метрики веса узла свыхода и-входового компаратора 2 черезблрк 12. вентилей на сумматоры 20, 21, гдеона вычитается одновременно из регистров23 веса узлов всех каналов обработки.Одновременно с декодированием информации осуществляется формированиесигнала достоверности, который вырабатывается блоком 10 сравнения в результатесравнения минимальной метрики веса узлас выхода и- входовога компэратора 2 с заранее выбранным пороговым значением метрики веса узла, задаваемым блоком 11 памяти,Через В входных тактов после сигнала"Начальная установка" с помощью счетчика4 и дешифратора 5 вырабатывается сигнал,по которому триггер 6 устанавливается еединичное состояние (фиг. 5, Т 8) и разрешает выдачу декодированной информации сВ-разряда регистра 25 памяти пути черезвторой элемент И 8 на информационныйвыход 18 (фиг, 5, Т 10), тактовых импульсов стактового входа 15 через первый элвл 1 ент И7 на тактовый выход 17 (фиг. 5, Т 9) и сигнала"Достоверно" с выхода блока 10 сравнениячерез третий элемент И 9 на выходц "Достоверно" (фиг, 5, Т 1 1),(56) Авторское свидетельство СССРМ 675616, кл. Н 03 М 13/12, 1977,Патент США М 3789360, кл. Н 01 ; /101974.Формула изобретения дешифратора, первый и второй выходы которого подключены соответственно к упУСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ Равляющему входу блока ключей и Я-входутриггера, выход. которого подключен ко СВЕРТОЧНОГО КОДА, содержащее вычис-второму входу первого элемента И и перлитель метрик ветвей, вход которого являвым входам второго и третьего элементовется информационным входом устройСтва И, выходы которых являются соответствен. и-входовый компаратор (п=2, К-величи- но информационным и тактовым выходамина кодового ограничения) и и каналов об- устройства, а каждый канал обработки ввеработки, каждый иэ которых включает а ден мультиплексор, управляющий вход и,10себя регистр. памяти пути, пеРвый и втОРОЙ выходы .которого подключены соответстсумматоры, выходы которых подключены венно к управляющему выходу компаратосоответственно к первым и вторым входам ра и входам первого - В-го (где В - 4 - 51) компаратора этого канала обработки, ин разрядов регистра памяти пути этого канаформационнцй выход компаратора под- ла обработки. й-вход триггера объединен с ключен к информационному входу Й-входами счетчика импульсов и я-входами регистра веса узла этого канала обработки, регистра веса узла и регистра памяти пути выходы регистров веса узла 1-го канала об- каждого канала обработки и является вхоработки (1=1;и) подключены к 1-м входам 20 дом начальной установки устройства, втои-входового компаратора и первым входам: рой вход второго элемента И подключен к первого и второго сумматоров каналов об- . выходу В-го разряда регистра памяти пути работки в соответствии с решетчатой диаг- соответствующего канала обработки, вцхораммой сверточного кода, выходы ды блока ключей соединены с третьими вычислителя метрик ветвей подключены ко 25 входами первого и второго сумматоров вторым входам сумматоров а каналах об-каждого канала обработки, вход элемента работки в соответствии с порождающими задержки объединен со вторым входом полиномамисаерточногокода,отличающе- третьего элемента И и тактовым входом еся тем,что,с целью повышения достовер- счетчика импульсов и является тактовым ности декодирования и быстродействия 30 входом устройства, выход элемента задерустройства, в него введены триггер, де- жки подключен к С-входам регистра веса шифратор, счетчик импульсоа, элементы узла и регистра памяти пути каждого кана- задержки, блок сравнения, блок памяти, ла обработки, выходы первого - (В - 1)-го блок ключей и первый - третий элементы разрядов регистра памяти пути каждого И, выходы и-входового компаратора под канала обработки подключены к первым и ключены к информационным входам блока вторым информационным входам мультик ключей и первым входам блока сравнения, плексоров каналов обработки в соответствторца входц и выход которого подключе- . аии с решетчатой диаграммой свертачного нц соответственнок выходам блока памя- када, вход нулевого разряда регистра пати и первому входу первого элемента И,мяти пути каждого канала обработки под 40выход которого является выходом "Досто-ключен к шине нулевого или единичного верно" устройства, выходы счетчика им- потенциала в соответствии с решетчатой, пульсов соединены со входами диаграммой сверточного кода.45