636_Nosov_V.I._Seti_radiodostupa_CH.1_

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

С помощью передаточной функции кода можно получить более подробную информацию, чем при использовании лишь расстояния между различными путями. В каждую ветвь диаграммы состояний введем множитель L так, чтобы показатель L мог служить счетчиком ветвей в любом пути из состояния а = 00 в состояние е = 00.

Более того, мы можем ввести множитель N во все ветви переходов, порожденных входной двоичной единицей. Таким образом, после прохождения ветви суммарный множитель N возрастает на единицу, только если этот переход ветви вызван входной битовой единицей. Для сверточного кода, приведенного на рис. 5.2,а на перестроенной диаграмме состояний (рис. 5.16) показаны дополнительные множители L и N. Уравнения (3.13) теперь можно переписать следующим образом

Xb D2 LNX a LNX c ,

X c DLXb DLX d ,

(5.15)

X d DLNXb DLNX d ,

X e D2 LX c .

Передаточная функция кода такой доработанной диаграммы состояний будет следующей

	T (D, L, N )		D5 L3 N
		1 DL(1 L)N
		(5.16)
		D5 L3 N D6 L4 (1 L)N 2 D7 L5 (1 L2 )N 3 ... Dl 5Ll 3nl 1 ...

Таким образом, мы можем проверить некоторые свойства путей, показанные на рис. 5.14. Существует один путь с расстоянием 5 и длиной 3, который отличается от нулевого пути одним входным битом. Имеется два пути с расстоянием 6, один из них имеет длину 4, другой – длину 5, и оба отличаются от нулевого пути двумя входными битами. Также есть пути с расстоянием 7, из которых один имеет длину 5, два - длину 6 и один – длину 7; все четыре пути соответствуют входной последовательности, которая отличается от нулевого пути тремя входными битами. Следовательно, если нулевой путь является правильным и шум приводит к тому, что мы выбираем один из неправильных путей с расстоянием 7, то в итоге получится три битовые ошибки.

Возможности сверточного кода в коррекции ошибок

В главе 4 при изучении блочных кодов говорилось, что способность кода к коррекции ошибок, t, представляет собой количество ошибочных кодовых

181

символов, которые можно исправить в каждом блоке кода путем декодирования по методу максимального правдоподобия.

00

LN

a = 00	11	b = 10		10			c = 01	11		e = 00
	D2LN			DL				D2L
		DLN 01			01 DL
				d = 11
		10			DLN

Рис. 5.16 Диаграмма состояний с обозначением расстояния, длины и числа входных единиц

В то же время при декодировании сверточных кодов способность кода к коррекции ошибок нельзя сформулировать так лаконично. Из уравнения (5.12) можно сказать, что при декодировании по принципу максимального правдоподобия код способен исправить t ошибок в пределах нескольких длин кодового ограничения, причем "несколько" – это где-то от 3 до 5. Точное значение длины зависит от распределения ошибок. Для конкретного кода и модели ошибки длину можно ограничить с использованием методов передаточной функции кода.

5.10 Систематические и несистематические сверточные коды

Систематический сверточный код – это код, в котором входные данные фигурируют как часть выходного кодового слова, соответствующего этим входным данным. На рис. 5.17 показан двоичный систематический кодер со скоростью кодирования 1/2 и К = 3. Для линейных блочных кодов любой несистематический код можно преобразовать в систематический с такими же пространственными характеристиками блоков. При использовании сверточных кодов это не так. Причина в том, что сверточные коды сильно зависят от свободного расстояния. При построении сверточного кода в систематической форме при данной длине кодового ограничения и степени кодирования максимально возможное значение свободного расстояния снижается.

182

В табл. 5.1 показан максимальный просвет при степени кодирования 1/2 для систематического и несистематического кодов с К от 2 до 8. При большой длине кодового ограничения результаты отличаются еще сильнее.

Вход

Выход

1 2 3

а)

Рис. 5.17 Систематический сверточный кодер (степень кодирования ½, К = 3)

Таблица 5.1. Сравнение систематического и несистематического свободных расстояний, степень кодирования ½

Длина кодового ограничения	Свободное расстояние	Свободное расстояние
	систематического кода	несистематического кода
2	3	3
3	4	5
4	4	6
5	5	7
6	6	8
7	6	10
8	7	10

Распространение катастрофических ошибок в сверточных кодах.

Катастрофическая ошибка возникает, когда конечное число ошибок в кодовых символах вызывает бесконечное число битовых ошибок в декодированных данных. Условием распространения катастрофических ошибок для кода со степенью кодирования 1/2 , реализованного на полиномиальных генераторах описанных в разделе 3.3.1.1, будет наличие у генераторов общего полиномиального множителя (степени не менее единицы). Например, если взять несистематический кодер со скоростью кодирования 1/2, величиной кодового ограничения К = 3 со старшим полиномом g1(x) и младшим – g2(x) (см. уравнение (5.1))

183

g1 (x) 1 X

(5.17)

g2 (x) 1 X 2.

Генераторы g1(x) и g2(x) имеют общий полиномиальный множитель 1+Х , поскольку

