Цель лекции: изучение алгоритмов сжатия данных и видов сжатия данных.

Содержание:

а) алгоритмы сжатия без потерь;

б) сжатие аудиосигналов;

в) сжатие изображения.

Алгоритмы сжатия без потерь

Код Хаффмана. Код Хаффмана (Huffman code) (201 - это свободный от префикса код, который может давать самую короткую среднюю длину кода я для данного входного алфавита. Самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника, и тогда эта невозможность выполнения обещанного сжатия данных будет связана с алфавитом, а не с методом кодирования. Часть алфавита может быть модифицирована для получения кода расширения, и тот же метод повторно применяется для достижения лучшего сжатия. Эффективность сжатия определяется коэффициентом сжатия. Эта мера равна отношению среднего числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия.

Код Лемпеля-Зива –Уэлча. Основной сложностью при использовании кода Хаффмана является то, что вероятности символов должны быть известны или оценены и как кодер, так и декодер должны знать дерево кодирования. Если дерево строится из необычного для кодера алфавита, канал, связывающий кодер и декодер, должен также отправлять кодирующее дерево как заголовок сжатого файла. Эти служебные издержки уменьшат эффективность сжатия, реализованную с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива (Lempel-Ziv) и его многочисленные разновидности используют текст сам по себе для итеративного построения синтаксически выделенной последовательности кодовых слов переменной длины, которые образуют кодовый словарь.

Алгоритм Хаффмана в факсимильной связи.

Факсимильная передача — это процесс передачи двухмерного образа как последовательности последовательных строчных разверток. В действительности наиболее распространенными образами являются документы, содержащие текст и цифры. Положение строчной развертки и положение вдоль развертки квантуются в пространственные расположения, которые определяют двухмерную координатную сетку элементов картинки, называемых пикселями. Ширина стандартного документа МККТТ определяется равной 8,27 дюймов (20,7 см ), а длина- 11,7 дюймов (29,2 см), почти 8,5 дюймов на 11,0 дюймов. Пространственное квантование для нормального разрешения составляет 1728 пикселей/строку и 1188 строк/документ. Стандарт также определяет квантование с высоким разрешением с теми же 1728 пикселями/строку, но с 2376 строками/документ. Общее число отдельных пикселей для факсимильной передачи с нормальным разрешением составляет 2 052 864, и оно удваивается для высокого разрешения. Для сравнения, число пикселей в стандарте NTSC (National Television Standards Committee — Национальный комитет по телевизионным стандартам) коммерческого телевидения составляет 480 х 460, или 307 200. Таким образом, факсимильное изображение имеет разрешение в 6,7 или 13,4 раза больше разрешения стандартного телевизионнго образа.

Сжатие аудиосигналов.

Аудиосжатие широко применяется в потребительских и профессиональных цифр< аудиопродуктах, таких как компакт-диски (compact disc — CD), цифровая аудиолента (digital audio type — DAT), мини-диск (mini-disk — MD), цифровая компакт-кассета (digital compact cassette — DCC), универсальный цифровой диск (digital versatile disc. DVD), цифровое аудиовещание (digital audio broadcasting — DAB) и аудиопродукция формате МРЗ от экспертной группы по вопросам движущегося изображения (М< Picture Experts Group — (MPEG). К тому же сжатие речи в телефонии, в частности, сотовой телефонии, требуемое для экономии полосы частот и сбережения времени, ни батареи, дало начало процессу разработки множества стандартов сжатия речи, личные алгоритмы применимы к речевым и потребительским сигналам более широкой полосы частот. Аудио- и речевые схемы сжатия можно для удобства разделить согласно приложениям, что отражает некоторую меру приемлемого качества.

Адаптивная дифференциальная ИКМ (АДИКМ). Используя прошлые данные для измерения (т.е. квантования) новых переходим от обычной импульсно-кодовой модуляции (pulse-code modulation — PCM) к дифференциальной (differential PCM — DPCM). В DPCM предсказание следующего выборочного значения формируется на основании предыдущих значений. Устройства квантования называются мгновенными устройствами квантования или устройствами квантования без памяти, так как цифровые преобразования основаны на единичной (текущей) входной выборке. Этими свойствами были неравновероятные уровни источника и зависимые выборочные значения. Корреляционные характеристики источника можно представить во временной области с помощью выборки его автокорреляционной функции и в частотной области — его спектром мощности. Если изучается спектр мощности G_x(f) кратковременного речевого сигнала, как изображено на рисунке 9.2, то видим, что спектр имеет глобальный максимум в окрестности от 300 до 800 Гц и убывает со скоростью от 6 до 12 дБ/октаву. Эта операция производится в контуре сказания и сравнения, верхний контур кодера изображен на рисунке 13.2. Кодер корректирует свои предсказания, составляя сумму предсказанного значения и ошибки предсказания.

Рисунок 13.1 - N- отводный дифференциальный импульсно-кодовый модулятор с предсказанием

Эта модель, использующая 12-отводный синтезатор речи, нашла применение в детских говорящих играх.

Рисунок 13.2 - Блочная диаграмма: моделирование речи с помощью линейного кодера с предсказанием