8.2.2. Оптимальное декодирование для свёрточных кодов — алгоритм Витерби

При декодировании блокового кода в канале без памяти, мы вычисляем расстояние  (расстояние Хемминга при декодировании жёстких решений и расстояние Евклида при декодировании мягких решений) между принимаемым кодовыми словами и  возможными к передаче кодовыми словами. Затем мы выбираем кодовое слово, которое наиболее близко по расстоянию к принятому кодовому слову. Это правило решения, которое требует вычисления  метрик, оптимально в том смысле, что оно приводит к минимуму средней вероятности ошибки в двоичном симметричном канале с АБГШ и .

В отличие от блокового кода, который имеет фиксированную длину , свёрточный код порождается устройством с ограниченным числом состояний. Как следствие, оптимальный декодер является максимально правдоподобным последовательным оценивателем (МППО) вида, описанного в разделе 5.1.4 для сигналов с памятью, таких как ДБНП и МНФ. Поэтому оптимальное декодирование свёрточных кодов включает поиск по решётке наиболее правдоподобной последовательности. В зависимости от того, формирует ли детектор, за которым следует декодер, жёсткие или мягкие решения, соответствующие метрики при поиске по решётке могут быть или метриками Хемминга или метриками Евклида, соответственно. Более подробно мы это рассмотрим ниже, используя решётку рис. 8.2.5 для свёрточного кода, показанного на рис. 8.2.2.

Рассмотрим два пути на решётке, которые начинаются в начальном состоянии  и сливаются в состоянии  после трёх переходов (трёх ветвей), которые соответствуют двум информационным последовательностям 000 и 100 и передаваемым последовательностям 000 000 000 и 111 001 011 соответственно. Обозначим переданные биты через , где индекс  указывает на -ю ветвь, а индекс  указывает на -й бит в этой ветви. Соответственно определим  как выход демодулятора. Если детектор формирует жёсткие решения, его выходом для каждого переданного бита является или 0, или 1. С другой стороны, если используется декодирование мягких решений, а кодированная последовательность передаётся двоичной когерентной ФМ, то входные величины для декодера определяются так:

,                     (8.2.9)

где  представляет собственный шум, а  - энергия, сигнала каждого переданного кодового символа (бита).

Для -й ветви и -го пути по решётке метрики определяются как логарифм совместной плотности вероятности последовательности  при условии передачи последовательности  для -го пути.

То есть

                    (8.2.10)

Далее, метрика -го пути решётки, содержащего  ветвей, определяется так:

.                     (8.2.11)

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

                      (8.2.12)

где  — вероятность ошибочного приёма бита. Предположив, что , находим, что метрика  больше, чем метрика . Этот результат согласуется с наблюдением, что путь из одних нулей  имеет расстояние Хемминга  от принимаемой последовательности, в то время как путь с  имеет расстояние Хемминга  от принимаемого пути. Таким образом, расстояние Хемминга является эквивалентной  метрикой для декодирования с жёстким решением.

Аналогично предположим, что используется декодирование мягких решений, а канал прибавляет к сигналу АБГШ. Тогда выход демодулятора описывается статистически через условную ФПВ

,                     (8.2.13)

где  - дисперсия аддитивного гауссовского шума. Если мы пренебрегаем слагаемыми, общими для всех метрик ветвей, метрику -й ветви -го пути можно выразить так:

,                     (8.2.14)

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

                    (8.2.15)

Имея метрики ветвей и метрики путей, рассчитанные декодером, мы теперь рассмотрим использование алгоритма Витсрби для оптимального декодирования информационной последовательности при свёрточном кодировании. Мы рассмотрим два пути, описанные выше, которые сливаются в состоянии  после трёх переходов. Заметим, что какой-либо частный путь по решётке, который ответвляется от этого узла, будет суммировать идентичные слагаемые в метриках путей  и . Как следствие, если , у сливающегося узла  после трёх переходов,  будет продолжать быть больше  для любого пути, который ответвляется от узла . Это значит, что путь, соответствующий , можно исключить из дальнейшего решения. Путь, соответствующий метрике , является выжившим. Аналогично, один из двух путей, которые сливаются в состоянии , может быть исключен на основе двух соответствующих метрик. Эта процедура повторяется в состоянии  и состоянии . Как результат, после трёх первых переходов имеются четыре выживших пути, один кончающийся на каждом состоянии, и соответствующие метрики для каждого выжившего пути. Эта процедура повторяется на каждом шаге решетки по мере того, как принимаются новые сигналы в последующих временных интервалах.

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

Задержка при декодировании при декодировании длинных информационных последовательностей, которые были кодированы свёрточным кодом, обычно слишком велика для большинства практических применений. Более того, память, требуемая для хранения всей длины выживших последовательностей, велика и дорогая. Как указано в разделе 5.1.4, решение этой проблемы заключается в модификации алгоритма Витерби таким образом, чтобы установить фиксированную задержку декодирования без существенной потери качества оптимальности алгоритма. Напомним, что модификация сводится к тому, чтобы удержать в заданное время  только самые последние  декодированных информационных бит (символов) в каждой выжившей последовательности. По мере приёма новых информационных битов (символов) оптимальное решение принимается относительно бита (символа), принятого на  ветвей раньше по решётке, путём сравнения метрик выживших последовательностей и принятия решение о бите в последовательности, имеющей наибольшую метрику. Если  выбран достаточно большим, все выжившие пути будут содержать одинаковый декодируемый бит (символ), принятый на  ветвей раньше. Это значит, что с большой вероятностью, все выжившие последовательности к моменту  выходят из одного и того же узла в момент времени . Экспериментально показано (компьютерное моделирование), что задержка  обеспечивает пренебрежимо малое ухудшение качества относительно оптимального алгоритма Витерби.