Теория Информации / 06 Информационные характеристики источников сообщений

1

6. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ ИСТОЧНИКОВ СООБЩЕНИЙ

6.1. Основные определения

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

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

Источник дискретных сообщений формирует дискретные последовательности из ограниченного числа элементарных сообщений.

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

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

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

R

pn (a,i ) представляет собой произведение одномерных распределений для всех моментов времени.

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

постоянного источника.

Генерируемое источником сообщение {Aj} представляет собой дискретный или непрерывный процесс, который затем преобразуется в сигнал {Sj}, передаваемый по каналу передачи информации. Полученный на приемной стороне сигнал {S*j}, в общем случае отличный от {Sj}, декодируется в сообщение {A*j}.

Информация, которую содержит любой процесс в системе связи, относится в конечном счете к выходному сообщению источника. Поэтому информация, содержащаяся в сообщении {A}, является собственной, а информация в сигналах {S}, {S*} и в декодированном сообщении {A*} является взаимной.

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

2

I(A)≥ I(A,S)≥ I(A,S )≥ I(A, A ).

Если рассматривать выходные сообщения {A} источника как ансамбль случайных событий с некоторым распределением вероятностей, образующих в сумме единицу, то для информационного анализа источника сообщений можно использовать соотношения для энтропии и количества информации, приведенные в 5-й главе.

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

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

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

			(X ) =	H(X )	.
		H				(6.1)
				< τ >
	Очевидно, поток информации зависит от					количества различных

символов, вырабатываемых источником, их длительности и вероятностных свойств источника. К примеру, если длительности всех символов одинаковы и равны τ0, то <τ> = τ0 и поток информации максимален, когда энтропия источника максимальна, а длительность τ0 минимальна.

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

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

Конкретизируем, что понимается под заданной точностью воспроизведения. Пусть x(t) некоторая заданная реализация, которую необходимо передать, а x’(t) – реализация, которая в действительности передается. Будем считать, что можно указать количественно, насколько х отличается от х’; другими словами, задается некоторая разумная мера отличия х от х’, ρ (x, x’). С помощью этой величины и определяется параметр ε точности воспроизведения. Сделать это можно различным образом; примерами могут служить следующие требования:

Mρ 2 (x, x′)≤ ε 2 ,			(6.2)
ρ(x, x′)≤ ε и т.д.			(6.3)
Простым случаем будет задание	ρ(x, x	) в виде разности	x(t)− x (t), тогда
	′		′

3

(6.2) означает ограничение на дисперсию ошибки воспроизведения, а (6.3) – на максимальное значение разности.

Рассматривая теперь процессы X = {x(t)} и X′ = {x′(t)}, мы можем утверждать, что они содержат информацию друг о друге. Будем оперировать с количеством информации I(x, x′), приходящимся в среднем на единицу времени.Это количество информации зависит не только от параметра точности ε, но и от характера статистической связи х и х’.

Определим теперь скорость создания информации как минимальное количество информации, которое необходимо (в единицу времени) для того, чтобы реализация х’(t) c заданной точностью ε воспроизводила реализацию х(t) (при заданном распределении р(х)):

	Hεα (x)=	min I(x, x′).		(6.4)
	{p(x′		x)}
Отметим, что численное значение величины Hεα (x) в общем				случае будет
различным для	разных определений параметра точности ε, в связи с чем и
введен индекс	α. Величину	Hεα (x) называют ε-энтропией		[7]. Удобной

интерпретацией ε-энтропии является представление ее с помощью пространства сигналов. Каждая точка этого пространства ставится в соответствие некоторой определенной реализации непрерывного процесса; функция ρ (х,х’), количественно характеризующаяразличие двух реализаций, рассматривается как расстояние между соответствующими точками.

Ниже будем рассматривать информационные характеристики источников дискретных сообщений.

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

информации несут его символы.
Таким образом,
R =	Hmax (X ) − H(X )	.	(6.5)
	Hmax (X )

Источник, избыточность которого R = 0, называют оптимальным. Все реальные источники имеют избыточность R ≠ 0.

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

4

Пусть сигнал длиной в п символов содержит количество информации I. Если это представление информации обладает избыточностью, то такое же количество информации I может быть представлено с помощью меньшего числа символов. Обозначим через п0 наименьшее число символов, необходимое для представления I без потерь. На каждый символ в первом случае приходится I1 = I/n бит информации, во втором Imах = 1/п0 бит. Очевидно, nI1 = n0I1max. В качестве меры избыточности R принимается относительное удлинение сигнала, соответствующее данной избыточности:

R =	n − n0	=1−	n0	=1−	I1	.	(6.6)
	n		n		I1max

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

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

Полная избыточность, обусловленная взаимосвязью символов

(обозначим ее Rp) и неэкстремальностью распределения (Rϕ), определяется соотношением

R = Rp + Rϕ – RpRϕ,
из которого следует, что при малых Rp и	Rϕ полная избыточность

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

R ≈ Rp + Rϕ.

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

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

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

5

