Сверточное кодирование

Типичная функциональная схема системы цифровой связи использующая сверточное кодирование/декодирование и модуляцию/демодуляцию, показана на рисунке 2.4. Исходное сообщение на входе обозначается последовательностью где , - двоичный знак (бит), a i - индекс времени. Если быть точным, то элементы m следовало бы дополнять индексом члена класса (например, для бинарного кода, 1 или 0) и индексом времени. В дальнейшем для простоты будем использовать только индекс, обозначающий время (или расположение элемента внутри последовательности). Будем предполагать, что все , равновероятно равны единице или нулю и независимы между собой. Будучи независимой, последовательность битов нуждается в некоторой избыточности, т.е. знание о бите , не дает никакой информации о бите , (при ). Кодер преобразует каждую последовательность m в уникальную последовательность кодовых слов . Даже несмотря на то что последовательность m однозначно определяет последовательность U, ключевой особенностью сверточных кодов является то, что данный k-кортеж внутри m не однозначно определяет связанные с ним n-кортежи внутри U, поскольку кодирование каждого из k-кортежей является функцией не только k-кортежей, но и предыдущих К-1 k- кортежей. Последовательность U можно разделить на последовательность кодовых слов: . Каждое кодовое слово U, состоит из двоичных кодовых символов, часто называемых канальными символами, канальными битами, или битами кода; в отличие от битов входного сообщения, кодовые символы не являются независимыми.

В типичных системах связи последовательность кодовых слов U модулируется сигналом . В ходе передачи сигнал искажается шумом, в результате чего, как показано на рисунке 2.4, получается сигнал и демодулированная последовательность Задача декодера состоит в получении оценки исходной последовательности сообщения с помощью полученной последовательности Z и априорных знаний о процедуре кодирования.

Рисунок 2.4 - Кодирование/декодирование и модуляция/демодуляция в канале связи

Обычный сверточный кодер, показанный на рисунке 2.5, реализуется с kK-разрядным регистром сдвига и n сумматорами по модулю 2, где K -- длина кодового ограничения. Длина кодового ограничения -- это количество k-битовых сдвигов, после которых один информационный бит может повлиять на выходной сигнал кодера. В каждый момент времени на место первых k разрядов регистра перемещаются k новых бит; все биты в регистре смещаются на k разрядов вправо, и выходные данные n сумматоров последовательно дискретизируются, давая, в результате, биты кода. Затем эти симво лы кода используются модулятором для формирования сигналов, которые будут пере даны по каналу. Поскольку для каждой входной группы из к бит сообщения имеется n бит кода, степень кодирования равна k/n бит сообщения на бит кода, где k < n.

Рисунок 2.5 - Сверточный кодер с длиной кодового ограничения K и степенью кодирования k/n

Рассмотрим только наиболее часто используемые двоичные сверточные кодеры, для которых k - 1, т.е. те кодирующие устройства, в которых биты сооб щения сдвигаются по одному биту за раз, хотя обобщение на алфавиты более высоких порядков не вызывает никаких затруднений [2]. Для кодера с k = 1, за i-й момент времени бит сообщения , будет перемещен на место первого разряда регистра сдвига; все предыдущие биты в регистре будут смещены на один разряд вправо, а выход ной сигнал n сумматоров будет последовательно оцифрован и передан. Поскольку для каждого бита сообщения имеется n бит кода, степень кодирования равна 1/n. Имеющиеся в момент времени , n кодовых символов составляют i-е кодовое слово ветви, где (j - 1, 2, ..., n) -- это j-й кодовый символ, принадлежащий i-му кодовому слову ветви. Отметим, что для кодера со степенью кодирования 1/n, kK-разрядный регистр сдвига для простоты можно называть K-разрядным регистром, а длину кодового ограничения K, которая выражается в единицах разрядов k-кортежей, можно именовать длиной кодового ограничения в битах.

2.5.1 Представление сверточного кодера

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

2.5.2 Представление связи

При рассмотрении сверточных кодеров в качестве модели будем использовать сверточный кодер, показанный на рисунке 2.6. На этом рисунке изображен сверточный кодер (2, 1) с длиной кодового ограничения K = 3. В нем имеется n = 2 сумматора по модулю 2; следовательно, степень кодирования кода k/n равна 1/2. При каждом поступлении бит помещается в крайний левый разряд, а биты регистра смещаются на одну позицию вправо. Затем коммутатор на выходе дискретизирует выходы всех сумматоров по модулю 2 (т.е. сначала верхний сумматор, затем нижний), в результате чего формируются пары кодовых символов, образующих кодовое слово, связанное с только что поступившим битом. Это выполняется для каждого входного бита. Выбор связи между сумматорами и разрядами регистра влияет на характеристики кода. Всякое изменение в выборе связей приводит в результате к различным кодам.

