Код Голомба

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Див. також[ред.ред. код]