Скляр в пересказе Орешкина

n		p)n j .	(7.9)
P( j, n)	p j (1
	j

Здесь р - вероятность получения канального символа с ошибкой, а через

n			n!
					(7.10)
			j!(n j)!
j

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

из n бит j ошибочных. Таким необнаруженной ошибки Рnd в

		n / 2 (при n четное)
		(n 1) / 2 (при n	нечетное) n
P					p2 j (1	p)n 2 j .	(7.11)
nd
		j 1		2 j

Прямоугольный код (rectangular code), называемый также композиционным (product code), создается следующим образом. Вначале из битов сообщения строятся прямо-

угольники, состоящие из М строк и N столбцов; затем к каждой строке и каждому столбцу прибавляется бит четности, что в результате дает матрицу размером M 1 N 1 . Сте-

пень кодирования прямоугольного кода k/n может быть записана

	k		MN	.
	n		(M 1)(N 1)

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

лим для такого блочного кода с коррекцией ошибок вероятность появления неисправлен-

ной ошибки, для чего учтем все способы появления ошибки сообщения. Исходя из веро-

ятности наличия j ошибок в блоке из п символов, записанной в выражении (7.9), можно записать вероятность ошибки сообщения, называемой также блочной ошибкой, или оши-

бочным словом, для кода, который может исправить ошибочные комбинации, состоящие из t или менее ошибочных битов:

P		n	n		p)n j .	(7.12)
				p j (1
M
		j t 1		j

81

7.4. Цели кодирования с коррекцией ошибок

Кодирование с коррекцией ошибок можно рассматривать как инструмент, реали-

зующий различные компромиссы системы. На рис.7.2 приведены две кривые, описываю-

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

но уже с использованием кодирования.

Pb

			Кодированная
10 2			A
			F
10	4			B
		C
10	6				D
		E			Некодированная
		Eb /N0 (дБ)
	8		9	14	E b / N	0 (дБ)

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

.

Компромисс 1: достоверность или полоса пропускания. Допустим, что сущест-

вует система связи без кодирования с коррекцией ошибок. Пусть рабочая точка системы совпадает с точкой А на рис.7.2 (Eb/N0 = 8 дБ, Рb – 10–2). После нескольких испытаний сис-

темы появляются жалобы на качество связи и необходимо обеспечение вероятности появ-

ления битовой ошибки не выше 10–4. Для этого требуется сдвиг рабочей точки из точки А,

например, в точку В (рис.7.2). В то же время допустим, что Eb/N0, равное 8 дБ, - это мак-

симальное значение, возможное в данной системе. Из рис.7.2 видно, что один из возмож-

ных выходов из ситуации (компромиссов) - это сдвиг рабочей точки из точки А в точку С.

Помимо введения новых компонентов (кодера и декодера), это приведет к увеличению необходимой полосы пропускания. Кодирование с коррекцией ошибок требует избыточ-

ности. Если предположить, что связь будет происходить в реальном времени (так что со-

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

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

Компромисс 2: мощность или полоса пропускания. Допустим, существует сис-

тема без кодирования с рабочей точкой, совпадающей с точкой D на рис.7.2 (Eb/N0 = 14

82

дБ, Рb = 10–6). К качеству связи претензий нет, но система работает на пределе своих энер-

гетических возможностей, на грани отказа. Если снизить требования к Eb/N0 или мощно-

сти, то проблем с надежностью оборудования можно избежать. В контексте рис.7.2 дан-

ные меры выглядят как сдвиг рабочей точки из D в E. Другими, словами, требуемое значение Eb/N0 можно получить, если применить кодирование с коррекцией ошибок. Та-

ким образом, при фиксированном качестве связи компромисс заключается в получении большей производительности при снижении требований к мощности или Eb/N0.

Рассмотренный пример компромиссных решений позволяет понизить Eb/N0 с 14 до

9 дБ при поддержании той же достоверности передачи. В контексте этого примера и с по-

мощью рис.7.2 мы можем ввести понятие эффективность кодирования (coding gain).

Итак, при данной вероятности битовой ошибки эффективность кодирования определя-

ется как уменьшение Eb/N0, достигаемое при использовании кодирования. Эффективность кодирования G, как правило, выражается в децибелах.

		Eb			Eb
	G дБ			дБ			дБ .	(7.13)
		N0			N0
			u			с

Здесь (Eb/N0)u и (Eb/N0)с - соответственно требуемые некодированное и кодирован-

ное значения.

Компромисс 3: скорость передачи данных или полоса пропускания. Пусть раз-

работана система без кодирования с рабочей точкой, совпадающей с точкой D на рис.7.2 (Eb/N0 = 14 дБ, Рb = 10–6). Допустим, что с качеством данных нет никаких проблем и нет особой нужды в снижении мощности. Однако возросли требования к скорости передачи данных.

Возрастание скорости передачи данных плохо отражается на качестве их передачи.

В то же время применение кодирования с коррекцией ошибок восстанавливает утраченное качество, сохраняя при этом прежний уровень мощности (Pr/N0). Итак, значение Eb/N0 по-

нижено, но код способствует получению той же вероятности ошибки при сниженном зна-

чении Eb/N0. Цена такого увеличения скорости передачи данных - увеличение полосы пропускания.

7.5. Линейные блочные коды

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

83

Кодовое

сообщение

000000

110100

011010

101110

101001

011101

110011

000111

тор), образованного с использованием элементов данного алфавита. В нашем пособии бу-

дем использовать простейший двоичный алфавит.

k-битовые сообщения формируют набор из 2k последовательностей сообщения, на-

зываемых k-кортежами (k-tuple), n-битовые блоки могут формировать 2n последователь-

ностей, также именуемых n-кортежами. Процедура кодирования сопоставляет с каждым из 2k k-кортежей сообщения один из 2n n-кортежей. Блочные коды представляют взаимно однозначное соответствие, в силу чего 2k k-кортежей сообщения однозначно отображают-

ся в множество из 2n n-кортежей кодовых слов; отображение производится согласно таб-

лице соответствия.

Множество всех двоичных n-кортежей Vn называется векторным пространством

над двоичным полем двух элементов (0 и 1). В двоичном поле определены две операции -

сложение и умножение, причем результат этих операций принадлежит этому же множест-

ву двух элементов.

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

1.Множеству S принадлежит нулевой вектор.

2.Сумма любых двух векторов в S также принадлежит S (свойство замкнутости).

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

двоичном блочном коде (n, k). Код называется линейным тогда и только тогда, когда (Vi

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

вых слов, принадлежащих этому подпространству.

Рассмотрим пример линейного блочного кода (6,3). Код состоит из 2k = 23 = 8 век-

торов сообщений и, следовательно, восьми кодовых слов. В векторном пространстве V6

имеется 2n (26 = 64) 6-кортежей.

Вектор

сообщения

000

100

010

110

001

101

011

111

84

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

(есть нулевой вектор, сумма любых двух кодовых слов дает кодовое слово этого же под-

пространства). Таким образом, эти кодовые слова представляют линейный блочный код.

При больших k реализация таблицы соответствия кодера становится слишком громоздкой. Для кода (127,92) существует 292 или приблизительно 5∙1027 кодовых векто-

ров, что потребует значительного количества памяти. Задачу можно существенно упро-

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

нейный блочный код, является k-мерным подпространством n-мерного двоичного вектор-

ного пространства (k < n), всегда можно найти такое множество n-кортежей (с числом элементов, меньшим 2k), которое может генерировать все 2k кодовых слова подпростран-

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

Наименьшее линейно независимое множество, охватывающее подпространство, называет-

ся базисом подпространства, а число векторов в этом базисном множестве является раз-

мерностью подпространства. Любое базисное множество k линейно независимых n-

кортежей V1, V2,..., Vk можно использовать для генерации нужных векторов линейного блочного кода, поскольку каждый вектор кода является линейной комбинацией V1, V2,..., Vk. Иными словами, каждое из множества 2k кодовых слов {U} можно представить как

U m1V1 m2V2 ... mk Vk .

Здесь mi = (0 или 1) - цифры сообщения; i = 1,..., k.

Вообще, матрицу генератора можно определить как массив размером k n .

V			v		v
	1			11	12
G V2			v21 v22
	V				v
			v
	k1			k1	k 2

v
1m
v2m		.	(7.14)
v
km

Кодовые векторы принято представлять векторами-строками. Таким образом, со-

общение m (последовательность k бит сообщения) представляется как вектор-строка (мат-

рица 1 k , в которой одна строка и k столбцов).

mm1, m2 ,..., mk .

Вматричной записи генерация кодового слова U будет выглядеть как произведение

m и G

U m G ,

(7.15)

где умножение матриц С = АВ выполняется по следующему правилу:

n
cij aik bkj , i 1,...,l,	j 1,...,m .
k 1
85

Здесь А - матрица размером 1 n ; В - матрица размером n m , а результирующая матрица С имеет размер 1 m . Для ранее рассмотренного примера матрица генератора имеет вид

V1		1 1 0 1 0 0
G V		0 1 1 0 1	0 .	(7.16)
2
V3		1 0 1 0 0 1

Здесь V1, V2 и V3 - три линейно независимых вектора (подмножество восьми ко-

довых векторов), которые могут сгенерировать все кодовые векторы.

Таким образом, кодовый вектор, соответствующий вектору сообщения, является линейной комбинацией строк матрицы G. Поскольку код полностью определяется матри-

цей G, кодеру нужно помнить лишь k строк матрицы G, а не все 2k кодовых вектора.

Систематическим называется код, у которого в кодовом слове в явном виде при-

сутствует исходное информационное слово. Матрица генератора систематического ли-

нейного блочного кода имеет вид

G	P					Ik
	p11				p12		p1(n k )		1 0 0		(7.17)
					p22 p2(n k )				0 1 0
	p21
										.
	p		k1	p		k 2	p	k (n k )	0 0 1
Здесь Р - массив			четности, входящий							в	матрицу генератора;
pij = (0 или 1), а Ik - единичная матрица размерностью k k										(у которой диагональные эле-

менты равны 1, а все остальные - 0). Заметим, что при использовании этого систематиче-

ского генератора процесс кодирования еще больше упрощается, поскольку нет необходи-

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

U p1, p2 ,..., pn k ,

Биты четности

m1, m2 ,...,mk . (7.18)

Биты сообщения

Для декодирования линейного блочного кода потребуется проверочная матрица.

Для каждой матрицы k n генератора G существует матрица Н размером

(n k) n , такая, что строки матрицы G ортогональны к строкам матрицы Н. Иными сло-

вами, GHT = 0, где НT - транспонированная матрица Н; а 0 - нулевая матрица.

H I	n k		PT .	(7.19)

86

Нетрудно убедиться, что произведение UHT любого кодового слова U, генерируе-

мого G, и матрицы HT дает следующее:

UHT 0.

Таким образом, поскольку проверочная матрица Н создана так, чтобы удовлетво-

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

руемым матрицей G, тогда и только тогда, когда UHT = 0.

7.6. Возможность обнаружения и исправления ошибок

Возможности кода для исправления ошибок в первую очередь определяются его структурой. Весовой коэффициент Хэмминга (Hamming weight) w(U) кодового слова U

определяется как число ненулевых элементов в U. Для двоичного вектора это эквивалент-

но числу единиц в векторе. Например, если U = 100101101, то w(U) = 5. Расстояние Хэмминга (Hamming distance) между двумя кодовыми словами U и V, обозначаемое как d(U, V), определяется как количество элементов, которыми они отличаются.

U 100101101

V 011110100

d U, V 6

Согласно свойствам сложения по модулю 2, можно отметить, что сумма двух дво-

ичных векторов является другим двоичным вектором, двоичные единицы которого рас-

положены на тех позициях, которыми эти векторы отличаются.

U V 111011001.

Таким образом, можно видеть, что расстояние Хэмминга между двумя векторами равно весовому коэффициенту Хэмминга их суммы, т.е. d (U, V) = w (U + V). Кроме того,

видно, что весовой коэффициент Хэмминга кодового слова равен его расстоянию Хэм-

минга до нулевого вектора.

Рассмотрим множество расстояний между всеми парами кодовых слов в простран-

стве Vn. Наименьший элемент этого множества называется минимальным расстоянием

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

Задача декодера после приема вектора r заключается в оценке переданного кодово-

го слова Ui. Оптимальная стратегия декодирования может быть выражена в терминах ал-

горитма максимального правдоподобия.

87

На рис.7.3 расстояние между двумя кодовыми словами U и V показано как рас-

стояние Хэмминга. Каждая черная точка обозначает искаженное кодовое слово. На этом рисунке проиллюстрирован прием вектора r1, находящегося на расстоянии 1 от кодового слова U, и на расстоянии 4 от кодового слова V. Декодер с коррекцией ошибок, следуя стратегии максимального правдоподобия, выберет при принятом векторе r1 кодовое слово

U. Если r1 получился в результате появления одного ошибочного бита в переданном век-

торе кода U, декодер успешно исправит ошибку. Но если это произошло в результате 4-

битовой ошибки в векторе кода V, декодирование будет ошибочным. Из рис.7.3 видно,

что если задача состоит только в обнаружении ошибок, а не в их исправлении, то можно определить искаженный вектор - изображенный черной точкой и представляющий 1-, 2-, 3- и 4-битовую ошибку. В то же время пять ошибок при передаче могут привести к прие-

му кодового слова V, когда в действительности было передано кодовое слово U; такую ошибку невозможно будет обнаружить.

Линия

решений

Область 1

Область 2

U V r1

Рис.7.3. Возможности определения и исправления ошибок

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

тей решения.

Способность кода к исправлению ошибок t определяется как максимальное число гарантированно исправимых ошибок на кодовое слово и записывается

d		min	1
t				.	(7.20)
		2

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

бит, применяется для исправления ошибок в двоичном симметричном канале с вероятно-

стью перехода р, то вероятность ошибки сообщения РM (вероятность того, что декодер со-

вершит неправильное декодирование и п-битовый блок содержит ошибку) можно оценить сверху:

88

89

P		n	n		p)n j .	(7.21)
				p j (1
M
		n t 1		j

Вероятность ошибки в декодированном бите Рb зависит от конкретного кода и де-

кодера. Приближенно ее можно выразить следующим образом:

	1	n	n
P				p j (1	p)n j .	(7.22)
b
	n n t 1			j

Оценить возможности кода к исправлению ошибок можно, воспользовавшись пре-

делом Хэмминга, который описывается следующим образом:

количество бит четности:

n k log			n		n			n		.	(7.23)
	2	1
			1			2		t

n

Здесь величина , определяемая уравнением (7.10), представляет число способов

j

выбора из п бит j ошибочных. Для обеспечения возможности коррекции t-битовых оши-

бок произвольных линейных блочных кодов (п, k) необходимым условием является удов-

летворение предела Хэмминга. Кроме того, возможности кода можно оценить, используя

предел Плоткина:

dmin	n 2k 1
		.	(7.24)
	2k 1
Вообще, линейный код (n, k) должен удовлетворять всем перечисленным выше ус-

ловиям, включая возможности коррекции ошибок (или минимальное расстояние). Для вы-

сокоскоростных кодов из удовлетворения предела Хэмминга следует удовлетворение пре-

дела Плоткина.

7.7. Циклические коды

Важным подклассом линейных блочных кодов являются двоичные циклические коды (cyclic codes). Код легко реализуется на регистре сдвига с обратной связью; на по-

добных регистрах сдвига с обратной связью вычисляется синдром; алгебраическая струк-

тура циклического кода естественным образом позволяет эффективно реализовать методы декодирования. Итак, линейный код (n, k) называется циклическим, если он обладает сле-

дующим свойством. Если n-кортеж U (u0 , u1, u2 , , un 1) является кодовым словом в под-

пространстве S, то U(1) (un 1, u0 , u1, u2 , , un 2 ) , полученный из U с помощью циклическо-

го сдвига, также является кодовым словом в S.

Компоненты кодового слова U u0 , u1, u2 , , un 1 можно рассматривать как коэф-

фициенты полинома U( X ) .

U(X ) u	0	u X u	2	X 2 u	n 1	X n 1 .	(7.25)
		1
В кодовых словах, выраженных в полиномиальной форме, циклическая природа
кода проявляется следующим образом. Если U(X) является кодовым словом, представлен-
ным полиномом порядка n 1 , то U i X - остаток от деления X i U X								на X n 1 - также

является кодовым словом. Иными словами,

	X i U X		q X	U i X		(7.26а)
	X n 1			X n 1
или, умножая обе части уравнения на X n 1 ,
X i U X q( X )(X n 1) U(i) ( X ) .						(7.26б)
				Остаток

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

так же как создавались блочные коды с использованием матрицы генератора. Полиноми-

альный генератор g(X) для циклического кода (n, k) является единственным и имеет вид

g(X ) g	0	g X g	2	X 2	g	p	X p .	(7.27)
		1

Здесь g0 и g p должны быть равны 1. Каждый полином кодового слова в подпро-

странстве имеет вид

U(X ) m(X )g(X ) ,

где U(X) - полином степени n 1 или меньше. Причем старшая степень полинома

g(X)

p n k .

U будет считаться действительным кодовым словом из подпространства S тогда и только тогда, когда U(Х) делится на g(X) без остатка.

Полиномиальный генератор g(X) циклического кода (n, k) является множителем

X n 1 .

Для кодирования в систематической форме придется изменить алгоритм получения кодового слова с использованием генератора. В систематической форме символы сообще-

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

крайних левых разряда кодового слова, а затем прибавить биты четности, разместив их в крайние правые n k разряды. Рассмотрим пример 7.3.

90