8.2. ИНФОРМАЦИОННЫЕ ХАРАКТЕРИСТИКИ ИСТОЧНИКА ДИСКРЕТНЫХ СООБЩЕНИЙ

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

где К — объем алфавита источника.

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

Количество информации, вырабатываемое источником, определяется его энтропией. Если сообщения (буквы) статистически независимы (источник без памяти), то энтропия источника, равная среднему количеству информации на букву, определяется известным выражением

где вероятность того, что на выходе источника появляется буква

Энтропия источника максимальна, когда все его сообщения имеют одинаковую вероятность . В этом случае

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

Важным частным случаем является источник двоичных сообщений, для которого Если то согласно (8.1)

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

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

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

где

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

Очевидно, имеют место следующие неравенства:

Дцесь Но — максимальная энтропия (8.2); — энтропия источника независимых сообщений (8.1); энтропия источника, когда учитывается статистическая связь между двумя сообщениями

(буквами); - энтропия источника с учетом трехбуквенных сочетании и т. д.

Величина

называется избыточностью источника, а

определяет эффективность кодека источника. Для оиенки эффективности устройств сжатия данных часто вводится величина обратная величине

которая называется коэффициентом сжатия.

В табл. 8.2 приведены значения энтропии для литературного текста на русском, английском и французском языках [179]. Оценка энтропии данным различных авторов, для русского языка лежит в пределах бит на букву, для английского 0,6 1,3 бит. Расчеты показывают, что (различие не превышает

Таблица 8.2. (см. скан)

Следовательно, избыточность русского литературного языка близка к 80%. Избыточность поэтических произведений еще больше (энтропия меньше 1 бита на букву), так «как в них имеются дополнительные вероятностные связи, обусловленные ритмом и рифмами. Деловые тексты, телеграммы весьма однообразны, и поэтому их избыточность очень большая. Так, энтропия источника телеграфных сообщений не превышает 0,8 бит на букву (избыточность порядка

Избыточность дискретного источника к обусловлена тем, что элементы сообщения (буквы) не равновероятны и что между буквами имеется статистическая связь (обозначим эту избыточность через Очевидно, полная избыточность источника [2]

Согласно табл. 8.2 для русского языка Следовательно, основная избыточность языка обусловлена статистической связью между буквами

Для передачи по дискретному каналу сообщения источника представляют (кодируют) последовательностями кодовых (чаще всего двоичных) символов так, чтобы по этим последовательностям можно было однозначно (без ошибок) восстановить исходные сообщения при декодировании. Задача состоит в том, чтобы эффективно закодировать сообщения, т. е. обеспечить наиболее экономное представление букв источника бинарными последовательностями

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

Теорема 1 К При любом способе кодирования: 1) ; 2) существует способ кодирования, при котором величина будет сколь угодно близкой к

Таким образом, энтропия источника определяет предельное значение двоичных символов, необходимых для представления букв источника. Теорема 1 остается справедливой и в том случае, когда вместо двоичного используется -ичное кодирование, по с той разницей, что логарифм при определении энтропии берется по основанию Для источника, все буквы которого независимы и равновероятны, оптимальным будет равномерный код. В этом случае Выберем для передачи каждой буквы последовательность из бинарных символов. Количество различных последовательностей равно Далее можно потребовать, чтобы (предполагается, что К — целая степень двух). Отсюда

Таким образом, равномерный код, который широко используется в телеграфии (код Бодо), не является оптимальным для передачи текста телеграмм. При таком кодировании не учитывают статистические свойства источника и на передачу каждой из 32 букв русского языка тратится максимальное число двоичных символов, равное 5 бит. Согласно теореме 1 и статистике языка (см. табл. 8.2) возможно более аффективное кодирование, при котором в среднем на букву русского текста будет затрачено не более 1,5 бит, т. е. примерно в 3 раза меньше, чем в коде Бодо.

Для реализации этих возможностей необходимо кодировать не отдельные буквы, а целые достаточно длинные последовательности букв (слова или даже фразы) и использовать для этого неравномерное кодирование, при котором более вероятным буквам (словам) присваивать короткие кодовые комбинации, а тем буквам (словам), которые встречаются редко, присваивать более длинные кодовые комбинации. В настоящее время разработано много методов эффективного кодирования для различных источников. Известные код Хаффмэна и код Шеннона — Фано, учитывающие только распределения вероятностей букв, не являются эффективными [178]. Коды же, учитывающие статистические связи между буквами, оказываются сложными и требуют значительной задержки передачи при кодировании и декодировании длинных последовательностей сообщений источника.

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

источники звуковых, видео- и телеметрических сообщений. В большинстве случаев эти источники относятся к классу источников непрерывных сообщений, которые рассматриваются в § 8.5.