Книги по Информационным технологиям / Теория информации СГАУ (дифференциальная энтропия)

			1 0 | p1,k 1			p1,n
Mn,k Ek Pk,n k			|			pi, j			,	(13.2)
					pk,k 1
			0 1 |				pk,n
где pi,j – проверочные символы.
При умножении в соответствии с (13.1) вектор-строки										Ak a1, ,ak на
матрицу Mn,k (13.2) получаем
An Ak Mn,k Ak Ek Ak Pk,n k Ak An k .										(13.3)
В данном случае первые k			символов вектор-строки An всегда информацион-
ные, а последние n k	– так называемые проверочные символы являются их
линейными комбинациями:
k
aj ai pi, j,	j			.						(13.4)
		k 1,n
i 1

Заметим, что формирование кодовой комбинации по правилу (13.3) сводится к поразрядному сложению строк образующей матрицы с номерами, соответст-

вующими номерам ненулевых информационных символов вектора Ak .

13.3 Построение матрицы-дополнения

Из (13.2) – (13.4) видно, что матрица-дополнение содержит всю информа-

цию о схеме построения кода. Например, pi,j 1 говорит о том, что в образова-

нии j-го проверочного разряда j k 1,n участвовал i-й i 1,k информа-

ционный разряд. Следовательно, по матрице-дополнению всегда можно запи-

сать уравнения кодирования в виде (11.11) или (13.4).

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

ла pi,j матрицы-дополнения может быть определено путем применения соот-

ветствующего уравнения для формирования j-го проверочного разряда к i-й

строке единичной матрицы.

Существует формальный способ построения матрицы дополнения, осно-

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

111

суммирования любых l, 1 l k строк матрицы дополнения, должна содер-

жать не менее dmin l отличных от нуля символов, где dmin – минимальное ко-

довое расстояние. В соответствии с указанным требованием матрица-

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

1)количество единиц в строке должно быть не менее dmin 1;

2)сумма по модулю два двух любых строк должна содержать не менее

dmin 2 единиц.

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

нием любых 2-х строк образующей матрицы, будет содержать не менее dmin не-

нулевых символов.

13.4 Понятие и построение проверочной (контрольной) матрицы

Код представляет собой n-мерное векторное пространство. Образующая матрица Mn,k определяет k -мерное подпространство. Следовательно, сущест-

вует ортогональное подпространство размерности n k. Пусть

H		h1,1		h1,n		(13.5)
	hn k,1		hn k,n

–матрица, векторы-строки которой задают это подпространство.

Всилу ортогональности указанных подпространств Mn,k HT 0. Следова-

тельно, для разрешенного кодового слова An	будем иметь:
An HT Ak Mn,k HT 0.	(13.6)

Матрица H, для которой имеет место равенство (13.6), всегда существует и на-

зывается проверочной (контрольной) матрицей, а указанное выражение исполь-

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

ответствии с (13.6) векторы, соответствующие разрешенным кодовым комби-

нациям, принадлежат нуль-пространству матрицы HT .

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

112

H	T		(13.7)
	Pk,n k	En k .

Нетрудно заметить, что в данном случае

Pk,n k

AnHT Ak An k S 0,0,...,0 ,En k

где S – вектор, компоненты которого определяются как

k

ai pi, j aj

0,

j

.

k 1,n

i 1

Если кодовый вектор

содержит ошибки:

An ξn , (ξn

0),

An,i

An

An ξn H

T

T

T

T

AnH

ξnH

ξnH

.

При этом компоненты Sj :

k

Sj i pi,j

j,

j

k 1,n

i 1

вектора S могут отличаться от нуля. Они зависят только от вектора ошибок, а

составленный из них вектор S является опознавателем ошибки (синдромом).

13.5 Границы для числа разрешенных комбинаций

Опираясь на понятие проверочной матрицы можно построить так назы-

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

В соответствии с (13.6) код является разрешенным тогда и только тогда,

когда

n
aihi 0,	(13.8)
i 1

где hi – i-й столбец m n матрицы H. Ясно, что число столбцов матрицы H,

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

пространству матрицы HT .

113

Отсюда, в частности, следует, что любой код, принадлежащий нуль-

пространству матрицы H, имеет минимальный вес, а следовательно и мини-

мальное кодовое расстояние равное самое меньшее d , тогда и только тогда, ко-

