Модемные протоколы сжатия

Протокол MNP5. Реализует комбинацию адаптивного кодирования с применением кода Хаффмена и группового кодирования. При этом хорошо поддающиеся сжатию данные уменьшают свой исходный объем примерно на 50% и, следовательно, реальная скорость их передачи возрастает вдвое по сравнению с номинальной скоростью передачи данных модемом.

На первом этапе процедуры сжатия используется метод группового кодирования для удаления из потока передаваемых данных слишком длинных последовательностей повторяющихся символов. Этот метод преобразует каждую группу из трех и более (вплоть до 253) одинаковых смежных символов к виду символ и число символов. Поскольку групповое кодирование не связано с большими вычислениями, этот метод особенно хорош для реализации в реальном масштабе времени, в частности, при передаче данных по линиям связи. Система группового кодирования проверяет проходящий поток данных. Алгоритм остается пассивным до тех пор, пока в этом потоке не обнаружатся три одинаковых смежных символа. После этого алгоритм начинает счет и удаляет из потока данных до 250 одинаковых следующих друг за другом символов. Счетный байт посылается вслед за тремя исходными символами, и передача продолжается (см. рисунок).

Кодирование группы из трех символов расширяет поток данных.

На втором этапе сжатия данных протокол MNP5 использует адаптивное кодирование на основе метода Хаффмана. Символы, которые встречаются чаще, кодируются с использованием небольшого числа битов. Реже встречающиеся символы передаются с использованием более длинных кодовых последовательностей. Когда формат передаваемых данных относительно хорошо известен и постоянен, кодовые битовые последовательности, или лексемы, могут быть определены заранее. Однако адаптивный алгоритм может подстраиваться под поток данных путем "обучения" с последующим изменением своих лексем.

В протоколе MNP5 определяются 256 лексем для всех возможных 8-разрядных величин (октетов). Лексема состоит из 3-разрядного префикса (заголовка) и суффикса (тела, или основы), который может включать от 1 до 8 разрядов. Как передатчик, так и приемник инициализируют свои символьно-лексемные таблицы одинаковым образом (см. рисунок).

Значение октета (десятичное)	Заголовок лексемы	Тело лексемы

Карта символьно-лексемного кодирования в начале процедуры сжатия данных

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

Протокол MNP7. Используется более эффективный (по сравнению с MNP5) алгоритм сжатия данных и позволяет достичь коэффициента сжатия порядка 3:1. MNP7 использует улучшенную форму кодирования методом Хаффмена в сочетании с марковским алгоритмом прогнозирования для создания кодовых последовательностей минимально возможной длины. Марковский алгоритм может предсказывать следующий символ в последовательности, исходя из появившегося предыдущего символа. Для каждого октета формируется таблица из всех 256 возможных следующих за ним октетов, расположенных в соответствии с частотой их появления. Октет кодируется путем выбора столбца, соответствующего предыдущему октету (озаглавливающему столбец), с последующим отысканием в этом столбце значения текущего октета. Строка, в которой находится текущий октет, определяет лексему точно так же, как в описанном выше случае кодирования с использованием кода Хаффмана. После того как каждый октет будет закодирован, порядок следования записей (октетов) в выбранном столбце изменяется в соответствии с новыми относительными частотами появления октетов.

На рисунке показан пример кодирования последовательности октетов 3120 в предположении, что перед этим был передан октет 0. Из рисунка видно, что в столбце, соответствующем предыдущему октету 0, отыскивается запись (строка) октета 3. После этого передается код Хаффмана для этой записи (октета 3) в таблице. Далее в столбце, соответствующем этому только что переданному октету 3, отыскивается строка с записью следующего октета — в данном случае октета 1, и передается код Хаффмена для этой строки и т.д. В этом примере отсутствует иллюстрация адаптивной части алгоритма, изменяющей порядок расположения октетов в каждом столбце.

Протокол V.42bis. Основан на алгоритме Лемпеля-Зива-Уэлча (LZW-алгоритме), обеспечивающем достижение коэффициента сжатия 4:1 файлов с оптимальной структурой. Входящий поток данных последовательно, символ за символом, сравнивается с имеющимися в словаре последовательностями. После того, как в словаре будет найдена кодируемая последовательность, идентичная входной, модем передает соответствующее ей кодовое слово. Алгоритм динамически создает и обновляет словарь символьных последовательностей.

Эффективность сжатия протокола V.42bis в общем случае зависит от двух основных параметров: размера словаря сжатия и длины строки. С помощью строки передающая сторона описывает определенную последовательность символов в потоке данных от компьютера и заменяет такую последовательность более коротким кодовым словом при передаче. Принимающий модем, получив кодовое слово, трансформирует его в соответствующую строку. При этом, чем больше символов в строке (больше ее длина), тем большие повторяющиеся фрагменты могут заменяться кодовыми словами, следовательно, тем эффективнее может быть сжатие. В том случае, если длинных повторяющихся участков мало, использование более коротких кодовых строк может способствовать получению лучших результатов. Совокупность используемых строк и соответствующих им кодовых слов составляет словарь - его размер определяется в элементах (строках). Структура словаря динамическая, состав элементов изменяется в процессе передачи в зависимости от того, какие последовательности встречаются в потоке данных чаще других. Чем больше размер словаря, тем большее количество различных строк может использоваться в процессе сжатия. Физическим фактором, ограничивающим максимальные размеры параметров протокола V.42bis в модемах различных производителей, является, прежде всего, имеющийся в распоряжении объем оперативной памяти (т.н. "быстрой" ОЗУ).

Само по себе сжатие может быть как полезным, так и нежелательным - в том случае, если передаются практически несжимаемые данные, попытка сжать их приведет к увеличению объема передаваемых данных. Протокол V.42bis способен отслеживать ситуацию, когда сжатие перестает приносить выгоду, и переключаться из режима сжатия в т.н. "прозрачный" режим. Вместе с тем излишне частое переключение из одного режима в другой снижает общую пропускную способность канала. Критерии переключения из режима в режим определяются конкретными производителями, и могут различаться у разных модемов. Интеллект алгоритма "переключений" во многом определяет общий КПД при передаче данных.

Дата добавления: 2014-01-04