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

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

Цель, изобретения - угфощение устройства.

На.фиг.1 изображена блок-схема устройства; на фиг о2 - блок тактовой синхронизации; на - формирователь адресов прослегвдвания путей J на фнг.Д - схема кодера, формирующего декодируемый устройством сверточный код; на фиг, 5-8 - диаграммы, поясняющие работу устройствао Устройство содержи.т блок 1 вычис- 1ления метрик ветвей, су маторы .2, |блок 3 сравнения, первьш третий |коъшутаторы 4-6, блок 7 нормиро- Ьанного порога, блок 8 памяти мет- 1рик, кодеры 9, формирователь 10 ад- ресов считьшания, формирователь 11 адресов записи форгдарователь 12 адресов памяти путей, формирователь адресов просленсивания путей, блок 14 памяти путей, блок -15 прослеживания путей, решающий блок 16 и блок 17 тактовой синхронизацииS а также информагц онный вход 18 и вход 19 сянкрониза1диия

Блок 1 вычисления метрик ветвейs ;блок 7 нормированного порога, блок 8 ;памяти метрик, кодеры 9.1 и 9.2, формирователь 10 адресов счктьша- ;ния и формирователь 1 адресов за- писи выполнены так же, как аналогнч- ные блоки известного усгфойства„

Блок 17 тактовой синхронизации содержит (фиг.2) генератор 20 такте- : вых импульсов, делитель 21 частоты,, первый 22 и второй 23 триггеры и элемент И-НЕ, а также вход 25 синхрнизации, управляющие входы 26, пер- ньй 27 и второй 28 выходы,

Формирователь 12 адресов памяти путей5 как и формирователи 10 и 11j представляет собой счетчик импульсо

Формирователь 13 адресов прослеживания путей содержит (фиг.З) счетчик 29 импульсов, триггер 30 и эле-- мент И 31, а также установочные входы 32, счетньй 33 к управляющий 34 входы, первый 35 и второй 36 .

Блок 14 памяти путей реализован как блок оперативной памяти. Блок 1 .просле}швания путей представляет собой регистр сдвига.

o

5

:5

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

Кодйр на передающей стороне, формирующий сверточньш код с длиной кодового ограничения К, подлежащий декодированию в предлагаемом устройстве, содер)жт (фиг,4) -К-разрядный регистр 37 сдвига, полусумматоры 38 и.39 и коммутатор 40, а также информационный 41 и тактовый 42 входы.

