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

 

.Изобретение относится к вычислительной технике, может быть использовано в системах передачи данных и обеспечивает повышение быстродействия. Устройство содержит корреляторы 1, п-входовый компаратор 2, элемент ИЛИ 3, сдвиговые регистры 4 и 5 и п каналов 6 обработки, в каждый из которых входят регистр 7 памяти, сумматоры 8 и 9, компаратор 10, реверсивный сдвиговый регистр 13, триггер 19, элемент НЕ 21, элементы И 23 и 24 и элемент ИЛ И 27. Благодаря введению в каждый канал 6 обработки сдвиговых регистров 11 и 12, коммутаторов 14-18, триггера 20, элемента НЕ 22, элементов И 25 и 26 и элемента ИЛИ 28 обеспечивается декодирование одного бита ПУТИ за один такт. 4 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1467753

А1

<511 4 Н 03 М 13/12

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

flQ ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

cpa rHHT CcCP (21) 4082411/24-24 (22) 01.07.86 (46) 23.03.89. Бюл. № 11 (?2) Н. Н. Евтихиев, И. Л. Корнеев, Н. А. Ковач, В. А. Пучков и В. Л. Таубкин (53) 681.325.53 (088.8) (56) Авторское свидетельство СССР № 675616, кл. Н 03 М 13/12, 1977.

Патент США № 3789360, кл. Н 04 1 1/10, 1974. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВА.

НИЯ СВЕРТОЧНОГО КОДА (57) Изобретение относится к вычислительной технике, может быть использовано в системах передачи данных и обеспечивает повышение быстродействия. Устройство содержит корреляторы 1, и-входовый компаратор 2, элемент ИЛИ 3, сдвиговые регистры 4 и 5 и и каналов 6 обработки, в каждый из которых входят регистр 7 памяти, сумматоры 8 и 9, компаратор 10, реверсивный сдвиговый регистр 13, триггер 19, элемент

НЕ 21, элементы И 23 и 24 и элемент ИЛИ 27.

Благодаря введению в каждый канал 6 обработки сдвиговых регистров 11 и !2, коммутаторов 4 — 18, триггера 20, элемента НЕ

22, элементов И 25 и 26 и элемента ИЛИ 28 обеспечивается декодирование одного бита пути за один такт. 4 ил.

1467753 если пришел входной символ И 1, либо опять в состояние 00, еси символ И=О. Из состояния 01 можно перейти в состояния 10 и 00 и т. д. Эти переходы отражены на решетчатой диаграмме (фиг. 3). В декодере сверточного кода подключение сумматоров 8 к коммутатору 10 одного из каналов 6 обработки, соответствующего определенному состоя- 45 нию кодера, полностью совпадает с переходами в решетчатой диаграмме сверточного кода.

Корреляторы 1 числом 2 (t — число порождающих полиномов сверточного кода) служат для вычисления меры близости при- 50 шедшей из канала связи пары символов (для t=2) с четырьмя возможными эталонными комбинациями: 00, 01, 10, 11. Эти меры близости называются метриками ветвей Roo, Roi, К1ю и Rl i. Выполнение корреляторов 1 зависит от того, какой пара 55 метр сигнала является носителем информа ции (амплитуда, фаза и т. д.), а также от того, как выбрана мера близости.

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

Цель изобретения — повышение быстродействия устройства.

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

Устройство для декодирования сверточного кода содержит корреляторы 1, п-входовый компаратор 2 (п=2 ), элемент

ИЛИ 3, первый 4 и второй 5 сдвиговые регистры и и каналов 6 обработки, каждый из которых включает в себя регистр 7 памяти, первый 8 и второй 9 сумматоры, компаратор !О, первый 11 и второй 12 сдвйговые регистры,.реверсивный сдвиговый регистр 13, первый — пятый коммутаторы 14 — 18, первый 19 и второй 20 триггеры, первый 21 и второй 22 элементы НЕ, первый — четвертый элементы И 23 — 26, первый 27 и второй 28 элементы ИЛИ. На фиг. 1 обозначены вход 29 и выход 30. Тактовые цепи и цепи управления коммутаторами 14 в 18 не показаны.

Сверточный кодер, формирующий на передающей стороне поспедовательность информационных символов, образующих сверточный код с кодовым ограничением к=3, состоит из сдвигового регистра 31 и сумматоров 32 по модулю два.

Состояние кодера описывает информация в двух левых разрядах регистра 31; 00, 01, 10, 11. Эти состояния нельзя путать со значениями пар сигналов Уl и У2. Из состояния 00 можно перейти на такте в состояние 10.

