Дельта-код Элиаса

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Кодирование[править | править вики-текст]

Алгоритм кодирования числа N:

  1. Сосчитать L — количество значащих битов в двоичном представлении числа N.
  2. Сосчитать M — количество значащих битов в двоичном представлении числа L.
  3. Записать M - 1 нулей и одну единицу.
  4. Дописать L_2 — M - 1 младших битов двоичного представления числа L без старшей единицы (2^{M-1}).
  5. Дописать N_2 — L - 1 младших битов двоичного представления числа N без старшей единицы (2^{L-1}).

Иначе этот алгоритм можно описать так:

  1. Сосчитать L — количество значащих битов в двоичном представлении числа N.
  2. Закодировать L с помощью гамма-кода Элиаса (γ(L)).
  3. Дописать двоичное представление числа N без старшей единицы.

То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты L (разрядности числа — количества значащих битов) и мантиссы N_2 (собственно значащих битов), но в гамма-коде экспонента записывается в унарном виде, а в дельта-коде к ней ещё раз применяется гамма-кодирование.

Пример кодирования числа 10:

  1. В двоичном представлении числа N = 10 = 1010_2 4 значащих бита (L = 4).
  2. В двоичном представлении числа L = 4 = 100_2 3 значащих бита (M = 3).
  3. Записываем M-1 = 2 нуля и одну единицу → 001.
  4. Дописывем биты числа L без старшей единицы → 00.
  5. Дописывем биты числа N без старшей единицы → 010.
  6. Результат — 00100010.

Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код):

N L M Дельта-код Длина,
бит
Предполагаемая
вероятность
Гамма-код Длина,
бит
γ(L) N_2 L N_2
1 1_2 1 1_2 1 1 1 1/2 1 1
2 10_2 2 10_2 2 01 0 0 4 1/16 01 0 3
3 11_2 2 10_2 2 01 0 1 4 1/16 01 1 3
4 100_2 3 11_2 2 01 1 00 5 1/32 001 00 5
5 101_2 3 11_2 2 01 1 01 5 1/32 001 01 5
6 110_2 3 11_2 2 01 1 10 5 1/32 001 10 5
7 111_2 3 11_2 2 01 1 11 5 1/32 001 11 5
8 1000_2 4 100_2 3 001 00 000 8 1/256 0001 000 7
9 1001_2 4 100_2 3 001 00 001 8 1/256 0001 001 7
10 1010_2 4 100_2 3 001 00 010 8 1/256 0001 010 7
11 1011_2 4 100_2 3 001 00 011 8 1/256 0001 011 7
12 1100_2 4 100_2 3 001 00 100 8 1/256 0001 100 7
13 1101_2 4 100_2 3 001 00 101 8 1/256 0001 101 7
14 1110_2 4 100_2 3 001 00 110 8 1/256 0001 110 7
15 1111_2 4 100_2 3 001 00 111 8 1/256 0001 111 7
16 10000_2 5 101_2 3 001 01 0000 9 1/512 00001 0000 9
17 10001_2 5 101_2 3 001 01 0001 9 1/512 00001 0001 9

С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: Гамма-код Элиаса#Обобщение).

Декодирование[править | править вики-текст]

Алгоритм декодирования числа из дельта-кода Элиаса:

  1. Сосчитать M — количество нулей во входном потоке до первой единицы.
  2. За единицей следуют M младших битов числа L, прочитать их и добавить к результату значение 2^M. Если биты L во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа L, в этом случае добавлять 2^M отдельным шагом нет необходимости.
  3. Следом идут L - 1 младших битов числа N, прочитать их и добавить к результату значение 2^{L-1}.

Пример декодирования последовательности битов 001010001:

  1. Прочитать из потока 001 и определить, что в начале 2 ведущих нуля (M = 2).
  2. Прочитать из потока следующие M = 2 бита → 01; это даёт L = 2^M + 01_2 = 4 + 1 = 5.
  3. Прочитать из потока следующие L-1 = 4 бита → 0001; это даёт N = 2^{L-1} + 0001_2 = 16 + 1 = 17.

Эффективность[править | править вики-текст]

Можно видеть, что для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Раздел 1. Методы сжатия без потерь. Глава 1. Кодирование источников данных без памяти. Разделение мантисс и экспонент // Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2002. — С. 23—24. — 384 с. — ISBN 5-86404-170-x