Гамма-, дельта- и омега-код Элиаса

Коды без памяти

Простейшими кодами, на основе которых может выполняться сжатие данных, являются коды без памяти. В коде без памяти каждый символ в кодируемом векторе данных заменяется кодовым словом из префиксного множества двоичных последовательностей или слов.

К примеру, множество двоичных слов [math]S_1[/math] = [math] \{00, 01, 100, 110, 1010, 1011\} [/math] является префиксным множеством двоичных последовательностей, поскольку, если проверить любую из 30 возможных совместных комбинаций ([math]w_i[/math], [math]w_j[/math]) из [math]S_1[/math], то видно, что [math]w_i[/math] никогда не явится префиксом (или началом) [math]w_j[/math]. С другой стороны, множество [math]S_2[/math] = [math] \{00, 001, 1110\} [/math] не является префиксным множеством двоичных последовательностей, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества — 001. Соответственно, множество [math]S_1[/math] может быть множеством кодовых слов для вектора данных в коде без памяти, а [math]S_2[/math] — нет.

Разделение мантисс и экспонент

Английское название метода - Separate Exponents and Mantissas (SEM).

Цель — сжатие потока R-битовых элементов.

Основная идея состоит в том, чтобы отдельно описывать порядок значения элемента ("экспоненту" [math]E_i[/math]) и отдельно — значащие цифры значения ("мантиссу" [math]M_i[/math]).

Значащие цифры начинаются со старшей ненулевой цифры: например, в числе [math]000001101_2[/math] = [math]1\times2^0+0\times2^1+1\times2^2+1\times2^3+0\times2^4+0\times...[/math] = 13 это последние 4 цифры. Порядок числа определяется позицией старшей ненулевой цифры в записи числа. Как и при обычной записи в десятичной системе, он равен числу цифр в записи числа без предшествующих незначащих нулей. В данном примере порядок равен четырем.

Методы данной группы являются трансформирующими и поточными, то есть могут применяться даже в том случае, когда объем входных данных заранее не известен. В общем случае скорость работы компрессора (содержащего прямое, «сжимающее» преобразование) равна скорости декомпрессора (реализующего обратное, «разжимающее» преобразование) и зависит только от объема исходных данных. Памяти потребуется всего несколько байтов.

В самом простом случае под запись экспонент и мантисс отводится фиксированное число битов: Е и М. Причем [math]E \geqslant 1[/math], [math]M \geqslant 1[/math], E + M = R, где R — число битов в записи исходного числа.

Этот первый из четырех вариантов метода условно обозначим

1. Fixed + Fixed (Фиксированная длина экспоненты — Фиксированная длина мантиссы), а остальные три:

2. Fixed + Variable (Фиксированная длина экспоненты — Переменная длина мантиссы),

3. Variable + Variable (Переменная длина экспоненты — Переменная длина мантиссы) и

4. Variable + Fixed (Переменная длина экспоненты — Фиксированная длина мантиссы).

Есть несколько путей еще большего увеличения степени сжатия. Например, применение хорошо исследованных схем кодирования (Элиаса, Раиса, Голомба, Фибоначчи).

Коды переменной длины (Variable + Variable)

Определение:

Унарное представление числа n — n подряд идущих единиц, заканчивающихся контрольным нулем (иногда наоборот: n нулей, за которыми следует контрольная единица). Более наглядно унарные коды можно представить в виде двоичного дерева, которое устроено следующим образом: каждому ребру, ведущему из вершины к правому ребенку, соответствует единица, иначе ноль, причем левый ребенок уже не имеет детей. Например, если нужно закодировать число m, нужно m раз пройти по правым вершинам и затем остановиться на левой.

Например, унарный код нуля — 0, единицы — 10, двойки — 110 и т. д.

Гамма-код Элиаса

Определение:

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

Алгоритм построения гамма-кода Элиаса

Способ первый:

1. Записать число в двоичном представлении;

2. Перед двоичным представлением дописать нули, количество нулей на единицу меньше количества битов двоичного представления числа.

Способ второй:

1. Выделить из целого числа старший значащий бит (самую большую степень 2, которую число включает — 2N) и младшие N бит;

2. Записать N в унарном коде, то есть N нулей, за которыми следует единица;

3. Дописать N младших двоичных цифр числа следом за этим унарным кодом.

Декодирование

1. Считать все нули, встречающиеся до первой 1. Пусть N — количество этих нулей;

