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

p(xi /xi-1,xi-2, ... xi-n)= p(xi /xi-1,xi-2, ... xi-n, ... xi-n-c), (7)

где с - произвольное положительное число.

Если объем алфавита источника равен k, а число связанных букв, которые необходимо учитывать при определении вероятности очередной буквы, равно порядку источника n, то каждой букве может предшествовать M=kn различных сочетаний букв (состояний источника), влияющих на вероятность появления очередной буквы xi на выходе источника. А вероятность появления в сообщении любой из k возможных букв определяется условной вероятностью (7) с учётом предшествующих букв, т.е. с учётом M возможных состояний. Эти состояния обозначим как q1, q2 ... qM.

Сказанное поясним двумя простыми примерами.

Пример 1. Пусть имеется двоичный источник (объём алфавита k=2) -например, источник, выдающий только буквы а и б ; порядок источника n=1. Тогда число состояний источника M=kn=21=2 (назовём их состояния q1 и q2). В этом случае вероятности появления букв а и б будут определяться следующими условными вероятностями:

p(а/q1=а), p(а/q2=б), p(б/q1=а), p(б/q2=б),

где q1=а - 1-е состояние q1,

q2=б - 2-е состояние q2.

Вероятности состояний источника равны p(q1)=p(a), p(q2)=p(б).

Пример 2. Пусть по-прежнему k=2 (буквы а и б), однако число связанных букв n=2. Тогда M=22=4 (4 возможных состояния: (а, а)=q1, (а, б)=q2, (б,а)=q3, (б, б)=q4 .

В этом случае имеем дело со следующими условными вероятностями:

p(а/а,а); p(а/а,б); p(а/б,а); p(а/б,б); p(б/а,а) . . . и т.д.

Вероятности состояний определяются равенствами p(q1)=p(a,a), p(q2)=p(a,б), p(q3)=p(б,a), p(q4)=p(б,б).

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

1. Вычисляется энтропия источника в каждом из M состояний, считая эти состояния известными:

для состояния q1 ;

для состояния q2 ;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

для состояния qM .

2. Далее находим H(x) путём усреднения по всем состояниям q:

.

Окончательно получаем

. (8)

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

Вопросы

1. Что такое эргодический дискретный источник?
2. Что такое состояние эргодического дискретного источника, как вычислить количество состояний?
3. Как вычисляется энтропия эргодического источника?
4. Когда энтропия эргодического источника максимальна? Чему равен этот максимум?