Древовидные диаграммы

Несмотря на то, что диаграммы состояний полностью описывают кодер, по сути, их нельзя использовать для легкого отслеживания переходов кодера в зависимости от времени, поскольку диаграмма не представляет динамики изменений. Древовидная диаграмма (tree diagram) прибавляет к диаграмме состояния временное измерение. Дре­вовидная диаграмма сверточного кодера, показанного на рис. 8.3, изображена на рис. 8.6. В каждый последующий момент прохождения входного бита процедура ко­дирования может быть описана с помощью перемещения по диаграмме слева напра­во, причем каждая ветвь дерева описывает кодовое слово на выходе. Правило ветвле­ния для нахождения последовательности кодовых слов следующее: если входным би­том является нуль, то он связывается со словом, которое находится путем перемещения в следующую (по направлению вверх) правую ветвь; если входной бит — это единица, то кодовое слово находится путем перемещения в следующую (по направлению вниз) правую ветвь. Предполагается, что первоначально кодер содержал одни нули. Диаграмма показывает, что если первым входным битом был нуль, то ко­довым словом ветви на выходе будет 00, а если первым входным битом была единица, то кодовым словом на выходе будет 11. Аналогично, если первым входным битом бы­ла единица, а вторым — нуль, на выходе вторым словом ветви будет 10. Если первым входным битом была единица и вторым входным битом была единица, вторым кодо­вым словом на выходе будет 01. Следуя этой процедуре, видим, что входная последо­вательность 1 1 0 1 1 представляется жирной линией, нарисованной на древовидной диаграмме (рис. 8.6). Этот путь соответствует выходной последовательности кодовых слов 1 1 0 1 0 1 0 0 0 1.

Добавленное измерение времени в древовидной диаграмме (по сравнению с диа­граммой состояния) допускает динамическое описание кодера как функции конкрет­ной входной последовательности. Однако заметили ли вы, что при попытке описания с помощью древовидной диаграммы последовательности произвольной длины возни­кает проблема? Число ответвлений растет как 2^L, где L — это количество кодовых слов ветвей в последовательности. При большом L вы бы очень быстро исписали бумагу и исчерпали терпение.

Дата добавления: 2015-08-02