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

 

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

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

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

(3.1)

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

 

(3.2)

 

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

 

(3.3)

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

Таким образом, энтропия Н(Х) есть среднее значение (математическое ожидание) энтропий всех характерных состояний источника.

В случае, когда символы источника независимы, имеется лишь одно состояние S1, вероятность которого P(S1) = 1. При появлении символа xi источник вновь возвращается в состояние S1 (рис. 3.1), и при этом P(S1/S1) = P(xi), следовательно,

 

что совпадает с (2.14).

Если коррелятивные связи имеются между двумя соседними символами, то P(Sk) = P(xk) и P(Sb/Sk) = P(xb/xk).

Из (3.3) тогда получим

 

(3.4)

 

Источник, генерирующий n разных символов – x1, x2, ... , xn, в этом случае может иметь n характерных состояний. Пример такого источника для случая n = 3 приведён на рис. 3.2.

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

P(Shj) = P(xh,xj) и P(Sji/Shj) = P(xi/xh,xj) .

 

Из (3.4) получаем

(3.5)

 

Чисел характерных состояний для этого случая столько, сколько имеется различных пар (xi,xh). Таких пар, очевидно, n2 .

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

 








Дата добавления: 2016-02-04; просмотров: 1343;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.01 сек.