Изменения
Перейти к навигации
Перейти к поиску
Строка 6:
Строка 6: − + − + Строка 16:
Строка 16: − + + + + + + + + + + Строка 64:
Строка 73: − + − + − +
стилевые правки, дополнение
# Сосчитать <math>M</math> — количество значащих битов в двоичном представлении числа <math>L</math>.
# Сосчитать <math>M</math> — количество значащих битов в двоичном представлении числа <math>L</math>.
# Записать <math>M - 1</math> нулей и одну единицу.
# Записать <math>M - 1</math> нулей и одну единицу.
# Записать L<sub>2</sub> — <math>M - 1</math> младших битов двоичного представления числа <math>L</math> без старшей единицы (<math>2^{M-1}</math>).
# Дописать L<sub>2</sub> — <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>).
# Дописать N<sub>2</sub> — <math>L - 1</math> младших битов двоичного представления числа <math>N</math> без старшей единицы (<math>2^{L-1}</math>).
Иначе этот алгоритм можно описать так:
Иначе этот алгоритм можно описать так:
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты L (разрядности числа — количества значащих битов) и мантиссы N<sub>2</sub> (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты L (разрядности числа — количества значащих битов) и мантиссы N<sub>2</sub> (собственно значащих битов), но в гамма-коде экспонента записывается в [[Унарное кодирование|унарном виде]], а в дельта-коде к ней ещё раз применяется гамма-кодирование.
Результаты кодирования первых 17 чисел (для сравнения показан результат гамма-кодирования):
Пример кодирования числа 10:
# В двоичном представлении числа <math>N = 10</math> (1010<sub>2</sub>) 4 значащих бита (<math>L = 4</math>).
# В двоичном представлении числа <math>L = 4</math> (100<sub>2</sub>) 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"
{| class="standard" align="center" style="text-align:right"
Алгоритм декодирования числа из дельта-кода Элиаса:
Алгоритм декодирования числа из дельта-кода Элиаса:
# Сосчитать <math>M</math> — количество нулей во входном потоке до первой единицы.
# Сосчитать <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>).
# Прочитать из потока <tt>001</tt> и определить, что в начале 2 ведущих нуля (<math>M = 2</math>).