Вернер М. Основы кодирования (2004) (1151849), страница 35
Текст из файла (страница 35)
Для ознакомления с алгоритмами последовательного декодирования см. например, [о].В настоящее время для декодирования сверточных кодов используют, как правило, алгоритм Витерби, который является частнымслучаем динамического программирования.
Динамическое программирование применяется при решении задач математической оптимизации. Одной из таких задач является, например, прокладка шоссейных дорог на местности. В этой задаче требуется проложить дорогитаким образом, чтобы общая длина была бы минимальной. Аналогичная задача возникает при декодировании сообщений. Здесь рольместности играют состояния на сетевой диаграмме, а роль общейдлины пути берет на себя некоторая метрика. Идея алгоритма Витерби интуитивно возникает при внимательном рассмотрении сетевой диаграммы, поэтому, прежде всего рассмотрим пример, а затемзаймемся теоретическими обобщениями.Пример: Декодирование сверточного (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 показан алгоритм декодирования и его результаты.ITinwno 2111Oilууу\по/° г л / т / . т Л пп \03 1 О I 2 Too] 2 I 1001 2НачальноесостояниеП у г ьПринятыйшвектороКонецДекодированная щ = 1последовательностьоюмоЧ-Оон16 Такт7Рис. 4.17.
Сетевая диаграмма декодера.На нервом шаге возможны два пути из нулевого состояния ^оДекодер, прежде всего, сравнивает принятую тройку бит с тройками бит двух возможных путей. Найденные при этом расстоянияХэмминга являются метриками этих путей. Так как один путь ве-4-6. Декодирования по максимуму правдоподобиядет в состояние So, а второй в состояние S\, в текущих регистрахметрик состояний So и Si записываются метрики соответствующихим путей (см. рис.
4.17). Одновременно в текущие регистры путейзаписываются первые разряды соответствующих информационныхпоследовательностей («О» - для So и «1» Si).На втором шаге декодирования из каждого состояния (So и Si)также возможны два перехода. Декодер прибавляет новые расстояния Хэмминга к текущим метрикам прежних состояний So и Si. Полученные таким образом новые метрики заносятся в регистры метрик новых состояний So, Si и S2, S3. В регистры путей этих состояний заносятся соответствующие им теперь уже вторые информационные разряды. В конце второго шага декодирования все возможныесостояния сетевой диаграммы оказываются достигнутыми.ПредыдущеесостояниеМетрика0Путь11Метрика5Путь01ПоследующеесостояниеНакопленная0+3=3ПриращениеУ5+2=7Метрикаmin3 - -*" метрика111Продолжение.
путиВыбор пути снаименьшейметрикойР и с . 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, •..).л нформацион ноеКодовоесловоСверточный! словоUVкодер1Кодирование-* Отображение 2*возможных двоичныхинформационных слов и длины N в2" возможных кодовых слов vПринятое~~Декодер~сверточногоДекодированноесловоДекодированние по максимуму правдоподобия-» Выбор наиболее вероятногокодового слова из 2" возможных 'при известном принятом слове гР и с . 4.19.
Декодирование по максимуму правдоподобия.Задачу декодера максимального правдоподобия (МП) можно сформулировать следующим образом: имея принятый вектор г из всехвозможных слов v, принадлежащих коду, выбрать такое v, для которогоP(r/v)=maxP(r/y).(4.67)Решение задачи декодирования по МП зависит от выбранной модели канала. Для источников и каналов без памяти ( например, для4-6. Декодирования по максимуму правдоподобия249)канала с АБГШ) задача упрощается. В этом случае передача отдельных бит кодовой последовательности длины J происходит независимо.
Вместо того, чтобы для вычисления P(r/v) рассматривать всюпоследовательность, мы можем свести вычисление P(r/v) к произведению условных вероятностей отдельных бит«/-1P(r/v) = J ] PWvj).(4.68)С точки зрения технических затрат, произведение условных вероятностей удобнее свести к сумме их логарифмов. Логарифмическаяфункция является монотонной и не изменяет соотношение междувеличинами условных вероятностей кодовых последовательностей.В этом случае, для логарифмической функции правдоподобия, (4.67)преобразуется в равенствоJ-1logP(r/v) = max Д logP(r,/uj).(4.69)j=oДля каналов без памяти декодирование но максимуму правдоподобия может быть реализовано с помощью алгоритма Витерби с наименьшими затратами.
Введем следующие вспомогательные величины:1. Метрику кодовой последовательности viM(r/vi) = log M(r/v 4 );.(4.70)2. Приращение метрики, как вклад j-ой компонентыМ (гj/viJ)= log Pirj/Vij);(4.71)3. Частичную метрику, как промежуточную суммуfc-iMk(r/Vi) = ^2M(rj/vij).(4.72)lj=Работа декодера Витерби показана на рис.
4.17 и 4.18. Для каждого состояния вычисляются метрики всех вливающихся в него путей. Величина приращений метрик зависит от модели канала. Нижебудут представлены два примера вычисления метрик. Для каждого конкретного состояния величина приращений метрик выходящихиз него путей не зависит от метрик путей, вливающихся в него. НаГлава 4- Сверточные кодыкаждом такте для каждого состояния из всех путей, в него вливающихся, декодер выбирает для продолжения единственный путь, обладающий наибольшей метрикой.После того, как алгоритм Витерби описан в общих чертах, можнооценить его сложность.1.
Для декодера с памятью М существует Iм возможных состояний.2. На каждом шаге декодирования определяются 2М+1 приращений метрик. Частичные метрики подсчитываются и сравниваются.3. На каждом шаге декодирования в память заносятся 2телей путей с частичными метриками этих путей.указа-Можно заметить, что сложность декодера Витерби экспоненциальновозрастает с ростом памяти декодера.Пример: Метрика декодера при передаче информации по двоичному симметричному каналу (ДСК).Двоичный канал без памяти (ДСК), по определению, являетсяканалом, в котором передаваемые биты искажаются независимо другот друга с вероятностью е (см. рис. 4.20).Р и с . 4.20.
Диаграмма передачи информации по двоичномусимметричному каналу.При декодировании по максиму правдоподобия сравниваютсяусловные вероятности кодовых слов (4.67). Условная вероятностьсобытия, при котором при передаче слова Vj принимается слово г,для ДСК определяется только расстоянием Хэмминга d#(r, Vj). Еслидлина кодовой последовательности равна J, то эта условная вероятность равна произведению вероятностей искажения d# (r,Vj) двоичных символов и правильного приема J — d#(r,Vj) бит.
Переходя к4-6. Декодирования по максимуму правдоподобиялогарифмической функции правдоподобия, имеемlogP(r/4) = \og{ed^T'v'\\ - s)J-d"(r'v^)=(4.73)= dH(r,Vi) log ;J—-^ + Jlog(l - e).. Результат может быть существенно упрощен. Параметры J и е независят от передаваемого сообщения и, поэтому, не оказывают никакого влияния на решение декодера. Это значит, что второе слагаемоев (4.73) может быть просто опущено. В оставшемся произведении сомножитель log Y§J является константой и имеет отрицательное значение при е < 0,5. Если его отбросить, то декодер должен искатькодовое слово v не с максимальной условной вероятностью p(r/v), aс минимальным расстоянием Хэмминга d#(r, v).Таким образом, правило решения декодера максимального правдоподобия для ДСК можно сформулировать следующим образом:декодер ищет такое кодовое слово v, для которогоdH{r,v) < dH(r,v)V v e коду.(4.74)Если имеется несколько таких кодовых слов, то из них произвольновыбирается любое.Замечание.
Рассматривая в предыдущем примере работу декодераВитерби, мы интуитивно правильно использовали метрику Хэмминга. Теперь мы убедились в том, что декодирование по критериюмаксимального правдоподобия в ДСК сводится к поиску кодовогослова с минимальным расстоянием Хэмминга до принятой последовательности.Пример: Декодирование Витерби сверточяого (3,1,2)-кода припередаче информации но ДСК.Рассмотрим декодирование но максимуму правдоподобия с помопц>ю алгоритма Витерби для ДСК, Данный пример аналогиченпредыдущему за исключением того, что в принятое сообщение внесены ошибки.Процесс декодирования зашумленного кодового слова показан нарис. 4.21.
В принятую последовательность (нижняя часть рис. 4.21)внесены пять ошибок (на рис. они выделены жирным шрифтом).Декодирование происходит аналогично предыдущему примеру. Разница заключается в том, что на третьем шаге декодирования в состоянии Si для продолжения выбирается путь, ведущий на второмГлава 4- Сверточные кодышаге из состояния SQ В SJ И, поэтому, на третьем шаге декодирования не происходит совпадения первого принятого бита для всехсостояний (как это было в предыдущем примере). Таким образом,первый информационный бит не может быть выдан потребителю натретьем шаге. Как видно, в нашем случае наличие шума приводит кзадержке процесса декодирования. Из рис. 4.21 следует, что первыйинформационный бит выдается потребителю только на пятом шаге.Далее, на шестом шаге выдаются сразу три бита, совпадающих длявсех состояний, и, наконец, на седьмом, последнем шаге декодирования к ним добавляются недостающие биты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
