Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
19 Свойства эргодических последовательностей знаков.
Характер последовательностей, формируемых реальным источником сообщений, зависит от существующих ограничений на выбор знаков. Они выражаются в том, что вероятности реализации знаков различны и между ними существуют корреляционные связи. Эти ограничения приводят к тому, что вероятности формируемых последовательностей существенно различаются.
Пусть, например, эргодический источник без памяти последовательно выдает знаки в соответствии с вероятностями 0,1; 0,3; 0,6. Тогда в образованной им достаточно длинной последовательности знаков мы ожидаем встретить в среднем на один знак три знака и шесть знаков . Однако при ограниченном числе знаков в последовательности существуют вероятности того, что она будет содержать;
только знаки (либо , либо );
только знаки и один знак или ;
только знаки и один знак или ;
только знаки и один знак или ;
только знаки и два знака или и т. д.
С увеличением числа знаков вероятности появления таких последовательностей уменьшаются.
Фундаментальные свойства длинных последовательностей знаков, создаваемых эргодическим источником сообщений, отражает следующая теорема: как бы ни малы были два числа δ>0 и μ>0 при достаточно большом Ν, все последовательности могут быть разбиты на две группы.
Одну группу составляет подавляющее большинство последовательностей, каждая из которых имеет настолько ничтожную вероятность, что даже суммарная вероятность всех таких последовательностей очень мала и при достаточно большом N будет меньше сколь угодно малого числа δ. Эти последовательности называют нетипичными.
Вторая группа включает типичные последовательности, которые при достаточно большом N отличаются тем, что вероятности их появления практически одинаковы, причем вероятность ρ любой такой последовательности удовлетворяет неравенству
где Η(Ζ) — энтропия источника сообщений.
Соотношение (4.5) называют также свойством асимптотической равномерности длинных последовательностей. Рассмотрим его подробнее.
Поскольку при N→ ∞ источник сообщений с вероятностью, сколь угодно близкой к единице, выдает только типичные последовательности, принимаемое во внимание число последовательностей равно 1/р. Неопределенность создания каждой такой последовательности с учетом их равновероятности составляет log(l/p). Тогда величина log(l/p)/N представляет собой неопределенность, приходящуюся в среднем на один знак. Конечно, эта величина практически не должна отличаться от энтропии источника, что и констатируется соотношением (4.5).
Ограничимся доказательством теоремы для простейшего случая эргодического источника без памяти. Оно непосредственно вытекает из закона больших чисел, в соответствии с которым в длинной последовательности из N элементов алфавита l (), имеющих вероятности появления , содержится Np элементов , Np элементов и т. д.
Тогда вероятность ρ реализации любой типичной последовательности близка к величине
Логарифмируя правую и левую части выражения (4.6), получаем
откуда (при очень больших Ν)
Для общего случая теорема доказывается с привлечением цепей Маркова.
Покажем теперь, что за исключением случая равновероятного и независимого выбора букв источником, когда нетипичные последовательности отсутствуют, типичные последовательности при достаточно большом N составляют незначительную долю от общего числа возможных последовательностей.
При объеме алфавита источника l и количестве знаков в последовательности N число всех возможных последовательностей
Принимая во внимание соотношение (4.5), число типичных последовательностей n можно записать в виде
Тогда
Так как
то
и неравенство усиливается с увеличением N.
К. Шеннон показал, что рассмотренные свойства длинных последовательностей могут служить основанием для осуществления эффективного кодирования информации (см. § 5.4).
Пример 4.2. Оценить, какую долю общего числа возможных последовательностей следует учитывать в практических расчетах, если эргодический источник характеризуется параметрами l = 16, Η(Ζ) = 3,5 дв.ед , а N = 50.
В соответствии с (4.7) и (4.8) имеем
откуда
Следовательно, к типичным последовательностям относится только одна тридцатимиллионная доля всех возможных реализаций!
PAGE \* MERGEFORMAT 1