Файл: Методы кодирования данных.pdf

6. АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ

Арифметическое кодирование – один из алгоритмов энтропийного сжатия.

В отличие от алгоритма Хаффмана, не имеет жесткого постоянного соответствия входных символов группам бит выходного потока. Это даёт алгоритму большую гибкость в представлении дробных частот встречаемости символов^[11].

Как правило, превосходит алгоритм Хаффмана по эффективности сжатия, позволяет сжимать данные с энтропией, меньшей 1 бита на кодируемый символ, но некоторые версии имеют патентные ограничения от компании IBM

Пусть имеется некий алфавит, а также данные о частотности использования символов (опционально). Тогда рассмотрим на координатной прямой отрезок от 0 до 1.

Назовём этот отрезок рабочим. Расположим на нём точки таким образом, что длины образованных отрезков будут равны частоте использования символа, и каждый такой отрезок будет соответствовать одному символу^[12].

Теперь возьмём символ из потока и найдём для него отрезок среди только что сформированных, теперь отрезок для этого символа стал рабочим. Разобьём его таким же образом, как разбили отрезок от 0 до 1. Выполним эту операцию для некоторого числа последовательных символов. Затем выберем любое число из рабочего отрезка. Биты этого числа вместе с длиной его битовой записи и есть результат арифметического кодирования использованных символов потока.

Возьмём для примера следующую последовательность:

NEUTRAL POSITIVE NEGATIVE END-OF-DATA

Сначала разобьём отрезок от 0 до 1 согласно частотам сигналов. Разбивать отрезок будем в порядке, указанном выше: NEUTRAL – от 0 до 0,6; POSITIVE – от 0,6 до 0,8; NEGATIVE – от 0,8 до 0,9; END-OF-DATA – от 0,9 до 1.

Теперь начнём кодировать с первого символа. Первому символу – NEUTRAL соответствует отрезок от 0 до 0,6. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем второй символ – NEGATIVE. На отрезке от 0 до 0,6 ему соответствует отрезок от 0,48 до 0,54. Разобьём этот отрезок аналогично отрезку от 0 до 1.

Закодируем третий символ – END-OF-DATA. На отрезке от 0,48 до 0,54 ему соответствует отрезок от 0,534 до 0,54.

Так как это был последний символ, то кодирование завершено. Закодированное сообщение – отрезок от 0,534 до 0,54 или любое число из него, например, 0,538.

7. АДАПТИВНЫЕ МЕТОДЫ КОДИРОВАНИЯ

Эффективность метода ДИКМ может быть повышена путем перехода к адаптивной дифференциальной импульсно-кодовой модуляции (АДИКМ). При этом производится автоматическое регулирование величины шага квантования сигнала ошибки предсказания, а также автоматическая подстройка коэффициентов c_i трансверсального фильтра устройства предсказания (рис. 3) в соответствии с изменением текущего спектра сообщения.

Рис. 3. Структурная схема трансверсального фильтра устройства предсказания

Для этого как в передающее, так и в приемное устройства вводятся дополнительные цепи автоматической регулировки усиления и подстройки параметров предсказателя на основе статистического оценивания параметров передаваемого сообщения^[13].

Амплитуда речевого сигнала (РС) может изменяться в широких пределах в зависимости от диктора, условий передачи, а также внутри фразы при переходе от вокализованного к невокализованному сегменту. Один из методов учета этих флуктуаций состоит в адаптации свойств квантователя к уровню входного сигнала. Учесть нестационарный характер РС, в частности медленное изменение его мощности (дисперсии), позволяет адаптивный квантователь.

Основная идея адаптивного квантования состоит в том, что шаг квантования изменяется таким образом, чтобы соответствовать изменяющейся дисперсии кодируемого сигнала. В результате размеры шкалы квантования подстраивают в соответствии с энергией речи так, чтобы слабые сигналы квантовались малыми ступенями квантования, а сильные сигналы – большими. Благодаря непрерывной подстройке шага квантования к текущей мощности речи, разрядность шкалы квантования при АДИКМ удалось снизить до четырех бит.

Адаптивная дифференциальная ИКМ была стандартизирована в 1984 г. (Рек. ITU-T G.721) для скорости передачи речи 32 кбит/с, и включает в себя два метода обработки сигнала: дифференциальное кодирование с предсказанием и адаптивное квантование (рис. 4).

Рис. 4. Схема кодирования речи по Рек. ITU-T G.721

