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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
3. не может быть декодирован и использовать его нельзя. Первый бит последовательно-
сти равен 1, поэтому первым символом может быть только символ
1
a
, так как ни какой
другой код не начинается с 1. Следующий код последовательности равен 0 , но коды
2
a
,
3
a
и
4
a
оба начинаются с 0, поэтому декодер должен читать следующий бит, он равен 1,
однако коды для
2
a
и
3
a
оба имеют в начале 01 – декодер не знает, как ему поступить,
декодирование невозможно.
В отличие от
code
1 к
code
2 имеет важное свойство , которое называется свойством
префикса. Это свойство предполагает, что если некоторая последовательность битов вы-
брана в качестве символа, то ни один код другого символа не может начинаться с этой по-
следовательности, не может быть префиксом или приставкой. Раз строка «1» уже выбра-
на для символа
1
a
, то ни одна другая кодовая комбинация не может начинаться с 1. Если
строка «01» выбрана в качестве кода для
2
a
, то никакая другая кодовая комбинация не
может начинаться с 01.
Таким образом, при выборе кода переменой длины следует назначать более корот-
кие коды часто встречающимся символам и выбранный код должен удовлетворять свой-
ству префикса. Для декодирования префиксного кода декодер должен знать префикс-
ный код каждого символа.
Решение этой задачи достигается 3 путями. Первое - префиксный код выбирается и
используется как кодерам, так и декодером. Во втором варианте кодер выполняет свою
работу в два этапа. Сначала он читает сжимаемый файл и собирает необходимые стати-
стические сведения. На втором этапе на основе полученной статистической информации
выбирается наилучший префиксный код и происходит сжатие, при этом таблицу кода
следует передавать по линии связи декодеру. В третьем варианте кодер сразу начинает
работать, не зная статистических свойств сжимаемого файла. По мере сжатия и сбора
статистической информации кодер улучшает префиксный код, что приводит к увеличе-
нию компрессии. Декодер повторяет все операции кодера. Такое кодирование называется
адаптивным.
4.3. Код Хаффмана
Метод сжатия информации на основе двоичных кодирующих деревьев был предложен
Д. А. Хаффманом в 1952 году задолго до появления современного цифрового компьютера.
Обладая высокой эффективностью, он и его многочисленные адаптивные версии лежат в
основе многих методов, используемых в современных алгоритмах кодирования. Код
Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами
кодирования. Метод Хаффмана является примером построения кодов переменной длины,
имеющих минимальную среднюю длину. Этот метод производит идеальное сжатие, то
есть сжимает данные до их энтропии, если вероятности символов точно равны отри-
цательным степеням числа 2.
Стоит отметить, что за 50 лет со дня опубликования, метод Хаффмана ничуть не поте-
рял своей актуальности и значимости. Так с уверенностью можно сказать, что мы сталки-
ваемся с ним, в той или иной форме практически каждый раз, когда архивируем файлы,
смотрим фотографии, фильмы, посылаем факс или слушаем музыку.
Идея, лежащая в основе метода Хаффмана, достаточно проста. Вместо того чтобы ко-
дировать все символы кодовой последовательности одинаковым числом бит, как это дела-
ется в ASCII кодировке, и где на каждый символ отводится ровно по 8 бит, в коде Хафф-
мана кодируются символы, которые встречаются чаще, меньшим числом бит, чем те, ко-
торые встречаются реже. Коды Хаффмана имеют префикс, что и позволяет однозначно их
декодировать, несмотря на их переменную длину. Динамический алгоритм Хаффмана на
входе получает таблицу частот символов в сообщении. Далее на основании этой табли-
цы строится дерево кодирования Хаффмана. Поэтому первый алгоритм, опубликованный

Страницы