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

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

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

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

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

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

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

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

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

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

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

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

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

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

R = k/n (2.3)

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

Дата добавления: 2014-01-07