636_Nosov_V.I._Seti_radiodostupa_CH.1_

каждое состояние, и исключении одного из них. Такие вычисления проводятся для каждого из 2К-1 состояний или узлов в момент времени ti ; затем декодер переходит к моменту времени ti+1 и процесс повторяется. В данный момент времени метрика выжившего пути для каждого состояния обозначается как метрика для этого состояния в этот момент времени. Первые несколько шагов в нашем примере декодирования будут следующими (рис. 5.10). Предположим, что последовательность входных данных m, кодовое слово U и полученная последовательность Z аналогичны показанным на рис. 5.8.

Допустим, что декодер знает верное исходное состояние решетки. (Это предположение не является необходимым, однако упрощает объяснения.) В момент времени t1 получены кодовые символы 11. Из состояния 00 можно перейти только в состояние 00 или 10, как показано на рис. 3.10, а. Переход между состояниями 00 10 имеет метрику ветви 0; переход между состояниями 00 00 — метрику ветви 2. В момент времени t2 из каждого состояния также может выходить только две ветви, как показано на рис. 5.10, б. Суммарная метрика этих ветвей обозначена как метрика состояний Гa, Гb, Гc и Гd соответствующих конечным состояниям. В момент времени t3 на рис. 5.10, в опять есть две ветви, выходящие из каждого состояния. В результате имеется два пути, входящих в каждое состояние, в момент времени t4. Один из путей, входящих в каждое состояние, может быть исключен, а точнее – это путь, имеющий большую суммарную метрику пути.

Если бы метрики двух входящих путей имели одинаковое значение, то путь, который будет исключаться, выбирался бы произвольно. Выживший путь в каждом состоянии показан на рис. 5.10, г. В этой точке процесса декодирования имеется только один выживший путь, который называется полной ветвью, между моментами времени t1 и t2. Следовательно, декодер теперь может решить, что между моментами t1 и t2 произошел переход 00 10. Поскольку переход вызывается единичным входным битом, на выходе декодера первым битом будет единица. Здесь легко можно проследить процесс декодирования выживших ветвей, поскольку ветви решетки показаны пунктирными линиями для входных нулей и сплошной линией для входных единиц. Заметим, что первый бит не декодируется, пока вычисление метрики пути не пройдет далее вглубь решетки. Для обычного декодера такая задержка декодирования может оказаться раз в пять больше длины кодового ограничения в битах.

На каждом следующем шаге процесса декодирования всегда будет два пути для каждого состояния; после сравнения метрик путей один из них будет исключен. Этот шаг в процессе декодирования показан на рис. 5.10, д. В момент t5 снова имеется по два входных пути для каждого состояния, и один путь из каждой пары подлежит исключению. Выжившие пути на момент t5 показаны на рис. 5.10, е. Заметим, что в нашем примере мы еще не можем принять решения относительно второго входного информационного бита, поскольку еще остается два пути, исходящих в момент t2 из состояния в узле

10.

171

			Метрики
			состояний
a = 00	t1	2 t2	Гa=2	a = 00	t1	2 t2	1 t3
		0				0	1

b = 10

Гb=0

b = 10

2

c = 01

0

d = 11

a = 00	t1	2	t2
			0
b = 10

c = 01

d = 11

а)

б)

1 t3	1 t4		a = 00	t1	t2	t3	t4
	1 1
1
					0		1
			b = 10
2		1			2		1
		2	c = 01
0	0	0			0		0
			d = 11				2
	2
	в)						г)

a = 00	t1	t2	t3	t4 1	t5
				1	1
		0		1
b = 10
			2	1	1
					0
c = 01

0

0

2

2

a = 00	t1	t2	t3	t4	t5
		0			1
b = 10
			2	1	1
c = 01					0
			0	0

Метрики

состояний

Гa=3

Гb=3

Гc=2

Гd=0

Гa=3

Гb=3

Гc=0

Гd=2

Гa=1

Гb=1

Гc=3

d = 11

2 0

				д)
a = 00	t1	t2	t3	t4	t5		1 t6
		0			1	1	1
b = 10					1		1
				1
			2
							2
					0
c = 01

	0	0		0	0
d = 11		2	0	2

ж)

d = 11	2	0	Гd=2

е)

a = 00	t1	t2	t3	t4	t5 1	t6	Гa=2
		0		1		1
b = 10							Гb=2
					1

c = 01	0		0	Гc=2
	0		0
d = 11	2	0		Гd=1

з)

Рис. 5.10 Выбор выживших путей: а) выживание на момент t2; б) выжившие на момент t3; в) сравнение метрик в момент t4; г) выжившие на момент t4; д) сравнение метрик в момент t5; е) выжившие на момент t5; ж) сравнение метрик в момент t6; з) выжившие на момент t6.