5 !

О

В простейшем случае пусть информация содержится в фазе сигнала. Пусть фаза О обозначает «О», а фаза 180 — «1». В корреляторе 11, в котором хранится в качестве эталонной величины комбинация 00, производится сравнение фазы обоих поступивших символов с, эталонной фазой О, в корреляторе 1, 2, в котором хранится комбинация

01, производится сравнение фазы первого символа с эталонной фазой О, а фазы второго символа с эталонной фазой 180 . В результате вырабатывается метрика ветви Ro>, равная сумме разностей этих фаз.

Аналогичным образом вычисляются метрики Rin u Rii. В случае отсутствия помехи при совпадении пришедшей пары символов с эталонной, хранящейся в соответствующем корреляторе 1, метрика ветви равна О, в случае полного несовпадения метрика равна максимальному числу в рамках разрядной сетки цифрового представления фазы. При наличии помехи с выходов корреляторов 1 поступают значения меры близости (метрики ветвей), лежащие в диапазоне от 0 до максимального возможного значения, причем минимальная метрика будет на выходе коррелятора 1, у которого пришедшая пара символов имеет максимальное сходство с хранящейся в нем эталонной парой символов. В качестве меры близости можно, использовать Хэммингово расстояние принятой пары символов от эталонной пары.

Компаратор 2 служит для выделения ми нимального из и поступающих на него чисел.

На его выходах появляется «1» в том канале, где метрика состояния минимальна.

Компаратор 10 определяет, какое из двух поступивших на него чисел наименьшее, и выдает это число в качестве новой метрики состояния, а также выдает информацию, из какого канала 6 обработки пришло это число. Если оно пришло из, канала 6, соответствующего состояниям 00, 10, то выдается

«О», если из каналов 6, соответствующих состояниям 01, 11, то выдается «1». Эта информация соответствует самому правому символу в обозначении состоянии кодера.

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

