Теория информации


Сжатие информации


Цель сжатия - уменьшение количества бит, необходимых для хранения или передачи заданной информации, что дает возможность передавать сообщения более быстро и хранить более экономно и оперативно (последнее означает, что операция извлечения данной информации с устройства ее хранения будет проходить быстрее, что возможно, если скорость распаковки данных выше скорости считывания данных с носителя информации). Сжатие позволяет, например, записать больше информации на дискету, "увеличить" размер жесткого диска, ускорить работу с модемом и т.д. При работе с компьютерами широко используются программы-архиваторы данных формата ZIP, GZ, ARJ и других. Методы сжатия информации были разработаны как математическая теория, которая долгое время (до первой половины 80-х годов), мало использовалась в компьютерах на практике.

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

значений одной д.с.в. .

Доказано1)

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

Кроме того, Доказано2) утверждение о том, что существует такое кодирование (Шеннона-Фэно, Fano), что .

Рассмотрим д.с.в. и , независимые и одинаково распределенные. и , следовательно,

Вместо и можно говорить о двумерной д.с.в. . Аналогичным образом для -мерной д.с.в. можно получить, что .

Пусть , где , т.е. - это количество бит кода на единицу сообщения . Тогда - это среднее количество бит кода на единицу сообщения при передаче бесконечного множества сообщений . Из

для кода Шеннона-Фэно для следует для этого же кода.

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


Начало    Вперед