Оптимальное декодирование СК–алгоритм Витерби

    При декодировании блокового кода в сигнале БВН без памяти

вычисляется между принимаемыми кодовыми словами и 2 ^k возможными к передаче кодовыми словами:

- расстояние Хемминга при декодировании жёстких решений;

- расстояние Евклида при декодировании «мягких» решений, учитывающих уровень решений на выходе детектора.

При этом по алгоритму МП декодером в качестве решения выбирается кодовое слово, которое наиболее близко по расстоянию к принятому слову. Это правило требует вычисления 2 ^k метрик оптимально в смысле минимума средней вероятности ошибки в симметричном канале без памяти с АБГШ и р_ош<1/2.

    В отличие от блокового кода фиксированной длины n, СК порождается устройством с ограниченным числом состояний и имеет память. Следовательно, оптимальный декодер СК является МП последовательным оценивателем (МППО) для сигналов с памятью, таких как ДБВНП (Двухполярный без возвращения к нулю с памятью).

Аналогично, в зависимости от того формирует ли детектор, за которым следует декодер СК, жёсткие или мягкие решения, соответствующие метрики при поиске по решётке могут быть или метриками Хемминга или Евклида соответственно. Рассмотрим нахождение этих метрик на примере кодера рис. 3.13.

    Метрики СК. Рассмотрим два пути (i =1,2) по решётке рис.3/20, которые начинаются в начальном состоянии «а» и сливаются в состоянии «а» после трёх тактов-переходов (трёх ветвей).

 

Рис. 3.20. Решетчатая диаграмма для СК со скоростью 1/3 (К=3, k=1, n=3).

 

Эти пути соответствуют двум информационным последовательностям 000 и 100, передаваемым последовательностями СК «000 000 000» и «111 001 011» соответственно.

Обозначим переданные биты СК через { C_jm, j =1,2,3; m =1,2,3} где j указывает на j – ветвь, а индекс m указывает на m -й бит в этой ветви. Соответственно обозначим выход демодулятора { r_jm, j =1,2,3; m =1,2,3}.

    Отметим, что выходом детектора жёстких решений является «0» или «1».

С другой стороны, выход детектора мягких решений является входной величиной для декодера СК и определяется для каждого символа при когерентном приеме двоичной ФМ согласно (1.4) в виде:

 

,                            (3.57)

где Ec – энергия сигнала переданного кодового символа (бита);

  n_jm –АБГШ (статистика шумов на выходе когерентного демодулятора ОФМ не изменяется).

    В этом случае для j – й ветви и i – го пути по решётке можно определить метрики как логарифм совместной плотности вероятности последовательности { r_jm, m =1,2,3} при условии передачи последовательности { C_jm ^{( i )}, m =1,2,3} для i -того пути, т.е.

 

μ _j ⁽ⁱ⁾ =log P(r_j/C_j)⁽ⁱ⁾,     j=1,2,3                             (3.58)

 

Тогда, метрика i -го пути решётки, содержащего В ветвей, равна:

PM ^{( i )} =.                                             (3.59)

    Правило МП для решения между двумя путями по решётке сводится к выбору того пути, у которого больше метрика (вероятность).

    Рассмотрим вычисление метрик для жестких и мягких решений детектора.

Пример 1. Найтирешение декодера МП при выборе пути, если детектором формируются жёсткие решения принимаемой последовательности {101 000 100}. Пусть i =0 означает путь с тремя ветвями из одних нулей, а i =1 означает второй путь с тремя ветвями (рис.3.20), который начинается в начальном, состоянии «a» и сливается с путём из одних нулей в состоянии «a» после трёх переходов.

Решение.

Найдем метрики вероятности для этих двух путей:

 PM⁽⁰⁾= 6 log(1-p)+3 log p;

 

PM⁽¹⁾= 4 log(1-p)+5 log p,                                (3.60)

                          

