Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Оптимальность кодов и разрешающая информация
Особая точка зрения при выборе кодовой функции появляется в случае, когда для заданного множества знаков А известна определенная, не зависящая от времени, вероятность (средняя частота) вхождения знаков из А в рассматриваемую последовательность из А*. Источник последовательности знаков с этими свойствами (каждому моменту времени для новых подлежащих пересылке знаков соответствуют вероятности, точно равные заданной средней частоте) называется стохастическим или шенноновским источником сообщений.
Пример (стохастический источник сообщений). Стохастический источник сообщений для заданного алфавита А поддается, например, следующим образом. Возьмем любое количество шаров и каждый шар пометим знаком из алфавита А (при этом один и тот же знак может встретиться на нескольких шарах). Положим помеченные шары в коробку и перемешаем их. Затем из коробки случайным образом возьмем шар, запишем содержащийся на нем знак, бросим шар обратно в коробу и перемешаем шары. После этого опять случайным образом возьмем шар из коробки и т.д.
Таким способом полним стохастический источник сообщений. Средняя частота (вероятность) появления какого-либо знака в порождаемой последовательности соответствует здесь отношению числа шаров. помеченных данным знаком, к общему числу шаров.
Обратим внимание на то, что последовательности знаков, встречающиеся в естественных языках, не являются стохастическими. Вероятность того, что определенная буква слезет за определенной заданной буквой в немецком, например, языке не является независимой от заданной буквы. В таком случае говорим о контактной частоте.
В дальнейшем укажем способ кодирования последовательностей знаков стохастического источника сообщений с целью получить по возможности короткую среднюю длину кода сообщения. Впрочем, с использованием этого способа с успехом могут кодироваться сообщения не стохастических источников (например, сообщения на естественном языке).
Прежде чем обратиться к собственно вопросу кодирования, обсудим понятие информационного содержания знака, который встречается в последовательности знаков стохастического источника сообщений.
Можно разрешающую информацию или информационное содержание знака примерно отождествить с обратной величиной частоты появления знака. Это наглядно соответствует нашему представлению об информационном содержании сообщений:
·
сообщение о фактическом наступлении почти всегда наступающего события имеет небольшое информационное содержание;
· сообщения о фактическом наступлении редкого события, напротив, имеют высокое информационное содержание. Другими словами, чем реже поступает сообщение, тем выше его информационное содержание.
