Гамма-кодирование Элиаса

Элиас $\gamma$ код или гамма-код Элиаса — универсальный код , кодирующий положительные целые числа, разработанный Питером Элиасом . Чаще всего он используется при кодировании целых чисел, верхняя граница которых не может быть определена заранее.

Кодировка

Чтобы закодировать число x ≥ 1:

1. Позволять $N=\lfloor \log _{2}x\rfloor$ быть наивысшей степенью двойки, которую он содержит, поэтому 2 ^Н ≤ х < 2 ^{Н +1} .
2. Написать $N$ ноль битов, тогда
3. Добавьте двоичную форму $x$, $(N+1)$-битное двоичное число.

Эквивалентный способ выразить тот же процесс:

1. Кодировать $N$в унарном ; то есть как $N$ нули, за которыми следует единица.
2. Добавьте оставшиеся $N$ двоичные цифры $x$ этому представлению $N$.

Чтобы представить число $x$, используется гамма Элиаса (γ) $2\lfloor \log _{2}(x)\rfloor +1$ биты.

Код начинается ( для ясности добавлено предполагаемое распределение вероятностей для кода):

Число	Двоичный	γ-кодирование	Подразумеваемая вероятность
1 = 2 0  + 0	1	1	1/2
2 = 2 1 + 0	1 0	0 1 0	1/8
3 = 2 1 + 1	1 1	0 1 1	1/8
4 = 2 2 + 0	1 00	00 1 00	1/32
5 = 2 2 + 1	1 01	00 1 01	1/32
6 = 2 2 + 2	1 10	00 1 10	1/32
7 = 2 2 + 3	1 11	00 1 11	1/32
8 = 2 3 + 0	1 000	000 1 000	1/128
9 = 2 3 + 1	1 001	000 1 001	1/128
10 = 2 3 + 2	1 010	000 1 010	1/128
11 = 2 3 + 3	1 011	000 1 011	1/128
12 = 2 3 + 4	1 100	000 1 100	1/128
13 = 2 3 + 5	1 101	000 1 101	1/128
14 = 2 3 + 6	1 110	000 1 110	1/128
15 = 2 3 + 7	1 111	000 1 111	1/128
16 = 2 4 + 0	1 0000	0000 1 0000	1/512
17 = 2 4  +  1	1 0001	0000 1 0001	1/512

Расшифровка

Чтобы декодировать целое число, закодированное гамма-гаммой Элиаса:

1. Считайте и посчитайте 0 из потока, пока не дойдете до первой 1. Назовите это количество нулей N .
2. Учитывая тот, который был достигнут, является первой цифрой целого числа со значением 2 ^Н , прочитайте оставшиеся N цифр целого числа.

Использует

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

Гамма-кодирование является строительным блоком дельта-кода Элиаса .

Обобщения

См. также: Величина переменной длины § Зигзагообразное кодирование.

Гамма-кодирование не кодирует ноль или отрицательные целые числа. Один из способов обработки нуля — добавить 1 перед кодированием, а затем вычесть 1 после декодирования. Другой способ — поставить перед каждым ненулевым кодом цифру 1, а затем закодировать ноль как одиночный 0.

Один из способов кодирования всех целых чисел — установить биекцию , отображающую целые числа (0, −1, 1, −2, 2, −3, 3, ...) в (1, 2, 3, 4, 5, 6). , 7, ...) перед кодированием. В программном обеспечении это проще всего сделать путем сопоставления неотрицательных входов с нечетными выходами, а отрицательных входов с четными выходами, поэтому младший бит становится битом с инвертированным знаком :
${\begin{cases}x\mapsto 2x+1&\mathrm {when~} x\geq 0\\x\mapsto -2x&\mathrm {when~} x<0\\\end{cases}}$

Экспоненциальное кодирование Голомба обобщает гамма-код на целые числа с «более плоским» степенным распределением, точно так же, как кодирование Голомба обобщает унарный код. Он включает в себя деление числа на положительный делитель, обычно степень 2, запись гамма-кода для числа, превышающего частное, и запись остатка в обычном двоичном коде.

См. также

• Дельта-кодирование Элиаса (d) – универсальный код, кодирующий положительные целые числа. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Кодирование Элиаса омега (?) - Универсальный код, кодирующий положительные целые числа.
• Posit (числовой формат) — вариант чисел с плавающей запятой в компьютерах. Страницы, отображающие краткие описания целей перенаправления.

Дальнейшее чтение

• Саюд, Халид (2003). «Гамма-коды Левенштейна и Элиаса». Справочник по сжатию без потерь . Эльзевир . ISBN  978-0-12-620861-0 .