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

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

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

Рисунок 2.9 - Древовидное представление кодера

(степень кодирования 1/2, К= 3)

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

При изображении решетчатой диаграммы (рисунок 2.10) мы воспользовались теми же условными обозначениями, что и для диаграммы состояния: сплошная линия обозначает выходные данные, генерируемые входным нулевым битом, а пунктирная - выходные данные, ге­нерируемые входным единичным битом.

Рисунок 2.10 - Решетчатая диаграмма кодера (степень кодирования 1/2, К= 3)

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

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

Для кодера со скоростью кодирования 2/3 примерный вид данной диаграммы приведен ниже:

Рисунок 2.11 - Решетчатая диаграмма кодера (степень кодирования 2/3, К= 3)