8.2. СВЁРТОЧНЫЕ КОДЫ

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

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

Рис. 8.2.1. Свёрточный кодер

Один метод для описания свёрточного кода сводится к заданию его порождающей матрицы, так же, как мы это делали для блоковых кодов. В общем, порождающая матрица для свёрточного кода полубесконечная, поскольку входная последовательность полубесконечная. Можно использовать эквивалентное представление кода, в котором мы определяем набор из  векторов, один вектор для каждого из  сумматоров по . Каждый вектор имеет  измерений и содержит в себе информацию о соединениях кодера с сумматорами по . «1» в -ой позиции вектора указывает на то, что соответствующая ячейка регистра сдвига подсоединена к сумматору по , а 0 в данной позиции указывает на то, что такого соединения нет.

Для конкретности рассмотрим двоичный свёрточный кодер с кодовым ограничением  и , показанный на рис. 8.2.2.

Рис. 8.2.2. Сверточный кодер с

Считается, что первоначально все ячейки регистра сдвига находятся в нулевом состоянии. Допустим, что первый входной бит «1». Он без задержки появляется на выходе первой (левой) ячейки регистра и, соответственно, на всех трёх входах выходного ключа (мультиплексора). Ключ поочерёдно выдаёт содержимое входов, и выходная последовательность из 3 бит 111. Допустим, что второй входной бит «0». Он записывается в первую ячейку регистра, проталкивает предыдущий бит («1») во вторую ячейку - и на входах мультиплексора (сверху вниз) появляются 0, 0 и 1. Тогда вторая выходная последовательность 001. Если третий входной бит 1, выходная последовательность 100 – и так далее. Таким образом, в ответ на каждый входной бит  свёрточный кодер откликается тремя битами, по числу функциональных генераторов . Пронумеруем функциональные генераторы и их выходы в соответствии с порядком считывания мультиплексором (1, 2 и 3). Затем, поскольку с первым функциональным генератором соединена только первая ячейка (сумматор по  не нужен) генератор можно отобразить вектором

.

Второй функциональный генератор соединен с ячейками 1 и 3. Следовательно,

.

Наконец,

.

Генераторы (порождающие полиномы) для этого кода обычно дают в восьмеричной форме как . Мы заключаем, что, когда , требуются  генераторов, каждый размерностью , чтобы описать кодер.

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

Пример 8.2.1. Рассмотрим свёрточный кодер со скоростью кода 2/3, показанный на рис. 8.2.3. В этом кодере каждый раз два бита поступают на вход регистров сдвига, а на выходе генерируется три бита.

Рис. 8.2.3. Свёрточный кодер с

Генераторы определяются векторами

.

В восьмеричной форме .

Имеются три альтернативных метода, которые часто используются для описания свёрточного кода. Это древовидная диаграмма, решетчатая диаграмма и диаграммд состояний. Для примера, древовидная диаграмма для свёрточного кодера, показанного на рис. 8.2.2, иллюстрируется на рис. 8.2.4.

Предположим, что кодер находится первоначально в нулевом состоянии (во всех ячейках нули). Диаграмма показывает, что, если первый вход 0 - выходная последовательность 000, а если первый вход 1 - выходная последовательность 111. Теперь, если первый вход 1, а второй 0 - второй набор выходных битов 001. Продвигаясь по дереву видим, что если третий входной бит 0, тогда выходной 011, если же третий выходной бит 1, то выход 100. Видим, что частная последовательность обуславливает выбор узла дерева, а правило движения по ветвям дерева такое – надо двигаться к верхней ветви, если следующий бит 0 и к нижней, если следующий бит 1. Таким образом, траектория частного пути по дереву определяется входной последовательностью.

Рис. 8.2.4. Древовидная диаграмма для сверточного  кода, имеющего скорость

