Меню Главная Случайная статья Настройки Дельта-код Элиаса Материал из https://ru.wikipedia.org Дельта-код Элиаса  — это универсальный код для кодирования положительных целых чисел, разработанный Питером Элиасом. Содержание 1 Кодирование 2 Декодирование 3 Эффективность 4 См. также 5 Литература Кодирование Алгоритм кодирования числа N: Сосчитать ${\displaystyle L}$ — количество значащих битов в двоичном представлении числа ${\displaystyle N}$. Сосчитать ${\displaystyle M}$ — количество значащих битов в двоичном представлении числа ${\displaystyle L}$. Записать ${\displaystyle M-1}$ нулей и одну единицу. Дописать ${\displaystyle L_{2}}$ — ${\displaystyle M-1}$ младших битов двоичного представления числа ${\displaystyle L}$ без старшей единицы (${\displaystyle 2^{M-1}}$). Дописать ${\displaystyle N_{2}}$ — ${\displaystyle L-1}$ младших битов двоичного представления числа ${\displaystyle N}$ без старшей единицы (${\displaystyle 2^{L-1}}$). Иначе этот алгоритм можно описать так: Сосчитать ${\displaystyle L}$ — количество значащих битов в двоичном представлении числа ${\displaystyle N}$. Закодировать ${\displaystyle L}$ с помощью гамма-кода Элиаса ((L)). Дописать двоичное представление числа ${\displaystyle N}$ без старшей единицы. То есть и в дельта-, и в гамма-коде Элиаса число кодируется в виде экспоненты ${\displaystyle L}$ (разрядности числа — количества значащих битов) и мантиссы ${\displaystyle N_{2}}$ (собственно значащих битов), но в гамма-коде экспонента записывается в унарном виде, а в дельта-коде к ней ещё раз применяется гамма-кодирование. Пример кодирования числа 10: В двоичном представлении числа ${\displaystyle N=10=1010_{2}}$ 4 значащих бита (${\displaystyle L=4}$). В двоичном представлении числа ${\displaystyle L=4=100_{2}}$ 3 значащих бита (${\displaystyle M=3}$). Записываем ${\displaystyle M-1=2}$ нуля и одну единицу 001. Дописывем биты числа ${\displaystyle L}$ без старшей единицы 00. Дописывем биты числа ${\displaystyle N}$ без старшей единицы 010. Результат — 00100010. Результаты кодирования первых 17 чисел (для сравнения показан также гамма-код): N L M Дельта-код Длина, бит Предполагаемая вероятность Гамма-код Длина, бит (L) ${\displaystyle N_{2}}$ ${\displaystyle L}$ ${\displaystyle N_{2}}$ 1 ${\displaystyle 1_{2}}$ 1 ${\displaystyle 1_{2}}$ 1 1 1 1/2 1 1 2 ${\displaystyle 10_{2}}$ 2 ${\displaystyle 10_{2}}$ 2 01 0 0 4 1/16 01 0 3 3 ${\displaystyle 11_{2}}$ 2 ${\displaystyle 10_{2}}$ 2 01 0 1 4 1/16 01 1 3 4 ${\displaystyle 100_{2}}$ 3 ${\displaystyle 11_{2}}$ 2 01 1 00 5 1/32 001 00 5 5 ${\displaystyle 101_{2}}$ 3 ${\displaystyle 11_{2}}$ 2 01 1 01 5 1/32 001 01 5 6 ${\displaystyle 110_{2}}$ 3 ${\displaystyle 11_{2}}$ 2 01 1 10 5 1/32 001 10 5 7 ${\displaystyle 111_{2}}$ 3 ${\displaystyle 11_{2}}$ 2 01 1 11 5 1/32 001 11 5 8 ${\displaystyle 1000_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 000 8 1/256 0001 000 7 9 ${\displaystyle 1001_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 001 8 1/256 0001 001 7 10 ${\displaystyle 1010_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 010 8 1/256 0001 010 7 11 ${\displaystyle 1011_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 011 8 1/256 0001 011 7 12 ${\displaystyle 1100_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 100 8 1/256 0001 100 7 13 ${\displaystyle 1101_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 101 8 1/256 0001 101 7 14 ${\displaystyle 1110_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 110 8 1/256 0001 110 7 15 ${\displaystyle 1111_{2}}$ 4 ${\displaystyle 100_{2}}$ 3 001 00 111 8 1/256 0001 111 7 16 ${\displaystyle 10000_{2}}$ 5 ${\displaystyle 101_{2}}$ 3 001 01 0000 9 1/512 00001 0000 9 17 ${\displaystyle 10001_{2}}$ 5 ${\displaystyle 101_{2}}$ 3 001 01 0001 9 1/512 00001 0001 9 С помощью дополнительной обработки исходных значений дельта-код можно использовать также для кодирования нулевых и отрицательных целых чисел (см.: Гамма-код Элиаса#Обобщение). Декодирование Алгоритм декодирования числа из дельта-кода Элиаса: Сосчитать ${\displaystyle M}$ — количество нулей во входном потоке до первой единицы. За единицей следуют ${\displaystyle M}$ младших битов числа ${\displaystyle L}$, прочитать их и добавить к результату значение ${\displaystyle 2^{M}}$. Если биты ${\displaystyle L}$ во входном потоке записаны от старших к младшим, то первую единицу после ведущей серии нулей можно читать как часть двоичного представления числа ${\displaystyle L}$, в этом случае добавлять ${\displaystyle 2^{M}}$ отдельным шагом нет необходимости. Следом идут ${\displaystyle L-1}$ младших битов числа ${\displaystyle N}$, прочитать их и добавить к результату значение ${\displaystyle 2^{L-1}}$. Пример декодирования последовательности битов 001010001: Прочитать из потока 001 и определить, что в начале 2 ведущих нуля (${\displaystyle M=2}$). Прочитать из потока следующие ${\displaystyle M=2}$ бита 01; это даёт ${\displaystyle L=2^{M}+01_{2}=4+1=5}$. Прочитать из потока следующие ${\displaystyle L-1=4}$ бита 0001; это даёт ${\displaystyle 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.