Кодовое дерево и решетчатая диаграмма

Еще одним очень наглядным способом описания и иллюстрации работы сверточных кодов является использование так называемого кодового дерева.

Рассмотрим сверточный (6.3)–код со схемой, изображенной на рис. 12.8.

Соответствующее этому кодеру кодовое дерево – последовательность выходных состояний кодера при подаче на его вход цепочки входных символов 0 и 1 – приведено на рис. 12.9.

На диаграмме рис. 12.9 изображены входные и выходные последовательности кодера: входные – направлением движения по дереву (вверх – 0, вниз – 1), выходные – символами вдоль ребер дерева. При этом кодирование состоит в движении вправо по кодовому дереву.

Например, входная последовательность G(x) = (01000…… кодируется как F = (0011101100000… , последовательность G(x) = (1010100000… – как F(x) = (1110001000… .

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

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

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

С учетом этого неограниченное кодовое дерево, изображенное на рис. 10.9, переходит в ограниченную решетчатую диаграмму (кодовое дерево со сливающимися узлами) рис. 12.10.

Рис. 12.10

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

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

Пусть G(x)=(0110000… . Соответствующая ей кодовая последовательность будет иметь вид:

F(x) = (001101011100… ,

или G(x) = ( 110100… , тогда

F(x) = (1101010010110000….

Рассмотренный механизм кодирования входной кодовой последовательности в свёрточном коде достаточно просто реализуется кодером Трелисса.