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

Фи.г.1

- 30

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

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

На фиг. 1 показана функциональная схема устройства для декодирования свер- точного кода при кодовом ограничении на фиг. 2 - схема кодера, формирующего используемый в рассматриваемом уст- ройстве сверточный код, пример; на фиг. 3 решетчатая диаграмма сверточного кода; на фиР 4 - временные диаграммы сигналов, управляющих работой устройства. Устройство для декодирования сверточноВ простейшем случае пусть информация содержится в фазе сигнала. Пусть фаза 0° обозначает «О, а фаза 180° - «1. В корреляторе 11, в котором хранится в качестве эталонной величины комбинация 00, производится сравнение фазы обоих поступивших символов с, эталонной фазой 0°, в корреляторе 1, 2, в котором хранится комбинация 01, производится сравнение фазы первого символа с эталонной фазой О, а фазь второго символа с эталонной фазой 180°. В результате вырабатывается метрика ветви Roi, равная сумме разностей этих фаз.

Аналогичным образом вычисляются метрики RIO и Rii. В случае отсутствия поУстройство для декодирования с ер,ич.и-н - . р-,,,„,ден„и пришедшей пары симвого кода содержит коррелятодь, 1, пвхо 15/ ,,a„„нной, хранящейся в.соответдовый компаратор 2 ( ), элемент

лов с эталонной, хранящейся в. соответ- иТи з пео вь7й1 и второй 5 сдвиговые ствующем корреляторе 1, метрика ветви .;. pL%:r/;-c: :r™cTr;L:s

ГЬг„ ГДГГеГс 5

1гИ,,гГв-л : r /P™ sri :r:±o :ro

3 19 и ВТОРОЙ 20 триггеры, первый 21до максимального возможного значения, прии ВТОРОЙ 22 эТменты НЕ, первый-четвер- чем минимальная метрика будет на выходе тыйэлементьГи 23-26, первый 27 и вто- 25 коррелятора 1, у которого пришедшая пара тыи элементы п t , символов имеет максимальное сходство с

хранящейся в нем эталонной парой символов. В качестве меры близости можно использовать Хэммингово расстояние принятой пары символов от эталонной пары.

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

t DJ rl yt I ivi 1 11 I ui .tj. , - - j- ..

рой 28 элементы ИЛИ. На фиг. 1 обозначены вход 29 и выход 30. Тактовые цепи и цепи управления коммутаторами 14-18 не показаны.

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

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

Компаратор 10.определ яет, какое из двух поступивших на него чисел наименьшее, и

srI ;rirI KL r,. ;° - „тггж: -iri-Lrr™ ,,

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

коммутатору 10 одного из каналов 6 обработки, соответствующего определенному состоя- 45 нию кодера, полностью совпадает с переходами в решетчатой диаграмме сверточного

кода.

Корреляторы 1 числом 2 (t - число порождающих полиномов сверточного кода)

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

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

Принятая последовательность символов поступает параллельно на входы корреляторов по тактам (фиг. 4). Для каждой пары символов в корреляторах 1 вычисляются метрики ветвей Roo, Roi, Rio и Rn, которые в

.; so г™г ° -гг™йшедшей из канала связи пары символов (для ) с четырьмя возможными эталонными комбинациями: 00, 01, 10, 11. Эти меры близости называются метриками ветвей ROO, ROI, RIO и RII. Выполнение корре- ляторов 1 зависит от того, какой пара- метр сигнала является носителем информа;- ции (амплитуда, фаза и т. д.), а также от того, как выбр.ана мера близости.

