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