Какое количество информации содержится в этом сообщении

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

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

Передаваемое по каналам связи сообщение можно представить в виде набора некоторых смысловых элементов или символов (например, букв алфавита). Если общее число (объем) символов алфавита равно т, а одно сообщение может быть составлено из п элементов, то максимальное число возможных сообщений N = тп. Например, с помощью двухразрядного десятичного числа (п = 2, т = 10) можно представить N = 102 = 100 различных чисел от 0 до 99. В частности, при средней длине русского слова п = 5 букв и алфавите в т = 32 буквы можно составить почти N = 32D = 33,6 млн различных слов. Казалось бы, искомая мера количества информации найдена. Однако использование числа Лгв качестве меры информации неудобно, так как нс выполняется условие пропорциональности между длиной слова (длительностью сигнала) и количеством содержащейся в нем информации. Между гем удвоение времени передачи сообщений должно приводить к удвоению количества передаваемой информации.

Р. Хартли в 1928 г. выдвинул идею о том, что информация допускает количественную оценку, и ввел в теорию передачи информации методологию измерения количества информации. При этом Хартли четко обозначил, что он имеет в виду под информацией, которую собирался измерять: «Группа физических символов — слов, точек, тире и т.п., имеющих по общему соглашению известный смысл для корреспондирующих сторон». Хартли ставил перед собой задачу ввести какую-то меру для измерения кодированной информации, а точнее, последовательности символов, используемых для кодирования информации.

Рассматривая передаваемую информацию в виде определенной последовательности символов алфавита объемом т, а передачу и прием этой информации — в виде последовательных выборов из этого алфавита, Хартли предложил информацию /, приходящуюся на одно сообщение, определять логарифмом общего числа возможных сообщений N с числом символов п:

