Декодер сверточного кода

 

Изобретение относится к электросвязи и может быть использовано в цифровых системах передачи сверточным кодом при декодировании по алгоритму Витерби. Целью изобретения является повышение быстродействия устройства. Устройство содержит синхронизатор 1, блок 2 вычисления метрик ветвей, каналы 3 обработки, состоящие из компаратора 4, блока 5 стирания и вычитателя 6, блок 7 вычисления метрик состояния, блок 8 памяти, блок 9 коррекции, блок 10 тактирования и регистр 11. 10 ил.

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

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

РЕСПУБЛИК (я)5 Н 03 М 13/12

ГОСУДДРСТВЕННЬЯ КОМИТЕТ

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

ПРИ ГКНТ СССР

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

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

Вхо (21) 4626945/24 (22) 26.12,88 (46) 30.06.91, Бюл. ¹ 24 (72) А.В. Савчук (53) 621.394.14 (088,8) (56) Авторское свидетельство СССР

¹ 675616, кл. Н 03 М 13/12, 1977.

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

¹ 1319283, кл, Н 03 M 13/12, 1984, Кларк Дж., Кейн Дж. Кодирование с исправлением. ошибок в системах цифровой связи. M. РиС, 1987, с. 237, рис. 6.20. (54) ДЕКОДЕР СВЕРТОЧНОГО КОДА.. Ж 1660178 А1 (57) Изобретение относится к электросвязи и может быть использовано в цифровых системах передачи сверточным кодом при декодировании по алгоритму Витерби. Целью изобретения является повышение быстродействия устройства. Устройство содержит синхронизатор 1, блок 2 вычисления метрик ветвей, каналы 3 обработки. состоящие из компаратора 4, блок 5 стирания и вычитателя 6, блок 7 вычисления метрик состояния, блок 8 памяти, блок 9 коррекции, блок 10 тактирования и регистр 11. 10 ил., 2 табл. о 0

О, 00

1660178

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

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

На фиг.1 приведена структурная схема декодера сверточного кода; на фиг. 2 — синхронизатор; на фиг,З вЂ” блок вычисления метрик ветвей; на фиг,4 — вычитатель; на фиг.5 — блок стирания; на фиг.б — блок вычисления метрики состояния; на фиг.7 — узел сравнения — сложения — выбора; на фиг.8— блок коррекции (на фиг,2 — 8 раскрыты отдельные блоки декодера сверточного кода на примере кода со скоростью 1/2 и кодовым ограничением 2); на фиг.9 — графическая иллюстрация процесса декодирования полностью нулевой кодовой последовательности по алгоритму Витерби с помощью известных декодеров (a); то же, но с помощью данного декодера (б); на фиг.10 — декодиро. вание полностью нулевой последовательности с помощью "сокращенного" поиска на основе известных принципов (а); то же, но на основе принципа обработки метрик ветвей, предложенных в изобретении (б).

Устройство содержит синхронизатор 1, блок 2 вычисления метрик ветвей, каналы 3 обработки, состоящие из компаратора 4, блока 5 стирания и вычитателя 6, блок 7 вычисления метрик состояния, блок 8 памяти, блок 9 коррекции, блок 10 тактирования и регистр 11.

Синхронизатор 1 содержит инвертор

12, ключи 13-24, D-триггеры 25-30.

Блок 2 вычисления метрик ветвей содержит регистры 31 и 32 и узел 33 постоянной памяти.

Вычитатель б содержит группу 34 инверторов, сумматоры 35 и 36 и мультиплексор 37.

Блок 5 с гира ния содержит элементы 3843 ИЛИ.

Блок 7 вычисления метрик состояния содержит узлы 44 — 47 сравнения — сложения — выбора и узел 48 сравнения.

Блок 9 коррекции содержит сумматоры

49 — 51 по модулю два, инвертор 52, элементы И 53 — 55, элементы ИЛИ 56 и 57, счетчики

58 и 59 импульсов и D-триггер 60.

Каждый из узлов 44 — 47 сравнения — сло-жения — выбора (ССВ) содержит компаратор

61, мультиплексор 62, регистр 63 и сумматоры 64 и.65,, Декодер работает следующим образом.

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

5 соответствует однбй принятой кодовой ветви.

