6.2. Алгоритм Фано

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

6.2.1. Цена пути

Будем предполагать, что для каждого пути на кодовом дереве декодер может вычислить вероятность того, что передавалась последовательность при условии, что принята последовательность Здесь последовательности длины

Рассмотрим алгоритм, который, сравнивая эту вероятность с некоторым порогом, принимает решение о том, является ли данная ветвь правильной или неправильной. Вероятность можно представить в следующем виде:

Если предположить, что канал является каналом без памяти, то

Для простоты рассмотрим случай двоичных кодов и, кроме того, предположим, что все пути кодового дерева порождаются с равными вероятностями. В этом случае

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

Если взять логарифм обеих частей равенства (6.6), то получим.

Заметим, что сумма в правой части этого равенства является взаимной информацией между последовательностями и

Фиг. 6.6. Изменение цен путей для алгоритма Фано.

Следовательно, при подходящем выборе скорости передачи среднее значение (6.7) для правильного пути будет положительным, а для неправильного пути — отрицательным. Более того, вдоль правильного пути это среднее значение (6.7) является возрастающей функцией Поэтому в общем случае определим цену пути следующим образом:

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

6.2.2. Поведение декодера

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

I. «Смотри вперед»

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

II. «Смотри назад»

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

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

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

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

Фиг. 6.7 иллюстрирует описанный выше алгоритм. Рассмотрим изменение величины при движении слева направо. Так как вначале величина возрастает, то декодер находится в состоянии и считает пройденный путь правильным. В узле значение несколько уменьшается, но тем не

менее оказывается выше порога и декодер остается в состоянии Однако в узле (2) значение становится меньше текущего значения порога, равного Декодер переходит в состояние но путь до самого левого узла, лежащего выше этого порога [т. е. узла (3)] считает правильным. Вначале декодер возвращается из узла (2) в узел (4) и начинает поиск правильного пути из этого узла, но ни одно ребро, выходящее из узла (4), не лежит выше порога. Декодер возвращается в узел (3) и продолжает поиск из этого узла. Путь, оканчивающийся в узле (5), оказывается лежащим выше порога, и декодер переходит в состояние Однако в узле цена пути вновь оказывается ниже порога, декодер возвращается в состояние но путь до узла (3) по-прежнему считает правильным.

Фиг. 6.7. Пример к описанию алгоритма Фано.

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

На фиг. 6.8 показана логическая блок-схема алгоритма Фано. Смысл операций «переход вперед в просмотренный узел», «возвращение назад в просмотренный узел», «увеличение порога», «понижение порога» должен быть понятен из приведенного выше описания алгоритма. Так как в каждом узле ребра упорядочены в соответствии с приращением вдоль них цены пути, то ясными оказываются и операции «выбор первого

(кликните для просмотра скана)

по порядку ребра» и «выбор следующего по порядку ребра». Наличие вопроса «ребро используется впервые?» связано с необходимостью фиксировать порог в состоянии и предотвратить остановку алгоритма из-за зацикливания. Фано предложил оригинальный способ получения ответа на этот вопрос, который иллюстрируется на фиг 6.9.

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

1) После продвижения вперед цена пути оказывается лежащей между текущим значением порога и величиной например в приведенном выше примере при переходе из узла в узел (5).

2) Декодер возвращается назад к некоторому пути, цена которого лежит между текущим значением порога и величиной Так, в приведенном выше примере при переходе в узел (7) цена пути оказывается лежащей ниже порога декодер возвращается в узел (2) и начинает поиск другого пути. Не найдя пути, исходящего из узла (2), декодер продолжает поиск из узла (4). Если и в этом случае поиск также оказывается безуспешным, декодер начинает поиск из узла Путь из узла (3) в узел (5) уже исследовался раньше, и это легко обнаружить, поскольку цена пути в узле (5) лежит между значениями порога и а не

Путь с узлом (7) не может быть достигнут при значении порога следовательно, он является новым. При переходе в него значение изменяется с 1 на 0.