Диаграмма состояний и решетка сверточного кода. Свободное расстояние.

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

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

Пример 10.2.1. Обратимся к кодеру из примера 10.1.1. Данное устройство может находиться в одном из следующих состояний: 00, 10, 01 и 11 (первый символ отражает состояние крайней левой ячейки памяти). Очевидно, что из состояния 00 кодер может перейти либо в состояние 00 (при входном бите, равном 0), либо в 10 (при подаче на вход единицы). Аналогичным образом указаны и остальные переходы в диаграмме состояний, приведенной на рис. 10.5, в которой узлы изображены в виде кружков, внутреннее содержание которых отражает текущее состояние регистра сдвига. Сплошные стрелки соответствуют переходам, которые обусловлены поступлением нулевого входного бита, тогда как пунктирные – битом, равным единице. Легко заметить, что каждому узлу отвечают два исходящих и столько же входящих переходов. Что же касается кодовых символов, то их значения приведены над соответствующими ветвями диаграммы. Так например, кодер, находящийся в состоянии 00, вырабатывает кодовую комбинацию 11 при поступлении на вход единичного бита. Поэтому ветвь, отражающая переход , помечена символами 11 и т.д.

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

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

Модель поведения кодера, построенная на основе вышеприведенных рассуждений, представлена на рис. 10.7 и называется решетчатой диаграммой, или просто решеткой. Любой путь по решетке представляет собой ничто иное, как кодовое слово сверточного кода, Например, входная информационная последовательность вида 01010 отображается в кодовое слово 00110100011100.

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