Копия койсра

КоманВа

на возрастание Ванном .

информационного каВра ?*«-ичиый регистр 1 кинпАимс

t , , " i , , cuCotr

1 i i ~- u*l йоБаелбннмй буфер )-«-йекойера

---- , - (К пользоеотелн!)

-т-I I

\ \ { ••• II ! Указатель

Первая

проба -информа- - ционного -*

каВра

Логика коВирования

начала файла

Начало регистра айресного файла

ичиыО регистр сйвига

3* Добавленный "буфер] Пробное койовое слово

Буфер вхоВных Ванных канала

Команйы на сВвиг U возростание

Команйа на возрастание

Порог

Добавленный буфер

-6 кййров-

Рис. 12.26. Реализация алгоритма Фано в виде регистра сдвига.

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

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

Теперь необходимо доказать два сделанных ранее утверждения: 1) если декодер не может найти альтернативный путь, то он двигается назад к узлу, в котором было установлено текущее значение порога, и понижает его; 2) декодер не будет повышать порог до тех пор, пока не достигнет ранее не исследованного узла. Что касается первого утверждения, очевидно, что если декодер не может найти новое ребро, от которого он должен двигаться

вперед, то он должен в конце концов возвратиться к указанному узлу. Но если в предшествующем некоторому узлу кадре перекошенное расстояние t(l I) меньше текущего значения порога Т, то порог был увеличен в 1-м кадре. В блок-схему на рис. 12.27 включен этот тест на нахождение узла, в котором был установлен текущий порог; теперь в этом узле порог уменьшается.

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

Дй-проверить, Выл ли послейний mip выше порога

Инйикатор

превыбуш,е10

Ьвшшп

M = i о,

если еперей если вбок Есш назйЗ

Был ли преВыВущий цтерагливный сйвиг сЗвигом назай 1

Нт- 6 этом кайре был установлен meKyuiuu порог

Понизить порог

и йекаться вперев

Ла-про9олжйть опробование новых

Нет-опробовать бругоО путь

путей

Если возможно {тл. если jq-\i т увеличить послевний ингаормационныо кайр Положить-

В противном случае йвигатьсн нцзаВ Положить I

М~-\ Заново вычислить j

Замечания. Кавры маркируются указателем кайра L Итерации не маркируится Ребра, выхойящие из текущего узла, маркируются j

Hem- посмотреть, превышает ли кайр порог

Да-посмотреть, нахоВится ли этот узел в НЕИССлеОовониой часто йерева (тогЭа ЭвиженоЕ J правильное)

Возможно,

Да-повысить порог йо максимальной кратной Д величины, меньшей

Сйвинуть вправо на обкм кайр

Начать новый информа-ционный KoBg с первого Значения (;=0)

Рис. 12.27. Развернутый алгоритм Фано.

может изменяться. Это происходит из-за того, что после понижения порога на Д перекошенное расстояние в тех узлах, где оно превышало первоначальный порог, никогда не будет меньше Т -\-+ Д. Когда декодер продвигается в новую часть дерева, он в конце концов достигает состояния, в котором t{l- \) <сТ -\- А и t{l) Т. В этой точке порог повышается. Это и является тестом для определения того, новый ли узел был посещен, и нет необходимости помнить все посещенные ранее узлы. Такой тест включен в схему на рис. 12.27.

Алгоритм Фано зависит от двух параметров р и А, которые могут быть выбраны при помощи моделирования на ЭВМ. На практике необходимо время от времени уменьшать t{l) и Т так, чтобы эти чИ(:ла не становились слишком большими. Вычитание из обеих функций некоторого числа, кратного А, не влияет на последующие вычисления.

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

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

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

В случае когда длина кодового ограничения не слишком велика, альтернативный путь состоит в движении указателя вперед. Если декодеру удастся найти правильный узел, то он может