Алгоритмы кодирования и сжатия данных

Введение

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

Проблема измерения количества информации

Измерение информации в быту (информация как новизна). Вы получили какое-то сообщение (например, прочитали статью в любимом журнале). В этом сообщении содержится какое-то количество информации. Как оценить, сколько информации вы получили? Другими словами, как измерить информацию? Можно ли сказать, что чем больше статья, тем больше информации она содержит? Разные люди, получившие одно и то же сообщение, по-разному оценивают количество информации, содержащееся в нем. Это происходит оттого, что знания людей об этих событиях, явлениях до получения сообщения были различными. Поэтому те, кто знал об этом мало, сочтут, что получили много информации, те же, кто знал больше, чем написано в статье, скажут, что информации не получили вовсе. Таким образом, количество информации в сообщении зависит от того, насколько ново это сообщение для получателя. При таком подходе непонятно, по каким критериям можно ввести единицу измерения информации. Следовательно, с точки зрения информации как новизны мы не можем оценить количество информации, содержащейся в научном открытии, новом музыкальном стиле, новой теории общественного развития.

Измерение информации в технике. В технике часто используют простой и грубый способ определения количества информации, который может быть назван объемным. Он основан на подсчете числа символов в сообщении, т.е. связан с его длиной и не учитывает содержания. Длина сообщения зависит от числа различных символов, употребляемых для записи сообщения. Например, слово “мир“ в русском алфавите записывается тремя знаками, в английском – пятью (реасе), а в КОИ-8 – двадцатью четырьмя битами (111011011110100111110010). В вычислительной технике применяются две стандартные единицы измерения: бит (binary digit) и байт (byte). Конечно, будет правильно, если вы скажете: “В слове “Рим” содержится 24 бита информации, а в сообщении “миру мир!” – 72 бита”. Однако, прежде чем измерить информацию в битах, вы определяете количество символов в этом сообщении.

Нам привычнее работать с символами, машине – с кодами. Каждый символ не случайно кодируется 8-битным кодом. Мы уже обсуждали, почему это так. Поэтому для удобства была введена более “крупная” единица информации в технике (преимущественно в вычислительной) – байт. Теперь вам легче подсчитать количество информации в техническом сообщении – оно совпадает с количеством символов в нем.

Измерение информации в теории информации (информация как снятая неопределенность). Пусть имеется колода из 32 игральных карт (от семерок до тузов). Задумывается одна из карт. Необходимо, задавая вопросы, на которые будут даны ответы “да” или “нет”, угадать задуманную карту. Первый вопрос: “Задумана карта черной масти?” Ответ: “Нет”. Ответ уменьшает неопределенность вдвое и приносит отгадывающему 1 бит информации. Второй вопрос: “Задумана карта бубновой масти?” Ответ: “Да”. Это еще один бит информации, исходная неопределенность уменьшилась в 4 раза. Третий вопрос: “Задумана карта – картинка?” Ответ: “Нет”. Третий бит информации, первоначальная неопределенность уменьшилась в 8 раз. Четвертый вопрос: “Задуманная карта младше девятки?” Ответ: “Да”. Еще один бит информации, первоначальная неопределенность уменьшилась в 16 раз. Пятый вопрос: “Задумана восьмерка бубновая?” Ответ: “Нет”. Отгадывающий получил пятый бит информации, исходная неопределенность уменьшилась в 32 раза. Последний ответ позволяет с уверенностью сказать, что была задумана бубновая семерка. Неопределенности не осталось. Очень приближенно можно считать, что количество информации в сообщении о каком-то событии совпадает с количеством вопросов, которые необходимо задать. Чтобы получить ту же информацию, ответ на эти вопросы может быть лишь “да” или “нет”. Причем событие, о котором идет речь, должно иметь равновероятные исходы (монета может упасть только “орлом” или “решкой” – два равновероятных исхода, задуманной может оказаться любая из 32 карт – 32 равновероятных исхода и т. п.).

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

В 100 Мб можно уместить:

Страниц текста – 50 000 или 150 романов

Цветных слайдов высочайшего качества – 150

Аудиозапись речи видного политического деятеля – 1.5 часа

Музыкальный фрагмент качества СD-стерео – 10 минут

Фильм высокого качества записи – 15 секунд

Протоколы операций с банковским счетом – за 1000 лет

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

H(U) = M {-logP(u_i)} = М{}=

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

Чем больше энтропия источника, тем больше степень неожиданности выдаваемых им сообщений в среднем, т.е. тем более неопределенным является ожидание сообщений. Если вероятности появления каждого из возможных сообщений одинаковы, то в этом случае энтропия источника максимальна, а сжимать эти сообщения практически бесполезно. Но если одни сообщения (символы) появляются чаще других, то результат работы источника может быть с успехом подвергнут сжатию.