Код задается связями ме:эду выходами разрядов регистра 37 сдвига и входами полусу1-{маторов 38 к 39. обозначая наличие связи между раз- рядом регистра и входом полусумматора символом

а. отсутствие св.язи

30

40

50

Л

символом О, получают кодовые генераторы (1011, 1101), а представляя кодовые генераторы в восьмеричной форме, получают (13,15). Длина кодового ограничения такого кода равна четырем Информатдк синая поел вдова- телыюсть I(D) поступает на вход .регистра 37 сдвига и в течение длительности одного информационного символа с помощью коммутатора 40 генери-- руются два канальных символа. Таким образом скорость кода в данном случае равна R 1/2. В общем случае скорость кода может быть равной R k/U; где k и п - целые положительные числа, причем, k-cn. Свер- точный,кодер является дискретньм автоматом с конечным числом состояний и полностью описывается диаграммой состояний.

Состоянием кодерй называется, со-.; держимоё трех правых регистров сдвига. Диаграмма состояний содержит все возможные переходы кодера из одного состояния в другое (фиг.5). Решетчатая диаграмма сверточного кода является разверткой диаграммы состояний во времени (фиг,6), На решетке, состояния .показаны узлат-ш, а переходы - ветвя№1. на одном шаге

Количество решетчатсй

узлов д,и5

аграммы равно (K-1). После каждого перехода из одного состояния в другое происходит смещение на один шаг вправо П.

Устройство работает следующим об- разоМо

Из принимаемой и канала связи последовательности Т (D) . выделяются дэе последовательности T1(D) и T2(D) которые триадами поступают с входа 18 на блок 1 вычисления метрик ветвей. Кроме того на вход 19 поступают тактовые импульсы с частотой F, в два раза ниже, чем канальная частота последовательности f (D), ив фазе, соответствующей правильному разделению последовательности 1(0) на последовательности T1(D) и 2(0), Блок 17 тактовой синхронизации в течение одного импульса F, формирует на своем первом выходе 27 пакет

из N тактовых импульсов F , а на втором выходе 28 - импульс конца цикла, которые используются совместно с импульсами F для синхронизации остальных блоков устройства,

На входы блока 1 вычисления метрик ветвей поступают триадами решения, вынесенные демодулятором о переданных двух канальных символах соот- ественно из последовательностей 1(D) и T2(D,), На вторые входы блока поступают двоичные триады с кодеров 9о1 и 9.2, представляющие собой значения ветвей решетчатой диаграммы, задаваемые формирователем 10 адресов считывания. На первых выходах блока 1 вычисления метрик ветвей формируют ся значения приращений метрик, пропорциональные логарифмической функции правдоподобия принятой кодовой ветви и каждой из ветвей, соответствующей на решетчатой диаграмме поступлению нулевого символа. На вторых выходах блока 1 вычисления метрик ветвей формируются значения приращения метрик, соответствуюпдае поступлению единичного информационного символа. Выходы блока 1 вычисления метрик ветвей подключены к входам сумматоров 2. 2.1 и 2.2, вторые входы которых подключены к входам блока 8 памяти метрик.

Результаты сложения с выходов сумматоров 2,1 и 2.2 подаются на входы блока 3 сравнения, где осуществляется сравнение двух метрик, и дальше на первый коммутаторв Д. Выжившие

2378 6

метрики записываются в блок 8 памяти метрик. Во избежание переполнеш1я ячеек блока 8 производится нормализация путем вычитания их значений метрики фиксированного числа. При превышении метрикой одного из узлов заданного порога блок 7 норьированного порога фиксирует запрос на пормализа- JQ щш и выполняет ее на следующем шаге по решетке. Поскольку вьмитание числа эквивалентно прибавлению дополнительного кода этого числа, то для выпол- нения нормами зации использ потся стар- шие разряды первых входов сумматоров 2 (третьи выходы), на которые блоком 7 нормирова .люго порога выдается дополнительный код числа, вычитаемого из метрик. На следующем после нормали- 20 зации шаге-по решетка запросы на нормализацию игнорируется. Такая схема, кроме уменьшения аппаратурньгх затрат позволяет уменьшать время, необходимое на обработку одного узла рещетки, 25 за счет одновременного сложения метрик и выполнения нормализации. Это позволяет cкo meнcиpoвaть потери в быстродействии, вызванные отказом от параллельной обработки двух узлов 0 решетки.

Елок 8 памяти метрик разделен на две ЧЕСТИ, одна из которых служит для хранения и считывания информации, , а другая - для записи и хр)нения. При тсаждом .j.tre по релиетке обе части обмеиива отся своими функциями. ,Цля осу1дествле 1ия параллельного доступа к двум ячейкам при сч ;тьгБании часть блока 8 памяти метрик, служащая для хранения и считывания, разделяется на две части.

На выходах первого коммутатора 4 метрики ветрей существуют в Биде

5 логической информации о переходах (О - верхний путь, 1 - нижний) по решетчатой диaгpaм e сверточного кода. Из рассмотретш фрагмента решет чатой диаграммы для двоичных сверточQ ных кодов со скоростями 1/п, где и 1,2.3,. о. (фкг.6), видгго, что ад-реса. узлоБ на .предыдущем (при движении слева напарво) шаге по решетке могут быть получены из адреса узJ ла на последующем шаге путем сдвига вправо двоичного кода адреса узла и подстановкой в освободившийся старший разряд информации о перехоцр Г О или 1).

