Дельта-код Элиаса
Дельта-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Кодирование
Алгоритм кодирования числа N:
- Сосчитать [math]\displaystyle{ L }[/math] — количество значащих битов в двоичном представлении числа [math]\displaystyle{ N }[/math].
- Сосчитать [math]\displaystyle{ M }[/math] — количество значащих битов в двоичном представлении числа [math]\displaystyle{ L }[/math].
- Записать [math]\displaystyle{ M - 1 }[/math] нулей и одну единицу.
- Дописать [math]\displaystyle{ L_2 }[/math] — [math]\displaystyle{ M - 1 }[/math] младших битов двоичного представления числа [math]\displaystyle{ L }[/math] без старшей единицы ([math]\displaystyle{ 2^{M-1} }[/math]).
- Дописать [math]\displaystyle{ N_2 }[/math] — [math]\displaystyle{ L - 1 }[/math] младших битов двоичного представления числа [math]\displaystyle{ N }[/math] без старшей единицы ([math]\displaystyle{ 2^{L-1} }[/math]).
Иначе этот алгоритм можно описать так:
- Сосчитать [math]\displaystyle{ L }[/math] — количество значащих битов в двоичном представлении числа [math]\displaystyle{ N }[/math].
- Закодировать [math]\displaystyle{ L }[/math] с помощью гамма-кода Элиаса (γ(L)).
- Дописать двоичное представление числа [math]\displaystyle{ N }[/math] без старшей единицы.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты [math]\displaystyle{ L }[/math] (разрядности числа — количества значащих битов) и мантиссы [math]\displaystyle{ N_2 }[/math] (собственно значащих битов), но в гамма-коде экспонента записывается в унарном виде, а в дельта-коде к ней ещё раз применяется гамма-кодирование.
Пример кодирования числа 10:
- В двоичном представлении числа [math]\displaystyle{ N = 10 = 1010_2 }[/math] 4 значащих бита ([math]\displaystyle{ L = 4 }[/math]).
- В двоичном представлении числа [math]\displaystyle{ L = 4 = 100_2 }[/math] 3 значащих бита ([math]\displaystyle{ M = 3 }[/math]).
- Записываем [math]\displaystyle{ M-1 = 2 }[/math] нуля и одну единицу →
001. - Дописывем биты числа [math]\displaystyle{ L }[/math] без старшей единицы →
00. - Дописывем биты числа [math]\displaystyle{ N }[/math] без старшей единицы →
010. - Результат —
00100010.
Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код):
| N | L | M | Дельта-код | Длина, бит |
Предполагаемая вероятность |
Гамма-код | Длина, бит | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| γ(L) | [math]\displaystyle{ N_2 }[/math] | [math]\displaystyle{ L }[/math] | [math]\displaystyle{ N_2 }[/math] | ||||||||
| 1 | [math]\displaystyle{ 1_2 }[/math] | 1 | [math]\displaystyle{ 1_2 }[/math] | 1 | 1 | 1 | 1/2 | 1 | 1 | ||
| 2 | [math]\displaystyle{ 10_2 }[/math] | 2 | [math]\displaystyle{ 10_2 }[/math] | 2 | 01 0 | 0 | 4 | 1/16 | 01 | 0 | 3 |
| 3 | [math]\displaystyle{ 11_2 }[/math] | 2 | [math]\displaystyle{ 10_2 }[/math] | 2 | 01 0 | 1 | 4 | 1/16 | 01 | 1 | 3 |
| 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | [math]\displaystyle{ 11_2 }[/math] | 2 | 01 1 | 00 | 5 | 1/32 | 001 | 00 | 5 |
| 5 | [math]\displaystyle{ 101_2 }[/math] | 3 | [math]\displaystyle{ 11_2 }[/math] | 2 | 01 1 | 01 | 5 | 1/32 | 001 | 01 | 5 |
| 6 | [math]\displaystyle{ 110_2 }[/math] | 3 | [math]\displaystyle{ 11_2 }[/math] | 2 | 01 1 | 10 | 5 | 1/32 | 001 | 10 | 5 |
| 7 | [math]\displaystyle{ 111_2 }[/math] | 3 | [math]\displaystyle{ 11_2 }[/math] | 2 | 01 1 | 11 | 5 | 1/32 | 001 | 11 | 5 |
| 8 | [math]\displaystyle{ 1000_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 000 | 8 | 1/256 | 0001 | 000 | 7 |
| 9 | [math]\displaystyle{ 1001_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 001 | 8 | 1/256 | 0001 | 001 | 7 |
| 10 | [math]\displaystyle{ 1010_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 010 | 8 | 1/256 | 0001 | 010 | 7 |
| 11 | [math]\displaystyle{ 1011_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 011 | 8 | 1/256 | 0001 | 011 | 7 |
| 12 | [math]\displaystyle{ 1100_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 100 | 8 | 1/256 | 0001 | 100 | 7 |
| 13 | [math]\displaystyle{ 1101_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 101 | 8 | 1/256 | 0001 | 101 | 7 |
| 14 | [math]\displaystyle{ 1110_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 110 | 8 | 1/256 | 0001 | 110 | 7 |
| 15 | [math]\displaystyle{ 1111_2 }[/math] | 4 | [math]\displaystyle{ 100_2 }[/math] | 3 | 001 00 | 111 | 8 | 1/256 | 0001 | 111 | 7 |
| 16 | [math]\displaystyle{ 10000_2 }[/math] | 5 | [math]\displaystyle{ 101_2 }[/math] | 3 | 001 01 | 0000 | 9 | 1/512 | 00001 | 0000 | 9 |
| 17 | [math]\displaystyle{ 10001_2 }[/math] | 5 | [math]\displaystyle{ 101_2 }[/math] | 3 | 001 01 | 0001 | 9 | 1/512 | 00001 | 0001 | 9 |
С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: Гамма-код Элиаса#Обобщение).
Декодирование
Алгоритм декодирования числа из дельта-кода Элиаса:
- Сосчитать [math]\displaystyle{ M }[/math] — количество нулей во входном потоке до первой единицы.
- За единицей следуют [math]\displaystyle{ M }[/math] младших битов числа [math]\displaystyle{ L }[/math], прочитать их и добавить к результату значение [math]\displaystyle{ 2^M }[/math]. Если биты [math]\displaystyle{ L }[/math] во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа [math]\displaystyle{ L }[/math], в этом случае добавлять [math]\displaystyle{ 2^M }[/math] отдельным шагом нет необходимости.
- Следом идут [math]\displaystyle{ L - 1 }[/math] младших битов числа [math]\displaystyle{ N }[/math], прочитать их и добавить к результату значение [math]\displaystyle{ 2^{L-1} }[/math].
Пример декодирования последовательности битов 001010001:
- Прочитать из потока 001 и определить, что в начале 2 ведущих нуля ([math]\displaystyle{ M = 2 }[/math]).
- Прочитать из потока следующие [math]\displaystyle{ M = 2 }[/math] бита → 01; это даёт [math]\displaystyle{ L = 2^M + 01_2 = 4 + 1 = 5 }[/math].
- Прочитать из потока следующие [math]\displaystyle{ L-1 = 4 }[/math] бита → 0001; это даёт [math]\displaystyle{ N = 2^{L-1} + 0001_2 = 16 + 1 = 17 }[/math].
Эффективность
Для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.
См. также
Литература
- Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Раздел 1. Методы сжатия без потерь. Глава 1. Кодирование источников данных без памяти. Разделение мантисс и экспонент // Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2002. — С. 23—24. — 384 с. — ISBN 5-86404-170-x.
- Universal codeword sets and representations of the integers (англ.) // IEEE Transactions on Information Theory[англ.] : journal. — 1975. — March (vol. 21, no. 2). — P. 194—203. — doi:10.1109/tit.1975.1055349.