Вернер М. Основы кодирования (2004), страница 2

неожиданные события, обладают высоким информационным содержанием. Следовательно, информация и вероятность находятся в обратно пропорциональной зависимости. Исходяиз этого, введем понятие количества информации, как измеряемойвеличины на основании следующих трех аксиом [1].Р и с . 2.1. Простейший источник источник информации алфавита AT.Аксиомы для определения количества информации [1]1. Информация одиночного события Х{ £ X, происходящего с вероятностью pi, имеет положительное значение> 0.

•(2.1)2. Совместная информация двух независимых событий (xi,Xj) ссовместной вероятностью P(xi,Xj) = Pij = Pi • Pj> равна суммеих информации(2.2)3. Информация является непрерывной функцией от вероятностисобытия.Аксиомы 1 и 2 утверждают, что информация нескольких событий неможет взаимно уничтожаться. Аксиома 2 вводит понятие совместной информации событий. Из аксиомы 3 следует, что небольшое изменение вероятности события приводит к небольшому изменению ееГлава 2. Информация, энтропия и избыточностьинформации. Аксиома 2 определяет информацию двух независимых/событий.

Из (2.2) следует, что информация события определяется/как логарифмическая функция ее вероятности. Следовательно, информацию можно определить следующим образом:Информация события, происходящего с вероятностью р, равна1(р) = -Iog 2 (p) с [/] = бит.(2.3)В данной формуле используется двоичный логарифм. Возможны следующие обозначения двоичного логарифма: Iog2(a;) = Id (x) = lb(a;),где под Id подразумевается термин дуальный логарифм, а под 1Ь бинарный.1 Иногда используют натуральный логарифм с единицейизмерения наш, но можно использовать любую единицу измеренияинформации. Можно также переходить от одной единице к другой,применяя формулу пересчета:k>go(z) = logb(ar)/logb(a) = logb(z) • loga(6).Размерность бит используется в информационной технике придвоичной системы исчисления.

Как будет показано в следующих разделах, двоичная система очень удобна при описании процесса принятия решения, когда на любой вопрос существует только два ответа:«да» или «нет». В [10] приведена наглядная интерпретация понятия«бит».10Up) fбитНевозможноесобытие/. = 0\5 V—-0Неизбежноесобытие0,5р• 1Р и с . 2.2. Информация символа 7(р) с вероятностью появления р.На рис.

2.2 показано поведение информации как функции вероятности. Информация постоянно происходящего события равна нулю.1В отечественной математической литературе для обозначения двоичного и натурального логарифма принято использовать log2 и In. - Прим. перев.\2.2. Энтропияи избыточность15,I\ С ростом неопределенности информация также растет и для невоз\можного события стремится к бесконечности. Таким образом, информация соответствует всем приведенным ранее рассуждениям иудовлетворяет аксиомам 1 - 3. С точки зрения теории вероятности,определение информации можно рассматривать как некоторое отображение событий.

Аналогичное отображение имеют стохастическиепеременные. В следующих разделах это будет поясняться на примерах.2.2. Энтропия и избыточностьПосле того, как информация отдельного события определена, рассмотрим источник событий. Для его описания будем использоватьинформацию, которую несут содержащиеся в нем события. По аналогии с термодинамикой введем понятие энтропии. В термодинамикеэнтропия является мерой неупорядоченности системы. В теории информации энтропия определена как мера неопределенности источника. Используя информацию отдельных событий, выразим энтропиюисточника следующим образом:Элтропия простейшего источника без памяти X с алфавитомX — {х\,х<2, • • • ,£JV} и соответствующим вероятностям Р\,Р2, • • • ,PравнаNH(x) = ^2-Pi\og2(Pi)6nT.(2.4)гПредставим себе игру, в которой некоторое событие источника должно быть предсказано.

Если источник отдает предпочтение определенному событию, смело ставьте на него и, в основном, вы будетевыигрывать. Если все события равновероятны, то ставьте на любоесобытие: если неопределенность источника максимальна, шансы навыигрыш минимальны.Пример: Оценка энтропии.Поясним эту связь на примере простейшего дискретного источника без памяти из табл. 2.1. Информация источника представляет собой результат эксперимента со случайными событиями а, Ь, с, d.Пусть в результате повторения этого эксперимента мы получаем последовательность{а,Ъ,а,d t а,а,с,d,b,a,a,b,...}.(2.5)Глава 2.

Информация, энтропия и избыточностьТаблица 2.1. Дискретный источник без памяти с символамиалфавита X = {а, Ь, с, d} с вероятностью р* иинформацией I(pi).Символсbаdр.1/21/4.1/81/8ПР.)1 бит2 бит3 бит3 битПодставив на место каждого события его информацию, получимтипичную функцию стохастического процесса{/[п]/бит} = {1,2,1,3,1,1,3,3,2,1,1,2,...}.(2.6)Предположим эргодичность (постоянство поведения) такого процесса во времени.

Такую эргодичность мы, например, предполагаемпри бросании монетки или игрального кубика. С ростом числа испытаний N среднее значение информации источникаJV-1/ = lim -i у /[га]N->oo N t-*1n=0(2.7)стремится к математическому ожиданию4(2.8)Таким образом, учитывая сходимость ряда (2.7) к математическомуожиданию, получаем практическую меру для информации источника.

