В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 143
Текст из файла (страница 143)
Глава начинается с обсуждения дискпюго косинуснога преобразовашш, представляющего собои ву ратного метод волнового кумна 1 многих алгоритмов сжатия с потерями. Затем изучается ,б ст ая и эффективная технология, получающая всеболее р ееши акое сжатия, ыстра знных ч звычайно аспространение, Методы сжатия изображений и видеоданных чрез важны для разработки высокопроизводительных мультимедийных сетей.
1й.1. Информация и энтропия 617 Глава 19 Теоретические основы сжатия данных Соврел~енная точка зрения заключается в том. что чем б олыяе вероятность появления сообщений, тем меньше инфюрмашти в каждом из ннх, и любое математическое онреЛеление информации до чжно следовать атой нде, То есть объем информации, переносимый символом, знаком, сообщеннел~ или наблюлением во множестве подобных событий, должен уменьшаться с увелнчениен частоты появления в атом люожестве.
Колин Четллс О челоееческок общении Прежде чем начать обсуждение проблем сжатия данных, освоим теоретический фундамент — теорию информации. Основы теории информации были заложены Клодом Шенноном (С1апбе 5(таппоп) в процессе исследования пропускной способности информационного канала. Теория информации получила самые разнообразные применения. Для настоящего обсуждения важно то, что теория информации определяет предел, до которого для заданного потока данных можно сжимать инфюрмацию без потерь. Эта глава начинается с обзора концепций теории информации, после чего рассматривается применение теории информации к кодированию. 19.1.
Информация и энтропия Основу теории информации составляют две математические концепции, названия которых могут ввести в заблуждение: информация и энтропия. Как правило, под информацией (ш(огптаг(оп) подразумевается нечто, относящееся к смыслу, а энтропия (епггору) — термин иа второго закона термодинамики. В теории информации информация имеет отношение к снижению неосведомленности о некоем событии, а энтропией называется усреднение информационных значений, подчиняюгпееся тем же математическим законам, что и термодинамическая энтропия. Рассмотрим это новое определение информации на примере. Представим инвестора, которому требуется информация (совет) о состоянии определенных цепных бумаг. Этот инвестор советуется с брокером, обладающим специальной информацией (знапием) в данной области.
Брокер информирует (сообшает) инвестора, что сегодня утром нагрянул федеральный инспектор, искавший информацию (свидетельства) о возможном мошенничестве, в котором замешана корпорация, выпустившая именно эти атщии, В ответ на з ту информацию (данные) инвестор решает продать свои акции, о чем и информирует (уведомляет) брокера. Другими словами, будучи неуверенным в вопросе о том, как распорядиться своим портфелем ценных бумаг, клиент консультируется с кем-то более уверенным в данном вопросе.
Брокер уменьшает неуверенность клиента в этой области, рассказав ему о визите федерального инспектора, который пришел, чтобы раарешить собственную профессиональную неуверенность Кульминацией возрастающей уввренностли клиента о состоянии своих ценных бумаг становится устранение тинтвврвнностни брокера о намерении клиента продать зти ценные бумаги. Хотя термин информация может означать уведомление, знание или просто данные„в калсдом случае получение информации эквивалентно уменьшению неуверенности. Таким образом, информация означает положительную разность между двумя уровнями неуверенности. Информация Чтобы рассматривать понятие информации с точки зрения математики, нам нужна определенная величина, топящаяся для измерения количества информации.
Впервые эту проблему сформулировал и решил Хартли (Нзгс!еу) в 1928 г., изучая телеграфную связь. Хартли заметил, что если вероятность того, что некоторое событие произойдет, высока (близка к 1), неуверенность в том, что это событие произойдет, невелика. Если впоследствии мы узнаем, что это событие произошло, то количество полученной нами информации будет невелико. Таким образом, внушающей доверие мерой информации может служить величина, обратная вероятности некоего события, — 1/р. Например, если происходит событие, вероятность которого равна 0,25, то мы получаем больше информации, чем если произойдет событие, вероятность которого равна 0,5. Если мера информации равна 1/р, тогда первое событие обладает информацией 4 (1/0,25), а количество информации о втором событии равно 2 (1/0,5).
Но с использованием этой меры количества информациии связано две трудности. + Эта единица измерения, кажется, ене работаета с последовательностями событий. Рассмотрим двоичный источник, генерирующий поток из единиц и нулей с равной вероятностью значения каждого бита. Таким образом, каждый бит несет количество информации, равное 2 (1/0,5). Но если бит Ь| несет в себе 2 единицы информации, то сколько информации содержится в строке из двух битов Ь~Ьт? Эта строка может содержать одну из четырех возможных комбинаций битов, причем каждое из четырех значений строка может принимать с вероятностью 0,25. Таким образом, при использовании б18 Глава 19.
Теоретические основы сжатия данных 19.1. Информация и энтропия 619 10 в качестве меры количества информации величину 1/Р два бита будут дуг содержать четыре единицы информации. Продолжая данные рассуждения количество информации, содержащееся в трех битах (ЬгЬгЬг), равно восьми Это означает. что первые два бита, Ьг и Ьг, несут по две единицы информ рмации, а третий бит (Ьг) добавляет сразу четыре единицы информации. Следую едующий бит (Ь,) добавит к последовательности уже восемь единиц информации и т, д Это не кажется разумным, + Рассмотрим событие, приводящее к изменению двух или более независи ависимых переменных. Примером такого события может быть сигнал, кодируемы" емый при помощи так называемого метода фазовой манипуляции, для которого используется четыре возможных фазы и две амплитуды.
Олин элемент такого сигнала содержит две единицы информации для амплитуды и четы етыре для фазы, итого шесть единиц. В то же время, каждый элемент сигнала может иметь восемь возможных значений, и поэтому должен соответствовать восьми единицам информации, если пользоваться принятой нами мерой Картли разрешил данную проблему, прологарттфъшровав данную величину, то есть он предложил в качестве меры количества информации события х функцию 1оя(1/Р(х)), где Р(т) означает вероятность событиях. Формально можно написать 1(х) = !оп (1/Р(х) ) = — 1оп Р(х). (19.1) Эта мера количества информации «работает» и позволяет получить множество полезных результатов.
Основание логарифма может быть взято произвольно, но удобнее всего логарифмнровать по основанию 2. в этом случае единица информа- ции называется битом. Правильность такого подхода должна стать очевидной по мере чтения данного раздела, и далее подразумеваются логарифмы по основанию 2. Можно отметить следутощее: + Один бит, с равной вероятностью принимающий значения 0 и 1, несет в себе один бит информации (1оя(1/0,5) = 1). Строка из двух битов может принимать четыре равновероятных результата с вероятностью 0,25 и содержит два бита информации (1оя(1/0,25) = 2).
Таким образом, второй бит добавляет один бит информации. В последовательности из трех независимых битов третий бит также добавляет один бит информации (! оп(1/0,125) = 3) и т. л. + В примере сигнала, кодированного методом фазовой манипуляции, олин элемент сигнала несет один бит информации для амплитуды и два бита для фазы, итого три бита, что согласуется с наблюдением о восьми воаможных результатах. На рис. 19.1 показан график зависимости количества информации единичного события от вероятности этого события.
Когда вероятность события п иближа- Р ется к единице (событие происходит почти наверняка), количество информашш, содержащееся в данном событии, приближается к нулю. И наоборот, когда ве- роятность события приближается к нулю (событие практически невероятна), количество информации, содержащееся в данном событии, приблигкается к бесконечности. 1,0 0,0 Вероятность Р Рис. 10.1.
Количество информации, содержащееся в одном собитии Энтропия Другая важная концепция теории информации — энтропия, Эта концепция была предложена в 1948 г. осттователем теории информации Шенноном (5паппогт). Шеннон определил энтропию как среднее количество информации, получаемое от значения случайной переменной. Предположим, что имеется случайная переменная Х, способная принимать значения хь хь ..., хт, и что соответствующие вероятности кагкдого исхода равны Р(хг), Р(х,)„..., Р(хк), В последовательности из К переменных Х результат х в среднем будет выбран КР(х) раз. Таким образом, среднее количество информации, получаемое от К событий, равно (будем использовать обозначение Рг для Р(х.)); КР~ 1оя (1/Р~) + ...
+ КРя 1оя (1/Рг). Если разделить это выражение на К, то мы получим среднее количество информации для одного результата случайной переменной, называемое энтропией Х и обозначаемое как Н(Х); к н Н(Х) = ~~г~Р, 1ой(1/Рг) = -~~ Р,1ой(Р1). (19.2) гн гм Функция Н часто выражается как перечень вероятностей возможных результатов Н(Рг Р, Р«) 620 Глаэа19. гворетическиеосновысжатияданних 19.1.
Информация и энтропия 621 Для примера рассмотрим случайную переменную Х, принимающую два возможных значения с соответствующими вероятностями Ри 1 — Р. В этом случае ассоциированная с Х энтропия будет равна Н(Р, 1 — Р) = — Р !08(Р) — (1 — Р)!оя(1 — Р), На рис. 19.2 показан график Н(Х) для данного случая как функция от Р. По этом графику можно отметить несколько важных особенностей энтропии.
Во-первых если одно из двух событий является достоверным (Р = 1 или Р = О), тогда энтропия равна нулю'. Одно из двух событий должно произойти, и никакой информации о том, что одно из них произошло, не содержится. Во-вторых, максимального значения функция Н(Л) достигает, когда два результата равновероятны. Это также обоснованно: когда два результата равновероятны, неуверенность в реаультате максимальна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
