Графическое представление сверточных кодов

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

Так кодер, изображенный на рис. 8.29 может находиться в таких состояниях: , - 00; 10; 11; 01. Эти состояния соответствуют вершинам графа (рис. 8.30).

Диаграмма построена следующим образом. Первоначально кодер находится в состоянии 00 и поступление на вход символа 0 переводит его также в состояние 00. На выходе кодера образуются символы 00. На диаграмме этот переход обозначают петлей 00 около состояния 00. Далее при поступлении символа 1 кодер переходит в состояние 10 и на его выходе образуются символы 11. Этот переход из состояния 00 в состояние 10 обозначают стрелкой (ребром). Затем возможно поступление символа 0 или 1. Кодер переходит в состояние 01 либо 11, а символами на выходе будут 10 или 01 соответственно. Построение диаграммы состояний заканчивается, когда просмотрены возможные переходы из каждого состояния во все остальные.

Рассматриваемую диаграмму состояний можно развернуть во времени, при этом получим так называемую решеточную (решетчатую) диаграмму.

Так, например, решеточная диаграмма для кодера (рис. 8.29) диаграмма состояний которого представлена на рис. 8.30, показана на рис. 8.31. На ней принято, что штриховые линии (ветви) соответствуют переходам, происходящим при приходе информационного символа 1, а сплошные линии (ветви) — информационного символа 0. Из решеточной диаграммы видно, что ее структура после окончания “переходного процесса” в кодере становится повторяющейся. Подобная повторяемость структуры решеточной диаграммы будет возможна после третьего такта работы кодера, так как при поступлении в кодер четвертого информационного символа первый символ покидает регистр сдвига и более не оказывает влияния на формирование кодовых символов. Важное значение решетчатого представления состоит в том, что с ростом числа входных символов число вершин в решетке не растет, а остается равным , где – число ячеек в регистре сдвига, необходимое для кодирования.

Решетчатая диаграмма показывает все разрешенные пути, по которым может продвигаться кодер при кодировании. Например, при поступлении на вход кодера последовательности 1011…(рис.8.32) путь по решетке (1 – пунктирная, 0 – сплошная линия) даст возможность получить конфигурацию выходной последовательности 11100001…

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

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

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

Для этого кодирующего устройства решетчатая диаграмма выглядит так, как показано на ри. 8.32.

На рис. 8.33 показана подобная решеточная диаграмма c метками весов для кодера сверточного кода, построенная на базе решеточной диаграммы (рис. 8.32).

Из нее можно видеть, что из всех ненулевых путей, расходящихся и сливающихся с горизонтальным нулевым, будет один, имеющий вес 5, отходящий от нулевого пути на 3 ветви [AB(11)–BC(10)–CA(11)], два пути, отходящие от нулевого пути на 4 ветви [AB(11)–BD(01)–DC(01)–CA(11)] и 5 [AB(11)–BC(10)–CB(00)–BC(10)–CA(11)] ветвей и имеющие вес w = 6 и т. д.

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

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

В табл. 8.24 приведены последовательности символов на выходах соответствующих кодеров при поступлении на вход информационной последовательности, содержащей только одну единицу – = 1000… Это дает возможность определить выходной набор символов на полной длине кодового ограничения, которая подчеркнута в табл. 8.24.

Табл. 8.24. Последовательности символов на выходах кодеров при поступлении на вход информационной последовательности, содержащей только одну единицу – = 1000

№	Порождающие многочлены	Скорость кода	Выходная последователь-ность
			110001 000
			111011 00
			111110111 00
			111110 0

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

,

где – вес кодовой последовательности.