Коды Голомба

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

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

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

p^m = \frac 1 2 ,

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

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

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

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

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

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

Пример[править | править исходный текст]

Пусть p = 0.85, требуется закодировать число n = 13.

Удовлетворяющее двойному неравенству Галлагера — Ван Вурхиса значение m = 4.

В соответствии с описанной выше процедурой кодирования кодовое слово, соответствующее кодируемому числу 13, строится как унарная запись частного от деления n/m:

 q = \left[ \frac{n}{m} \right] = \left[\frac{13}{4} \right] = 3 ,

(унарный код  0001 , то есть q нулей с завершающей единицей),

и кодированного остатка

r = 1,

(код  01 , то есть собственно остаток, записанный в \lceil\log_2(m)\rceil битах).

Результирующее кодовое слово

 0001|01

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]