Интернет магазин китайских планшетных компьютеров



Компьютеры - Дельта-код Элиаса

23 января 2011


Оглавление:
1. Дельта-код Элиаса
2. Декодирование
3. Эффективность



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

Кодирование

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

  1. Сосчитать L — количество значащих битов в двоичном представлении числа N.
  2. Сосчитать M — количество значащих битов в двоичном представлении числа L.
  3. Записать M − 1 нулей и одну единицу.
  4. Дописать L2 — M − 1 младших битов двоичного представления числа L без старшей единицы.
  5. Дописать N2 — L − 1 младших битов двоичного представления числа N без старшей единицы.

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

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

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

Пример кодирования числа 10:

  1. В двоичном представлении числа N = 10 = 10102 4 значащих бита.
  2. В двоичном представлении числа L = 4 = 1002 3 значащих бита.
  3. Записываем M − 1 = 2 нуля и одну единицу → 001.
  4. Дописывем биты числа L без старшей единицы → 00.
  5. Дописывем биты числа N без старшей единицы → 010.
  6. Результат — 00100010.

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

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

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



Просмотров: 2505


<<< Гамма-код Элиаса
Дельта-кодирование >>>