Первые т + 1 кадров кодового слова с имеют вид

Мы хотим найти сегмент кодового слова, для которого log [Рг (с*") I v<>) ] максимален. По определению последовательного декодера выбор начального сегмента кодового слова длины т + 1 должен производиться без учета последующей структуры кодового дерева. Но по правилу Бейеса

Рг (у() I с")) Рг (сС"))

Рг (с*") I у<л)) =

Рг (у())

По предположению кодовые слова используются с одинаковой вероятностью; поэтому

Рг (с*-»)) = •

(m+I) fro

(m+I) •

Множитель Рг (v"> с<")) можно переписать в виде

, га п- N п„

Pr(v>)c"">) = nnpr(j0 П ПРгН)-

Правая часть распадается на две части: произведение условных вероятностей по m + 1 кадрам кодового слова и произведение безусловных вероятностей по тем кадрам, в которых кодовое слово еще не определено. Разбиение вероятности на две части, которое мы провели, приводит естественным образом к вероятностному описанию последовательного декодирования. Задача сводится к нахождению пути, для которого величина

т п„

Рг (у<> I сО")) Рг (ct")) в в

Рг (v<))

т п„

ППрКО

1=0 /=1

-(m+l) п„«

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

Рг (у() I с<">) Рг (сС")) Рг (v*™))

fx (с<")) = log

1=0 L /=1

log,

Рг (./)

В квадратную скобку заключен вклад в метрику Фано, вносимый i-u кадром. В каждом кадре каждого кодового слова необходимо

вычислять лишь этот член. Метрика пути р, (с")) получается прибавлением соответствующего приращения к метрике Фано кодового слова, находившегося на вершине стека на предыдущей итерации.

Последовательное декодирование для жесткого решения, основанное на алгоритме Фано, уже обсуждалось в § 12.9; аналогичное обсуждение может быть проведено и для каналов с мягким решением. Единственно реальная разница между декодером для каналов с жестким решением и каналов с мягким решением состоит в используемой метрике пути. Соответствующая мягкому решению метрика пути - это метрика Фано. Единственное, что необходимо изменить в алгоритме Фано, описанном в § 12.9, - это ввести новую метрику. После такого изменения декодер Фано, описанный в § 12.9, станет пригодным и для каналов с мягким решением.

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

Число вычислений, производимых любым последовательным декодером для продвижения на один узел в глубь кодового дерева, является случайной величиной. Это обстоятельство в основном и влияет на сложность, требуемую для достижения заданного качественного уровня. Когда шум слаб, декодер обычно продвигается по правильному пути, используя лишь одно вычисление для продвижения в глубь кодового дерева на одно ребро. Однако когда шум становится сильным, декодер может проследовать вдоль неправильного пути, и прежде чем декодер найдет правильный путь, ему, возможно, потребуется произвести большое число вычислений. Непостоянство числа вычислений означает, что буферу входных данных может потребоваться большая память. Использование любого конечного буфера при последовательном декодировании приводит к ненулевой вероятности переполнения; это обстоятельство должно приниматься во внимание при вычислениях характеристик декодера.

ЗАДАЧИ

15.1. Привести простое выражение для метрики Фано в случаях д-ичного симметричного канала и гауссовского канала.

15.2. Построить блок-схему ОМР-алгоритма для недвоичных кодов.

Q(x) =

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

15.4. Разобрать случай декодирования, представленный на рис. 12.25, используя стек-алгоритм.

ЗАМЕЧАНИЯ

Возможность использования декодирования с мягким решением для улучшения качества декодиррвания стала ясной почти с того момента, когда бьши построены первые коды, однако хорошие декодеры для них тогда не были найдены. По существу первая попытка построить алгоритмический декодер мягкого решения для блоковых кодов была сделана Форни [1966], который ввел понятие обобщенного минимального расстояния. Несколько отличающийся алгоритм был предложен Чейзом [1972], который дополнил внешней петлей декодер двоичных кодов с жестким решением, исправляющий только ошибки. В работе Хартмана и Рудолфа [1976] предложен декодер мягкого решения совершенно иного типа. *

Для сверточных кодов декодеры с мягким решением были введены легче и получили более широкое практическое распространение, чем для блоковых. Это произошло из-за того, что декодеры минимального расстояния, используемые для сверточных кодов, менее сложны, чем алгебраические декодеры, используемые для блоковых кодов, таких, как коды БЧХ. Хэ.ммингово расстояние может быть заменено другими мерами разделения кодовых слов при весь.ма малом изменении структуры вычислений.

Унгербёк [1977, 1982] построил специально предназначенные для приемника мягкого решения коды, комбинируя выбор модуляции и выбор кода. Использование решетки для модуляции исследовали также Андерсон и Тейлор [1978], но вне связи с кодированием.

Последовательное декодирование было предложено Возенкрафтом [1957] и описано Возенкрафтом и Рейффеном [1961]. Оно было развито далее в работах Фано [1963], Зигангирова [1966] и Джелинека [1969]. Прогрессу в данной области способствовали также обзорные работы Джелинека [1968] и Форни [1974] и последующие разработки Шевийя и Костелло [1978] и Хаккоуна и Фергюсона [1975].

Нижние границы распределения числа вычислений последовательного декодирования получили Джекобе и Берлекэмп [1967], рассмотревшие также иллюстративный пример. Соответствующая верхняя граница была найдена Севиджем [1966].

15.3. Для сверточного кода с порождающей матрицей