В момент времени t6 на рис. 5.10, ж снова можем видеть структуру сливающихся путей, а на рис. 5.10, з — выжившие пути на момент t6. Здесь же, на рис. 5.10, з, на выходе декодера в качестве второго декодированного

172

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

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

5.7 Реализация декодера

В контексте решетчатой диаграммы, показанной на рис. 5.8, переходы за один промежуток времени можно сгруппировать в 2 -1 непересекающиеся ячейки; каждая ячейка будет изображать четыре возможных перехода, причем v = K- 1 называется памятью кодера (encoder memory). Если К = 3, то = 2, и, следовательно, мы имеем 2 -1 = 2 ячейки. Эти ячейки показаны на рис. 5.11, где буквы a, b, с и d обозначают состояния в момент времени ti , а a', b', с' и d' – состояния в момент времени ti+1. Для каждого перехода изображена метрика ветви xy, индексы которой означают переход из состояния х в состояние у. Эти ячейки и соответствующие логические элементы, которые корректируют метрики coстояний {Гх}, где x означает конкретное расстояние состояния, представляют основные составляющие элементы декодера.

Процедура сложения, сравнения и выбора.

Вернемся к примеру двух ячеек с К = 3. На рис. 5.12 показан логический блок, соответствующий ячейке 1. Логическая схема осуществляет специальную операцию, которая называется сложение, сравнение и выбор (add- compare-select — ACS). Метрика состояния Гa' вычисляется путем прибавления метрики предыдущего состояния а, Гa, к метрике ветви aa' и метрики предыдущего состояния с, Гc, к метрике ветви ca'.

Это даст в результате две метрики путей в качестве кандидатов для новой метрики состояния Гa'. Оба кандидата сравниваются в логическом блоке, показанном на рис. 5.12. Наиболее правдоподобная из двух метрик путей (с наименьшим расстоянием) запоминается как новая метрика состояния Гa' для состояния а'. Также сохраняется новая история путей m€a для состояния а, где

m€a – история пути информации для данного состояния, дополненная

сведениями о выжившем пути.

На рис. 5.12 также показана логическая схема ACS для ячейки 1, которая дает новую метрику состояния Гь’ и новую историю состояния m€b' . Операция

173

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

		Ячейка 1
a	ti	aa´	ti+1	a´

ab ´

	Ячейка 2
ti	ti+1

c

c	a	´		b´	b
				´
			b
			c
							b
							c´
							bd´
					d	c	´

d		dd´
Рис. 5.11 Примеры ячеек декодера

c´

d´

Вид процедуры сложения, сравнения и выбора на решетке.

Рассмотрим тот же пример, которым мы воспользовались в этом разделе для описания декодирования на основе алгоритма Витерби. Последовательность сообщений имела вид m = 1 1 0 1 1, последовательность кодовых слов – U = 11 01 01 00 01, а принятая последовательность – Z = 11 01 01 10 01, т.е. в канале в седьмом символе произошла ошибка.

Решетчатая диаграмма декодирования, аналогичная показанной на рис. 5.8, изображена на рис. 5.13. Метрика ветви, которая описывает каждую ветвь, – это расстояние Хэмминга между принятым кодовым символом и соответствующим кодовым словом из решетки кодера. Еще на решетке (рис. 5.13) показаны значения каждого состояния х в каждый момент t2 – t6, метрика состояния которых обозначена Гx. Операция ACS выполняется после появления двух переходов, входящих в состояние, т.е. для момента t4 и более поздних. Например, в момент времени t4 значение метрики состояния для состояния а вычисляется суммированием метрики состояния Гa = 3 в момент t3 и метрики ветви aa’ = 1, что в итоге дает значение 4. В то же время к метрике состояния Гc = 2 в момент времени t3 прибавляется метрика ветви ca’ = 1, что дает значение 3. В ходе процедуры ACS происходит отбор наиболее правдоподобной метрики (с минимальным расстоянием), т.е. новой метрики состояния; поэтому для состояния а в момент t4

174

новой метрикой состояния будет Гa’ = 3. Отобранный путь изображен жирной линией, а путь, который был отброшен, показан тонкой линией.

Гa	Гc

aa´	ca´
	Сравнение
	m^a m^c
Выбор	Выбор
1 из 2	1 из 2
Гa’	m^a’

ab´	cb´
	Сравнение
	m^a m^c
Выбор	Выбор
1 из 2	1 из 2
Гb’	m^b’

К следующему логическому	К следующему логическому
элементу	элементу

Рис. 5.12 Логический блок, предназначенный для осуществления операции сложения, сравнения и выбора

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