гда любые d 1 или меньше столбцов матрицы H линейно-независимы.

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

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

стве первого столбца берется любая ненулевая последовательность длины m n k. Вторым столбцом может быть любая некратная первой ненулевая по-

следовательность длины m. Третий столбец – любая последовательность длины m не являющаяся линейной комбинацией первых двух. Вообще в качестве i-го столбца берется любая последовательность длины m, не являющаяся линейной комбинацией никаких d 2 или меньше предыдущих столбцов. При этом ни-

какая линейная комбинация из d 1 или меньше столбцов матрицы не обраща-

ется в нуль.

Число всех возможных двоичных линейных комбинаций из d 2 или

меньше столбцов, выбранных из общего числа n столбцов, в наихудшем случае

(когда все они различны) равно

d 2
Cn1 Cn2 ... Cnd 2 Cni .	(13.9)

i 1

Очередной столбец может быть присоединен к матрице в том случае, если число комбинаций определяемых суммой (13.9) меньше, чем общее число от-

личных от нуля последовательностей длины m:

d 2
Cni 2m 1.	(13.10)

i 1

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

нием d и m проверочными символами, где m – наименьшее целое число,

удовлетворяющее неравенству (13.10).

Соответствующая неравенству (13.10) граница (Варшамова-Гилберта) по-

лучена в расчете на наихудший случай. Она указывает лишь на принципиаль-

ную возможность реализации n-разрядного кода с заданной корректирующей

114

способностью. Представляет интерес установить также верхнюю границу для

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

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

жит Cni ,
	i 1,s элементов. Вместе с разрешенной общее число комбинаций
в подмножестве составляет Cni ,				i	0,s	. Следовательно, при разложении

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

	s
2k 2n	Cni .	(13.11)
	i 0

Приведенное соотношение (13.11) называют оценкой Хэмминга. Если в этом выражении имеет место равенство, код называют плотно упакованным.

13.6 Матричное представление циклических кодов

Циклический код является групповым кодом, поэтому он может строиться

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

связанные со свойством цикличности. Рассмотрим способы построения обра-

зующей матрицы циклического кода.

Способ 1. Пусть образующий многочлен задан в виде

g x gmxm ... g1x g0 .

Тогда образующая матрица может быть построена путем умножения g x на одночлен xk 1, k n m и последующим циклическим сдвигом так, что каждая i-я строка образующей матрицы составляется из коэффициентов многочлена

g x xk i (i 1,k ):

115

		gm gm 1		g0 0	0
			gm	gm 1 g0
M	n,k	0			0 .	(13.12)
		0		0 gm gm 1 g0
Способ 2. Рассматриваются многочлены Qi x , соответствующие коду, со-
держащему только один ненулевой разряд: Q						x xn i,i		. Для них вычис-
							1,k
					i
ляются остатки ri x Qi x g x .					Каждая i-я строка образующей матрицы

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

ветствующих им остатков. При этом образующая матрица (в данном случае систематического кода) представляется двумя подматрицами:

Mn,k Ek Pk,n k ,

где Ek – единичная k k- матрица, а строками матрицы дополнения Pk,n k яв-

ляются остатки ri x ,i 1,k .

13.7 Построение проверочной матрицы циклического кода

Проверочная матрица в данном случае может строиться так же, как в слу-

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

венств и/или матрицы-дополнения. Однако для циклического кода существует еще один способ построения проверочной матрицы, заключающийся в делении многочлена xn 1 на многочлен g 1 x , являющийся дополнением к образую-

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

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

Предположим, что в результате деления двучлена xn 1 на многочлен до-

полнения получен некоторый многочлен:

	xn	1	b xk ...bx b .			(13.13)
	g 1	x
			k	1	0

Из коэффициентов этого многочлена составляется первая строка проверочной матрицы, а остальные строки образуются циклическим сдвигом:

116

b		b1 b0				0 0
	k
	0 b b1					b0 0				(13.14)
H			k						.
	0 0 b					b1		b0
					k
В качестве примера построим проверочную матрицу для кода (7,4), порож-
даемого образующим многочленом									g x x3 x 1. Соответствующий много-
член дополнения			g 1 x x3				x2 1.			В результате деления на него двучлена
x7 1 получаем многочлен x4 x3									x2 1. Соответствующая этому многочле-
ну проверочная матрица имеет вид
1		1	1	0	1		0	0
H 0 1 1 1 0 1								0
		0	1	1	1		0
