В. Столлингс - Современные компьютерные сети (2-е издание, 2003) (1114681), страница 147
Текст из файла (страница 147)
Как сообщалось в [1131, выигрыш от перехода с прото- кола 1ВМ 2780 на протокол 3780 в ряде компьютерных конфигураций составил от 30 до 50 %, и все это благодаря данному методу сжатия данных. 632 Глава 20. Сжатие без потерь 20.1. Методы группового кодирования 633 Групповое кодирование Групповое кодирование представляет собой обобщение метода подавления нулей Групповое кодирование применяется для сжатия повторяющихся данных любого типа.
На рис. 20.1 иллюстрируется применение данного метода к символьным данным. Здесь используются следующие обозначения: + 8, — специальный символ, указывающий на то, что за пим следуют сжатые данные: + Х вЂ” любой повторяющийся символ; + С, — счетчик символов, то есть количество повторений сжатого символа, Рнс. 20.1. формат сжатия при групповом кодировании В табл. 20.1 приводится несколько примеров сжатия по этому алгоритму, Таблица 20.1. Примеры сжатия при групповом кодировании Кодированная строка данных Исходная строка данных 3*** **55.72 ЗЗ.*655.72 $,-9 ВипвЗ,ЬЗВинег ВипвЬЬЬЬЬЬЬЬЬВинвг Как и в методе подавления нулей, передатчик ищет последовательности повторяющихся символов.
В данном случае он заменяет их трехсимвольным кодом, Код состоит из специального индикатора сжатия, за которым следуют сам повторяющийся символ и число епт повторений. Таким образом, данный метод позволяет сократить место, занимаемое лктбой последовательностью из четырех и более одинаковых символов. Эффективность метода группового кодирования зависит от того, насколько часто в исходных данных встречаются последовательности повторяющихся символов, и от средней длины таких серий. Стандартной мерой эффективности сжатия является коэффициент сжатия, нредставляюший собой опюшение длины несжатых данных к длине сжатых данных (включая символы кодирования). В табл. 20.2, взятой нз 1113], показаны коэффициенты сжатия при использовании метода группового кодирования с различными входными последовательностями из 1000 символов.
Здесь представлены результаты сжатия, для количества серий с повторами в исходных данных, варьируюшегося от 10 до 50, и для длин серий, варьирующихся от 4 до 10. Для этих вариакгов исходных данных метод группового кодирования показал коэффициент сжатия от 1,01 до 1,538 в зависимости от характеристик входного текста.
Это показывает, что любая схема сжатия будет обладать переменной производительностью, зависящей от исходных данных. Однако в большинстве случаев в тексте содержится достаточтюе количе- ство повторяюш оряюшихся символов, чтобы применение даже такого простого метода, как групповое кодирование, было опранцано. Таблица 20.2. ЭФфективность метода группового кодирования (по 11131) Средняядлнна повторяющихся символов Коэффициент сжатия Числа серий псвтсрягсщнхся символов 10 9 10 9 1О 4 5 6 7 8 9 10 5 1,176 1,250 1,ЗЗЗ 1,429 50 9 1,538 10 50 10 10 10 1О 10 10 10 20 20 20 20 20 20 20 30 30 30 30 30 30 30 40 40 40 40 40 40 50 50 1.010 1,020 1,031 1,042 1,053 1,064 1,075 1,020 1,042 1,0Б4 1,087 1,111 1, 136 1,163 1,031 1,064 1,099 1,136 1,17Б 1,220 1,266 1,042 1,087 1,136 1,190 1,250 1,316 1,384 1,053 1,111 634 Глава 20.
Сжатие без потерь 20.2. Факсимильное сжатие 635 0000000000 0000000000 0001111000 0001001000 0001111000 0000001000 0000001000 0001111000 0000000000 0000000000 Длина равна 100 бит Двоичный код 23ЧЧ 4В 6ЧЧ 1В 2ЧЧ 18 6УЧ 49 9ЧЧ 18 9ЧЧ 19 6УЧ4823ЧЧ или 234612164916423 Длина равна 16 символов, или 12й бит Проотов групповое кодирование Иэображение Рис. 20.2. Пример группового кодирования Групповое кодирование было одним из первых методов сжатия факсимильных сообщений, но теперь оно более не используется для этой цели.
Однако этот метод следует изучить, так как он применяется в более сложных методах сжатия изображений. При использовании метода группового кодирования для изображений вместо отсканированной и оцифрованной линии передаются длины серии белых и черных элементов изображения. На рис. 20.2 показан пример применения метода группового кодирования к простому изображению размером 10 х 10 точек, Это может быть факсимильное изображение или отсканированное растровое комш,- ютерное изображение. Изображение формата 10 х 10 легко преобразуется в 100-битовый код.
В данном примере каждый пиксел представляется одним битом, обозначающим белый или черный цвет. Код длин серий состоит из длин чередующихся черных и белых последовательностей. Поскольку при таком кодировании изображения черный и белый цвета всегда чередуются, нет необходимости в использовании специального символа, указывающего цвет серии. Таким образом, кодированный поток данных представляет собой строку чисел, обозначающих длины чередующихся серий черных и белых точек. Обратите внимание на то, что в данном простом примере кодированные данные занимают больше места, чем исходные.
Однако в случае применения данного метода к типичной странице текста этот метод будет сжимать данные. Тем не менее, это далеко не самый эффективный способ сжатия изображений. 20.2. Факсимильное сжатие Методы сжатия данных очень важны для широкого применения цифровых факсимильных аппаратов. Для примера рассмотрим типичную страницу, отсканированную с разрешением в 200 пелов' (белых или черных точек) на дюйм (что является приемлемой, но не высокой степенью разрешения). В результате такая страница содержит 3 740 000 бит (8,5 дюймов х 11 дюймов х 40 000 пелов на квадратный дюйм). При базовой скор!готя службы 1Я))ч) в 64 Кбит/с передача такой страницы займет около одной минуты, Обычно пользователи ожидают от систем работы со скоростью, близкой к скорости копирования, то есть несколько секунд на страницу, Для удовлетворения данного требования, если не прибегать к увеличению скорости передачи данных в линии, необходимо использовать метод сжатия данных.
Сектор ГП)-Т стандартизировал два метода сжатия данных без потерь для факсимильной связи: модифицированный код Хаффмана и модифицированный код КЕАГ) (Ке1а(!че Е1ешеп( АсЫгечч Г)ез!йпа(е — относительное назначение адресов элементов). Модифицированный код Хаффмана используется по умолчанию в факсимильной аппаратуре группы Зг, в которой модифицированный код КЕАГ) может применяться факультативно. В аппаратуре группы 4э применяется модифицированный код КЕАР. Кратко эти два стандарта (группы 3 и 4) характеризуются следующим образам: + Группа 3. Первый цифровой факсимильный стандарт.
Эта система обеспечивает только кодирование черных и белых значений с плотностью сканирования в 200 точек на дюйм по горизонтали и от 100 до 200 по вертикали. В аппаратуре группы 3 используются цифровая схема кодирования, а также средства уменьшения избьггочной информации в сигнале документа перед модуляцней. Предполагается, что передача сигнала осуществляется через модем по аналоговой телефонной линии. Передача данных ускоряется в три и более раз цо сравнению с группой 2.
+ Группа 4. Также представляет собой черно-белый цифровой факсимильный стандарт. Эта группа предназначена для использования в цифровых сетях со скоростями до 64 Кбит/с при условии безошибочного приема. Стандартизированы разрешения от 200 до 400 точек на дюйм. Как и в группе 3, для снижения количества передаваемых битов применяются методы сжатия. В аппаратуре группы 4 время передачи одной страницы сокращено до нескольких секунд по сравнению с несколькими минутами в предыдущих стандартах. ' дел — элемент наображенги (р!ггггге е!ещепг, ре!), представляет собой минимальный дискретный эле. иенс отсканированной строки факсимильной системы, содержащий только черно-белуа ф Р -бе. > ннфопмапию (беэ уровней серого). 1!икпелои (р!ле!) наэывыог элемент иэображения, содержащий более детальную информацию об уровне яркосч и.
' 8гапгуап(итюп/аг Сгоир у Гасит!!е Арра гагмг/ег 0осиглепг Тгапптм!еп. йесопппепйацоп Т.4, 1988. ' ращ!тйе Саг(!ай угйетег апг! Соитий Сопли! Гипсгюю/е> Сгаир 4 Аррагагги/т Оогиттп Рлгпэт!агюп. йесопппепйабоо Т.б, 1988. 636 Глава 20. Сжатие беэ потерь 20.2. Факсимильное сжатие 637 таблице 20 3. Модифицированные коды Хаффмана Черная серия Бепаясерия Длинасерии аые слова остатка аредикнееннеХ Модифицированный код Хаффмана В типичном документе черные и белые области имеют тенденцию к объединению Если рассматривать документ как последователыккть линий и обратить внимание на расположение участков белого и черного в липин, можно обнаружить длин ные серии белых и черных точек.
Благодаря этому свойству можно предположить, что сжатие на основе метода группового кодирования даст хороший результат Состоящие из двух значений входные данные преобразуются в длины серий, которые затем кодируются для передачи. Кроме того, поскольку в общем случае длиц. пые серии черных или белых точек менее вероятны, чем короткие, можно воспользоваться преимуществом кодирования последовательностей переменной длины Для кодирования факсимильных документов может применяться код Хаффмана, описанный в главе 19. Этот метод можно применить к изображению построчно, кодируя последовательности черных и белых точек. Например, предположим, что при сканировании отдельной строки получается следующая последовательность черных и белых точек: ЪЪ'7, В7, ЪЪе4, В8, ЪЪ'4, В7, ЪЪ'10 (здесь ЪЪ' означает белый, а  — черный).
Если рассматривать каждый из этих элементов как символ алфавита источника, тогда для кодирования этих данных может быть использован метод кодирования Хаффмана. Однако поскольку стандарт 1ТН-Т требует по меньшей мере 1728 точек на линию, количество различных кодов, а следовательно, н средняя длина кода будет очень больпюй. Альтернативой является модифицированный метод кодирования Хаффмана. В этом методе длина серии Л! рассматривается как сумма двух слагаемых: У = 64т + п; т = О, 1, 2, ..., 27; п = О, 1, 2, ..., 63. То есть длина каждой серии черных нли белых точек считается величиной, кратной 64 с остатком. Теперь каждая длина серии может быть представлена двумя значениями, одним для т и другим для п, и эти значения могут кодироваться при помо!ци метода Хаффмана.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