5

0

20

25

Продвигаясь по решетч; лч)й диаграмме слева направо, декодер отбрасы- йает половину ветвейj входящих в , и решетчатая диаграмма приоб- 1 етает соответствующий вид. (фиг.7), Причем в каждый узел входит только Одна ветвь. Информация о переходах Подается на управляющий вход блока 14 Памяти путей,IО

Формирователь 12 адресов памяти пу- teй., формирователь 13 пг.мяти путейj йрослеживания путейs, обеспечивающие подключение соответственно старших и мтшдших разрядов адреса коммутато ры 5 и 6, блок 14 памяти путей, блок 15 прослеживания ,путей и решающий флок 16 образуют модуль прослеживания путей и обеспечивают хранение инфор- liiaip-m о переходах по решетчатой диаг- |)амме и прослеживание непрерывного йути. Поскольку достаточным является прослеживание . на глубину L /5-б)«К, та необходимо хранение информации о переходах через N 2 узлов на длине L шагов. Хранение информации о переходах ос-уществляет-- ся в блоке 14 памяти путей; адресное пространство которого .организовано в виде адресного кольца длиной L 30 (фиг.8), При такой организации нет необходимости выполнять сдвиг информа- turn на длине L, а модифицируется только адрес текущего етага по решетчатой диаграмме.35

Таким образом, блок 14 памяти пу- тай может быть выполнен на одкой кикросхеме ОЗУ, что позволяет сократить количество микросхем по сравнению с известнь1М устройством в А К раз.4С

Адрес перехода в решетчатой диаг - рамме состоит из адреса узла, в который вьтолнен переход (младшая часть;, -к адресаI шага по решетчатой диаграмме . (старшая часть) (фиг.7). При этом 45 объек памяти путей, необходимый для

хранения информации о переходах, сое- - тавляет М L N бит, При записи решений последовательно перебираются адреса узлов формирователем 11 адреса ,;о записи и адреса шагов по решетчатой диаграмме формирователе .м 12 адреса памяти путей. Решения записываются в ешок 14 памяти путей по полученному адресу перехода, которьп передается ,.5 через коммутаторы 5 и 6 (старших и {шадших разрядов памяти путей).

Прослеживание непрерьгоного пути .производится справа налево по решетча1612378 .8

той диаграмме5 Адрес, узла, из которого сделан переход к данному узлу, формируется блоком 15 прослеживания путей, представляющим собой регистр сдвига, на вход которого поступает информация с выхода блока 14 памяти путей о Адрес узла на предьщущем marej сформированньм блоком 15 прослежива- ния путей,подается череа:коммутатор 5, (младише разряды адреса памяти путей) па первые адресные входы блока 14 памяти путей. Считанная с блока . 14 информация поступает на вход блока 15 прослезкивания путей, который новьй адрес узла (фиг. 7). При прослезкивании путей адреса шагов по решетчатой диаграмме перебг-гр ают- ся форг-шрователем - 13 адресов просле- лшвания путей, начиная с текущего адреса записи, s обратном направлении, для чего в начале просле-ж11вания текущий адрес переписывается из формирователя 12 адресов памяти путей в формирователь 13 адресов прослежн:ва- ния путей.

Поскольку в конце прослежиБания непрерывного пути на глубину L шагов на выходе сдвигового регистра блока 15 присутствует информация о К-1 самых старых переходах, зта информация вьщается на решаюпщй блок I6s как решение декодера. Решаюгдий блок 16. выход которого является выходом устройства, в течение К-1 кнформационньпс тактов 7-i преобразует решение декодера из параллельного кода в последовательный.

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

Так как прслемшание ведется в течение К-1 информационных тактов F, а в течение одного информационного . такта F обрабатывается последовательно N узлов, то длина прослеживания составляет I N.(K-1) (К-1) 2 шагов, что удон.г1етворяет условию L (5-6) К при К 4.

Предлагаемое устройство по сравнению с известным более простое при сохранении быстродействия, что дости гается однопременньс-) выполнением сложения метрик и нормализации и реализации блока 14 памяти.путей на одной микросхеме ОЗУ. Указанные техничесшение декодера. Решаюгдий блок 16. выход которого является выходом устройства, в течение К-1 кнформационньпс тактов 7-i преобразует решение декодера из параллельного кода в последовательный.

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

Так как прслемшание ведется в течение К-1 информационных тактов F, а в течение одного информационного . такта F обрабатывается последовательно N узлов, то длина прослеживания составляет I N.(K-1) (К-1) 2 шагов, что удон.г1етворяет условию L (5-6) К при К 4.

Предлагаемое устройство по сравнению с известным более простое при сохранении быстродействия, что дости гается однопременньс-) выполнением сложения метрик и нормализации и реализации блока 14 памяти.путей на одной микросхеме ОЗУ. Указанные техничес9,6

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

