52

2. Сведения из теории

2.1 Кодирование

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

n выходных битов

a→b(1)b(2)b(3)…b(n)	, n>1 *.
*Выходное кодовое слово b(1)b(2) b(3)…b(n)	удобно интерпретировать в виде числа
на отрезке [0,2n−1 ] .

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

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

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

Рассмотрим сверточный код с соответствием a→b(1)b(2) , согласно которому на один входной бит приходится два выходных. В связи с этим, скорость кодирования такого кода равна ½. Возьмем, например, два следующих порождающих полинома

G1 (x)=1 , G2 (x)=1+x .	(14)
Последовательности входных битов ai	поставим в соответствие
полином3

3 Математически удобно индекс суммирования ничем не ограничивать

(ячейка памяти),

53

A( x)=∑ai xi ,

i

где символом обозначено множество целых чисел.

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

B(1)(x)=A (x)G1 (x)=A (x) ,						(15)
B(2)(x)=A (x)G2 (x)= A(x)+x A( x)=∑(ai+ai−1) xi .
					i
На основании (15) определим правило работы кодирующего устройства
(кодера) во временной области
b(1)=a ,		b(2)=a +a		i−1	.
i	i	i	i

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

Если для изучаемого сверточного кода сконструировать

порождающую матрицу, которая есть у любого линейного блочного кода, то окажется, что она будет бесконечной

		(				…		…					)
			1	1	0	1		0		0	0	0
(…b0(1)b0(2)b1(1)b1(2)…)=(…a0 a1	…)	…	0 0		1 1		0		1		0	0	…	,
			0	0	0	0		1		1	0	1
			0	0	0	0		0		0	1	1

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

изображена на рис. 14. Блок MUX является мультиплексором, выходные биты которого являются результатом чередования входных. Блок x — это триггер хранящий на своем выходе предыдущий входной бит

4 Отсюда и название изучаемых кодов — сверточные

ai−1

54

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

0+0=0, 0+1=1, 1+0=1, 1+1=0 .

Выходное		слово	кодера
однозначно	определяется		текущим
входным	битом	и	набором
Рисунок 14: Схема сверточного кодера ½ предыдущих,	хранящихся в		регистре
сдвига. Предыдущие биты			образуют

вектор состояния кодера, который удобно записывать в виде соответствующего десятичного числа. В рассматриваемом примере вектор состояния состоит из единственного бита ai−1 , которому можно поставить в соответствие два числа — 0 и 1.

Поясним принцип построения диаграммы состояний на примере рассматриваемого сверточного кода.

Общепринято, что в начальный момент времени кодер находится в нулевом состоянии. Если при этом на вход поступил бит 0, то на выходе будет кодовое слово 00. В момент прихода

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

00, которое указано над линией). Число на конце стрелки указывает на будущее состояние кодера.

Определим ветку, если на вход поступил бит 1, а кодер при этом находится в состоянии 0. Очевидно, что выходное слово будет равно 11, а будущее состояние — 1. В данном случае будущее

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

55

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

Осталось определить две ветки для единичного начального состояния: а) пришел 0, на выходе 01, будущее состояние — 0; б) пришла 1, на выходе 10, будущее состояние — 1.

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

Если кодер переходит в исходное состояние, например, из 1 в 1, то получается петля (цикл). К такому циклу приводит кодирование последовательности из всех единиц, что в установившемся режиме даст

Рисунок 15: Диаграмма периодическую выходную последовательность

состояний сверточного кодера ½

кодовых слов (иногда кодовые слова называют

кодовыми символами)

...10 10 10....

Процесс кодирования по диаграмме состояний очень прост и нагляден. Для начала подадим на вход кодера дельта-последовательность

δn=100…0… ,

отклик на которую является импульсной характеристикой (ИХ) hn=1101 00…00… .

Два первых ненулевых слова (11 и 01) ИХ говорят о наличии у кода памяти (один входной бит дает два кодовых символа). Индекс n в ИХ hn

отвечает за пару битов (за кодовое слово). Избыточность кода равна 50%, так как на один входной бит приходится два выходных.

Теперь рассмотрим более сложную входную последовательность a=110100…0… ,

56

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

b=1110 01 11010000…00 … .

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

a=1101=1000+0100+0001=δn +δn−1+δn−3 ,

b=hn +hn−1 +hn−3=(1101 00 00 00…)+(00 1101 00 00…)+(00 00 00 1101…)= .

=(1110 01 1101…)

Не забываем про суммирование коэффициентов по модулю два.

Изобразить схему сверточного кодера с генераторными

полиномами G1 (x)=1 , G2 (x)=1+x+x2 , а также диаграмму состояний кода.

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

5 Это следует из равенства: A (x )[B(x)+C (x)]= A(x)B(x)+B(x)C (x)