- Коды Голомба
-
Коды Голомба — семейство энтропийных кодов. Под кодом Голомба может подразумеваться также один из представителей этого семейства.
Рассмотрим источник, независимым образом порождающий целые неотрицательные числа
с вероятностями
, где
— произвольное положительное число, не превосходящее 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число
таково, что
,
то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной С. Голомбом процедурой, согласно которой для любого кодируемого числа
при известном
кодовое слово образуют унарная запись числа
и кодированный в соответствии с описанной ниже процедурой остаток
от деления
:
- Если
является степенью числа 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.
Категории:- Теория кодирования
- Алгоритмы сжатия без потерь
Wikimedia Foundation. 2010.