2. Принимая во внимание единицу, которая станет первым битом целого числа, со значением 2^N, считать оставшиеся N цифр целого числа.

Примеры

Пример кодирования числа 15

1. Записать число 15 в двоичном представлении [math]1111_2[/math];

2. Дописать перед числом три нуля 0001111.

Пример декодирования последовательности битов 000010001

1. Считываем нули до первой единицы, N = 4;

2. Считываем единицу и N = 4 бит. Получаем [math]2^4[/math] + [math]0001_2[/math] = 17.

Приведем примеры нескольких первых гамма-кодов Элиаса:

Число	Гамма-код
1	1
2	010
3	011
4	00100
5	00101
6	00110
7	00111
8	0001000

Гамма-код Элиаса не подходит для кодирования нулевых значений или отрицательных чисел. Для того, чтобы закодировать ноль нужно прибавить к нему 1 до кодирования и отнять после декодирования. Чтобы закодировать все целые числа можно установить биекцию (соответствие), отображая целые числа из (0, 1, −1, 2, −2, 3, −3, …) в (1, 2, 3, 4, 5, 6, 7, …).

Дельта-код Элиаса

Определение:

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

Алгоритм построения дельта-кода Элиаса

Способ первый:

1. Сосчитать L — количество значащих битов в двоичном представлении числа N;

2. Сосчитать M — количество значащих битов в двоичном представлении числа L;

3. Записать M — 1 нулей и одну единицу;

4. С правой стороны дописать биты числа L без старшей единицы;

5. С правой стороны дописать биты числа N без старшей единицы ([math]N_2[/math]).

Способ второй:

1. Сосчитать L — количество значащих битов в двоичном представлении числа N;

2. Закодировать L с помощью гамма-кода Элиаса;

3. Дописать к L справа двоичное представление числа N без старшей единицы.

Декодирование

1. Сосчитать M — количество нулей во входном потоке до первой единицы;

2. Не включая единицу считать M битов. Считанное число в сумме с [math]2^M[/math] дает L;

3. Далее идут L — 1 младших битов числа N. Считать их и к считанному числу прибавить [math]2^{L-1}[/math].

Примеры

Пример кодирования числа 10

1. В двоичном представлении числа N = 10 = [math]1010_2[/math] 4 значащих бита (L = 4);

2. В двоичном представлении числа L = 4 = [math]100_2[/math] 3 значащих бита (M = 3);

3. Пишем M — 1 ноль и одну единицу 001;

4. Дописываем справа биты числа L без старшей единицы 00100;

5. Дописываем с правой стороны биты числа N без старшей единицы 00100010.

Пример декодирования последовательности битов 00100010

1. Считаем количество нулей до первой единицы во входном потоке (M = 2);

2. Читаем из потока следующие M бит (00). Это дает нам L = [math]2^M[/math] + [math]00_2[/math] = 4;

3. Читаем из потока следующие L — 1 бит (010). N = [math]2^{L- 1}[/math] + [math]010_2[/math] = 10.

Приведем примеры нескольких первых дельта-кодов Элиаса:

Число	Дельта-код
1	1
2	0100
3	0101
4	01100
5	01101
6	01110
7	01111
8	00100000
9	00100001

Сравнение гамма- и дельта-кодов Элиаса

Диапазон	Гамма-коды	Длина кода, бит	Дельта-коды	Длина кода, бит
1	1	1	1	1
2...3	01x	3	010x	4
4...7	001xx	5	011xx	5
8...15	0001xxx	7	00100xxx	8
16...31	00001xxxx	9	00101xxxx	9
32...63	000001xxxxx	11	00110xxxxx	10
64...127	0000001xxxxxx	13	00111xxxxxx	11
128...255	00000001xxxxxxx	15	0001000xxxxxxx	114

и т. д. Символами "x" тут обозначены биты мантиссы без старшей единицы.

Для диапазона [[math]2^K[/math],[math]2^{K+1}[/math]- 1 ] коды формируются следующим образом:

Гамма-код: 00..(К раз)..01x..(К раз)..x; длина [math]2\times{K} + 1[/math] бит;

Дельта-код: [math]n...(2\times{L}+1[/math] раз)...nx..(K раз)..x; длина: [math]2\times{L}+K+1[/math] бит, где L = [math][\log_2{(K+1)}][/math] - целая часть логарифма числа (K+1) по основанию 2; n - биты, относящиеся к записи экспоненты дельта-кода, их число [math]2\times{L} + 1[/math].