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

Материал из in.wiki
Версия от 23:00, 21 мая 2009; w>AVB (оформление списка таблицей)
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Число Значение N' N Кодирование Предполагаемая
вероятность
1 20 0 1 1 1/2
2 21 + 0 1 2 01 0 0 1/16
3 21 + 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 24 + 0 4 5 001 01 0000 1/512
17 24 + 1 4 5 001 01 0001 1/512

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

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

Пример для 001010001:

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

При некотором старании этот код может быть также применён к целым числам с нулевыми или отрицательными значениями (см.: гамма-код Элиаса).

См. также

en:Elias delta coding ko:엘리어스 델타 부호 ja:デルタ符号