Чтобы показать это, посмотрим на рис. 5.13 в момент t6. Видим, что значение метрики состояния, соответствующей минимальному расстоянию, равно 1. Отобранный путь можно проследить из состояния d обратно, к моменту t1 и убедиться, что декодированное сообщение совпадает с исходным, несмотря на наличии ошибки в принятой последовательности. Напомним, что пунктирные линии соответствуют двоичной единице, а сплошные – двоичному нулю.

5.8 Память путей и синхронизация

175

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

Z:	11		01	01	10	01
	t1	t2	t3	t4	t5	t6

a = 00	2	2	1
	0		1

b = 10	0

3

3

1	3	1	1
1	1	1	1

3

1

1

1

1	2
1	1
	2
	1

2

2

0

2

c = 01	2	0	3	0	2
	0		2

0

0

2

0

d = 11			0	2	2	1
			2	0		2
Декодированные	1	1	0	1		1
выходные данные

Метрика ветви

Г

Метрика пути

Рис. 5.13 Операции сложения, сравнения и выбора при декодировании по алгоритму Витерби

Для кода со степенью кодирования 1/n после каждого шага декодирования декодер держит в памяти набор из 2K-1 путей. С высокой степенью вероятности можно утверждать, что при значительном превышении существующей на данный момент глубины декодирования эти пути не будут взаимно непересекающимися [18, 20]. Все 2К-1 пути ведут к полной ветви, которая, в конце концов, разветвляется на разные состояния. Поэтому, если декодер сохраняет историю 2К-1 путей, самые первые биты на всех путях будут одинаковы. Следовательно, простой декодер имеет фиксированный объем истории путей и выдает самые ранние биты произвольного пути каждый раз, когда продвигается на один уровень вглубь решетки. Требуемый объем сохраняемых путей будет равен

u h 2K 1.

(5.11)

Здесь h — длина истории пути информационного бита на состояние. При уточнении, которое проводится для минимизации h, вместо самых ранних битов произвольных путей на выходе декодера используются самые ранние биты наиболее вероятных путей. Было показано [18], что значения h, равного 4 или 5 длинам кодового ограничения, достаточно, чтобы характеристики декодера были близки к оптимальным. Необходимый объем памяти и является основным ограничением при разработке декодеров, работающих

176

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

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

5.9 Свойства сверточных кодов

5.9.1 Пространственные характеристики сверточных кодов

Рассмотрим пространственные характеристики сверточных кодов в контексте простого кодера (рис. 5.2, а) и его решетчатой диаграммы (рис. 5.6). Мы хотим узнать расстояния между всеми возможными парами последовательностей кодовых слов. Как и в случае блочных кодов (см. раздел 4), нас интересует минимальное расстояние между всеми такими парами последовательностей кодовых слов в коде, поскольку минимальное расстояние связано с возможностями коррекции ошибок кода. Поскольку сверточный код является групповым или линейным, можно без потери общности просто найти минимальное расстояние между последовательностью кодовых слов и нулевой последовательностью. Другими словами, для линейного кода данное контрольное сообщение окажется точно таким же "хорошим", как и любое другое. Так почему бы не взять то сообщение, которое легко проследить, а именно нулевую последовательность? Допустим, что на вход передана нулевая последовательность; следовательно, нас интересует такой путь, который начинается и заканчивается в состоянии 00 и не возвращается к состоянию 00 нигде внутри пути. Всякий раз, когда расстояние любых других путей, которые сливаются с состоянием а = 00 в момент ti, окажется меньше расстояния нулевого пути, вплоть до момента ti, будет появляться ошибка, вызывая в процессе декодирования отбрасывание нулевого пути. Иными словами, при нулевой передаче ошибка возникает всегда, когда не выживает нулевой путь.

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

177

обнаружения ошибки достаточно лишь того, чтобы пути расходились? В принципе, достаточно, но если ошибка характеризуется только расхождением, то декодер, начиная с этой точки, будет выдавать вместо оставшегося сообщения сплошной "мусор". Мы хотим выразить возможности декодера через число обычно появляющихся ошибок, т.е. хотим узнать "самый легкий" для декодера способ сделать ошибку. Минимальное расстояние для такой ошибки можно найти, полностью изучив все пути из состояния 00 в состояние 00. Итак, давайте сначала заново начертим решетчатую диаграмму, как показано на рис. 5.14, и обозначим каждую ветвь не символом кодового слова, а ее расстоянием Хэмминга от нулевого кодового слова. Расстояние Хэмминга между двумя последовательностями разной длины можно получить путем их сравнивания, т.е. прибавив к началу более короткой последовательности нужное количество нулей. Рассмотрим все пути, которые расходятся из нулевого пути и затем в какой-то момент снова сливаются в произвольном узле. Из диаграммы на рис. 5.14 можно получить расстояние этих путей до нулевого пути. Итак, на расстоянии 5 от нулевого пути имеется один путь; этот путь отходит от нулевого в момент t1 и сливается с ним в момент t4. Точно так же имеется два пути с расстоянием 6, один отходит в момент t1 и сливается в момент t5, а другой отходит в момент t1 и сливается в момент t6 и т.д. Также можно видеть (по пунктирным и сплошным линиям на диаграмме), что входными битами для расстояния 5 будут 100; от нулевой входной последовательности эта последовательность отличается только одним битом. Точно так же входные биты для путей с расстоянием 6 будут 1100 и 10100; каждая из этих последовательностей отличается от нулевого пути в двух местах, минимальная длина пути из числа расходящихся, а затем сливающихся путей называется минимальным свободным расстоянием (minimum free distance), или просто свободным расстоянием (free distance).

