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

Материал из in.wiki
Перейти к навигации Перейти к поиску
w>AVB
(оформление списка таблицей)
Строка 5: Строка 5:
 
# Сосчитать значащие биты в N и записать их количество в двоичном виде (Х)
 
# Сосчитать значащие биты в N и записать их количество в двоичном виде (Х)
 
# В двоичном представлении N, полученном на шаге 1, удалить старший бит и запомнить результат (Y).
 
# В двоичном представлении N, полученном на шаге 1, удалить старший бит и запомнить результат (Y).
−
# К X присоединить Y.  
+
# К X присоединить Y.
 
# Добавить в начало число нулей, на единицу меньшее количества значащих бит в двоичном представлении X.
 
# Добавить в начало число нулей, на единицу меньшее количества значащих бит в двоичном представлении X.
  
Строка 14: Строка 14:
  
 
Начало кодирования:
 
Начало кодирования:
−
<source lang="html4strict">
+
{| class="standard" style="text-align:right"
−
                                        Предполагаемые вероятности
+
! Число || Значение || N' || N || Кодирование || Предполагаемая<br />вероятность
−
1 = 20 => N' = 0, N = 1 => 1             1/2
+
|-
−
2 = 21 + 0 => N' = 1, N = 2 => 0100      1/16
+
| 1 || 20 || 0 || 1 || 1 || 1/2
−
3 = 21 + 1 => N' = 1, N = 2 => 0101      "
+
|-
−
4 = 2² + 0 => N' = 2, N = 3 => 01100    1/32
+
| 2 || 21 + 0 || 1 || 2 || 01 0 0 || 1/16
−
5 = 2² + 1 => N' = 2, N = 3 => 01101      "
+
|-
−
6 = 2² + 2 => N' = 2, N = 3 => 01110      "
+
| 3 || 21 + 1 || 1 || 2 || 01 0 1 || 1/16
−
7 = 2² + 3 => N' = 2, N = 3 => 01111      "
+
|-
−
8 = 2³ + 0 => N' = 3, N = 4 => 00100000  1/256
+
| 4 || 2² + 0 || 2 || 3 || 01 1 00 || 1/32
−
9 = 2³ + 1 => N' = 3, N = 4 => 00100001  "
+
|-
−
10 = 2³ + 2 => N' = 3, N = 4 => 00100010  "
+
| 5 || 2² + 1 || 2 || 3 || 01 1 01 || 1/32
−
11 = 2³ + 3 => N' = 3, N = 4 => 00100011  "
+
|-
−
12 = 2³ + 4 => N' = 3, N = 4 => 00100100  "
+
| 6 || 2² + 2 || 2 || 3 || 01 1 10 || 1/32
−
13 = 2³ + 5 => N' = 3, N = 4 => 00100101  "
+
|-
−
14 = 2³ + 6 => N' = 3, N = 4 => 00100110  "
+
| 7 || 2² + 3 || 2 || 3 || 01 1 11 || 1/32
−
15 = 2³ + 7 => N' = 3, N = 4 => 00100111  "
+
|-
−
16 = 24 + 0 => N' = 4, N = 5 => 001010000 1/512
+
| 8 || 2³ + 0 || 3 || 4 || 001 00 000 || 1/256
−
17 = 24 + 1 => N' = 4, N = 5 => 001010001  "
+
|-
−
…
+
| 9 || 2³ + 1 || 3 || 4 || 001 00 001 || 1/256
−
</source>
+
|-
 +
|10 || 2³ + 2 || 3 || 4 || 001 00 010 || 1/256
 +
|-
 +
|11 || 2³ + 3 || 3 || 4 || 001 00 011 || 1/256
 +
|-
 +
|12 || 2³ + 4 || 3 || 4 || 001 00 100 || 1/256
 +
|-
 +
|13 || 2³ + 5 || 3 || 4 || 001 00 101 || 1/256
 +
|-
 +
|14 || 2³ + 6 || 3 || 4 || 001 00 110 || 1/256
 +
|-
 +
|15 || 2³ + 7 || 3 || 4 || 001 00 111 || 1/256
 +
|-
 +
|16 || 24 + 0 || 4 || 5 || 001 01 0000 || 1/512
 +
|-
 +
|17 || 24 + 1 || 4 || 5 || 001 01 0001 || 1/512
 +
|-
 +
|… || || || || ||
 +
|}
  
−
Чтобы декодировать число из Дельта-кода Элиаса:
+
Чтобы декодировать число из дельта-кода Элиаса:
 
# Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей.
 
# Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей.
 
# Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2<sup>L</sup>, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число.
 
# Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2<sup>L</sup>, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число.
 
# Поместить единицу на первое место конечного вывода, который представляет собой значение 2<sup>N</sup>-1. Прочитать и добавить следующие N-1 цифр.
 
# Поместить единицу на первое место конечного вывода, который представляет собой значение 2<sup>N</sup>-1. Прочитать и добавить следующие N-1 цифр.
  
−
Пример:
+
Пример для 001010001:
−
 
 
−
001010001
 
  
 
# Читаем из потока 001 и определяем, что в начале кода 2 ведущих ноля.
 
# Читаем из потока 001 и определяем, что в начале кода 2 ведущих ноля.
 
# Читаем из потока еще 2 бита, то есть вместе с результатом первого шага получаем код 00101.
 
# Читаем из потока еще 2 бита, то есть вместе с результатом первого шага получаем код 00101.
−
# Декодируем 00101 = 5.
+
# Декодируем 00101 = 5.
−
# Вычисляем N' = 5 — 1 = 4 - число оставшихся бит для завершения чтения полного кода. Читаем 4 бита и получаем 0001=1.
+
# Вычисляем N' = 5-1 = 4 — число оставшихся бит для завершения чтения полного кода. Читаем 4 бита и получаем 0001=1.
 
# Закодированное число = 2<sup>4</sup> + 1 = 17.
 
# Закодированное число = 2<sup>4</sup> + 1 = 17.
  

Версия от 23:00, 21 мая 2009

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

Для того, чтобы закодировать число N:

  1. Записать N в двоичном виде.
  2. Сосчитать значащие биты в N и записать их количество в двоичном виде (Х)
  3. В двоичном представлении N, полученном на шаге 1, удалить старший бит и запомнить результат (Y).
  4. К X присоединить Y.
  5. Добавить в начало число нулей, на единицу меньшее количества значащих бит в двоичном представлении X.

Аналогичным образом этот процесс можно описать так:

  1. Разделить целое число на самую большую степень 2, которую оно содержит (2N'), и оставшиеся N' двоичных цифр целого числа.
  2. Закодировать N = N' + 1 с помощью гамма-кода Элиаса.
  3. Добавить оставшиеся N' двоичных цифр к представлению N.

Начало кодирования:

Число Значение N' N Кодирование Предполагаемая
вероятность
1 20 0 1 1 1/2
2 21 + 0 1 2 01 0 0 1/16
3 21 + 1 1 2 01 0 1 1/16
4 2² + 0 2 3 01 1 00 1/32
5 2² + 1 2 3 01 1 01 1/32
6 2² + 2 2 3 01 1 10 1/32
7 2² + 3 2 3 01 1 11 1/32
8 2³ + 0 3 4 001 00 000 1/256
9 2³ + 1 3 4 001 00 001 1/256
10 2³ + 2 3 4 001 00 010 1/256
11 2³ + 3 3 4 001 00 011 1/256
12 2³ + 4 3 4 001 00 100 1/256
13 2³ + 5 3 4 001 00 101 1/256
14 2³ + 6 3 4 001 00 110 1/256
15 2³ + 7 3 4 001 00 111 1/256
16 24 + 0 4 5 001 01 0000 1/512
17 24 + 1 4 5 001 01 0001 1/512
…

Чтобы декодировать число из дельта-кода Элиаса:

  1. Прочитать и сосчитать количество нулей из потока, пока не встретится 1. Пусть L — количество нулей.
  2. Учитывая, что единица, которая была достигнута — это первая цифра целого числа, значение которого 2L, прочитать оставшиеся L цифр этого целого числа. Пусть N — прочитанное число.
  3. Поместить единицу на первое место конечного вывода, который представляет собой значение 2N-1. Прочитать и добавить следующие N-1 цифр.

Пример для 001010001:

  1. Читаем из потока 001 и определяем, что в начале кода 2 ведущих ноля.
  2. Читаем из потока еще 2 бита, то есть вместе с результатом первого шага получаем код 00101.
  3. Декодируем 00101 = 5.
  4. Вычисляем N' = 5-1 = 4 — число оставшихся бит для завершения чтения полного кода. Читаем 4 бита и получаем 0001=1.
  5. Закодированное число = 24 + 1 = 17.

При некотором старании этот код может быть также применён к целым числам с нулевыми или отрицательными значениями (см.: гамма-код Элиаса).

См. также

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

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