Вернер М. Основы кодирования (2004), страница 10

Избыточность может быть устранена без потери информации. Примером является кодирование Хаффмана. Такое кодирование называют кодированием без потерь.Важнейшими примерами сжатия данных являются цифровое радиовещание (Digital Audio Broadcasting, DAB) и цифровое телевидение (Digital Video Broadcasting, DVB)[19]. Обе системы работаютна основе кодирования аудио и видео сигналов, использующего стандарты MPEG (Motion Pictures Experts Group). Кодирование аудиосигнала основано на психологической модели восприятия речи, которая использует скрытые спектральные и временные эффекты, приэтом в сигнальном блоке происходит удаление невоспринимаемой наслух части аудиосигнала (несущественной информации).

Аналогичные эффекты используются также при кодировании видеосигнала (вчастности, психологический эффект движения). Кодирование изображений позволяет достичь еще большей степени сжатия.Глава 6. Сжатие данныхСтепень сжатия определяется затратами для передачи или хранения информации без сжатия fco и затратами с использованиемнекоторого метода сжатия ктКО — КтG.(6.1)fcoСтепень сжатия зависит от используемого алгоритма и свойств источника. Приведем некоторые численные примеры степеней сжатия,достигаемых на практике :-до 80 % для текстовых данных (в формате редактора Word 97 спомощью программы сжатия ZIP);-87,5 % при переходе от РСМ-телефонии со скоростью 64 кбит/секк передаче информации по рекомендации ITU G.725 со скоростью 8кбит/сек;-90 % при кодировании информации стереофоничских аудио компакт дисков со скоростью 2-16 бит-44 кГц = 1408 кбит/сек методом,использующим стандарт сжатия MPEG (Advanced Audio Coding) соскоростью 112 кбит/сек и почти равнозначным качеством речи.Следующим примером является энтропия немецкого литературного текста.

Результаты частотного анализа представлены на рис.6.1. Если рассматривать буквы изолированно, то получим энтропию,приблизительно равную 4,7 бит/букву. Объединяя буквы в блоки,мы используем уже такие очевидные связи, как слоги, слова и т.д.,поэтому, для блоков очень большой длины асимптотически достижимая граница равна Г, 6 бит/букву.ЭнтропияO—rj4,7 бит/символ1,6 бит/символ-——пв 1Длина блок•+-*•л = 10Р и с .

6.1. Энтропия немецкого литературного языка какфункция длины блокаАлгоритмы сжатияданных можно разделить на три группы:1. Статические алгоритмы, например, кодирование Хаффмана.Сжатие немецкого литературного текста методом Хаффмана,по сравнению с сжатием информации, состоящей из произволь-6.2. Арифметическое кодированиеных стандартных символов ASCII, позволяет достичь приблизительно 50 % выигрыша.2.

Адаптивные алгоритмы, например, модифицированное кодирование Хаффмана. Здесь распределение вероятностей символов вначале полагается равномерным, а потом меняется вовремени по мере накопления статистики.3. Динамические алгоритмы, например кодирование, используемое в рекомендации ITU V42. bis.Основная проблема энтропийного кодирования заключается втом, что оно предполагает знание распределения вероятностей символов. Очень часто статистика символов заранее неизвестна и эффективному кодированию должен предшествовать частотный анализ. Здесь на помощь приходят универсальные алгоритмы.• Универсальные алгоритмы сжатия, являющиеся по своей сути адаптивными, не нуждаются в априорной статистике.

Такоеэффективное кодирование начинается сразу же после поступления информации на вход кодера.• Кроме этого, существуют «быстрые» алгоритмы с относительно простой технической сложностью.• Каждый из предполагаемых алгоритмов помогает достичь высокой степени сжатия.В качестве примера методов сжатия, рассмотрим два важнейшихалгоритма: арифметическое кодирование, лри котором производитсядинамический частотный анализ и универсальный алгоритм ЛемпеляЗива. Алгоритм Ле'мпеля-Зива LZ77 был предложен в 1977 году и модифицирован в 1984 г.

Он используется в рекомендации ITU V.42.bisи называется LZW алгоритмом.6,2. Арифметическое кодированиеПри арифметическом кодировании мы исходим из того факта, чтопри нормализованном распределении сумма вероятностей символов(и соответствующих им относительных частот) источника всегда равна единице. Если относительные частоты символов неизвестны передатчику и приемнику:к78Глава 6. Сжатие данныхТаблица 6.1. Буквы и их относительные частоты.БукваОтносительная частотаЕSGLR0,50,20,10,10,1- они могут определяться, например, путем текущих статистических изменений передаваемой информации в фиксированные моменты времени;- приемник и передатчик совместно, исходя из относительныхчастот, устанавливают жесткие правила кодирования.Особенностью арифметического кодирования является то, чтодля отображения последовательности символов в потоки натуральных чисел на интервале [0,1] используются относительные частоты.Результатом такого отображения является сжатие символов (посимвольное сжатие) в соответствии с их вероятностями.

