Русская Википедия:Коды Голомба
Коды Голомба — семейство энтропийных кодов. Под кодом Голомба может подразумеваться также один из представителей этого семейства.
Рассмотрим источник, независимым образом порождающий целые неотрицательные числа <math>i</math> с вероятностями <math>P(i) = (1-p)p^{i}</math>, где <math>p</math> — произвольное положительное число, не превосходящее 1, то есть источник, описываемый геометрическим распределением. Если при этом целое положительное число <math>m</math> таково, что
- <math>p^m = \frac 1 2 </math>,
то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной Соломоном Голомбом процедурой, согласно которой для любого кодируемого числа <math>n</math> при известном <math>m</math> кодовое слово образуют унарная запись числа <math>q = \left[ \frac{n}{m}\right]</math> и кодированный в соответствии с описанной ниже процедурой остаток <math>r</math> от деления <math>\frac{n}{m}</math>:
- Если <math>m</math> является степенью числа 2, то код остатка представляет собой двоичную запись числа <math>r</math>, размещённую в <math>\log_2(m)</math> битах.
- Если <math>m</math> не является степенью 2, вычисляется число <math>b = \lceil\log_2(m)\rceil</math>. Далее:
- Если <math>r < 2^b-m </math>, код остатка представляет собой двоичную запись числа <math>r</math>, размещённую в <math>b-1</math> битах,
- иначе остаток <math>r</math> кодируется двоичной записью числа <math>r+2^b-m</math>, размещённой в <math>b</math> битах.
Позже Р. Галлагером и Д. Ван Вурхисом было показано, что предложенный Голомбом код оптимален не только для дискретного набора значений <math>p</math>, удовлетворяющих приведённому выше критерию, но и для любых <math>p</math>, для которых справедливо двойное неравенство
- <math>p^{m} + p^{m+1} \le 1 < p^{m} + p^{m-1}</math>,
где <math>m</math> — целое положительное число. Поскольку для любого <math>p</math> всегда найдётся не более одного значения <math>m</math>, удовлетворяющего приведённому выше неравенству, предложенная С. Голомбом процедура кодирования геометрического источника оказывается оптимальной для любого значения <math>p</math>.
Чрезвычайно простая в реализации, но не всегда оптимальная разновидность кода Голомба в случае, когда <math>m</math> является степенью 2, называется кодом Райса.
Пример
Пусть <math>p = 0.85</math>, требуется закодировать число <math>n = 13</math>.
Удовлетворяющее двойному неравенству Галлагера — Ван Вурхиса значение <math>m = 4</math>.
В соответствии с описанной выше процедурой кодирования кодовое слово, соответствующее кодируемому числу 13, строится как унарная запись частного от деления n/m:
- <math> q = \left[ \frac{n}{m} \right] = \left[\frac{13}{4} \right] = 3 </math>,
(унарный код <math> 0001 </math>, то есть q нулей с завершающей единицей),
и кодированного остатка
- <math>r = 1</math>,
(код <math> 01 </math>, то есть собственно остаток, записанный в <math>\lceil\log_2(m)\rceil</math> битах).
Результирующее кодовое слово
- <math> 0001|01 </math>
См. также
Ссылки
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- 2.3 Golomb Codes / Amir Said, On the Determination of Optimal Parameterized Prefix Codes for Adaptive Entropy Coding. HPL-2006-74
