Решетчатый код может быть также представлен особым графом, показанным на рис. 12.6 и называемым деревом. В этом графе число узлов и ветвей неограниченно увеличивается при росте дерева вправо; этим и объясняется название древовидных кодов. Каждый узел дерева - это состояние, соответствующее всем поступившим в него информационным символам, начиная с нулевого момента времени. Для кодов с бесконечной длиной кодового ограничения или даже умеренно большой длиной кодового ограничения дерево - это именно тот граф, который их описывает. Кодовые слова соответствуют путям по дереву. Для кодов с малой длиной кодового ограничения, однако, удобнее использовать решетку. Как мы уже видели, код полностью описывается последними V поступившими в кодер символами, и их достаточно для определения состояния.

12.2. ОПИСАНИЕ СВЕРТОЧНЫХ КОДОВ С ПОМОЩЬЮ МНОГОЧЛЕНОВ

Сверточный ((т*-Ь 1) «о. (" + 1) о)-код над GF (q) с длиной кодового ограничения v = тк можно генерировать с помощью наборов фильтров с конечным импульсным откликом (КИО-фильтров); каждый набор состоит из kg КИО-фильтров над GF (q). В кодер поступает поток символов со скоростью символов в единицу времени, а из него выходит в канал поток символов со скоростью щ символов в единицу времени. На рис. 12.7 показан кодер для двоичного сверточного кода с По = 5 и = 1. Такой кодер состоит из серии фильтров и выходного регулирующего буфера, который необходим для согласования выходной скорости со скоростью фильтров. На рис. 12.8 приведен аналогичный кодер для двоичного сверточного кода с = 5, = 3. Для согласования входной скорости со скоростью фильтров добавлен входной буфер.

Каждый КИО-фильтр может быть представлен многочленом степени не выше т. Если входной поток записать как многочлен (быть может, бесконечной длины), то работа фильтра может быть описана как умножение многочленов. В этом случае кодер сверточного кода может быть представлен множеством многочленов; поэтому и сам код может быть представлен посредством того же множества многочленов. Иначе говоря, код является множеством кодовых слов, которое порождается данным множеством многочленов. Эти многочлены называются порождающими многочленами кода. Наибольшая степень порождающих многочленов равна т.

В отличие от блоковых кодов, которые описываются единственным порождающим многочленом, сверточный код требует для своего описания нескольких порождающих многочленов - в общем случае кПо многочленов. Пусть gu (х), t = 1, о. / = 1, Rq - множество порождающих многочленов. Они могут

Ширина 1 Бит

5 ffumoe. за ейиницу времени

Выхойной

регулирующий

гуфер

На&ор КИО-фильтров Рис. 12.7. Сверточный кодер.

3 бита за ейиницу времени

5 битов за ейиницу времени

Набор КИО-фильтров Рис. 12.8. Сверточный кодер (пр = 5, ko = 3).

В дальнейшем, следуя автору, мы иногда будем для краткости называть эту матрицу порождающей матрицей. - Прим ред.

) На практике используется несколько различных определений термина длина кодового ограничения. Неопровержимый довод в пользу нашего выбора состоит в следующем: код с меньшей решеткой имеет меньшую длину кодового ограничения, решетка всегда имеет q узлов, и любой минимальный кодер - будь он кодером с обратной или прямой связью - всегда имеет v элементов памяти. Следовательно, v измеряет сложность сверточного кода. Иногда полезны также данные нами определения k я п; в литературе они также называются длиной кодового ограничения.

быть объединены в матрицу размера X По, называемую поро-ждаюи/ей матрицей из многочленов i):

G W= lgi,-{x)].

При ko, большем единицы, некоторые порождающие многочлены могут равняться нулю.

Например, порождающие матрицы из многочленов кодеров на рис. 12.3 записываются в виде

G (х) = и х + х + I]

* G (х) = [х + X + 1 + 1 1.

Дадим формальное определение длины кодового ограничения сверточного кода, основываясь на порождающей матрице из многочленов G (х).

Определение 12.2.1. Длиной кодового ограничения сверточного кода, задаЬаемого порождающей матрицей из многочленов [gij (х) I, называется величина )

V = Ц max [deg gtj- (х)]. 1=1 /

Информационной длиной кодового слова называется k = ko max [deg gtj (x) -f- 11.

i. i

a кодовой длиной блока называется

п = По max [deg g (х) -f П. (, /

Например, у сверточных кодов, кодеры которых показаны на рис. 12.9, V = 3, == 6, R = 9 и V == 4, = 6, R = 9 соответственно.

Будем рассматривать входной кадр как ko параллельно поступающих символов, а последовательность входных кадров как ko параллельных последовательностей символов. Они могут быть