Устройство для декодирования сверточного кода Советский патент 1993 года по МПК H03M13/12 

Изобретение относится к вычислительной технике и может быть использовано в системах передачи данных.

Известно устройство для декодирования сверточного кода, содержащее корреляторы, n-входовой компаратор, два регистра, элемент ИЛИ, блок синхронизации и п-кана- лов обработки. Каждый из которых включает в себя первый и второй сумматоры, регистр памяти, компаратор, реверсивный сдвиговый регистр, первый и второй элементы И, элемент ИЛИ, элемент НЕ и триггер с их взаимосвязью. Известное устройство имеет низкие быстродействие и достоверность выдаваемой информации.

Наиболее близким к изобретению является устройство для декодирования сверточного кода, содержащее корреляторы, n-входовой компаратор, элемент ИЛИ, два сдвиговых регистра и п каналов обработки, в каждый из которых входят регистр памяти, два сдвиговых регистра, два сумматора, компаратор, реверсивный регистр, два триггера, два элемента НЕ, четыре элемента И, два элемента ИЛИ, пять коммутаторов с их взаимосвязью. Известное устройство имеет низкое быстродействие из-за большого интервала декодирования информации и низкую достоверность выдаваемой декодированной информации.

Цель изобретения - повышение достоверности выдаваемой информации и повышение быстродействия устройства путем сокращения интервала декодирования.

Цель достигается тем, что в устройство для декодирования сверточного кода, содержащее п каналов обработки (п 2 , К - величина кодового ограничения), вычислитель метрик ветвей, вход которого соединен с информационным входом устройства, п- аходовой компаратор, входы которого соединены с выходами регистров веса узла каналов обработки, причем каждый канал обработки включает в себя первый и второй сумматоры, регистр веса узла, регистр памяти пути, компаратор, информационный выход которого подключен к информационному входу регистра веса узла, первый и второй входы компаратора подключены соответственно к выходам первого и второго сумматоров, первые входы которых соединены с выходами регистров веса узла каналов обработки в соответствии с решетчатой диаграммой сверточного кода, выходы вычислителя метрик ветвей подключены к вто- рым входам сумматоров в каналах обработки в соответствии с порождающими полиномами сверточного кода, введены элемент задержки, счетчик, дешифратор, триггер, блок сравнения, блок памяти, первый, второй и третий элементы И, блок вентилей, информационные входы которого соединены с первыми входами блока сравнения и с выходом n-входового компаратора, при этом вход устройства Начальная установка соединен с R входами регистров веса узла и памяти пути в каналах обработки, с R-входами триггера и счетчика, выходы которого соединены с входами дешифратора, управляющий вход блока вентилей соединен с первым выходом дешифратора, второй выход которого соединен с S-входом триггера, тактовый выход устройства соединен с выходом первого

элемента И, первый вход которого соединен с первыми входами второго и третьего элементов И и с выходом триггера, второй вход первого элемента И соединен с тактовым входом устройства, тактовым входом счетчика и входом элемента задержки, выход которого соединен с тактовыми входами регистров веса узла и памяти пути в каналах обработки, выход блока памяти соединен с вторыми входами блока сравнения, выход

которого соединен с вторым входом третьего элемента И, выход третьего элемента И соединен с выходом Достоверно устройства, информационный выход устройства соединен с выходом второго элемента И,

второй вход которого соединен с b-м разрядом (Ь (4-6)К) регистра памяти пути одного из каналов, обработки, выход блока вентилей соединен с третьими входами первого и второго сумматоров в каждом -канале обработки, в каждый канал обработки введен мультиплексор, первые и вторые входы которого соединены с выходами первых (В-1) разрядов регистров памяти пути каналов обработки в соответствии с решетчатой диаграммсй сверточного кода, управляющий выход компаратора соединен с управляющим входом мультиплексора, выход которого соединен с информационными (от первого до В-го) входами регистра памяти

пути, нулевой информационный вход регистров памяти пути каналов обработки соединен с нулевым или единичным сигналом в соответствии с решетчатой диаграммой сверточного кода.

На фиг. 1 и 2 показана функциональная схема устройства для декодирования сверточного кода при кодовом ограничении К 3; на фиг. 3 - схема кодера, формирующего используемый в рассматриваемом устройстве сверточный код, пример: на Фиг. 4 решетчатая диаграмма сверточного кода; на

. фиг. 5 - временные диаграммы сигналов ус

