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

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

Для того, чтобы закодировать число N:

1. Записать N в двоичном виде.
2. Сосчитать значащие биты в N и записать их количество в двоичном виде (Х)
3. В двоичном представлении N, полученном на шаге 1, удалить старший бит и запомнить результат (Y).
4. К X присоединить Y.
5. Добавить в начало число нулей, на единицу меньшее количества значащих бит в двоичном представлении X.

Аналогичным образом этот процесс можно описать так:

1. Разделить целое число на самую большую степень 2, которую оно содержит (2^N'), и оставшиеся N' двоичных цифр целого числа.
2. Закодировать N = N' + 1 с помощью гамма-кода Элиаса.
3. Добавить оставшиеся N' двоичных цифр к представлению N.

Начало кодирования:

Число	Значение	N'	N	Кодирование	Предполагаемая вероятность
1	2^0	0	1	1	1/2
2	2^1 + 0	1	2	01 0 0	1/16
3	2^1 + 1	1	2	01 0 1	1/16
4	2² + 0	2	3	01 1 00	1/32
5	2² + 1	2	3	01 1 01	1/32
6	2² + 2	2	3	01 1 10	1/32
7	2² + 3	2	3	01 1 11	1/32
8	2³ + 0	3	4	001 00 000	1/256
9	2³ + 1	3	4	001 00 001	1/256
10	2³ + 2	3	4	001 00 010	1/256
11	2³ + 3	3	4	001 00 011	1/256
12	2³ + 4	3	4	001 00 100	1/256
13	2³ + 5	3	4	001 00 101	1/256
14	2³ + 6	3	4	001 00 110	1/256
15	2³ + 7	3	4	001 00 111	1/256
16	2^4 + 0	4	5	001 01 0000	1/512
17	2^4 + 1	4	5	001 01 0001	1/512
…

Чтобы декодировать число из дельта-кода Элиаса:

1. Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей.
2. Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2^L, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число.
3. Поместить единицу на первое место конечного вывода, который представляет собой значение 2^N-1. Прочитать и добавить следующие N-1 цифр.

Пример для 001010001:

1. Прочитать из потока 001 и определить, что в начале 2 ведущих ноля.
2. Прочитать из потока ещё 2 бита; вместе с результатом первого шага получится код 00101.
3. Декодировать 00101, результат — 5.
4. N' = 5-1 = 4 — число бит, которые осталось прочитать. Прочитать 4 бита; результат — 0001=1.
5. Закодированное число равно 2⁴ + 1 = 17.

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

См. также

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