Файл: Бовбель, Е. И. Элементы теории информации.pdf

Р е ш е н и е . Подставим (1.31) в (1.26). Получим

со

dx -|-

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

Задача 5. Имеется два источника флюктуирующего напряжения с одинаковой энтропией, но разными зако­ нами распределения вероятностей: первый — гауссовским законом, второй— равновероятным. Сравнить их мощ­ ности.

Р е ш е н и е . Как мы знаем, энтропия источника с га­ уссовским законом распределения вероятностей

/-/Е(Л') = log \/2пеаГі

(Ь—а )— ширина интервала возможных напряжений вто­ рого источника.

По условию задачи, источники обладают одинаковой информативностью, т. е.

\/2тс 6 ог b’— а.

По определению, дисперсия для равновероятного распре­ деления

°і = (’ (* — < * » 2 w(x) dx =

00

44

Г Л А В А 2

ИСТОЧНИКИ ДИСКРЕТНЫХ СООБЩЕНИЙ

§ 1. Эргодические источники и их энтропия

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

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

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

46

ч

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

Соотношение

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

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

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

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

H(Sk) = - 2 /> С З Д ) log Р (S/АЗД. .

1\к

47

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

ч

т

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

Задача 1. Сколько различных последовательностей, со­ держащих по 5 символов, можно составить из алфавита, содержащего два различных символа?

волов Х\ и ,ѵ2, вырабатывает последовательность хь х2>х% Хи Хо, хь Х2>Л'і ... Вероятностныесвязи в данной последова­

стояний источника равно 23= 8 . Выпишем их, нумеруя со­ стояния соответствующими индексами:

Чтобы установить, в каком состоянии находится источ ник, необходимо подождать, пока он выработает три сим вола. Поэтому в последовательности Х\Х2Х2Х\Х2Хі*2*і...

первым состоянием является <Si22. Затем источник после появления символа х\ переходит в состояние S22i и таг далее. Получается следующая последовательность состоя ний, проходимая источником:

48

Задача 3. Показать, что при отсутствии вероятностной связи между символами из формулы (2.3) следует фор­ мула (2.1).

Р е ш е н и е. Когда символы источника независимы, как следует из равенства

PiXj/xW, ..., *<'>) = P{Xj),

у источника имеется лишь одно состояние So, вероятность которого, на основании (2.2),

Поэтому при появлении символа хс источник вновь воз­ вращается в состояние So, при этом

Подставляя (2.4) и (2.5) в (2.2), получаем

# ( * ) = ■ - 2 Р (хі) log Р(хД *= ■

£=1 /=1

ъ в

= - 2 P(Xi) log P(Xi)„

1=1

так как число различных переходов из So в S0 равно чис­ лу различных символов источника.

Задача 4. Получить из (2.3) формулы для энтропии эргодического источника, когда вероятностные связи име­ ют место между: а) двумя ^символами; б) тремя; в) че­

а вероятность перехода из состояния S k в St