PROFILPELAJAR.COM

Коды Голомба — семейство энтропийных кодов. Под кодом Голомба может подразумеваться также один из представителей этого семейства.

Рассмотрим источник, независимым образом порождающий целые неотрицательные числа $i$ с вероятностями $P(i)=(1-p)p^{i}$ , где $p$ — произвольное положительное число, не превосходящее 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число $m$ таково, что

p^{m}={\frac {1}{2}}

,

то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной Соломоном Голомбом процедурой, согласно которой для любого кодируемого числа $n$ при известном $m$ кодовое слово образуют унарная запись числа $q=\left[{\frac {n}{m}}\right]$ и кодированный в соответствии с описанной ниже процедурой остаток $r$ от деления ${\frac {n}{m}}$ :

Если $m$ является степенью числа 2, то код остатка представляет собой двоичную запись числа $r$ , размещённую в $\log _{2}(m)$ битах.
Если $m$ не является степенью 2, вычисляется число $b=\lceil \log _{2}(m)\rceil$ . Далее:

Если

r<2^{b}-m

, код остатка представляет собой двоичную запись числа

r

, размещённую в

b-1

битах,

иначе остаток

r

кодируется двоичной записью числа

r+2^{b}-m

, размещённой в

b

битах.

Позже Р. Галлагером и Д. Ван Вурхисом было показано, что предложенный Голомбом код оптимален не только для дискретного набора значений $p$ , удовлетворяющих приведённому выше критерию, но и для любых $p$ , для которых справедливо двойное неравенство

p^{m}+p^{m+1}\leq 1<p^{m}+p^{m-1}

,

где $m$ — целое положительное число. Поскольку для любого $p$ всегда найдётся не более одного значения $m$ , удовлетворяющего приведённому выше неравенству, предложенная С. Голомбом процедура кодирования геометрического источника оказывается оптимальной для любого значения $p$ .

Чрезвычайно простая в реализации, но не всегда оптимальная разновидность кода Голомба в случае, когда $m$ является степенью 2, называется кодом Райса.

Пример

Пусть $p=0.85$ , требуется закодировать число $n=13$ .

Удовлетворяющее двойному неравенству Галлагера — Ван Вурхиса значение $m=4$ .

В соответствии с описанной выше процедурой кодирования кодовое слово, соответствующее кодируемому числу 13, строится как унарная запись частного от деления n/m:

q=\left[{\frac {n}{m}}\right]=\left[{\frac {13}{4}}\right]=3

,

(унарный код $0001$ , то есть q нулей с завершающей единицей),

и кодированного остатка

r=1

,

(код $01$ , то есть собственно остаток, записанный в $\lceil \log _{2}(m)\rceil$ битах).

Результирующее кодовое слово

0001|01

См. также

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

Ссылки

S. W. Golomb. Run-length encodings // IEEE Trans. Inf. Theor. — 1966. — № 3, IT-12. — P. 399—401.
R. G. Gallager, D. C. Van Voorhis. Optimal source codes for geometrically distributed integer alphabets // IEEE Trans. Inf. Theor. — 1975. — № 2, IT-21. — P. 228—230.
R. F. Rice, J. R. Plaunt. Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data // IEEE Trans. on Commun. — 1971. — Vol. 16(9). — P. 889—897.
2.3 Golomb Codes / Amir Said, On the Determination of Optimal Parameterized Prefix Codes for Adaptive Entropy Coding. HPL-2006-74