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

Материал из in.wiki
Перейти к навигации Перейти к поиску
w>AVB
(оформление списка таблицей)
м (22 версии импортировано: Импорт из Википедии)
 
(не показано 11 промежуточных версий 7 участников)
Строка 1: Строка 1:
 
'''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
 
'''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
  
−
Для того, чтобы закодировать число N:
+
== Кодирование ==
−
# Записать N в двоичном виде.
+
Алгоритм кодирования числа N:
−
# Сосчитать значащие биты в N и записать их количество в двоичном виде (Х)
+
# Сосчитать <math>L</math> — количество значащих битов в двоичном представлении числа <math>N</math>.
−
# В двоичном представлении N, полученном на шаге 1, удалить старший бит и запомнить результат (Y).
+
# Сосчитать <math>M</math> — количество значащих битов в двоичном представлении числа <math>L</math>.
−
# К X присоединить Y.
+
# Записать <math>M - 1</math> нулей и одну единицу.
−
# Добавить в начало число нулей, на единицу меньшее количества значащих бит в двоичном представлении X.
+
# Дописать <math>L_2</math> — <math>M - 1</math> младших битов двоичного представления числа <math>L</math> без старшей единицы (<math>2^{M-1}</math>).
 +
# Дописать <math>N_2</math> — <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> без старшей единицы.
  
−
Начало кодирования:
+
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты <math>L</math> (разрядности числа — количества значащих битов) и мантиссы <math>N_2</math> (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
−
{| class="standard" style="text-align:right"
+
 
−
! Число || Значение || N' || N || Кодирование || Предполагаемая<br />вероятность
+
Пример кодирования числа 10:
−
|-
+
 
−
| 1 || 20 || 0 || 1 || 1 || 1/2
+
# В двоичном представлении числа <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 чисел (для сравнения показан также гамма-код):
 +
 
 +
{| 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"| Длина,<br />бит
 +
|-align="center"
 +
! γ(L) || <math>N_2</math> || <math>L</math> || <math>N_2</math>
 
|-
 
|-
−
| 2 || 21 + 0 || 1 || 2 || 01 0 0 || 1/16
+
| 1 || <math>1_2</math> || 1 || <math>1_2</math> || 1 || 1 ||align="left"| || 1 || 1/2 || 1 ||align="left"| || 1
 
|-
 
|-
−
| 3 || 21 + 1 || 1 || 2 || 01 0 1 || 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
 
|-
 
|-
−
| 4 || 2² + 0 || 2 || 3 || 01 1 00 || 1/32
+
| 3 || <math>11_2</math> || 2 || <math>10_2</math> || 2 || 01 0 ||align="left"| 1 || 4 || 1/16 || 01 ||align="left"| 1 || 3
 
|-
 
|-
−
| 5 || 2² + 1 || 2 || 3 || 01 1 01 || 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
 
|-
 
|-
−
| 6 || 2² + 2 || 2 || 3 || 01 1 10 || 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
 
|-
 
|-
−
| 7 || 2² + 3 || 2 || 3 || 01 1 11 || 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
 
|-
 
|-
−
| 8 || 2³ + 0 || 3 || 4 || 001 00 000 || 1/256
+
| 7 || <math>111_2</math> || 3 || <math>11_2</math> || 2 || 01 1 ||align="left"| 11 || 5 || 1/32 || 001 ||align="left"| 11 || 5
 
|-
 
|-
−
| 9 || 2³ + 1 || 3 || 4 || 001 00 001 || 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
 
|-
 
|-
−
|10 || 2³ + 2 || 3 || 4 || 001 00 010 || 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
 
|-
 
|-
−
|11 || 2³ + 3 || 3 || 4 || 001 00 011 || 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
 
|-
 
|-
−
|12 || 2³ + 4 || 3 || 4 || 001 00 100 || 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
 
|-
 
|-
−
|13 || 2³ + 5 || 3 || 4 || 001 00 101 || 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
 
|-
 
|-
−
|14 || 2³ + 6 || 3 || 4 || 001 00 110 || 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
 
|-
 
|-
−
|15 || 2³ + 7 || 3 || 4 || 001 00 111 || 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
 
|-
 
|-
−
|16 || 24 + 0 || 4 || 5 || 001 01 0000 || 1/512
+
| 15 || <math>1111_2</math> || 4 || <math>100_2</math> || 3 || 001 00 ||align="left"| 111 || 8 || 1/256 || 0001 ||align="left"| 111 || 7
 
|-
 
|-
−
|17 || 24 + 1 || 4 || 5 || 001 01 0001 || 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 || <math>10001_2</math> || 5 || <math>101_2</math> || 3 || 001 01 ||align="left"| 0001 || 9 || 1/512 || 00001 ||align="left"| 0001 || 9
 
|}
 
|}
  
−
Чтобы декодировать число из дельта-кода Элиаса:
+
С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: [[Гамма-код Элиаса#Обобщение]]).
−
# Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей.
+
 
−
# Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2<sup>L</sup>, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число.
+
== Декодирование ==
−
# Поместить единицу на первое место конечного вывода, который представляет собой значение 2<sup>N</sup>-1. Прочитать и добавить следующие N-1 цифр.
+
Алгоритм декодирования числа из дельта-кода Элиаса:
 +
# Сосчитать <math>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>.
 +
 
 +
Пример декодирования последовательности битов <tt>001010001</tt>:
  
−
Пример для 001010001:
+
# Прочитать из потока <tt>001</tt> и определить, что в начале 2 ведущих нуля (<math>M = 2</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} + 0001_2 = 16 + 1 = 17</math>.
  
−
# Читаем из потока 001 и определяем, что в начале кода 2 ведущих ноля.
+
== Эффективность ==
−
# Читаем из потока еще 2 бита, то есть вместе с результатом первого шага получаем код 00101.
 
−
# Декодируем 00101 = 5.
 
−
# Вычисляем N' = 5-1 = 4 — число оставшихся бит для завершения чтения полного кода. Читаем 4 бита и получаем 0001=1.
 
−
# Закодированное число = 2<sup>4</sup> + 1 = 17.
 
  
−
При некотором старании этот код может быть также применён к целым числам с нулевыми или отрицательными значениями (см.: [[гамма-код Элиаса]]).
+
Для чисел 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:デルタ符号]]
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Прочитать из потока 001 и определить, что в начале 2 ведущих нуля ( M = 2 M = 2 ).
  2. Прочитать из потока следующие M = 2 M = 2 бита → 01; это даёт L = 2 M + 01 2 = 4 + 1 = 5 L = 2^M + 01_2 = 4 + 1 = 5 .
  3. Прочитать из потока следующие L − 1 = 4 L-1 = 4 бита → 0001; это даёт N = 2 L − 1 + 0001 2 = 16 + 1 = 17 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.
Источник — https://in.wiki/w/index.php?title=Дельта-код_Элиаса&oldid=1573999