дого канала 6 в соответствии с порождающими полиномами сверточного кода. Для приведенного на фиг. 2 кодера порождающие полиномы: Gi( ; G2(D) 1 |-D+D. В соответствии с этими полиномами переходу из состояния 00 в состояние 00 соответствует пара симв олов У , . Переходу из 00 в 10 соответствует , и т. д. Значения У1 и У2, со

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

Аналогичным образом вычисляются метрики RIO и Rii. В случае отсутствия пон - . р-,,,„,ден„и пришедшей пары симво „тггж: -iri-Lrr™

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

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

Принятая последовательность символов поступает параллельно на входы корреляторов по тактам (фиг. 4). Для каждой пары символов в корреляторах 1 вычисляются метрики ветвей Roo, Roi, Rio и Rn, которые в

г™г ° -гг™йг™г ° -гг™йдого канала 6 в соответствии с порождающими полиномами сверточного кода. Для приведенного на фиг. 2 кодера порождающие полиномы: Gi( ; G2(D) 1 |-D+D. В соответствии с этими полиномами переходу из состояния 00 в состояние 00 соответствует пара симв олов У , . Переходу из 00 в 10 соответствует , и т. д. Значения У1 и У2, соответствующие переходам в решетчатой диаграмме, обозначены над ветвями решетчатой диаграммы.

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

10

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

Сохраняя в памяти информацию о переходах длиной В, предшествующих концу отрезка оптимального пути, можно, начиная обратное движение по решетчатой диаграмме, восстановить со стороны новых битов отос 1 о /1, ° - - 1П оп ь LU LIUpUHbl новых ОИТОВ ОТ8 канала 6.1 (00 и канала 6.3 (10) и т. д. ,5 резок оптим,ального пути длиной В Этот пропи ЧТПМ ИРПУНИИ f-VMMaT-r n Х l/Q-u nnrn Ь аио

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

В сумматорах 8 происходит сложение

цесс движения назад по диаграмме свер- точного кодера можно назвать процессом окончательного поиска. Процесс предварительного поиска выполняется с использованием в каждом канале 6 реверсивного ре„ 11Ш.1.1 и ламйлс и иевеисивного оеэтих значении с вычислительными значения- 20 ристра 13 группы логических элементов 20 ми метрики состоянии, поступающими из 22, 25. 26 и 28 регистров 7, которые являются элементами памяти на один такт. Таким образом выПроцесс начинается после введения в реверсивный регистр 13 информации о переходах длиной В, при этом коммутаторы 1416

которые затем поступают на компарато- в положении А (фиг. 4, . В следующий ры 10 (фиг. 2) в соответствии со связями в „«мент времени направление движения информации в реверсивный регистр 13 меняется на противоположное. Коммутаторы 14-16 переключаются в положение Б и остаются в этом положении В тактов (фиг. 4, ). 30 На один такт все коммутаторы 17 переключаются в положение А и информация о флажках (Fo, FI, Fa, Fg) с выходов п-входо- вого компаратора 2 поступает из триггера 20 каждого канала 6.

,.. ,-- -Флажок, установленный на выходе компаформацию о переходе в данное состояние. 35 ратора 2, соответствующая каналу 6 с Переход в каждое состояние возможен из наименьшей метрикой состояния осуществая- двухпредыдущихА(),...,А2,ОиА() ет внешний запуск волны обратного движе ..., А2,1. В соответствии с последним сим- „ия по решетчатой диаграмме В канале 6 опГшж ™ состоянии компара- с наименьшей метрикой состояния триггер 20 тором 10 формируется информации о пере- устанавливается в единицу. При этом инфор ходах «О или 1, которая в дальнейшем 40 реверсивного регистра 13 поступает в соответствую„жи кяня. fi йпп.я нала 6 подается на логические эле

менты 25 и 26 и этого канала 6. Выходы эти.х логических элементов соединены с входами

--элементов ИЛИ 28 в соответствии с виют на п-входовыи компаратор 2, который дом решетчатой диаграммы сверточного производит выбор наименьшего значения мет- кода. « личнию

числяются новые значения метрик состояний.

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

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

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

Процесс восстановления пути происходит следующим образом. Если проследить в« выжившие пути на расстоянии В(4-б)-., и определить, какой из них имеет меньшую

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

На следующем такте все коммутаторы 17 переключаются в положение Б и флажок

-- - j- icuci jitu4dtu (.и В положение п и ттям пкметрику состояния (меньщую длину), то мож- 55 (логическая «I) перезаписьшается в тГг но утверждать, что самый старый бит ин- гер 20 одного из каналов 6 в соответствии

с информацией, поступающей с выхода элеформации на отрезке пути наименьшей дли ны лежит на оптимальном пути и соответмента ИЛИ 28. Во всех остальных канала.х 6

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

Сохраняя в памяти информацию о переходах длиной В, предшествующих концу отрезка оптимального пути, можно, начиная обратное движение по решетчатой диаграмме, восстановить со стороны новых битов от ° - - 1П оп ь LU LIUpUHbl новых ОИТОВ ОТрезок оптим,ального пути длиной В Этот про резок оптим,ального пути длиной В Этот про

цесс движения назад по диаграмме свер- точного кодера можно назвать процессом окончательного поиска. Процесс предварительного поиска выполняется с использованием в каждом канале 6 реверсивного ре11Ш.1.1 и ламйлс и иевеисивного оеристра 13 группы логических элементов 20 22, 25. 26 и 28

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

На следующем такте все коммутаторы 17 переключаются в положение Б и флажок

icuci jitu4dtu (.и В положение п и (логическая «I) перезаписьшается в тГг гер 20 одного из каналов 6 в соответствии

с информацией, поступающей с выхода элемента ИЛИ 28. Во всех остальных канала.х 6

в триггерах 20 будут записаны логические «О. Так повторяется В тактов.

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

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

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

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

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

5 Q

15 25

30 35 Q 45

5055

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

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

Устройство для декодирования сверточного кода, содержащее корреляторы, входы которых объединены и являются входом fCT- ройства, п-входовый компаратор ( k - величина кодового ограничения), элемент ИЛИ, выход которого соединен с входом первого сдвигового регистра, выходы разрядов которого подключены к соответствующим.входам BTOport) сдвигового регистра, выход которого является выходом устройства, и п каналов обработки, каждый из которых включает в себя первый и второй сумматоры, регистр памяти, компаратор, реверсивный сдвиговый регистр, первый и второй элементы И, первый элемент НЕ, первый элемент ИЛИ и первый триггер, выход которого соединен с первыми входами первого и второго элементов И, второй вход первого элемента И объединен с входом первого элемента НЕ, выход которого подключен к второму входу второго элемента И, первый выход компаратора (i-ro канала обработки (,n) подключен к входу регистра памяти этого канала обработки, выходы которого соединены с первыми входами первого и второго сумматоров этого канала обработки и i-M входом п-входового компаратора, выходы корреляторов подключены к вторым входам сумматоров в каналах обработки в соответствии с порождающими полиномами сверточного кода, выходы сумматоров каждого канала обработки подключены к соответствующим входам компараторов в каналах обработки в соответствии с решетчатой диаграммой сверточного кода, первые и вторые входы первых элементов ИЛИ каждого канала обработки соединены с выходами соответствующих первого и второго элементов И каналов обработки в соответствии с решетчатой диаграммой сверточного кода, выходы первых элементов ИЛИ в каналах обработки, двоичные номера которых содержат единицу в старщем разряде, подключены к соответствующим входам элемента ИЛИ, отличающееся тем, что, с целью повышения быстродействия устройства, в каждый канал обработки введены первый и второй сдвиговые регистры, первый-пятый коммутаторы, третий и четвертый элементы И, второй элемент НЕ, второй элемент ИЛИ и второй триггер (i-й выход п-входового компаратора подключен к первому входу четвертого коммутатора i-ro канала обработки, второй выход компаратора в каждом канале обработки соединен с входом первого коммутатора, первый и второй выходы которого подключены к одноименным входам реверсивного сдвигового регистра, первый и второй выходы которого подключены соответственно к первому входу второго коммутатора и входу первого сдвигового регистра, к второму входу второго коммутатора и входу второго сдвигового регистра, выходы первого и второго сдвиговых регистров соединены соответственно с первым и вторым входами третьего коммутатора, выход которого подключен к входу первого элемента НЕ, выход второго коммутатора соединен с первым входом третьего элемента И и входом второго элемента НЕ, выход которого подключен к первому входу четвертого элемента И, первые и вторые входы вторых элементов ИЛИ каждого канала обработки сое

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

.Изобретение относится к вычислительной технике, может быть использовано в системах передачи данных и обеспечивает повышение быстродействия. Устройство содержит корреляторы 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 ил.

У1

п

Фиг.2

Фиг.З