636_Nosov_V.I._Seti_radiodostupa_CH.1_

m = 101000

Время

u1

t1			1	0	0

u2

u1

t2			0	1	0

u2

u1

t3			1	0	1

u2

u1

t4			0	1	0

u2

u1

t5			0	0	1

u2

u1

t6			0	0	0

u2

Выход

u1	u2
1	1

1 0

00

10

1 1

0 0

Рис. 5.3 Процесс сверточного кодирования сообщения m кодером (2, 1, 3)

151

Предположим теперь, что вектор сообщения m = 1 0 1 0 0 0 закодирован с использованием сверточного кода и кодера, показанного на рис. 5.2, а. Введены шесть бит сообщения, по одному в моменты времени t1 ,

– t6 , как показано на рисунке 5.3. Затем для очистки регистра в моменты времени t4 и t5 введены (К - 1) = 2 нуля, что в результате приводит к смещению конечного участка на всю длину регистра. Последовательность на выходе выглядит следующим образом: 11 1 0 0 0 1 0 1 1 00, где крайний левый символ представляет первую передачу.

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

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

g ( X )		1	X X 2
1
g	( X )	1	X 2
2

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

U(X ) m(X )g1(X ) чередуется с m(X )g2 (X ).

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

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

152

1 Xi ).

m( X )g ( X )			(1	X 2 )(1	X	X 2 )	1	X X 3	X 4
1
m( X )g		( X )	(1	X 2 )(1	X 2 ) 1		X 4
	2
m( X )g ( X ) 1				X		0 X 2		X 3	X 4	0X 5
1
m( X )g		( X ) 1		0 X		0 X 2		0 X 3	X 4	0X 5
	2
U ( X )			(1,1) (1,0) X			(0,0) X 2		(1,0) X 3	(1,1) X 4	(0,0) X 5
U			11	10		00		10	11	00

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

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

ограничиваются	прошлыми состояниями. Для сверточного кода	со
скоростью кодирования 1/п состояние представлено содержимым К -		1

крайних правых разрядов (рис. 5.3). Знание состояния плюс знание следующих данных на входе является необходимым и достаточным условием для определения данных на выходе.

Итак, пусть состояние кодера в момент времени t1 , определяется как Xi mi 1,mi 2,...,mi K 1. i-я ветвь кодовых слов U, полностью опре-

деляется состоянием Xi и введенными в настоящее время битами mi . Таким образом, состояние Xi описывает предысторию кодера для определения данных на его выходе. Состояния кодера считаются Марковскими в том смысле, что вероятность P(Xi 1 Xi ,..., X0 ) нахождения в состоянии Xi + 1,

