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

Упражнение

223

ричного канала без памяти, в котором ошибки при приеме различных символов являются статистически независимыми. Для такого

канала вероятность получения r ошибок при передаче n символов подчиняется биномиальному закону [23]

Pn (r) Cnr pошr 1 pош n r .

Из этого выражения можно найти такие характеристики, как вероят-

ность правильного приема блока из n символов Pn (0) (1 pош )n , вероятность приема блока, содержащего хотя бы одну ошибку

Pn (r 1) 1 Pn (0) 1 (1 pош )n , вероятность появления в блоке

m и более ошибок и т.д.

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

символом. Более сложной является марковская модель порядка N ,

в которой состояние канала определяется N последними принятыми символами (последовательность состояний канала представляет собой N -связную цепь Маркова101).

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Что такое канал связи? Как описать канал?

2.Существуют ли линейные стационарные каналы?

3.Что такое многолучевость?

4.Как описываются дискретные каналы?

5.Что такое дискретно-непрерывный канал? Как он описывается?

6.К каким последствиям приводит нелинейность канала?

УПРАЖНЕНИЕ

Выведите формулу определения вероятности появления в блоке из n символов m и более ошибок для стационарного симметричного дискретного канала без памяти.

101Андрей Андреевич Марков (1856 – 1922) – выдающийся русский математик, известен своими достижениями в области теории вероятностей и др.

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

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

8.1.ОСНОВНЫЕ ПОНЯТИЯ И ТЕРМИНЫ

нформация относится к предельно широким Ипонятиям, которым трудно или невозможно дать строгое определение, поэтому приходится прибегать к интуи-

ции, объясняя термин «информация» через синонимичные понятия

– «данные», «сведения» и т.п. Однако для решения инженерных задач требуется количественное определение информации. В теории и технике связи в настоящее время используется определение количества информации, предложенное К. Шéнноном102.

Для введения этого определения необходимо абстрагироваться от физического воплощения источника и семантического (смыслового) содержания сообщений. Дискретный источник сообщений то-

гда	полностью		определяется набором символов (алфавитом)
	1,...,	K	( K – объем алфавита) и распределением вероятно-
стей P(a) ,		заданным на множестве всех возможных последователь-

ностей символов a (a1,...,an ) , ai произвольной длины. В про-

стейшем случае источника без памяти символы в последовательности являются независимыми, и распределение P(a)

полностью определяется набором априорных вероятностей отдельных символов p( k ), k 1,..., K . В более сложных моделях ис-

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

102Клод Элвуд Шеннон (1916 – 2001) – выдающийся американский математик и инженер, один из основоположников теории информации.

разных в

8.1. Основные понятия и термины

225

«я», «й» и т.п. Далее, как правило, рассматриваются источники без

памяти.

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

Канал связи (дискретный) формально описывается входным и выходным алфавитами X x1,..., xL и Y y1,..., yM

общем случае объемов L и M и условным распределением вероятностей P(y | x) , заданным для всех возможных последовательно-

стей y и x произвольной длины. Условное распределение P(y | x)

описывает вероятностный механизм действия помех в	канале.
В простейшем случае канала без памяти распределение	P(y | x)

полностью определяется набором условных вероятностей для всех пар отдельных символов P(y j | xi ) , xi X, y j Y .

