Коды Голомба

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

Рассмотрим источник, независимым образом порождающий целые неотрицательные числа $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}$:

1. Если $m$ является степенью числа 2, то код остатка представляет собой двоичную запись числа $r$, размещённую в $\log_2(m)$ битах.
2. Если $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} \le 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.–1996.- IT-12, No 3. – pp. 399-401
• R. G. Gallager , D. C. Van Voorhis «Optimal source codes for geometrically distributed integer alphabets» //IEEE Trans. Inf. Theor.–1975.-IT-21, No 2. – pp. 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), – pp. 889-897