Коды Голомба

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

Код Голомба позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что распределение вероятности символов подчиняется геометрическому закону: $$P(i) = (1-p)p^{i} ,$$

где i — номер символа, а p — параметр геометрического распределения. Также должно соблюдаться условие: $$p^m = \frac 1 2 ,$$

где m — основной параметр кода Голомба.

Для кодирования символа с номером n необходимо представить n в виде: $$n = qm + r ,$$

где q и r — целые положительные числа, $0 \le r < m$. Затем r кодируется унарным кодом, а q — бинарным. Полученные двоичные последовательности объединяются в результирующее слово.

Пример:

основной параметр кода $$m = 4$$ кодируемое число $$n = 13$$

частное $$q = \left[ \frac{n}{m} \right] = \left[\frac{13}{4} \right] = 3$$ унарный код $$1110$$

остаток $$r = n \mod m = 13 \mod 4 = 1$$ бинарный код $$01$$

результирующее кодовое слово $$1110|01$$