WikiSort.ru - Не сортированное

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

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

${\displaystyle p^{m}={\frac {1}{2}}}$ ,

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

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

Если ${\displaystyle r<2^{b}-m}$ , код остатка представляет собой двоичную запись числа ${\displaystyle r}$ , размещённую в ${\displaystyle b-1}$ битах,

иначе остаток ${\displaystyle r}$ кодируется двоичной записью числа ${\displaystyle r+2^{b}-m}$ , размещённой в ${\displaystyle b}$ битах.

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

${\displaystyle p^{m}+p^{m+1}\leq 1<p^{m}+p^{m-1}}$ ,

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

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

Пример

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

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

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

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

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

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

${\displaystyle r=1}$ ,

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

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

${\displaystyle 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