Код Голомба
Коди Голомба — сімейство ентропійних кодів. Під кодом Голомба може матися на увазі також один із представників цього сімейства.
Розглянемо джерело, яке незалежним чином породжує цілі невід'ємні числа з імовірностями , де 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