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

Любой сверточный кодер можно трактовать как конечный автомат, т.е. машину с конечным числом состояний. Конкретное состояние автомата есть просто содержимое его памяти. В зависимости от того, какое из двух значений имеет бит входного информационного потока кодер в следующем такте переходит в одно из двух возможных состояний. В свою очередь, в текущем такте кодер принимает некоторое конкретное состояние только как результат перехода в него из одного из двух возможных предыдущих. Подобный двоичный характер смены состояний связан с подачей на вход регистра единственного информационного бита на один такт работы (R=1/n). Если бы – в желании обеспечить скорость R=l/n – скользящее окно сдвигалось на l битов за один такт, число разрешенных переходов в и из некоторого состояния оказалось бы равным 2^l.

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

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

Что касается выходных кодовых символов, они показаны как метки при соответствующих ветвях. Так, кодер с текущим состоянием 00, вырабатывает кодовую комбинацию 11 при поступлении на вход бита, равного единице. Поэтому ветвь, отвечающая переходу 00®10, помечена символами 11 и т.д.

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

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

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