Информация, согласно современным представлениям, – это свойство сообщения снимать (или уменьшать) неопределенность относительно исхода некоторого случайного опыта (например, относительно переданного символа). Действительно, во всех реальных случаях получатель сообщения что-то знает о некотором объекте или событии до опыта («a priori»), но ему известно не все, иначе не было бы необходимости передавать сообщение. Например, футбольный болельщик знает, с кем сегодня играла его любимая команда, но не знает, кто победил. Таким образом, до опыта (до получения сообщения) налицо некоторая неопределенность. После приема сообщения неопределенность исчезает (или, по

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

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

не получаем.

Количественная мера информации должна удовлетворять следующим интуитивно очевидным требованиям:

если исход опыта единствен (достоверное событие), то количество информации в сообщении о нем должно быть равно нулю;

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

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

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

равняться сумме количеств информации в отдельных сообщениях

(аддитивность информации).

Мера неожиданности сообщения a в виде 1/ P(a) удовлетворя-

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

двух независимых сообщений a1 и a2 равна, очевидно, 1/[P(a1)P(a2)]. Чтобы обеспечить выполнение всех требований,

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

	logm	1	logm P(a) .
		P(a)

Основание логарифма может быть произвольным и определяет

лишь масштаб (единицу измерения). Общепринятым является основание 2, при этом единица называется битом103. Учитывая это, в

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

Поскольку событие, состоящее в выдаче сообщения a , случайно и происходит с вероятностью P(a) , количество информации,

связанное с этим сообщением, также является случайной величиной. Введем величину

I( i ) log p( i ) ,

называемую собственной информацией символа i .

Информационная производительность дискретного источника характеризуется средним количеством информации на символ, ко-

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

вол и называемое энтропией дискретного источника			, в виде
K
H ( ) p(	k )log p(	k ) .	(8.1)
k 1

103В литературе упоминаются единицы нат и хартли, соответствующие основаниям логарифма е и 10.

8.2. Энтропия и информация

227

Пример 8.1. Предположим, что передается сообщение о карте, вытащенной наугад из идеально перетасованной колоды в 32 карты (вероятность вытащить любую карту равна при этих условиях 1/32). Очевидно, это сообщение несет количество информации, равное 5 битам. Если это сообщение разбить на два так, что вначале сообщается масть карты, а затем ее достоинство, то это количество информации будет передано частями – сначала 2 бита, затем еще 3. (Убедитесь, что это действительно так!) ◄

8.2. ЭНТРОПИЯ И ИНФОРМАЦИЯ

Рассмотрим основные свойства энтропии.

1. Энтропия любого источника неотрицательна H ( ) 0 .

Это следует из того, что вероятность любого события неотрицательна и не превосходит единицы. Энтропия источника равна нулю в том случае, если один из символов имеет вероятность 1, а остальные – 0. Неопределенность, возникающая вследствие того, что

log p при p 0 , может быть раскрыта с применением правила Лопиталя:

lim( plog p) lim log1/ p		lim	log q	lim	1/ qloge	0 .
p 0	p 0 1/ p	q	q	q	1
2. При заданном объеме алфавита K				энтропия максимальна,

если все символы равновероятны p(	k ) pk 1/ K .
Доказательство состоит в нахождении условия максимума эн-
K
тропии при ограничении pk 1 .	Задачу поиска экстремума
k 1
функции при наличии ограничения можно свести к обычному на-

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

( p ,..., p		K		log p	K			,
		) p			p		1
1	K	k 1	k	k	k 1	k

104Этот метод называется методом неопределенных множителей Лагранжа.

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

где – неопределенный множитель Лагранжа, и запишем условие достижения ее экстремума

		K			K
								0 , i 1, K .
	p			log p	p		1
pi		k 1	k	k	k 1	k

Решая уравнения относительно pi , получаем

1 1

ln pi

1

0 ,

pi ln 2 p

0

ln 2

ln pi

ln 2

1

i

откуда pi

exp( ln2 1)

независимо от i , а это и означает равно-

вероятность символов. Максимальное значение энтропии равно

Hmax log K . В частности, при

K 2 энтропия максимальна при

p1 p2 1/ 2 и равна 1 биту. Таким образом, 1 бит – это количе-

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

Два источника	и , рассматриваемых в совокупности, ха-
рактеризуются совместной энтропией

H( , ) p(	i ,	j )log p( i ,	j ) ,
i j

где p( i , j ) – совместная вероятность символов; суммирование проводится по всем возможным значениям индексов. Совместная

энтропия характеризуется свойством коммутативности H (

, )

H (

, ), что прямо следует из равенства p(

i ,

j ) p( j ,

i ) .

Используя выражение для совместной вероятности, перепишем

совместную энтропию в виде

H(

, ) p(

i ) p(

j |

i ) p(

j |

i )log p(

i )

i

j

p(

i ) p(

j |

i )log p(

i ) p(

i ) p(

j |

i )log p( j |

i ) .

i

j

i

j

Заметим, что

p( i ) p(

j |

i ) p(

i ,

j ) p( i ) , тогда пер-

j

j

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

p(

i )log p(

i ) H(

) , а второе

i

слагаемое представляет собой условную энтропию

p( i ,

j )log p(

j |

i ) H(

|

) .

i

j

8.2. Энтропия и информация		229
Таким образом, совместная энтропия
H( , ) H( ) H( |	) H( ) H( | ) .	(8.2)
Если источники статистически независимы, то
H( , ) H(	) H( ) ,

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

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

ется условным распределением	P(	|	) . Можно считать, что на
входе действует источник с алфавитом			и энтропией H( ) , а на
выходе – источник с алфавитом	и энтропией H (			) , причем эти
источники статистически связаны.
Условное распределение P(	|	)	описывает	вероятностную

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

Количество информации в символе				j относительно символа					i
определяется выражением			p(	i |		j )
I(	i ;	j ) log					.	(8.3)
			p(		i )
В самом деле, если символы независимы, то p( i |								j ) p(	i )
и I ( i ; j ) 0 (символ	j	не несет информации о символе							i ).

И, наоборот, при жесткой (детерминированной) связи между сим-

волами

i

и

j ,

очевидно,

p( i |

j ) 1, поэтому

I(

i ;

j ) log

1

I(

i ) , т. е. количество информации в симво-

p(

i )

ле

j относительно символа i равно собственному количеству

информации в символе

i (или, что эквивалентно, в символе j ).

Используя известные формулы для совместных и условных ве-

роятностей, легко видеть, что

I( i ;

j ) log

p( i | j ) p( j )

log

p(

i , j )

p( i ) p( j )

p(

i ) p( j )

230				8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ
log	p( j |	i ) p( i )		log	p( j |	i )		I( j ; i ) .
	p( i ) p( j )				p(	j )
Количество информации в символе						j	относительно символа
i равно количеству информации в символе								i	относительно сим-
вола j . Поэтому величина I (				i ; j ) I (		j ;		i )	называется взаим-

ной информацией указанных символов.

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

сообщения. Иными словами, представляет интерес вопрос: какова

энтропия входного алфавита при условии наблюдения выходных символов? Очевидно, что чем меньше эта условная энтропия, тем

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

H ( |	L M
	) p(	i ,	j )log p( i | j ) .	(8.4)
	i 1 j 1

Пример 8.2. Предположим, что на входе двоичного канала действует источник с равновероятными символами 0 и 1, а искажения символов при передаче происходят с некоторыми вероятно-

стями p0 p(y 1| x 0) и p1 p(y 0| x 1) .
Найдем количество информации в выходном символе относи-
тельно входного. Безусловные вероятности выходных символов
p(y 0) p(y 0|x 0) p(x 0) p(y 0|x 1) p(x 1) 1 p0 p1						;
				2
p(y 1) p(y 1|x 0) p(x 0) p(y 1|x 1) p(x 1) 1 p1 p0 .
				2
Взаимная информация переданного символа				x 0 и наблю-
даемого символа y 0 равна
I(0;0) log	p(y 0 | x 0)	log	2(1 p0 )		,
	p(y 0)		1 p p
			0	1

8.2. Энтропия и информация

231

аналогично взаимная информация переданного символа x 1 и наблюдаемого символа y 0 равна

I(1; 0)		log	p(y 0 | x 1)		log	2 p1
			p(y 0)			1 p	p .
						0	1

Так же находятся два оставшихся количества информации:

I(0;1)

log

p(y 1| x 0)

log

2 p0

,

p(y 1)

1 p

p

1

0

I(1;1) log

p(y 1| x 1)

log

2(1 p1)

.

p(y 1)

1 p

p

1

0

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

ется вероятностями p0 p1 0 . Тогда, очевидно, I(0; 0) I(1;1) 1 . Поскольку энтропия источника равна 1 биту и

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

Второй частный случай имеет место при p0 p1 0.5 . Тогда I(0; 0) I(1;1) I(0;1) I(1; 0) 0 и канал не передает информации

(такая ситуация называется «обрывом канала»). ◄

Рассмотрим основные свойства условной энтропии.

1. Если источники сообщений и являются независимыми, то условная энтропия равна безусловной:

			H( | ) H(				) ,	H ( | ) H ( ) .
	Действительно,				если		источники		независимы,	то
p(	i |	j ) p(	i )	при всех i, j . Тогда выражение (8.4) можно пе-
реписать в виде
			L M					L	M
H (		| ) p(			i ,	j )log p(		i ) log p( i ) p( i ,		j ) .
			i 1 j 1					i 1	j 1
		M		j ) p(	i ) , откуда немедленно следует
	Но	p( i	,
		j 1
	|	L		i )log p(		i )
