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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

. (6.1)

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

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

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

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

(6.2)

и т.д. (6.3)

 

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

Рассматривая теперь процессы и , мы можем утверждать, что они содержат информацию друг о друге. Будем оперировать с количеством информации , приходящимся в среднем на единицу времени.Это количество информации зависит не только от параметра точности e, но и от характера статистической связи х и х^’.

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

(6.4)

Отметим, что численное значение величины в общем случае будет различным для разных определений параметра точности e, в связи с чем и введен индекс a. Величину называют e-энтропией [7]. Удобной интерпретацией e-энтропии является представление ее с помощью пространства сигналов. Каждая точка этого пространства ставится в соответствие некоторой определенной реализации непрерывного процесса; функция ρ (х,х^’), количественно характеризующаяразличие двух реализаций, рассматривается как расстояние между соответствующими точками.

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

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

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

. (6.5)

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

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

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

(6.6)

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

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

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

R = R_p + R _j– R_pR _j,

 

из которого следует, что при малых R_p и R _jполная избыточность приближенно равна сумме частных избыточностей:

 

R » R_p + R _j.

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

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

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

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

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

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

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

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

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

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

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

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

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

 

.

 

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

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

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

(6.7)

не может быть использовано для вычисления энтропии эргодического источника, так как при его получении не учитывались вероятностные связи между символами. Оно выражает энтропию источника, у которого символы x_i вырабатываются независимо друг от друга и, следовательно, не учитывает коррелятивных связей.Учет коррелятивных связей значительно упрощается для эргодического источника сообщений. Для такого источника может быть найдено конечное число характерных состояний – S_!, S₂,... таких, что условная вероятность появления очередного символа зависит лишь от того, в каком из этих состояний находится источник. Вырабатывая очередной символ, источник переходит из одного состояния в другое либо возвращается в исходное состояние. Поскольку коррелятивная связь, как правило, распространяется на ограниченное число предыдущих знаков, для описания функциони­рования источника целесообразно использовать цепи Маркова.

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

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

Когда коррелятивные связи имеют место лишь между двумя соседними символами, вероятность появления символа х_i зависит лишь от того, какой символ был выработан до этого. Источник, генерирующий п разных символов – х₁, х₂,....., х_п, в этом случае может иметь п характерных состояний: S₁ – после появления символа х ₁, S ₂ – после появления символа х ₂ и т.д. Например, для описания источника в случае п = 3 необходимо задать распределение вероятностей р(х_i) и вероятностей переходов для всех i, j. Вместо этого могут быть заданы вероятности всех возможных пар символов – р (х_i,x_j).

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

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

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

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

. (6.8)

 

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

 

. (6.9)

 

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

(6.10)

 

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