Тема 3. Кодирование источника (774420), страница 5
Текст из файла (страница 5)
Процесс "всплытия*' пузырьков к вершине группы дает код с уменьшенной дисперсией длины кода, в противном случае— код с такой же средней длиной, как та, которая получена посредством простого присоединения к группе. Эта сниженная дисперсия длины кода уменьшает шанс переполнения буфера. ' О 1ОО в оы о1о Рис. 13.34. Дерево кодирования Хаффмана дян шестизначноео мноисестеа В качестве примера этой части процесса кодирования применим процедуру Хаффмана к входному алфавиту, изображенному на рис. 13,34. Протабулированный алфавит и связанные с ним вероятности изображены на рисунке. После формирования дерева, чтобы различать две ветви, каждая вершина ветви снабжается двоичным решением "1/О".
Присвоение является произвольным, но для определенности на каждой вершине будем обозначать ветвь, идущую вверх как "1", и ветвь, идущую вниз как "0". После обозначения вершин ветвей проследим траектории дерева от основания (крайнее правое положение) до каждой выходной ветви (крайнее левое положение). Траектория — зто двоичная последовательность для достижения этой ветви.
В следующей таблице для каждого конца ветви указана последовательность, соответствующая каждой траектории, где 1= 1, ..., б. 880 Р(Х,) Код и, л,Р(Х,) Х, с г( Находим, по средняя длина када й для этого алфавита равна 2,4 бит на знак. Это не означает, что необходимо найти способ передачи нецелого числа бит. Это означает, что лля передачи 100 входных символов через канал связи в среднем должно пройти 240 бит. Для сравнения, код фиксированной длины, требуемый дяя охвата шестизначного входного алфавита, должен иметь длину 3 бнг и энтропию входного алфавита (используем формулу (13.32)), равную 2,32 бит.
Таким образом, этот код дает коэффициент сжатия 1,25 (3,0/2,4) и достигает 96,7% (2,3272,40) возможного коэффициента слгатия. В качестве еше одного примера рассмотрим случай, дяя которого можно продемонстрировать использование кода расширения. Изучим трехзначный алфавит, представленный в разделе 13.6.1. Х, Р(Х,) а 0,73 Ь 025 с 0,02 Дерево кода Хаффмана для этого алфавита изображено на рис. 13.35, а его элементы протабулированы ниже. олз о,тз Входная Кодовыо ~авит символы в 1 Ь О1 с 00 Рис, гЗ.г5. Дерево коднрованив Ха(х))мана двв трехгнаннога множества х, Р(Х) Код л, о,Р(Х,) 0,73 1 1 073 0,27 01 2 0,54 0,02 00 2 0,04 й= 1,31 Здесь 1 = 1, 2, 3.
Средняя длина кода в приведенном примере равна 1,31 бит; она будет равна 2 бит дяя кода 7(аффмана фиксированной длины. Коэффициент сжатия для этогО кода равен 1,53. И снова, используя равенство (13.32), получим, что энтропия лля алфавита равна 0,9443 бит, так что эффективность кода (0,944/1,31 = 72%) значительно меньше, чем для предыдущего примера. 0,4 0,2 0,1 0,1 0,1 О,1 11 00 101 100 011 010 0,8 0,4 0,3 0,3 0,3 0.3 н =2,4 Чтобы улучшить эффективность кодирования или достичь большего сжатия„следует переопределить алфавит источника, больший алфавит источника увеличивает разнообразие, что является одним из требований при сокращении средней длины кода и увеличении числа ветвей дерева для присвоения кода переменной длины. Это делается посредством выбора знаков (по два) из алфавита источника„которые становятся новыми знаками в расширенном алфавите.
Если предположить, что символы независимы, вероятность каждого нового элемента является произведением отдельных вероятностей. Алфавит расширения имеет следующий вид. Х, Р(Х,) Код п, и,Р(Х,) аа аЬ Ьа ЬЬ ас са Ьс сЬ сс Здесь 1 = 1, ..., 9, а кодовая последовательность для каждого Х, была найдена с использованием выше приведенной процедуры Хаффмана. Коэффициент сжатия для этого кода расширения равен 2,076, а эффективносп кодирования — 97,7%. Коды расширения предлагают очень мощную технологию включения эффектов множеств символов, которые не являются независимыми. Например, в английском алфавите соседние буквы являются высоко коррелированными.
Очень часто встречаются следующие пары букв. г)з ге (п з)з )зе е Йе еб 3 п8 аг 1е ез Й Здесь подчеркивание представляет пробел. Наиболее общими английскими наборами трех букв являются следующие. )ог езз Спе 1п8 Таким образом, вместо того чтобы производить кодирование Хаффмана отдельных букв, более эффективно расширить алфавит, включив все 1-кортежи плюс распространенные 2- и З-кортежи, а затем произвести кодирование с помощью кода расширения. апг) юп 13.7.3. Групповые коды Во многих приложениях последовательность символов, которую необходимо передать или запомнить, характеризует последовательное кодирование определенных символов, Иногда, вместо того чтобы кодировать каждый символ последовательности, есть смысл описать группу с помощью подстановочного кода.
В качестве примера рассмотрим случай, когда последовательности пробелов (наиболее употребимый символ в 882 0,5329 ! 0,1825 00 0,1825 01! 0,0625 0101 0,0146 01000 0,0146 010011 0,0050 0100100 0,0050 01001011 0,0002 01001010 0,5329 0,3650 0,5475 0,2500 0,0730 0,0876 0,0350 0,0400 0,0016 и = 1,9326 бит/два символа = 0,9663 бит/символ тексте) кодируются во многих протоколах связи с помошью символа управления, за которым следует счетчик символов. Протокол 1ВМ 3780 В!8УХС имеет опцию замены последовательности пробелов с помощью знака "1ОБ" (если имеем дело с ЕВСР1С) или '"Об" (если имеем дело с АБС11), за которым следует счетчик от 2 до 63.
Более длинные последовательности делятся на серии по 63 знака. Групповое подстановочное кодирование может быть применено к исходному алфавиту символов или двоичному представлению этого алфавита. В частности, групповое кодирование является удачным для двоичных алфавитов, полученных от специфических источников. Наиболее важным коммерческим примером является факсимильное кодирование, используемое для передачи документов по мгновенной электронной почте (22]. 13.7.3.1.
Кодирование Хаффмана для факсимильной передачи Факсимильная передача — это процесс передачи двухмерного образа как последовательности последовательных строчных разверток. В действительности наиболее распространенными образами являются документы, содержащие текст и цифры. Положение строчной развертки и положение вдоль развертки квантуются в пространственные расположения, которые определяют двухмерную координатную сетку элементов картинки, называемых пикселями. Ширина стандартного документа МККТТ определяется равной 8,27 дюймов (20,7 см ), а длина — 11,7 дюймов (29,2 см), почти 8,5 дюймов на 11,0 дюймов.
Пространственное квантование для нормального разрешения составляет !728 пикселей/строку и 1188 строк/документ. Стандарт также определяет квантование с высоким разрешением с теми же 1728 пикселями/строку, но с 2376 строками/документ. Обшее число отдельных пикселей для факсимильной передачи с нормальным разрешением составляет 2 052 864„и оно удваивается дпя высокого разрешения. Для сравнения, число пикселей в стандарте ХТЗС (Хабопа1 Те1ет)з)оп Бгапг(апЬ Соппп!цее — Национальный комитет по телевизионным стандартам) коммерческого телевидения составляет 480 х 460, или 307 200. Таким образом, факсимильное изображение имеет разрешение в 6,7 или 13,4 раза больше разрешения стандартного телевизионного образа.
Относительная яркость или затемненность развернутого образа в каждом положении на строке развертки квантуется в два уровня: Ч (черный) и Б (белый). Таким образом, сигнал, наблюдаемый на протяжении линии развертки, — это двухуровневая модель, представляющая элементы Ч и Б. Легко видеть, что горизонтальная развертка данной страницы будет представлять последовательность, состоящую из длинных групп уровней Ч и Б. Стандарт МККТТ схемы группового кодирования для сжатия отрезков Ч и Б уровней базируется на модифицированном коде Хаффмана переменной длины, который приведен в табл.
13.1. Определяются два типа шаблонов, группы Б и Ч. Каждый отрезок описывается кодовыми словами деления. Первое деление, названное созданное кодовое слово, определяет группы с длинами, кратными 64. Второе деление, именуемое оконечное кодовое слово, определяет длину оставшейся группы. Каждая серия из знаков Ч (или Б), длиной от 0 до 63, обозначает единственное кодовое слово Хаффмана, как и каждая группа длины 64 х К, где К = 1, 2, ..., 27. Также кодом определен уникальный символ конца строки (епг( оГ Иле — ЕО1.), который указывает, что дальше не следуют черные пиксели.
Следовательно, должна начаться следующая строка, что подобно возврату каретки пишушей машинки [23). Таблица 13.1. Модифицированный код Хаффмана для стандарта факсимильной связи МККТТ Длина группы Белые Длина группы Черные Черные Созданные кодовые слова Длина группы Белые Черные Длина группы Белые Черные Оконечные кодовые слова 00000!1010!О 000001101011 0000!10)0010 00001!010011 00001!О!0100 0000110!0101 0000!!0101!О 0000! 10 03111 000001101100 000001101101 ОООО!!011010 00001!011011 000001010100 000001010101 0000010!01!О 000001010!1! 000001100100 00000!!00!01 000001010010 64 128 192 256 320 384 448 512 576 640 704 768 832 896 0 1 2 3 4 5 6 7 8 9 10 11 !2 13 14 15 16 17 !8 !101! 10010 010111 011011! 00110!!О 00110!11 О!100!00 01!00101 01!01000 О!100!11 011001100 011001101 011010010 0)1010011 00110101 000!!! 01)1 !000 1011 1100 !110 1111 1001! 10100 001!1 01000 001000 000011 110100 ! 10101 1010!О 10101! 0100111 000000! 111 00001!001000 000011001001 0000010110 П 00000011001! 000000110! 00 00000011010! 0000001101100 000000110110! 000000!001010 0000001001011 0000001001100 000000!ОО!101 000000!!10010 000110111 010 11 10 О!1 0011 0010 00011 000!О! 000100 0000100 000010! 000011! 00000100 00000!11 000011000 0000010111 0000011000 0000001000 960 1024 )088 1152 !216 1280 1344 1408 !472 1536 1600 1664 !728 ЕОЬ 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 011010100 011010101 011010110 О!1010!1! 01!011000 О!101!00! 0110110!О 011011011 010011000 О!001!001 0100! 1010 011000 О!00!!01! 000000000001 000110! 1 00010010 000! 00!! 00010100 0001010! 00010110 000!01!! 0010!000 00101001 00!01010 00101011 00!О!!00 00!0110! 00000100 0000010! 00001010 00001011 010!0010 0101001! 0000001110011 0000001110100 0000001!!О!01 0000001110110 000000!!10!!1 00000010!0010 000000101001! 0000001010!00 00000010!О!01 00000010!!010 000000!О!101! 000000!!00100 000000!10010! 000000000001 Онанчаные табл.
13.1 Длина Белые Черные Длина Белые группы группы Черные Оконечные кодовые слова Пример 13.8. Код ~руппового кодирования Используйте модифицированный код Хаффмаиа для сжатия строки 200 Б, 10 Ч, 10 Б, 84 Ч, 1424 Б, состоящей из 1728 пиксельных элементов. Решение Используя табл. !3.1, определим, каким должно быть кодирование лля этой модели (для удобства чтения введены пробелы). 010111 10011 0000100 0011! 0000001111 00001101000 000000000001 192Б ВБ 10Ч 10Б 64Ч 20Ч ЕОЬ Итак, требуется всего 56 бит, чтобы послать эту строку, содержащую последовательность 1!88 бит. 13.7.3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
