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

Рассмотрим источник, независимым образом порождающий целые неотрицательные числа с вероятностями , где  — произвольное положительное число, не превосходящее 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число таково, что

,

то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной С. Голомбом процедурой, согласно которой для любого кодируемого числа при известном кодовое слово образуют унарная запись числа и кодированный в соответствии с описанной ниже процедурой остаток от деления :

1. Если является степенью числа 2, то код остатка представляет собой двоичную запись числа , размещённую в битах.
2. Если не является степенью 2, вычисляется число . Далее:

Если , код остатка представляет собой двоичную запись числа , размещённую в битах,

иначе остаток кодируется двоичной записью числа , размещённой в битах.

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

,

где  — целое положительное число. Поскольку для любого всегда найдётся не более одного значения , удовлетворяющего приведённому выше неравенству, предложенная С. Голомбом процедура кодирования геометрического источника оказывается оптимальной для любого значения .

Чрезвычайно простая в реализации, но не всегда оптимальная разновидность кода Голомба в случае, когда является степенью 2, называется кодом Райса.

Пример

Пусть , требуется закодировать число .

Удовлетворяющее двойному неравенству Галлагера — Ван Вурхиса значение .

В соответствии с описанной выше процедурой кодирования кодовое слово, соответствующее кодируемому числу 13, строится как унарная запись частного от деления n/m:

,

(унарный код , то есть q нулей с завершающей единицей),

и кодированного остатка

,

(код , то есть собственно остаток, записанный в битах).

Результирующее кодовое слово

См. также

• Экспоненциальный код Голомба

Ссылки

• S. W. Golomb. Run-length encodings // IEEE Trans. Inf. Theor. — 1966. — № 3, IT-12. — P. 399—401.
• R. G. Gallager, D. C. Van Voorhis. Optimal source codes for geometrically distributed integer alphabets // IEEE Trans. Inf. Theor. — 1975. — № 2, IT-21. — P. 228—230.
• R. F. Rice, J. R. Plaunt. Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data // IEEE Trans. on Commun. — 1971. — Vol. 16(9). — P. 889—897.