<< Предыдущая

стр. 44
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

( 4 -64)
T(I, D, J) = ID3J2(1 + IDJ + I2D2J2 + I3D3J3 + •••)=
J 4 + / 4 ? > 6 J5 + • • • .
= ID3J2 + I2DAJ3 + I3Db

Учитывая, что dfree определяется наименьшим показателем D в ве-
совой функции, имеем
dfree = 3. (4.65)
4. Код не является катастрофическим, так как единственная
«петля» на модифицированной диаграмме состояний обладает весом
IDJ и, следовательно, повышает вес кодовой последовательности на
единицу.
4-6. Декодирования по максимуму правдоподобия

4.6. Декодирования по максимум/ правдоподобия
Для декодирования сверточных кодов имеются две альтернативы:
последовательное декодирование и алгоритм Витерби.
Алготитмы последовательного декодирования - стек-алгоритм
или алгоритм Фано могут рассматриваться как методы проб и оши-
бок при поиске правильного пути на кодовом дереве. В ряде прило-
жений использование последовательного декодирования может быть
весьма эффективным. Для ознакомления с алгоритмами последова-
тельного декодирования см. например, [о].
В настоящее время для декодирования сверточных кодов исполь-
зуют, как правило, алгоритм Витерби, который является частным
случаем динамического программирования. Динамическое програм-
мирование применяется при решении задач математической оптими-
зации. Одной из таких задач является, например, прокладка шоссей-
ных дорог на местности. В этой задаче требуется проложить дороги
таким образом, чтобы общая длина была бы минимальной. Анало-
гичная задача возникает при декодировании сообщений. Здесь роль
местности играют состояния на сетевой диаграмме, а роль общей
длины пути берет на себя некоторая метрика. Идея алгоритма Ви-
терби интуитивно возникает при внимательном рассмотрении сете-
вой диаграммы, поэтому, прежде всего рассмотрим пример, а затем
займемся теоретическими обобщениями.
Пример: Декодирование сверточного (3,1,2)-кода с использова-
нием сетевой диаграммы.
Исходным пунктом декодирования служит сетевая диаграмма
рис. 4.8. Мы предполагаем, что кодирование начинается и закан-
чивается в состоянии So- Поиск альтернативных кодовых последо-
вательностей сводится к поиску альтернативных путей на- сетевой
диаграмме (рис. 4.16.).
Предположим, что в канале не произошло ошибок, тогда на де-
кодер поступает кодовая последовательность
{r[n}} = {v[n}} = {1,1,1,0,1,0,1,1,0,0,1,1,1,1,1,1,0,1,0,1,1}. (4.66)
Каким образом декодер может определить, какая последовательность
была передана?
Декодер сравнивает биты принятой последовательности с битами
возможных кодовых последовательностей и выбирает из всех кодо-
вых последовательностей ту, которая наиболее «похожа» на приня-
тую. Для независимых ошибок в канале мерой «похожести» является
расстояние Хэмминга.
,246 Глава 4- Сверточные коды




Рис. 4.16. Сетевая диаграмма сверточного (3,1,2)-кодера,
соответствующая (4.36).

Сравнение расстояний Хэмминга всех кодовых последовательно-
стей может быть эффективно реализовано с помощью сетевой диа-
граммы. На рис. 4.17 показан алгоритм декодирования и его резуль-
таты.


IT in 111 Oil
у у у \
0 wo 2
n
по/° г л / т / . т Л пп \



3 1 О I 2 Too] 2 I 1001 2
Конец
Начальное Пугь
Ч-О
Декодированная щ = 1
состояние
последовательность
Принятый
ш ою мо он
вектор

о 1 7
6 Такт


Рис. 4.17. Сетевая диаграмма декодера.

На нервом шаге возможны два пути из нулевого состояния ^о-
Декодер, прежде всего, сравнивает принятую тройку бит с трой-
ками бит двух возможных путей. Найденные при этом расстояния
Хэмминга являются метриками этих путей. Так как один путь ве-
4-6. Декодирования по максимуму правдоподобия

дет в состояние So, а второй в состояние S\, в текущих регистрах
метрик состояний So и Si записываются метрики соответствующих
им путей (см. рис. 4.17). Одновременно в текущие регистры путей
записываются первые разряды соответствующих информационных
последовательностей («О» - для So и «1» Si).
На втором шаге декодирования из каждого состояния (So и Si)
также возможны два перехода. Декодер прибавляет новые расстоя-
ния Хэмминга к текущим метрикам прежних состояний So и Si. По-
лученные таким образом новые метрики заносятся в регистры мет-
рик новых состояний So, Si и S2, S3. В регистры путей этих состоя-
ний заносятся соответствующие им теперь уже вторые информаци-
онные разряды. В конце второго шага декодирования все возможные
состояния сетевой диаграммы оказываются достигнутыми.

Предыдущее Последующее
состояние состояние
Накопленная
Метрика 0 -*" метрика
3-
0+3=3
min
Приращение
11
Путь
5+2=7 111 Продолжение
У
. пути

Метрика
Метрика 5 Выбор пути с
наименьшей
01
Путь метрикой


