Предисловие переводчика

Никто не будет отрицать, что политическая и экономическая активность в современном обществе в значительной степени держится на надежных коммуникациях, в которые вовлечены огромные объемы информации. С целью обеспечения информационных средств сообщения были разработаны и продолжают разрабатываться всевозможные электронные устройства и программные комплексы для передачи, отображения и хранения информации. Это телеграф, радио, телефония, телевидение, модемы, космические линии связи, оптические диски и многое другое. Основная проблема, которую необходимо решить при построении системы коммуникации, была впервые сформулирована Клодом Шенноном в 1948 году:

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

Такая точная и ясная постановка проблемы коммуникации оказала огромное воздействие на развитие средств связи. Возникла новая научная отрасль, которая стала называться теорией информации. Главная идея, обоснованная Шенноном, заключается в том, что надежные коммуникации должны быть цифровыми, т.е. задачу связи следует рассматривать как передачу двоичных цифр (битов).

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

Рис. 1. Блок-схема системы связи.

Кроме того, Шеннон доказал, что задачу надежной связи можно разложить на две подзадачи без умаления ее эффективности. Эти две подзадачи называются кодированием источника и кодированием канала (см. рис. 2).

Рис. 2. Системы связи с раздельным кодированием.

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

Задачей кодирования источника является создание кодера источника, который производит компактное (укороченное) описание исходного сигнала, который необходимо передать адресату. Источником сигналов может служить текстовый файл, цифровое изображение, оцифрованная музыка или телевизионная передача. Это сжатое описание сигналов источника может быть неточным, тогда следует говорить о расхождении между восстановленным после приема и декодирования сигналом и его оригиналом. Это обычно происходит при преобразовании (квантовании) аналогового сигнала в цифровую форму.

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

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

Обратимся к кодированию источников. Как и в обычном тексте в различных источниках цифровых данных имеются избыточные данные, то есть, некоторые участки, которые, "содержатся" в других частях данных источника. Поэтому возникает вопрос: что есть наиболее компактное представление данных источника? На этот вопрос ответ был дан Шенноном. В своей пионерской работе по теории информации он ввел числовую характеристику источника, которая называется энтропией. Фундаментальное значение этой величины состоит в том, что она задает нижнюю границу возможного сжатия. Кроме того, имеется теорема, которая утверждает, что к этой границе можно приблизиться сколь угодно плотно с помощью подходящего метода кодирования источника. Например, известно, что энтропия усредненного английского текста равна примерно 3.2 бит/букву. В компьютерном представлении одна буква занимает 8 бит (стандартный код ASCII). Значит, при сжатии типичного текстового файла на английском языке достигается сжатие примерно в 2.5 раза.

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

Здесь мы приходим к другой важной проблеме: каково наиболее компактное представление информации, если допускается неточное восстановление сжатых данных. Такое сжатие называется сжатием с частичной потерей информации. Сжатие с потерями, но существу, предполагает уменьшение энтропии исходной информации. На практике компрессия с потерями применяется, например, при сжатии цифровых изображений и оцифрованного звука. Величина допустимого расхождения оригинальных данных и их разжатой копии часто определяется субъективно по их неразличимости глазом или ухом человека, который, в конечном итоге является получателем данного рода информации.

Эти проблемы будут подробно разбираться в книге с привлечением большого числа примеров, таблиц и иллюстраций. Многие важные методы и алгоритмы сжатия данных представлены в виде программ, написанных на языке популярных пакетов Matlab и Matematica. Большинство из них будут тщательно разобраны но шагам применительно к конкретным сжимаемым образцам и фрагментам.

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

Москва                                                                                                                      
Владимир Чепыжов