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

Оценка совместной вероятности пар символовp(xi,yj) и вероятность отдельных символов2/1№Vi00,20XI0,100,050,05Х20,050,150,1500,35хз00,100,100,100,30Х400,050,050,050,150,150,350,350,151v(Vj)Условная энтропия двух дискретных источников без памяти X и У(4.15)ЩХ/Y)битp { X t y ) l o g 2 p { x / y ).XYЗаменяя в (4.14) \og2p{x,y) ua.\og2(p(x/y)p(y)) и наполучимIog2(p(y/x)p{y)),Н(Х, Y) = H{Y) + H{X/Y) = Н{Х) + H(Y/X).(4.16)Таким образом, совместная энтропия может быть представленав виде суммы энтропии одного источника и некоторой части энтропии другого источника. Для независимых источников энтропиявторого источника входит в сумму целиком, т.к.

H(X/Y) — Н(Х)и H(Y/X) = H(Y). Для связанных источников всегда H(X/Y) <Н(Х) и H{Y/X) < H(Y). Поэтому, в общем случае, всегда имеетместоH{X,Y)<H{Y) + H(X).(4.17)Пример: Связанные источники.Сейчас самое время подробно разобрать числовой пример, наглядно поясняющий приведенные выше определения и формулы. Дляэтой цели была подобрана задача, методика решения которой можетнепосредственно использоваться на практике.Пусть мы имеем выборку 100000 пар совместных событий (xi,yi)дискретных источников X и У и алфавит каждого источника содержит четыре события.

Пусть пара (xi,yi) встретилась 10000 раз.Г40Глава 4- Энтропия связанных источниковТогда оценка вероятности пары (xi,2/i) равна 10000/10000 = 0,1.Оценки остальных пар событий также получены подсчетами их относительной частоты и сведены в таблицу 4.1. Будем считаем, чтополученные оценки близки к вероятностям пар событий и в дальнейшем будем говорить уже о вероятностях. Вероятности событийXi, yi получены суммированием строк и столбцов.

Контрольная сумма Y2i=ixi = X/i=i 2/г = 1 приведена в правом нижнем углу.Теперь, когда нам известны все вероятности, необходимые дляподсчета энтропии, определим:1. Энтропии источников X и У;2. Совместную энтропию источников;3. Обе условные энтропии;Для контроля мы также вычислим:4. Условные вероятности P(yg/xi);5. Определим условную энтропию H(Y/X).Замечание. Для простоты проведем расчеты с точностью до 4знаков после запятой.Решение.1.н(х) _ А _бит^—*i=i= -2[0,15 • log2(0,15) + 0,35 • log2(0,35)] = 1,9261,_4(4.18)>( № ) = 1,8813;j=i244?~р- = Е Е -p(Xi> УЗ)=3-4464;i=i(4-19)j=\3. Без длинных вычислений из (4.16) получаемH(X/Y)= H(X,Y) - H(Y) = 3,4464 - 1,8813 = 1,5651 бит,H(Y/X) = H{X,Y) - H{X) = 3,4464 - 1,19261 = 1,5203 бит;4-3.

Выводы41Таблица 4.2. Условная вероятность p(y,/Xj).У1г/2Уз2/4XI1/21/41/401XI1/73/73/701хз01/31/31/31Xi01/31/31/314. В таблице 4.2 приведены условные вероятности, подсчитанные исходя из таблицы 4.1. Заметим, что при этом мы получили так называемую стохастическую матрицу. Сумма условных вероятностей длякаждой строки равна 1.= 1,5496.(4.20)г=1 j = l4.3. ВыводыВсе приведенные в предыдущих разделах рассуждения в математической форме сведены в табл.

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

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

Условная вероятность - это вероятностьодного события при условии, что другое событие уже произошло, по-(42Глава 4- Энтропия связанных источниковТаблица 4.3. Дискретные источники без памяти X и У с символами х S X = {xi,xa, • • • , 1 м } и ;(/ 6 У —{г/1. №,•••, 1/JV}ИнформацииЭнтропияВероятностьИнформация отдельного Энтропияотдельного сим- символавола (априорнаяI(x) = -log 2 p(x) битвероятность)р(х)Совместная ве- Информация пары симроятность двух воловсимволов1(х,у) = - log2 р(х, у) битР(х, У)H(X,Y)Условная веро- Условная информацияятность(апоЦх/у) = - \<щгр{х/у) битстериорнаявероятность)Цу/х) = - log2p(y/x) битР(.х,у)р(у)Р(х,у)Р(у/х) =р{х)-H(X/Y) =I битH(Y/X) =р(х/у) =р^'у'l o gВзаимная информация,/ч _,апостериорная вероятность ,и J\ 'У/ - &2 априорная информацияI бит4-3.

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

