Русская Википедия:Дельта-код Элиаса
Дельта-код Элиаса — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Кодирование
Алгоритм кодирования числа N:
- Сосчитать <math>L</math> — количество значащих битов в двоичном представлении числа <math>N</math>.
- Сосчитать <math>M</math> — количество значащих битов в двоичном представлении числа <math>L</math>.
- Записать <math>M - 1</math> нулей и одну единицу.
- Дописать <math>L_2</math> — <math>M - 1</math> младших битов двоичного представления числа <math>L</math> без старшей единицы (<math>2^{M-1}</math>).
- Дописать <math>N_2</math> — <math>L - 1</math> младших битов двоичного представления числа <math>N</math> без старшей единицы (<math>2^{L-1}</math>).
Иначе этот алгоритм можно описать так:
- Сосчитать <math>L</math> — количество значащих битов в двоичном представлении числа <math>N</math>.
- Закодировать <math>L</math> с помощью гамма-кода Элиаса (γ(L)).
- Дописать двоичное представление числа <math>N</math> без старшей единицы.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты <math>L</math> (разрядности числа — количества значащих битов) и мантиссы <math>N_2</math> (собственно значащих битов), но в гамма-коде экспонента записывается в унарном виде, а в дельта-коде к ней ещё раз применяется гамма-кодирование.
Пример кодирования числа 10:
- В двоичном представлении числа <math>N = 10 = 1010_2</math> 4 значащих бита (<math>L = 4</math>).
- В двоичном представлении числа <math>L = 4 = 100_2</math> 3 значащих бита (<math>M = 3</math>).
- Записываем <math>M-1 = 2</math> нуля и одну единицу →
001. - Дописывем биты числа <math>L</math> без старшей единицы →
00. - Дописывем биты числа <math>N</math> без старшей единицы →
010. - Результат —
00100010.
Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код):
| N | L | M | Дельта-код | Длина, бит |
Предполагаемая вероятность |
Гамма-код | Длина, бит | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| γ(L) | <math>N_2</math> | <math>L</math> | <math>N_2</math> | ||||||||
| 1 | <math>1_2</math> | 1 | <math>1_2</math> | 1 | 1 | 1 | 1/2 | 1 | 1 | ||
| 2 | <math>10_2</math> | 2 | <math>10_2</math> | 2 | 01 0 | 0 | 4 | 1/16 | 01 | 0 | 3 |
| 3 | <math>11_2</math> | 2 | <math>10_2</math> | 2 | 01 0 | 1 | 4 | 1/16 | 01 | 1 | 3 |
| 4 | <math>100_2</math> | 3 | <math>11_2</math> | 2 | 01 1 | 00 | 5 | 1/32 | 001 | 00 | 5 |
| 5 | <math>101_2</math> | 3 | <math>11_2</math> | 2 | 01 1 | 01 | 5 | 1/32 | 001 | 01 | 5 |
| 6 | <math>110_2</math> | 3 | <math>11_2</math> | 2 | 01 1 | 10 | 5 | 1/32 | 001 | 10 | 5 |
| 7 | <math>111_2</math> | 3 | <math>11_2</math> | 2 | 01 1 | 11 | 5 | 1/32 | 001 | 11 | 5 |
| 8 | <math>1000_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 000 | 8 | 1/256 | 0001 | 000 | 7 |
| 9 | <math>1001_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 001 | 8 | 1/256 | 0001 | 001 | 7 |
| 10 | <math>1010_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 010 | 8 | 1/256 | 0001 | 010 | 7 |
| 11 | <math>1011_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 011 | 8 | 1/256 | 0001 | 011 | 7 |
| 12 | <math>1100_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 100 | 8 | 1/256 | 0001 | 100 | 7 |
| 13 | <math>1101_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 101 | 8 | 1/256 | 0001 | 101 | 7 |
| 14 | <math>1110_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 110 | 8 | 1/256 | 0001 | 110 | 7 |
| 15 | <math>1111_2</math> | 4 | <math>100_2</math> | 3 | 001 00 | 111 | 8 | 1/256 | 0001 | 111 | 7 |
| 16 | <math>10000_2</math> | 5 | <math>101_2</math> | 3 | 001 01 | 0000 | 9 | 1/512 | 00001 | 0000 | 9 |
| 17 | <math>10001_2</math> | 5 | <math>101_2</math> | 3 | 001 01 | 0001 | 9 | 1/512 | 00001 | 0001 | 9 |
С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: Гамма-код Элиаса#Обобщение).
Декодирование
Алгоритм декодирования числа из дельта-кода Элиаса:
- Сосчитать <math>M</math> — количество нулей во входном потоке до первой единицы.
- За единицей следуют <math>M</math> младших битов числа <math>L</math>, прочитать их и добавить к результату значение <math>2^M</math>. Если биты <math>L</math> во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа <math>L</math>, в этом случае добавлять <math>2^M</math> отдельным шагом нет необходимости.
- Следом идут <math>L - 1</math> младших битов числа <math>N</math>, прочитать их и добавить к результату значение <math>2^{L-1}</math>.
Пример декодирования последовательности битов 001010001:
- Прочитать из потока 001 и определить, что в начале 2 ведущих нуля (<math>M = 2</math>).
- Прочитать из потока следующие <math>M = 2</math> бита → 01; это даёт <math>L = 2^M + 01_2 = 4 + 1 = 5</math>.
- Прочитать из потока следующие <math>L-1 = 4</math> бита → 0001; это даёт <math>N = 2^{L-1} + 0001_2 = 16 + 1 = 17</math>.
Эффективность
Для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.
См. также
Литература
