Экспоненциально-кодирование Голомба

редактировать

Экспоненциально-кодирование Голомба (или просто Экспоненциально-кодирование Голомба ) является разновидностью универсального кода. Чтобы закодировать любое неотрицательное целое число x с использованием кода exp-Golomb:

Запишите x + 1 в двоичном формате
Подсчитайте записанные биты, вычтите единицу и запишите это число начального нуля биты, предшествующие предыдущей битовой строке.

Первые несколько значений кода:

0 ⇒ 1 ⇒ 1 1 ⇒ 10 ⇒ 010 2 ⇒ 11 ⇒ 011 3 ⇒ 100 ⇒ 00100 4 ⇒ 101 ⇒ 00101 5 ⇒ 110 ⇒ 00110 6 ⇒ 111 ⇒ 00111 7 ⇒ 1000 ⇒ 0001000 8 ⇒ 1001 ⇒ 0001001...

Это идентично гамма-коду Элиаса x + 1, что позволяет для кодирования 0.

Содержание

1 Расширение до отрицательных чисел
2 Обобщение до порядка k
3 См. также
4 Ссылки

Расширение до отрицательных чисел

Exp- Кодирование Голомба используется в стандартах сжатия видео H.264 / MPEG-4 AVC и H.265 High Efficiency Video Coding, в которых также есть вариант для кодирования подписанных чисел путем присвоения значения 0 двоичному кодовому слову '0' и присвоения последующих кодовых слов входным значениям возрастающей величины (и чередования знак, если поле может содержать отрицательное число):

0 ⇒ 0 ⇒ 1 ⇒ 1 1 ⇒ 1 ⇒ 10 ⇒ 010 −1 ⇒ 2 ⇒ 11 ⇒ 011 2 ⇒ 3 ⇒ 100 ⇒ 00100 −2 ⇒ 4 ⇒ 101 ⇒ 00101 3 ⇒ 5 ⇒ 110 ⇒ 00110 −3 ⇒ 6 ⇒ 111 ⇒ 00111 4 ⇒ 7 ⇒ 1000 ⇒ 0001000 −4 ⇒ 8 ⇒ 1001 ⇒ 0001001...

Другими словами, не -положительное целое число x≤0 отображается в четное целое число −2x, а положительное целое число x>0 отображается в нечетное целое число 2x − 1.

Кодирование Exp-Golomb также используется в видеокодеке Дирака.

Обобщение для порядка k

Для кодирования больших чисел меньшим количеством бит (за счет использования большего количества битов для кодируют меньшие числа), это можно обобщить с помощью параметра k неотрицательного целого числа. Чтобы закодировать неотрицательное целое число x в экспоненциальном коде Голомба порядка k:

Закодируйте ⌊x / 2⌋, используя описанный выше код exp-Голомба порядка 0, затем
Закодируйте x mod 2 в двоичном формате

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

Кодировать x + 2−1, используя экспоненциальный код Голомба порядка 0 (т. Е. Кодировать x + 2, используя гамма-код Элиаса), затем
Удалить k начальные нулевые биты из результата кодирования

Примеры кодирования Exp-Golomb-k
x	k=0	k=1	k=2	k = 3	x	k=0	k=1	k=2	k = 3	x	k=0	k = 1	k = 2	k = 3
0	1	10	100	1000	10	0001011	001100	01110	010010	20	000010101	00010110	0011000	011100
1	010	11	101	1001	11	0001100	001101	01111	010011	21	000010110	00010111	0011001	011101
2	011	0100	110	1010	12	0001101	001110	0010000	010100	22	000010111	00011000	0011010	011110
3	00100	0101	111	10 11	13	0001110	001111	0010001	010101	23	000011000	00011001	0011011	011111
4	00101	0110	01000	1100	14	0001111	00010000	0010010	010110	24	000011001	00011010	0011100	00100000
5	00110	0111	01001	1101	15	000010000	00010001	0010011	010111	25	000011010	00011011	0011101	00100001
6	00111	001000	01010	1110	16	000010001	00010010	0010100	011000	26	000011011	00011100	0011110	00100010
7	0001000	001001	01011	1111	17	000010010	00010011	0010101	011001	27	000011100	00011101	0011111	00100011
8	0001001	001010	01100	010000	18	000010011	00010100	0010110	011010	28	000011101	00011110	000100000	00100100
9	0001010	001011	01101	010001	19	000010100	00010101	0010111	011011	29	000011110	00011111	000100001	00100101

См. Также

Ссылки