определяемая всеми предыдущими состояниями, зависит только от самого последнего состояния Хi , т.е. она равна P(Xi

Одним из способов представления простых кодирующих устройств является диаграмма состояния (state diagram). Представление кодера, изображенного на рис. 5.2, а, в виде диаграммы состояний показано на рис. 5.4. Состояния, показанные в рамках диаграммы, представляют собой возможное содержимое К - 1 крайних правых разрядов регистра, а пути между состояниями – кодовые слова ветвей на выходе, являющиеся результатом переходов между такими состояниями. Состояния регистра выбраны

153

следующими: а = 00, b = 10, с = 01 и d = 11. Диаграмма, показанная на рис. 5.4, иллюстрирует все возможные смены состояний для кодера, показанного на рис. 5.2, а. Существует всего два исходящих из каждого состояния перехода, соответствующие двум возможным входным битам. Далее для каждого пути между состояниями записано кодовое слово на выходе, связанное с переходами между состояниями.

00

			a = 00				Выходное слово
	11							кодера
				11
			00
	b = 10				c = 01			Состояние кодера
			10
	01			01
			d = 11			Условные обозначения

		Входной бит 0
10		Входной бит 1

Рис. 5.4 Диаграмма состояний сверточного кодера (2, 1, 3)

При изображении путей, сплошной линией принято обозначать путь, связанный с нулевым входным битом, а пунктирной линией – путь, связанный с единичным входным битом. Отметим, что за один переход невозможно перейти из данного состояния в любое произвольное. Так как за единицу времени перемещается только один бит, существует только два возможных перехода между состояниями, в которые регистр может переходить за время прохождения каждого бита. Например, если состояние кодера — 00, при следующем смещении возможно возникновение только состояний 00 или 10.

Рассмотрим диаграмму состояний сверточного кодера (3, 2, 2), схема которого представлена на рис. 5.2, б. Первые два входных бита могут быть 00, 01, 10, 11, а соответсвующие выходные биты – 000, 010, 111, 101. Когда следующая пара входных бит, входит в кодер, первая пара передвигается в следующую ячейку. Соответствующие выходные биты зависят от пары битов переместившихся во вторую ячейку и новой пары входных битов. Диаграмма состояний для этого кодера приведена на рис. 5.4.1.

154

						100
													Выходное слово
						b = 00
														кодера
010												001
110									111
		111						001
000	a = 00											c = 01		010
		101
011					011				100					Состояние кодера
101												000
						d = 00
						110

Рис. 5.4.1 Диаграмма состояний сверточного кодера (3, 2, 2)

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

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

Предполагается, что первоначально кодер содержал одни нули. Диаграмма показывает, что если первым входным битом был нуль, то кодовым словом ветви на выходе будет 00, а если первым входным битом была единица, то кодовым словом на выходе будет 11. Аналогично, если первым входным битом была единица, а вторым – нуль, на выходе вторым словом ветви будет 10.

Если первым входным битом была единица и вторым входным битом была единица, вторым кодовым словом на выходе будет 01. Следуя этой

155

процедуре, видим, что входная последовательность 1 1 0 1 1 представляется жирной линией, нарисованной на древовидной диаграмме (рис. 5.5). Этот путь соответствует выходной последовательности кодовых слов 1 1 0 1 0 1 0 0 0 1 .

								00		a
						00		a	11	b
				00		a
Ветвь кодовых								10		c
							11	b
		слов							01	d
	00			a
								11		a
						10		c	00	b
					11	b
								01		c
0		a					01	d	10	d
								00		a
1
						11		a
									11	b
				10		c
								10		c
			11	b			00	b	01	d
								11		a
						01		c		b
					01	d			00
								01		c
							10	d	10	d
		t1		t2		t3		t4		t5

11

10

01

11

00

01

10

00

11

10

01

11

00

01

10

00

11

10

01

11

00

01

10

00

11

10

01

11

00

01

10

Рис. 5.5 Древовидное представление сверточного кодера (2, 1, 3)

156

Древовидная диаграмма сверточного кодера (3, 2, 2) (рис. 5.2, б) представлена на рис. 5.5.1.

000 a

010

000 b

(00)111

a c

101

d

110

a

100

010b

(01)001

b c

		011
		d
a		101
		a

111

111b

(10)010

c c

000

d

011

a

001

101b

(11)100

d c

110

d

t1

t2

t3

Рис. 5.5.1 Древовидное представление сверточного кодера (3, 2, 2)

157

Эта диаграмма имеет четыре ветви на узел, соответствующие четырем возможным парам входных символов. Поскольку кодовое ограничение кодера K = 2, дерево начинает повторяться после второго шага. Как показано на рис. 5.5.1. все ветви, исходящие из узла

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

5.4 Решетчатая диаграмма

Исследование древовидной диаграммы на рис. 5.5 показывает, что в этом примере после третьего ветвления в момент времени t4 структура повторяется (в общем случае древовидная структура повторяется после К ответвлений, где К – длина кодового ограничения). Пометим каждый узел в дереве (рис. 5.5), ставя в соответствие четыре возможных состояния в регистре сдвига: а =00, b = 10, с = 01 и d = 11. Первое ветвление древовидной структуры в момент времени t1 дает пару узлов, помеченных как а и b. При каждом последующем ветвлении количество узлов удваивается. Второе ветвление в момент времени t2 дает в результате четыре узла, помеченных как а, b, с и d. После третьего ветвления всего имеется восемь узлов: два – а, два – b, два – с и два – d.

Можно видеть, что все ветви выходят из двух узлов одного и того же состояния, образуя идентичные ветви последовательностей кодовых слов. В этот момент дерево делится на идентичные верхнюю и нижнюю части. Смысл этого становится яснее после рассмотрения кодера, изображенного на рис. 3.2а. Когда четвертый входной бит, входит в кодер слева, первый входной бит справа выбрасывается и больше не влияет на кодовые слова на выходе. Следовательно, входные последовательности 1 0 0 x y... и 0 0 0 х у..., где крайний левый бит является самым ранним, после (K = 3)-го ветвления генерируют одинаковые кодовые слова ветвей. Это означает, что любые состояния, имеющие одинаковую метку в один и тот же момент ti можно соединить, поскольку все последующие пути будут неразличимы. Если мы проделаем это для древовидной структуры, показанной на рис. 5.5, получим иную диаграмму, называемую решетчатой. Решетчатая диаграмма, которая использует повторяющуюся структуру, дает более удобное описание работы кодера, по сравнению с древовидной диаграммой. Решетчатая диаграмма для сверточного кодера, изображенного на рис. 5.2,а показана на рис, 5.6.

При изображении решетчатой диаграммы мы воспользовались теми же условными обозначениями, что и для диаграммы состояния: сплошная линия обозначает выходные данные, генерируемые входным нулевым битом, а пунктирная – выходные данные, генерируемые входным единичным битом. Узлы решетки представляют состояния кодера; первый ряд узлов соответствует состоянию а = 00, второй и последующие – состояниям b = 10, с =01 и d = 11.

158

Состояние

t1

a = 00

00	t2	00	t3	00	t4	00	t5	00	t6
11		11		11		11		11

b = 10		11		11		11		Ветвь
			00		00		00
								кодового
10								слова
			10		10		10
c = 01
01		01	01	01	01	01	01
d = 11		10		10		10
Условные		Входной бит 0					Входной бит 1
обозначения:

Рис. 5.6 Решетчатая диаграмма сверточного кодера (2, 1, 3)

Вкаждый момент времени для представления 2К-1 возможных состояний кодера решетка требует 2К-1 узлов. В нашем примере после достижения глубины

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

Всоответствии с древовидной диаграммой, входная последовательность данных 1 1 0 1 1 представляется жирной линией нарисованной на решетчатой диаграмме рис. 3.6. Этот путь кодера соответствует выходной последовательности 11 01 01 00 01.

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

Один столбец временного интервала сформировавшейся решетчатой структуры кодирования полностью определяет код. Несколько столбцов показаны исключительно для визуализации последовательности кодовых символов как функции времени. Состояние сверточного кодера представлено содержанием крайних правых К - 1 разрядов в регистре кодера. Некоторые авторы описывают состояние с помощью крайних левых К - 1 разрядов. Какое описание правильно? Они оба верны. Каждый переход имеет начальное и конечное состояние. Крайние правые К - 1 разрядов описывают начальное состояние для текущих входных данных, которые находятся в крайнем левом разряде (степень кодирования предполагается равной 1/n).

159

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

Таким образом, мы запускаем биты в моменты времени t1 , t2 , ..., tN и интересуемся метрикой состояния в моменты времени t1 , t2 , ..., tN+1. Здесь использовано следующее условие: текущий бит располагается в крайнем левом разряде, а крайние правые К-1 разрядов стартуют из состояния со всеми нулями. Этот момент времени обозначим как начальное время, t1. Время завершения последнего перехода обозначим как время прекращения работы,

tN+1.

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

На рис. 5.6.1 представлена решетчатая диаграмма для сверточного кодера

(3, 2, 2)

t1	000	t2	000	t3	000	t4	000	t5
a						010
			010		010
	010
		101		101		111
			111		111
						101
				110
	111	110				110
b		100		100		100
			001
		011		001		001
				011		011
	101				000
		101 000		101		101111
				111
c		010		010		010
		000		000		000
		011	001	011 001		011
			100		100	001
						100
d			110		110		110

Рис. 5.6.1 Решетчатая диаграмма декодера сверточного кода (3, 2, 2)

5.5 Декодирование сверточного кода

160