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

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

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

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

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

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

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

Результаты кодирования первых 17 чисел:

N		L		M	Результат		Длина, бит	Предполагаемая вероятность
					γ(L)	N2
1	12	1	12	1	1		1	1/2
2	102	2	102	2	01 0	0	4	1/16
3	112	2	102	2	01 0	1	4	1/16
4	1002	3	112	2	01 1	00	5	1/32
5	1012	3	112	2	01 1	01	5	1/32
6	1102	3	112	2	01 1	10	5	1/32
7	1112	3	112	2	01 1	11	5	1/32
8	10002	4	1002	3	001 00	000	8	1/256
9	10012	4	1002	3	001 00	001	8	1/256
10	10102	4	1002	3	001 00	010	8	1/256
11	10112	4	1002	3	001 00	011	8	1/256
12	11002	4	1002	3	001 00	100	8	1/256
13	11012	4	1002	3	001 00	101	8	1/256
14	11102	4	1002	3	001 00	110	8	1/256
15	11112	4	1002	3	001 00	111	8	1/256
16	100002	5	1012	3	001 01	0000	9	1/512
17	100012	5	1012	3	001 01	0001	9	1/512

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

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₂ $= 4 + 1 = 5$.
3. Прочитать из потока следующие $L-1 = 4$ бита → 0001; это даёт $N = 2^{L-1}$ + 0001₂ $= 16 + 1 = 17$.

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

См. также

• Омега-код Элиаса