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

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

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

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

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

, (4.1.1.1)

где - энтропия источника сообщений.

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

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

При объеме алфавита источника и количестве знаков в последовательности число всех возможных последовательностей

.

Принимая во внимание соотношение (4.1.1.1), число типичных последовательностей n₂ можно записать в виде:

.

Тогда

.

Так как , то и неравенство усиливается с ростом .

Дата добавления: 2015-07-08