Аналоговый сигнал дискретизируется и линейно обрабатывается в 12-битном (b=12) квантователе. На следующем этапе вычисляется ошибка предсказания как разность между реальным и предсказанным значениями сигнала. Представленный 12-битным словом разностный сигнал обрабатывается в квантователе, имеющим логарифмическую (по основанию 2) характеристику и 16 порогов квантования (b=4). В результате формируется 4-битовое представление ошибки отсчета, что при частоте дискретизации 8 кГц обеспечивает скорость цифрового потока на выходе кодера АДИКМ равной 32 кбит/с. 4-битовый разностный сигнал на основе статистического оценивания его параметров позволяет определить коэффициенты предсказания, используемые как в адаптивном квантователе, так и в схеме адаптивного предсказания.

8. СЛОВАРНЫЕ КОДЫ КЛАССА LZ

Словарные коды класса LZ широко используются в практических задачах. На их основе реализовано множество программ-архиваторов. Эти методы также используются при сжатии изображений в модемах и других цифровых устройствах передачи и хранения информации.

Словарные методы сжатия данных позволяют эффективно кодировать источники с неизвестной или меняющейся статистикой. Важными свойствами этих методов являются высокая скорость кодирования и декодирования, а также относительно небольшая сложность реализации. Кроме того, LZ-методы обладают способностью быстро адаптироваться к изменению статистической структуры сообщений.

Словарные коды интенсивно исследуются и конструируются, начиная с 1977 года, когда появилось описание первого алгоритма, предложенного А.Лемпелом и Я.Зивом. В настоящее время существует множество методов, объединенных в класс LZ-кодов, которые представляют собой различные модификации метода Лемпела-Зива.

Общая схема кодирования, используемая в LZ-методах, заключается в следующем. При кодировании сообщение разбивается на слова переменной длины. При обработке очередного слова ведется поиск ему подобного в ранее закодированной части сообщения. Если слово найдено, то передается соответствующий ему код. Если слово не найдено, то передается специальный символ, обозначающий его отсутствие, и новое обозначение этого слова. Каждое новое слово, не встречавшееся ранее, запоминается, и ему присваивается индивидуальный код^[14].

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

По способу организации хранения и поиска слов словарные методы можно разделить на две большие группы:

• алгоритмы, осуществляющие поиск слов в какой-либо части ранее закодированного текста, называемой окном;
• алгоритмы, использующие адаптивный словарь, который включает ранее встретившиеся слова. Если словарь заполняется до окончания процесса кодирования, то в некоторых методах он обновляется (на место ранее встретившихся слов записываются новые), а в некоторых кодирование продолжается без обновления словаря.

Алгоритмы класса LZ отличаются размерами окна, способами кодирования слов, алгоритмами обновления словаря и тому подобное. Все указанные факторы влияют и на характеристики этих методов: скорость кодирования, объем требуемой памяти и степень сжатия данных, различные для разных алгоритмов. Однако в целом методы из класса LZ представляют значительный практический интерес и позволяют достаточно эффективно сжимать данные с неизвестной статистикой.

8.1. Кодирование с использованием скользящего окна

Рассмотрим основные этапы кодирования сообщения Х=х₁х₂х₃х₄…, которое порождается некоторым источником информации с алфавитом А. Пусть используется окно длины W, то есть при кодировании символа x_i исходной последовательности учитываются W предыдущих символов^[15].

Сначала осуществляется поиск в окне символа х₁. Если символ не найден, то в качестве кода передается 0 как признак того, что этого символа нет в окне и двоичное представление х₁.

Если символ х₁ найден, то осуществляется поиск в окне слова х₁х₂, начинающегося с этого символа. Если слово х₁х₂ есть в окне, то производится поиск слова х₁х₂х₃ , затем х₁х₂х₃х₄ и так далее, пока не будет найдено слово, состоящее из наибольшего количества входных символов в порядке их поступления^[16]. В этом случае в качестве кода передается 1 и пара чисел (i, j), указывающая положение найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина этого слова, позиции в окне нумеруются справа налево). Затем окно сдвигается на j символов вправо по тексту и кодирование продолжается.

Для кодирования чисел (i, j) могут быть использованы рассмотренные ранее коды целых чисел.

Пример.

Пусть алфавит источника А={а, b, с}, длина окна W=6. Необходимо закодировать исходное сообщение bababaabacabac (рис. 5).

Рисунок 5. Кодирование последовательности bababaabacabac

Заключение

После кодирования первых шести букв окно будет иметь вид bababa.

