Реферат: Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия

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

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

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

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

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

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

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

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

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

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

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

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

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

Выход кодера - сжатые данные, соответствующие входному вектору X, - представим в виде двоичной последовательностиB ( X ) = ( b ₁ , b ₂ ,… b_k ), размер которой k зависит от X . Назовем B ( X ) кодовым словом, присвоенным вектору X кодером (или кодовым словом, в которое вектор X преобразован кодером). Поскольку система сжатия - неразрушающая, одинаковым векторам X_l = X_m должны соответствовать одинаковые кодовые слова B ( X_l ) = = B ( X_m ).

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

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

r = = ,

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

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

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

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

R = k / n ( 13)

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

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

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

X ® Квантователь ®X ^q ® Неразрушающий кодер ®B ( X^q ) ® Декодер ®X*

Как и в предыдущей схеме, X = ( x ₁ , x ₂ ,… x_n ) - вектор данных, подлежащих сжатию. Восстановленный вектор обозначим как X * = ( x ₁ , x ₂ ,… x_n ). Отметим наличие в этой схеме сжатия элемента, который отсутствовал при неразрушающем сжатии, - квантователя.

Квантователь применительно к вектору входных данныхX формирует вектор X^q , достаточно близкий к X в смысле среднеквадратического расстояния. Работа квантователя основана на понижении размера алфавита (простейший квантователь производит округление данных до ближайшего целого числа).

Далее кодер подвергает неразрушающему сжатию вектор квантованных данных X^q таким образом, что обеспечивается однозначное соответствие между X^q и B ( X^q ) (для X_l ^q = X_m ^q выполняется условиеB ( X_l ^q ) = B ( X_m ^q )). Однако система в целомостается разрушающей, поскольку двум различным векторам X может соответствовать один и тот же вектор X * .

Разрушающий кодер характеризуется двумя параметрами - скоростью сжатия R и величинойискаженийD , определяемых как

R = k/n,

D = (1/ n ) ∑( x_i - x_i )² . (14)