Васюков В_Н_ Теория электрической связи_

8.4. Кодирование источника												243
				Кодирование группами							Т а б л и ц а 8.2
	1	1 :0,81							1	1 :0,81		1
												1
	1	2 :0,09							____0,1________
					1							0
		1 :0,09								2 :0,09
	2								1			0
	2	2 :0,01			0

Средняя длина кодовой комбинации, приведенная к одному символу алфавита (для этого взвешенная сумма делится на 2), равна

0,81 0,09 2 0,09 3 0,01 3 0,645 . 2

Вероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесенное к средней длине кодового слова:

p(1) 0,81 0,09 2 0,01 0,775 . 0,645 2

Энтропия кода находится как энтропия случайной величины, принимающей два значения (0 и 1) с вероятностями 0,225 и 0,775:

Hк 0,225log0,225 0,775log0,775 0,769.

Избыточность кода

к Hк max Hк 1 0,769 0,231 .

Hк max 1

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

Еще более эффективные коды для данного источника можно получить, объединяя символы алфавита в группы по три, четыре и т. д. В пределе, согласно теореме Шеннона, средняя длина кодовой комбинации, приведенная к одному символу алфавита, должна стремиться к значению 0,469, избыточность кода – к нулю, а вероятности кодовых символов 0 и 1 – к значению 0,5. ◄

244	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

8.5. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

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

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

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

Такая возможность достигается целенаправленным введением избыточности в передаваемые сообщения. Наиболее простой способ

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

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

для каналов с помехами (шумами) [10].

ТЕОРЕМА. Если производительность источника H ( )

меньше пропускной способности канала C , то существует по

крайней мере одна процедура кодирования/декодирования, при которой вероятность ошибочного декодирования и ненадежность

H ( | ) могут быть сколь угодно малы. Если H '( ) C , то та-

кой процедуры не существует.

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

107 Широко употребляется также термин сжатие.

8.5. Помехоустойчивое кодирование

245

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

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

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

Блочные коды, как правило, являются равномерными.

