Прокис Дж. Цифровая связь (2000) (1151856), страница 19
Текст из файла (страница 19)
В некоторых случаях, представляющих практический интерес, случайная величина Х ляется дискретной, а У вЂ” непрерывной. Для конкретности предположим, что Х имеет вможные исходы хь 1=1, 2„..., и, а У определяется собственной ФПВ р(у). Если Х и У атистически взаимосвязаны, мы можем выразить р(у) так: 11 р(у) = ~ р(у ! х, ) р(х,) .
г! Взаимная информация относительно события Х=х, при наблюдении события 1'=у ределяется как р(у ! х,)Р(х,) р(у ~ х,) (" 2.20) р(у)Р(х,) р(у) Тогда средняя взаимная информация между Х и У 1(Х;У)=~ ~ р(у~х,.)Р(х,)1о8 ' сну. р(у) Пример 3.2.5. Предположим, что Х является дискретной случайной величиной с двумя ~новероятными выходами Х1 = А и Хз =А. Предположим, что условная ФПВ р(у~х,), , 2, является гауссовской со средним Х, и дисперсией а~, т.е. р(у~ А) = е " "' ' '; (3.2.22) р(у1-А) = е о'"~ "' . ~/2яо Средняя взаимная информация согласно (3.2.21) равна (3.2.21) 1(Х; У) = х ~ ~р(у ! А)1ой + р(у1-А) 1оа ' 'у, (3.2.23) р(у ! А) р(у! — А)1.
р(у) р(у) вели Хи 1' — случрйные величины с СПВ р(ху) и собственными ФПВ р(х) и р(у), то средняя взаимная информация между Хи 1'определяется как 1(Х; 1') = ~ ~ р(х)р(у / х) 1о8 сйс1у. (3.2.17) р(х)р(у) Несмотря на то, что выражение для средней взаимной информации легко обобщается ва непрерывные случайные величины, сделать это для собственной информации 'вепрерывной случайной величины невозможно.
Проблема в том, что непрерывные ;лучайяые величины требуют неограниченного числа двоичных цифр для их точного представления. Следовательно, энтропия непрерывной случайной величины также ~еограииченна. Все же введем характеристику, которую назовем дифференциальной итропией непрерывной случайной величины Х: Ь(Х) = — ~ р(х)1одр(х)сй.
(3.2.18) Подчеркнем, что эта характеристика не имеет физического смысла собственной иформации, хотя может показаться, что она является естественным обобщением вределения энтропии для дискретной случайной величины (см. задачу З.б). Определим реднюю условную дифференциальную энтропию Х при заданном 1' как Ь(Х ~ К) = — ~ ~ р(х, у)!ойр(х ( у)с1хЫу. (3.2.19) Тогда среднюю взаимную информацию можно выразить как 1(Х;Г) = Ь(Х)-ЩХ ~ 1') б-56 81 > Р(У)=>~Р(У!А)+Р(У~ — А)3 (3224) 1 Здс В гл. 7 мы покажем, что средняя взаимная информация 1(Х;У), определяемая (3.2.23 Я б представляет пропускную способность канала с двоичным входом и аддитивнь дин с| гауссовским шумом. Эф 3.3. КОДИРОВАНИЕ ДЛЯ ДИСКРЕТНЫХ ИСТОЧНИКОВ В разд. 3.2 мы ввели меру для информационного содержания дискретной случайн данн величины Х. Когда Х является выходом дискретного источника, энтропия Н(Х) источнин(степеи определяет среднее количество информации на символ, выдаваемой источником.
В этфольш' разделе мы рассмотрим процесс кодирования выхода источника, т.е. проце~высокн представления выхода источника последовательностью двоичных цифр. Эффективносф~о>кно способа кодирования источника можно измерить путйм сравнения среднего количестивремя двоичных символов кодера на один символ источника и энтропии источника Н(Х).
1кодовь На первый взгляд может показаться, что кодирование дискретного источника ~образо конечным объемом алфавита является простой проблемой. Однако это верно, только есн~ источник без памяти, т.е. когда последовательные символы источника статистичесн1 независимы и каждый символ кодируется отдельно. Дискретный источник без памя4 (ДИБП) является простейшей моделью, которую можно предложить для физическоп источника. Эта идеализированная математическая модель подходит для немногн~ физических источников. Например, можно легко убедиться в том, что последовательнйнеэфф( выдаваемые буквы устройством, печатающим осмысленный текст, статистичес н взаимосвязаны, С другой стороны, если печатается компьютерная программа на язы Фортран, то можно о>кидать, что зависимость в последовательности выходных символ проявится значительно меньше. Во всяком случае, мы покажем, что всегда бол эффективно кодировать блок символов источника вместо того, чтобы кодировать каж одовь символ отдельно.
Если размер блока достаточно большой, то среднее количество символ кодера на один выходной символ источника можно сделать сколь угодно близким энтропии источника. столько 3.3.1. Кодирование дли дискретных источников без памяти и 1 Предположим, что ДИБП выдает буквы илн символы каждые т, секунд. Каждьи>днозн символ выбирается из конечного алфавита хь 1=1, 2, ..., я'., с вероятностью Р(я1одним 1=1,2, ..., Е. Энтропия ДИБП в битах на символ 'декоди я к>знача Н(Х) = — ~Р(х,) 1оя> Р(х,) < 1од,.(., (3.3.1) юм причем равенство имеет место, если все символы равновероятны. Н(Х) определяа Те< среднее число бит на символ источника, а производительность источника в битахнкон „„ определяется как Н(Х)/т, .
Кодовые слова фиксированной длины. Сначала рассмотрим схему блоковойеколь 1 г кодирования, которая сопоставляет уникальный ряд из л двоичных символов с ка>кдьд символом источника. Поскольку имеется Е возмо>кных символов источника, то числ двоичных символов кодера на один символ источника при уникальном кодировании л =1оя> Е, (332) 1 Иа когда Е равно целой степени основания 2, и л =~1ой ь!+1, (33,3), ~ Эт когда я'. не равно целой степени основания 2. и'> Ф >,У 108, У.. Следовательно, требуется минимальное целое значение для У, равное Ф =1,У1ойз У.3+1.
(3.3.4) Теперь среднее число символов кода на символ источника )с=ззЧУ, и, таким образом, кзффективность кодирования сокращается примерно в,У раз по сравнению с 1осимвольным кодированием, описанным выше. Взяв У достаточно большим, можно делать эффективность процедуры кодирования, измеренную отношением УН(Х)/)т', как годно близкой к единице.
Методы кодирования, описанные выше, не приводят к ,скажевиям, так как кодирование символов источника или блоков таких символов в одовые слова выполняется однозначно (уникально). Такие типы кодов названы есшумными. Теперь предположим, что мы пытаемся уменьшить скорость кодирования Я путем мвгчения условия однозначности процесса кодирования.
Например, предположим, что олько доля А блоков символов источника кодируется однозначно. Конкретно, выберем "-1 наиболее вероятных .У-символьных блоков и будем кодировать каждый из них днозначно, в то время как оставшиеся У.' — (2 — 1) блоков длины У будем представлять дним оставшимся кодовым словом. Эта процедура кодирования вызовет ошибку :кодирования каждый раз, когда источник выдаст такой маловероятный блок. Пусть Р,, значает вероятность такой ошибки.
Отталкиваясь от этой процедуры кодирования, 1еннон (1948) доказал следующую теорему кодирования источника. Теорема кодирования источника 1. Пусть Х вЂ” это ансамбль символов ДИБП с >вечной энтропией Н(Х). Блоки из,У символов источника кодируются в двоичные кодовые ива длиной М. Для любого а>0 вероятность Р,, ошибки декодирования можно сделать юдь угодно малой, если Ф Я = — > Н(Х)+а У (3.3.5) Удостаточно велико.
Наоборот, если Этот параметр не следует путать со скоростью передачи информации от двоичного источника, тользуемой, в част ности, в гл. 4. По своему смыслу используемый здесь параметр А можно было бы назвать ~траты (на кодирование)» (прп). 83 Здесь |х3означает наибольшее целое, меньшее, чем х. з Я будем называть скоростью кодирования . Она определяет число символов кодера на ~дии символ источника. ПосколькУ У1(Х)< 1ойз У. „то Я > Н(Х), Эффективность кодирования для ДИБП определяется отношением Н(Х)(К Видим, что коли У, равно степени числа 2 и символы источника равновероятны, то Я=Н(Х), дедовательно, код фиксированной длины с Я двоичными символами на символ источника данном случае обеспечивает стопроцентную эффективность.
Однако, если У. не равно взепени 2, но символы источника все еще равновероятны, Я отличается от Н(Х) самое 1ольшее на один бит на символ. Если 1ой У»1, эффективность такой схемы кодирования сока. С другой стороны, если У. мало, эффективность кода с фиксированной длиной яно увеличить путем кодирования последовательности из У символов источника за 1ремя .й,. Чтобы выполнить такое кодирование, мы должны выбрать ьх уникальных 1оловых слов. Используя кодовую последовательность из У двоичных символов, мы можем 1бразовать 2" возможных кодовых слов. Число Ф должно быть выбрано так, чтобы 4 Я < Н(Х)-е, тогда Р, сколь угодно близка к 1 при достаточно больших Х Исходя из этой теоремы мы видим, что среднее число бит на символ источни требуемое для кодирования выхода ДИБП с произвольно малой вероятностью ошиб декодирования, ограничено снизу энтропией источника Н(Х).
С другой стороны, ес /1 < Н(Х), вероятность ошибки декодирования приближается к 100 %, если / произвольн увеличивать. Рис. 3. Кодовые слова переменной длины. Если символы источника неравновероятны, болс» эффективный метод кодирования сводится к использованию кодовых слов перемени длины. Примером такого кодирования является код Морзе, который восходит девятнадцатому веку.
В коде Морзе символам, возникающим более часто, сопоставляю более короткие кодовые слова, а символам, возникающим менее часто, сопоставляю более длинные кодовые слова. Следуя этой общей идее, мы можем учесть вероятное различных символов источника при выборе кодовых слов. Проблема в том, что предложить метод выбора кодовых слов для символов источника. Этот метод кодирован назван энтропийным кодированием. оичи| ван Код чае 1 Ясн Нап ОЗН8 днее Таблица 3.3.1. Коды пе еменной длины Символ Р(а„) Код 1 Код 11 Код П1 1 ыло овлет 1/2 1/4 1/8 1/8 1 00 01 10 0 10 110 111 0 01 011 111 а, Нер ~воичнг 1рефик< Для примера предположим, что выходные символы ДИБП а„а„а„а4 соответствующими вероятностями Р(а,) = Т, Р(о, / = —,, Р(о, / = Р(о„/ = —, кодируются те1 как показано в табл.3,3.1, Код 1 имеет переменную длину и имеет принципиальны~ Сна недостаток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
