Коды Голомба

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

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

Код Голомба позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что распределение вероятности символов подчиняется геометрическому закону:

P(i) = (1 − p)pi,

где 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



Источник — «http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4%D1%8B_%D0%93%D0%BE%D0%BB%D0%BE%D0%BC%D0%B1%D0%B0»
На других языках