ГЛАВА 12. СВЕРТОЧНЫЕ КОДЫ

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

При другой схеме кодирования поток данных разбивается на гораздо меньшие блоки длины которые мы будем называть кадрами информационных символов. Эти кадры информационных символов обычно включают лишь несколько символов. Кадры информационных символов кодируются кадрами кодового слова длины каждый. Однако вместо того, чтобы независимо кодировать отдельные кадры информационных символов в отдельные кадры кодового слова, кодирование каждого кадра информационных символов в отдельный кадр кодового слова производится с учетом предыдущих кадров информационных символов. Поэтому процедура кодирования связывает между собой последовательные кадры кодовых слов.

Коды, получаемые таким образом, называются древовидными кодами. Наиболее важными древовидными кодами являются коды, известные под названием сверточных кодов. Сверточнымн кодами являются тревовндные коды, которые обладают дополнительными свойствами линейности и постоянства во времени. Вначале мы рассмотрим общий класс древовидных кодов, в основном концентрируя свое внимание на изучении сверточных кодов как частного случая древовидных кодов.

12.1. ДРЕВОВИДНЫЕ И РЕШЕТЧАТЫЕ КОДЫ

Изучение древовидных кодов начнем с рассмотрения кодера, представленного на рис. 12.1 в виде регистра сдвига. Многие основные определения могут быть введены с использованием этой

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

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

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

Рис. 12.1. Кодер в виде регистра сдвига.

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

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

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

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

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

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

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

Конечность длины кодового ограничения. Длила кодового ограничения может быть конечной или бесконечной. Практически древовидные коды всегда имеют конечную длину кодового ограничения. Однако в теоретических исследованиях иногда полезны коды с бесконечной длиной кодового ограничения. Древовидный -код с копечной длиной кодового ограничения длиной слова и кодовой длиной блока называется также решетчатым -кодам.

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

Линейность. Кодовая последовательность любой линейной комбинации двух информационных последовательностей совпадает с такой же линейной комбинацией кодовых последовательностей этих двух информационных последовательностей. Иначе говоря, если являются двумя информационными последовательностями с кодовыми последовательностями то соответствует кодовая последовательность

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

Определение 12.1.2. Линейный постоянный во времени древовидный -код, имеющий конечную длину слова называется сверточным -кодом. Сверточный -код, удовлетворяющий условию систематичности, называется систематическим сверточным -кодом.

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

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

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

Рис. 12.2. (см. скан) Классификации древовидных кодов.

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

Сверточные и другие решетчатые коды удобно описывать специальным графам, называемым решеткой; отсюда название — решетчатые коды. Решеткой называется граф, узлы которого находятся в прямоугольной координатной сетке, полубесконечной справа; число узлов в каждом столбце конечно. Конфигурация ребер, соединяющих узлы каждого столбца с узлами столбца справа, одинакова для всех столбцов. Узлы, которые не могут быть достигнуты при движении вправо из верхнего левого узла, обычно не указываются.

Типичная решетка для двоичного кодового алфавита представлена на рис. 12.4. Эту решетку можно использовать для описания второго кодера, изображенного на рис. 12.3. Ее маркировка на рис. 12.5 соответствует этому кодеру. Узлы в каждом столбце решетки представляют состояний, в которых может находиться регистр сдвига. Каждый последующий столбец представляет собой набор состояний в следующий момент времени.

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

Маркированная решетка описывает сверточный код в том смысле, что все пути слева направо по решетке обозначают кодовые слова. Маркировка ребер одинакова для каждого сегмента и линейна в том смысле, что линейная комбинация маркировок любого множества ребер является маркировкой некоторого ребра.

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

Рис. 12.3. Примеры соерточных кодеров, а — кодер для двоичного сверточного -кода, б - кодер для двоичного сверточного (6, 3)-кода.

Рис. 12.4. Решетка сверточного кода

Рис. 12.5. Решетчатая диаграмма сверточного -кода.

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

Рис. 12.6. Дерево двоичного древовидного кода со скоростью 1/2.

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