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

Γ-код Элиаса или гамма-код Элиаса - это универсальный код, кодирующий положительные целые числа, разработанный Питером Элиасом . ^[1]^{: 197, 199} Чаще всего используется при кодировании целых чисел, верхняя граница которых не может быть определена заранее.

Кодировка [ править ]

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

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

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

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

Для представления числа гамма Элиаса (γ) использует биты. ^[1]^:¹⁹⁹ $x$ $2\lfloor \log _{2}(x)\rfloor +1$

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

Число	Двоичный	γ-кодирование	Предполагаемая вероятность
1 = 2 ⁰ + 0	`1`	`1`	1/2

2 = 2 ¹ + 0	`1 0`	`0 1 0`	1/8
3 = 2 ¹ + 1	`1 1`	`0 1 1`	1/8

4 = 2 ² + 0	`1 00`	`00 1 00`	1/32
5 = 2 ² + 1	`1 01`	`00 1 01`	1/32
6 = 2 ² + 2	`1 10`	`00 1 10`	1/32
7 = 2 ² + 3	`1 11`	`00 1 11`	1/32

8 = 2 ³ + 0	`1 000`	`000 1 000`	1/128
9 = 2 ³ + 1	`1 001`	`000 1 001`	1/128
10 = 2 ³ + 2	`1 010`	`000 1 010`	1/128
11 = 2 ³ + 3	`1 011`	`000 1 011`	1/128
12 = 2 ³ + 4	`1 100`	`000 1 100`	1/128
13 = 2 ³ + 5	`1 101`	`000 1 101`	1/128
14 = 2 ³ + 6	`1 110`	`000 1 110`	1/128
15 = 2 ³ + 7	`1 111`	`000 1 111`	1/128

16 = 2 ⁴ + 0	`1 0000`	`0000 1 0000`	1/512
17 = 2 ⁴ + 1	`1 0001`	`0000 1 0001`	1/512

Расшифровка [ править ]

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

Читать и считать 0s из потока , пока вы не достигнете первой 1. Вызовите это количество нулей N .
Считая, что достигнутая цифра является первой цифрой целого числа со значением 2 ^N , прочтите оставшиеся 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}}$

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

См. Также [ править ]

Ссылки [ править ]

^ ^а ^б Элиас, Питер (март 1975). «Универсальные наборы кодовых слов и представления целых чисел». IEEE Transactions по теории информации . 21 (2): 194–203. DOI : 10,1109 / tit.1975.1055349 .

Дальнейшее чтение [ править ]

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

[Elias-1] а ^б Элиас, Питер (март 1975). «Универсальные наборы кодовых слов и представления целых чисел». IEEE Transactions по теории информации . 21 (2): 194–203. DOI : 10,1109 / tit.1975.1055349 .

[1]