В рассмотренном нримере математическое ожидание Е{1) равно1,75 бит. Из первых 12 испытаний мы также получаем оценку для/(га) 1,75 бит.Проводя аналогичные рассуждения, Шеннон [1] заложил в определение энтропии три следующие аксиомы.Аксиоматическое определение энтропии1. Энтропия Н{Х) = f(pi,P2, • • • ,PN) является непрерывной функцией вероятностей р\,Р2,...

,ры2. Для источников с одинаковой вероятностью событий pi = jjэнтропия увеличивается с ростом числа событий N.3. Разложение процедуры выбора событий на несколько этаповне изменяет энтропию (процедуру выбора можно свести к последовательным двоичным решениям).2.2. Энтропия и избыточностьIПример: Разложение процедуры выбора.\ Данный пример поясняет аксиому 3. Рассмотрим три события a, bй с.

которые происходят с соответственными вероятностями 1/2,1/3и 1/6. Для того, чтобы выбрать одно из этих трех, мы можем поставить два независимых вопроса (рис. 2.3).1/6 " о ,Рис. 2.3. Разложение процесса выбора символов.На эти вопросы могут быть даны только два ответа: или «да» или«нет». Согласно аксиоме (3), к энтропии предъявляется следующеетребование:причем, второй вопрос задается с вероятностью 1/2. Мы покажем вобщем виде (рис.

2.4), что определение энтропии (2.8) удовлетворяеттребованию аксиомы (НЗ).ОаРг(Ь)ОЬЬ=сРис. 2.4. Разложение процедуры принятия решения.Для разложенной энтропии получаемН(Х)бит= -Pi(a)log 2 (pi(a)) -Pi(a)log 2 (pi(a))+(2.10)+ Pi (о)[-рг(Ь) Iog2(p2(b)) - Mb) Iog2(p2(b))],где вероятности определяются следующим образомPi(a) =р(Ь)+р(с),(2.11)18Глава 2. Информация, энтропия и избыточностьР2(6)(Ь)Р2=Р(Ь)р(сУЗамечание. Последнее равенство подтверждается постановкой эксперимента со случайными событиями.

Пусть событие а произошло300 раз, событие Ь - 200, а событие с - 100 раз. Частота каждогособытия в данном примере, равна его вероятности. Если мы отбросим событие а, то останется 300 выборок событий Ь и с, частотывыборок этих событий удвоятся, но их отношение не изменится.Из (2.11)- (2.13) следует, что вероятности на втором шаге можновыразить какПодставляя полученные выражения в формулу для энтропии, имеем- д — = -Pi(a)log 2 (pi(o)) -Pi(a)log 2 (pi(a))+Pl(tчто после упрощений соответствует энтропии без разложения процесса выбора событий= - P l ( o ) lo g 2 ( P l (a)) - р(Ь) log2(p(6)) - р(с) Iog2(p(c)).

(2.17)В рассмотренном примере было использовано свойство логарифмической функции, переводящее произведение в сумму. Определение(2.4) является единственным, при котором аксиома 3 имеет силу.Заметим также, что рассмотренное разложение процесса выбора событий может быть сведено к последовательности бинарных решений«да» и «нет». Максимальной неопределенности соответствует максимальная энтропия источника. Сформулируем следующую теорему:2.2. Энтропия и избыточность 19)Теорема 2.2.1. Энтропия простейшего дискретного источника безпамяти максимальна, если все события, в нем содержащиеся, имеют одинаковую вероятность, В этом случае энтропия просто равналогарифму числа событий#о =Ьит.(2.18)Замечание.

Последующее доказательство теоремы является типичным в теории информации. В таких доказательствах используются оценки и предельные переходы, которые ранее были известны,но не находили практического применения.Рис. 2.5. Верхняя оценка логарифмической функции.Доказательство. Для доказательства рассмотрим два дискретныхисточника без памяти Р и Q, каждый из которых содержит N событий с вероятностями р{ и <& соответственно.

Далее воспользуемсяизвестной верхней оценкой логарифмической функции ( рис. 2.5)lnx < x — .1.(2.19)Используя эту оценку, получаемIng; —In pjPiPi(2.20)Умножив обе части неравенства на pi и просуммировав по всем событиям 1 < i < N, имеем(2.21),20Глава 2. Информация, энтропия и избыточностьПосле упрощения получаемад+"нат 2 -1пл 1 п<""= о•'*^|^ А £11и, следовательнонамN: -S^Pilnqi." ^—'(2.23)г=1Предположим, что источник Q содержит только равновероятные события.

Тогда(2.24)г=1L"Jг=11Так как в процессе доказательства на источник Р не было наложеноникаких ограничений, то данное неравенство имеет место для любогодискретного источника без памяти, содержащего JV событийH(X)<\og2N6nT.(2.25)Максимум достигается, когда все события имеют одинаковые вероятности. •Любой источник, содержащий TV событий, не все из которых имеют одинаковую вероятность, обладает энтропией, меньшей Iog2./V.Рассмотрим источник емкостью Щ = log2 N как резервуар для хранения информации, который никогда не переполняется.Разность между максимальной емкостью # о и энтропией источника X, содержащего N событий, называется избыточностью источникаR = Но - Н(Х).(2.26)Относительная избыточность определяется какПример: Энтропия дискретного источника без памяти, содержащего 6 событий.2.2.