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

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

ОГЛАВЛЕНИЕ

Следующая >>

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, для которого

V v e коду. (4.74)
dH{r,v) < dH(r,v)

Если имеется несколько таких кодовых слов, то из них произвольно
выбирается любое.

Замечание. Рассматривая в предыдущем примере работу декодера
Витерби, мы интуитивно правильно использовали метрику Хэм-
минга. Теперь мы убедились в том, что декодирование по критерию
максимального правдоподобия в ДСК сводится к поиску кодового
слова с минимальным расстоянием Хэмминга до принятой после-
довательности.

Пример: Декодирование Витерби сверточяого (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. Канал с АБГШ также яв-
ляется каналом без памяти, поэтому, для декодера максимального
правдоподобия приращение метрики можно определить как

exp (_
= logPirj/vj) = log (4.76)
,254 Глава 4- Сверточные коды

где +го при Vj = 0 и —го при Vj = О. Выражение (4.76) можно
упростить


log e - - log 27ГС72.
log P{rj/vj) = - (4.77)
^'

Так как для декодера МП все константы несущественны, их мож-
но отбросить, поэтому, без потери общности, в качестве приращения
метрики можно использовать расстояние Евклида между нродетек-
тированным сигналом г и значениями ±го

М (rj/vj) = — (г ± го) 2 . (4-78)

Можно произвести дальнейшие упрощения. Из

(г ± го) = г2 ± 2гг0 + г20 (4.79)

следует, что для декодера МП приращение метрики можно свести к

Vj =
?• (4-80)
'
ДЛЯ Vj = 1

Таким образом, при вычислении приращений метрик нужно толь-
ко учитывать знак переменной г.
Заметим, что метрика декодера является непрерывной величи-
ной. В этом случае говорят о мягком решении декодера, в отличии от
жесткого решения, при котором продетектированный сигнал кванту-
ется на два уровня «0» и «1». Ниже приводится пример практиче-
ской реализации декодера Витерби с мягким решением, при этом, в
частности, учитывается сложность реализации. Во многих практи-
ческих применениях, например, в мобильной связи, предъявляются
повышенные требования к стоимости декодера. Очень часто деко-
дер представляет собой интегральную схему, размещенную в одном
чипе. Важную роль играют так же надежность в эксплуатации и ми-
нимальная мощность принимаемого сигнала. В связи с указанными
требованиями, разработчики декодеров стремяться минимизировать
их сложность с минимальными потерями эффективности, при этом,
особую роль играют целочисленное представление метрики и про-
стота арифметических операций декодирования.
Упрощенные декодеры позволяют реализовать субоптимальные
решения. Во многих применениях достигнут разумных компромисс
между сложностью декодера Витерби с мягким решением и мини-
мальной мощностью принимаемого сигнала.
4j
4-6. Декодирования по максимуму правдоподобия 255^

Пример: Декодер Витерби с мягким решением для канала с
АБГШ.


/(г/0)




-го О

Рис. 4.23. Квантование принятого сигнала.

Пусть информация источника с равномерным распределением
символов «О» и «1» передается по каналу с АБГШ. В этом случае
на выходе согласованных фильтров приемника мы получаем ироде-
тектированный сигнал г с нормальным распределением плотностей
условных вероятностей /(г/0) и /(г/1) (рис. 4.23). Вместо жестко-
го решения, при котором условные вероятности квантуются на два
уровня, рассмотрим реализацию декодером простейшего мягкого ре-
шения. При таком решении на вход декодера поступают символы ко-
дового слова «О» и «1», имеющие длину, равную двум битам. Такая
информация соответствует 4 уровням квантования текущих значе-
ний переменной г (см. рис. 4.23). Дополнительный двоичный разряд
входных символов позволяет различать «хорошие» и «плохие» би-
ты. Смысл такой градации состоит в том, что если переменная г
имеет положительное значение, очень близкое к нулю, то вероят-
ность «1» лишь немного превышает вероятность «О». В этом случае
имеет смысл говорить о «ненадежной» или «плохой» единице. Если
значение г превышает г0, то с большой долей уверенности можно
утверждать, что была принята единица.
Замечание. Интервалы квантования переменной г были выбраны
интуитивно, для того, чтобы продемонстрировать реализацию де-
кодера Витерби с мягким решением.
При мягком решении с минимальными техническими затрата-
ми для подсчета приращений метрик будем пользоваться таблицей,
4.7. В этом случае текущее значение метрики рассматриваемого пути
^256 Глава 4- Свершенные коды

Таблица 4.7. Таблица приращений метрик.

Принятый символ Приращение метрики Коментарий
0 1
00 —Од «хороший» ноль
3 0
1
2 «плохой» ноль
01 — ОЬ
1 2 «плохая» единица
10— 1Ь
11 — 1д «хорошая» единица
0 3




будет складываться с некоторым целым числом из интервала ]0,3[.
Выбор этого числа зависит от уровня квантования, в который по-
падает продетектированный сигнал г и текущего значения кодового
символа анализируемого участка пути.

2
6
3
К/

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

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

ОГЛАВЛЕНИЕ

Следующая >>