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

 

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

сова сонетсних социмистичесних

РЕСПУВЛИН

ОПИСАНИК ИЗОБРЕ ГЕНИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ по изовРетениям и отнРытиям . ПРИ П нт СССР (21 ) 4 639 79 i /24-24

1 (22) 19.01.89 (46) 07.12.90.Бюл. Р 45 (72) А.В.Салабай, Д.В.Орлов, Ю.Ф.Коновалов и А.В.Брукер (53) 621.394.14:681.32 (088,8) (56) Кейн Дж. Кларк Дж. Кодирование, с исправлением ошибок в системах цифровой связи. — M,: Радио и связь, 1987, с.235-246.

Авторское свидетельство СССР

В 675616, кл. Н 03 M 13/12, 1977.

Авторское свидетельство СССР

Р 1319283, кл . Н 03 И 13/12, 1984.

Авторское свидетельство СССР

Р 1005322, кл . Н 04 . 17/30, 198 1. (54) УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ

СВЕРТОЧНОГО КОДА (57) Изобретение относится к вычисли.— тельной технике и технике связи. Его

„.Я0„„1612378 А1 (51) 5 Н 03 М 13/12

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

cCe:.ïå÷íвается одновременное сложе9 ние метрик и нормализации, а циркуляция адресов шага декодирования ocv ществляется в одном блоке памяти пу- Са тей. " "-„„и. ф-лы, 8 ил.

1612378

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

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

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

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

17 тактовой синхронизации, а также информационный вход l8 н вход 19 синхронизации.

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

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

Формирователь 12 адресов памяти путей, как и формирователи 10 и I 1,представляег собой счетчик импульсов

Формирователь 13 адресов прослеживания путей содержит (фиг.3} счетчик 29 импульсов триггер 30 и эле-мент И 31, а также установочные.

:входы 32, счетный 33 и управляющий

34 входы первый 35 и з орой 36 выйоды.

С С;

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

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

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

Код задается связями межд выходами разрядов регистра 37 сдвига и входами полусумматоров 38 и 39.

Обозначая наличие связи между ря=рядом регистра и входом полусуммяторя символом "1",. я отсутствие свчзи символом "0, получают коцовь1е =åíåраторы (1011, !101), а представгяя кодовые генераторы в восьмеричной форме, получают (13,15). Кп>»!а кодового ограничения такого кода равна четырем. Информационная последовательность T.(O) поступает на вход . регистра 37 сдвига и в течение длительности одного информационного сим" вола с помощью коммутаторе 40 генерируются два канальных символа. Таким образом скорос.ть кода в данном случае равна R = 1/2. В общем случае скорость кода может бь:ть равной

R = k/è, где 1с и и — целые положительные числя, причем, kап. Сверточный кодер является дискретным автоматом с конечным числом состояний и полностью описывается диаграммой состояний

Состоянием кодера называется, содержимое трех правых регистров сдви" гB., Диаграмма состояний содержит все возможные переходы кодерc: из одного состояния в другое (фиг.5). Решетчатая диаграмма сверточного кода является разверткой диаграммы состояни во времени (фиг,6!, На решетке, состояния --.оказаны узлами,, я переходы - ветвями,, Количество узлов на одном шаге решетчатой ди-. метрики записываются в блок 8 памяти метрик. Во избежание переполнения ячеек блока 8 производится нормализация путем вычитания их значений метрики фиксированного числа. При превышении метрикой одного из узлов заданнога 11арога блок 7 нормированного порога фиксирует запрос на нормализацию и выполняет ее на следующем шаге по решетке. Поскольку вычитание числа эквивалентно прибавлению дополнительнага кода этого числа, то для выполнения нормализации используются старшие paзряды первых входов сумматоров

2 (третьи выходы), на которые блоком

7 нармнрав11::11ага порога выдается дополните.:ьный кад чи;ла, вычитаемаго иэ метр:-к. На следующем после нормализации шаге па решет1 е запросы на нормализацию игнорируются. Такая схема, кр Оме vNerlümenèë л пп11р11тур11ых затрату позволяет уче11ь11п ть время „необходимое на обработку ад «ага узла решетки, за счет одновременного сложения метрик и выполнения нормализации. Это позволяет скамг1енсировать потери в аыстрадействии, вызванные отказом ат параллельной абрабатк11 дгух узлов решетки.

Блок 8 памяти метр11к разделен на две части, адна иэ хатopll. служит для хранения и считывания 11нфармации, а :другая — для за1..ис11 н хр 1нения.

