Скляр Б. Цифровая связь (2003) (1151859), страница 204
Текст из файла (страница 204)
Эти позиции таблицы соответствуют концам ветвей дерева, как изображено на рис. 13.34. Каждой ветви присваивается ее весовой коэффициент, равный вероятности этой ветви. Теперь процесс образует дерево, поддерживающее зти ветви. Два входа с самой низкой относительной частотой объединяются (на вершине ветви), чтобы образовать новую ветвь с их смешанной вероятностью. После каждого объединения новая ветвь и оставшиеся ветви переупорядочиваются (если необходимо), чтобы убедиться, что сокращенная таблица сохраняет убывающую вероятность появления. Это переупорядочение называется методом пузырька (21).
Во время переупорядочения после каждого объединения поднимается ("всплывает") новая ветвь в таблице до тех пор, пока она не сможет больше увеличиваться. Таким образом, если образуется ветвь с весовым коэффициентом 0,2 и во время процесса находятся две другие ветви уже с весовым коэффициентом 0,2, новая ветвь поднимается до вершины группы с весовым коэффициентом 0,2, а не просто присоединяется к ней.
Процесс "всплытия*' пузырьков к вершине группы дает код с уменьшенной дисперсией длины кода, в противном случае— код с такой же средней длиной, как та, которая получена посредством простого присоединения к группе. Эта сниженная дисперсия длины кода уменьшает шанс переполнения буфера. ' О 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п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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
