Алгоритм Витерби с мягким решением

Алгоритм МАВ дает минимальную вероятность ошибки символа и обеспечивает оптимальное мягкое решение при посимвольном расчёте апостериорных вероятностей. Для алгоритма МАВ необходимо знать уровень шума на приёмном конце и выполнять вычисления в вероятностной области. Ниже описан асимптотически оптимальный алгоритм с мягким выводом для многоуровневых модуляций, который хранит мягкое значение расстояния для каждого состояния и уточняет его при обработке на каждом шаге декодирования. Этот алгоритм называется алгоритм Витерби с мягким выходом или мягким решением (АВМР) (Soft Output Viterbi Algorithm – SOVA) может быть успешно использован для итерационного декодирования турбо-кодов с ухудшением ЭВК по сравнению с МАВ в области больших шумов до 0,7 дБ.

Рассмотрим ту же систему, которая изображена на рис. 1.

Стандартный алгоритм декодирования Витерби ищет такую информационную последовательность , которая соответствует модулированной последовательности в решетчатой диаграмме так, чтобы вероятность была максимальной. Эта вероятность выражается так

(23)

поскольку существует прямая связь между b и x.

Чтобы упростить вычисления, прологарифмируем функцию . Для Гауссова канала выражается:

(24)

где P(b_t) – априорная вероятность двоичного символа b_t.

Выражение (24) показывает, что максимизация вероятности соответствует минимизации Евклидова расстояния между принятой последовательностью сигналов и переданной в решётке, где P(b_t) – константа равная 0.5 для двоичного симметричного канала.

Мы предписываем к каждой ветви на пути x в решетке Евклидово расстояние, называемое метрикой ветви и обозначенное v_t, следующим образом

(25)

Тогда метрику пути , соответствующую пути x, можно выразить следующим образом

(26)

Обычный декодер Витерби находит на решётке путь с наименьшей метрикой.

Алгоритм Витерби с мягким решением (ABMP) выносит мягкую оценку в виде логарифмической функции вероятности , соответствующей принятой последовательности .

( 27)

где , i=0, 1 – априорная вероятность бита данных b_t.

ABMP декодер выдаёт жёсткое решение, сравнивая значение с нулём.

( 28)

ABMP декодер выбирает путь x с минимальной метрикой пути m_t_{, min} как наиболее вероятный путь таким же образом, как и обычный алгоритм Витерби. Вероятность выбора этого пути пропорциональна

(29)

Обозначим m_t_,c метрику наиболее сильного конкурента пути максимальной вероятности, который соответствует пути с минимальной метрикой, когда символ решётки на пути максимальной вероятности в момент времени t заменён другим символом.

Если жёсткая оценка наиболее вероятного пути в момент времени t равна 1, то оценка самого сильного конкурента в этот момент равна 0. Следовательно

(30)

(31)

А логарифм отношения этих вероятностей равен

(32)

Обозначим через минимальную метрику пути при b_t= 1 и минимальную метрику пути при b_t= 0.

На мягком выходе декодера ABMP образуется оценка

(33)

Если решение принимается на блоках конечной длины, как в блочных кодах, турбо кодах или свёрточных кодах в системах МДВР (TDMA), то предложенный алгоритм может быть использован в двунаправленном рекуррентном методе с прямыми и обратными рекурсиями. Например, следующая простая диаграмма решетки на два состояния, показанная на рис. 4 используется, чтобы пояснять алгоритм. Решетка состоит из W + 1=M_t = 8 узлов, которые обозначены квадратами с номерами от 0 до 7. Решетка начинается от узла 0 и заканчивается узлом 7. Каждая ветвь помечена своей метрикой, которая

Рисунок 4 Пример решетчатой диаграммы кода

вычисляется из принятой последовательности r. Рекурсия вперёд использует хорошо известные операции (сложить, сравнить, выбрать) для поиска:

1. W минимальных метрик путей, обозначенных m_f,i, от узла 0 к остальным i=1, 2, ..., W = 7 узлам.

2. Наиболее вероятного пути с метрикой обозначенной m_min, от узла 0 к узлу W = 7.

Результат прямой рекурсии показан на рис. 5, где узлы обозначены своими минимальными метриками m_f,_t, для t = 1, 2, ..., 7 от узла 0. Соединённые ветви показывают наиболее вероятный путь с метрикой пути равной сумме метрик

Рисунок 5 Результат прямой рекурсии

ветвей m_min = 1. Обратная рекурсия так же использует набор операций сложить, сравнить, выбрать для поиска:

1. W-1 минимальных метрик путей, обозначенных m_b,i, от узла W = 7 к узлам (W–1), (W–2), ..., 1. Эти минимальные метрики, вместе с вычисленными при прямой рекурсии, позволяют вычислить метрики путей наиболее сильных конкурентов m_c так

(34)

2. Значения мягкого выхода в соответствии с выражением (32)

(35)

Например, на рис. 5 жесткая оценка в момент времени t = 1 читается из пути максимальной вероятности, и это - 0. Следовательно, в момент времени t=1 . Вес самого сильного конкурента в момент времени t = 1 соответствует дополнительному символу, который является 1. Таким образом .

