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

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

Представим себе решетку сверточного кода с большой длиной кодового ограничения, скажем равной 40. Для того чтобы найти решение, эту решетку нужно исследовать на нескольких сотнях уровней. Еще больше будет число узлов на каждом уровне. Всего таких узлов будет 2*", или приблизительно 1№. Декодер должен найти по этой решетке путь, наиболее близкий к принятому слову в смысле расстояния Хэмминга - по крайней мере он должен сделать это с очень высокой вероятностью, хотя время от времени ему дозволено отказываться от декодирования. Такой отказ является дополнительным видом ошибки, не существовавшим в декодере Витерби; декодер может отказаться от декодирования даже в том случае, когда декодирование по минимуму расстояния было бы верным.

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

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

В этом выражении знак выбран так, чтобы правильной работе декодера cpoTBeTCTBOBajio положительное значение расстояния,

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

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

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

ЦГ) = pnol-d{l),

где d (1) - расстояние Хэмминга между принятым словом и текущим путем по решетке. Для правильного пути d (1) приблизительно равно pnj, а t{l) положительно и возрастает. До тех пор пока t(l) возрастает, декодер продолжает следовать по пути на решетке. Если вдруг t{[) станет уменьшаться, то декодер заключает, что в некотором узле он выбрал ошибочное ребро, и возвращается по решетке, проверяя другие пути. Он может найти лучший путь и проследовать по нему или может возвратиться к тому же самому узлу, но уже более уверенно и продолжить путь через него. Для того чтобы решить, когда t{l) начинает уменьшаться, декодер пользуется текущим порогом Т, который всегда кратен приращению Д порога. Пока декодер движется вперед, порог, оставаясь меньшим t(l) и кратным приращению А, принимает максимально возможное при этих ограничениях значение. Благодаря тому что Т квантуется, допускается небольшое убывание t(f) без пересечения порога.

В алгоритме Фано требуется, чтобы q° ребер, выходящих из каждого узла, были перенумерованы согласно некоторому правилу упорядочения. Это правило ставит в соответствие каждому ребру индекс /, / = О, .... 9*» - 1. Нет необходимости запомнить эти индексы в каждом ребре, достаточно знать правило.

ПО которому при возвращении декодера в узел по ребру с известным индексом / он мог переупорядочить ребра, найти ребро / и, зная его, найти ребро /+ 1. Наиболее общим правилом является правило минимума расстояния. Ребра упорядочиваются в соответствии с их расстояниями Хэмминга до соответствующего кадра принятого слова, а неопределенность разрешается по любому удобному подправилу. Алгоритм Фано будет нормально функционировать и в том случае, когда ребрам приписан любой фиксированный порядок; например, ребра могут быть упорядочены лексикографически в соответствии с их информационными символами. Это последнее правило упорядочения приводит к более длительному поиску назад - вперед, но освобождает от необходимости вычисления и перевычисления порядка при достижении каждого узла. Какое правило упорядочения более просто в реализации, зависит от конструкции декодера. Для.простоты понимания структуры алгоритма правило упорядочения лучше оставить несколько неопределенным; предположим лишь, что в каждом узле ребро, ближайшее к принятому ребру по расстоянию Хэмминга, считается первым. Декодер будет искать ребра из каждого узла в соответствии с этим правилом.

Реализация декодера в виде регистра сдвига, основанная на алгоритме Фано, приведена на рис. 12.26. Основой декодера является копия кодера с несколькими вспомогательными запоминающими регистрами. Декодер пытается подать символы в копию кодера таким образом, чтобы на его выходе появилось кодовое слово, достаточно близкое к принятому слову. После каждой итерации он может обратиться к последнему кадру, поданному в копию кодера. Он может изменить информацию в этом кадре, вернуться к более раннему кадру или ввести новый кадр. Декодер решает, что делать, основываясь на сравнении величины перекошенного расстояния t{l) и текущего значения порога Т.

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

Если шум в канале мал и ошибки редки, то декодер будет циркулировать по правой петле рис. 12.27, каждый раз сдвигая все регистры рис. 12.26 на один кадр вправо. До тех пор пока t(I) остается выше порога, декодер продолжает сдвигаться вправо и повышать порог так, чтобы тот оставался близким к t{l). Если t{l) опускается ниже порога, то декодер проверяет альтернативные ребра этого кадра, пытаясь найти то ребро, которое находится выше порога. Если он не может сделать этого, то возвращается назад.

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