Вернер М. Основы кодирования (2004), страница 5
Описание файла
PDF-файл из архива "Вернер М. Основы кодирования (2004)", который расположен в категории "". Всё это находится в предмете "основы теории и техники радиосистем передачи информации (рспи)" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
В терминах теорииинформации это означает, что неопределенность второго источникаснижается, т.е. источники обмениваются взаимной информацией.Введем условную вероятность р(х/у) - вероятность события хпри условии, что произошло событие у. Выразим совместную вероятность p(xi, г/г) двух событий Х{ и j/j через их априорные и условныевероятностиp{xi,yi)=p(xi/yi)p(yi)=p(yi/xi)p{Xi).(4.1)Используя логарифмическую функцию, сразу же получаем информации Событий {Xi,yi), (Xi) И (у)-Цим) битi(Vi) битто естьI{xi,Vi) = I(Vi) - ld(ii/3/j) бит = 1(ц) - \og2p{yi/xi) бит.(4.3)Прибавляя и одновременно вычитая I(xi) в первой части (4.3) и,соответственно, I{yi) во второй, получаем'l(Xi, уг) = (Xi) + 1(уг) - log2 ^^бит =Таким образом, информация пары событий (xi,yi) определяетсясуммой информации этих событий за вычетом некоторой неотрицательной величины, которая снижает неопределенность, т.е.
сама всвою очередь является информацией. Поэтому, назовем ее взаимнойинформацией нары событий.Взаимная информация нары событий определяется как7\/ апостериорная вероятность \= log2 (I.\ априорная вероятность /4-1- Взаимная и условном информация-Обратите внимание на то, что взаимная информация /(ж,; у,) всегда положительна. Важным свойством также является симметриявзаимной информации относительно источников, т.к.Р(Уг)Симметрия относительно источников в (4.5) позволяет сделатьвывод, что обмен информацией между источниками является взаимным, а не односторонним.Для того, чтобы лучше представлять себе смысл взаимной информации, рассмотрим два граничных случая.1. Источники независимы. Тогда для пары независимых событийимеемp(*i,Vi) = P{xi)p(yi),'(4.7)то есть источники не обмениваются информацией(4.8)1{Хг;Уг)=0.2.
Источники жестко связаны, то есть событие одного источникаоднозначно определяет событие другого) = 1.•(4.9)В этом случае происходит полный обмен информациейЦХГМ) = 1(ъ) = /(w).(4.10)Из (4.4) следует, что информацию пары событий {xi,yi) можно интерпретировать, как разность между информацией пары независимых событий l{xi) + I(yi) и заранее предсказанной взаимной информацией I(xi;yi), обусловленной связанностью источников X и YЦхит) = I(Xi) + 1{УГ) - 1{ХГ,1Н).(4.11)Рассмотрим еще раз (4.3) и введем понятие условной информации.Условная информация (апостериорная неопределенность)Iixilm)= - l o g a p f o / и ) бит.(4.12)Из (4.3) следует/(*<;») = 1{Уг) + I(Xi/yi)= Цц) + НУг/Xi),(4.13),38Глава 4- Энтропия связанных источниковто есть информацию пары событий можно определить как суммуинформации события у\ и информации события ж, при условии, чтособытие yi уже известно, или, наоборот, как сумму информации события Xi и информации события ;(/, при условии, что событие xt ужеизвестно.4.2.
Совместная и условная энтропияПосле рассмотрения отдельных нар событий в предыдущем разделе,перейдем к средним оценкам источника.На рис. 4.2 показана исходная ситуация.Алфавит Х={х,,...,хи\Вероятность р(х,)1^(ЖШ^^^ШШ"^ЖЖУсловная вероятность р(у} I Xj)Д ^ Д ИСТОЧНИК |„,_^_^_Алфавит К = ( ^УдВероятность р(у*),)II ^Символы-Я Н и ^ и ЛI Вероятность парысимволов р^,,у>)Связанные источникиР и с . 4.2. Два связанных дискретных источника.Совместная энтропия двух источников определяется как математическое ожидание информации всех пар событий.Совместная энтропия двух дискретных источников без памятиX HY^ т).(4.14)Замечание. Здесь подразумевается, что рассматриваются все пары совместных событий, то естьМ NA:Yt=i j=iУсредняя условные информации всех нар событий, получим условную энтропию.4-2.
Совместная и условная энтропияТаблица 4.1. Оценка совместной вероятности пар символов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.