Так как в непрерывной последовательности трехбитовых сигналов

o) Ео

Е1

Ег

Кг) В априори не известны границы кодовых ветвей, то имеются две возможности их группи15 рования;, Правильная синхронизация ветвей

Ао

" A1

Аг

Неправильная синхронизация ветвей

25 Синхронизатор 1 обеспечивает правильную синхронизацию ветвей по сигналу, который поступает на его второй вход, Выходные сигналы синхронизатора 1 переписываются в блок 2 вычисления метрик

30. ветвей с тактовой частотой, в два раза меньшей.

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

40 Предположим, что принята без ошибок кодовая ветвь "01". Тогда на группе выходов

М2 появится метрика ветви "01", которая равна "000" и соответствует позиции А7 в матрице (отмечена в таблице кружком). На

45 группе выходов М2 появится метрика ветви

"10", которая равна "111" и соответствует десятичному эквиваленту "7" в тои же позиции А7, На группах выходов М1 и М1 противоположных метрик ветви "00" и "11" в тех

50 же позициях А7 появятся равные значения

"3", которые являются десятичным эквивалентом числа "011". Когда эти равные значения поступают на входы вычитателя 6, то на его выходе сигнал будет равен 3- 3- О. Он

55 подается на первый вход компаратора 4 и, поскольку пороговый сигнал на втором входе компаратора 4 не менее "0", то на его выходе появится сигнал лог. "1" и вызовет на обоих выходах блока 5 сигналы "111" независимо от того, какие значения метрик

1660178

20

55 ветвей имели место на его первых и вторых входах.

Это означает, что метрики ветвей, вычисленные в блоке 2, "стерты", а в блок 7 через регистр 11 поступает информация о том, что передача кодовых ветвей "00" и "11" маловероятна, Разность метрик ветвей "01" и "10", полученная в соответствующем вычитателе 6, входы которого подключены к выходам . М2 и М2, равна "0" — "7"= -"7".

Абсолютную величину этой разности "7" вычитатель 6 выдает на входы соответствующего компаратора 4 и поскольку пороговый сигнал на его втором входе не превышает

"7", то на выходе компаратора появится сигнал лог. "0", который обеспечит без изменений поступление вычисленных в блоке 2 метрик ветвей "01" и "10" на входы блока 7 через блок 5 и регистр 11, Это означает, что

:в блок 7 поступает информация о том, что кодовая ветвь "01" наиболее вероятна, а кодовая ветвь "10" маловероятна.

Дальнейшая обработка метрик ветвей в блоке 7, блоке 8 памяти и в блоке 9 коррекции не отличается от обработки в известных декодерах. В,частности, в блоке 9 непрерывно оценивается качество приема по резуль. татам декодирования. Если качество приема оказывается ниже допустимого уровня, то выносится решение о том, что синхронизация ветвей неправильна и на второй вход синхронизатора 1 подается сигнал для коррекции ветвей синхронизации.

Блок 7 вычисления метрик состояния работает следующим образом.

На тактовый вход блока 7 вычисления метрик состояния поступает сигнал от блока

10. Синхронно с тактовым сигналом (границы битов совпадают с переходом тактового сигнала от лог. "0" к лог. "1") на информационные входы блока 7 от регистра 11 поступают в параллельном коде трехбитовые метрики ветвей, которые обозначены на фиг,6 следующим образом: М1 — метоика ветви "00"; M1 — метрика ветви "11"; М2-метрика ветви "01"; М2 — метрика ветви

"10".

Как видно из фиг.6, блок 7 состоит из

2 (в данном примере v = 2) идентичных об. рабатывающих узлов 44-47 ССВ, которые работают одновременно, одинаково и во взаимодействии друг с другом. Поэтому рас-. смотрим работу одного узла ССВ.

В узле 45 ССВ хранится четырехразрядное двоичное число — назовм его метрикой состояния М7-2. Это число суммируется с двумя метриками ветвей М2 и М2, поступающими на входы узла 45 ССВ регистра 11.

В результате образуются две суммы, которые обозначим следующим образом; М2

+М7 — 2; M2 + М7-2.

Первая из этих сумм поступает на вход узла 46 ССВ, а вторая — на вход узла 47

CCB.

