Материал: Лекция 9

Тогда на выходе первого сумматора по модулю 2 кодера (рис. 8.9) последовательность кодовых символов будет 11011, ей соответствует многочлен

.

На выходе второго сумматора по модулю 2 этого кодера последовательность кодовых символов будет 10001, а ей соответствует многочлен

.

В итоге на выходе кодера будет сформирована последовательность выходных символов за 5 тактов нахождения входной последовательности 101 в трехразрядном регистре:

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

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

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

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

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

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

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

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