Сжатие без потерь информации

Цель сжатия данных и типы систем сжатия

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

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

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

Ниже приведена условная структура системы сжатия данных:

Данные источника®Кодер®Сжатые данные®Декодер®Восстановленные данные

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

Существуют два типа систем сжатия данных:

· системы сжатия без потерь информации (неразрушающее сжатие);

· системы сжатия с потерями информации (разрушающее сжатие).

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

Вектор данных X ® Кодер ® B (X)® Декодер ® X

 

Вектор данных источника X, подлежащих сжатию, представляет собой последовательность X = (x1, x2,… xn ) конечной длины. Отсчеты xi - составляющие вектора X - выбраны из конечного алфавита данных A.При этом размер вектора данных n ограничен, но он может быть сколь угодно большим. Таким образом, источник на своем выходе формирует в качестве данных X последовательность длиной n из алфавита A .

Выход кодера - сжатые данные, соответствующие входному вектору X, - представим в виде двоичной последовательностиB(X) = ( b1,b2,…bk ), размер которой k зависит от X. Назовем B(X)кодовым словом, присвоенным вектору X кодером (или кодовым словом, в которое вектор X преобразован кодером). Поскольку система сжатия - неразрушающая, одинаковым векторам Xl = Xmдолжны соответствовать одинаковые кодовые слова B ( Xl ) = = B ( Xm ).

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

размер данных источника в битах n log 2 (dim A) (2.2)

r == ,

размер сжатых данных в битах k

где dim A -размер алфавита данных A.

Таким образом, коэффициент сжатия r= 2 означает, что объем сжатых данных составляет половину от объема данных источника. Чем больше коэффициент сжатия r, тем лучше работает система сжатия данных.

Наряду с коэффициентом сжатия r эффективность системы сжатия может быть охарактеризована скоростью сжатия R, определяемой как отношение

R = k/n(2.3)

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