При каждом,a;ге па ре111ет11е абе части абменива лтся crlîèìè функциями.

Для осущест11ле.111я парвллел1.нага достуП;. К ДВУМ ЯЧЕПКаМ ПРИ Сч11:.тв1Ваинн част1 блока 8 памяти метрик, служащая для хра:1ения и c÷èòûâàllèÿ, разделяет я на две части.

Via выходах первого коммутатора 4 метрики ветг,ей сущест1лу. r в виде

45 ла;-iëåñêîé информации а пер входах ("й" — верхний пут -., "1" — нижний) па решет-..атой диаграмме свертачнага када, Иэ рассматре1111я:ррагмента решет четой диаграммы для двоичных сверточных кацав са скоростями 1/11, где

n =- 1,2..3,... (фиг,6), видно, что адреса, узлà-, на.предыдущем (при движении слева напарво) шаге па решетке могут быть получены из адреса уэ55 Jia на последующем шаге путем сдвига вправо дваичнага кода адреса узла и подстановкой в освободившийся стар.ший разряд информации о переходе ("0" ч.1и "1").

5 16 t 2378

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

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

Из принимаемой из канала связи последовательности Т(D) выделяютлся

М две последовательности T1(D) и T2(D)

10 которые триадами поступают с входа

18 на блок 1 вычисления метрик ветвей. Кроме того на вход 19 поступают тактовые импульсы с частотой F

1 в два раза ниже, чем канальная частота последовательности Т(Р), и в

15 фазе, соответствующей правильному разделению последовательности f (D) па последовательности Т1(D) и Т2(D)

Блок 17 тактовой синхронизации в 20 течение одного импульса Г1 формирует на своем первом выходе 27 пакет из N тактовых импульсов Г а на т втором вьгхаде 28 —. импульс конца цикла, которые используются совмест- 25 но с импульсами F1 для синхронизации остальных блоков устройства, На входы блока 1 вычисления метрик ветвей поступают триадами решения, вынесенные демодулятором а пере- данных двух канальных символах саотФ ,вественна из последовательностей л

11(9) и Ò2(0), На вторые входы блока поступают двоичные триады с кодеров 9.1 и 9.2, представляющие собой значения ветвей реаетчатай диаграммы, задаваемые формирователем 10 адресов считывания. На первых выходах блока

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

Выходы блока 1 вычисления метрик ветвей подключены к входам сумматоров 2.

2.1 и 2.2, вторые входы которых подключены к входам блока 8 памяти метрик

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

161237

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

Одна ветвь. Информация о переходах йодается на управляющий вход блока 1 4 памяти путей, 10

Формирователь 12 адресов памяти путей„ формирователь 13 памяти путей, йрослеживания путей, обеспечквающие подключение соответственна старших. и младших разрядов адреса коммутато фы 5 и 6, алак 14 памяти путей, блок

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

Пути. Поскольку достаточным является прослеживание.на глубину 1. = =/5-6)<К, тс. необходимо хранение III»формации о переходах черeз N = 2 " 25 узлов на длине Ь шагов. Хранение информации о переходах осуществляется в блоке 14 памяти путей, адресное пространство которого .организовано в виде адресного кольца длиной О (фиг.8) . При такой организации нет необходимости выполнять сдвиг инфозмации на длине Е, а модифицируется только адрес текущего шага по решетчатой диаграмме. 35

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

Адрес перехода в решетчатой диаграмме состоит из адреса узла, в котсрый выполнен переход (младшая часть), и адреса шага по решетчатой диаграмме (старшая часть) (фиг.7). При зтам объем памяти путей, необходимый для хранения информации с переходах, составляет М = 1. И бит. При записи решений последовательно перебираются адреса узлов формирователем 11 адреса 1;О записи и адреса шагов пс решетчатой диаграмме формирователем 12 адреса памяти путей. Решения записываются в блок 14 памяти путей по полученному адресу перехода, который передается через коммутаторы 5 и 6 (старших и младших разрядов памяти путей).

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

14 информация поступает на вход блаха 15 прослеживания путей,. который формирует навык адрес узла (фиг.7).

Прн прослеживании путей адреса шагов по решетчатой диаграмме перебираются формирователем 13 ацресов просле>лвания путей, начиная с текущего адреса записи, в обратном направленич, для чего в начале прослеживания текущий адрес переписыв"-ется из "„ Ioðìèрователя 12 адресов памяти путей в формирователь 13 адресов прослеживания путей.

