Скляр Б. Цифровая связь (2003) (1151859), страница 205
Текст из файла (страница 205)
Модифицированный код Хаффмана для стандарта факсимильной связи МККТТ Длина группы Белые Длина группы Черные Черные Созданные кодовые слова Длина группы Белые Черные Длина группы Белые Черные Оконечные кодовые слова 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.
Коды Лемпепя-Зива (к(Р) Основной сложностью при использовании кода Хаффмана является то, что вероятности символов должны быль известны или оценены и как кодер, так и декодер должны знать дерево кодирования, Если дерево строится из необычного для кодера алфавита, канал, связывающий кодер и декодер, должен также отправлягь кодирующее дерево как запновок сжатого файла. Эти служебные издержки уменьшат эффективность сжатия, реализованную с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива (Ьещре1-е,1т) и его многочисленные разновидности используют текст сам по себе для итеративного построения синтаксически выделенной последовательности кодовых слов переменной длины, которые образуют кодовый словарь.
Код предполагает, что существующий словарь содержит уже закодированные сегменты последовательности символов алфавита. Данные кодируются с помощью просмотра существующего словаря дня согласования со следующим коротким сегментом кодируемой последовательности. Если согласование найдено, код следует такой фило- !9 20 21 22 23 24 25 26 27 28 29 30 31 0001100 0001000 00101!! 0000011 0000100 0101000 010101! 0010011 0100100 0011000 00000010 00000011 00011010 00001!00!1! 00001101000 00001101100 00000!!01!1 00000101000 000000!0111 00000011000 000011001010 00001! 001011 ООООИООИОО 0000!100110! 00000!101000 00000110!001 51 52 53 54 55 56 57 58 59 60 6! 62 63 01010100 01010101 00100100 00100101 О!01!000 0101100! 010!10!О 01011011 01001010 О!001011 00110010 00110011 00110100 00000! О! 0011 000001000100 000000!!О!!! 000000!!1000 000000100!!! 000000!О!000 00000!О!!000 00000101!001 00000010101! 00000010!100 00000101!О!О 00000!100!10 000001100111 софии: поскольку получатель уже имеет этот сегмент кода в своей памяти, нет необходимости пересылать его, требуется только определить адрес, чтобы найти сегмент.
Код ссылается на расположение последовательности сегмента и затем дополняет следующий символ в последовательности, чтобы образовать новую позицию в словаре кода. Код начинается с пустого словаря, так что первые элементы являются позициями, которые не ссылаются на более ранние. В одной форме словаря рекуррентно формируется выполняемая последовательность адресов и сегмент символов алфавита, содержащийся в ней. Закодированные данные состоят из пакета <адрес словаря, следующий знак данных>, а каждый новый входной элемент словаря образован как пакет, содержащий адрес того словаря, за которым следует следующий символ. Рассмотрим пример такой технологии кодирования.
Закодируйте последовательность символов [а Ь а а Ь а Ь Ь Ь Ь Ь Ь Ь а Ь Ь Ь Ь а[ Закодированные <О,а>, <О,Ь>, «1,а>, <2,а>, <2,Ь>, <5,Ь>, <5,а>. <6,Ь>, <4,-> пакеты: Адрес 1 2 3 4 5 6 7 8 Содержимое: а Ь аа Ьа ЬЬ ЬЬЬ ЬЬа ЬЬЬЬ Закодируйте последовательность символов [а Ь а а Ь а Ь Ь Ь Ь Ь Ь Ь а Ь Ь Ь Ь Ь а1 Закодированные <О,О,а>, <О,О,Ь>, <2,1,а>, <3,2,Ь>, <1,7,а>, <6,5,а> пакеты: Содержимое: Текущий текст: а Ь аа ЬаЬ ЬЬЬЬЬЬЬа ЬЬЬЬЬа а аЬ аЬаа аЬааЬаЬ аЬааЬаЬЬЬЬЬЬЬЬа вся последовательность Начальный пакет <О,а> показывает нулевой адрес, потому что в словаре еще нет ни одной позиции. В этом пакете знак "а" является первым в последовательности данных, и он приписан к адресу 1.
Следующий пакет <О,Ь> содержит второй знак данных Ь, который еще не был в словаре (следовательно, адресное значение есть 0); Ь приписывается адресу 2. Пакет <1,а> представляет кодирование следующих двух знаков "ы" с помощью вызова адреса 1 лля первого и присоединения к этому адресу следующего знака "а".
Пара знаков "аа" приписывается адресу 3. Пакет <2,а> представляет кодирование следующих двух знаков данных "Ьа" с помощью вызова адреса 2 лля знака "Ь" и присоединения к этому адресу следующего знака "а". Пара знаков данных "Ьа" приписывается адресу 4 и т.д. Отметим, как завершается групповое кодирование. Восьмой пакет составлен из адреса 6, содержащего три знака "Ь", за которыми следует другой знак "Ь". В этом примере закодированные данные могут быть описаны с помощью трехбитового адреса с последующим битом О или 1 для определения присоединенного знака.
В закодированной последовательности существует последовательность из 9 символов для общего содержимого в 36 бит для кодирования данных, содержащих 20 знаков. Как во многих схемах сжатия, эффективность кодирования не достигается для коротких последовательностей, как в этом примере, и имеется только для длинных последовательностей. В другой форме алгоритма Лемпеля-Зива закодированные данные представлены как три словесных пакета вида <число знаков сзади, длина, следующий знак>. Здесь концепция адреса не используется.
Наоборот, имеются ссылки на предшествующие последовательности данных, а также допускаются рекуррентные ссылки на параметр длины. Это показано в следующем примере, представленном как позиция <1,7,а>. Здесь также не видно эффективности кодирования для короткой серии данных. Разновидности кода ограничивают размер обратной ссылки, например 12-битовая для максимума в 4 096 пунктов обратной ссылки.
Это ограничение уменьшает размер памяти, требуемой для словаря, и сокращает вероятность перегрузки памяти. Возможны также модификации кода, ограничивающие длину префикса или фразы, определенной первыми двумя аргументами сназад и1, вперед л2, ххх>, которые должны быль меньше некоторого значения (например, 16) с целью ограничения сложности обратного поиска во время кодирования. Алгоритм Лемпеля-Зива присутствует во многих коммерческих и пробных программах, которые включают сжатие 1.777, Сгх!р, (.с.78, (.Х% и (ЛЧ1Х.
13.В. Примеры кодирования источника 13.8.1. Аудиосжетие Аудиосжатие широко применяется в потребительских и профессиональных цифровых аудиопродуктах, таких как компакт-диски (сотрасг б!зс — СО), цифровая аудиолента (г!!8!га! аид!о гуре — Г1АТ), мини-диск (щ!п1-д!з!г — М())„цифровая компакт-кассета (б!8!га! согпрасг саззегге — 1)СС), универсальный цифровой диск (б!8!га! тегзаг!!е г((зев 1)Ч(3), цифровое аудиовещание (б!8!га! ацб!о Ьгоас1сазйп8 — 1)АВ) и аудиопродукция в формате МР3 от экспертной группы по вопросам движущегося изображения (Мойоп Р!с!иге Ехрепз Огоцр — (МРЕО).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
