Код Голомба

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

Розглянемо джерело, яке незалежним чином породжує цілі невід'ємні числа $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}}$:

Якщо m є ступенем числа 2, то код залишку являє собою двійковий запис числа r, розміщений в $\ log_{2}(m)$ бітах.
Якщо 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}\leq 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