Тема 3. Кодирование источника (774420), страница 6
Текст из файла (страница 6)
Коды Лемпепя-Зива (к(Р) Основной сложностью при использовании кода Хаффмана является то, что вероятности символов должны быль известны или оценены и как кодер, так и декодер должны знать дерево кодирования, Если дерево строится из необычного для кодера алфавита, канал, связывающий кодер и декодер, должен также отправлягь кодирующее дерево как запновок сжатого файла. Эти служебные издержки уменьшат эффективность сжатия, реализованную с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива (Ьещре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,а>. Один из таких методов кодирования, позволяющий получить экономный код, предложили Р. М. Фано и К. Шеннон. Он заключается в следующем. Элементарные сообщения (символы) а;, г' = 1, ..., гп, подлежащие кодированию, записывают в порядке убывания их вероятностей р~а~. Полученную последовательность сообщений разбивают на две группы так, чтобы суммы вероятностей сообщений в каждой группе были по возможности одинаковыми.
Всем сообщениям первой группы приписывают символ О, а сообщениям второй группы — символ 1. Эти двоичные символы используют в качестве первых символов кодовых комбинаций. Затем аналогичным образом каждую группу сообщений делят на две подгруппы. Сообщениям первой подгруппы каждой группы приписывают символ О, а сообщениям второй подгруппы каждой группы — символ 1.
Процесс продолжается до тех пор„пока в каждой подгруппе не останется по одному сообщению. Пример экономного кодирования по методу Шеннона — Фано представлен в табл. 4.1. Таблица 4.1 В рассмотренном примере энтропия Н(А) = 1,875, а среднее число двоичных символов, приходящихся на одно сообщение, л=1,875. Следовательно, полученный код является экономным. Существуют и другие процедуры кодирования, устраняющие избыточность сообщений из-за их неравновероятности [14).
Избыточность источника, обусловленная наличием статистических связей между элементарными сообщениями, устраняется кодированием укрупненных сообщений. При передаче письменного текста зто означает, что необходимо кодировать не отдельные буквы, а слова. В результате такого кодирования остается избыточность, обусловленная наличием статистической связи между словами, которая значительно слабее статистической связи между буквами. 73 Здесь также не видно эффективности кодирования для короткой серии данных. Разновидности кода ограничивают размер обратной ссылки, например 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 от экспертной группы по вопросам движущегося изображения (Мойоп Р!с!иге Ехрепз Огоцр — (МРЕО). К тому же сжатие речи в телефонии, в частности сотовой телефонии, требуемое для экономии полосы частот и сбережения времени жизни батареи, дало начало процессу разработки множества стандартов сжатия речи.
Различные алгоритмы применимы к речевым и потребительским сигналам более широкой полосы частот. Аудио- и речевые схемы сжатия можно для удобства разделить согласно приложениям, что отражает некоторую меру приемлемого качества. Рассмотрим параметры, описывающие это деление [24, 25]. Типичные значения параметров лля трех классов аудиосигналов Диапазон Частота Бит частот дискретизации РСМ/выборку Скорость передачи битов РСМ Телефонная речь Широкополосная речь Широкополосное аудио 64 Кбит/с 224 Кбит/с 300-3 400 Гц 8 кГц 60-7 000 Гц 16 кГц 8 14 768 Кбит/с 10-20 000 Гц 48 кГц 16 Кодирование источника стало основной подсистемой в современных системах связи. Высокие требования к полосе частот и возможносп запоминания явились мотивом его развития, в то время как интегрированные схемы и методы обработки сигналов предоставили такую возможность.
Вторичной причиной широкого внедрения процесса в систему связи является определение обшеиндустриальных стандартов, которые позволяют множеспюнным поставщикам проводить рентабельную и конкурентоспособную реализацию процесса кодирования. Существуют стандарты МККТТ для кодирования источника или алгоритмов сжатия речи, аудио, неподвижных образов и движущихся изображений. В этом разделе будет изучено множество алгоритмов кодирования источника, основанных на стандартах, что должно продемонстрировать широкую применимость кодирования источника в системах связи и проиллюстрировать типичные уровни производительности.
поиска, формируется группа, содержащая последовательность параметров голоса, последовательность адресов кодовой книги и информацию о коэффициентах 1.РС. Кодер должен доставить параметры, описывающие модель ЬРС, на декодер. Спектральная характеристика фильтра 1.РС очень чувствительна к квантованию коэффициентов и как таковая должна бы представляться с помощью неприемлемо большого числа бит.
Поэтому коэффициенты ЬРС преобразуются в иное множество параметров, названных линейными спекпгральнымп парами (!О), которые являются нечувствительными к квантованию. Системы, созданные согласно стандарту 18-95, используют следующий формат кадра ЬРС. Кадр, требуемый для описания 2 мс данных, содержит !92 бит, присвоенных представителю закодированных параметров. 1О коэффициентов ЬРС 40 бит 4 параметра запаздывания и опережения 40 бит 8 адресов кодовой книги 80 бит Биты четности, проверочные биты и прочая служебная информация 32 бит Общая скорость передачи битов для этой системы составляет 192 бит за 20 мс, нли 9600 бит/с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
