УДК 621.398

Сидякин И.М.,

Павлов Ю.Н.

1.Описание метода сжатия

Арифметическое кодирование считается оптимальным для стационарного источника без памяти на основании того, что предел ожидаемого значения среднего количества бит на символ равен энтропии источника:

(1)

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

Кодируемая информация представляет собой последовательность квантованных по времени и уровню отсчётов аналоговых сигналов ТМИ. Каждый отсчёт представлен целым n – разрядным числом без знака. Информация разделяется на блоки отсчётов фиксированной длины. Каждый блок кодируется независимо. Исходный блок информации разделяется на битовые слои. Каждый битовый слой содержит биты одного из разрядов всех отсчётов блока. Вначале кодируется и передаётся в канал битовый слой, содержащий старшие значащие разряды. Последним кодируется и передаётся битовый слой, содержащий младшие значащие разряды. В случае задержки при передаче битового потока, которая приводит к переполнению буфера передатчика, младшие битовые слои теряются.

Двоичное арифметическое кодирование использует адаптивную подстройку таблицы частот появления символов. Алфавит содержит два символа: 0 и 1. Подстройка таблицы частот происходит при обработке очередного входного символа. В исходном состоянии предполагается, что вероятности появления символов равны. Сброс таблицы частот в исходное состояние происходит каждый раз при переходе к следующему блоку или следующему битовому слою. Очевидно, что разные битовые слои могут иметь резко отличающиеся параметры статистических моделей. Проведённые эксперименты подтверждают это предположение.

Используемый алгоритм двоичного арифметического кодирования состоит из трёх основных процедур: перерасчёт границ интервала(a), ренормализация (б) и перерасчёт таблицы частот (в). Эти процедуры приведены на рисунке 1.

На рисунке использованы следующие обозначения: начальная граница интервала; длина интервала; символ входной двоичной последовательности; счётчик символов выходной двоичной последовательности; символ выходной двоичной последовательности; счётчик символов выходной двоичной последовательности; счётчик символов 0 во входной последовательности; счётчик символов входной последовательности.

На рисунке не показана процедура определения и обработки переноса.

Рис.1. Процедура двоичного кодирования.

2.Результаты экспериментов

Рис. 2. Двоичное арифметическое кодирование. Средняя длина кодового слова.

Зависимость средней длины кодового слова от размера блока для ВЧ параметров приведена на рисунке 2. Зависимость имеет хорошо выраженный минимум при длине блока около 8000 отсчётов.

Литература

[1] C.E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379–423, 623–656, 1948.

[2] D. A. Huffman, A method for the construction of minimum redundancy codes, Proc. IRE, vol. 40, pp. 1098–1101, Sept. 1952.

[3] J. Rissanen, G.G. Langdon. Arithmetic coding. IBM J. Res. Dev. 23, 2, pp.149-162, 1979.

[4] Witten, R. Neal, J. Cleary. Arithmetic coding for data compression. Comm. Of the ACM, 30(6), 1278–1288, 1986.

[5] S. D. Stearns. Arithmetic coding in lossless waveform compression. IEEE Trans. Signal Proc., vol. 43, pp. 1874–1879, 1995.

[6] А. Said, Introduction to arithmetic coding – theory and practice. HPL-2004-76, 2004.