Принятая последовательность символов г!оступает параллельно на входы корреляторов по тактам (фиг. 4). Для каждой пары символов в корреляторах 1 вычисляются метрики ветвей Roo, Roi, К о и Rii, которые в двоичном виде подаются на сумматоры 8 каждого канала 6 в соответствии с порождающими полиномами сверточного кода. Для приведенного на фиг. 2 кодера порождающие полиномы: Cii (D l+D, Cig(D) =

=1+D+D . В соответствии с этими полиномами переходу из состояния 00 в состояние 00 соответствует пара символов У1=0, У2=0. Переходу из 00 в 10 соответствует

Уl= l, У2=1, и т. д. Значения Уl и У2, со1467753

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

Так как каждый канал 6 обработки соответствует одному из состояний кодера, то на входы сумматоров 8 каждого канала 6 поступают значения метрик ветвей с корреляторов 1, в которых хранятся в качестве эталонных соответствующие значения У! и У2. Из коррелятора 1.1 с эталоном 00 (в котором У1=0, У2=0) значения метрики поступают в соответствии с обозначением ветвей диаграммы на сумматор 8 канала 6.1 (00) и канала 6.2 (01), из коррелятора 1.2 с эталоном 1! — на сумматоры

8 канала 6.1 (00) и канала 6.3 (10) и т. д.

При этом верхний сумматор 8 каждого канала 6 соответствует верхней ветви решетчатой диаграммы, входящей в узел соответствующего состояния.

В сумматорах 8 происходит сложение этих значений с вычислительными значениями метрики состояний, поступающими из регистров 7, которые являются элементами памяти на один такт. Таким образом вычисляются новые значения метрик состояний, которые затем поступают на компараторы 10 (фиг. 2) в соответствии со связями в решетчатой диаграмме сверточного кода.

Компараторы 10 из двух значений метрик выбирают меньшее. Эти значения и записываются в регистры 7 в качестве новых метрик состояний.

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

Переход в каждое состояние возможен из двух предыдущих А(к=1), ..., А2,0 и А(к=l ) ..., А2,1. В соответствии с последним символом в записи этих состояний компаратором 10 формируется информация о переходах «О» или «1», которая в дальнейшем поступает в соответствующий канал 6 блока восстановления пути.

Кроме того, значения метрик состояний из регистров 7 памяти периодически поступают на п-входовый компаратор 2, который производит выбор наименьшего значения метрики. Информация о наличии в канале 6 наименьшего значения метрики состояния появляется в виде логической «1» — флажке на выходе одного из каналов компаратора

2 — и в дальнейшем используется для восстановления пути.

Процесс восстановления пути происходит следующим образом. Если проследить в< . выжившие пути на расстоянии В= (4 — 6) ° ., и определить, какой из них имеет меньшую метрику состояния (меньшую длину), то можно утверждать, что самый старый бит информации на отрезке пути наименьшей длины лежит на оптимальном пути и соответ5

1О

55 ствует правильно декодированной информации. Поик этого бита информации можно назвать процессом предварительного поиска.

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

Проводя этот процесс, можно определить конец (со стороны новых битов) оптимального пути.

Сохраняя в памяти информацию о переходах длиной В, предшествующих концу отрезка оптимального пути, можно, начиная обратное движение по решетчатой диаграмме, восстановить со стороны новых битов отрезок оптимального пути длиной В. Этот процесс движения назад по диаграмме сверточного кодера можно назвать процессом окончательного поиска. Процесс предварительного поиска выполняется с использованием в каждом канале б реверсивного регистра 13 группы логических элементов 20, 22, 25. 26 и 28.

Процесс начинается после введения в реверсивный регистр 13 информации о переходах длиной В, при этом коммутаторы 14 — 16 в положении А (фиг. 4, Т2=1) . .В следующий момент времени направление движения информации в реверсивный регистр 13 меняется на противоположное. Коммутаторы 14 — 16 переключаются в положение Б и остаются в этом положении В тактов (фиг. 4, T2=0).

На один такт все коммутаторы 17 переключаются в положение А и информация о флажках (Fp, Ft, Fz, F3) с выходов и-входового компаратора 2 поступает из триггера 20 каждого канала 6.

Флажок, установленный на выходе компаратора 2, соответствующая каналу 6 с наименьшей метрикой состояния, осуществляет внешний запуск волны обратного движения по решетчатой диаграмме. В канале 6 с наименьшей метрикой состояния триггер 20 устанавливается в единицу. При этом информация с выходов реверсивного регистра 13 этого канала 6 подается на логические элементы 25 и 26 и этого канала б. Выходы этих логических элементов соединены с входами элементов ИЛИ 28 в соответствии с видом решетчатой диаграммы сверточного кода.

В начале 6 с наименьшей метрикой состояния в зависимости от того, какая информация поступила из реверсивного регистра 13, сигнал логической единицы появяется либо на выходе элемента И 25, либо на выходе элемента И 26 и соответственно на выходе одного из элементов ИЛИ 28, связанных с этими элементами И.

На следующем такте все коммутаторы 17 переключаются в положение Б и флажок (логическая «1») перезаписывается в триггер 20 одного из каналов 6 в соответствии с информацией, поступающей с выхода элемента ИЛИ 28. Во всех остальных каналах 6

1467753 в триггерах 20 будут записаны логические

«О». Так повторяется В тактов.

Информация из реверсивных регистров 13 перезаписывается в сдвиговые регистры 12.

Эта информация будет использоваться в процессе окончательного поиска. В реверсивные же регистры 13 с выходов компара. торов 10 будут записаны новые В-битовые информации о переходах. В это время на входы тактирования сдвиговых регистров 11 подается потенциал логического «О», что исключает запись информации о переходах в эти регистры.

Процесс окончательного поиска выполняется с использованием в каждом канале регистров 11 и 12 логических элементов 19, 21, 23, 24 и 27 аналогично процессу предварительного поиска. В результате движения по решетчатой диаграмме назад в процессе предварительного поиска в одном из триггеров будет запи и флажок, соответствующий концу отрезка оптимального пути. Это флажок в следующем также запускает волну движения по решетчатой диаграмме назад в процессе окончательного поиска, Для этого на один такт коммутаторы 18 переключаются в положение А (фиг. 4, Т3=1).

Направление движения информации в ревероивных регистрах 13 меняется. Коммутаторы 14 — 16 переключаются в положение А и остаются в этом положении следующие

В тактов.

Информация из реверсивных регистров

13 переписывается в сдвиговые регистры 1, а информация, поступающая из этих сдвиговых регистров 11 через коммутаторы 16, поступает на логические элементы 23 и 24 этого же канала 6. Выходы этих логических элементов соединены с входом элементов ИЛИ

27 в соответствии с решетчатой диаграммой сверточного кодера. Элемент ИЛИ 3 подключен к выходам элементов ИЛИ 27 каналов 6.2 и 6.4 (Ol и 11), соответствующих декодированной единице. Информация с выхода элемента ИЛИ 3 записывается в сдвиговый регистр 4 и в конце приема посылки их В бит перезаписывается в регистр 5 с параллельной записью, откуда последовательно поступает, начиная с самых старых битов, на выход 30 декодера.

Устройство для декодирования сверточного кода обладает большим быстродействием за счет того, что для декодирования одного бита пути требуется один такт работы при выполнении процедуры восстановления пути. При этом обработка во время устройства декодирования ведется с одной тактовой частотой, что существенно упрощает процесс тактирования. Кроме того, общая часть устройства может быть выполнена из отдельных одинаковых модулей в виде БИС с ограниченным числом межмодульных связей. Из таких универсальных модулей простым соединением можно выполнить параллельные устройства декодирования сверточ5

55 ных кодов с кодовым ограничением в диапазоне от 3 до 7 при приемлемых затратах аппаратуры.

Формула изобретения

Устройство для декодирования сверточного кода, содержащее корреляторы, входы которых объединены и являются входом устройства, и-входовый компаратор (п=2

k — величина кодового ограничения), элемент ИЛИ, выход которого соединен с входом первого сдвигового регистра, выходы разрядов которого подключены к соответствующим входам eToporo сдвигового регистра, выход которого является выходом устройства, и п каналов обработки, каждый из которых включает в себя первый и второй сумматоры, регистр памяти, компаратор, реверсивный сдвиговый регистр, первый и второй элементы И, первый элемент НЕ, первый элемент ИЛИ и первый триггер, выход которого соединен с первыми входами первого и второго элементов И, второй вход первого элемента И объединен с входом первого элемента НЕ, выход которого подключен к второму входу второго элемента И, первый выход компаратора (i-ro канала обработки (i= 1,ï) подключен к входу регистра памяти этого канала обработки, выходы которого соединены с первыми входами первого и второго сумматоров этого канала обработки и i-м входом п-входового компаратора, выходы корреляторов подключены к вторым входам сумматоров в каналах обработки в соответствии с порождающими полиномами сверточного кода, выходы сумматоров каждого канала обработки подключены к соответствующим входам компараторов в каналах обработки в соответствии с решетчатой диаграммой сверточного кода, первые и вторые входы первых элементов ИЛИ каждого канала обработки соединены с выходами соответствующих первого и второго элементов И каналов обработки в соответствии с решетчатой диаграммой сверточного кода, выходы первых элементов ИЛИ в каналах обработки, двоичные номера которых содержат единицу в старшем разряде, подключены к соответствующим входам элемента ИЛИ, отличаюи1ееся тем, что, с целью повышения быстродействия устройства, в каждый канал обработки введены первый и второй сдвиговые регистры, первый — пятый коммутаторы, третий и четвертый элементы И, второй элемент НЕ, второй элемент ИЛИ и второй триггер (i-й выход и-входового компаратора подключен к первому входу четвертого коммутатора i-ro канала обработки, второй выход компаратора в каждом канале обработки соединен с входом первого коммутатора, первый и второй выходы которого подключены к одноименным входам реверсивного сдвигового регистра, первый и второй выходы которого подключены соответствен!

467753

00 00

Фиг.2

Фиг3

Составитель О. Ревинский

Редактор П. Гереши Техред И. Верее Корректор И. Муска

Заказ 1213/55 Тираж 879 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Производственно-издательский комбинат «Патент», г. Ужгород, ул. Гагарина, IO I но к первому входу второго коммутатора и входу первого сдвигового регистра, к второму входу второго коммутатора и входу второго сдвигового регистра, выходы первого и второго сдвиговых регистров соединены соответственно с первым и вторым входами третьего коммутатора, выход которого подключен к входу первого элемента НЕ, выход второго коммутатора соединен с первым входом третьего элемента И и входом второго элемента НЕ, выход которого подключен к первому входу четвертого элемента И, первые и вторые входы вторых элементов ИЛИ каждого канала обработки соединены с выходами соответствующих третьего и четвертого элементов И каналов обработки в соответствии с решеточной диаграммой сверточного кода, выход второго элемента ИЛИ в каждом канале обработки подключен к первому входу пятого коммутатора и к второму входу четвертого коммутатора, выход которого соединен с входом второго триггера, выход которого подключен к вторым входам третьего и четвертого элементов И, выход первого элемента ИЛИ в каждом канале обработки соединен с вторым входом пятого коммутатора, выход которого подключен к входу первого триггера.