с.одер: г; и-,, - ,

игил, 1 Нор 2.

элемент 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 Начальная установка устройства соединен с R-входами регистров

23 веса узла и 25 памяти пути в каналах 13 обработки, с R-входами триггера 6 и счетчика 4, выходы которого соединены с входами дешифратора 5. Управляющий вход блока 12 вентилей соединен с первым выходом дешифратора 5, второй выход которого соединен с S-входом триггера 6. Тактовый выход 17 устройства соединен с выходом первого элемента И 7, первый вход которого соединен с первыми входами второго 8 и третьего 9 элементов И и с выходом триггера 6. Второй вход первого элемента И соединен с тактовым входом 15 устройства, тактовым входом счетчика 4 и входом элемента 3 задержки, выход которого соединен с тактовыми входами регистров 23 веса узла и 25 памяти пути в каналах 13 обработки. Выход блока 11 памяти соединен с вторыми входами блока 10 сравнения, выход которого соединен с вторым входом третьего элемента И 9. Выход третьего элемента Л соединен с выходом 19 Достоверно устройства. Информационный выход 18 устройства соединен с выходом второго элемента И 8, второй вход которого соединен с b-разрядом (В 4-6 К) регистра 25 памяти пути одного из каналов обработки. Выход блока 12 .вентилей соединен с третьими входами первого 20 и второго 21 сумматоров в каждом -канале 13 обработки. В

каждом канале обработки первые и вторые входы мультиплексора 24 соединены с выходами первых (В-1) разрядов регистров 25 памяти пути каналов обработки п соответст- 5 вии с решетчатой диаграммой сеерточного кода, управляющий выход компаратора 22 соединен с управляющим входом мультиплексора 24, выход которого соединен с информационными (от первого до В-го)

0 входами регистра 25 памяти пути. Нулевой информационный вход регистров 25 памяти пути каналов обработки соединен с нулевым или единичным сигналом в соответствии с решетчатой диаграммой сверточного

5 кода.

Сверточный код, поступающий через приемник на вход стройстпз для декодирования, формируется кодером на передающей стороне канала связи. Закон

0 формирования кодовых символов задается образующими многочленами кода, по которым строится схема кодера. Схема кодера простейшего сверточного кода с длиной кодового ограничения К 3 и образующими

5 многочленами Q1 1 + X + X 2и Q2 1 ч- X2 приведена на фиг. 3 Каждый многочлен определяет схему подключении сумматоров 26 по модулю два к определенным разрядам регистра 27 сдвига.

0 Процесс формирования кодовой последовательности сдвиговым регистром отражается решетчатой диаграммой сверточного кода, приведенной на фиг. 4, которая используется при декодировании

5 На этой диаграмме каждому узлу (А - состояние 00, В -состояние 01, С-состояние 10, D - состояние 11) соответствует определенное состояние (К - 1} левых разрядов сдвигового регистра 27, каждому переходу из

0 состояния в состояние (каждому информационному/символу 1 и 0) соотретствует определенная комбинация из двух кодовых символов на выходе кодера - ребро (ветвь) решетки: 00, 01, 10, 11. При движении по

5 решетчатой диаграмме сверточного кода слева направо в устройстве для декодирования сверточного кода вычисляется расстояние между поступающими на вход информационными символами и всеми воз0 можными группами символов, образующих один постоянно повторяющийся шаг решетки. На каждом шаге кодовые расстояния очередных символов складываются с накопленными до этого шага кодовыми рэсстоя5 ниями (метрикой или весом узла), после чего в каждом узле решетки производится сравнение кодового расстояния путей, входящих в данный узел, и выбор пути с наименьшим кодовым расстоянием (наименьшей метрикой или наименьшим весом узла). ГЬ if -ранная метрика запоминается как метрика данного узла и используется на следующем шаге декодирования. Таким образом, на каждом шаге половина конкурирующих путей отбрасывается и при следовании по решетке на достаточную глубину В (4-6)К выживает один максимально правдоподобный путь с минимальной метрикой. Прослеживание выживших путей на глубину В (4-6)К считается достаточным.

Устройство для декодирования сверточ- ного кода работает следующим образом.

На вход 16 поступает сигнал Начальная установка (фиг. 5, Т1), пр которому устройство устанавливается в исходное состояние, в частности в регистры беса узлов 23 И памяти путей 25 всех каналов 13 обработки записывается нулевая информация, счетчик 4 и триггер 6 устанавливаются в исходное состояние, при этом запрещается через первый 7, второй 8 и третий 9 элементы И выдача всех выходных сигналов с устройства. По окончании сигнала Начальная установка устройство готово к приему информационного сообщения.

