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

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

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

только знаки (либо , либо );

только знаки и один знак или ;

только знаки и один знак или ;

только знаки и один знак или ;

только знаки и два знака или и т. д.

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

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

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

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

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

, (6.11)

где Н (Х)– энтропия эргодического источника, определяемая по (6.10).

Соотношение (6.11) называют также свойством асимп­тотической равномерности длинных последовательностей. Рассмотрим его подробнее.

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

.

При М → ∞ δ → 0. Поэтому при достаточно большом М можно положить

. (6.12)

Из (6.12) видно, что все последовательности С равновероятны и число их равно

N_T ≈ 1/ p (C) или N_T ≈2 ^{МН (Х)}. (6.12а)

Поскольку при М ® ¥ источник сообщений с вероят­ностью, сколь угодно близкой к единице, выдает только типичные последовательности, неопределенность создания каждой такой последовательности с учетом их равновероятности составляет . Тогда величина log(1/ p)/ M представляет собой неопределенность, прихо­дящуюся в среднем на один знак. Конечно, эта величина практически не должна отличаться от энтропии источни­ка, что и констатируется соотношением (6.11).

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

Тогда вероятность р реализации любой типичной последовательности близка к величине

(6.13)

Логарифмируя правую и левую части выражения (6.13), получаем

откуда (при очень больших M)

.

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

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

Общее число всевозможных последовательностей дли­ны М, вырабатываемых источником,

.

,

откуда при М → ∞ N_T/N → 0, так как Н (Х) – log п ≤ 0. Однако хотя типичных последовательностей мало, но только они в основном вырабатываются источником, как то следует из теоремы.

Пусть, например,

а = 2, п = 100, Н = 2,75, т = 8. Тогда N = 8¹⁰⁰ = 2³⁰⁰, N ₂ = 2¹⁰⁰ ּ 2,75 = 2²⁷⁵.

Отсюда

Т.е. к высоковероятной группе относится лишь одна тридцатимиллионная доля всех реализаций.

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

Целесообразно отметить, что в простейшем случае отсутствия статистической зависимости между элементами процесса свойство Е является простым следствием закона больших чисел [7].