Вернер М. Основы кодирования (2004) (1151882), страница 35
Текст из файла (страница 35)
Для источников и каналов без памяти ( например, для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 следует, что первыйинформационный бит выдается потребителю только на пятом шаге.Далее, на шестом шаге выдаются сразу три бита, совпадающих длявсех состояний, и, наконец, на седьмом, последнем шаге декодирования к ним добавляются недостающие биты. Заметим, что несмотряна наличие 5 ошибочных бит в кодовом слове, все ошибки исправляются (слово нродекодировано правильно).состояниеПринятоеслово6ТактР и с . 4.21.
Декодирование по максимуму правдоподобия с-помощью алгоритма Витерби.Заметим также, что при правильном декодировании, метриканайденного пути показывает число ошибок в принятом слове. Этаинформация может быть использована для оценки надежности, продекодированного сообщения. Наконец, число исправленных ошибок может служить индикатором качества канала.
Так, например,метрика продекодированного слова позволяет своевременно обнаружить резкое ухудшение качества канала и принять соответствующиеконтрмеры.Пример: Метрика декодера при передаче информации но каналус аддитивным белым гауссовским шумом (АБГШ).4-6. Декодирования по максимуму правдоподобия 2 5 3 ,При передаче информации противоположными сигналами по каналу с АБГШ и приеме с помощью согласованных фильтров используется модель канала связи, представленная на рис. 4.22 (см. ЧастьI, раздел 7.5.2). Согласно рис. 4.22, отдельный бит кодового слова«1» или «О» после передачи но каналу без шума и детектированияпринимает аналоговое значение го или — TQ.
Из-за наличия шума вканале продетектированный сигнал г на выходе приемника являетсянепрерывной стохастической переменной с условными плотностямираспределения вероятностей, равными /(г/1) /(г/0)/(г/0)/(г/1)Р и с . 4.22. Условные плотности распределения вероятностей продетектированного сигнала г при передаче противоположными сигналами по каналу сАБГШ."(4.75)/27ГО2Замечание. Значения Г(, и <т2 зависят от канала передачи информации. Приведенные в примере рассуждения можно обобщить и наслучай М-ичных сигналов и использовать там аналогичную метрику.Будем предполагать, что «1» и «О» передаются независимо другот друга с вероятностями, равными 1/2.
Канал с АБГШ также является каналом без памяти, поэтому, для декодера максимальногоправдоподобия приращение метрики можно определить как= logPirj/vj)= logexp (_(4.76),254Глава 4- Сверточные кодыгде +го при Vj = 0 и —го при Vj = О. Выражение (4.76) можноупроститьlog P{rj/vj) = -(Г^ 'log e - - log 27ГС72.(4.77)Так как для декодера МП все константы несущественны, их можно отбросить, поэтому, без потери общности, в качестве приращенияметрики можно использовать расстояние Евклида между нродетектированным сигналом г и значениями ±гоМ (rj/vj) = — (г ± го) 2 .(4-78)Можно произвести дальнейшие упрощения. Из(г ± го) = г2 ± 2гг0 + г20(4.79)следует, что для декодера МП приращение метрики можно свести кVj ='+ГДЛЯ? •(4-80)Vj = 1Таким образом, при вычислении приращений метрик нужно только учитывать знак переменной г.Заметим, что метрика декодера является непрерывной величиной. В этом случае говорят о мягком решении декодера, в отличии отжесткого решения, при котором продетектированный сигнал квантуется на два уровня «0» и «1».
Ниже приводится пример практической реализации декодера Витерби с мягким решением, при этом, вчастности, учитывается сложность реализации. Во многих практических применениях, например, в мобильной связи, предъявляютсяповышенные требования к стоимости декодера. Очень часто декодер представляет собой интегральную схему, размещенную в одномчипе. Важную роль играют так же надежность в эксплуатации и минимальная мощность принимаемого сигнала. В связи с указаннымитребованиями, разработчики декодеров стремяться минимизироватьих сложность с минимальными потерями эффективности, при этом,особую роль играют целочисленное представление метрики и простота арифметических операций декодирования.Упрощенные декодеры позволяют реализовать субоптимальныерешения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
