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

Введя в пространстве состояний преобразование координат s t Ps t и

умножив (14.3) слева на P, систему (14.3) (14.4) представим в виде

Ps t 1 PAP 1					s	t PBu t ,			(14.8)
y t CP 1			s	t Du t ,					(14.9)
Далее введя обозначения
ˆ	1			ˆ		ˆ	1	,	ˆ
A PAP		, B PB, C CP							D D,

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

Ps t 1 s t 1 ,

уравнения (14.8), (14.9) можно переписать в виде
					ˆ			ˆ
	s t 1								(14.10)
			As t					Bu t ,
		ˆ					ˆ		(14.11)
y t Cs t Du t .

Системы (14.3), (14.4) и (14.10), (14.11) описывают различные, но совпа-

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

Минимальная ЛПМ может быть определена в результате выполнения сле-

дующей последовательности шагов [2].

1.Строится так называемая диагностическая матрица (наблюдаемости)

K C CA CAk 1 T .

2.Из линейно независимых строк диагностической матрицы формируется

матрица			T и осуществляется преобразование подобия:	ˆ	1	,	ˆ
				A TAT			B TB,
ˆ		1	ˆ
C CT			, D D.
Результатом преобразования будет минимальная ЛПМ.
	Если ЛПМ с матрицей A имеет подобную ЛПМ с матрицей					ˆ	, то она
					A
имеет и естественную нормальную форму A* . Каждая подматрица A							i x	мат-

рицы A* , имеющая вид (14.6), соответствует некоторой канонической ЛПМ.

121

Каноническая форма является минимальной ЛПМ. Следовательно, в ре-

зультате преобразования подобия исходная ЛПМ всегда может быть представ-

лена в виде совокупности ЛПМ, каждая из которых соответствует элементар-

ному делителю i x , i 1,r в разложении многочлена x .

14.5 Понятие простой автономной ЛПМ

Рассмотрим каноническую (минимальную) ЛПМ, имеющую сопровож-

дающую матрицу вида (14.6) при u t 0. ЛПМ с нулевым входным воздейст-

вием: называются автономными. Выходные последовательности на всех выхо-

дах ЛПМ, являющихся компонентами вектора y, в этом случае формируются по соотношению (14.5) под действием начальных условий.

Для автономной ЛПМ можно выполнить преобразование подобия для ка-

ждого отдельного выхода (компонента вектора y) исходной ЛПМ. При этом из ЛПМ с m выходами будет получено m различных ЛПМ с одинаковыми матри-

цамиA и различными матрицами C, представляющими собой отдельные стро-

ки исходной m n– матрицы C.

Каждая из построенных таким образом m схем называется простой авто-

номной ЛПМ (простой АЛПМ), а матрица A x каждой простой АЛПМ имеет

вид (14.6) и является сопровождающей для многочлена обратной связи

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

Матричные соотношения, описывающие соответствующую матрице A x и

указанному многочлену x						простую автономную ЛПМ при C 1,0, ,0 ,
имеют вид:
s1 t 1				0		E	s1 t
									,
	t
sk		1		0	1 k 1 sk			t

s1 t y t 1,0,...,0 .

sk t

122

Приведенные равенства можно представить в виде схемы, показанной на рисунке 14.3.

Непосредственно по схеме можно за-

писать соотношение для формирования вы-

ходной последовательности простой

	АЛПМ:	Рис. 14.3 – Схема простой
		АЛПМ
	yt k k 1yt k 1 1yt 1 0 yt .
		(14.12)

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

нейной комбинацией начального состояния АЛПМ.

14.6 Формирование разрешенных комбинаций циклического

кода с помощью АЛПМ

В разделе 12.5 мы рассмотрели два способа формирования комбинаций и декодирования циклических кодов. Рассмотрим еще один способ, который наи-

более удобно реализуется с помощью АЛПМ.

Определим многочлен обратной связи x как частное от деления xn 1

на образующий многочлен. В силу свойств g x такой целый полином сущест-

вует:

	x	xn 1		xk k 1xk 1	... 1x 0 .	(14.13)
		g x