1 X 2 (1 X )(1 X ).

Следовательно, в таком кодере может происходить распространение катастрофической ошибки.

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

5.11 Наиболее известные сверточные коды

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

Затем при данном свободном расстоянии df минимизируется число путей или число ошибочных битов данных, которые представляют путь. Процедуру выбора можно усовершенствовать, рассматривая количество путей или ошибочных битов при df+l, df + 2 и т.д., пока не останется только один код или класс кодов. Список наиболее известных кодов со скоростью кодирования 1/2 при К, равном от 3 до 9, и со степенью кодирования 1/3 при К, равном от 3 до 8, соответствующих этому критерию приводится в табл. 5.2. Векторы связи в этой таблице представляют наличие или отсутствие (1 или 0) соединения между соответствующими регистрами сверточного кодера, причем крайний левый элемент соответствует крайнему левому разряду регистра кодера. Интересно, что эти соединения можно обратить (заменить в указанной выше схеме крайние левые на крайние правые). При декодировании по алгоритму Витерби обратные соединения приведут к кодам с точно такими же пространственными характеристиками, а значит, и с такими же рабочими характеристиками, как показаны в табл. 5.2 – 5.7.

184

Таблица 5.2 Максимальное свободное расстояние кодов со скоростью кодирования 1/2

Длина кодового	Порождающие полиномы					dсв
ограничения K	(в восьмеричной записи)
3	5		7			5
4	15		17			6
5	23		35			7
6	53		75			8
Таблица 5.3 Максимальное свободное расстояние кодов со скоростью
кодирования 1/3
Длина кодового	Порождающие полиномы					dсв
ограничения K	(в восьмеричной записи)
3	5	7			7	8
4	13	15			17	10
5	25	33			37	12
6	47	53			75	13
7	133	145			175	15
8	225	331			367	16
9	557	663			711	18
Таблица 5.4 Максимальное свободное расстояние кодов со скоростью
кодирования 2/3
Длина кодового	Порождающие полиномы					dсв
ограничения K	(в восьмеричной записи)
2	17	06			15	3
3	27	75			72	5
4	236	155			337	7

Таблица 5.5 Максимальное свободное расстояние кодов со скоростью кодирования k/5

Скорость	Длина		Порождающие полиномы				dсв
	кодового		(в восьмеричной записи)
	ограничения
	K
	2	17	07	11	12	04	6
2/5	3	27	71	52	65	57	10
	4	247	366	171	266	373	12
3/5	2	35	23	75	61	47	5
4/5	2	234	274	156	255	337	3

185

Таблица 5.6 Максимальное свободное расстояние кодов со скоростью кодирования k/7

Скорость	Длина		Порождающие полиномы						dсв
	кодового		(в восьмеричной записи)
	ограничения
	K
	2	05	06	12	15	15	13	17	9
2/7	3	33	55	72	47	25	53	75	14
	4	312	125	247	366	171	266	373	18
3/7	2	45	21	36	62	57	43	71	8
4/7	2	130	067	237	274	156	255	337	6

Таблица 5.7 Максимальное свободное расстояние кодов со скоростью кодирования 3/4 и 3/8

Скорость	Длина		Порождающие полиномы					dсв
	кодового			(в восьмеричной записи)
	ограничения
	K
3/4	2	13		25	61		47	4
3/8	2	15		42	23		61	8
		51		36	75		47

5.12 Мягкое декодирование по алгоритму Витерби

Для двоичной кодовой системы со степенью кодирования 1/2, демодулятор подает на декодер два кодовых символа за раз. Для жесткого (двухуровневого) декодирования каждую пару принятых кодовых символов можно изобразить на плоскости в виде одного из углов квадрата, как показано на рис. 5.18, а. Углы помечены двоичными числами (0, 0), (0, 1), (1, 0) и (1, 1), представляющими четыре возможных значения, которые могут принимать два кодовых символа в жесткой схеме принятия решений. Аналогично для 8- уровневого мягкого декодирования каждую пару кодовых символов можно отобразить на плоскости в виде квадрата размером 8 8, состоящего из 64 точек, как показано на рис. 5.18, б. В этом случае демодулятор больше не выдает жестких решений; он выдает квантованные сигналы с шумом (мягкая схема принятия решений).

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

186

пользоваться парами целых чисел от 0 до 7. На рис. 5.18, в также изображена точка 5,4, представляющая пример пары значений кодовых символов с шумом. Представим себе, что квадрат на рис. 5.18, в изображен в координатах (x, у). Каким будет евклидово кодовое расстояние между точкой с шумом 5,4 и точкой без

шума 0,0? Оно равно (5 0)2 (4 0)2 41. А если мы захотим узнать евклидово кодовое расстояние между точкой с шумом 5,4 и точкой без шума

7,7? Аналогично (5 7)2 (4 7)2 13.

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

0,1		1,1	0,1		1,1

0,0	1,0			0,0		б)	1,0
	а)
	t1		0,0	t2			t1

0,7		7,7
0,0	в)	7,0
t2

7,7

г)

д)

