Основы теории передачи информации


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


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

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

Рис. 2.5

Соответствующее этому кодеру кодовое дерево

– последовательность выходных состояний кодера при подаче на его вход цепочки входных символов 0 и 1 – приведено на рис. 2.6. 

                                    Рис. 2.6

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

Например,  входная последовательность  m  = (01000……  кодируется  как  U = (0011101100000… , последовательность  m = (1010100000… -   как U = (1110001000… .

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

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

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

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

Рис. 2.7


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

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

Пусть m=(0110000… .

Соответствующая ей кодовая последовательность будет иметь вид: 

U = (001101011100… ,

или m  = ( 110100… , тогда

U = (1101010010110000…; 

или m  = ( 000000… , тогда

U = (1101010010110000

и т.д., проще не придумаешь.




Начало  Назад  Вперед



Книжный магазин