Тема №7: Сверточные коды

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

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

Кодирующее устройство сверточного кода может быть реализовано с помощью K- разрядного сдвигающего регистра и сумматоров по модулю 2.

На рисунке представлены примеры кодеров разделимого и неразделимого кодов соответственно.

Разделимый код

Неразделимый код

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

Сверточный код с параметрами n, k, K обозначается как (n, k, K).

Отношение , как и в блочном кодере, называется относительной скоростью кода. В рассмотренных примерах .

K называют памятью кодера.

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

В случае разделимого кода первым из выходных символов всегда будет первый информационный символ.

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

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

- для первого символа выходной пары

- для второго символа выходной пары

Здесь переменная х играет роль “указателя сдвига” и означает сдвиг по ячейкам регистра на число позиций, соответствующих степени этого указателя относительно нулевого разряда первой ячейки, причем слагаемое 1x⁰ представляется просто “1”, соответствующей символу в первой ячейке регистра, т.е. в первом разряде.

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

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

Такая диаграмма для кодера неразделимого кода имеет вид (для кода K=3):

Диаграмма состоит из ветвей (ребер). Число узлов в ней равно (K-число ячеек в регистре сдвига). Каждому из четырех узлов соответствует содержание двух левых ячеек регистра. Это двоичное число называют состоянием кодера. Ветви, соединяющие узлы, характеризуют переход из одного состояния кодера в другое. Число ветвей, исходящих из каждого узла, равно основанию кода. Ветвь в виде штриховой линии соответствует входному информационному символу “1”, а ветвь в виде сплошной линии – символу “0”. Над ветвью записываются формируемые выходные символы. Таким образом, каждой входной информационной последовательности соответствует некоторый путь на решетчатой диаграмме.

Например, входная последовательность 101100 дает выходную последовательность 110100101011 (см. решетчатую диаграмму, приведенную ранее).

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

Для нашего кода (2,1,3) состояния кодера (две левые ячейки регистра) можно обозначить S₀=00; S₁=10; S₂=01; S₃=11, тогда с учетом двоичного характера смены состояний и заданного алгоритма формирования выходной пары символов получим:

Дробь означает алгоритм работы кодера:

Если информационную последовательность “протащить” по состояниям этой диаграммы, можно получить выходную комбинацию символов:

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

Каждой кодовой комбинации соответствует свой путь на диаграмме состояний (сетевой диаграмме), поэтому ясно, что чем больше различий между путями, тем легче распознать истинное кодовое слово, тем меньше вероятность ошибки декодирования.

Как измерять эти различия между путями по диаграмме состояний?

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

Расстояние между кодовыми словами или между путями по диаграмме состояний можно также искать в метрике Хемминга. При этом будем считать, что кодирование начинается и заканчивается в нулевом состоянии.

Для анализа введем понятие весовой функции пути:

,

где I,D,J - абстрактные переменные с показателями:

i- вес Хемминга информационной последовательности,

d- вес Хемминга кодовой последовательности,

j – число переходов (смены состояний), осуществленных на этом пути.

На основе этого понятия весовой функции пути модифицируем диаграмму состояний для примера, рассмотренного ранее.

		IJ

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

Тогда весовая функция пути для рассмотренного примера равна:

S₀→S₂→S₁→S₂→S₃→S₁→S₀ T= ID²J· DJ· IJ· IDJ· DJ· D²J= I³ D⁷ J⁶

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

Сверточный код считается оптимальным, если при заданной скорости кода и памяти кодера, он имеет максимальное свободное расстояние .

→ код оптимальный

Существует довольно много оптимальных кодов, но для их построения не существует аналитических методов. Оптимальные сверточные коды находятся путем компьютерного моделирования.

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

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

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

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

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

Однако при большой длине информационной последовательности N, такой метод практически нереализуем, поскольку приходится перебирать 2^N возможных кодовых последовательностей. Существенное упрощение процедуры декодирования по методу максимального правдоподобия предложил Витерби. Характерной особенностью метода Витерби является то, что при декодировании запоминаются и анализируются только 2^k-1 наиболее правдоподобных путей, т.е. количество путей определяется числом узлов в сечении сетевой диаграммы или числом состояний в диаграмме состояний.

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

Наиболее правдоподобным считается путь с наименьшей метрикой.

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

Таким образом, для принятой кодовой комбинации 11010010 (на первых четырех тактах) получим информационную комбинацию 1011, которая соответствует переданной.

Однако, первый информационный символ “выдается” на выходе декодера только на том шаге, когда он будет одинаков для всех состояний (узлов), т.е. при декодировании сверточного кода имеет место задержка.

Обнаружение и исправление ошибок.

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

Таким образом, при паре символов в выходном блоке сверточный код будет способен обнаруживать однократные ошибки, так как выполняется условие , при s=1, d=2.

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

Чтобы сверточный код обладал способностью исправлять ошибки, необходимо выполнить известное условие для блоков выходных символов: , т.е. для t=1, d≥3. Следовательно, количество символов в выходном блоке сверточного кода на каждом такте должно быть не менее трех. Тогда в каждом блоке принятой кодовой комбинации будет исправляться однократная ошибка, а метрика найденного пути будет указывать общее число ошибок, обнаруженных во всех принятых блоках кодовой последовательности.

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