Рис.5.18 Декодирование Витерби: а) плоскость жесткой схемы принятия решений; б) 8- уровневая плоскость мягкой схемы принятия решений; в) пример мягких кодовых символов; г) секция решетки кодирования; д) секция решетки декодирования.

На рис. 5.18, г показана первая секция решетки кодирования, которая вначале имела вид, приведенный на рис. 5.6. При этом кодовые слова преобразованы из двоичных в восьмеричные. Допустим, что пара кодовых символов, поступившая на декодер во время первого перехода, согласно мягкой схеме декодирования имеет значения 5,4. На рис. 5.18, д показана первая

секция решетки декодирования. Метрика ( 41 ), представляющая евклидово кодовое расстояние между прибывшим кодовым словом 5,4 и кодовым словом

0,0, обозначена сплошной линией. Аналогично метрика ( 13 ) представляет

187

собой евклидово кодовое расстояние между поступившим кодовым символом 5,4 и кодовым символом 7,7; это расстояние показано пунктирной линией. Оставшаяся часть задачи декодирования, которая сводится к отсечению решетки и поиску полной ветви, осуществляется аналогично схеме жесткого декодирования. Заметим, что в реальных микросхемах, предназначенных для сверточного декодирования, евклидово кодовое расстояние в действительности не применяется, вместо него используется монотонная метрика, которая обладает сходными свойствами, но значительно проще в реализации. Примером такой метрики является квадрат евклидова кодового расстояния, в этом случае исключается рассмотренная выше операция взятия квадратного корня. Более того, если двоичные кодовые символы представлены биполярными величинами, тогда можно использовать метрику скалярного произведения, определяемую уравнением (5.10). При такой метрике вместо минимального расстояния мы должны будем рассматривать максимальные корреляции.

Выводы.

В течение последних десяти лет наиболее популярной схемой кодирования являлась сверточная, поскольку почти во всех приложениях сверточные коды лучше блочных при той же конструктивной сложности кодера и декодера. Для каналов спутниковой связи схемы прямого исправления ошибок позволяют легко понизить на 5-6 дБ требуемое значение SNR для заданной достоверности передачи. Из этой эффективности кодирования непосредственно вытекает снижение эффективной изотропной излучаемой мощности спутника (effective isotropic radiated power — EIRP), что, соответственно, приводит к снижению веса

истоимости спутника.

Вэтой главе мы описали значительную структурную разницу между блочными и сверточными кодами – сверточные коды со степенью кодирования 1/п сохраняют в памяти предыдущие К - 1 бит, где К означает длину кодового ограничения. С такой памятью кодирование каждого входного бита данных зависит не только от значения этого бита, но и от предшествующих ему К- 1 бит. Задача описывалась в контексте алгоритма максимального правдоподобия. При его использовании изучаются все возможные последовательности кодовых слов, которые могли быть созданы кодером, и выбирается та, которая выглядит статистически наиболее вероятной. Решение опирается на метрику расстояния принятых кодовых символов. Анализ безошибочной работы сверточных кодов является более сложным, чем простое биномиальное разложение, описывающее работу без ошибок многих блочных кодов.

Втаблице 5.8 приведены значения ЭВК для сверточного кода с Rc = ½ , 32-битовой памятью путей при использовании в гауссовом канале модуляции BPSK, вероятности ошибки 10-4 при отношении Eb/N0.= 8,2 дБ без использования кодирования.

188

Таблица 5.8 Значения ЭВК сверточного кода

Глубина	3	4	5	6	7	8
кодирова
ния, K
ЭВК	1.1	1.4	1.9	2.2	2.6	3.0

189

6 КАСКАДНЫЕ КОДЫ

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

Недвоичный (N, К) код образует внешний код, а двоичный - внутренний код. Кодовые слова формируются путѐм подразделения блока на Kk информационных бита по К группам, называемым символами, причѐм каждый такой символ состоит из k бит. К символов (с k битами каждый) кодируются в N символов внешним кодом, как это обычно делается при недвоичном кодировании. Внутренний кодер берет каждый k –битовый символ и кодирует его в двоичный блоковый код длины п. Таким образом, мы получаем каскадный блоковый код, имеющий длину Nn бита и содержащий Kk информационных бита. Это значит, мы создали эквивалентный (Nn.Kk) длинный двоичный код. Биты в каждом кодовом слове передаются по каналу посредствам ФМ или, возможно, ЧМ.

Входные

данные

Внешнее

Внешнее

Внутреннее

Внутреннее

кодирование

перемежение

кодирование

перемежение

Выход

кодера

Вход

декодера

Внешнее

Внешнее

Внутреннее

Внутреннее

декодирование

деперемежение

декодирование

деперемежение

Декодированные

даные

Рис. 6.1 Структурная схема каскадной системы кодирования

Также укажем, что минимальное расстояние для каскадного кода равно

dmimDmim, где Dmim – это минимальное расстояние для внешнего кода, a dmim – минимальное расстояние для внутреннего кода. Далее, скорость каскадного

кода равна Kk/Nn, что равно произведению скоростей двух кодов.

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

190