В отличие от блочных кодов, имеющих фиксированную длину слова n, в сверточных кодах нет определенного размера блока. Однако с помощью периодического отбрасывания сверточным кодам часто принудительно придают блочную структуру. Это требует некоторого количества нулевых разрядов, присоединенных к концу входной последовательности данных, которые служат для очистки (или «промывки») регистра сдвига от бит данных. Поскольку добавленные нули не несут дополнительной информации, эффективная степень кодирования будет ниже k/n. Чтобы степень кодирования оставалась близкой к k/n, период отбрасывания чаще всего делают настолько большим, насколько это возможно.

Рисунок 2.6 - Сверточный кодер (степень кодирования 1/2, K - 3)

Один из способов реализации кодера заключается в определении n векторов связи, по одному на каждый из n сумматоров по модулю 2. Каждый вектор имеет размерность K и описывает связь регистра сдвига кодера с соответствующим сумматором по модулю 2. Единица на i-Й позиции вектора указывает на то, что соответствующий разряд в регистре сдвига связан с сумматором по модулю 2, а нуль в данной позиции указывает, что связи между разрядом и сумматором по модулю 2 не существует. Для кодера на рисунке 2.6 можно записать вектор связи для верхних связей, a -- для нижних.

Предположим теперь, что вектор сообщения m = 1 0 1 закодирован с использованием сверточного кода и кодера, показанного на рисунке 2.6. Введены три бита сообщения, по одному в момент времени , и , как показано на рисунке 2.7. Затем для очистки регистра в моменты времени t₄ и t₅ введены (К - 1) = 2 нуля, что в результате приводит к смещению конечного участка на всю длину регистра. Последовательность на выходе выглядит следующим образом: 1 1 1 0 0 0 1 0 1 1, где крайний левый символ представляет первую передачу. Для декодирования сообщения нужна полная последовательность на выходе (включающая кодовые символы). Для удаления со общения из кодера требуется на единицу меньше нулей, чем имеется разрядов в регистре, или К - 1 очищенных бит. В момент времени t₆ показан нулевой выход, это должно дать читателю возможность убедиться в том, что в момент времени t₅ регистр устанавливается в исходное состояние. Таким образом, в момент времени t₆ уже можно передавать новое сообщение.

2.5.3 Реакция кодера на импульсное возмущение

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

Рисунок 2.7 - Сверточное кодирование последовательности сообщения со степенью кодирования 1/2 кодером с К = 3.

Рис.

Последовательность на выходе при единице на входе называется откликом кодера на импульсное возмущение, или его импульсной характеристикой. Для входной последовательности m = 1 0 1 данные на выходе могут быть найдены путем суперпозиции или линейного сложения смещенных во времени входных "импульсов".

Рис.

Следует отметить, что эти данные на выходе такие же, как и на рис. 2.7, что указывает на линейность сверточных кодов -- точно так же как и в блочных кодах. Название сверточный кодер (convolutional encoder) возникло именно вследствие этого свойства генерации данных на выходе с помощью линейного сложения (или свертки) смещенных во времени импульсов последовательности на входе с импульс ной характеристикой кодера. Такие устройства часто описываются с помощью матричного генератора бесконечного порядка [2].

Отметим, что в рассмотренном выше примере входной последовательности из 3 бит и последовательности на выходе из 10 бит эффективная степень кодирования составляет k/n = 3/10, что значительно меньше величины 1/2, которую можно было бы ожидать, зная, что каждый бит данных на входе порождает пару канальных битов на выходе. Причина этого заключается в том, что финальные биты данных нужно про вести через кодер. Все канальные биты на выходе требуются в процессе декодирования. Если бы сообщение было длиннее, скажем 300 бит, последовательность кодовых слов на выходе содержала бы 640 бит и значение для степени кодирования кода 300/640 было бы значительно ближе к 1/2.

2.5.4 Полиномиальное представление

Иногда связи кодера описываются с помощью полиномиального генератора для описания реализации обратной связи регистра сдвига циклических кодов. Сверточный кодер можно представить в виде набора из n полиномиальных генераторов, по одному для каждого из n сумматоров по модулю 2. Каждый полином имеет порядок K - 1 или меньше и описывает связь кодирующего регистра сдвига с соответствующим сумматором по модулю 2, почти так же как и вектор связи. Коэффициенты возле каждого слагаемого поли нома порядка (К - 1) равны либо 1, либо 0, в зависимости от того, имеется ли связь между регистром сдвига и сумматором по модулю 2. Для кодера на рис 2.6 можно записать полиномиальный генератор для верхних связей и - для нижних.

