НАУКА и ОБРАЗОВАНИЕ

УДК 621.391:519.72

Сидякин И.М., Павлов Ю.Н.

1.Коды Голомба-Райса

При кодировании коротких сообщений состоящих из символов принадлежащих большому алфавиту алгоритм Хаффмана и арифметическое кодирование становится более сложным в реализации и менее эффективным, за счёт возрастающего объёма служебной информации. Для источников такого типа часто более эффективным оказывается применение универсальных алгоритмов кодирования, которые используют заранее заданные ФПВ.

Для сжатия ТМИ предлагается простая и эффективная процедура кодирования методом Райса. Коды Райса являются частным случаем кодов Голомба. Коды Голомба эффективны для источников подчиняющихся геометрическому распределению: . Двусторонне геометрическое распределение, в свою очередь является хорошей статистической моделью сигнала ошибки линейного предсказания. Длина кодового слова символа равна , , где регулируемый параметр алгоритма кодирования. Первые бит кодового слова равны нулю. За ними следует бит равный 1, который разделяет кодовое слово на две части. Следующие бит используются для хранения остатка от деления . Для заданного значения , значение рассчитывается по формуле

(1)

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

(2)

, где константа, , среднее значение входного сигнала.

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

Кодируемое число разделяется на два слагаемых , где

и

Кодовое слово формируется соединением представленным унарным кодом и представленным битами двоичного кода. Коды Райса эффективны для значений близких к и рекомендуются для источников с геометрической ФПВ.

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

Зависимость средней длины кодового слова при длине блока 32 отсчёта от оценки энтропии приведена на рисунке 1. Параметр определяется адаптивным алгоритмом. Оценка энтропии рассчитывается на более длинных блоках N=256 отсчётов. Изменения статистических характеристик на коротких участках учитываются при кодировании методом Райса короткими блоками, и усредняются при вычислении оценки энтропии на более длинных блоках. Этим объясняется тот факт, что среднее значение кодового слова оказывается ниже значения оценки энтропии. Это означает лишь то, что оценка энтропии даёт значение энтропии в среднем на длинном участке, но реальное значение энтропии на этом участке отклоняется от её среднего значения. В то же время расчёт оценки энтропии на коротких блоках имеет низкую точность. На рисунке 1 показана зависимость средней длины кодового слова от значения оценки энтропии при расчёте этой оценки на блоке длиной N=32 отсчёта. На рисунке 1 показаны исходные данные, регрессионные полиномы 3-й степени и доверительные 95 % интервалы.

Рис 1.Экспериментальная зависимость средней длины кодового слова от значения энтропии для кода.N=32.

Литература

[1]S.W.Golomb. Run-length encodings. IEEE Trans. Inform. Theory, pp. 399-401, 1966.

[2] R.F. Rice, Some Practical Universal Noiseless Coding Techniques, Jet Propulsion Laboratory, JPL Publication 79-22, Pasadena, California Mar 1979.

[3] Lossless data compression. Recommendation for space data systems standards. CCSDS 121.0-B-1, Issue 1, 1997.

[4] P.-S. Yeh, W.Serafino, L. Miles, B.Kobler, D.Menasce. Implementation of CCSDS lossless data compression in HDF. Proc. Of NASA ESTO Conf. 2002, Pasadena,CA,June 11-13, 2002.