Последовательность символов с информационного входа 14 синхронно С тактами на входе 15 (фиг. 5, Т2) поступает на входы вычислителя 1 метрик ветвей (фиг. 5. Т5, Т6), где для каждой пары символов вычисляются метрики ветвей Л 00. Л 10, Л 01, Л 11.

Вычисленные метрики ветвей в двоичном коде подаются в п каналов 13 обработки (13.1 - канал А. 13.2 - канал В, 13.3 - канал С, 13,4 - канал D) на сумматоры 20, 21. В каждом канале обработки в соответствии с решетчатой диаграммой сверточного кода, изображенной на фиг. 4, переходу из состояния 00 в состояние 00 соответствует пара входных символов С1 -О, С(1+1)0, переходу из состояния 00 в состояние 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 каждого канала обработки поступают значения метрик ветвей Л 00, Л .10, Л 01, Л 11 с вычислителя 1 метрик ветвей, в котором хранятся в качестве эталонных соответствующие значения С1 и С(1 + 1).

Из блока 1.1 вычислителя 1 метрик кетвей с эталоном 00 (в котором С1 О, С(1 + 1) - 0) значения метрики Л 00 поступают я соответствии с обозначением ветвей решетчатой диаграммой свер.точногс кода на сумматор 20 канала А и сумматор 21 канала В. Из

блока 1.2 вычислителя метрик ветвей с эталоном 01 (в котором С1 1; С(1 + 1) 0) значения метрики Л 10 поступают на сумматор 20 канала С и сумматор 21 канала D. Из

блока 1.3 вычислителя метрик ветвей с эталоном Л 10 (а котором С1 О, С(1 + 1) 1) значения метрики Л 01 поступают на сумматор 21 канала С и сумматор 20 канала D. Из блока 1.4 вычислителя метрик ветвей С зта0 лоном 11 (в котором С1 1, С1 1) значения метрики Л 11 поступают на сумматор 21 канала А и сумматор 20 канала В.

В сумматорах 20 и 21 каждого канала 13 обработки происходит сложение значений

5 Л 00, Л 10, Л 01. Л 11 с вычисленными значениями метрик состояний (веса узлов), поступающих из регистров 23 веса узлов каналов обработки в соответствии с решетчатой диаграммой сверточного кода. Вес уз0 ла из регистра 23 канала А поступает на сумматоры 20 каналов А и В, вес узла из регистра 23 канала В - на сумматоры 20 каналов С и D, вес узла из регистра 23 канала С - на сумматоры 21 каналов А и В, вес

5 узла из регистра 23 канала D - на сумматоры 21 каналов Си D.:

В каждом канале обработки вычисленные сумматорами 20 и 21 значения метрик состояний (веса узлов) поступают на компа0 раторы 22, в которых из двух значений метрик выбирается меньшее, передается на информационные входы регистров 23 веса узлов и записывается в них в качестве новых метрик веса узлов по входу с тактовыми

5 сигналами, поступающими с тактового входа 14 через элемент 3 задержки (фиг. 5, ТЗ). Величина задержки гз элемента задержки должна быть Т гз tp, где Т - длительность периода входных тактовых импульсов; tp 0 максимальное время задержки сигнала сум-, матором и компаратором в канале обработки.

Соединение выходов регистров 25 памяти пути с входами мультиплексоров 24 в

5 каналах 13 обработки соответствует связям между узлами решетчатой диаграммы сверточного кода (фиг. 4). На вход X мультиплексора 24 канала А поступает информация с первых (В-1) разрядов регистра памяти пу0 ти канала обработки А, а на вход Y - информация с .переы.х (В-1) разрядов регистра памяти пути канала С. На вход X мультиплексора 24 канала В поступает информация с первых (В-1) разрядов регистра

5 памяти пути канала А, а на вход Y - информация с первых (В-1) разрядов регистра памяти пути канала С. На вход X мультиплексора 24 канала С поступает информация с первых(В-1)разрядов регистра памяти пути канала D, а нл вход V - информация с первых (В-1) разрядов регистра памяти пути канала В. На вход X мультиплексора 24 канала D поступает информация с первых (В-1) разрядов регистра 25 памяти пути канала D, а на вход Y - информация с первых (В-1) разрядов памяти канала В. Выходы мультиплексоров 24 соединены с информационными (D1-DB) входами регистров памяти пути каналов 13 обработки.

