Дельта-код Элиаса: различия между версиями

Текущая версия от 00:51, 20 августа 2025

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

Кодирование[править | править код]

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

Сосчитать $L$ — количество значащих битов в двоичном представлении числа $N$ .
Сосчитать $M$ — количество значащих битов в двоичном представлении числа $L$ .
Записать $M - 1$ нулей и одну единицу.
Дописать $L_2$ — $M - 1$ младших битов двоичного представления числа $L$ без старшей единицы ( $2^{M-1}$ ).
Дописать $N_2$ — $L - 1$ младших битов двоичного представления числа $N$ без старшей единицы ( $2^{L-1}$ ).

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

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

То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты $L$ (разрядности числа — количества значащих битов) и мантиссы $N_2$ (собственно значащих битов), но в гамма-коде экспонента записывается в унарном виде, а в дельта-коде к ней ещё раз применяется гамма-кодирование.

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

В двоичном представлении числа $N = 10 = 1010_2$ 4 значащих бита ( $L = 4$ ).
В двоичном представлении числа $L = 4 = 100_2$ 3 значащих бита ( $M = 3$ ).
Записываем $M-1 = 2$ нуля и одну единицу → 001.
Дописывем биты числа $L$ без старшей единицы → 00.
Дописывем биты числа $N$ без старшей единицы → 010.
Результат — 00100010.

Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код):

N		L		M	Дельта-код		Длина, бит	Предполагаемая вероятность	Гамма-код		Длина, бит
N		L		M	γ(L)	$N_2$	Длина, бит	Предполагаемая вероятность	$L$	$N_2$	Длина, бит
1	$1_2$	1	$1_2$	1	1		1	1/2	1		1
2	$10_2$	2	$10_2$	2	01 0	0	4	1/16	01	0	3
3	$11_2$	2	$10_2$	2	01 0	1	4	1/16	01	1	3
4	$100_2$	3	$11_2$	2	01 1	00	5	1/32	001	00	5
5	$101_2$	3	$11_2$	2	01 1	01	5	1/32	001	01	5
6	$110_2$	3	$11_2$	2	01 1	10	5	1/32	001	10	5
7	$111_2$	3	$11_2$	2	01 1	11	5	1/32	001	11	5
8	$1000_2$	4	$100_2$	3	001 00	000	8	1/256	0001	000	7
9	$1001_2$	4	$100_2$	3	001 00	001	8	1/256	0001	001	7
10	$1010_2$	4	$100_2$	3	001 00	010	8	1/256	0001	010	7
11	$1011_2$	4	$100_2$	3	001 00	011	8	1/256	0001	011	7
12	$1100_2$	4	$100_2$	3	001 00	100	8	1/256	0001	100	7
13	$1101_2$	4	$100_2$	3	001 00	101	8	1/256	0001	101	7
14	$1110_2$	4	$100_2$	3	001 00	110	8	1/256	0001	110	7
15	$1111_2$	4	$100_2$	3	001 00	111	8	1/256	0001	111	7
16	$10000_2$	5	$101_2$	3	001 01	0000	9	1/512	00001	0000	9
17	$10001_2$	5	$101_2$	3	001 01	0001	9	1/512	00001	0001	9

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

Декодирование[править | править код]

Алгоритм декодирования числа из дельта-кода Элиаса:

Сосчитать $M$ — количество нулей во входном потоке до первой единицы.
За единицей следуют $M$ младших битов числа $L$ , прочитать их и добавить к результату значение $2^M$ . Если биты $L$ во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа $L$ , в этом случае добавлять $2^M$ отдельным шагом нет необходимости.
Следом идут $L - 1$ младших битов числа $N$ , прочитать их и добавить к результату значение $2^{L-1}$ .

Пример декодирования последовательности битов 001010001:

Прочитать из потока 001 и определить, что в начале 2 ведущих нуля ( $M = 2$ ).
Прочитать из потока следующие $M = 2$ бита → 01; это даёт $L = 2^M + 01_2 = 4 + 1 = 5$ .
Прочитать из потока следующие $L-1 = 4$ бита → 0001; это даёт $N = 2^{L-1} + 0001_2 = 16 + 1 = 17$ .

