Интернет магазин китайских планшетных компьютеров

Компьютеры - Коды Голомба

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

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

,

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

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

Если r < 2 − m, код остатка представляет собой двоичную запись числа r, размещённую в b − 1 битах,

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

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

,

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

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