Теория информации |
Конспект лекций |
2. ВЕРОЯТНОСТНЫЙ ПОДХОД К ИЗМЕРЕНИЮ КОЛИЧЕСТВА ИНФОРМАЦИИ
2.2 Оценка количества информации сообщений
Большой класс дискретных сообщений, передаваемых по каналам связи, можно представить как набор из n символов (элементов), которые последовательно порождает некоторый источник информации. Элементы сообщения могут принимать значения из некоторого конечного алфавита мощности m. Элементами сообщений могут быть импульсы тока или напряжения, символы текста, биты и др.
Определим количество различных сообщений, которые можно составить из n символов, принимающих любое из m различных фиксированных значений. Первый элемент сообщения может принимать m значений, второй – также m значений и т.д. Тогда общее количество различных сообщений равно
Чем больше L, тем значительней отличается каждое данное сообщение от остальных, т. е. величина L может служить мерой количества информации для равновероятных сообщений. Однако более удобной мерой количества информации является логарифм числа возможных сообщений (здесь и далее )
Логарифмическая мера I(L) количества информации обладает следующими свойствами
Последнее соотношение выражает свойство аддитивности количества информации, т.е. количество информации нескольких независимых источников сообщений равно сумме количеств информации каждого источника
Пример 2.2.1. Определить количество информации, которое содержится в телевизионном сигнале, соответствующем одному кадру развертки. В кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайных по амплитуде импульсов, причем амплитуда импульса может принять любое из 8 значений с шагом в 1 В.
Решение. В рассматриваемом случае длина сообщения, соответствующая одной строке, равна числу случайных по амплитуде импульсов в ней, т.е. n=600.
Каждый элемент сообщения может принимать любое из 8 значений амплитуды импульса, т.е. m=8.
Количество информации в одной строке
а общее количество информации в кадре бит или 137,33 Кб.
Пример 2.2.2. Определить минимальное число взвешиваний, которое необходимо произвести на равноплечих весах, чтобы среди 27 внешне неотличимых монет найти одну фальшивую, более легкую.
Решение. Так как монеты внешне неотличимые, то они представляют источник с равновероятными состояниями, а общая информация такого источника бит.
Каждое взвешивание имеет один из трех возможных исходов: левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии. Так как все исходы равновероятны (нельзя заранее отдать предпочтение одному из них), то результат одного взвешивания представляет источник с тремя равновероятными состояниями, а общее количество информации такого источника составляет бит.
Так как количество информации отвечает требованию аддитивности и при этом , то для определения фальшивой монеты достаточно произвести три взвешивания.
Алгоритм определения фальшивой монеты следующий. При первом взвешивании на каждую чашку весов кладется по девять монет. Фальшивая монета будет либо среди тех девяти монет, которые оказались легче, либо среди тех, которые не взвешивались, если имело место равновесие. Аналогично, после второго взвешивания число монет, среди которых находится фальшивая монета, сократится до трех. Последнее, третье, взвешивание дает возможность точно указать фальшивую монету.
Рассмотренная выше оценка информации основана на предположении о равновероятности всех знаков алфавита источника информации. Рассмотрим теперь сообщения длины n, символы которого порождаются независимо некоторым источником информации в соответствии с распределением дискретной случайной величины, т.е. элементы сообщения могут принимать значения с вероятностями
соответственно,
. Вычислим среднюю вероятность такого сообщения.
Обозначим количество элементов сообщения, принимающих значение
,
. Очевидно, что
. Поскольку элементы сообщения принимают значения независимо, то вероятность сообщения равна
.
При достаточно больших n по теореме Бернулли допустимо такое приближение или
и тогда
. Последняя формула выражает среднюю вероятность сообщения.
По средней вероятности подсчитаем среднее число всех возможных сообщений . Зная среднее число L всех возможных сообщений, определим и среднее количество информации I(L), содержащееся в одном сообщении
.
Последнее соотношение было получено Шенноном для определения среднего количества информации в сообщении с произвольными вероятностями появления состояний. При равновероятных состояниях элементов сообщений, т.е. , формула Шеннона превращается в уже знакомую формулу
.
Пример 2.2.3. Источник информации A порождает сообщения, состоящие из символов с вероятностями
. Сравнить количество информации, приходящуюся на букву источника информации A с количеством информации, которая была бы у того же источника при равновероятном использовании букв.
Решение. При одинаковых вероятностях появления любой из всех m=4 букв алфавита количество информации, приходящуюся на одну букву, характеризует величина бит.
Найдем количество информации источника A.
бит
Таким образом, неравномерность распределения вероятностей использования букв снижает количество информации источника с 2 до 1.37 бит