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

Универсальная схема кодирования для положительных целых чисел

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

Кодирование

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

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

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

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

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

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

Расшифровка

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

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

Использует

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

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

Обобщения

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

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

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

Смотрите также

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

Ссылки

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

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

• Sayood, Khalid (2003). "Levenstein and Elias Gamma Codes". Справочник по сжатию без потерь . Elsevier . ISBN 978-0-12-620861-0.