0								1

Нетрудно убедиться, что любая разрешенная комбинация An , полученная путем умножения некоторого заданного информационного многочлена a x на указанный выше образующий многочлен: g x , в результате умножения на транспонированную проверочную матрицу: AnHT дает синдром, состоящий из одних нулей.

117

	Лекция 14
	Кодирование линейными последовательными машинами
	14.1 Понятие линейной последовательной машины
	Линейная последовательная машина (ЛПМ) – это система с конечным
числом входов ui,i 1,l и выходов yj, j 1,m, сигналы на которых наблюдают-
ся в дискретные моменты времени, и						1)
выполняющая следующие элементар-
ные функции (рис. 14.1) [2]:						2)			3)
				l
1)	сложение: y ui ;
			i 1				Рис. 4.1 – Элементы ЛПМ
2)	умножение на постоянную:
	y u;
3)	задержка: y t u t 1 .
Здесь и далее под аргументом сигнала подразуме-
вается номер момента времени.
	Общая схема ЛПМ может быть представлена в
виде, показанном на рис. 14.2. Число задержек оп-
ределяет размерность ЛПМ.					Запрещаются		петли,
								Рис. 14.2 – Общая схема
не содержащие ни одной задержки, т.к. это приво-									ЛПМ
дит	к	неопределенности в			описании	состояний
si t ,		i 1,k .	Для	ЛПМ	размерности		k	имеют	место	равенства
si t 1 si t ,			i 1,k	или в векторном виде
		s' t 1 s t ,
где s t – k 1-вектор состояний. Множество векторов s t									образует простран-
ство состояний ЛПМ.

118

14.2 Матричное описание ЛПМ

В соответствии с общей схемой (рис. 14.2) работу ЛПМ можно описать

следующими соотношениями

k	l
si t 1 aijsj t bijuj t ,		i				,	(14.1)
				1,k
j 1	j 1
k	l
yi t cijsj	t dijuj t , i				.		(14.2)
			1,m
j 1	j 1

Равенства (14.1), (14.2) можно представить компактно в векторно-матричной форме:

s t 1 As t Bu t ,				(14.3)
y t Cs t Du t ,				(14.4)
где A, B, C, D – k k,	k l,	m k ,	m l-матрицы, а u, y	– l 1,
m 1-векторы соответственно.

По соотношениям (14.3), (14.4) нетрудно выписать реакцию системы на любом шаге. В частности, при отсутствии входного сигнала (u t 0), выход-

ной сигнал на шаге t связан с начальным состоянием ЛПМ соотношением вида

y t Cs t CAs t 1 .... CAts 0 .

(14.5)

14.3 Каноническая и естественная нормальная форма ЛПМ

Аннулирующим многочленом для матрицы A является многочлен x та-

кой, что

A 0.

Аннулирующий многочлен минимальной степени со старшим коэффициентом,

равным единице, называется минимальным.

Многочлен

x det A Ex

называется характеристическим. По теореме Гамильтона-Кэли всякая матрица удовлетворяет своему характеристическому многочлену, т.е.

A 0.

119

Следовательно, характеристический полином всегда является аннулирующим,

но не обязательно минимальным.

Матрица

		0		E
A x						(14.6)
	0			1 k 1

называется канонической (сопровождающей) матрицей для многочлена\

x xk k 1xk 1 ... 1x 0 .

Многочлен x может быть разложен на элементарные множители:

x 1 x 2 x r x p1 x l1 p2 x l2 pr x lr .

Многочлены i x , i 1,r называют			элементарными делителями	матрицы
A x . С использованием указанного			разложения на элементарные	делители

может быть построена естественная нормальная форма матрицы:

	A		1	x	0			0
					A
A*			0			x		0		,	(14.7)
	x				2
			0		0		A
								r x

где A i x , i 1,r – матрицы вида (14.6).

14.4 Подобные и минимальные ЛПМ

Преобразование Aˆ PAP 1, где P – невырожденная матрица, называется

преобразованием подобия. Преобразование подобия не изменяет собственные значения матрицы, следовательно, подобные матрицы имеют одинаковые эле-

ментарные делители. В частности, если A x подобна некоторой матрице Aˆ с

элементарными делителями 1 x , , r x , то она также подобна естествен-

ной нормальной форме (14.7).

120