СРАВНЕНИЕ КОДОВ ГОЛОМБА И ХАФФМАНА В СРЕДЕ MATLAB

COMPARE THE CODES GOLOMB AND HOFFMAN IN MATLAB

Daniel Golubev

student, Department of information security, Moscow State Technical University N.E. Bauman,

Russia, Moscow

Alexey Kodanev

student, Department of information security, Moscow State Technical University N.E. Bauman,

Russia, Moscow

Alexey Moroz

student, Department of information security, Moscow State Technical University N.E. Bauman,

Russia, Moscow

Mikhail Polyakov

student, Department of information security, Moscow State Technical University N.E. Bauman,

Russia, Moscow

ABSTRACT

The rationale for the selection of series lengths for encoding is presented, and comparative characteristics are developed. A simulation experiment was conducted and its results were provided. The analysis of the obtained data is carried out and conclusions are formulated.

АННОТАЦИЯ

Представлено обоснование выбора длин серий для кодирования, разработаны сравнительные характеристики. Проведен имитационный эксперимент, предоставлены его результаты. Проведен анализ полученных данных и сформулированы выводы.

Ключевые слова: matlab, код Голомба, код Хаффмана, коэффициент сжатия, избыточность на символ.

Keywords: matlab, Golomb code, code Hoffman, compression ratio, redundancy per character.

Теоретическая часть

Код Хаффмана

Алгоритм Хаффмана – адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево):

• Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который может быть равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение.
• Выбираются два свободных узла дерева с наименьшими весами.
• Создается их родитель с весом, равным их суммарному весу.
• Родитель добавляется в список свободных узлов, а два его потомка удаляются из этого списка.
• Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0. Битовые значения ветвей, исходящих от корня, не зависят от весов потомков.
• Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева (2).

КодГоломба

Рассмотрим источник, независимым образом порождающие целые неотрицательные числа с вероятностями ,где p–произвольное положительное число, не превосходящие 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число m таково, что

то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определенное кодовое слово) для такого источника будет код, построенный в соответствии с предложенной Соломоном Голомбом процедурой, согласно которой для каждого кодируемого числа  и кодированный в соответствии с описанной ниже процедурой остаток от деления :

• если  является степенью числа 2, то код остатка представляет собой двоичную запись числа , размещенную в битах;
• если  не является степенью 2, вычисляется число , далее: если , код остатка представляет собой двоичную запись числа , размещенную в битах,

иначе остаток кодируется двоичной записью числа , размещенную в bбитах.

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

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

Кодирование длин серий

Серия –последовательность, состоящая из нескольких одинаковых элементов.

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

Экспериментальная часть

Пусть имеется последовательность бит [5,5,5,5,5,5,5,5,5,5,5,5,5,5,2,2,2,2,2,2,2,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,3,5,5,5,4,4,4,4,7,7,9,9,9,9,8], сгенерированная случайным образом источником сообщения, имеющим геометрическое распределение случайной величины с заданной вероятностью. Поскольку данная последовательность состоит из нескольких серией с геометрическим распределением случайной величины, то использование кода Голомба при кодировании длин серий является оптимальным, поскольку для неё выполняется неравенство Галлагера – Ван Вурхиса.

Произведем сравнение кодов Голомба и Хаффмана по коэффициентам сжатия и избыточность на символ для кода Голомба.

В зависимости от априорной вероятности приема заданного символа для кода Голомба мы получили следующие значения коэффициентов сжатия (таблица 1).

Таблица 1.

Результаты имитационного эксперимента

Коэффициент сжатия – основная характеристика алгоритма сжатия. Она определяется как отношение объема исходных несжатых данных к объему сжатых, то есть

где k – коэффициент сжатия, S₀–объем исходных данных, S_с – объем сжатых.

Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее.

Определим энтропию источника сообщения как меру неопределенности, определяемую вероятностью появления тех или иных символов при передаче, по формуле

Где где p–произвольное положительное число, не превосходящие 1.

Преобразуем выражение (4)

Рисунок 1. График зависимости энтропии источника сообщения от вероятности принятия заданного символа.

Определим теоретическую избыточность на символ статического кода Голомба как превышение количества информации, используемой для передачи сообщения, над его информационной энтропией по формуле

где  – средняя длина кодового слова.

Рисунок 2. График избыточности на символ для кода Голомба как функция вероятности

Анализ результатов и выводы

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

Список литературы:

1. Энтропийное кодирование [Электронный ресурс]. – Режим доступа: URL: https://allbest.ru
2. Код Хаффмана [Электронный ресурс]. – Режим доступа: URL: https://http://opds.spbsut.ru
3. S. W. Golomb. Run-length encodings // IEEE Trans. Inf. Theor. — 1966. — № 3, IT-12. — P. 399—401
4. R. G. Gallager, D. C. Van Voorhis. Optimal source codes for geometrically distributed integer alphabets // IEEE Trans. Inf. Theor. — 1975. — № 2, IT-21. — P. 228—230
5. R. F. Rice, J. R. Plaunt. Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data // IEEE Trans. on Commun. — 1971. — Vol. 16(9). — P. 889—897