Свойства эргодических последовательностей знаков

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

, (2.13)

где H (z) – энтропия источника сообщений.

Выражение (2.13) называют свойством асимптотической равномерности длинных последовательностей. При N ® ¥ источник сообщений с вероятностью, сколь угодно близкой к единице, выдает только типичные последовательности, принимаемое во внимание число последовательностей равно 1/ p. Неопределенность создания каждой такой последовательности равна log(1/ p). С учетом неопределенности, приходящейся на один знак, это – энтропия источника: = H (z).

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

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

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

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

D = , (2.14)

где H _max(z) – максимально возможная энтропия, равная log l;

H (z) – энтропия источника.

Если избыточность равна 0, то формируемые сообщения оптимальны в смысле наибольшего количества переносимой информации. Для передачи информации в количестве I при отсутствии помех в этом случае необходимо знаков.

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

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

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