6.8. Стек-алгоритм

Выше было проведено детальное исследование алгоритма Фано. Этот алгоритм обладает рядом несомненных достоинств, но, как можно было убедиться выше, анализ многих его характеристик очень сложен. Рассматриваемый в этом разделе так называемый стек-алгоритм, найденный независимо Джелинеком [7] и Зигангировым [8], по сравнению с алгоритмом Фано может быть описан гораздо проще, а кроме того, он достаточно прост для понимания. Этот алгоритм не всегда лучше алгоритма Фано (Гейст [15]), но благодаря своей простоте он позволяет глубже понять сущность последовательного декодирования. Для простоты рассмотрим здесь этот алгоритм применительно к двоичным кодам.

Для пояснений будем использовать двоичный древовидный код со скоростью кодовое дерево которого изображено на фиг. 6.17. Пусть двоичный информационный символ, поступающий в момент времени на вход кодера. Пути длины будем обозначать с помощью соответствующих им векторов Через обозначим символы, используемые для передачи по каналу ребра пути Так как

передаваемые символы, соответствующие ребрам показанного на фиг. 6.17 кодового дерева, представляют собой последовательности из трех двоичных символов, то для них удобно использовать восьмеричное представление, например Предположим, что на выходе канала принята последовательность где длина этой последовательности в ребрах кодового дерева. Задача состоит в том, чтобы по этой последовательности восстановить входную последовательность

Фиг. 6.17. Пример древовидного кода со скоростью

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

При декодировании принятой последовательности находятся функции правдоподобия для различных путей

Для этого используются функции правдоподобия ребер, соединяющих узлы

Поскольку в процессе декодирования последовательность не изменяется и символы для каждого определяются кодовым деревом, которое считается заданным, то величины являются функциями только путей. Рассмотрим следующий алгоритм декодирования:

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

2. Если то извлекается из памяти декодера и вычисляются значения Если то из памяти извлекается и вычисляются значения Величина удаляется из памяти декодера, а вновь найденные значения функций правдоподобия помещаются в память декодера. На этом шаг 2 заканчивается. Таким образом, перед следующим шагом в памяти декодера хранятся значения функций правдоподобия трех путей, а именно двух путей длиной 2 и одного пути длиной 1.

3. Значения функций правдоподобия трех путей, хранящиеся в памяти декодера, упорядочиваются в порядке их убывания, после чего находится путь, соответствующий наибольшему из этих значений. Для двух путей, которые получаются из указанного выше пути присоединением следующего ребра, вычисляются значения функции правдоподобия. Значение функции правдоподобия пути, который был только что удлинен, из памяти удаляется, а в память помещаются вновь вычисленные значения функций правдоподобия. Например, предположим, что в памяти декодера хранятся значения . В этом случае из памяти удаляется а помещаются в память значения функций правдоподобия На этом шаг декодирования заканчивается. Перед следующим шагом декодирования в памяти декодера хранятся значения функций правдоподобия четырех путей, среди которых два пути имеют длину 3, один — длину 1, и еще один — длину 2 (возможно, что все четыре пути будут иметь длину 2).

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

получающихся из указанного выше пути присоединением следующего ребра, помещаются в память.

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

Так как содержимое памяти декодера постоянно упорядочивается, то этот алгоритм получил название стек-алгоритма.

Поясним этот алгоритм на примере. Рассмотрим кодовое дерево, узлы которого пронумерованы так, как показано на фиг. 6.18.

Фиг. 6.18. Пример распределения значений функций правдоподобия по различным путям.

Для обозначения путей будем использовать номера узлов, в которых они оканчиваются. Числа, приведенные над каждым ребром, являются значениями функции правдоподобия соответствующего ребра для некоторой принятой последовательности Так, значение функции правдоподобия пути с номером 13 равно . В рассматриваемом примере состояние памяти декодера меняется следующим образом (номера путей в каждой строке упорядочены таким образом, что значение функции правдоподобия пути, номер которого занимает крайнее левое положение, максимально):

Так как путь с номером 13, занимающим крайнее левое положение в последней строке, имеет длину 3, то декодер на шаге 7 декодирование прекращает.

Таким образом, стек-алгоритм действительно значительно проще алгоритма Фано. В работе [7] приведено обобщение этого алгоритма на случай недвоичных кодов. Анализ вероятности ошибки и среднего числа операций при декодировании можно найти в работе [25]. Методы расчета этих характеристик для стек-алгоритма аналогичны методам расчета соответствующих характеристик алгоритма Фано и здесь рассматриваться не будут.