АЛГОРИТМ ФАНО

При изучении алгоритма Фано ограничимся, как и ранее, случаем Обобщение алгоритма на случай более общих каналов проведено в приложении Описание алгоритма упростится, если вместо расстояния Хемминга определяемого соотношением (6; 108), ввести понятие «перекошенного» расстояния

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

Прежде чем подробно рассмотреть алгоритм декодирования, полезно ввести дополнительные определения. Соотношения (6.108) и (6.109) определяют перекошенное расстояние между принятым вектором и каждым из путей в кодовом дереве из I ребер, Каждому узлу дерева, расположенному на глубине I, припишем -значение, равное значению на пути, ведущем к этому узлу; узлу в начале дерева припишем -значение, равное нулю. Совокупность -значений задает отображение кодового дерева в дерево расстояний принятого сигнала, как показано на фиг. 6.436: узлы связаны так же, как и в кодовом дереве, но ордината каждого узла выбирается равной его -значению.

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

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

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

Фиг. 6.44. Основная логическая схема алгоритма Фано. В приложении рассмотрены более общие сверточные коды, у которых из кашдого узла кодового дерева исходит и ребер, (см. фиг. 6А.1). Приведенная выше логическая схема сформулирована таким образом, чтобы она была применима и к этим более общим кодам; в этом случае соответствующая полная совокупность узлов в дереве расстояний принятого сигнала предполагается упорядоченной в направлении от лучшего к худшему узлу в порядке возрастания их -значений. Два или большее число узлов с одинаковыми -значениями можно упорядочить относительно друг друга любым фиксированным способом.

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

Работу декодера лучше всего объяснить на примере. Рассмотрим фиг. 6.45. Декодер начинает поиск по дереву в начальном узле, обозначенном индексом 0. Начальное значение текущего порога равно нулю. Согласно схеме, представленной на фиг. 6.44, декодер обследует путь вперед, в узел, обозначенный индексом 1. Так как величина соответствующая этому узлу, не превышает указатель исследуемого узла передвигается вперед в узел 1. При этом декодер принимает предварительное решение это решение равно 0, если узел, отмеченпый индексом 1, соответствует и равно 1, если этот узел соответствует

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

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

указатель в узел 2, тем самым принимая предварительное решение . С узле 2 декодер может установить более жесткий текущий порог и положить Такая процедура — обследование, движение указателя и установление более жесткого порога продолжается до тех пор, пока декодер, исследуя путь вперед от узла 4 к узлу 5, не обнаружит превышения текущего порога Декодер реагирует на это повторным обследованием узла 3. Так как текущий порог не превосходится узлом 3, указатель движется назад. Этот шаг представляет собой стирание предварительного решения При передвижении на шаг вперед к узлу 6 для выбирается противоположное значение. В остальном схема на фиг. 6.45 понятна без дополнительных пояснений. Исследуемый путь в любой момент времени задается совокупностью предварительных решений которая определяет положение указателя исследуемого узла.

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

Фиг. 6.46. (см. скан) Уеонершенствованная логическая схема алгоритма Фано.

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

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

2) если указатель исследуемого узла достигает узла, до которого он никогда ранее не доходил. Другие свойства алгоритма рассмотрены в приложении Анализ, проведенный там, позволяет разумным образом выбрать параметры

При эффективном практическом построении алгоритма основную логическую схему, изображенную на фиг. 6.44, необходимо, конечно, тщательно разработать. Блок с надписью «В первый ли раз находится указатель в данном узле?» можно, конечно, реализовать, снабдив его достаточно большой памятью. Но число узлов, исследованных декодером, вообще говоря, чрезвычайно велико, и такая память будет стоить баснословно дорого. Остроумный выход, предложенный Фано, состоит в использовании единственной двоичной переменной, которую мы обозначим через 6 для определения того, когда необходимо устанавливать более жесткий порог. Усовершенствованная логическая схема, использующая эту дополнительную переменную и связанные с ней логические операции, представлена на фиг. 6.46. Переменная В, первоначально равная 0, принимает значение 1 сразу же после того,

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

Новый узел может встретиться лишь при движении вперед, и его легко распознать. Во-первых, узел считается новым, если он превышает порог , лежащий непосредственно под текущим порогом Т: например, если декодер достиг узла 11 (фиг. 6.45), то он превысил предшествующее значение порога Во-вторых, узел, удовлетворяющий порогу считается новым, если он достигнут при движении вперед из узла, который превышал например, узел. 10 на фиг. 6.45 удовлетворяет и достигнут при движении из узла 7, который превышает данную величину текущего порога. (Текущий порог был увеличен с до перед обратным движением от узла 8 к узлу 7.) Указатель исследуемого узла может быть установлен в новый узел только в одном из этих двух случаев, иначе узел был бы достигнут при значении текущего порога следовательно, был бы исследован преждевременно. Алгоритм, изображенный на фиг. 6.46, обнаруживает обе возможности и реагирует на них выбором

Логическую схему, представленную на фиг. 6.46, так же как и схему, изображенную на фиг. 6.44, легче всего понять на примере. Для процесса поиска, представленного на фиг. 6.47, пояснения не нужны.

Блок-схема декодера Фано представлена на фиг. 6.48. Принятые символы поступают параллельно в -регистр декодера по одному ребру символов) в каждый момент. На практике ребра вводятся через одинаковые интервалы времени. Как только поступает новое ребро, символы, находящиеся в -регистре, сдвигаются вправо. Всякий раз, когда приходит новое ребро, самое старое из хранящихся в регистре ребер удаляется из регистра и сбрасывается.

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

В процессе генерирования аналогом сверточного кодера вектора гипотетические двоичные символы сообщения записываются в -регистре. Таким образом, разряды -регистра, находящиеся справа от указателя, заполнены, а находящиеся слева не заполнены. Декодированный вектор представляет собой последовательность символов, выходящих из самого правого разряда -регистра. Отметим, что х-регистр эквивалентен указателю исследуемого узла, рассмотренному в связи с логической схемой на фиг. 6.44. Напротив, указатель глубины поиска, представленный на фиг. 6.48, указывает местонахождение в -регистре принятого ребра, исследуемого декодером.

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

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

искаженных принятых символов очень велико, то в процессе поиска необходимо провести очень большое количество вычислений и указатель в моменты поступления в декодер новых ребер остается у правого конца декодера. Если указатель глубины поиска достигает выходного конца декодера, то декодер не может продолжать работу. Следствия из этого факта будут обсуждены в разд. 6.5.