В результате аналогичной операции в узле 44 ССВ образуется сумма М1 + М7 — 1, которая с выхода узла 44 CCB поступает на вход узла 45 ССВ. Также в узле 46 CCB образуется сумма М1 + М7-3, которая с выхода узла 46 поступает на вход узла 45

CCB.

Указанные две суммы сравниваются друг с другом в узле 45. Если выполняется неравенство М1 + М7-1 > M1 + М7-3, то на выходе узла 45 появляется уровень лог, "1".

С этого момента времени в узле 45 в качестве метрики состояния М7 — 2 будет храниться сумма Mi + M7 i: М7-2 = M1 + М7-1, а предыдущее значение М7-2 стирается.

Если же М1 + М7-1< М1 + M7 — 3, то в узле 45 в качестве метрики состояния М7 — 2 будет храниться сумма M1 + M7 — 3: М7 — 2=

= М1 + М7 — 3, а предыдущее значение М7-2 также стирается.

Аналогично работают остальные узлы

44, 46 и 47 ССВ.

Вновь полученные метрики состояния через выходы всех узлов 44 — 47 ССВ поступают на 2 входов узла 48 сравнения. В узле

48 все 2" метрик состояний сравниваются между собой по величине. Сигналы на выходах узла 48 формируются в соответствии с табл. 2.

Из этой табл. 2 следует, что лог, "1" появляется только на одном из двух выходов узла 48 сравненИя, а именно на том, который соответствует наибольшей метрике состояния.

Электрическая принципиальная схема узлов 44 — 47 ССВ изображена на фиг.7, Применительно к узлу 45 на верхние входы его поступает метрика М2 ветви 01, а на нижние входы — метрика М2 ветви 10. В сумматорах

64 и 65 соответствующие метрики ветвей суммируются с метрикой состояния М7 — 2, которая хранится в регистре 63. Результаты суммирования через выходы узла 45 поступают на соответствующие. входы узлов 46 и

47.. Одновременно на входы узла 45 поступают результаты суммирования от соответствующих выходов узлов 44 и 46, которые сравниваются по величине в компараторе

61 на фиг.7. Выходной сигнал компаратора

61 поступает на выход и одновременно управляет мультиплексором 62. Если реэультат суммирования. поступающий на входы

А1, ..., А4 компаратора 61, больше результата суммирования, поступающего на его входы Bi, „., В4, то на выходе компаратора 61

1660178

20

ЗО

55 имеет место лог. "1", В противном случае появляется лог, "0", В том случае, если на входе А/B мультиплексора 62 появляется лог. "1", то на его выходы проходит четырехразрядный сигнал через входы узла 45 ССВ, Если же на входе

А/В мультиплексора 62 появляется лог. "0", то на его выходы проходит четырехразрядный сигнал через третьи выходы 4.

Выходы мультиплексора 62 подключены к входам регистра 63, поэтому при изменении тактового сигнала на входе от лог, "О" к лог. "1" выходной сигнал мультиплексора

62 записывается в регистр 63 в качестве новой метрики состояния М7 — 2. Далее описанный цикл повторяется, Вычитатель работает следующим образом.

Пусть необходимо вычислить разность двух чисел; уменьшаемое М1 = 1(10) = 001 (2); вычитаемое М1 = 7(10) = 111 (2).

Тогда в сумматоре 35 выполняются следующие операции.

Сигналы на входах А3, А2, А1, АО: 0001, Сигналы на входах ВЗ, В2, 81, ВО; 1000.

Сигналы на входе PO:, . 1, Сигналы на выходах $3, S2, S1, SO: 1010.

В сумматоре 36 выполняются следующие операции.

Сигналы на входах А2, А1, AO: 010, Сигналы на входах В2, 81, ВО; 111.

Сигнал на выходах S2, S11, SO; 110.

Сигнал 3 с выхода сумматора 35 воздействует на управляющий вход АВ мультиплексора 37 так, что и ри SÇ = 1 на его выходы проходят сигналы 110 (2) = 6 (10). что, очевидно, является модулем разности двух чисел 1 и7, В случае, когда уменьшаемое больше вычитаемого, то на выходе SÇ сумматора 35 имеет место сигнал S3 = О, который воздей ствует на управляющий вход АВ мультиплексора 37 так, что на его выходы проходят сигналы S2, S1, SO с выходов сумматора 35.

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