Это понятие будет подробно рассмотрено в 7 главе этой книги.ГЛАВА 5СТАЦИОНАРНЫЕДИСКРЕТНЫЕ ИСТОЧНИКИС ПАМЯТЬЮ5.1. ЭнтропияСигналы аналоговых источников информации ограничены по полосе, поэтому коррелированы во времени. Примером может служитьаналоговый речевой сигнал в телефонной линии. После оцифровки, аналоговый источник превращается в дискретный и, например,после квантования сигнала на 256 уровней, мы получаем последовательнось 8-ми битовых двоичных целых чисел от 0 до 255. Каквидно из рис.

5.1, значение двух соседних чисел близки друг к другу, т.к. телефонный сигнал передается в узкой полосе частот. Изза временной связи соседних отсчетов, то есть памяти отсчета, егонеопределенность (информация) снижается по сравнению с аналоговым источником без памяти, поэтому основной задачей методовсжатия, особенно при передаче видеосигналов, является снижениеизбыточности.III!!i iiiJfi%j •ITi:;;;I i!лi:\yr({ i[\\\cloРис. 5.1.

Непрерывный сигнал.Возникает вопрос о том, каким образом определить энтропиюдискретного источника с памятью. Начнем с постановки задачи.Определение 5.1.1. Дискретный источник X можно представитькак дискретный во времени стохастический процесс, реализацией5.1. Энтропиякоторого является последовательность событий хп, принадлежащихалфавиту источника X = {оц, «2,..., адг}Замечание. Во избежание путаницы, мы обозначили содержимоеалфавита греческими буквами. В этом случае на месте переменнойхп п-го события может быть поставленно любое число из алфавита X.Определение 5.1.2.

Дискретный источник является стационарным, если совместные вероятности последовательностей событий независят от выбора начальной точки отсчета времени.Замечание. Независимость наблюдений от точки отсчета означает, что мы можем начинать выборку с любого момента-времени, то есть статистика не зависит от времени начала наблюде}шй.Определение 5.1.3. Стационарный дискретный источник математически полностью описан, если известны все совместные вероя т н о с т и р(хП1,хП2,...,хпм)д л я л ю б о й в ы б о р к и пх,П2,...,пм,гдеМ —> оо.Определение энтропии стационарного дискретного источника спамятью следует из двух подходов, приводящих к одинаковому результату.

При первом подходе мы используем понятие совместной энтропии, при втором - условной энтропии. В обоих случаях мы ищемответ на следующий вопрос: «Если память источника распространяется на несколько последовательных событий, то какую дополнительную информацию несет отдельное событие в том случае, еслиблок предшествующих событий уже известен?»Подход 1. Совместная энтропия.Совместная энтропия двух источников Х\ и xi с одинаковымиалфавитами и одинаковыми распределениями вероятностей событийопределяется какм мH(X1,X2) = -^2^2p(Xi,Xj)log2P(Xi,Xj).(5.1)Распространим это определение на L последовательных источниковXi и найдем энтропию источника Xi какi^,(5.2)Глава 5.

Стационарные дискретные источники с памятью/jгде вектор X = (х\,х2, • • • ,£/,) и суммирование производится по вс^мвозможным компонентам вектора X. Устремляя L к бесконечнос+и,мы полностью охватим память источника и получим предельное значение Hi(X) (если оно существует), равноеiЯоо(Х) = lim H(XL).(5.3)L—юоПодход 2. Условная энтропия.Условная энтропия L-того события в случае, если L — 1 предшествующих событий уже известны, определяется какlim H(XL/X1,X2,...,XL_1).(5.4)L—tooХотя в левых частях равенств (5.3) и (5.4) мы уже использовали одинаковое обозначение энтропии отдельного события, этот факт предстоит доказать. Проведем это доказательство за 4 шага.НО0{Х)=Теорема 5.1.1. Для стационарного дискретного источника с Hi{x) <ос имеет место:1.

H(Xi\Xi, X2, • • •, XL^I) не возрастает с ростом длины блока L;2.HL(X)>H(XL\Xi,X2,...,XL-1);3. HL(X) не возрастает с ростом длины блока L;4. Энтропия стационарного дискретного источника HL(X)lim HL(X) = lim ff(Xt|Xi,X2,...,XL_i) = Я о о Р 0 .L—tooL—tooДоказательство.1. Из определения энтропии, как меры неопределенности источника, непосредственно следует, что возрастание числа ограниченийне может повлечь за собой рост неопределенности, а следовательнои энтропии.2. Из «правила цепочки» для совместной энтронии следуетj[H(X1)Li+ H(X2\X1)+ --- +.(5.5)+H(XL\X1,X2,...,XL^)].Замечание. «Правило цепочки» для совместной энтропии следуетиз «правила цепочки» для вероятностей.