Другие методы сжатия данных

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

Методы символьного кодирования проверяют поток передаваемых данных по одному передаваемому биту, затем заменяют последовательность из общих или повторяющихся символов более короткой (алгоритм Лемпеля-Зива [Lempel-Ziv] является примером именно такого метода сжатия). Принимающее устройство распознает сжатую последовательность и восстанавливает исходную последовательность символов.

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

В методе статистического кодирования рассчитывается вероятность появления двух индивидуальных символов или символьного шаблона. Общие шаблоны могут заменяться более короткими кодами, тогда как менее часто встречаемые шаблоны заменяются более длинными кодовыми последовательностями. В методе кодирования Хаффмана (Huffman) используется именно такой способ. В этом методе вырабатываются очень короткие последовательности, которые легко расшифровываются, при этом исключается возможность его ошибочного распознавания в качестве части другой кодовой группы.

Количество двоичных разрядов, необходимых для представления символа с использованием метода сжатия Хаффмана (Huffman), часто выражается следующим образом:

B = целое число А (–log2P),

где

B — действительное количество битов,

P — вероятность появления символа.

Член, представляющий «целое число» в вышеприведенном выражении, указывает, что полученное значение должно быть округлено до целого значения ближайшего числа. Например, если буква «Е» имеет вероятность появления в обычном тексте, равную 0,13 (или 13%), то тогда значение В составляло бы [целое число (2,94)], то есть равнялось бы 3. Следовательно, понадобилось бы 3 разряда для представления символа «Е», вместо 7 разрядов из 8-битового символьного кода, используемого в кодировке ASCII. Варианты метода сжатия Хаффмана (Huffman) используются для сжатия данных методом длин отрезков для передачи в аппаратуре факсимильной связи.

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

Протоколы могут быть символьно-ориентированными, такие, например, как Протокол двоичной синхронной передачи данных (протокол BiSync) компании АйБиЭм (IBM), быть байт-ориентированныыми подобно Протоколу сообщений цифровой передачи данных (протокол DDCMP) компании Диджитал Экуипмент Корпорэйшен (Digital Equipment Corporation — DEC), либо быть бит- ориентированными, подобно Протоколу синхронного управления передачей данных (протокол SDLC) компании АйБиЭм (IBM).

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

Примеры каждого из трех протоколов приведены на рис. 9.16.

Рис. 9.16.Примеры протоколов

В символьно-ориентированном протоколе BiSync используются различные символы из символьного набора для указания начала заголовка, начала текста сообщения и конца текста. Символ, указывающий на начало заголовка сообщения и получивший обозначение SOH, обеспечивает накопление символов блокового контроля (BCC) метода избыточных кодов, необходимых для восстановления. Байт-ориентированный протокол DDCMP начинается с заголовка, который содержит информацию о типе сообщения, количестве символов в тексте, номере сообщения, адресе назначения и кода циклического избыточного контроля (СRС). Затем следует текст самого сообщения, и фрейм заканчивается вторым кодом циклического избыточного контроля (СRС). Фрейм бит-ориентированного протокола SDLC начинается и заканчивается собственной уникальной битовой последовательностью: 01111110.

Биты, изображенные в последовательности кадрового контроля (FCS), представляют коды циклического избыточного контроля (СRС) фрейма. Самой важной особенностью является то, что сообщение всегда является прозрачным, т.е. оно может включать любую последовательность битов без опасности спутать ее с контрольным символом.