Редактирование: Коды Голомба

'''Коды [[Голомб, Соломон Вольф|Голомба]]''' — семейство [[энтропийное кодирование|энтропийных кодов]]. Под кодом Голомба может подразумеваться также один из представителей этого семейства. 

Рассмотрим источник, независимым образом порождающий целые неотрицательные числа <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> битах.

Позже {{нп5|Галлагер, Роберт|Р. Галлагером|en|Robert G. Gallager}} и Д. Ван Вурхисом было показано, что предложенный Голомбом код оптимален не только для дискретного набора значений <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>

== См. также ==
* [[Экспоненциальный код Голомба]]

== Ссылки ==
* {{статья|ссылка=http://urchin.earth.li/~twic/Golombs_Original_Paper/|автор=S. W. Golomb.|заглавие=Run-length encodings|издание=IEEE Trans. Inf. Theor|год=1966|номер=3, IT-12|pages=399—401}}
* {{статья|ссылка=http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true&arnumber=1055357|автор=R. G. Gallager, D. C. Van Voorhis.|заглавие=Optimal source codes for geometrically distributed integer alphabets|издание=IEEE Trans. Inf. Theor|год=1975|номер=2, IT-21|pages=228—230}}
* {{статья|ссылка=http://dx.doi.org/10.1109/TCOM.1971.1090789|автор=R. F. Rice, J. R. Plaunt.|заглавие=Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data|издание=IEEE Trans. on Commun|год=1971|volume=16(9)|pages=889—897}}
* [http://www.hpl.hp.com/techreports/2006/HPL-2006-74.pdf#page=18 2.3 Golomb Codes] / Amir Said, On the Determination of Optimal Parameterized Prefix Codes for Adaptive Entropy Coding. HPL-2006-74

{{методы сжатия}}

[[Категория:Теория кодирования]]
[[Категория:Алгоритмы сжатия без потерь]]