Для сравнительной оценки традиционного и предложенного принципов обработки метрик ветвей сделан прямой расчет процесса декодирования сверточного кода при работе в двоичном симметричном кана-ле с вероятностью ошибки 001. Результаты представлены в виде "решетчатой диаграммы" на фиг.9 процесса декодирования.

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

4-и и 5-м шагах декодирования вызвали ошибочное событие на 4-м-9-м шагах декодирования, которое заключается в том, что декодированная. последовательность не совпадает с переданной (полностью нулевой последовательностью).

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

Как видно иэ фиг..9а, вплоть до 24-ro, шага декодирования, в памяти декодера хранятся три последовательности, которые расходятся друг с другом на 4-м и 8-м шагах декодирования, Следовательно, на 24-м шаre декодирования еще нельзя утверждать, что, начиная с 10-го шага декодированИя, событие будет правильным, поскольку на

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

Как видно из фиг.9б, предложенный принцип обработки метрик ветвей приводит к значительно лучшему результату. При точно такой же ошибке в канале (4-я и 5-я ветви приняты как "11", хотя передавалась полностью нулевая последовательность) ошибочного события вообще не происходит, а, начиная с 9-го шага декодирования, все последовательности, которые хранятся в памяти декодера (они также выделены полужирными линиями) слились в одну правильную последовательность в ветвях 1-9.

Это означает, что на 9-м шаге декодирования можно с уверенностью сказать. что эти ветви приняты правильно. В этом конкретном примере задержка декодирования, равная 14 -.3 =- 11 шагам, оказывается достаточной для исправления ошибки в канале. В то же время при традиционной обработке задержка кодирования, равна

24- 3 = 21 шагу недостаточна для надежного декодирования.

Еще более значительный эффект дает предлагаемый принцип обработки метрик ветвей в случае процедуры "сокращенного поиска",основанного на алгоритме Витерби.

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

1660178

Таблица 1

13."

1

0

0

0 (1

3

4

6

0

0

1

3

1

0

0

2

0

0

3

1

0

0

0

0

1

3.

2

2

4

5 б

5

3

2

4

2

0

0 а

4

2

1

0

0

0

2

А

Б

Г

Д

Ж

0

0

2

0

0 . 0

2

1

1

3

7

5

3

3

А

Б

В

Г

Д

Е

Ж

3 4

2 3

6 7

1 2

5 6

0 1

А

Б

В

Г

Д

Е

Ж

Г 7, 6

4

3

0

0

0

2

2

0

0

3

1

0

0

0 б

5 . 4

2

2

0

0

2

0

0

0

2

0

0

2

0

0

1

3

1

0

0

4

2

1

1,,А

" Б

В

Г

Д

Е

Ж

3

1

0 а

1

0

0

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

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

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

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

Метрика М1 ветви "00"

Метрика М2 ветви "01" коррекции, первый и второй выходы которого подключены соответственно к выходу декодера и второму входу синхронизатора, третий вход которого подключен к первому

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

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

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

Метрика М1 ветви "11"

Метрика М2 ветви "10"

1660178

12

Таблица 2

Вход

/(&ану2

1660178

Фиг. Х

Orn блоков

7- ... 7-

16601 8

К длакаи

7-7... 7- Ф

5 К Юлвгу

7-Х

1660178

От

bnos(a

8 кф

Фиг. 8

ПРаВильиав кИой7у по слИа8атель носам оо по о о. 1 Л Э 4 Я 6 7 g 9 1о 11 12 13 И обочное сань!тие пра3ильнай ко3а3оя после3о3атепьность

/ оо оо оо ао оо оо оо оа оо оо оо оо оо оо оо.

4 5 6 7 8 9 1D11 2Q 14 1576111В 13202Т228324i сц

Q.

1660178

ence gOdngO ag Ища dauOe

С) о с>

С

Сэ

Редактор Е.Копча

Заказ 1855 Тираж 466 Подписное

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

113035, Москва, Ж-35, Рауйская наб„4/5

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

Ь

Ф с

9 о

Cb о с

late с, Ъ <

Составитель О.Тюрина

Техред М.Моргентал КоРРектоР Т.Пали