Код Голомба

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

Розглянемо джерело, яке незалежним чином породжує цілі невід'ємні числа ${\displaystyle i}$ з імовірностями ${\displaystyle P(i)=(1-p)p^{i}}$, де p - довільне позитивне число, яке не перевищує 1, тобто джерело, описуване геометричним розподілом.

Якщо при цьому ціле позитивне число m таке, що

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

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

Якщо m є ступенем числа 2, то код залишку являє собою двійковий запис числа r, розміщений в ${\displaystyle \ log_{2}(m)}$ бітах.
Якщо m не є ступенем 2, обчислюється число ${\displaystyle b=\lceil \log _{2}(m)\rceil }$.
Далі: Якщо ${\displaystyle r<2^{b}-m}$, код залишку являє собою двійковий запис числа r, розміщений в b-1 бітах, інакше залишок r кодується двійковим записом числа ${\displaystyle r+2^{b}-m}$, розміщеним у b бітах.

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

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

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

(унарний код 0001, тобто q нулів із завершальною одиницею),

і кодованого залишку

    r = 1,

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

Результуюче кодове слово

     0001 | 01