Васюков В.Н. - Введение в ТЭС (1275345), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

.

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

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

,

называемую собственной информацией символа .

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

.

Пример 1. Предположим, что передается сообщение о карте, вытащенной наугад из идеально стасованной колоды в 32 карты (вероятность вытащить любую карту равна при этих условиях 1/32). Очевидно, это сообщение несет количество информации, равное 5 битам. Если это сообщение разбить на два, так, что вначале сообщается масть карты, а затем ее достоинство, то это количество информации будет передано частями – сначала 2 бита, затем еще 3. (Убедитесь, что это действительно так!) 

1. Энтропия и информация

Рассмотрим основные свойства энтропии.

1. Энтропия любого источника неотрицательна . Это следует из того, что вероятность любого события неотрицательна и не превосходит единицы. Равенство нулю энтропии источника имеет место в том случае, если один из символов имеет вероятность 1, а остальные – 0. Неопределенность, возникающая вследствие того, что при , может быть раскрыта с применением правила Лопиталя:

.

1. При заданном объеме алфавита энтропия максимальна, если все символы равновероятны .

Составим целевую функцию по методу неопределенных множителей Лагранжа

и запишем условие достижения ее экстремума

.

Решая уравнение относительно , получаем

,

откуда независимо от , а это и означает равновероятность символов. Максимальное значение энтропии равно . В частности, при энтропия максимальна при и равна 1 биту. Таким образом, 1 бит – это количество информации, доставляемое одним из двух равновероятных символов, вырабатываемых источником без памяти.

Два источника и , рассматриваемые в совокупности, характеризуются совместной энтропией

,

где – совместная вероятность символов; суммирование проводится по всем возможным значениям индексов. Совместная энтропия характеризуется свойством коммутативности , что прямо следует из равенства .

Используя выражение для совместной вероятности, перепишем совместную энтропию в виде

.

Заметим, что , тогда первое слагаемое принимает вид , а второе слагаемое представляет собой условную энтропию

.

Таким образом, совместная энтропия

.

Если источники статистически независимы, то

,

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

Рассмотрим более подробно понятие условной энтропии. Предположим, что имеется дискретный канал связи, на входе которого задан алфавит , а на выходе алфавит ; канал описывается условным распределением . Можно считать, что на входе действует источник с алфавитом и энтропией , а на выходе – источник с алфавитом и энтропией , причем эти источники статистически связаны.

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

.

В самом деле, если символы независимы, то , и (символ не несёт информации о символе ). И наоборот, при жесткой (детерминированной) связи между символами и , очевидно, , поэтому , то есть количество информации в символе относительно символа равно собственному количеству информации в символе (или, что эквивалентно, в символе ).

Используя известные формулы для совместных и условных вероятностей, легко видеть, что

.

Количество информации в символе относительно символа равно количеству информации в символе относительно символа . Поэтому величина называется взаимной информацией указанных символов.

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

.

Пример 2. Предположим, что на входе двоичного канала действует источник с равновероятными символами 0 и 1, а искажения символов при передаче происходят с некоторыми вероятностями и .

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

;

.

Взаимная информация переданного символа и наблюдаемого символа равна

,

аналогично взаимная информация переданного символа и наблюдаемого символа равна

.

Так же находятся два оставшихся количества информации

,

.

Особый интерес представляют некоторые частные случаи.

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

Второй частный случай имеет место при . Тогда и канал не передает информации (такая ситуация называется «обрывом канала»). 

Упражнение. Рассчитайте для этих частных случаев, а также для условную энтропию согласно .

Рассмотрим основные свойства условной энтропии.

1. Если источники сообщений и являются независимыми, то условная энтропия равна безусловной:

, .

Действительно, если источники независимы, то при всех . Тогда выражение можно переписать в виде

.

Но , откуда немедленно следует

, что и требовалось доказать.

2. Если символы источников и жестко связаны, то условная энтропия равна нулю. В самом деле, при жесткой связи в выражении некоторые условные вероятности равны 1, а остальные 0. Но как было показано выше, в этом случае сумма равна нулю.

Для условий примера 2 жесткая (детерминированная) связь входных и выходных символов соответствует вероятностям ошибок (или ).

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

_.

Если потери информации отсутствуют (канал без помех), то энтропия источника после передачи равна 0, количество передаваемой информации равно . Величина , таким образом, характеризует потери информации в канале и называется ненадежностью [3].

Заметим, что из выражения

,

следует

.

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

4. Из выражения для совместной энтропии и . Подставляя эти выражения в , получаем среднее количество передаваемой информации на символ

.

Приведем выражение к более удобному виду, для чего подставим в него формулы для вычисления безусловной и совместной энтропии.

.

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

1. Кодирование источника

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

.

Для независимых источников (источников без памяти) избыточность равна нулю (а энтропия максимальна) при равновероятности символов. Для источников с памятью избыточность тем больше, чем выше степень статистической зависимости символов в сообщении, при этом неопределенность относительно очередного символа в сообщении уменьшается, соответственно уменьшается и количество информации, переносимое этим символом. Например, в естественном английском языке после буквы “q” всегда следует буква “u”, поэтому при передаче такого текста буква “u” информации не несет. (В реальном английском тексте могут встречаться аббревиатуры, например, “QWERTY”, а также иноязычные, например, французские слова, для которых указанная закономерность не выполняется).

Характеристики

Список файлов книги