Если в кодовом слове можно выделить информационные символы, служащие для передачи сообщения, и проверочные (кон-

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

мерами неразделимых кодов являются так называемые коды с постоянным весом, в частности, код «3 из 7» (стандартный телеграф-

ный код № 3 [10]), а также коды на основе матриц Адамара (коды

Рида–Мюллера).

Разделимые коды, в свою очередь, подразделяются на линейные

инелинейные.

Вкачестве примера рассмотрим один класс помехоустойчивых кодов – линейные блочные коды.

Блочный равномерный код состоит из кодовых слов (комбина-

ций) одинаковой длины n . Элементы кодовых слов выбираются из некоторого алфавита (канальных) символов объемом q . Если

q 2 , код называется двоичным. Далее для простоты считается, что q 2 . Поскольку все кодовые слова имеют одинаковую длину,

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

верждение: линейная комбинация кодовых слов является кодовым словом.

Всего можно образовать 2n n -мерных векторов с двоичными компонентами (кодовых комбинаций или слов). Из них только

M 2k , k n комбинаций являются разрешенными и составляют

108Широкое распространение получили непрерывные коды, принадлежащие подклассу сверточных кодов.

246 8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

код, который называется (n, k) -кодом (отношение k / n R назы-

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

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

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

комбинации можно не только обнаруживать, но и исправлять ошибки. Для этого декодер должен принимать решение о переданной комбинации на основе расстояния между принятой запрещенной комби-

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

собность кода. Алгоритм работы декодера формально сводится к разбиению всего пространства на области Ai , i 1,...,M , каждая из ко-

торых содержит одну разрешенную комбинацию xi . Если принятая комбинация принадлежит области Ak , то декодер принимает решение о том, что передавалась разрешенная комбинация xk .

Для кодирования и декодирования линейных блоковых кодов применяются действия, описываемые операциями над векторами в линейном пространстве над конечным полем целых чисел [2]. Сложение и умножение в конечном поле понимаются как сложение и умножение по модулю q . Простейшее из таких полей, назы-

ваемых полями Галуá – поле по модулю 2, обозначаемое GF(2) .

Сложение и умножение в этом поле описываются следующими таблицами сложения и умножения (табл. 8.3, 8.4).

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

Мерой различия между векторами линейного пространства, как известно, может служить некоторая функция (функционал), называемая метрикой, или расстоянием [2]. В теории кодирования часто

Т а б л и ц а 8.3	Т а б л и ц а 8.4
Таблица сложения в поле GF (2)	Таблица умножения в поле GF (2)

+	0	1
0	0	1
1	1	0

	0	1
0	0	0
1	0	1

8.5. Помехоустойчивое кодирование

247

используется метрика Хэмминга, определяемая для двух двоичных кодовых векторов x и y выражением

n

d(x, y) (xi yi )mod 2 .

i 1

Легко видеть, что расстояние по Хэммингу между двумя двоичными векторами равно количеству несовпадающих элементов (например, для векторов 00011100 и 11000110 расстояние равно 5).

В n -мерном пространстве двоичных векторов можно опреде-

n

лить скалярное произведение выражением (x, y) xi yi , где сум-

i 1

ма понимается как сумма по модулю 2. Если для некоторой пары

векторов скалярное произведение равно 0, то векторы являются

ортогональными.

Таким образом, множество всех двоичных кодовых слов длины n можно рассматривать как n -мерное линейное пространство над

конечным полем скаляров GF(2) . Хотя это пространство содержит

лишь конечное множество векторов, а именно 2n , оно удовлетворяет всем аксиомам векторного пространства [2].

Линейные коды являются разделимыми, поэтому из n символов только k являются информационными, а остальные ( n k ) –

проверочными. Тогда, очевидно, в n -мерном пространстве Sn всех комбинаций можно выделить k -мерное подпространство Sk разрешенных комбинаций. Таким образом, пространство Sn можно представить прямой суммой k -мерного подпространства Sk и ( n k )-мерного подпространства Sn k , так что любой вектор из Sn k ортогонален любому вектору, принадлежащему Sk :

Sn Sk Sn k ,

Sk Sn k ,

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

Предположим, что блок из k информационных двоичных символов кодируется словом из n канальных двоичных символов. Обозначим информационный k -мерный вектор109 через

X (x1,..., xk ) , кодовый n -мерный вектор через C (c1,...,cn ) . Ко-

109 В кодировании принято записывать векторы, как векторы-строки.

248	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

дирование описывается линейным преобразованием (оператором), отображающим векторы, принадлежащие подпространству Sk , в

векторы из Sn

C = XG ,

(8.9)

где G – матрица кодирования (порождающая матрица кода) вида

g11	g12	.	.	.	g1n
	g22	.	.	.
g21					g2n
.	.	.	.	.	.
G	.	.	.	.	.	.
.
.	.	.	.	.	.
	gk 2	.	.	.
gk1					gkn

Уравнение (8.9) можно рассматривать и как систему из n линейных уравнений вида

c j x1g1 j x2 g2 j ... xk gkj ,

j 1,...,n ,

где сложение понимается по модулю 2.

Нетрудно видеть, что любое кодовое слово – это не что иное, как линейная комбинация строк матрицы G с весовыми коэффи-

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

странству Sn , они также принадлежат k -мерному подпространству Sk , натянутому на векторы – строки матрицы G , какова бы ни

была эта матрица (если, конечно, у нее n столбцов и k строк, ко-

торые, очевидно, должны быть линейно независимыми). Путем

линейных операций над строками и перестановки столбцов любую такую матрицу можно привести к систематическому виду:

			1	0	0 .	.	0 p11
			0	1	0 .	.	0 p21
G Ik		. . . . . . .
		P
		. . . . . . .
		. . . . . . .
			0	0	0 .	.	1 pk1

p12 p22

.

.

.

pk 2

.p1(n k)

.p2(n k)

..

. .

..

.pk(n k)

. , (8.10)

8.5. Помехоустойчивое кодирование

249

где Ik – единичная матрица размера k k , а P – матрица размера k (n k) . Воздействие такого преобразования на информацион-

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

ционных матрицей P и являются проверочными (паритетными). В этом случае код называют систематическим. Любой линейный

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

Пример 8.7. Систематический (7, 4)-код порождается матрицей

	1		0	0	0	1	0	1
G		0	1	0	0	1	1	1
		0 0 1			0	1	1	0
									.
		0	0	0	1	0	1	1

Кодовые слова имеют структуру C (x1, x2, x3, x4, c5, c6, c7 ) ,

где

c5 x1 x2 x3 , c6 x2 x3 x4 , c7 x1 x2 x4

(подразумевается сложение по модулю 2).

Реализовать такое кодирование можно при помощи устройства, структурная схема которого показана на рис. 8.2.

Устройство включает два сдвиговых регистра объемом 4 и 3 разряда, а также три сумматора по модулю 2. Информационная последовательность поступает на вход первого регистра и записывается в его разрядах. На выходах сумматоров по модулю 2 формируются проверочные символы, которые запоминаются в разрядах второго сдвигового регистра. Последним шагом формирования кода является считывание вначале четырех информационных символов, а затем – трех проверочных, при этом на выходе устройства получается семиразрядное кодовое слово. ◄

250

8.

ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

х

x3

x2

x1

x4

Выход

с7 с6 с5

Рис. 8.2. Структура кодера для систематического

(7, 4)-кода

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

Вернемся к структуре пространства Sn . Подпространство Sk

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

дающей матрицы G . Другими словами, подпространство Sk и есть (n, k) -код. Тогда подпространство Sn k , ортогональное к нему, также можно считать некоторым (n, n k) -кодом, дуальным к

данному. Порождающая матрица		H дуального кода содержит
(n k) линейно независимых строк длины n .
Любое кодовое слово (n, k) -кода ортогонально любому кодо-
вому слову (n, n k) -кода, следовательно,
GHT = 0 ,
где 0 – матрица размера k (n k) , состоящая из нулей,			( )T –
символ транспонирования. С учетом (8.10) можно записать
H PT		In k ,	(8.11)

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

Матрица H является порождающей матрицей дуального кода; в то же время она может использоваться для обнаружения ошибок. В самом деле, если принятая кодовая комбинация Y является раз-

8.5. Помехоустойчивое кодирование			251
решенной, то она ортогональна к подпространству110 S		k	, или,
n
что то же самое, ко всем строкам матрицы H , поэтому YHT = 0 ,

где 0 – нулевой вектор размерности (n k) . Таким образом, ум-

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

ции, на транспонированную матрицу HT , получаем вектор (называемый синдромом), который равен нулевому вектору в том и

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

Коды Хэмминга

Одним из наиболее известных классов помехоустойчивых линейных блочных кодов являются коды Хэмминга. Коды Хэмминга представляют собой (n, k) -коды, удовлетворяющие условию

(n, k) (2m 1,2m 1 m)

при некотором целом m .

В частности, рассмотренный (7, 4)-код является кодом Хэмминга.

Особое свойство кодов Хэмминга заключается в строении проверочной матрицы. Для любого линейного кода проверочная мат-

рица содержит (n k) строк и n столбцов; для кода Хэмминга

n 2m 1 и проверочная матрица содержит в качестве столбцов

все возможные комбинации нулей и единиц, исключая нулевой вектор.

Для (7, 4)-кода, рассмотренного в примере 8.7, проверочная матрица в соответствии с выражением (8.11), очевидно, имеет вид

1		1	1	0	1	0	0
H	0	1	1	1	0	1	0	.
	1	1	0	1	0	0	1

Если передается кодовая комбинация C и в канале происходит ее искажение, то принятую комбинацию Y можно представить в виде Y C e , где e – вектор ошибки, содержащий единичные

110 Это подпространство также называют нуль-пространством [15].

252	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ

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

Умножим принятую комбинацию на транспонированную проверочную матрицу

YHT = CHT +eHT = +eHT = σ

0 ,

здесь вектор σ представляет собой синдром, который равен нуле-

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

ству Sn k . Это означает, что не могут быть обнаружены ошибки,

составляющие вектор, который сам является разрешенной комбинацией кода.

Чтобы убедиться в корректирующих свойствах кода Хэмминга, рассмотрим пример обнаружения ошибки в кодовой комбинации.

Пример 8.8. Предположим, что передавалась разрешенная кодовая комбинация 0100111 (напомним, что разрешенными комбинациями являются все линейные комбинации строк порождающей матрицы кода). Предположим также, что при передаче произошла ошибка, скажем, во втором символе, так что принята комбинация

0000111.

Умножая вектор-строку, соответствующую принятой комбина-

ции, слева на транспонированную проверочную матрицу HT , получим синдром

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

который совпадает со второй строкой матрицы HT . Это указывает на то, что ошибочным является второй символ принятой комбинации. ◄

То обстоятельство, что синдром позволяет определить номер «испорченного» символа, фактически означает возможность исправления ошибок. В самом деле, если точно известно, что во вто-