7.2.7. Стек-алгоритмы последовательного декодирования

Другой интересный класс алгоритмов последовательного декодирования составляют так называемые стек-алгоритмы, которые были предложены и исследованы независимо Зигангировым [75] и Джелинеком [76]. Эти алгоритмы не получили широкого признания, поскольку наиболее приемлемым при практической реализации считается алгоритм Фано. Однако стек-алгоритмы представляют интерес, поскольку идейно очень просты и их удобнее всего использовать для получения некоторых аналитических результатов о свойствах последовательных декодеров.

Блок-схема типичного стек-алгоритма показана на рис. 7.22. Алгоритм очень прост. Декодер порождает стек, состоящий из просмотренных ранее путей различных длин, упорядоченных в соответствии со значениями метрики (используется та же метрика, что и в алгоритме Фано). На каждом шаге происходит продолжение пути, находящегося наверху стека, что дает следующих -тей (для кодов с и таким образом путь заменяется на эти путей. Ясно, конечно, что для этих путей вычисляется значение метрики. После этого новый стек переупорядочивается в соответствии со значениями метрики и процедура повторяется заново. Процесс повторяется до тех пор, пока путь, находящийся наверху стека, не дойдет до конца кодовой последовательности.

Рассмотрим для примера код кодовое дерево которого изображено на рис. 7.1. Предположим далее, что передаваемая информационная последовательность имеет вид а принятая (с жесткими решениями) - вид Таким образом, в первом и четвертом ребрах возникли одиночные ошибки. Именно этот пример был рассмотрен ранее при изучении алгоритма Фано, и соответствующие метрики на ребрах для этой принятой последовательности показаны на дереве на рис. 7.13. На шаге 1 происходит продолжение начальной вершины, которое приводит к путям 0 и 1, метрика каждого из которых —4. Примем, что на верх стека помешается верхнее ребро. На шаге 2 верхнее ребро продолжается и дает пути метрика каждого из которых —8. После переупорядочения стека наверху окажется

Рис. 7.22. Стек-алгоритм последовательного декодирования

путь 1 с метрикой —4. На шаге 3 этот путь продолжается, давая пути 10 и 11 с метриками —3 и —13 соответственно. Процесс продолжается дальше, и после шага 5 наверху стека окажется путь 1000. Все дальнейшие продолжения этого пути будут оставаться наверху стека, так что выбранным окажется именно этот путь. Последовательность шагов показана в табл. 7.4.

Таблица 7.4. (см. скан) Декодирование стек-алгоритмом для примера на рис. 7.20

Интересно, что при сравнении этой таблицы с табл. 7.2 для алгоритма Фано видим, что стек-алгоритм требует существенно меньше вычислительных операций. Однако такое сравнение не очень корректно, поскольку одна операция стек-алгоритма существенно сложнее одной операции алгоритма Фано. Особенно неприятной является операция переупорядочения стека.

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

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

Стек-алгоритмы имеют ряд преимуществ. Одно из них состоит в возможности эффективно использовать буфер в периоды, когда он пуст. Когда буфер пуст, согласно алгоритму Фано вычислений

не происходит до тех пор, пока не будет принято следующее ребро, и только тогда могут быть продолжены вычисления. В противоположность этому при стек-алгоритме периоды, когда буфер пуст, могут использоваться для продолжения некоторых из путей, содержащихся в стеке. Таким образом, стек-алгоритм может обеспечивать отсутствие простоев. Другое явное преимущество состоит в меньшем среднем числе операций, причем это преимущество становится ощутимым, когда Проведенные Джелинеком эксперименты показали, что два алгоритма эквивалентны по вычислительным затратам при а при дальнейшем увеличении проявляется преимущество стек-алгоритма, и при он оказывается примерно в 7 раз лучше. К сожалению, каждая из вычислительных операций стек-алгоритма существенно сложнее вычислительной операции алгоритма Фано, и стек-алгоритм предъявляет существенно большие требования к емкости памяти.

Задачи

(см. скан)

(см. скан)