Эффективность[править | править код]

Для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.

См. также[править | править код]

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

Литература[править | править код]

Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Раздел 1. Методы сжатия без потерь. Глава 1. Кодирование источников данных без памяти. Разделение мантисс и экспонент // Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2002. — С. 23—24. — 384 с. — ISBN 5-86404-170-x.
Universal codeword sets and representations of the integers (англ.) // IEEE Transactions on Information Theory^[англ.] : journal. — 1975. — March (vol. 21, no. 2). — P. 194—203. — doi:10.1109/tit.1975.1055349.

@@ Строка 1: / Строка 1: @@
 '''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
+== Кодирование ==
 Алгоритм кодирования числа N:
 # Сосчитать <math>L</math> — количество значащих битов в двоичном представлении числа <math>N</math>.
 # Сосчитать <math>M</math> — количество значащих битов в двоичном представлении числа <math>L</math>.
 # Записать <math>M - 1</math> нулей и одну единицу.
-# Записать L<sub>2</sub> — <math>M - 1</math> младших битов двоичного представления числа <math>L</math> без старшей единицы (<math>2^{M-1}</math>).
+# Дописать <math>L_2</math> — <math>M - 1</math> младших битов двоичного представления числа <math>L</math> без старшей единицы (<math>2^{M-1}</math>).
-# Записать N<sub>2</sub> — <math>L - 1</math> младших битов двоичного представления числа <math>N</math> без старшей единицы (<math>2^{L-1}</math>).
+# Дописать <math>N_2</math> — <math>L - 1</math> младших битов двоичного представления числа <math>N</math> без старшей единицы (<math>2^{L-1}</math>).
 Иначе этот алгоритм можно описать так:
@@ Строка 13: / Строка 14: @@
 # Дописать двоичное представление числа <math>N</math> без старшей единицы.
-То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты (разрядности числа — количества значащих битов) и мантиссы (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
+То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты <math>L</math> (разрядности числа — количества значащих битов) и мантиссы <math>N_2</math> (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
+Пример кодирования числа 10:
+# В двоичном представлении числа <math>N = 10 = 1010_2</math> 4 значащих бита (<math>L = 4</math>).
+# В двоичном представлении числа <math>L = 4 = 100_2</math> 3 значащих бита (<math>M = 3</math>).
+# Записываем <math>M-1 = 2</math> нуля и одну единицу → <code>001</code>.
+# Дописывем биты числа <math>L</math> без старшей единицы → <code>00</code>.
+# Дописывем биты числа <math>N</math> без старшей единицы → <code>010</code>.
+# Результат — <code>00100010</code>.
+Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код):
-Результаты кодирования первых 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 />вероятность
+!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"
-! γ(L) || N<sub>2</sub>
+! γ(L) || <math>N_2</math> || <math>L</math> || <math>N_2</math>
 |-
-| 1 || 1<sub>2</sub> || 1 || 1<sub>2</sub> || 1 || 1 ||align="left"| || 1 || 1/2
+| 1 || <math>1_2</math> || 1 || <math>1_2</math> || 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 || <math>10_2</math> || 2 || <math>10_2</math> || 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 || <math>11_2</math> || 2 || <math>10_2</math> || 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 || <math>100_2</math> || 3 || <math>11_2</math> || 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 || <math>101_2</math> || 3 || <math>11_2</math> || 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 || <math>110_2</math> || 3 || <math>11_2</math> || 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 || <math>111_2</math> || 3 || <math>11_2</math> || 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 || <math>1000_2</math> || 4 || <math>100_2</math> || 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 || <math>1001_2</math> || 4 || <math>100_2</math> || 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 || <math>1010_2</math> || 4 || <math>100_2</math> || 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 || <math>1011_2</math> || 4 || <math>100_2</math> || 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 || <math>1100_2</math> || 4 || <math>100_2</math> || 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 || <math>1101_2</math> || 4 || <math>100_2</math> || 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 || <math>1110_2</math> || 4 || <math>100_2</math> || 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 || <math>1111_2</math> || 4 || <math>100_2</math> || 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 || <math>10000_2</math> || 5 || <math>101_2</math> || 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 || <math>10001_2</math> || 5 || <math>101_2</math> || 3 || 001 01 ||align="left"| 0001 || 9 || 1/512 || 00001 ||align="left"| 0001 || 9
 |}
+С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: [[Гамма-код Элиаса#Обобщение]]).
+== Декодирование ==
 Алгоритм декодирования числа из дельта-кода Элиаса:
 # Сосчитать <math>M</math> — количество нулей во входном потоке до первой единицы.
-# За единицей следуют <math>M</math> младших битов числа <math>L</math>. Прочитать их и добавить к результату <math>2^M</math>. Если число <math>L</math> во входном потоке записано от старших битов к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа <math>L</math>, в этом случае добавлять <math>2^M</math> отдельным шагом нет необходимости.
+# За единицей следуют <math>M</math> младших битов числа <math>L</math>, прочитать их и добавить к результату значение <math>2^M</math>. Если биты <math>L</math> во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа <math>L</math>, в этом случае добавлять <math>2^M</math> отдельным шагом нет необходимости.
-# Следом идут <math>L - 1</math> младших битов числа <math>N</math>. Прочитать их и добавить к результату <math>2^{L-1}</math>.
+# Следом идут <math>L - 1</math> младших битов числа <math>N</math>, прочитать их и добавить к результату значение <math>2^{L-1}</math>.
-Пример декодирования для <tt>001010001</tt>:
+Пример декодирования последовательности битов <tt>001010001</tt>:
 # Прочитать из потока <tt>001</tt> и определить, что в начале 2 ведущих нуля (<math>M = 2</math>).
-# Прочитать из потока следующие <math>M = 2</math> бита → <tt>01</tt>; это даёт <math>L = 2^M +</math> 01<sub>2</sub> <math>= 4 + 1 = 5</math>.
+# Прочитать из потока следующие <math>M = 2</math> бита → <tt>01</tt>; это даёт <math>L = 2^M + 01_2 = 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>.
+# Прочитать из потока следующие <math>L-1 = 4</math> бита → <tt>0001</tt>; это даёт <math>N = 2^{L-1} + 0001_2 = 16 + 1 = 17</math>.
+== Эффективность ==
-С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: [[Гамма-код Элиаса#Обобщение]]).
+Для чисел 2, 3, 8…15 дельта-код длиннее гамма-кода, для чисел 1, 4…7, 16…31 длина дельта-кода совпадает с длиной гамма-кода, для всех остальных чисел дельта-код короче гамма-кода. Соответственно, дельта-код тем менее выгоднее гамма-кода, чем неравномернее распределение вероятностей кодируемых чисел и чем более вероятны их значения при приближении к нулю.
 == См. также ==
 * [[Омега-код Элиаса]]
+== Литература ==
+* {{книга|автор=Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин.|часть=Раздел 1. Методы сжатия без потерь. Глава 1. Кодирование источников данных без памяти. Разделение мантисс и экспонент|заглавие=Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео|место={{М}}|издательство=Диалог-МИФИ|год=2002|страниц=384|страницы=23—24|isbn=5-86404-170-x}}
+* {{статья |author-first=Peter |author-last=Elias |заглавие=Universal codeword sets and representations of the integers |издание={{Нп3|IEEE Transactions on Information Theory}} |том=21 |номер=2 |страницы=194—203 |ссылка=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1055349 |doi=10.1109/tit.1975.1055349 |язык=en |тип=journal |месяц=3 |год=1975}}
 [[Категория:Алгоритмы сжатия без потерь]]
-[[en:Elias delta coding]]
-[[ko:엘리어스 델타 부호]]
-[[ja:デルタ符号]]