Количество информации и энтропия

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

Метод сжатия данных

Сжатие данных применяется для сохранения времени их передачи. Так как на сжатие данных передающая сторона тратит дополнительное время, к которому нужно еще прибавить аналогичные затраты времени на декомпрессию этих данных принимающей стороной, то выгоды от сокращения времени на передачу сжатых данных обычно бывают заметны только для низкоскоростных каналов. Этот порог скорости для современной аппаратуры составляет около 64 Кбит/с. Многие программы и аппаратные средства сети способны выполнять динамическое сжатие данных в отличии от статического, когда данные предварительно сжимаются (например, с помощью популярных архиваторов), а уже затем отсылаются в сеть.

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

Обычно применяются следующие алгоритмы сжатия данных.

Десятичная упаковка. Когда данные состоят только из чисел, значительную экономию можно получить путем уменьшения количества используемых на цифру бит с 7 до 4, используя простое двоичное кодирование десятичных цифр вместо кода ASCII. Просмотр таблицы ASCII показывает, что старшие три бита всех кодов десятичных цифр содержат комбинацию 011. Если все данные в кадре информации состоят из десятичных цифр, то, поместив в заголовок кадра соответствующий управляющий символ, можно существенно сократить длину кадра.

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

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

Коды переменной длины. В этом методе кодирования используется тот факт, что не все символы в передаваемом кадре встречаются с одинаковой частотой. Поэтому во многих схемах кодирования коды часто встречающихся символов заменяют кодами меньшей длины, а редко встречающихся – кодами большей длины. Такое кодирование называется также статистическим кодированием. Из-за того, что символы имеют различную длину, для передачи кадра возможно только бит-ориентированная передача. При статистическом кодировании коды выбираются таким образом, чтобы при анализе последовательности бит можно было бы однозначно определить соответствие определенной порции бит тому или иному символу, или же запрещенной комбинации бит. Если данная последовательность бит представляет собой запрещенную комбинацию, то необходимо к ней добавить еще один бит и повторить анализ. Например, если при неравномерном кодировании для наиболее часто встречающегося символа «Р» выбран код1, состоящий из одного бита, то значение 0 однобитного кода будет запрещенным. Иначе можно будет закодировать только два символа. Для другого часто встречающегося символа «О» можно использовать код 01, а код 00 оставить как запрещенный. Тогда для символа «А» можно выбрать код 001, для символа «П» – код 0001 и т.п.

Неравномерное кодирование наиболее эффективно, когда неравномерность распределения частот передаваемых символов достаточно велика, как при передачи длинных текстовых строк. Напротив, при передачи двоичных данных, например кодов программ, оно малоэффективно, так как 8-битовыекоды при этом распределены почти равномерно. Одно из наиболее распространенных алгоритмов, на основе которых строятся неравномерные коды, является алгоритм Хаффмана, позволяющий строить коды автоматически, на основании известных частот символов. Существуют адаптивные модификации метода Хаффмана, которые позволяют строить дерево кодов «на ходу», по мере поступления данных от источника.

Многие модели коммуникационного оборудования, такие как модемы, мосты, коммутаторы и маршрутизаторы, поддерживают протоколы динамического сжатия, позволяющие сократить объем передаваемой информации в 4, а иногда и 8 раз. В таких случаях говорят, что протокол обеспечивает коэффициент сжатия 1:4 или 1:8. Существуют стандартные протоколы сжатия, например V.42bis, также большое количество нестандартных, фирменных протоколов. Реальный коэффициент сжатия зависит от типа передачи передаваемых данных. Так графические и текстовые данные обычно сжимаются хорошо, а коды программ – хуже.