Пояснимидею арифметического кодирования с помощью следующего примера.Рассмотрим арифметическое кодирование последовательностибукв «GELEEESSER». Относительные частоты букв в этом потокеприведены в таблице 6.1.Процедура кодирования представлена на рис. 6.2.Первой букве «G», в соответствии с ее относительной частотой,соответствует интервал [0.7,0.8[. Согласно алгоритму, каждая цепочка букв, начинающихся с G, всегда будет отображаться в число, принадлежащее этому интервалу. Таким образом, в рассматриваемомпримере первая десятичная цифра после запятой уже определена.Кодирование последующих букв производится аналогично с темважным отличием, что теперь делению каждый раз будет подвергаться интервал, выбранный на предыдущем шаге.

Из рис. 6.2 следует, что букве «Е» на втором шаге соответствует интервал [0.7,0.75[.Таблица 6.3, в которой алгоритм кодирования прослежен но шагам, показывает, что последовательность «GELEEESER» отображается в число 740387 (0 и запятая не нуждаются в отображении). Отметим, что:1. Часто встречающимся буквам ставятся в соответствие большиеинтервалы.

На их отображение затрачивается меньше десятичныхцифр, чем на отображение редко встречающихся букв.2. Длинные сообщения отображаются в «длинные» числа. Представление этих чисел в двоичной форме, необходимое для передачисообщений, приводит к появлению кодовых слов большой длины.6,2. Арифметическое кодирование79 JПрактическая реализация скользящего алгоритма арифметического кодирования требует высокой точности, которая ограничивается длиной кодовых слов. Для сокращения необходимой длины регистра, при реализации арифметического кодирования используетсяцелочисленная арифметика с выдачей уже готовых промежуточныхрезультатов.Рис.

6.2. Арифметическое кодирование.Алгоритм представлен в таблице 6.2. Механизм его действия раскрывается с помощью таблицы 6.3. В нашем примере для реализациикодирования достаточно регистра для хранения шести текущих десятичных цифр.В соответствии с таблицей 6.2, на первом шаге происходит инициализация переменных LO и HI. Для первой кодируемой буквы«G» ширина интервала равна В = l'000'OOO. Нижняя и верхняя границы равны соответственно LO =F 0 4- l'000'OOO • 0, 7 = 700'000 и/// = 0 + l'000'OOO -0,8- 1 = 799'999. Первая десятичная цифра ужеопределена и равна 7, а содержимое регистров LO и HI сдвигаетсяна одну позицию влево.

Заметим, что в регистре LO освободившеесяместо занимает 0, а в регистре HI - 9.к80Глава. 6. Сжатие данныхТаблица 6.2. Алгоритм арифметического кодирования.Начальные значенияIII - 999'999РегистрLO- ООО'ОООСимволЕSGLRLS(-)00,50,70,80,9HS(-)0,50,70,80,91АлгоритмШирина интервалаВ=Ш-Ш+1Нижняя границаLO=LO - B L SВерхняя границаHI-LO+BHS-1Для второй буквы «Е» ширина интервала равна В = l'000'OOO,поэтому, получаем LO = 0 + l'000'OOO = ОООО' ОО и HI = 0+ l'000'OOO0,5 — 1 = 499'999. Кодирование последующих букв проводится аналогично.

В завершении работы алгоритма выдается некоторое числоиз последнего интервала. Для этого мы округляем верхнюю границу интервала HI, отбрасывая младшие разряды до тех пор, покаэто возможно. В результате получаем число с минимальным количеством цифр, принадлежащее последнему интервалу.6.3. Кодирование Лемпеля - ЗиваАлгоритм кодирования Лемпеля Зива LZ77 основан на принципединамических словарей. Мы представим вкратце эту концепцию инаглядно поясним ее на простейших примерах [19].В основе алгоритма лежат четыре основные идеи:1. Каждая очередная закодированная последовательность символов добавляется к ранее закодированным символам таким образом, что вместе с ними она образует разложение всей переданной и принятой информации на несовпадающие междусобой фразы (Парсинг).2.

Такое разложение хранится в памяти и используется в дальнейшем в качестве словаря.3. Кодирование осуществляется при помощи указателей на фразыиз уже сформированного словаря фраз. .6.3. Кодирование Лемпсля - ЗиваТаблица 6.3. Арифметическое«GELEEESSER».СимволLOIIIСтартООО'ООО 999'999G700'000 799'999Выход/сдвиг ООО'ООО 999'999ЕООО'ООО 499'999L400'000 449'999Выход/сдвиг ООО'ООО 499'999кодированиеВыходСимволLOЕфразыHIS312'500 437'499S375'000 399'999Выход/сдвиг 750'000 999'9994ВыходООО'ООО 062'499Выход/ сдвиг ООО'ООО 624'999781Е750'000 874'999862'500 874'999'ЕООО'ООО 249'999RЕООО'ООО 124'999Конец03874.

Кодирование является динамической процедурой, ориентированной на блоки. Сам процесс кодирования может быть дополнен скользящими окнами, содержащими текущий словарь фрази Look-ahead буфером.ФразаF A|C|H|H|O|C|H|S|C|H|U|L|E21 20 19 18 17 16 15 14 13 12 11 10 9 8lF|U|LlD765|43Буфер Look-aheadА¥ А С Н|В|Е R Е2 1Рис. 6.3.