2014-02-09
859
Каждый входной символ порождает на выходе кодера m (у нас ДВА) символа, приписанные соответствующему ребру.
Например, входная последовательность 1011
дает выходную последовательность 11 01 00 10.
Декодирование
Задача декодирования сверточного кода по алгоритму Витерби рассматривается как задача нахождения наиболее правдоподобного пути по решетчатой диаграмме с помощью некоторых правил. Это означает, что последовательность, образованная в результате движения по найденному пути, должна быть ближе всего к принятой последовательности. Другими словами декодер приемника пытается определить, по какому пути на решетчатой диаграмме изменялось состояние кодера в передатчике. Решение принимается в соответствии с принципом максимального правдоподобия.
Рассмотрим, как приемник восстанавливает информационную последовательность. Предположим, информационная последовательность представляет собой U=0 1 0 1 0 1 0 1…..
На выходе сверточного кодера появилась последовательность
V=00 11 01 00 01 00 01 00
На вход приемника поступила последовательность
Y=01 11 01 00 01 00 01 00 (ошибка во втором бите)
При нахождении наиболее правдоподобного пути по решетчатой диаграмме будем использовать понятие метрики пути – расстояние Хемминга (t) между принятой комбинацией и комбинацией, образованной при движении по определенному пути на диаграмме.
|
 ·
| · | t=1 (Путь по диаграмме дает 00) | t-метрика пути | |
| · | t=1 (Путь по диаграмме дает 11) | Уровень 1. Принято: 01 |
Накопленное значение метрики пути
| · | · | · | t=3 (Путь по диаграмме 00 00) | ||||||
| · | · | t=1 (Путь 00 11) | Уровень 2. Принято: 0111 | ||||||
| · | t=2 (Путь 11 01) | ||||||||
| · | t=2 (Путь 11 10) |
Каждый из путей после уровня 2 раздваивается. Общее число путей стало равно 8.
Сравним метрики для пар путей, ведущих в каждую вершину уровня 3. В каждой паре сохраним только один путь – с лучшей (минимальной) метрикой. Оставшиеся пути называются выжившими.
|
 ·
| · | · | · | t=3 | ||||||||
| · | · | · | t=3 | Уровень 3. Принято: 01 1101 | ||||||||
| · | · | t=1 | ||||||||||
| · | · | t=2 |
| · | · | · | · | · | t=3 | |||||||
| · | · | · | · | t=1 | Уровень 4. Принято: 01 11 0100 | |||||||
| · | · | · | t=3 | |||||||||
| · | · | · | t=3 |
| · | · | · | · | · | · | T=4 | |||||||
| · | · | · | · | · | T=4 | Уровень 5. Принято: 01 11 01 00 01 | |||||||
| · | · | · | · | T=1 | |||||||||
| · | · | · | · | T=3 |
И так далее…
1. При условии равных метрик из двух путей выбирается путь с наименьшей накопленной метрикой на предыдущем уровне.
2. Если происходит слияние путей на некотором участке диаграммы, приемник делает однозначный вывод о переданной информационной последовательности на этом участке.
В рассмотренном примере после обработки 5-го уровня решетчатой диаграммы, произошло слияние путей на уровнях 0-3. Приемник делает вывод, что кодер передавал последовательность
00 11 01,
а это соответствует информационной последовательности 0 1 0.
3. Обычно в приемнике устанавливается фиксированная глубина декодирования. Например, 10-й уровень. Если слияние путей не происходит, тогда после обработки 10-гоуровня, приемник выбирает путь с минимальной метрикой и формирует один информационный символ для выдачи получателю, соответствующий первому уровню этого пути. После обработки 11-го уровня делается вывод о следующем информационном символе, который соответствует второму уровню пути с минимальной метрикой и т.д.
