Реферат: Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия
Если имеются система разрушающего сжатия со скоростью и искажениями R 1 иD 1 соответственно и вторая система со скоростью R 2 и искажениями D 2, то первая из них лучше, если R 1 ‹R 2 и D 1 ‹ D 2 . Однако, к сожалению, невозможно построить систему разрушающего сжатия, обеспечивающую одновременно снижение скорости 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= 221 , или 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).
Для сжатия данных возьмем кодер, использующий следующую таблицу перекодирования данных источника в кодовые слова (вопрос о выборе таблицы оставим на будущее):
| Кодер | |
| Отсчет | Кодовое слово |
| 3 | 001 |
| 2 | 01 |
| 1 | 1 |
| 0 | 000 |
Используя таблицу кодирования, заменим каждый элемент вектора X соответствующей кодовой последовательностью из таблицы (так называемое кодирование без памяти). Сжатые данные (кодовое слово B ( X )) будут выглядеть следующим образом:
B ( X ) = ( 0,0,1,0,0,1,0,1,1,0,0,1,0,1,0,1,1,0,1,0,1,1,0,0,0,1,1,1,0,0,0).
Коэффициент сжатия при этом составит r = 32/31, или 1,03. Соответственно скорость сжатия R = 31/16 бит на отсчет.
Пример 3. Сравним два различных кодера, осуществляющих сжатие одного и того же вектора данных
X = ABRACADABRA .
Первый кодер - кодер без памяти, аналогичный рассмотренному в предыдущем примере (каждый элемент вектора X кодируется независимо от значений других элементов - кодер без памяти ). Таблица кодирования для него выглядит следующим образом:
| Кодер 1 | |
| Символ | Кодовое слово |
| A | 0 |
| B | 10 |
| R | 110 |
| C | 1110 |
| D | 1111 |
Второй кодер при кодировании текущего символа учитывает значение предшествующего ему символа, таким образом, кодовое слово для текущего символа A будетразличным в сочетаниях RA , DA и CA ( иными словами, код обладает памятью в один символ источника):
| Кодер 2 | |
| Символ, предыдущий символ | Кодовое слово |
| (A,-) | 1 |
| (B,A) | 0 |
| (C,A) | 10 |
| (D,A) | 11 |
| (A,R) | 1 |
| (R,B) | 1 |
| (A,C) | 1 |
| (A,B) | 1 |
Кодовые слова, соответствующие вектору данных X = ABRACADABRA , при кодировании с использованием этих двух таблиц будут иметь вид:
B 1 ( X ) = 01011001110011110101100,
B 2 ( X ) = 10111011111011.
Таким образом, скорость сжатия при использовании кодера 1 (без памяти) составит 23/11 = 2,09 бита на символ данных, тогда как для кодера 2 - 13/11 = =1,18 бита на символ. Использование второго кодера, следовательно, является более предпочтительным, хотя он и более сложен.
ЛИТЕРАТУРА
1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.
2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для вузов. / В.И. Нефедов, В.И. Халкин, Е.В. Федоров и др. – М.: Высшая Школа, 2001 г. – 383с.
3. Цапенко М.П. Измерительные информационные системы. – М.: Энергоатом издат, 2005. - 440с.
4. Зюко А.Г. , Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.
5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.