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

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

Запишите 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
... ^[1]

В приведенных выше примерах рассмотрим случай 3. Для 3 x+1 = 3 + 1 = 4. 4 в двоичном формате равно «100». «100» имеет 3 бита, а 3-1 = 2. Следовательно, добавьте 2 нуля перед «100», что равно «00100».

Аналогично рассмотрим число 8. «8 + 1» в двоичном формате равно «1001». «1001» имеет 4 бита, а 4-1 — это 3. Следовательно, добавьте 3 нуля перед 1001, что составит «0001001».

Это идентично гамма-коду Элиаса x +1 , позволяющему кодировать 0. ^[2]

Расширение отрицательных чисел [ править ]

Кодирование Exp-Golomb используется в стандартах сжатия видео 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
... ^[1]

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

Кодирование Exp-Golomb также используется в видеокодеке Dirac . ^[3]

Обобщение на порядок k [ править ]

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

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

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

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

Exp-Golomb- k Примеры кодирования
Икс	к = 0	к =1	к =2	к =3	Икс	к = 0	к =1	к =2	к =3	Икс	к = 0	к =1	к =2	к =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	1011	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

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

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

^ Перейти обратно: ^а ^б Ричардсон, Иэн (2010). Расширенный стандарт сжатия видео H.264 . Уайли. стр. 208, 221. ISBN. 978-0-470-51692-8 .
^ Рупп, Маркус (2009). Передача видео и мультимедиа по сотовым сетям: анализ, моделирование и оптимизация в действующих мобильных сетях 3G . Уайли. п. 149. ИСБН 9780470747766 .
^ «Спецификация Дирака» (PDF) . Би-би-си. Архивировано из оригинала (PDF) 3 мая 2015 г. Проверено 9 марта 2011 г.

[richardson-1] Перейти обратно: ^а ^б Ричардсон, Иэн (2010). Расширенный стандарт сжатия видео H.264 . Уайли. стр. 208, 221. ISBN. 978-0-470-51692-8 .

[2] Рупп, Маркус (2009). Передача видео и мультимедиа по сотовым сетям: анализ, моделирование и оптимизация в действующих мобильных сетях 3G . Уайли. п. 149. ИСБН 9780470747766 .

[3] «Спецификация Дирака» (PDF) . Би-би-си. Архивировано из оригинала (PDF) 3 мая 2015 г. Проверено 9 марта 2011 г.

[1]

[2]

[3]