Паскальк г в конце прослеживания непрерыв ого пути на:глуби,.у L шагов на выходе сцвигавогс регистра блока .15 присутствует информация о К-1 самых старых переходах, зта информация выдается на решающий блок 16, как решение декодера, Решаю.ций блок :6, выход котс-.рого является выходом Jcòðoèства, в течение К-1 инфсрмацчанн ьх . тактов Г преобразует решение декодера из параллельного кода в последовательный.

Прослеживание непрерывнога путч ведется синхронно с записью решений, причем за время обработки одного узла решетчатой диаграммы производится адин шаг прослеживания и запись решения, Так как прслеживание Eiäåòñÿ в течение К-1 информационных тактов Р1, а в течение одного инфармацианногo такта Г обрабатывается последовательно И узлов. то длина прослеживания - ( составляет 1. =- h (К-1) = (К-1) ° 2 шагов, что удаглетвсряет условию

1, (5-6) K при К ) 4.

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

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

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

1. Устройство для декодирования сверточного кода, содержащее блок вы l5 числения метрик ветвей, информационный вход которого является информационным входом устройства, формирователь адресов считывания, первые и вторые выходы которого соединены с вхо- 20 дами соответственно первбго и второго кодеров, выходы которых подключены соответственно к первым и вторым адресным входам блока вычисления метрик, ветвей, первые и вторые выходы кото- 25 рого соединены с первыми входами соответственно первого и второго суммато- ров, выходы которых подключены соответственно к первым и вторым информационным вхопам первого коммутатора и к первым и вторым входам блока сравнения, выход которого соединен с управляющим входом первого коммутатора, формирователь адресов записи, выходы которого и третьи выходы формирователя адресов считывания подключены к первым и вторым адресным входам блока памяти метрик, первые и вторые выходы которого соединены с вторыми входами соответственно первого и второго сумматоров, блок нормированного порога, входы которого объединены с информационными входа.и блока памяти метрик, блок памяти путей, второй и третий коммутаторы, о т л и ч а ю щ е— е с я тем, что, с целью упрощения, 45 в устройство введены формирователь адресов памяти путей, формирователь адресов прослеживания путей, блок прослеживания путей, решающий блок и блок тактовой синхронизации вход синхронизации которого объединен с входом формирователя адресов памяти путей и входом синхронизации решающего блока и является входом синхронизации устройства, выходы первого ком55 мутатора соединены с входами блока нормированного порога, выходы которого подключены к третьим входам сумма8 l0 торов, первый выход блока тактовой синхронизации соединен со счетным входом формирователя адресов прослеживания путей, тактовыми входами блока прослеживания путей, блока памяти путей, второго и третьего коммутаторов и входами формирователя адресов считывания и формирователя адресов записи, второй выход блока тактовой синхронизации подключен к управляющему входу формирователя адресов прослеживания путей, управляющие входы блока тактовой синхронизации объединены с первыми информационными входами второго коммутатора и подключены к выходам формирователя адресов записи, выходы формирователя адресов памяти путей соединены с первыми информационными входами третьего коммутатора и установочными входами формирователя адресов прослеживания путей, первые и вторые выходы которого подключены соответственно к вторым информационным входам третьего коммутатора и управляющему входу решающего блока, выходы второго и третьего коммутаторов соединены с первыми и вторыми адресными входами блока памяти путей, управляющий вход которого подключен к выходу блока сравнения, выход блока памяти путей соединен с информационньг". входом блока прослеживания путей, вь ходы .-<оторого подключены к вторым информационным входам второго коммута. тора и информационным входам решающего блока, выход которого является выходом устройства. !

2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок тактовой синхронизации содержит генератор тактовых импульсов, делитель частоты, первый и второй триггеры и элемент

И-HE. вкоцы которого являются управляющими входами блока, выход элемента И†i!F. соединен с тактовым входом второго триггера, тактовый вход первого триггера является входом синхронизации блока, выход генератора тактовых импульсов подключен к счетному входу делителя частоты, выход которого является первым выходом блока, выход первого триггера соединен с установочньгы входами делителя частоты и второго триггера, выход которого подключен к установочному входу первого. триггера и является вторым выходом блока.

I1 1612378 !2

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

101

11О

Адресуют. ооо

001

0f1

101

f10! 612378

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

Редактор И.Дербак Техред N.Õoäàíè÷ Корректор М.Максимищинец

Заказ 3835 . Тираж 662 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 1р1