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

Материал из in.wiki
Перейти к навигации Перейти к поиску
(орфография)
w>AVB
(стилевые правки, дополнение, оформление)
Строка 1: Строка 1:
 
'''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
 
'''Дельта-код Элиаса ''' — это [[универсальный код]] для кодирования положительных целых чисел, разработанный Питером Элиасом.
  
−
Для того, чтобы закодировать число N:
+
Алгоритм кодирования числа 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"
−
| 1 || 2^0 || 0 || 1 || 1 || 1/2
+
|-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>.
−
# Декодировать 00101, результат — 5.
+
# Прочитать из потока следующие <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.
 
−
# Закодированное число равно 2<sup>4</sup> + 1 = 17.
 
  
 
С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: [[Гамма-код Элиаса#Обобщение]]).
 
С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: [[Гамма-код Элиаса#Обобщение]]).
Строка 71: Строка 72:
 
== См. также ==
 
== См. также ==
 
* [[Омега-код Элиаса]]
 
* [[Омега-код Элиаса]]
−
* [[Гамма-код Элиаса]]
 
  
 
[[Категория:Алгоритмы сжатия без потерь]]
 
[[Категория:Алгоритмы сжатия без потерь]]

Версия от 05:09, 26 октября 2009

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

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

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

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

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

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

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

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

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

  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 + L = 2^M + 012 = 4 + 1 = 5 = 4 + 1 = 5 .
  3. Прочитать из потока следующие L − 1 = 4 L-1 = 4 бита → 0001; это даёт N = 2 L − 1 N = 2^{L-1} + 00012 = 16 + 1 = 17 = 16 + 1 = 17 .

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

См. также

en:Elias delta coding ko:엘리어스 델타 부호 ja:デルタ符号

Источник — https://in.wiki/w/index.php?title=Дельта-код_Элиаса&oldid=1573990