H (		) p(					H ( ) , что и требовалось доказать.
		i 1

232	8. ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ
2. Если символы источников	и жестко связаны, то услов-

ная энтропия равна нулю. В самом деле, при жесткой связи в выражении (8.4) некоторые условные вероятности равны 1, а остальные 0. Но как было показано выше, в этом случае сумма равна нулю.

Для условий примера 8.2 жесткая (детерминированная) связь входных и выходных символов соответствует вероятностям оши-

бок p0 p1 0 (или p0 p1 1).

3. Условная энтропия входного алфавита относительно выходного характеризует передаваемую по каналу информацию следующим образом. Если энтропия входного источника в отсутствие

передачи равна H( ) , а после приема выходного символа она становится равной H ( | ) , то, очевидно, среднее количество передаваемой информации на символ равно разности

I( , ) H( ) H( | ) .

Величина I( , ) представляет собой взаимную информацию

входа и выхода.

Если потери информации отсутствуют (канал без помех), то условная энтропия источника после передачи равна 0, количество

передаваемой информации равно H( ) . Величина H ( | ) , та-

ким образом, характеризует потери информации в канале и назы-

вается ненадежностью [10].

Заметим, что из выражения (8.2) для совместной энтропии следует

	H( ) H(		|	) H(	) H(	|	) ,
поэтому
I( ,	) H(	) H(	|	) H(	) H(	|	) I(	, ) . (8.5)
При очень высоком уровне помех условные энтропии равны
безусловным	( H(	| ) H(		) , H (	| ) H (		) ) и	количество

информации, передаваемой по каналу, становится равным нулю.

4. Из	выражения	для	совместной энтропии H ( |	)
H ( ,	) H( ) и	H( |	) H( , ) H( ) . Подставляя	эти

выражения в (8.5), получаем среднее количество передаваемой информации на символ

I( , ) I( ,

) H(

) H(

) H( , ) .

(8.6)