где р - вероятность ошибочного приёма бита.

    При р<1/2 метрика PM⁽⁰⁾ больше, чем метрика PM⁽¹⁾ и путь i =0 более правдоподобен. Этот результат согласуется с наблюдением. Путь из одних нулей (i =0), имеет расстояние Хемминга d=3 от принимаемой последовательности, а путь с i=1 имеет расстояние Хемминга d=5. Таким образом, расстояние Хемминга является эквивалентной метрикой при декодировании жёстких решений по алгоритму МП.

 

Пример 2. Найти метрики путей i =0 и i=1 декодера СК (рис.3.20) при мягких решениях детектора сигналов когерентного приема ОФМ в канале с АБГШ.

Решение.

Выход когерентного демодулятора ОФМ описывается статистикой

условной ФПВ:

,     (3.61)

где σ² - дисперсия АБГШ.

Если пренебречь слагаемыми, общими для всех метрик ветвей, метрику j -й ветви i -того пути можно выразить (по аналогии с (2.24) в [2]) в виде корреляционной метрики (3.58):

.                                      (3.62)

В нашем примере СК n = m =3.

Таким образом, корреляционные метрики декодирования мягких решений для путей i =0 и i=1 при оговоренных условиях равны:

              (3.63)

 

Алгоритм Витерби для оптимального декодирования информационных последовательностей при СК.

Рассмотрим два пути, описанные выше (рис.3.20), которые сливаются в состоянии «a»  после трёх тактов-переходов. Заметим, что какой-либо частный путь по решетке, который ответвляется от этого узла, будет суммировать идентичные слагаемые в метриках путей CM⁽⁰⁾ и CM⁽¹⁾.

Если CM⁽⁰⁾ > CM⁽¹⁾, то у сливающего узла «a» после трёх переходовCM⁽⁰⁾ будет продолжать быть больше, чем CM⁽¹⁾ для любого пути, который ответвляется от узла «a». Это значит, что путь, соответствующий метрике CM⁽⁰⁾, является выжившим, а другой может быть исключен.

Аналогично, один из двух путей, которые сливаются в состоянии «b», может быть исключён на основе двух соответствующих метрик для узла «b». Эта процедура повторяется в состоянии «с» и «d».

В результате, после трёх первых тактов-переходов имеются четыре выживших пути (один, кончающийся на каждом состоянии), и соответствующие метрики для каждого выжившего пути. Эта процедура повторяется на каждом шаге решётки по мере того, как принимаются новые сигналы в последующие интервалы времени.

    В общем случае, когда декодируется посредством алгоритма Витерби двоичный СК с k =1 и кодовым ограничением К, то имеются 2^К-1 состояний. Следовательно, имеются 2^К-1 выживших путей на каждом шаге и 2^К-1  метрик (по одной для каждого выжившего пути).

Аналогично при k >1 число состояний, выживших путей, метрик и вычислений, выполняемых на каждом шаге, возрастает экспоненциально 2^{k( K -1)} с ростом k и K, что ограничивает использование алгоритма Витерби только для относительно малых значений K и k.

    Кроме того задержка при декодировании длинных информационных последовательностей, которые были кодированы СК, обычно слишком велика. Более того, память, требуемая для хранения всей длины выживших последовательностей, велика. Решение этой проблемы заключается в модификации алгоритма Витерби.

Модификация алгоритма состоит в том, чтобы сохранить в заданное время t только самые последние δ декодированных информационных бит (символов) в каждой выжившей последовательности. По мере приёма новых информационных битов (символов) решение принимается относительно бита (символа), принятого на δ раньше по решётке, путём сравнения метрик выживших последовательностей и принятия решения о бите в последовательности, имеющей большую метрику.

Если δ выбран достаточно большим, все выжившие пути будут содержать одинаковый декодируемый бит (символ), принятый на δ символов раньше. Это значит, что к моменту t с большой вероятностью все выжившие последовательности выходят из одного и того же узла, соответствующего моменту времени t - δ. Компьютерное моделирование показывает, что задержка δ ≥ 5K обеспечивает пренебрежимо малое ухудшение качества модифицированного алгоритма относительно оптимального алгоритма Витерби.