Его можно видеть на рис. 5.14, где он показан жирной линией. Для оценки возможностей кода по коррекции ошибок, мы повторно приведем уравнение из раздела 4 с заменой минимального расстояния dmin на свободное расстояние df

t	d f	1	.	(5.12)
	2
Здесь x означает наибольшее целое,		не большее х. Положив df = 5, можно

видеть, что код, описываемый кодером на рис. 5.2,а может исправить две любые ошибки канала.

Решетчатая диаграмма представляет собой "правила игры". Она является как бы символическим описанием всех возможных переходов и соответствующих начальных и конечных состояний, ассоциируемых с конкретным конечным автоматом. Эта диаграмма позволяет взглянуть глубже на выгоды (эффективность кодирования), которые дает применение кодирования с коррекцией ошибок, Взглянем на рис. 5.14 и на возможные ошибочные расхождения и слияния путей. Из рисунка видно, что декодер не может сделать ошибку произвольным образом. Ошибочный путь должен

178

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

Состояние

t1

a = 00

0

t2

0

t3

0

t4

0

t5

0

t6

2

2

2

2

2

b = 10	2		2		2
		0		0		0
1
		1		1		1
c = 01
1	1	1	1	1	1	1
d = 11	1		1		1

Рис. 5.14 Решетчатая диаграмма с обозначенными расстояниями от нулевого пути

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

Хотя на рис. 5.14 представлен способ прямого вычисления свободного расстояния, для него можно получить более строгое аналитическое выражение, воспользовавшись для этого диаграммой состояний, изображенной на рис. 5.4. Для начала обозначим ветви диаграммы состояний как D0= 1, D1 или D2, как это показано на рис. 5.15, где показатель D означает расстояние Хэмминга между кодовым словом этой ветви и нулевой ветвью. Петлю в узле а можно убрать, поскольку она не дает никакого вклада в пространственные характеристики последовательности кодовых слов относительно нулевой последовательности. Более того, узел а можно разбить на два узла (обозначим их а и е), один из них представляет вход, а другой – выход диаграммы состояний.

Все пути, начинающиеся из состояния а = 00 и заканчивающиеся в состоянии е = 00, можно проследить на модифицированной диаграмме состояний, показанной на рис. 5.15. Передаточную функцию пути abce (который начинается и заканчивается в состоянии 00) можно рассчитать через неопределенный "заполнитель" D как D2DD2 = D5. Степень D – общее число единиц на пути, а значит, расстояние Хэмминга до нулевого пути. Точно так же пути abdсе и аbсbсе имеют передаточную функцию D6 и, соответственно, расстояние Хэмминга, равное 6, до нулевого пути.

179

00

D

a = 00	11	b = 10		10			c = 01	11		e = 00
	D2			D				D2
		D 01			01 D
				d = 11
		10			D

Рис. 5.15 Диаграмма состояний с обозначенными расстояниями до нулевого пути

Теперь уравнения состояния можем записать следующим образом

X	b	D2 X	a	X	,
				c

X c DXb DX d ,

(5.13)

X d DXb DX d ,

X	e	D2 X	.
		c

Здесь Ха ,..., Хе являются фиктивными переменными неполных путей между промежуточными узлами. Передаточную функцию кода, T(D), которую иногда называют производящей функцией кода, можно записать как T(D) = Xc / Xa. Решение уравнений состояния (5.13) имеет следующий вид

		D5
T (D)			D5	2D6	4D7 ... 2l Dl 5 ...	(5.14)
1		2D

Передаточная функция этого кода показывает, что имеется один путь с расстоянием 5 до нулевого вектора, два пути – с расстоянием 6, четыре – с расстоянием 7. В общем случае существуют 2l пути с расстоянием l + 5 до нулевого вектора, причем l = 0, 1, 2, ... . Свободное расстояние df кода является весовым коэффициентом Хэмминга слагаемого, имеющего наименьший порядок в разложении T(D). В данном случае df = 5. Для оценки пространственных характеристик при большой длине кодового ограничения

180