<< Предыдущая

стр. 13
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


7г(2/1)
тг(1/2) тг(2/2)


n(2/N)
и начальным распределением




• Эквивалентом матрицы переходных вероятностей является 1т>аф
состояний с узлами, путями и весом путей, соответствующим состо-
яниям, переходам между состояниями и переходным вероятностям




Рис. 5.11.

• Распределение состояний гомогенной марковской цепи на п -ом шаге
определяется как
р„ = р 0 П " .
74 Глава 5. Стационарные дискретные источники с памятью

Таблица 5.4. Марковские цени, (продолженеие)


Гомогенная цепь Маркова стационарна, если распределение состояний по-
стоянно во времени. В этом случае начальное распределение является соб-
ственным вектором переходной матрицы, т.е

ро = РоП.



Гомогенная цепь Маркова регулярна, если существует предел

= lim П " ,
Пх

причем, все строки Пос равны предельному распределению рос.


Предельное распределение р^ является единственным стационарным рас-
пределением регулярной цепи Маркова.


Таблица 5.5. Стационарные Марковские источники.


Конечный дискретный марковский источник с памятью г полностью опре-
деляется следующими условиями:
Задано непустое множество состояний S = {Si,S2,... ,SN}, причем, S со-
держит все векторы длины г;
Каждое состояние Si 6 S соответствует дискретному источнику без памяти с
алфавитом X, = {xi, X2, • • •, хм} и вероятностями jVbix символов алфавита

Состояние S[n] = (х[п — г],х[п — г + 1],... ,х[п — 1]) из г последовательных
символов и очередной символ х[п] образуют новое состояние s[n+l] = (х[п —

Задано начальное распределение состояний ро = (ро(1),Ро(2),... ,po(N)).


Энтропия стационарного марковского источника с памятью г определяется
как математическое ожидание условных энтропии подисточников




при этом условная энтропия г-ого подисточника, соответствующего состоя-
нию г равна
м
H(X\Si) = - ? p S j (x m )log 2 (P S i (x m )) бит.
m=l
ГЛАВА 6
СЖАТИЕ
ДАННЫХ

6.1. Введение
Задачей сжатия данных является минимизация технических затрат
на хранение или передачу информации путем оптимального кодиро-
вания источников. При этом различают два понятия:

• Несущественная информация - это информация, которой мож-
но пренебречь при передаче. Примером может служить тради-
ционная телефония. В телефонных каналах передача инфор-
мации осуществляется в полосе 3,4 кГц. Все остальные спек-
тральные составляющие отбрасываются, при этом существен-
ная часть передаваемой-информации теряется. Ясно, что пер-
воначальный речевой сигнал не может быть полностью восста-
новлен на приемном конце. В этом случае говорят о кодирова-
нии с потерями.

• Под избыточностью понимают неоднократное повторение в со-
общении необходимой для приемника информации. Избыточ-
ность может быть устранена без потери информации. Приме-
ром является кодирование Хаффмана. Такое кодирование на-
зывают кодированием без потерь.

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

Степень сжатия определяется затратами для передачи или хра-
нения информации без сжатия fco и затратами с использованием
некоторого метода сжатия кт
КО — Кт .
(6.1)
G 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 бит/букву.

Энтропия

4,7 бит/символ-
O—rj

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. Буквы и их относительные частоты.

Е S
Буква G L R
0,5
Относительная частота 0,2 0,1
0,1 0,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. Длинные сообщения отображаются в «длинные» числа. Пред-
ставление этих чисел в двоичной форме, необходимое для передачи
сообщений, приводит к появлению кодовых слов большой длины.
79 J
6,2. Арифметическое кодирование

Практическая реализация скользящего алгоритма арифметиче-
ского кодирования требует высокой точности, которая ограничива-
ется длиной кодовых слов. Для сокращения необходимой длины ре-
гистра, при реализации арифметического кодирования используется
целочисленная арифметика с выдачей уже готовых промежуточных
результатов.




Рис. 6.2. Арифметическое кодирование.

Алгоритм представлен в таблице 6.2. Механизм его действия рас-
крывается с помощью таблицы 6.3. В нашем примере для реализации
кодирования достаточно регистра для хранения шести текущих де-
сятичных цифр.

<< Предыдущая

стр. 13
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>