Коды Голомба

---

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

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

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

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

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

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

---