12.8. АЛГОРИТМ ДЕКОДИРОВАНИЯ ВИТЕРБИ 433

которая нанесена штриховыми линиями, может быть опущена. Заштрихованные разряды регистра сдвига также могут быть опущены, а S]9 может вводиться непосредственно из предшествующего сумматора по модулю 2.

Сначала декодер исправляет второй бит каждого кадра пакета ошибок, а затем возвращается к началу пакета и исправляет первый бит каждого кадра. Поэтому декодер имеет четырехразрядный регистр сдвига, в котором он хранит {х) после завершения исправления. Третий бит каждого кадра является проверочным; он не исправляется.

Для исправления ошибки в {х) декодер проверяет компоненты «4 и s,9 синдрома. Если обе компоненты равны единице, то правый бит L>2 (л:) является ошибочным и в потоке данных, а также в регистре синдрома делаются соответсгвующие исправления. Пакет ошибок {х), начинающийся в более позднем кадре, не может вызвать сбоя, так как отклик eg (х) равен нулю. Параллельно с этим для нахождения ошибки в (х) декодер четырьмя кадрами позднее проверяет компоненты Sg и sg синдрома. Если они обе равны единице, а S4 равна нулю, то правый бит (л:)-регистра ошибочен. Такая проверка {х) не приводит к нахождению ошибок в течение первых четырех тактов, но затем начинает исправлять ошибки в W] (л:). Пакет (х), начинающийся в более позднем кадре, не может вызвать сбоя, так как отклик eg (л:) равен нулю. В силу выбора способа проверки еще не исправленный бит eix) также не может вызвать сбоя, и поэтому равна нулю.

После появления пакета ошибок длины 12 принятое слово не должно содержать больше ошибок, чтобы синдрому ничто не мешало во время исправления этого пакета. Для этого необходимо, чтобы до 29-го кадра не происходило ошибок. Следовательно, между пакетами ошибок должно быть свободно от ошибок не менее 24 кадров (72 хороших бита). При выполнении этого правила декодер будет успешно исправлять следующие друг за другом пакеты ошибок длины не больше 12 каждый.

12.8. АЛГОРИТМ ДЕКОДИРОВАНИЯ ВИТЕРБИ

Алгоритм декодирования Витерби является полным алгоритмом декодирования сверточных кодов. Так как он является полным, вероятность отказа от декодирования равна нулю; однако при фиксированном коде вероятность ошибки декодирования будет больше, чем у неполного декодера. Этот алгоритм практически употребляется для двоичных кодов с малой длиной кодового ограничения - в настоящее время пределом являются длины кодового ограничения от 7 до10. Недвоичные коды декодировать декодером Виберби труднее, и это возможно лишь при очень малых длинах кодового ограничения.

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

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

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

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

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

12.8. AЛroPИtм ДЕКОДИРОВАНИЙ BHtEPBrt 438

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

Рассмотрим множество выживших путей, ведущих в множество узлов в г-й временной кадр. Эти пути проходят через один или более узлов в первом временном кадре. Если все пути проходят через один и тот же узел в первом временном кадре, то вне зависимости от того, в каком узле кодер находится в г-й временной кадр, мы знаем наиболее правдоподобный среди посещенных им в первый временной кадр узлов. Иначе говоря, мы знаем первый информационный кадр, хотя еще не приняли решение об г-м кадре.

Для построения декодера Витерби требуется выбрать ширину окна декодирования Ъ, которая обычно в несколько раз превосходит длину блока, и оценить работу декодера путем моделирования на ЭВМ. В п-й временной кадр декодер проверяет, все ли выжившие пути имеют одинаковое первое ребро. Если первое ребро одинаково, то оно определяет первый декодированный информационный кадр, который подается на выход декодера.

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

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

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