Если же все множество возможных для передачи сообщений состоит только из одного (N=m = 1), то I = log 1=0, что соответствует отсутствию информации в этом случае. При наличии независимых источников информации с N{ и N2 числом возможных сообщений

т.е. количество информации, приходящееся на одно сообщение, равно сумме количеств информации, которые были бы получены от двух независимых источников, взятых порознь.

Логарифмическая мера удобна по ряду следующих причин.

• 1. Ее легко использовать на практике. Параметры, важные в инженерных приложениях, такие как время, пропускная способность, число переключателей и т.д., обычно меняются линейно при логарифмическом изменении числа возможных вариантов. К примеру, добавление одного переключателя удваивает число возможных состояний их группы, увеличивая на единицу его логарифм по основанию 2. Увеличение в два раза времени приводит к квадратичному росту числа сообщений, или удвоению их логарифма, и т.д.
• 2. Она близка к нашему интуитивному представлению о такой мерс. Эго тесно связано с предыдущим пунктом, так как мы интуитивно измеряем величины, линейно сравнивая их со стандартами. Так, нам кажется, что на двух одинаковых дисках памяти можно разместить в два раза больше информации, а по двум одинаковым каналам — передать ее в два раза больше.
• 3. Она удобна математически; многие предельные переходы просты в логарифмах, в то время как в терминах числа вариантов они достаточно сложны.

Выбор основания логарифма, безусловно, соответствует выбору единицы измерения количества информации. Если взять основание 2, то полученные единицы есть не что иное, как двоичные цифры, или биты. Устройство с двумя устойчивыми состояниями способно хранить 1 бит информации, N таких устройств — N бит, так как полное число состояний 2jV и log22jV = N. При использовании же основания 10 единицы называют десятичными цифрами. При этом один разряд десятичного кода содержит I = -log2р = 3,32 бита информации.

Рассмотрим подробнее вопрос о количественной оценке информации, предложенной Р. Хартли. Выберем некоторое случайное событие, относительно которого известно, что оно может появиться с вероятностью р. Пусть информация об этом событии передается алфавитом, состоящим из т смысловых символов. Если возможность появления любого символа алфавита также равновероятна, то эта вероятность р= /т (при этом т = 1 /р). Полагая, что N = т, получим

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

где логарифм может быть взят при любом основании а.

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

Этот подход принципиально изменил понятие информации. Под информацией стали понимать не любые сообщения, передаваемые по системе связи, а лишь те, которые уменьшают неопределенность у получателя. Количество информации, переданное в этом случае, наиболее удобно и следует принять за единицу ее количества. Именно это количество информации может быть получено, если применить формулу (7.23) и взять логарифм по основанию 2:

Тогда 1= -log 2р = — log2( 1/2) = log22 = 1.

Полученная единица количества информации является битом (напомним, что термин «бит» имеет два различных значения; одно используется в качестве синонима двоичного символа, а второе обозначает единицу количества информации; скорость передачи данных представляет собой именно количество двоичных символов, передаваемых за 1 с). Здесь бит является не только единицей количества информации, но и единицей измерения степени неопределенности. При этом имеется в виду неопределенность, которая содержится в одном опыте, имеющем два равновероятных исхода. Эта мера представления информации является универсальной и позволяет сравнить различные сообщения и количественно определить ценность различных источников информации, оценить величину ее потерь при передаче, приеме, обработке, храпении и т.д. Применение двоичных логарифмов диктуется тем, что сообщение в практических системах связи чаще всего принимает форму отдельных групп (кодовых слов), состоящих только из двух символов, которые можно трактовать как 0 или 1. Каждая такая группа кодирует, например, буквы того или иного естественного языка, из которых составляются отдельные слова. Если основанием логарифма в формуле (7.24) выбрано е (т.е. взят натуральный логарифм), то информация будет измеряться в натуральных единицах, или патах {1 нат « 1,443 бита).

Пример 7.3

На одной стандартной странице на русском языке написан текст, содержащий 40 строк по 65 букв в каждой строке. Оценим по формуле Хартли объем информации в данном тексте, полагая, что алфавит состоит из 32 букв.

Решение

Для упрощения будем считать, что появление любой буквы в тексте равновероятно. В этом случае каждая буква содержит количество информации /б = = -log2(l/32) = 5 бит.

Тогда общий объем информации страницы текста составит / = 40 • 65 • 5 = 13 000 бит = 13 Кбит.

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

Пример 7.4

Вычислим по формуле Хартли характеристики угадывания одного числа из набора чисел от 1 до 100.

Решение

Воспользуемся формулой (7.24) и вычислим, какое количество информации требуется: I = log2100 > 6,644. Таким образом, сообщение о верно угаданном числе содержит количество информации, приблизительно равное 6,644 ед.

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

Основной недостаток формулы Хартли — она не отражает случайного характера формирования сообщений. Чтобы устранить этот недостаток, необходимо связать количество информации в сообщениях с вероятностью появления символов. Эта задача была решена К. Шенноном, который применил теоретико-вероятностный подход.

Развивая и обобщая идеи Р. Хартли, К. Шеннон в 1948 г. в фундаментальном труде «Математическая теория связи» ввел два важнейших понятия: информации, содержащейся в подлежащих передаче по каналу связи сообщениях, и энтропии источника сообщений. Шеннон впервые стал рассматривать статистическую структуру передаваемых сообщений и действующих в канале шумов, и, кроме того, он рассматривал не только конечные, но и непрерывные множества сообщений. Созданная им теория информации дала ключ к решению двух основных проблем теории связи: устранение избыточности сообщений и кодирование сообщений, передаваемых по каналу связи с шумами.

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

Пусть объем какого-то алфавита X равен т и источник передает сообщения этими символами. Положим, что величины всех вероятностей появления любого из символов pjt г = 1,2,…, т, — априорные, т.е. известные. Проследим за достаточно длинным отрезком сообщения. Пусть в нем имеется N{ символов первого типа, N2 символов второго типа, …, Nm сигналов т-го типа, причем Л’, + iV2 + … + Nj + … + Nm = N — общее достаточно большое число символов в наблюдаемом отрезке, /,,/2,… /(, — частоты появления соответствующих символов.

При возрастании длины отрезка сообщения каждая из частот появления г-го символа стремится к фиксированному пределу: 1 inif. = pjti = 1, 2,…, т, где Pi можно считать вероятностью данного символа.

Предположим, получен символ г-го типа с вероятностью pjt содержащий согласно формуле (7.23) -logар: единиц информации. Очевидно, что в рассматриваемом отрезке сообщения г’-й символ встретится примерно Npt раз и общая информация, доставленная символами этого типа, будет равна произведению Np}ogaPi. То же относится к символам любого другого типа, поэтому полное количество информации (для нее К. Шеннон ввел метрику //), доставленное отрезком из JV символов алфавита X, будет примерно равно

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

Оказалось, что формула (7.23), предложенная Хартли, представляет собой частный случай более общей формулы Шеннона. Если в формуле Шеннона (7.25) принять, чтор, = р2 = … = pN = 1 /N, то приходим к формуле Хартли:

Выражение (7.25) К. Шеннон назвал энтропией источника сообщений. Значит, энтропия отражает среднее значение количества информации, приходящееся на один символ алфавита (бит/символ).

Знак «минус» в формулах Шеннона (7.25) и (7.26) не означает, что энтропия сообщения — величина отрицательная. Объясняется это тем, что вероятность р согласно определению меньше единицы, но больше нуля. Так как логарифм числа, меньшего единицы, т.е. log2p(, — величина отрицательная, то (с учетом знака «минус» перед формулой) произведение вероятности на логарифм этого числа будет положительным. Под информацией теперь понимают не любые сообщения, передаваемые в системе связи, а лишь те, которые снижают энтропию сообщения. При этом увеличивается информативность поступившего сообщения.

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

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

Пример 7.5

Определим по Хартли и Шеннону количество информации, связанное с появлением каждого символа в сообщениях, записанных на русском языке. Будем считать, что русский алфавит состоит из 32 букв.

Решение

По формуле Хартли I = log232 = 5 бит (при расчетах считаем, что появление каждой буквы равновероятно). По формуле Шеннона (для неравновероятных исходов) это значение равно Н = 4,72 бита.

Чтобы пояснить наглядный смысл понятия энтропии, опишем ее свойства.

1. Энтропия является положительной непрерывной величиной.

Пусть сообщение передается с помощью двоичного алфавита (двоичного источника), состоящего только из двух символов, например 0 и 1. Если вероятность появления первого символа равна р, то вероятность появления второго символа составляет 1- р. В этом случае энтропия изменяется от 0 до 1 и

На рис. 7.27 приведен график зависимости Н(Х) для двоичного источника, построенный по формуле (7.27). Он показывает, что максимальное значение энтропии, равное 1 бит/символ, достигается при равновероятном появлении обеих букв алфавита. Если же вероятность р приближается к нулю или единице, энтропия источника становится весьма низкой, что говорит о малой информативности выбранного алфавита. Сообщение оказывается детерминированной последовательностью символов.

Рис. 7.27. Энтропия двоичного источника

• 2. Энтропия равна нулю тогда и только тогда, когда вероятность одного из состояний равна единице. Это соответствует случаю, когда одно из состояний источника достоверно, а другие невозможны, т.е. отсутствует любая неопределенность.
• 3. Энтропия максимальна, когда все символы источника сообщений равновероятны, а значит, р{ = р2 = … = рт = 1 /т. Тогда приходим к формуле Хартли

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

Дадим пояснения этим свойствам. Если ситуация при передаче информации полностью ясна, то никакой неопределенности нет и энтропия равна нулю. В частности, если ток в цепи равен 20 А, то он не может быть одновременно равным 10 А. На данном примере можно пояснить и другое свойство. Если одно из событий ожидается с очень малой вероятностью, например р, = 0,01, а другое с высокой, например р2 = 0,99, то неопределенность невелика, так как почти наверняка получим второе сообщение. Если события равновероятны и р{ = р2 = 0,5, то уже нет уверенности, что будет получено какое-то из сообщений, т.е. неопределенность возрастает. Очевидно, что неопределенность возрастает, если вместо одного из двух сообщений может прийти одно из трех, четырех и более.

Теперь с помощью свойств 1—3 можно дать другое общепринятое определение энтропии. Энтропия — это средняя информативность источника на один символ, определяющая «непредсказуемость» выдаваемых им сообщений. Полностью детерминированный источник, вырабатывающий лишь одну, заранее известную последовательность символов, обладает нулевой информативностью. И наоборот, наиболее «хаотический» источник, выдающий взаимно независимые и равновероятные символы, обладает максимальной информативностью.

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

Пример 7.6

Вычислим энтропию источника, который может выдавать четыре символа с равной вероятностью появления.

Решение

Используя формулу (7.26), получаем II(X) = log2m = log24 = 2 бит.