источник, на выходе которого появляется последовательность букв из алфавита мощностью К = 32 (русский язык). При равновероятной и независимой передаче букв энтропия этого источника составляет \ogK = 5 бит/символ. В действительности в осмысленном тексте буквы передаются не хаотически и оказываются существенно связанными. Они, как известно, имеют различную вероятность, и вместе с тем появление последующих букв зависит от предыдущего текста. Результаты статистического анализа совокупности текстов русской художественной прозы позволяют сделать вывод, что энтропия такого источника принимает значения, не превосходящие 1,5 бит/символ. Еще более связанным (а потому и более легко запоминающимся) является стихотворный текст, где энтропия принимает еще меньшие значения [3].

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

1. В предположении, что русский алфавит содержит 32 буквы, максимальное значение энтропии определяется величиной Но(А) = 5 бит. Учет неравновероятности букв приводит к значению энтропии Н\(А) ≈ 4,35 бит.

2.Подсчет числа повторений различных двухбуквенных и трехбуквенных комбинаций в отрывке из романа Л.Н. Толстого, содержащего 30000 букв дал следующие значения энтропии художественного текста, учитывающие его избыточность, связанную с наличием статистической зависимости:

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

Приведенные выше результаты анализа показывают, что в английском языке избыточность явно превосходит 60 %. Как показали опыты в МГУ, избыточность литературного языка русской классической прозы близка к 80 % [3].

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

6.2. Понятие об эргодическом источнике сообщений

Объект, состояние которого определяется физическим процессом, протекающем во времени по заранее не известному закону, называется источником сообщений. Будем считать, что число возможных сообщений, вырабатываемых источником, конечно, и обозначать их символами x1, x2, …, xn. Заметим, что в данном случае различными символами могут обозначаться как элементарные сообщения типа «да» или «нет», так и более сложные, например, стандартные тексты, числа с заданным числом разрядов и т.п. Важно лишь, чтобы каждое сообщение, независимо от сложности его

6

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

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

Достаточно хорошей математической моделью дискретных источников, встречающихся на практике, являются так называемые эргодические источники. Назовем эргодическим источником r-го порядка такой источник, у которого вероятность появления некоторого символа xj зависит только от r предыдущих, т.е.

P(x j | xi(1) , xq(2) ,..., xn(r) ) = P(x j | xi(1) , xq(2) ,..., xn(r) , xn(r+1) ) .

Таким образом, в эргодическом источнике r-го порядка распределение вероятностей выбора символов p(xi) не остается постоянным, а зависит от того, какими были последние r символов сообщения. Эти последние r символов определяют некоторое состояние Sk источника (k = 1, 2, ..., т). Число всевозможных состояний источника r-го порядка, имеющего п различных символов, очевидно, определится выражением т = пr.

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

систем связи, машин для печати, перевода и др.

Энтропия эргодического источника. Соотношение

n
H(X ) = −∑P(xi )log P(x1)	(6.7)
i=1

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

7

найдено конечное число характерных состояний – S!, S2,... таких, что условная вероятность появления очередного символа зависит лишь от того, в каком из этих состояний находится источник. Вырабатывая очередной символ, источник переходит из одного состояния в другое либо возвращается в исходное состояние. Поскольку коррелятивная связь, как правило, распространяется на ограниченное число предыдущих знаков, для описания функционирования источника целесообразно использовать цепи Маркова.

Цепь Маркова порядка п характеризует последовательность событий, вероятности которых зависят от того, какие п событий предшествовали данному. Эти п конкретных событий определяют состояние источника, в котором он находится при выдаче очередного знака. При объеме алфавита знаков l число R различных состояний источника не превышает ln .

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

Когда коррелятивные связи имеют место лишь между двумя соседними символами, вероятность появления символа хi зависит лишь от того, какой символ был выработан до этого. Источник, генерирующий п разных символов – х1, х2, ....., хп, в этом случае может иметь п характерных состояний: S1 – после появления символа х1, S2 – после появления символа х2 и т.д. Например, для описания источника в случае п = 3 необходимо задать распределение вероятностей р(хi) и вероятностей переходов p(xi xj ) для всех

i, j. Вместо этого могут быть заданы вероятности всех возможных пар символов – р(хi,xj).

Если известны р(хi,xj),то р(хi) и p(xi |xj) могут быть найдены по известным формулам

p(xi )= ∑ p(xi , xj ),	p(xi		xj	)=	p(xi , xj )	.
j					p(xj )

Если коррелятивные связи имеются только между тремя символами, то вероятность появления символа хi зависит от того, какие два символа были выработаны перед этим, следовательно, число характерных состояний источника определяется числом различных пар хi, xj. Для описания такого источника должны быть заданы вероятности появления отдельных символов р(хi) и вероятности переходов p(xi xj , xh ), либо вероятности всех возможных

групп, состоящих из трех символов - p(xi , xj , xh ).

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

Обозначим через P(Sl) вероятность того, что источник находится в

z1, z2 , z3

8

состоянии Sl, причем

m
∑P(Sl ) =1.	(6.8)
l=1

