Статистическое компрессирование аудио сигналов. Вологдин Э.И. - 27 стр.

UptoLike

ВУЗ: 

СПбГУТ | Санкт-Петербург

Составители: 

Рубрика: 

27
битов. Такой подход работоспособен, но он значительно снижает степень сжатия, особен-
но на коротких сообщениях.
Лучше начинать моделирование с пустого дерева и добавлять в него символы только
по мере их появления в сжимаемом сообщении. Но это приводит к очевидному противо-
речию: когда символ появляется в сообщении первый раз, он не может быть закодирован,
так как его еще нет в дереве кодирования. Чтобы разрешить это противоречие вводится
специальный код, который означает, что следующий символ закодирован вне контекста
модели сообщения.
4.4. Арифметическое кодирование
Метод Хаффмана обладает очень высокой эффективностью только при условии, что
у формируемого кода переменной длины средняя длина равна энтропии алфавита. Одна-
ко, это возможно только в случаях, когда вероятности символов алфавита являются сте-
пенями числа 2, то есть равны 1/2, 1/4, 1/8 и т.п. Тогда по методу Хаффмана каждому
символу алфавита присваивается код с целым числом битов. Теория информации предска-
зывает, что при вероятности символа, скажем, 0.4, ему в идеале следует присвоить код
длины 1.32 бита, а метод Хаффмана присвоит этому символу код длины 1 или 2 бита, что
снижает эффективность кода. Эта проблема решается при арифметическом кодировании.
Арифметическое кодирование это блоковое кодирование, при котором кодируют-
ся не символы, как в коде Хаффмана, а блоки данных, состоящие из множества симво-
лов. Сжатый блок данных представляется одним кодовым словом, часто очень большой
длины. При кодировании обрабатывается символ за символом входного блока данных и
добавляются биты к сжатому файлу. Блок аудиоданных, сжатый арифметическим коде-
ром, рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия
можно представить как последовательность двоичных цифр из записи этой дроби.
Алгоритм арифметического кодирования наиболее наглядно представляется в графи-
ческом виде. В этом алгоритме блок данных, включающий все символы, представляется
в виде отрезка линии с границами [0,1). Каждый символ блока представляется отрезком
на числовой оси с длиной, равной вероятности его появления и началом, совпадающим с
концом отрезка символа, предшествующего ему в алфавите. Сумма всех отрезков, оче-
видно должна равняться единице (рис.23).
Кодируются символы шагами, последовательно, один за другим. На каждом шаге те-
кущий интервал, соответствующий вероятности кодируемого сигнала, уменьшается про-
порционально вероятности следующего символа. Этот символ «вырезает» из текущего
интервала подынтервал пропорционально своей вероятности. После каждого шага кодиро-
вания, а текущий интервал становится все меньше, поэтому требуется все больше бит для его
представления в двоичном коде. Кодом сообщения является интервал, выделенный после
кодирования всех его символов, точнее, любое число, входящее в этот интервал. Длина
полученного интервала пропорциональна вероятности кодируемого блока данных. Ре-
зультатом кодирования является единственное двоичное кодовое слово, в котором сжата вся
информация входного блока .
Перед кодированием определяются экспериментально или берутся из таблиц частоты
следования каждого символа алфавита. Эта операция обычно осуществляется на первом
проходе алгоритма сжатия. Однако, если можно получить хорошие оценки частот символов
из другого источника, первый проход можно опустить.
Основой арифметического кодирования является алгоритм определения верхней и нижней
границ интервалов кодирования каждого символа.. Они , определяются равенствами:
для первого символа
11
()G low L
,
11
()G high H
,
для последующих символов

Страницы