• Далее проверяем наличие в окне буквы а. Она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Этого слова нет в окне, тогда кодируем aba кодовой комбинацией (1,3,3), где 1– признак того, что слово есть в «окне», 3 – номер позиции в окне, с которой начинается это слово, 3 – длина этого слова.
• Далее окно сдвигаем на 3 символа вправо и ищем в окне букву с. Ее нет в окне, поэтому кодируем комбинацией (0, «с»), где 0 – признак того, что буквы нет в окне, «с» – двоичное представление буквы. Окно сдвигаем на 1 символ вправо.
• Ищем в окне букву а, она найдена, добавляем к ней b, ищем в окне ab. Эта пара есть в окне, добавляем букву а, ищем aba. Это слово есть в окне, добавляем букву с, ищем abac. Это слово есть в окне, тогда кодируем abaс кодовой комбинацией (1,4,4), где 1 – признак того, что слово есть в окне, 4 – номер позиции в окне, с которой начинается это слово, 4 – длина этого слова.

СПИСОК ЛИТЕРАТУРЫ

1. Белоногов, Г.Г. Автоматизация процессов накопления, поиска и обобщения информации / Г.Г. Белоногов, А.П. Новоселов. - М.: Наука, 2017. - 256 c.
2. Берлекэмп, Э. Теория кодирования / Э. Берлекэмп. - М.: [не указано], 2017. – 575 c.
3. Верещагин, Н. К. Информация, кодирование и предсказание / Н.К. Верещагин, Е.В. Щепин. - М.: ФМОП, МЦНМО, 2016. - 240 c.
4. Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 2004.
5. Кудряшов Б.Д. Теория информации. Учебник для вузов Изд-во ПИТЕР, 2014. - 320с.
6. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 2014. - Т.35, Вып. - С.95 - 108.
7. Семенюк В.В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2011
8. Быков С.Ф., Журавлев В.И., Шалимов И.А. Цифровая телефония: Учеб. пособие для вузов. – М.: Радио и связь, 2013. -144 с.
9. Назаров М.В., Прохоров Ю.Н. Методы цифровой обработки и передачи речевых сигналов. - М.: Радио и связь, 2012. - 176 с.
10. Грошев А.С., Закляков П. В, Информатика: учеб. для вузов — 3-е изд., перераб. и доп. — М.: ДМК Пресс, 2015 — 588 с.
11. Шелухин О.И., Лукьянцев Н.Ф. Цифровая обработка и передача речи. – М.: Радио и связь, 2014. – 456 с.
12. https://studfiles.net/preview/2919113/page:7/
13. https://ru.wikipedia.org/wiki/Арифметическое_кодирование
14. https://studfiles.net/preview/6389276/page:5/
15. https://studfiles.net/preview/2919113/page:14/

1. Белоногов, Г.Г. Автоматизация процессов накопления, поиска и обобщения информации / Г.Г. Белоногов, А.П. Новоселов. - М.: Наука, 2017. - 256 c. ↑

2. Берлекэмп, Э. Теория кодирования / Э. Берлекэмп. - М.: [не указано], 2017. – 575 c. ↑

3. Верещагин, Н. К. Информация, кодирование и предсказание / Н.К. Верещагин, Е.В. Щепин. - М.: ФМОП, МЦНМО, 2016. - 240 c. ↑

4. Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 2004. ↑

5. Кудряшов Б.Д. Теория информации. Учебник для вузов Изд-во ПИТЕР, 2008. - 320с. ↑

6. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 2009. - Т.35, Вып. - С.95 - 108. ↑

7. Семенюк В.В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2001 ↑

8. Быков С.Ф., Журавлев В.И., Шалимов И.А. Цифровая телефония: Учеб. пособие для вузов. – М.: Радио и связь, 2003. -144 с. ↑

9. Назаров М.В., Прохоров Ю.Н. Методы цифровой обработки и передачи речевых сигналов. - М.: Радио и связь, 1985. - 176 с. ↑

10. https://studfiles.net/preview/2919113/page:7/ ↑

11. https://ru.wikipedia.org/wiki/Арифметическое_кодирование ↑

12. Шелухин О.И., Лукьянцев Н.Ф. Цифровая обработка и передача речи. – М.: Радио и связь, 2000. – 456 ↑

13. https://studfiles.net/preview/6389276/page:5/ ↑

14. https://studfiles.net/preview/2919113/page:14/ ↑

15. https://studfiles.net/preview/2919113/page:14/ ↑

16. https://studfiles.net/preview/2919113/page:14/ ↑