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



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

23 января 2011


Оглавление:
1. Коды Голомба
2. Пример



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

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

p^m = \frac 1 2 ,

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


  1. Если m является степенью числа 2, то код остатка представляет собой двоичную запись числа r, размещённую в log2 битах.
  2. Если m не является степенью 2, вычисляется число b = \lceil\log_2\rceil. Далее:
Если r < 2 − m, код остатка представляет собой двоичную запись числа r, размещённую в b − 1 битах,
иначе остаток r кодируется двоичной записью числа r + 2 − m, размещённой в b битах.


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


p^{m} + p^{m+1} \le 1 < p^{m} + p^{m-1},


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

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



Просмотров: 2007


<<< Кодирование длин серий
Омега-код Элиаса >>>