Практически устройство рассчитано на использование сверточных кодов с длиной кодового ограничения в диапазоне от 4 до 8.

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

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

торов, первый выход блока тактовой синхронизации соединен со счетным входом формирователя адресов прослеживания путей, тактовыми входами блока прослеживания путей, блока памяти путей, второго и третьего коммутаторов и входами формирователя адресов считывания и формирователя адресов записи, Q второй выход блрка тактовой синхронизации подключен к. управляющему входу формирователя адресов прослеживания путей, управляющие входы блока тактовой синхронизации объединены с первы- JJ ми информационными входами второго кoм iyтaтopa и подключены к выходам формироватапя адресов записи, выходы формирователя адресов памяти путей соединены с первыми информагд - 20 онными входами третьего коммутатора и установочными входами формирователя адресов прослеживания путей, первые и вторые выходы которого подключе- ны соответственно к вторым информаци- 25 онным входам третьего коммутатора и управляющему входу решающего блока, выходы второго и третьего коммутаторов соеди 1ены с первыми и вторыми адресными входами блока памяти путей, 0 управляющий вход которого подключен к выходу блока сравнения, выход блока памяти, путей соединен с информацион- ньр-; входом блока прослеживания путей, выходы которого под)слючены к вторым информационным входам второго коммутатора и информационным входам решающего блока, выход которого является выходом устройства.

5

40

2. Устройство по П.1, о т л и 45

50

55

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

блока.

П .16

3. Устройство по п,1, о т л н - ч. а ю D е е с я тем, что формирователь адресов прослеживания путей содержит триггер, элемент И и счетчик импульсов, счётный вход Которого объединен с тактовым входом триггера и является счетным входом формирователя, первые входы элемента И соответственно объединены с младшими разрядами установочных входов счетчика импульсов и являются собтветствующи- ми младшими разрядами установочных

2378 2

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

10

Изобретение относится к вычислительной технике и технике связи. Его использование в аппаратуре передачи цифровых данных позволяет упростить устройство, содержащее блок 1 вычисления метрик ветвей, сумматоры 2, блок 3 сравнения, коммутаторы 4 - 6, блок 7 нормированного порога, блок 8 памяти метрик, кодеры 9, формирователь 10 адресов считывания, формирователь 11 адресов записи и блок 14 памяти путей. Благодаря введению формирователя 12 адресов памяти путей, формирователя 13 адресов прослеживания путей, блока 15 прослеживания путей, решающего блока 16 и блока 17 тактовой синхронизации в устройстве обеспечивается одновременное сложение метрик и нормализации, а циркуляция адресов шага декодирования осуществляется в одном блоке памяти путей. 2 з.п. ф-лы, 8 ил.

4f

фиг. 4

дпчч«чд

10

HI О

1612378

ф1/г.д

Адрес