Одновременно с выбором меньшего значения метрики состояния узла компаратор 22 каждого канала обработки, соответствующего одному из состояния кодера, формирует управляющий сигнал, по которо- му мультиплексор 24 разрешает передачу на информационные входы регистра 25 памяти пути своего канала обработки информацию памяти пути с того канала обработки, из регистра 23 веса узла которого информа- ция после суммирования одним из сумматоров 20 или 21 с вычисленными значениями метрик передана компаратором 22 в свой регистр 23 веса узла. Запись информации в регистр 25 памяти пути осуществляется так- товыми сигналами (фиг.4, ТЗ), поступающими с тактового входа 14 через элемент 3 задержки.

Регистры веса узла 23 и памяти пути 25 являются элементами памяти на один такт и в них целесообразно использовать двухступенчатые триггеры, в которых информация в вспомогательный триггер записывается по фронту сигнала, а в основной триггер - по спаду сигнала.

Таким образом, на каждом такте на входах мультиплексоров 24 каждого канала 13 обработки присутствуют два пути, а записываются в регистры 25 памяти пути каждый раз только один путь с наименьшим весом узла в зависимости от сигнала на V-входе мультиплексора. Через каждый мультиплексор 24 проходит путь, выживший на данном этапе.

В соответствии с решетчатой диаграм- мой сверточного кода (фиг. 4), по которой любые метрики ветвей, входящие в узел А или. В и узел С, декодируются как a любые метрики ветвей, входящие в узлы В и D, декодируются как Г. На каждом такте обработки узлов в первые разряды регистров 25 памяти пути каналов 13,1 (канал А) и 13.3 (канал С) записывается логический О, а в первые разряды регистров 25 каналов 13.2 (канал В) и 13.4 (канал D) - логическая Г.

Таким образом, в регистрах 25 памяти пути каналов обработки по каждому такту происходит стирание умерших путей и запись выживших путей.

Через В (4-б)К входных тактов в кань- лзх обработки выживают самые старые пути, которые являются наиболее правдоподобными по решетчатой диаграмме спер- точного кода, и в каждом регистре 25 памяти путей в В-м разряде находится одинаковая информация. Поэтому выходную декодированную информацию можно выдавать с 8-го разряда регистра 25 памяти пути любого канала обработки, в частности в нашем примере информация снимается с В-го разряда регистра памяти пути канала А.

Из-за искажения входной информации и связанного с Ийм непрерывного роста метрик веса узлов для исключения переполнения регистров 23 веса узлов и сумматоров 20, 21 в устройство осуществляется нормализация, заключающаяся в следующем.

В процессе декодирования информация из регистра 23 веса узлов всех кана; -. 13 обработки поступает на гт-входовой ког .- паратор 2, на выход которого передается минимальная метрика веса узла с одного из п его входов. Через М входных тактов с помощью счетчика 4 и дешифратора 5 вы и, батывается длительностью, равной периоду входных тактовых импульсов, строб нормирования (фиг. 5,17), который разрешает прохождение минимальной метрики веса узла с выхода n-входового компаратора 2 через блрк 12. вентилей на сумматоры 20, 21, где она вычитается одновременно из регистров 23 веса узлов всех каналов обработки.

Одновременно с декодированием информации осуществляется формирование сигнала достоверности, который вырабатывается блоком 10 сравнения в результате сравнения минимальной метрики веса узла с выхода п- входового компаратора 2 с заранее выбранным пороговым значением метрики веса узла, задаваемым блоком 11 памяти.

Через В входных тактов после сигнала Начальная установка с помощью счетчика 4 и дешифратора 5 вырабатывается сигнал, по которому триггер б устанавливается в единичное состояние (фиг. 5, Т8) и разрешает выдачу декодированной информации с В-разряда регистра 25 памяти пути через второй элемент И 8 на информационный выход 18 (фиг. 5, Т10), тактовых импульсов с тактового входа 15 через первый элемент 1/1 7 на тактовый выход 17 (фиг. 5, Т9) и сигнала Достоверно с выхода блока 10 сравнения через третий элемент И 9 на выход 19 Достоверно (фиг. 5, Т11).

(56) Авторское свидетельство СССР Мг 675616, кл. Н 03 М 13/12, 1977.