Р и с . 4 . 1 8 . Выбор пути с наилучшей метрикой.


На третьем шаге декодирования производится аналогичная про-
цедура. Здесь, однако, впервые оказывается, что в каждое новое со-
стояние ведут два пути. Вот тут то и раскрывается сущность дина-
мического программирования. В качестве примера на рис. 4.18 рас-
смотрена процедура декодирования нового состояния S3. В новое со-
стояние S3 могут переходить два прежних состояния Si и S3 с прира-
щениями метрик, равными 2 и 3 соответственно. С учетом прежних
значений, новые метрики путей равны: от состояния Si - 7 и от со-
стояния S3 - 3, поэтому, на третьем шаге декодирования, в качестве
предшествующего новому состоянию S3, мы выбираем прежнее со-
стояние Ss- Метрику нового состояния S3 полагаем равной трем и,
в качестве третьего информационного разряда, выбираем бит пере-
хода S3 — S3, равный «1». Дальнейшее приращение метрик путей,
>
выходящих из состояния S3, не зависят от метрики S3, накопленной
на третьем шаге, поэтому, на третьем шаге декодирования, мы мо-
Глава 4- Свертпочные коды


жем смело отбросить переход Si — S3, как обладающий большей
>
метрикой, чем переход S3 — S3.
>
Таким образом, сущность динамического программирования за-
ключается в том, что на каждом шаге декодирования но сетевой диа-
грамме для каждого состояния мы выбираем единственный, втекаю-
щий в него путь с минимальной метрикой (в случае равных метрик
выбор одного из двух путей осуществляется произвольно).
Дальнейшие шаги декодирования производятся аналогично. При
практической реализации процесс декодирования в данном примере
можно существенно упростить. Из рис. 4.7 видно, что уже на тре-
тьем шаге всем состояниям предшествует первый бит информацион-
ной последовательности, равный «1», поэтому, первый информаци-
онный символ уже можно выдать потребителю и в дальнейшем не
учитывать. Таким образом снижается длина регистров пути декоде-
ра и уменьшается время задержки декодирования. Окончательно, на
7-ом шаге декодирования мы выбираем в состоянии So путь, облада-
ющий наименьшей метрикой. Содержимое регистра пути состояния"
So дописывается к ранее продекодированным информационным сим-
волам и, тем самым, процесс декодирования заканчивается.
Рассмотренный пример раскрывает основы алгоритма Витерби.
Процесс декодирования по максимуму правдоподобия обобщает рис.
4.19. Для наглядной интерпретации представим кодовую последова-
тельность в виде вектора v = (VQ, VI,I>2, •..).

л нформацион ное Кодовое Принятое Декодированное
слово Сверточный! слово Декодер˜
˜˜ слово
U V
кодер 1 сверточного


Кодирование Декодированние по максимуму правдоподобия
-* Отображение 2*возможных двоичных -» Выбор наиболее вероятного
информационных слов и длины N в кодового слова из 2" возможных '
2" возможных кодовых слов v при известном принятом слове г



Р и с . 4.19. Декодирование по максимуму правдоподобия.

Задачу декодера максимального правдоподобия (МП) можно сфор-
мулировать следующим образом: имея принятый вектор г из всех
возможных слов v, принадлежащих коду, выбрать такое v, для кото-
рого
P(r/v)=maxP(r/y). (4.67)
Решение задачи декодирования по МП зависит от выбранной мо-
дели канала. Для источников и каналов без памяти ( например, для
249)
4-6. Декодирования по максимуму правдоподобия

канала с АБГШ) задача упрощается. В этом случае передача отдель-
ных бит кодовой последовательности длины J происходит независи-
мо. Вместо того, чтобы для вычисления P(r/v) рассматривать всю
последовательность, мы можем свести вычисление P(r/v) к произ-
ведению условных вероятностей отдельных бит

«/-1
P(r/v) = J ] PWvj). (4.68)

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

J-1
logP(r/v) = max Д logP(r,/uj). (4.69)
j=o

Для каналов без памяти декодирование но максимуму правдоподо-
бия может быть реализовано с помощью алгоритма Витерби с наи-
меньшими затратами. Введем следующие вспомогательные величи-
ны:
1. Метрику кодовой последовательности vi

M(r/vi) = log M(r/v 4 ); . (4.70)

2. Приращение метрики, как вклад j-ой компоненты

(4.71)
М (гj/viJ) = log Pirj/Vij);

3. Частичную метрику, как промежуточную сумму

fc-i
(4.72)
Mk(r/Vi) = ^2M(rj/vij).
l
j=

Работа декодера Витерби показана на рис. 4.17 и 4.18. Для каж-
дого состояния вычисляются метрики всех вливающихся в него пу-
тей. Величина приращений метрик зависит от модели канала. Ниже
будут представлены два примера вычисления метрик. Для каждо-
го конкретного состояния величина приращений метрик выходящих
из него путей не зависит от метрик путей, вливающихся в него. На
Глава 4- Сверточные коды


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

2. На каждом шаге декодирования определяются 2М+1 прираще-
ний метрик. Частичные метрики подсчитываются и сравнива-
ются.

<< Предыдущая

стр. 44
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>