Многочлен (14.13) называют также генераторным полиномом. Для этого поли-

нома можно построить сопровождающую матрицу A x вида (14.6) и соответ-

ствующую ей АЛПМ.

Если начальное состояние АЛПМ (рисунок 14.3) соответствует исходной информационной последовательности, на выходе будет сформирована комби-

нация, первые k символов которой информационные, а следующие за ними n k являются линейной комбинацией предыдущих символов:

	k 1
aj k	iаj i,	j		.	(14.14)
			1,n k
	i 0
					123

где i – двоичные коэффициенты многочлена обратной связи АЛПМ (14.13) (генераторного многочлена). Таким образом, с использованием АЛПМ может быть построен систематический циклический код.

14.7 Образующая матрица АЛПМ

Если x – многочлен обратной связи (генераторный многочлен), удов-

летворяющий (14.13), то образующий многочлен степени m n k определяет-

ся как

g x xn 1 gmxm ... g1x g0 .

x

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

		gm gm 1			g0	0	0
				gm	gm 1	g0
M	n,k		0				0 .
			0
					0 gm gm 1 g0

Разделим образующую матрицу Mn,k на два блока M M1 M2			так, что-
бы M1 была квадратной. В силу неприводимости многочлена g x			ее диаго-
нальные элементы отличны от нуля, следовательно, матрица M1 является не-
вырожденной.
Последовательность информационных символов Ak можно представить
как линейную комбинацию строк матрицы M : A	k	vT M , откуда
1		1
vT AkM11 .			(14.15)

С другой стороны, избыточный код является той же линейной комбинацией строк матрицы M:

An vT M vT M1 M2 .

Подставляя в это равенство vT из (14.15) имеем

124

An AkM11 M1 M2 Ak E M11M2 .

Матрица M E M11M2 E Pk,n k является образующей матрицей АЛПМ с

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

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

ний, посвященных собственно теории кодирования. Цель этого раздела состоя-

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

125

Лекция 15

Обнаружение и различение сигналов

15.1 Постановка задачи обнаружения сигналов

при наличии помех

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

мума полезной информации. Для этого последовательно решаются, по крайней мере, две задачи [9]:

1)обнаружение (принятие решения о наличии сигнала);

2)восстановление (определение параметров сигнала).

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

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

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

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

тов компонентов векторов полезного сигнала X и помехи Ξ. Ясно, что по при-

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

p XY .

В общем случае в соответствии с формулой Байеса апостериорная плот-

ность вероятности вектора X определяется как

	w X Y		w X w Y X	,	(15.1)
			w Y
	где w X	– априорная плотность вероятности вектора			X, w Y X – условная
	плотность	вероятности вектора		Y при условии, что	вектор X известен, а

w Y w X w YX dX – безусловная плотность вероятности вектора Y, где

Vx

VX – пространство передаваемого сигнала.

Если вектор X имеет конечное число значений, по аналогии с (15.1)

126

p X Y	p X w Y X		p X w Y X	,		(15.2)
	w Y		N
			p xj w Y xj
			j 1
где p X – априорная, а p X Y		– апостериорная вероятности вектора X.
Таким образом, для определения апостериорной плотности w X Y						и/или
вероятности p X Y необходимо знать априорные плотность					w X и/или ве-

роятность p X , а также условную плотность w YX , которая при известном

(измеренном) Y зависит только от X и обозначается L X :

w Y X L X .

(15.3)

Функция L X называется функцией правдоподобия. Эта функция может иметь конечное (в случае дискретного X) или бесконечное (в случае непрерывного

X) число значений.

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

взаимно исключающих альтернатив (гипотез): гипотезы H1 о том, что X x1 –

сигнал есть, или гипотезы H0 о том, что X x0 – сигнал отсутствует. В матема-

тическом отношении эта задача эквивалентна задаче оптимального разбиения пространства принимаемых сигналов V на области v1 и v0 . Если принятый век-

тор Y окажется в области v1, принимается гипотеза H1, если же он окажется в области v0 , принимается гипотеза H0 .

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

