Коды Голомба

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

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

См. также

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

Ссылки

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• 2.3 Golomb Codes / Amir Said, On the Determination of Optimal Parameterized Prefix Codes for Adaptive Entropy Coding. HPL-2006-74