книги / Теория информации

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

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

/ (А) > I (A,S) >I(A,S")>1 (А,А *)

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

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

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

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

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

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

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

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

и т.д.

Простым случаем будет задание р2(хгт') в виде разности x(t)-x'(t), тогда (6.2) означает ограничение на дисперсию ошибки воспроизведе­ ния, а (6.3) - на максимальное значение разности.

Рассматривая теперь процессы X = {*(?)} и Х '= {*'(/)}, мы мо­ жем утверждать, что они содержат информацию друг о друге. Бу­ дем оперировать с количеством информации 7(х,х'), приходящимся в среднем на единицу времени. Это количество информации зави­ сит не только от параметра точности е, но и от характера статисти­ ческой связи х и х'.

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

Отметим, что численное значение величины Я “ (х) в общем случае будет различным для разных определений параметра точности е, в связи с чем и введен индекс а. Величину Н* (х) называют е-эн- тропией [7]. Удобной интерпретацией е-энтропии является пред­ ставление ее с помощью пространства сигналов. Каждая точка этого пространства ставится в соответствие некоторой определен­ ной реализации непрерывного процесса; функция р (х,х'), количес­

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

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

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

Таким образом,

(6.5)

^max ( - ^ Г)

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

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

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

R п - п 0 { п0 _ х

(6.6)

I шах

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

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

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

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

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

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

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

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

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

Н{(А) ~ 4,35 бит.

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

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

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

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

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

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

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

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

х.зависит только от г предыдущих, т.е.

Р(л}(|),х (2)..х,(г)) = / >(х (')| х (2)...х,(г),х,('и>).

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

т). Число всевозможных состояний источника r -го порядка, имеющего п различных символов, очевидно, определится выражением т = rf.

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

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

не может быть использовано для вычисления энтропии эргодического источника, так как при его получении не учитывались вероятностные связи между символами. Оно выражает энтропию источника, у кото­ рого символы xi вырабатываются независимо друг от друга и, следова­ тельно, не учитывает коррелятивных связей. Учет коррелятивных свя­ зей значительно упрощается для эргодического источника сообщений. Для такого источника может быть найдено конечное число характерных состояний - S}, S2,..., таких, что условная вероятность появления оче­ редного символа зависит лишь от того, в каком из этих состояний нахо­ дится источник. Вырабатывая очередной символ, источник переходит из одного состояния в другое либо возвращается в исходное состояние. Поскольку коррелятивная связь, как правило, распространяется на огра­ ниченное число предыдущих знаков, для описания функционирования источника целесообразно использовать цепи Маркова. Цепь Маркова порядка п характеризует последовательность событий, вероятности ко­ торых зависят от того, какие п событий предшествовали данному. Эти п конкретных событий определяют состояние источника, в котором он находится при выдаче очередного знака. При объеме алфавита знаков / число R различных состояний источника не превышает /"

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

Когда коррелятивные связи имеют место лишь между двумя сосед­ ними символами, вероятность появления символа х. зависит лишь от того, какой символ был выработан до этого. Источник, генерирующий п разных символов - х ,, х2, .... , хп, в этом случае может иметь п харак­ терных состояний: St - после появления символах,, S2- после появле­ ния символа х2и т.д. Например, для описания источника в случае и = 3 необходимо задать распределение вероятностей p(xi) и вероятностей переходов р{хрс) для всех i,j. Вместо этого могут быть заданы веро­ ятности всех возможных пар символов - p(x.jc ).

Если известны />(х.,х.),то р(х) и р{х.|х.) могут быть найдены по из­ вестным формулам

Если коррелятивные связи имеются только между тремя символами, то вероятность появления символа х. зависит от того, какие два символа были выработаны перед этим, следовательно, число характерных состо­ яний источника определяется числом различных пар х, ху. Для описания такого источника должны быть заданы вероятности появления отдельных символов р(х) и вероятности переходов /?(х|х, хЛ) либо вероятности всех возможных групп, состоящих из трех символов -p(xfxf хЛ).

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

Обозначим через P(S} вероятность того, что источник находится в состоянии St, причем

m

(6.8)

/=i

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

l/k

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

т т

Я(Х) = £ P(.s„mst)= -Z I ,n S k)P(S,/S^ogP^/S,) =

где значок 1/к у суммы означает, что производится суммирование по всем переходам из состояния Skв Sr

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

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

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

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

только знаки z, и два знака z2 или z3 и т. д.

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

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

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

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

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

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

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

тельностей

2-ми*®<р(с)< 2 W(W+S).

При М —►оо 8 —> 0. Поэтому при достаточно большом М можно положить

Поскольку при М —> оо источник сообщений с вероятностью, сколь угодно близкой к единице, выдает только типичные последовательнос­ ти, неопределенность создания каждой такой последовательности с