КаЭр информационных симболоб

II II I

Длина койоеого ограничения

Окно койирования

III

1 I I

Кобер

Рис. 12,1. Кодер в виде регистра сдвига.

I I I I I I I I

Найр койоеого слова

схемы. Информационная последовательность вводится в кодер, начиная с нулевого момента времени и до бесконечности. Поток входящих информационных символов разбивается на сегменты, которые содержат по символов и называются кадрами информационных символов. Кадр информационных символов может, в частности, состоять из единственного символа, что нередко имеет место на практике. В кодере может храниться т кадров. В течение каждого временного кадра в регистр сдвига вводится новый кадр информационных символов, а кадр информационных символов, дольше остальных хранившийся в нем, выводится из него и сбрасывается. В конце каждого временного кадра в кодере хранятся последние т и,з поступивших в него кадров (всего mk информационных символов). В начале каждого временного кадра кодер по введенному кадру информационных символов и т хранящимся Б нем кадрам вычисляет один кадр кодового слова, имеющий длину «о символов. Этот кадр кодового слова выводится из кодера, как только следующий кадр информационных символов выводится Б него. Следовательно, каждым информационным символам соответствует передача по каналу щ кодовых символов.

Бесконечное множество всех бесконечно длинных кодовых слов, получсемых при поступлении в этот кодер всех возможных входных последовательностей, называется древовидным («о, k-KodoM. Скорость R этого древовидного кода определяется отношением

R -- kji\.

Важной характеристикой сверточного кода является величина v= mk. Она называется длиной кодового ограничения. Это нестрогое определение длины кодового ограничения достаточно для

МНОГИХ целей (хотя в некоторых случаях необходимо более строгое определение). Формальное определение будет дано в следующем параграфе. На рис. 12.1 изображен кодер, у которого 4 = 3, = 5hv=21.

В древовидном коде используются и несколько других мер длины. Положим k = (т + I) ко- Это k непосредственно связано с длиной кодового ограничения. Назовем ее информационной длиной слова сверточного кода. Соответствующая ей мера кодовых последовательностей называется кодовой длиной блока п. Она дается формулой

« = (т + 1) По = knjkf).

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

Дадим формальное определение древовидного кода.

Определение 12.1.1. Древовидный («д, кУкод - это отображение на себя множества полубесконечных последовательностей элементовиз GF (q), такое, что если для любого М первые Мк компонент двух полубесконечных последовательностей совпадают, то первые компонент отображений этих последовательностей тоже совпадают.

Древовидный код лучше всего можно представить себе, обратившись к кодеру, изображенному на рис. 12.1. Древовидный код характеризуется длиной кодового ограничения (быть может, бесконечной) и скоростью.

Частные случаи древовидных кодов получаются различными комбинациями следующих четырех свойств. Эти свойства полезно проследить на показанном на рис. 12.1 кодере.

Конечность длины кодового ограничения. Длина кодового ограничения может быть конечной или бесконечной. Практически древовидные коды всегда имеют конечную длину кодового ограничения. Однако в теоретических исследованиях иногда полезны коды с бесконечной длиной кодового ограничения. Древовидный (щ, /го)-код с конечной длиной кодового ограничения v, длиной слова к = V ~{- ко и кодовой длиной блока п называется также решетчатым («, к)-кодом.

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

Линейность. Кодовая последовательность любой линейной комбинации двух информационных последовательностей совпадает с такой же линейной комбинацией кодовых последовательностей этих двух информационных последовательностей. Иначе говоря, если dy и с?2 являются двумя информационными последовательностями с кодовыми последовательностями G [d и G (dg), то adx -Ь bdi соответствует кодовая последовательность

G {ady -f bd) = aG (dy) + bG(d,).

Систематичность. Систематическим древовидным кодом называется код, в котором каждый кадр информационных символов составляет первые kg символов первого из тех кадров кодовой последовательности, на которые влияет данный кадр информационных символов.

Определение 12.1.2. Линейный постоянный во времени древовидный («о, )-код, имеющий конечную длину слова к = {т-\-1) k, называется сверточным (п, к)-кодом. Сверточный (п, )-код, удовлетворяющий условию систематичности, называется систематическим сверточным (п, к)-кодом.

Заметим, что мы можем называть один и тот же код древовидным («0. йо)-кс)дом или сверточным (п, )-кодом. На практике k значительно больше k, и поэтому недоразумений не возникает.

Определение 12.1.3. Постоянный во времени древовидный («0. ко)-код, имеющий конечную информационную длину слова k, называется скользящим блоковым (п, к)-кодом. Следовательно, линейный скользящий блоковый код является сверточным кодом.

На рис. 12.2 графически иллюстрируются связи между различными классами древовидных кодов. Существуют и другие возможности, но наиболее интересны.ми являются эти случаи. Примеры кодеров для двух различных сверточных кодов показаны на рис. 12.3; в обоих случаях щ = 2, = I. Первый из них служит кодером для систематического двоичного сверточного (12,6)-кода с длиной кодового ограничения, равной 5. Он обладает всеми указанными выше свойствами. Второй является кодером для несистематического двоичного сверточного (6,3)-кода с длиной кодового ограничения 2. В обоих случаях входные символы преобразуются двумя фильтрами, один из которых образуетсяверх-ними отводами, а другойнижними. Символы с выходовэтих двух фильтров попеременно во времени считываются и подаются