Изменения
← Новая страница: «'''Дельта-код Элиаса ''' — это универсальный код для кодирования положительных цел…»
'''Дельта-код Элиаса ''' — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом.
Для того, чтобы закодировать число:
# Запишите его в двоичном виде.
# Посчитайти биты и запишите количество битов в двоичном виде (Х).
# Используйте двоичное значение, записанное в шаге 1 снова, удалите стоящий впереди бит и запишите оставшиеся биты (Y).
# Присоедините второе двоичное значение (Y) к первому (X).
# Посчитайте биты, написанные в шаге 2 (X), вычтите 1 из этого числа и добавьте в начало много нулей.
Аналогичным образом этот процесс можно описать так:
# Разделите целое число на самую большую степень 2, которую оно содержит (2N ' ), и оставшиеся N' двоичных цифр целого числа.
# Закодируйте N = N' + 1 с помощью Гамма кода Элиаса.
# Добавьте оставшиеся N' двоичных цифр к представлению N.
Начало кодирования:
<source lang="html4strict">
Предполагаемые вероятности
1 = 20 => N' = 0, N = 1 => 1 1/2
2 = 21 + 0 => N' = 1, N = 2 => 0100 1/16
3 = 21 + 1 => N' = 1, N = 2 => 0101 "
4 = 2² + 0 => N' = 2, N = 3 => 01100 1/32
5 = 2² + 1 => N' = 2, N = 3 => 01101 "
6 = 2² + 2 => N' = 2, N = 3 => 01110 "
7 = 2² + 3 => N' = 2, N = 3 => 01111 "
8 = 2³ + 0 => N' = 3, N = 4 => 00100000 1/256
9 = 2³ + 1 => N' = 3, N = 4 => 00100001 "
10 = 2³ + 2 => N' = 3, N = 4 => 00100010 "
11 = 2³ + 3 => N' = 3, N = 4 => 00100011 "
12 = 2³ + 4 => N' = 3, N = 4 => 00100100 "
13 = 2³ + 5 => N' = 3, N = 4 => 00100101 "
14 = 2³ + 6 => N' = 3, N = 4 => 00100110 "
15 = 2³ + 7 => N' = 3, N = 4 => 00100111 "
16 = 24 + 0 => N' = 4, N = 5 => 001010000 1/512
17 = 24 + 1 => N' = 4, N = 5 => 001010001 "
…
</source>
Чтобы декодировать число из Дельта-кода Элиаса:
# Вычитайте и посчитайте ноли из потока, пока не доберетесь до первой единицы. Назовите число нолей L.
# Учитывая, что единица, которая была достигнута – это первая цифра целого числа, значение которого 2L, прочитайте оставшиеся L цифр этого целого числа. Назовите это целое число N.
# Поместите единицу на первое место конечного вывода, который представляет собой значение 2N-1. Вычитайте и добавьте следующие N-1 цифр.
Пример:
001010001
# 2 ведущих ноля в 001.
# вычитайте 2 или более битов, т.e. 00101.
# декодируйте N = 00101 = 5.
# получим N' = 5 - 1 = 4 оставшихся бита для полного кода, т.e. '0001'.
# закодированное число = 24 + 1 = 17.
Этот код может быть также применен к целым числам с нулевым или отрицательным значением таким же способом, которые был описан в статье о [[Гамма код Элиаса |Гамма-коде Элиаса]] .
== Ссылки ==
Оригинал статьи на английском
{{cite web
| url = http://en.wikipedia.org/wiki/Elias_delta_coding
| title = Elias delta coding
}}
Для того, чтобы закодировать число:
# Запишите его в двоичном виде.
# Посчитайти биты и запишите количество битов в двоичном виде (Х).
# Используйте двоичное значение, записанное в шаге 1 снова, удалите стоящий впереди бит и запишите оставшиеся биты (Y).
# Присоедините второе двоичное значение (Y) к первому (X).
# Посчитайте биты, написанные в шаге 2 (X), вычтите 1 из этого числа и добавьте в начало много нулей.
Аналогичным образом этот процесс можно описать так:
# Разделите целое число на самую большую степень 2, которую оно содержит (2N ' ), и оставшиеся N' двоичных цифр целого числа.
# Закодируйте N = N' + 1 с помощью Гамма кода Элиаса.
# Добавьте оставшиеся N' двоичных цифр к представлению N.
Начало кодирования:
<source lang="html4strict">
Предполагаемые вероятности
1 = 20 => N' = 0, N = 1 => 1 1/2
2 = 21 + 0 => N' = 1, N = 2 => 0100 1/16
3 = 21 + 1 => N' = 1, N = 2 => 0101 "
4 = 2² + 0 => N' = 2, N = 3 => 01100 1/32
5 = 2² + 1 => N' = 2, N = 3 => 01101 "
6 = 2² + 2 => N' = 2, N = 3 => 01110 "
7 = 2² + 3 => N' = 2, N = 3 => 01111 "
8 = 2³ + 0 => N' = 3, N = 4 => 00100000 1/256
9 = 2³ + 1 => N' = 3, N = 4 => 00100001 "
10 = 2³ + 2 => N' = 3, N = 4 => 00100010 "
11 = 2³ + 3 => N' = 3, N = 4 => 00100011 "
12 = 2³ + 4 => N' = 3, N = 4 => 00100100 "
13 = 2³ + 5 => N' = 3, N = 4 => 00100101 "
14 = 2³ + 6 => N' = 3, N = 4 => 00100110 "
15 = 2³ + 7 => N' = 3, N = 4 => 00100111 "
16 = 24 + 0 => N' = 4, N = 5 => 001010000 1/512
17 = 24 + 1 => N' = 4, N = 5 => 001010001 "
…
</source>
Чтобы декодировать число из Дельта-кода Элиаса:
# Вычитайте и посчитайте ноли из потока, пока не доберетесь до первой единицы. Назовите число нолей L.
# Учитывая, что единица, которая была достигнута – это первая цифра целого числа, значение которого 2L, прочитайте оставшиеся L цифр этого целого числа. Назовите это целое число N.
# Поместите единицу на первое место конечного вывода, который представляет собой значение 2N-1. Вычитайте и добавьте следующие N-1 цифр.
Пример:
001010001
# 2 ведущих ноля в 001.
# вычитайте 2 или более битов, т.e. 00101.
# декодируйте N = 00101 = 5.
# получим N' = 5 - 1 = 4 оставшихся бита для полного кода, т.e. '0001'.
# закодированное число = 24 + 1 = 17.
Этот код может быть также применен к целым числам с нулевым или отрицательным значением таким же способом, которые был описан в статье о [[Гамма код Элиаса |Гамма-коде Элиаса]] .
== Ссылки ==
Оригинал статьи на английском
{{cite web
| url = http://en.wikipedia.org/wiki/Elias_delta_coding
| title = Elias delta coding
}}