Код Голомба

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

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

Розглянемо джерело, яке незалежним чином породжує цілі невід'ємні числа з імовірностями , де p - довільне позитивне число, яке не перевищує 1, тобто джерело, описуване геометричним розподілом.

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

    ,

то оптимальним посимвольним кодом (тобто кодом, що ставить у відповідність кожному кодованого символу певне кодове слово) для такого джерела буде код, побудований згідно з запропонованою С. Голомб процедурою, згідно з якою для будь-якого кодованого числа n при відомому m кодове слово утворюють унарний запис числа і кодований відповідно до описаної нижче процедурою залишок r від ділення :

Якщо m є ступенем числа 2, то код залишку являє собою двійковий запис числа r, розміщений в бітах.
Якщо m не є ступенем 2, обчислюється число .
Далі: Якщо , код залишку являє собою двійковий запис числа r, розміщений в b-1 бітах, інакше залишок r кодується двійковим записом числа , розміщеним у b бітах.

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

     ,

де m - ціле позитивне число. Оскільки для будь-якого p завжди знайдеться не більше одного значення m, що задовольняє наведеній вище нерівності, запропонована С. Голомб процедура кодування геометричного джерела виявляється оптимальною для будь-якого значення p.

Надзвичайно простий в реалізації, але не завжди оптимальний різновид коду Голомба у разі, коли m є ступенем 2, називається кодом Райса.

Приклад[ред.ред. код]

Нехай p = 0.85, потрібно закодувати число n = 13.

Задовольняє подвійній нерівності Галлагера - Ван Вурхиса значення m = 4.

Відповідно до описаної вище процедури кодування кодове слово, відповідне кодованому числу 13, будується як унарний запис результату від ділення n / m:

  ,

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

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

    r = 1,

(код 01, тобто власне залишок, записаний в бітах).

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

     0001 | 01

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