Здесь слагаемое самого нижнего порядка в полиноме соответствует входному разряду регистра. Выходная последовательность находится следующим образом:

чередуется с

Прежде всего, выразим вектор сообщения m = 1 0 1 в виде полинома, т.е. . Для очистки регистра мы снова будем предполагать использование нулей, следующих за битами сообщения. Тогда выходящий полином U(X), или выходящая последовательность U кодера (рис. 2.6) для входного сообщения m может быть найдена следующим образом:

Рис.

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

2.5.5 Представление состояния и диаграмма состояний

Сверточный кодер принадлежит классу устройств, известных как конечный авто мат. Для сверточного кода со степенью кодирования 1/n состояние представлено содержимым K - 1 крайних правых разрядов (рис. 2.7). Знание состояния плюс знание следующих данных на входе является необходимым и достаточным условием для определения данных на выходе. Итак, пусть состояние кодера в момент времени , определяется как . i-я ветвь кодовых слов U, полностью определяется состоянием X, и введенными в настоящее время битами ; таким образом, состояние X, описывает предысторию кодера для определения данных на его выходе. Состояния кодера считаются Марковскими в том смысле, что вероятность нахождения в состоянии , определяемая всеми предыдущими состояниями, зависит только от самого последнего состояния , т.е. она равна .

Одним из способов представления простых кодирующих устройств является диаграмма состояния (state diagram); такое представление кодера, изображенного на рис. 2.6, показано на рис. 2.8. Состояния, показанные в рамках диаграммы, представляют собой возможное содержимое К - 1 крайних правых разрядов регистра, а пути между состояниями -- кодовые слова ветвей на выходе, являющиеся результатом переходов между такими состояниями. Состояния регистра выбраны следующими: а = 00, b = 10, с = 01 и d = 11; диаграмма, показанная на рис. 2.8, иллюстрирует все возможные смены состояний для кодера, показанного на рис. 2.6. Существует всего два исходящих из каждого состояния перехода, соответствующие двум возможным входным битам. Далее для каждого пути между со стояниями записано кодовое слово на выходе, связанное с переходами между со стояниями. При изображении путей, сплошной линией принято обозначать путь, связанный с нулевым входным битом, а пунктирной линией -- путь, связанный с единичным входным битом. Отметим, что за один переход невозможно перейти из данного состояния в любое произвольное. Так как за единицу времени перемещается только один бит, существует только два возможных перехода между состояниями, в которые регистр может переходить за время прохождения каждого бита.

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

2.5.6 Древовидные диаграммы

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

Древовидная диаграмма сверточного кодера, показанного на рис. 2.6, изображена на рис. 2.9. В каждый последующий момент прохождения входного бита процедура кодирования может быть описана с помощью перемещения по диаграмме слева направо, причем каждая ветвь дерева описывает кодовое слово на выходе. Правило ветвления для нахождения последовательности кодовых слов следующее: если входным битом является нуль, то он связывается со словом, которое находится путем перемещения в следующую (по направлению вверх) правую ветвь; если входной бит -- это единица, то кодовое слово находится путем перемещения в следующую (по направлению вниз) правую ветвь.

Предполагается, что первоначально кодер содержал одни нули. Диаграмма показывает, что если первым входным битом был нуль, то кодовым словом ветви на выходе будет 00, а если первым входным битом была единица, то кодовым словом на выходе будет 11. Аналогично, если первым входным битом была единица, а вторым -- нуль, на выходе вторым словом ветви будет 10. Если первым входным битом была единица и вторым входным битом была единица, вторым кодовым словом на выходе будет 01. Следуя этой процедуре, видим, что входная последовательность 110 11 представляется жирной линией, нарисованной на древовидной диаграмме (рис. 2.9). Этот путь соответствует выходной последовательности кодовых слов 1 1 0 1 0 1 0 0 0 1.

Добавленное измерение времени в древовидной диаграмме (по сравнению с диаграммой состояния) допускает динамическое описание кодера как функции конкретной входной последовательности. Однако при попытке описания с помощью древовидной диаграммы последовательности произвольной длины возникает проблема: число ответвлений растет как 2^L, где L -- это количество кодовых слов ветвей в последовательности.

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.6 Декодирование по методу максимального правдоподобия