Внимательное наблюдение за деревом, показанном на рис. 8.2.4, обнаруживает, что структура повторяет себя после третьего такта. Правый столбец выходных «троек» бит распадается на две одинаковые совокупности по 8 «троек». Это поведение согласуется с тем фактом, что кодовое ограничение . Это значит, трёхбитовые выходные последовательности на каждом такте определяются входным битом и двумя предыдущими входными битами, т.е. двумя битами, содержащимися в первых двух ячейках регистра сдвига. Бит в последней ячейке регистра сдвига перемещается направо (покидает регистр) и не влияет больше на выход. Так что мы можем сказать, что трёхбитовая последовательность выхода для каждого входного бита определяется входным битом и четырьмя возможными состояниями регистра сдвига, обозначенными . Если пометить узлы дерева этими же метками, найдем, что на третьем такте имеются два узла с пометкой , два с пометкой , два с пометкой  и два с пометкой . Теперь видим, что все ветви, исходящие из двух узлов с одинаковой меткой (одинаковым состоянием) являются идентичными в том смысле, что они генерируют одинаковые выходные последовательности. Это означает, что два узла, имеющие одинаковую метку, можно слить. Если мы это сделаем в дереве, показанном на рис. 8.2.4, мы получим другую диаграмму, которая более компактна, именно получим решётку. Для примера решётчатая диаграмма для свёрточного кодера рис. 8.2.2 показана на рис. 8.2.5.

Чтобы изучить эту диаграмму, договоримся о том, что сплошные линии означают выходы, генеририруемые входом 0, а пунктирные – выходы, генеририруемые входом 1. В примере, который мы рассматриваем, видим, что после начального состояния решётка содержит четыре узла на каждом шаге, соответствующие четырем состояниям регистра сдвига  и . После второго шага каждый узел в решётке имеет два входных пути и два выходных. Из выходных путей один соответствует входу 0, а второй – входу 1.

Рис. 8.2.5. Решётчатая диаграмма для свёрточного кода, имеющего скорость

Поскольку выход кодера определяется входом и состоянием кодера, ещё более компактной, чем решётка, является диаграмма состояний. Диаграмма состояний — это просто граф возможных состояний кодера и возможных переходов из одного состояния в другое. Для примера на рис. 8.2.6 показана диаграмма состояний для кодера, показанного на рис. 8.2.2.

Рис. 8.2.6. Диаграмма состояний для свёрточного кода, имеющего скорость

Эта диаграмма показывает, что возможные переходы таковы

,

где  означает переход из состояния  в , когда входной бит 1. Три бита, показанных далее на каждой ветви диаграммы состояний, представляют выходные биты. Пунктирная линия на графе означает, что входной бит 1, в то время как сплошная линия

указывает, что входной бит 0.

Пример 8.2.2. Рассмотрим свёрточный код со скоростью , описанный в примере 8.2.1 и показанный на рис. 8.2.3. Первые два входных бита могут быть 00, 01, 10 или 11. Соответствующие выходные биты – 000, 010, 111, 101. Когда следующая пара входных битов входит в кодер, первая пара передвигается в следующую ячейку. Соответствующие выходные биты зависят от пары битов, переместившихся во вторую ячейку и новой пары входных битов. Следовательно, древовидная диаграмма для этого кода, показанная на рис. 8.2.7, имеет четыре ветви на узел, соответствующие четырём возможным парам входных символов.

Рис. 8.2.7. Древовидная диаграмма для свёрточного кода, имеющего параметры  

Поскольку кодовое ограничение кодера , дерево начинает повторяться после второго шага. Как показано на рис. 8.2.7, все ветви, исходящие из узла, обозначенного  (состояния ) дают идентичные выходы. Путем слияния узлов, имеющих одинаковое название, мы получаем решётку, показанную на рис. 8.2.8. Итоговая диаграмма состояний для этого кодера показана на рис. 8.2.9.

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

Рис. 8.2.8. Решётчатая диаграмма для сверточного кода, имеющего параметры

Три типа диаграмм, описанных выше, используются также для представления недвоичных свёрточных кодов. Если число символов в алфавите равно , результирующий недвоичный код можно также представить как эквивалентный двоичный код. Следующий пример рассматривает свёрточный код этого типа.

Рис. 8.2.9. Диаграмма состояний для свёрточного кода, имеющего параметры

Пример 8.2.3. Рассмотрим свёрточный код, генерируемый кодером, показанный на рис. 8.2.10. Этот код можно описать как двоичный свёрточный код с параметрами  и с генераторами

.

Рис. 8.2.10. Свёрточный кодер с

За исключением различия в скорости, этот код похож по форме на свёрточный код со скоростью , рассмотренный в примере 8.2.1.

Альтернативно, код, генерируемый кодером рис. 8.2.10, можно описать как не двоичный  код с одним четырехпозиционным символом на входе и двумя четырехпозиционных символов на выходе. Действительно, если выходные символы кодера трактуются модулятором и демодулятором как -ичные , которые передаются по каналу посредством некоторой -ичный  модуляции, код можно соответственно рассмотреть как недвоичный.

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