Предположим, мы установили, что источник находится в состоянии Sl. У нас имеется неопределенность, из какого состояния Sk источник, выработав некоторый символ, перешел в состояние Sl. Так как вероятность состояния Sl зависит только от предыдущего состояния Sk и не зависит от того, в каких состояниях находился источник ранее (по определению состояния), неопределенность источника в состоянии Sk можно найти по формуле, аналогичной (6.7):

H(Sk ) = − ∑P(Sl / Sk )log P(Sl / Sk ).	(6.9)
l / k

Величина H(Sk) случайно меняется в зависимости от состояния источника, поэтому только среднее значение H(Sk) может характеризовать энтропию источника

m

m

H(X ) = ∑P(Sk )H(Sk ) = − ∑ ∑P(Sk )P(Sl / Sk )log P(Sl / Sk ) =

k =1 k =1l / k (6.10)

m

= ∑ ∑ P(Sl / Sk )log P(Sl / Sk ),

k =1l / k

где значок l/k у суммы означает, что производится суммирование по всем переходам из состояния Sk в Sl.

6.3. Связь между энтропией и числом различных последовательностей сообщений

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

Пусть, например, эргодический источник без памяти последовательно выдает знаки в соответствии с вероятностями 0,1; 0,3; 0,6. Тогда в образованной им достаточно длинной последовательности знаков мы ожидаем встретить в среднем на один знак z1 три знака z 2 и шесть знаков z3 . Однако при ограниченном числе знаков в последовательности существуют вероятности того, что она будет содержать;

только знаки z1 (либо z 2 , либо z3 ); только знаки z1 и один знак z 2 или z3 ; только знаки z 2 и один знак z1 или z3 ;

9

только знаки z3 и один знак z1 или z 2 ; только знаки z1 и два знака z 2 или z3 и т. д.

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

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

Теорема 1. Как бы ни малы были два числа ε > 0 и δ > 0 при достаточно большом М, все последовательности могут быть разбиты на две группы.

Одну группу составляет подавляющее большинство последовательностей, каждая из которых имеет настолько ничтожную вероятность, что даже суммарная вероятность всех таких последовательностей очень мала и при достаточно большом М будет меньше сколь угодно малого числа ε. Эти последовательности называют нетипичными. Говорят, также, что такие последовательности относятся к «маловероятной» группе реализаций.

Вторая группа включает типичные последовательности («высоковероятная» группа реализаций), которые при достаточно большом М отличаются тем, что вероятности их появления практически одинаковы, причем вероятность р любой такой последовательности удовлетворяет неравенству

	log		1
H(X ) −			P(C)			< δ,	(6.11)
		M

где Н(Х) – энтропия эргодического источника, определяемая по (6.10). Соотношение (6.11) называют также свойством асимптотической

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

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

2−M (H +δ) < P(C) < 2−M (H −δ) .

При М → ∞ δ → 0. Поэтому при достаточно большом М можно

положить
P(C) 2−MH .	(6.12)
Из (6.12) видно, что все последовательности С равновероятны и число
их равно
NT ≈ 1/p(C) или NT ≈ 2МН(Х) .	(6.12а)

Поскольку при М → ∞ источник сообщений с вероятностью, сколь угодно близкой к единице, выдает только типичные последовательности, неопределенность создания каждой такой последовательности с учетом их равновероятности составляет log(1/ p) . Тогда величина log(1/p)/M представляет собой неопределенность, приходящуюся в среднем на один знак. Конечно, эта величина практически не должна отличаться от энтропии

10

источника, что и констатируется соотношением (6.11).

Ограничимся доказательством теоремы для простейшего случая эргодического источника без памяти. Оно непосредственно вытекает из закона больших чисел, в соответствии с которым в длинной последовательности из М элементов алфавита l (z1, z2 ,..., zl ) , имеющих вероятности появления p1, p2 ,..., pl , содержится Мр1 элементов z1 , Мр2 элементов z2 и т.д.

Тогда вероятность р реализации любой типичной последовательности близка к величине

p = p p1M p p2M ...p piM .			(6.13)
1	2	i

Логарифмируя правую и левую части выражения (6.13), получаем

M

log p = M ∑ pi log pi

i=1

откуда (при очень больших M)

log (1/ p)/ M = H (X ).

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

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

Общее число всевозможных последовательностей длины М, вырабатываемых источником,

N = nM = 2M log n .

NT = 2M[H (X )−log n] ,

N

откуда при М → ∞ NT/N → 0, так как Н(Х) – log п ≤ 0. Однако хотя типичных последовательностей мало, но только они в основном вырабатываются источником, как то следует из теоремы.

Пусть, например,

а = 2, п = 100, Н = 2,75, т = 8. Тогда N = 8100 = 2300, N2 = 2100 ּ 2,75 = 2275.

Отсюда N2 = 2−25 ≈ (3.107 )−1 ,

N1

Т.е. к высоковероятной группе относится лишь одна тридцатимиллионная доля всех реализаций.

К.Шеннон показал, что рассмотренные свойства длинных последовательностей могут служить основанием для осуществления эффективного кодирования информации.

Целесообразно отметить, что в простейшем случае отсутствия статистической зависимости между элементами процесса свойство Е является простым следствием закона больших чисел [7].