Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия (стр. 2 из 3)

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

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

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

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

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

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

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

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

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

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

Вектор данных 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, определяемый как отношение

размер данных источника в битах nlog₂ (dimA)(12)

r=

= ,

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

где dimA - размер алфавита данных 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)

Параметр Rхарактеризует скорость сжатия в битах на один отсчет источника, величина D является мерой среднеквадратического различия между X* иX.

Если имеются система разрушающего сжатия со скоростью и искажениями R₁ иD₁ соответственно и вторая система со скоростью R₂ и искажениями D_2, то первая из них лучше, если R₁ ‹R₂ и D₁ ‹ D₂. Однако, к сожалению, невозможно построить систему разрушающего сжатия, обеспечивающую одновременно снижение скорости R и уменьшение искажений D, поскольку эти два параметра связаны обратной зависимостью. Поэтому целью оптимизации системы сжатия с потерями может быть либо минимизация скорости при заданной величине искажений, либо получение наименьших искажений при заданной скорости сжатия.

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

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

Пример 1. Предположим, что источник генерирует цифровое изображение (кадр) размером 512*512 элементов, содержащее 256 цветов. Каждый цвет представляет собой число из множества {0,1,2… 255}. Математически это изображение представляет собой матрицу 512х512, каждый элемент которой принадлежит множеству {0,1,2… 255}. (Элементы изображения называют пикселами).

В свою очередь, каждый пиксел из множества {0,1,2… 255} может быть представлен в двоичной форме с использованием 8 бит. Таким образом, размер данных источника в битах составит 8х512х512= 2²¹, или 2,1 Мегабита.

На жесткий диск объемом в 1 Гигабайт поместится примерно 5000 кадров изображения, если они не подвергаются сжатию (видеоролик длительностью примерно в пять минут). Если же это изображение подвергнуть сжатию с коэффициентом r = 10, то на этом же диске мы сможем сохранить уже почти часовой видеофильм!

Предположим далее, что мы хотим передать исходное изображение по телефонной линии, пропускная способность которой составляет 14000 бит/с. На это придется затратить 21000000 бит/14000 бит/с, или примерно 3 минуты. При сжатии же данных с коэффициентом r = 40 на это уйдет всего 5 секунд !

Пример 2. В качестве данных источника, подлежащих сжатию, выберем фрагмент изображения размером 4х4 элемента и содержащее 4 цвета: R = ="красный", O = "оранжевый", Y = "синий", G = "зеленый":

R	R	O	Y
R	O	O	Y
O	O	Y	G
Y	Y	Y	G

Просканируем это изображение по строкам и каждому из цветов присвоим соответствующую интенсивность, например, R = 3, O = 2, Y = 1 и G = 0, в результате чего получим вектор данных X = (3,3,2,1,3,2,2,1,2,2,1,0,1,1,1,0).