Решетчатая диаграмма

Исследование древовидной диаграммы на рис. 8.6 показывает, что в этом приме­ре после третьего ветвления в момент времени t₄ структура повторяется (в общем случае древовидная структура повторяется после К ответвлений, где К — длина ко­дового ограничения). Пометим каждый узел в дереве (рис. 8.6), ставя в соответствие четыре возможных состояния в регистре сдвига: а = 00, b= 10, с = 01 и d = 11. Пер­вое ветвление древовидной структуры в момент времени t₁ дает пару узлов, поме­ченных как а и b. При каждом последующем ветвлении количество узлов удваивает­ся. Второе ветвление в момент времени t₂ дает в результате четыре узла, помечен­ных как а,b, с и d. После третьего ветвления всего имеется восемь узлов: два — а, два — b, два — с и два — d.

Можно видеть, что все ветви выходят из двух узлов одного и того же состояния, образуя идентичные ветви последовательностей кодовых слов. В этот момент дерево делится на идентичные верхнюю и нижнюю части. Смысл этого становится яснее после рассмотре­ния кодера, изображенного на рис. 8.3. Когда четвертый входной бит входит в кодер слева, первый входной бит справа выбрасывается и больше не влияет на кодовые слова на выходе. Следовательно, входные последовательности 1 0 0 x y... и 0 0 0 x y..., где крайний левый бит является самым ранним, после (К = 3)-го ветвления генерируют одинаковые кодовые слова ветвей. Это означает, что любые состояния, имеющие одина­ковую метку в один и тот же момент t_i можно соединить, поскольку все последующие пути будут неразличимы. Если мы проделаем это для древовидной структуры, показан­ной на рис. 8.6, получим иную диаграмму, называемую решетчатой.

Решетчатая диа­грамма, которая использует повторяющуюся структуру, дает более удобное описание ко­дера, по сравнению с древовидной диаграммой. Решетчатая диаграмма для сверточного кодера,

изображенного на рис. 8.3, показана на рис. 8.7.

При изображении решетчатой диаграммы мы воспользовались теми же условными обозначениями, что и для диаграммы состояния: сплошная линия обозначает выходные данные, генерируемые входным нулевым битом, а пунктирная — выходные данные, ге­нерируемые входным единичным битом. Узлы решетки представляют состояния кодера; первый ряд узлов соответствует состоянию а = 00, второй и последующие — состояниям b = 10, с = 01 и d - 11. В каждый момент времени для представления 2^К-1 возможных со­стояний кодера решетка требует 2^К-1 узлов. В нашем примере после достижения глуби­ны решетки, равной трем (в момент времени t₄), замечаем, что решетка имеет фиксиро­ванную периодическую структуру. В общем случае фиксированная структура реализует­ся после достижения глубины К. Следовательно, с этого момента в каждое состояние можно войти из любого из двух предыдущих состояний. Также из каждого состояния можно перейти в одно из двух состояний. Из двух исходящих ветвей одна соответствует нулевому входному биту, а другая — единичному входному биту. На рис. 8.7 кодовые слова на выходе соответствуют переходам между состояниями, показанными как метки на ветвях решетки.

Один столбец временного интервала сформировавшейся решетчатой структуры ко­дирования полностью определяет код. Несколько столбцов показаны исключительно для визуализации последовательности кодовых символов как функции времени. Со­стояние сверточного кодера представлено содержанием крайних правых К - 1 разря­дов в регистре кодера. Некоторые авторы описывают состояние с помощью крайних левых К -1 разрядов. Какое описание правильно? Они оба верны. Каждый переход имеет начальное и конечное состояние. Крайние правые К - 1 разрядов описывают начальное состояние для текущих входных данных, которые находятся в крайнем ле­вом разряде (степень кодирования предполагается равной 1/n). Крайние левые К – 1 разрядов являются конечным состоянием для такого перехода. Последовательность кодовых символов характеризуется N ветвями (что представляет N бит данных), зани­мающими N интервалов времени. Она связана с конкретным состоянием в каждый из N + 1 интервалов времени (от начала до конца). Таким образом, мы запускаем биты в моменты времени t₁,t₂,..., t_N и интересуемся метрикой состояния в моменты времени t₁,t₂,..., t_N+1. Здесь использовано следующее условие: текущий бит располагается в крайнем левом разряде, а крайние правые К - 1 разрядов стартуют из состояния со всеми нулями. Этот момент времени обозначим как начальное время, t₁. Время завер­шения последнего перехода обозначим как время прекращения работы, t_N+1.

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