|
Читайте также: |
Конечные дискретные источники характеризуются множеством различных символов, Х(п), где п= 1, 2,..., N — алфавит источника, а п — индекс данных. Полное описание требует вероятности каждого символа и совместных вероятностей символов, выбранных по два, три и т.д. Символы могут представлять двухуровневый (двоичный) источник, такой как черно-белые уровни факсимильного изображения, или многосимвольный источник, такой как 40 общих знаков санскрита. Еще одним общим многосимвольным алфавитом является клавиатура компьютерного терминала. Эти недвоичные символы отображаются посредством словаря, называемого знаковым кодом, в описание с помощью двоичного алфавита. (На рис. 2.2 представлен код ASCII, а на рис. 2.3 — код EBCDIC.) Стандартные знаковые коды имеют фиксированную длину, такую как 5-7 бит. Длина обычно выбирается так, чтобы существовало достаточно двоичных знаков для того, чтобы присвоить единственную двоичную последовательность каждому вход
ному знаку алфавита. Это присвоение может включать большие и маленькие буквы алфавита, цифры, знаки пунктуации, специальные знаки и знаки управления, такие как знак забоя, возврата и т.д. Коды фиксированной длины обладают следующим свойством: знаковые границы отделены фиксированным числом бит. Это допускает превращение последовательного потока данных в параллельный простым счетом бит.
Двухкодовые стандарты могут определять один и тот же символ разными способами. Например, (7-битовый) код ASCII имеет достаточно бит, чтобы присвоить различные двоичные последовательности большой и маленькой версиям каждой буквы. С другой стороны, (5-битовый) код Бодо, который обладает только 32 двоичными последовательностями, не может сделать то же самое. Для подсчета полного множества знаков код Бодо определяет два контрольных знака, называемых переключением на печатание букв (letter shift — LS) и переключением на печатание цифр (figure shift — FS), которые должны использоваться как префиксы. При использовании эти контрольные знаки переопределяют отображение символа в двоичную форму. Это напоминает клавишу переключения регистра (shift key) на печатающем устройстве; эта клавиша полностью переопределяет новое множество символов на клавиатуре. Клавиатуры некоторых калькуляторов также имеют две клавиши переключения регистров, так что каждое нажатие клавиши имеет три возможных значения. Кроме того, некоторые команды текстового процессора используют двойные и тройные командные функции. В некотором смысле эти двух- и трехсловные команды представляют собой кодовое присвоение переменной длины. Эти более длинные кодовые слова присваиваются знакам (или командам), которые не встречаются так часто, как присвоенные отдельным кодовым словам. В обмен на использование соответствующих случаю более длинных слов получаем более эффективное запоминание (меньшая клавиатура) или более эффективную передачу источника.
Коды сжатия данных часто имеют переменную длину. Интуитивно ясно, что длина двоичной последовательности, присвоенной каждому символу алфавита, должна обратно зависеть от вероятности этого символа. Из всего сказанного очевидно, что если символ появляется с высокой вероятностью, он содержит мало информации и ему не должен выделяться значительный ресурс системы. Аналогично не будет казаться неразумным, что когда все символы одинаково вероятны, код должен иметь фиксированную длину. Возможно, наиболее известным кодом переменной длины является код (или азбука) Морзе (Morse code). Самуэль Морзе, чтобы определить относительную частоту букв в нормальном тексте, вычислил количество букв в шрифтовой секции печатающего устройства. Кодовое присвоение переменной длины отражает эту относительную частоту.
Если имеется существенное различие в вероятностях символов, может быть получено значительное сжатие данных. Чтобы достичь этого сжатия, необходимо достаточно большое число символов. Иногда, чтобы иметь достаточно большое множество символов, образуется новое множество символов, определенное из исходного множества и называемое кодом расширения. Эта процедура уже рассматривалась в примере 13.3, а общая технология будет изучена в следующем разделе.
13.7.1. Свойства кодов
Ранее обращалось внимание на свойства, которым должен удовлетворять полезный код. Некоторые из этих свойств являются очевидными, а некоторые — нет. Желаемые свойства стоят того, чтобы их перечислить и продемонстрировать. Рассмотрим следующий трехсимвольный алфавит со следующими вероятностными соответствиями.
а 0,73 Ь 0,25 с 0,02
Входному алфавиту сопутствуют следующие шесть двоичных кодовых соответствий, где крайний правый бит является наиболее ранним.
Символ Код 1 Код 2 Код 3 Код 4 Код 5 Код 6 а 00 00 б 1 1 i b 00 01 1 10 00 01 с_ И 10 11 100 01 11
Изучите предлагаемые соответствия и попытайтесь определить, какие коды являются практичными.
Свойство единственности декодирования. Единственным образом декодируемые коды позволяют обратить отображение в исходный символьный алфавит. Очевидно, код 1 в предыдущем примере не является единственным образом декодируемым, так как символам а и b соответствует одна и та же двоичная последовательность. Таким образом, первым требованием полезности кода является то, чтобы каждому символу соответствовала уникальная двоичная последовательность. При этих условиях все другие коды оказываются удовлетворительными до тех пор, пока мы внимательно не изучим коды 3 и 6. Эти коды действительно имеют уникальную двоичную последовательность, соответствующую каждому символу. Проблема возникает при попытке закодировать последовательность символов. Например, попытайтесь декодировать двоичное множество 10111 при коде 3. Это Ь, а, Ь, Ь, Ь; Ь, а, Ь, с или Ь, а, с, Ы Попытка декодировать ту же последовательность в коде 6 вызывает аналогичные сложности. Эти коды не являются единственным образом декодируемыми, даже если отдельные знаки имеют единственное кодовое соответствие.
Отсутствие префикса. Достаточным (но не необходимым) условием того, что код единственным образом декодируем, является то, что никакое кодовое слово не является префиксом любого другого кодового слова. Коды, которые удовлетворяют этому условию, называются кодами, свободными от префикса. Отметим, что код 4 не является свободным от префикса, но он единственным образом декодируем. Свободные от префикса коды также обладают таким свойством — они мгновенно декодируемы. Код 4 имеет свойство, которое может быть нежелательным. Он не является мгновенно декодируемым. Мгновенно декодируемый код — это такой код, для которого граница настоящего кодового слова может быть определена концом настоящего кодового слова, а не началом следующего кодового слова. Например, при передаче символа b с помощью двоичной последовательности 10 в коде 4, получатель не может определить, является ли это целым кодовым словом для символа b или частью кодового слова для символа с. В противоположность этому, коды 2 и 5 являются свободными от префикса.
13.7.1.1. Длина кода и энтропия источника
В начале главы были описаны формальные концепции информационного содержания и энтропии источника. Самоинформация символа Хп в битах была определена следующим образом: I(Xn) = log2[l//,(X„)]. С точки зрения того, что информация разрешает неопределенность, было осознано, что информационное содержание символа стремится к нулю, когда вероятность этого символа стремится к единице. Кроме того, была определена энтропия конечного дискретного источника как средняя информация этого источника. Поскольку информация разрешает неопределенность, энтропия является средним количеством неопределенности, разрешенной с использованием алфавита. Она также представляет собой среднее число бит на символ, которое требуется для описания источника. В этом смысле это также нижняя граница, которая может быть достигнута с помощью некоторых кодов сжатия данных, имеющих переменную длину. Действительный код может не достигать граничной энтропии входного алфавита, что объясняется множеством причин. Это включает неопределенность в вероятностном соответствии и ограничения буферизации. Средняя длина в битах, достигнутая данным кодом, обозначается как п. Эта средняя длина вычисляется как сумма длин двоичных кодов, взвешенных вероятностью этих кодовых символов Р(Х,).
"=Х"'Р(Х,)
I
Когда говорится о поведении кода переменной длины, массу информации можно получить из знания среднего числа бит. В кодовом присвоении переменной длины некоторые символы будут иметь длины кодов, превосходящие среднюю длину, в то время как некоторые будут иметь длину кода, меньшую средней. Может случиться, что на кодер доставлена длинная последовательность символов с длинными кодовыми словами. Кратковременная скорость передачи битов, требуемая для передачи этих символов, будет превышать среднюю скорость передачи битов кода. Если канал ожидает данные со средней скоростью передачи, локальный избыток информации должен заноситься в буфер памяти. К тому же на кодер могут быть доставлены длинные модели символов с короткими кодовыми словами. Кратковременная скорость передачи битов, требуемая для передачи этих символов, станет меньше средней скорости кода. В этом случае канал будет ожидать биты, которых не должно быть. По этой причине для сглаживания локальных статистических вариаций, связанных с входным алфавитом, требуется буферизация данных.
Последнее предостережение состоит в том, что коды переменной длины создаются для работы со специальным множеством символов и вероятностей. Если данные, поступившие на кодер, имеют существенно отличающийся перечень вероятностей, буферы кодера могут быть не в состоянии поддержать несоответствие и будет происходить недогрузка или перегрузка буфера.
13.7.2. Код Хаффмана
Код Хаффмана (Huffman code) [20] — это свободный от префикса код, который может давать самую короткую среднюю длину кода п для данного входного алфавита. Самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника, и тогда эта невозможность выполнения обещанного сжатия данных будет связана с алфавитом, а не с методом кодирования. Часть алфавита может быть модифицирована для получения кода расширения, и тот же метод повторно применяется для достижения лучшего сжатия. Эффективность сжатия определяется коэффициентом сжатия. Эта мера равна отношению среднего числа бит на выборку до сжатия к среднему числу бит на выборку после сжатия.
Процедура кодирования Хаффмана может применяться для преобразования между любыми двумя алфавитами. Ниже будет продемонстрировано применение процедуры при произвольном входном алфавите и двоичном выходном алфавите.
Код Хаффмана генерируется как часть процесса образования дерева. Процесс начинается с перечисления входных символов алфавита наряду с их вероятностями (или относительными частотами) в порядке убывания частоты появления. Эти позиции таблицы соответствуют концам ветвей дерева, как изображено на рис. 13.34. Каждой ветви присваивается ее весовой коэффициент, равный вероятности этой ветви. Теперь процесс образует дерево, поддерживающее эти ветви. Два входа с самой низкой относительной частотой объединяются (на вершине ветви), чтобы образовать новую ветвь с их смешанной вероятностью. После каждого объединения новая ветвь и оставшиеся ветви переупорядочиваются (если необходимо), чтобы убедиться, что сокращенная таблица сохраняет убывающую вероятность появления. Это переупорядочение называется методом пузырька [21]. Во время переупорядочения после каждого объединения поднимается (“всплывает”) новая ветвь в таблице до тех пор, пока она не сможет больше увеличиваться. Таким образом, если образуется ветвь с весовым коэффициентом 0,2 и во время процесса находятся две другие ветви уже с весовым коэффициентом
0, 2, новая ветвь поднимается до вершины группы с весовым коэффициентом 0,2, а не просто присоединяется к ней. Процесс “всплытия” пузырьков к вершине группы дает код с уменьшенной дисперсией длины кода, в противном случае — код с такой же средней длиной, как та, которая получена посредством простого присоединения к группе. Эта сниженная дисперсия длины кода уменьшает шанс переполнения буфера.1
| в 011 f 010 Рис. 13.34. Дерево кодирования Хаффмана дм шестизначного множества |
В качестве примера этой части процесса кодирования применим процедуру Хаффмана к входному алфавиту, изображенному на рис. 13.34. Протабулированный алфавит и связанные с ним вероятности изображены на рисунке. После формирования дерева, чтобы различать две ветви, каждая вершина ветви снабжается двоичным решением “1/0”. Присвоение является произвольным, но для определенности на каждой вершине будем обозначать ветвь, идущую вверх как “1”, и ветвь, идущую вниз как “О”. После обозначения вершин ветвей проследим траектории дерева от основания (крайнее правое положение) до каждой выходной ветви (крайнее левое положение). Траектория — это двоичная последовательность для достижения этой ветви. В следующей таблице для каждого конца ветви указана последовательность, соответствующая каждой траектории, где i - 1,..., 6.
X,_____________ Р(Х,)___________ Код________________ п,____________ п,Р(Х,)
|
Находим, что средняя длина кода п для этого алфавита равна 2,4 бит на знак. Это не означает, что необходимо найти способ передачи нецелого числа бит. Это означает, что для передачи 100 входных символов через канал связи в среднем должно пройти 240 бит. Для сравнения, код фиксированной длины, требуемый для охвата шестизначного входного алфавита, должен иметь длину 3 бит и энтропию входного алфавита (используем формулу (13.32)), равную 2,32 бит. Таким образом, этот код дает коэффициент сжатия 1,25 (3,0/2,4) и достигает 96,7% (2,32/2,40) возможного коэффициента сжатия. В качестве еще одного примера рассмотрим случай, для которого можно продемонстрировать использование кода расширения. Изучим трехзначный алфавит, представленный в разделе 13.6.1.
X, Р(Х.)
А 0,73
b 0,25
С 0,02
Дерево кода Хаффмана для этого алфавита изображено на рис. 13.35, а его элементы протабулированы ниже.
0,73 0,73 а о----- — — 1
|
Здесь / = 1, 2, 3. Средняя длина кода в приведенном примере равна 1,31 бит; она будет равна 2 бит для кода Хаффмана фиксированной длины. Коэффициент сжатия для этого кода равен 1,53. И снова, используя равенство (13.32), получим, что энтропия для алфавита равна 0,9443 бит, так что эффективность кода (0,944/1,31 = 72%) значительно меньше, чем для предыдущего примера.
Чтобы улучшить эффективность кодирования или достичь большего сжатия, следует переопределить алфавит источника. Больший алфавит источника увеличивает разнообразие, что является одним из требований при сокращении средней длины кода и увеличении числа ветвей дерева для присвоения кода переменной длины. Это делается посредством выбора знаков (по два) из алфавита источника, которые становятся новыми знаками в расширенном алфавите. Если предположить, что символы независимы, вероятность каждого нового элемента является произведением отдельных вероятностей. Алфавит расширения имеет следующий вид.
| X, | Р(Х.) | Код | п, | п,Р(Х,) |
| аа | 0,5329 | 0,5329 | ||
| ab | 0,1825 | 0,3650 | ||
| Ьа | 0,1825 | 0,5475 | ||
| ЪЬ | 0,0625 | 0,2500 | ||
| ас | 0,0146 | 0,0730 | ||
| са | 0,0146 | 0,0876 | ||
| Ьс | 0,0050 | 0,0350 | ||
| cb | 0,0050 | 0,0400 | ||
| сс | 0,0002 | 0,0016 п = 1,9326 бит/два символа = 0,9663 бит/символ |
Здесь i = 1,..., 9, а кодовая последовательность для каждого X, была найдена с использованием выше приведенной процедуры Хаффмана. Коэффициент сжатия для этого кода расширения равен 2,076, а эффективность кодирования — 97,7%. Коды расширения предлагают очень мощную технологию включения эффектов множеств символов, которые не являются независимыми. Например, в английском алфавите соседние буквы являются высоко коррелированными. Очень часто встречаются следующие пары букв.
th re in
sh he е_
de ed s_
ng at r_
te es d_
Здесь подчеркивание представляет пробел. Наиболее общими английскими наборами трех букв являются следующие.
the and for
ing ion ess
Таким образом, вместо того чтобы производить кодирование Хаффмана отдельных букв, более эффективно расширить алфавит, включив все 1-кортежи плюс распространенные 2- и 3-кортежи, а затем произвести кодирование с помощью кода расширения.
13.7.3. Групповые коды
Во многих приложениях последовательность символов, которую необходимо передать или запомнить, характеризует последовательное кодирование определенных символов. Иногда, вместо того чтобы кодировать каждый символ последовательности, есть смысл описать группу с помощью подстановочного кода. В качестве примера рассмотрим случай, когда последовательности пробелов (наиболее употребимый символ в
тексте) кодируются во многих протоколах связи с помощью символа управления, за которым следует счетчик символов. Протокол IBM 3780 BISYNC имеет опцию замены последовательности пробелов с помощью знака “IGS” (если имеем дело с EBCDIC) или “GS” (если имеем дело с ASCII), за которым следует счетчик от 2 до 63. Более длинные последовательности делятся на серии по 63 знака.
Групповое подстановочное кодирование может быть применено к исходному алфавиту символов или двоичному представлению этого алфавита. В частности, групповое кодирование является удачным для двоичных алфавитов, полученных от специфических источников. Наиболее важным коммерческим примером является факсимильное кодирование, используемое для передачи документов по мгновенной электронной почте [22].
13.7.3.1. Кодирование Хаффмана для факсимильной передачи
Факсимильная передача — это процесс передачи двухмерного образа как последовательности последовательных строчных разверток. В действительности наиболее распространенными образами являются документы, содержащие текст и цифры. Положение строчной развертки и положение вдоль развертки квантуются в пространственные расположения, которые определяют двухмерную координатную сетку элементов картинки, называемых пикселями. Ширина стандартного документа МККТТ определяется равной 8,27 дюймов (20,7 см), а длина — 11,7 дюймов (29,2 см), почти 8,5 дюймов на 11,0 дюймов. Пространственное квантование для нормального разрешения составляет 1728 пикселей/строку и 1188 строк/документ. Стандарт также определяет квантование с высоким разрешением с теми же 1728 пикселями/строку, но с 2376 строками/документ. Общее число отдельных пикселей для факсимильной передачи с нормальным разрешением составляет 2 052 864, и оно удваивается для высокого разрешения. Для сравнения, число пикселей в стандарте NTSC (National Television Standards Committee — Национальный комитет по телевизионным стандартам) коммерческого телевидения составляет 480 х 460, или 307 200. Таким образом, факсимильное изображение имеет разрешение в 6,7 или 13,4 раза больше разрешения стандартного телевизионного образа.
Относительная яркость или затемненность развернутого образа в каждом положении на строке развертки квантуется в два уровня: Ч (черный) и Б (белый). Таким образом, сигнал, наблюдаемый на протяжении линии развертки, — это двухуровневая модель, представляющая элементы Ч и Б. Легко видеть, что горизонтальная развертка данной страницы будет представлять последовательность, состоящую из длинных групп уровней Ч и Б. Стандарт МККТТ схемы группового кодирования для сжатия отрезков Ч и Б уровней базируется на модифицированном коде Хаффмана переменной длины, который приведен в табл. 13.1. Определяются два типа шаблонов, группы Б и Ч. Каждый отрезок описывается кодовыми словами деления. Первое деление, названное созданное кодовое слово, определяет группы с длинами, кратными 64. Второе деление, именуемое оконечное кодовое слово, определяет длину оставшейся группы. Каждая серия из знаков Ч (или Б), длиной от 0 до 63, обозначает единственное кодовое слово Хаффмана, как и каждая группа длины 64 х К, где К= 1, 2,..., 27. Также кодом определен уникальный символ конца строки (end of line — EOL), который указывает, что дальше не следуют черные пиксели. Следовательно, должна начаться следующая строка, что подобно возврату каретки пишущей машинки [23].
Таблица 13.1. Модифицированный код Хаффмана для стандарта факсимильной связи МККТТ
|
Оконечные кодовые слова
|
| Длина группы | Белые | Черные | Длина группы | Белые | Черные |
| Оконечные кодовые слова | |||||
| Пример 13.8. Код группового кодирования Используйте модифицированный код Хаффмана для сжатия строки |
200 Б, 10 Ч, 10 Б, 84 Ч, 1424 Б,
состоящей из 1728 пиксельных элементов.
Решение
Используя табл. 13.1, определим, каким должно быть кодирование для этой модели (для
удобства чтения введены пробелы).
010111 10011 0000100 00111 0000001111 00001101000 000000000001
192Б 8Б 104 10Б 644 204 EOL
Итак, требуется всего 56 бит, чтобы послать эту строку, содержащую последовательность
1188 бит.
13.7.3.2. Коды Лемпеля-Зива (ZIP)
Основной сложностью при использовании кода Хаффмана является то, что вероятности символов должны быть известны или оценены и как кодер, так и декодер должны знать дерево кодирования. Если дерево строится из необычного для кодера алфавита, канал, связывающий кодер и декодер, должен также отправлять кодирующее дерево как заголовок сжатого файла. Эти служебные издержки уменьшат эффективность сжатия, реализованную с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива (Lempel-Ziv) и его многочисленные разновидности используют текст сам по себе для итеративного построения синтаксически выделенной последовательности кодовых слов переменной длины, которые образуют кодовый словарь.
Код предполагает, что существующий словарь содержит уже закодированные сегменты последовательности символов алфавита. Данные кодируются с помощью просмотра существующего словаря для согласования со следующим коротким сегментом кодируемой последовательности. Если согласование найдено, код следует такой фило-
Дата добавления: 2015-10-28; просмотров: 54 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Основы теории принятая статистических решений 1051 73 страница | | | Основы теории принятая статистических решений 1051 75 страница |