Изменения
оформление, дополнение
'''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
'''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
== Кодирование ==
Алгоритм кодирования числа N:
Алгоритм кодирования числа N:
# Сосчитать <math>L</math> — количество значащих битов в двоичном представлении числа <math>N</math>.
# Сосчитать <math>L</math> — количество значащих битов в двоичном представлении числа <math>N</math>.
# Дописать двоичное представление числа <math>N</math> без старшей единицы.
# Дописать двоичное представление числа <math>N</math> без старшей единицы.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты (разрядности числа — количества значащих битов) и мантиссы (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты L (разрядности числа — количества значащих битов) и мантиссы N<sub>2</sub> (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
Результаты кодирования первых 17 чисел (для сравнения показан результат гамма-кодирования):
{| class="standard" align="center" style="text-align:right"
{| class="standard" align="center" style="text-align:right"
|-align="center"
|-align="center"
!colspan="2" rowspan="2"| N ||colspan="2" rowspan="2"| L ||rowspan="2"| M ||colspan="2"| Результат ||rowspan="2"| Длина,<br />бит ||rowspan="2"| Предполагаемая<br />вероятность
!colspan="2" rowspan="2"| N ||colspan="2" rowspan="2"| L ||rowspan="2"| M ||colspan="2"| Дельта-код ||rowspan="2"| Длина,<br />бит ||rowspan="2"| Предполагаемая<br />вероятность ||colspan="2"| Гамма-код ||rowspan="2"| Длина,<br />бит
|-align="center"
|-align="center"
! γ(L) || N<sub>2</sub>
! γ(L) || N<sub>2</sub> || L || N<sub>2</sub>
|-
|-
| 1 || 1<sub>2</sub> || 1 || 1<sub>2</sub> || 1 || 1 ||align="left"| || 1 || 1/2
| 1 || 1<sub>2</sub> || 1 || 1<sub>2</sub> || 1 || 1 ||align="left"| || 1 || 1/2 || 1 ||align="left"| || 1
|-
|-
| 2 || 10<sub>2</sub> || 2 || 10<sub>2</sub> || 2 || 01 0 ||align="left"| 0 || 4 || 1/16
| 2 || 10<sub>2</sub> || 2 || 10<sub>2</sub> || 2 || 01 0 ||align="left"| 0 || 4 || 1/16 || 01 ||align="left"| 0 || 3
|-
|-
| 3 || 11<sub>2</sub> || 2 || 10<sub>2</sub> || 2 || 01 0 ||align="left"| 1 || 4 || 1/16
| 3 || 11<sub>2</sub> || 2 || 10<sub>2</sub> || 2 || 01 0 ||align="left"| 1 || 4 || 1/16 || 01 ||align="left"| 1 || 3
|-
|-
| 4 || 100<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 00 || 5 || 1/32
| 4 || 100<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 00 || 5 || 1/32 || 001 ||align="left"| 00 || 5
|-
|-
| 5 || 101<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 01 || 5 || 1/32
| 5 || 101<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 01 || 5 || 1/32 || 001 ||align="left"| 01 || 5
|-
|-
| 6 || 110<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 10 || 5 || 1/32
| 6 || 110<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 10 || 5 || 1/32 || 001 ||align="left"| 10 || 5
|-
|-
| 7 || 111<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 11 || 5 || 1/32
| 7 || 111<sub>2</sub> || 3 || 11<sub>2</sub> || 2 || 01 1 ||align="left"| 11 || 5 || 1/32 || 001 ||align="left"| 11 || 5
|-
|-
| 8 || 1000<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 000 || 8 || 1/256
| 8 || 1000<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 000 || 8 || 1/256 || 0001 ||align="left"| 000 || 7
|-
|-
| 9 || 1001<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 001 || 8 || 1/256
| 9 || 1001<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 001 || 8 || 1/256 || 0001 ||align="left"| 001 || 7
|-
|-
| 10 || 1010<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 010 || 8 || 1/256
| 10 || 1010<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 010 || 8 || 1/256 || 0001 ||align="left"| 010 || 7
|-
|-
| 11 || 1011<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 011 || 8 || 1/256
| 11 || 1011<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 011 || 8 || 1/256 || 0001 ||align="left"| 011 || 7
|-
|-
| 12 || 1100<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 100 || 8 || 1/256
| 12 || 1100<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 100 || 8 || 1/256 || 0001 ||align="left"| 100 || 7
|-
|-
| 13 || 1101<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 101 || 8 || 1/256
| 13 || 1101<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 101 || 8 || 1/256 || 0001 ||align="left"| 101 || 7
|-
|-
| 14 || 1110<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 110 || 8 || 1/256
| 14 || 1110<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 110 || 8 || 1/256 || 0001 ||align="left"| 110 || 7
|-
|-
| 15 || 1111<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 111 || 8 || 1/256
| 15 || 1111<sub>2</sub> || 4 || 100<sub>2</sub> || 3 || 001 00 ||align="left"| 111 || 8 || 1/256 || 0001 ||align="left"| 111 || 7
|-
|-
| 16 || 10000<sub>2</sub> || 5 || 101<sub>2</sub> || 3 || 001 01 ||align="left"| 0000 || 9 || 1/512
| 16 || 10000<sub>2</sub> || 5 || 101<sub>2</sub> || 3 || 001 01 ||align="left"| 0000 || 9 || 1/512 || 00001 ||align="left"| 0000 || 9
|-
|-
| 17 || 10001<sub>2</sub> || 5 || 101<sub>2</sub> || 3 || 001 01 ||align="left"| 0001 || 9 || 1/512
| 17 || 10001<sub>2</sub> || 5 || 101<sub>2</sub> || 3 || 001 01 ||align="left"| 0001 || 9 || 1/512 || 00001 ||align="left"| 0001 || 9
|}
|}
С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: [[Гамма-код Элиаса#Обобщение]]).
== Декодирование ==
Алгоритм декодирования числа из дельта-кода Элиаса:
Алгоритм декодирования числа из дельта-кода Элиаса:
# Сосчитать <math>M</math> — количество нулей во входном потоке до первой единицы.
# Сосчитать <math>M</math> — количество нулей во входном потоке до первой единицы.
# Прочитать из потока следующие <math>L-1 = 4</math> бита → <tt>0001</tt>; это даёт <math>N = 2^{L-1}</math> + 0001<sub>2</sub> <math>= 16 + 1 = 17</math>.
# Прочитать из потока следующие <math>L-1 = 4</math> бита → <tt>0001</tt>; это даёт <math>N = 2^{L-1}</math> + 0001<sub>2</sub> <math>= 16 + 1 = 17</math>.
== Эффективность ==
Можно видеть, что для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.
== См. также ==
== См. также ==
* [[Омега-код Элиаса]]
* [[Омега-код Элиаса]]
== Литература ==
* {{книга|автор=Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин.|часть=Раздел 1. Методы сжатия без потерь. Глава 1. Кодирование источников данных без памяти. Разделение мантисс и экспонент|заглавие=Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео|место={{М}}|издательство=Диалог-МИФИ|год=2002|страниц=384|страницы=23—24|isbn=5-86404-170-x}}
[[Категория:Алгоритмы сжатия без потерь]]
[[Категория:Алгоритмы сжатия без потерь]]