Результаты прямой и обратной рекурсий изображёны на рис 6. Первое число в обозначении узла показывает минимальную метрику пути в результате прямой рекурсии, а вторая – метрику пути в результате обратной рекурсии. Например, в момент времени t = 1, жёсткоё решение о переданном символе может быть принято на основании наиболее вероятного пути и это =0. Если мы удалим путь, который соответствует двоичному 0 в момент времени 1, мы получаем путь, который соответствует =1. Этот путь заканчивается в узле 2 в момент времени 1. Для этого пути минимальный вес полученный из уравнения (34) как сумма веса прямого пути m_p.f = 1, показанный первым числом, и весом обратного пути m_p,b = 1, показанный второй цифрой рассчитывается в узле, следующим образом

Рисунок 6 Результат прямой и обратной рекурсии

Значения на мягком выходе в соответствии с выражением (34) вычисляется как

Следует отметить, что мягкое решение может быть сделано после каждого обратного шага рекурсии. Из-за этого, никакое реальное дополнительное ЗУ не требуется для обратной рекурсии. Вычислительная сложность прямой рекурсии эквивалентна обычному алгоритму Витерби. Вычислительная сложность обратной рекурсии - обычно меньше чем в обычном алгоритме Витерби поскольку, поиск ведётся только по части решетки. Следовательно, верхняя оценка вычислительной сложности ограничена значением в двое большим, чем для обычного алгоритма Витерби. При двоичных входными битах b_t вычислительная сложность приблизительно в 1,5 раза больше, чем для обычного алгоритма Витерби.

Таким образом, можно коротко описать АВМР.

1. Прямая рекурсия

a. Установить начальные значения

i. t = 0, S₀ = 0, , , S_t = 0

b. Увеличить время t на 1

i. Рассчитать метрики ветвей для всех ветвей входящих в узлы в момент времени t

ii. Рассчитать метрики путей для всех путей входящих в узлы в момент времени t

iii. Сравнить метрики путей и найти выжившие для каждого узла

iv. Сохранить выжившие пути и их метрики для каждого узла

v. Повторять пункт 2 пока t £ t

c. Путь, выживший до узла S_t – это наиболее вероятный путь, а его метрика – m_t_,min.

2. Обратная рекурсия

a. Установить начальные значения

i. t = t, S_t = 0, , , S₀ = 0

b. Уменьшить время t на 1

i. Рассчитать метрики ветвей для всех ветвей входящих в узлы в момент времени t

ii. Рассчитать метрики путей для всех путей входящих в узлы в момент времени t

iii. Сравнить метрики путей и найти выжившие для каждого узла

iv. Сохранить выжившие пути и их метрики для каждого узла

v. Повторять пункт 2 пока t £ t

3. Мягкое решение

a. Установить t = 0

b. Увеличить время t на 1

i. В момент времени t найти наиболее вероятные оценки c_t = i, где i Î {0, 1}

ii. Определить как

iii. Найти метрику пути наиболее сильного конкурента , c = i Å 1 (сложение по модулю 2).

где , – это метрика прямого выжившего пути для момента времени (t-1) и узла l’, – это метрика ветви во время t для дополнительных символов c при переходах от узла l’ к узлу l, - это метрика обратного выжившего пути в момент времени t и узла l

iv. Вычислить

Рассмотрим конкретный пример для РССК в метрике Евклида (1, 1/3)

Пусть принятая последовательность сигналов представлена в виде:

Рисунок 7 Решетчатая диаграмма РССК (1, 1/3)

Начальное и конечное состояние кодера – 0. Метрики ветвей для этой принятой последовательности изображены на Рисунок 8. Они вычислены, как для обычного алгоритма Витерби. Результат выполнения прямой рекурсии по алгоритму Витерби изображён на Рисунок 9. Метрики выживших путей записаны в каждом из узлов, а наиболее вероятный путь выделен жирным. Итоговая метрика наиболее вероятного пути оказалась равна m_4,min= 0,04.

Рисунок 8 Метрики ветвей для рассматриваемого примера

Рисунок 9 Выбранный путь в результате прямой рекурсии

Рисунок 10. Выбранный путь в результате обратной рекурсии

Результат обратной рекурсии приведен на Рисунок 10. Первое число внутри каждого узла показывает метрику пути в результате прямой рекурсии, а второе число – метрику выжившего пути в результате обратной рекурсии

Во время t=1, наиболее вероятное жёсткое решение c₁=1 и соответственно . Очевидно, что минимальная метрика пути при прямой рекурсии в момент времени t=1 равна 0. Минимальная метрика пути при обратной рекурсии равна 4,04, а метрика ветви – наиболее сильного конкурента для наиболее вероятного перехода равна 8. Таким образом

а логарифм отношения метрик наиболее вероятных путей в момент времени t=1 равен

Наиболее вероятный символ в момент времени 2 – это , а минимальная метрика пути опять же . Лучший альтернативный путь в этот момент времени обозначается и равен

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

Логарифм отношения наиболее вероятных путей в момент времени 2 равен

Подобным образом можно вычислить и остальные логарифмы отношения наиболее вероятных путей:

Вычислительная сложность алгоритма при прямой рекурсии эквивалентна обычному алгоритму Витерби, а вычислительная сложность обратной рекурсии вдвое меньше, поскольку на каждом этапе приходится анализировать вдвое меньшее количество ветвей. Таким образом, для двоичных сигналов АВМР только в полтора раза сложнее обычного алгоритма Витерби, а в предельном случае АВМР может быть максимум в два раза сложнее.