8. МЕТОДЫ ПЕРЕДАЧИ ДАННЫХ КАНАЛЬНОГО
УРОВНЯ
8.6. Компрессия данных
Компрессия (сжатие) данных применяется для сокращения времени их
передачи. Так как на компрессию данных и на ее декомпрессию тратится дополнительное
время, то выгоды от сжатия данных, обычно, заметны только для низкоскоростных
каналов. Многие программные и аппаратные средства сети способны
выполнять динамическую компрессию данных в отличие от статической, когда данные
предварительно компрессируются (например, с помощью архиваторов типа WinZip), а уже затем отсылаются в сеть.
На практике может использоваться ряд алгоритмов
компрессии, каждый из которых применим к определенному типу данных. Некоторые
модемы (называемые интеллектуальными) предлагают адаптивную компрессию, при
которой в зависимости от передаваемых данных выбирается определенный алгоритм
компрессии. Рассмотрим некоторые из общих алгоритмов компрессии данных.
Десятичная упаковка. Когда данные состоят только из чисел, значительную
экономию можно получить путем уменьшения количества используемых на цифру бит с
7 до 4, используя простое двоичное кодирование десятичных цифр вместо кода
ASCII. Просмотр таблицы ASCII показывает, что старшие три бита кодов десятичных
цифр содержат комбинацию 011. Если все данные в кадре информации состоят из
десятичных цифр, то, поместив в заголовок кадра соответствующий управляющий
символ, можно существенно сократить длину кадра.
Относительное кодирование. Альтернативой десятичной упаковке при передаче
числовых данных с небольшими отклонениями между последовательными цифрами
является передача только этих отклонений вместе с известным опорным значением. Такой
метод используется, в частности, в методе цифрового кодирования голоса ADPCM,
передающем в каждом только разницу между соседними замерами голоса.
Символьное подавление. Часто передаваемые данные содержат большое
количество повторяющихся байт. Например, при передаче
черно-белого изображения черные поверхности будут порождать большое количество
нулевых значений, а максимально освещенные участки изображения — большое количество
байт, состоящих из всех единиц. Передатчик сканирует последовательность передаваемых
байт и, если обнаруживает последовательность из трех или более одинаковых байт,
заменяет ее специальной трехбайтовой последовательностью, в которой указывает
значение байта, количество его повторений, а также отмечает начало этой
последовательности специальным управляющим символом.
Коды переменной длины. В этом методе кодирования используется тот факт, что
не все символы в передаваемом кадре встречаются с одинаковой частотой. Поэтому
во многих схемах кодирования коды часто встречающихся символов заменяют кодами
меньшей длины, а редко встречающихся — кодами большей дайны. Такое кодирование
называется также статистическим кодированием. Из-за того, что символы имеют
различную длину, для передачи кадра возможна только бит-ориентированная
передача.
При статистическом кодировании коды
выбираются таким образом, чтобы при анализе последовательности бит можно было
бы однозначно определить соответствие определенной порции бит тому или иному
символу или же запрещенной комбинации бит. Если данная последовательность бит
представляет собой запрещенную комбинацию, то необходимо к ней добавить еще
один бит и повторить анализ. Например, если при неравномерном кодировании для
наиболее часто встречающегося символа «Р» выбран код 1, состоящий из одного
бита, то значение 0 однобитного кода будет запрещенным. Иначе мы сможем
закодировать только два символа. Для другого часто встречающегося символа «О»
можно использовать код 01, а код 00 оставить как запрещенный. Тогда для символа
«А» можно выбрать код 001, для символа «П» — код 0001 и т. п.
Неравномерное кодирование эффективно, когда
неравномерность распределения передаваемых символов достаточно велика, как при
передаче длинных текстовых строк. Напротив, при передаче двоичных, например
кодов программ, оно малоэффективно, так как 8-битовые коды при этом
распределены почти равномерно.
Одним из наиболее распространенных алгоритмов, на
основе которых строятся неравномерные коды, является алгоритм Хафмана, позволяющий строить коды автоматически, на
основании известных частот символов. Существуют адаптивные модификации метода Хафмана, которые позволяют строить дерево кодов «на ходу»,
по мере поступления данных от источника.
Многие модели коммуникационного оборудования, такие
как модемы, мосты, коммутаторы и маршрутизаторы,
поддерживают протоколы динамической компрессии, позволяющие сократить объем
передаваемой информации в 4, а иногда и в 8 раз. В таких случаях говорят, что
протокол обеспечивает коэффициент сжатия 1:4 или 1:8. Существуют стандартные
протоколы компрессии, например V.42bis, a также
большое количество нестандартных, фирменных протоколов. Реальный коэффициент
компрессии зависит от типа передаваемых данных, так, графические и текстовые
данные обычно сжимаются хорошо, а коды программ — хуже.