Патент США № 3789360. кл. Н 01 1974.

111839281 12

Формула изобретениядешифратора, первый и второй выходы которого подключены соответственно к упУСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ равняющему.входу блока ключей и S-входу ОБЕРТОЧНОГО КОДА, содержащее вычис- v тРиггера. выход которого подключен ко литель метрик ветвей, вход которого явля- второму входу первого элемента И и пер- ется информационным входом устройства, вым. входам второго и третьего элементов

, „k-1 , ВЬ|Х°ДЫ которых являются соответствиип-входовыи компаратор ( , k-величи- но информационным и тактовь выхоГми на кодового ограничения) и п каналов об- устройства, в каждый канал обработки вве- работки, каждый из которых включает в Ю ден мультиплеуправляющий вход и себя регистр .памяти пути, первый и второй ВЫХОды которого подключены соотве ст сумматоры, выходы которых подключены венно к управляющему выходу ком° арато- соответственно к первым и вторым входам ра и входам первого -В-го (где В Л Si компаратора этого канала обработки, ин- разрядов регистра памяти пути этого кана- формационныи выход компаратора под- 1Ь ла обработки. R-вход триггера обьединен с ключей к информационному входу R-входами счетчика импульсов и R входами регистра веса узла этого канала обработки, регистра веса узла р регистра памяти пути выходы регистров веса узла 1-го канала об- каждого канала обработки и является вхо работки () подключены к 1-м входам Q дом начальной установки устройства вто- n-входового компаратора и первым входам рой вход второго элемента И подключен к первого и второго сумматоров каналов об- - ВЫХОду в-го разряда регистра памяти пути работки в соответствии с решетчатой дйаг- соответствующего канала обработТи выхо раммои сверточного кода, выходы ды блока ключей соединены с третьими вычислителя метрик ветвей подключены ко 25 входами первого и второго сумматоров вторым входам сумматоров в каналах об- каждого канала обработки вход элемента работки в соответствии с порождающими задержки объединен со вторым Голом полиномами сверточного кода, отличающе- третьего элемента И и тактовым вхолпм еся тем, что, с целью повышения достовер- счетчика импульсов и является тактовым ности декодирования и быстродействия 30 входом устройства, выход элемента задео устройства. в него введены триггер, де- жхи подключен к С-входам регистра веса шифратор, счетчик импульсов, элементы узла и регистра памяти пути каждого кан задержки, блок сравнения, блок памяти, ла обработки, выходы первого - ГВ - 1Wn блок ключей и первый - третий элементы разрядов регистра памяти пути каждого И. выходы n-входового компаратора под- 35 канала обработки подключены к первым и ключены к информационным входам блока вторым информационным входам мульти- ключей и первым входам блока сравнения, плексоров каналов обработки в соответст вторые входы и выход которого подключе- вии с решетчатой диаграммой сверточного ны соответственно к выходам блока памя- кода, вход нулевого разряда регистра па ти и Первому входу первого элемента И. ,40 мяти пути каждого канала обработки пол- выход которого является выходом Досто- ключей к шине нулевого или единичного верно устройства, выходы счетчика им- потенциала в соответствии с решетчатой пульсов соединены со входами -диаграммой сверточного кода

Ф#& 1

a

/7

-Ct

Изобретение относится к вычислительной технике и может быть использовано в системах передачи данных Цель изобретения - повышение достоверности декодирования и быстродействия устройства Устройство для декодирования сверточ- ного кода содержит вычислитель метрик ветвей, n-входовой компаратор, элемент задержки, счетчик, дешифратор, триггер, первый, второй и третий зпементы И, блок сравнения, блок памяти, блок вентилей, п каналов обработки, каждый из которых включает первый и второй сумматоры, компаратор, регистр веса узла, мультиплексор, регистр памяти пути, информационный вход, тактовый вход вход начальной установки, тактовый выход информационный выход выход Достоверно. За счет введения элемента задержки, счетчика, дешифратора, триггера блока сравнения, блока памяти, первого, второго и третьего элементов И, блока вентилей и их взашосвязей обеспечивается высокая достоверность выдаваемой информации за счет стробиро- вания выхода устройства на время декод (рования, контроля процесса декодирования и выдачи потребителю сигнала о достоверности выдаваемой декодированной информации и сокращается интервал декодирования. 5 ил.

$

-9 -Ь/+

00

--