функция (отношение) правдоподобия:

	L x1			w Y x1
						.	(15.4)
	L x			w Y x
0			0

Рассмотрим различные критерии принятия решений, формулируемые в терми-

нах отношения правдоподобия (15.4).

127

15.2 Обнаружение по критерию максимального правдоподобия

По этому критерию наиболее правдоподобным считается то значение X,

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

ружения рассматривается две альтернативы, существо дела сводится к сравне-

нию L x1 и L x0 . При этом решающее правило в терминах отношения прав-

доподобия принимает вид:

	если	L x1			1, то X x ,	(15.5)
		L x0
				1
	если	L x1			1, то X x ,	(15.6)
		L x0
				0

Важное достоинство критерия максимума правдоподобия состоит в том, что в данном случае не требуется знание априорных вероятностей p x1 , p x0 сиг-

нала X.

15.3 Обнаружение сигналов по критерию максимума

апостериорной вероятности

В соответствии с этим критерием сравниваются значения апостериорных вероятностей p x1 /Y и p x0 /Y :

	если	p x1	/Y	1, то X x1	,	(15.7)
		p x0 /Y
	если	p x1	/Y	1, то X x0 .		(15.8)
		p x0	/Y

С использованием формулы Байеса (15.2) и равенства (15.3) отношение апостериорных вероятностей выражается через отношение правдоподобия:

p x1 /Y		p x1 L x1				p x1		.
p x /Y		p x	L x			p x
0		0	0			0

При этом критерий можно записать следующим образом:

	если	p x1	1, то X x ,	(15.9)
		p x0
			1

128

если	p x1			1, то X x .				(15.10)
	p x0						0
Решающее правило можно также представить в виде:
если			p x0			, то X x ,		(15.11)
			p x1			0	1
если		p x0					, то X x ,	(15.12)
			p x1			0	0

где 0 – пороговое значение отношения правдоподобия. Критерий максимума апостериорной вероятности применяется в случае, когда известны априорные вероятности p x1 , p x0 сигнала X.

15.4 Информационный критерий обнаружения

С точки зрения теории информации наиболее предпочтительно то значение

X, относительно которого в Y содержится больше информации:

I Y,x		I			Y,x log					2	p x log				2	p x	/Y
1					0						1					1
log			2	p x log		2			p x	/Y							(15.13)
					0				0
log2		p x1 /Y p x0							log2			p Y/x1		log2 .
		p x			/Y p x							p Y/x
				0	1						0

В соответствии с информационным критерием (15.13), если логарифм отноше-

ния правдоподобия положителен, следует принять гипотезу H1 (X x1), если отрицателен или равен нулю – H0 (X x0 ).

Нетрудно заметить, что этот критерий совпадает с критерием максималь-

ного правдоподобия (15.5), (15.6).

15.5 Обнаружение по критерию Неймана-Пирсона

При решении задачи обнаружения сигналов могут иметь место ошибки двух типов:

1)ошибка первого рода – «ложная тревога» (при отсутствии сигнала приня-

та гипотеза H1 – X x1), вероятность которой определяется как

129

w Y/x0 dY;	(15.14)
v1

2)ошибка второго рода «пропуск сигнала» (при наличии сигнала принята гипотеза H0 – X x0 ), вероятность которой

w Y/ x1 dY.	(15.15)
v0
При этом общая вероятность ошибочного решения
pош p x0 p x1 .	(15.16)

В соответствии с критерием Неймана–Пирсона наилучшим считается ре-

шение, при котором

w Y/ x1 dY min,

v0

при условии, что

w Y/x0 dY ,

v1

где – заданная величина.

Рассмотрим решение указанной задачи для простейшего случая, когда

Y y – скаляр. При этом

0

w y/x0 dy, w y/ x1 dy,

0

0

а функция Лагранжа принимает вид

0
F w y/x1 dy w y/x0 dy .
0
	0

Необходимые условия экстремума F 0 0,		F 0
w 0	/x1 w 0 /x0 0,	(15.17)
w y/x0 dy .		(15.18)
0
В соответствии с (15.17)
w 0	/x1 w 0 /x0 .	(15.19)
130