Изменения

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

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

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

Рассмотрим источник, независимым образом порождающий целые неотрицательные числа <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>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>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>r</math>, размещённую в <math>\log_2(m)</math> битах.

#Если <math>m</math> не является степенью 2, вычисляется число <math>b = \lceil\log_2(m)\rceil</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 < 2^b-m </math>, код остатка представляет собой двоичную запись числа <math>r</math>, размещённую в <math>b-1</math> битах,

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

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

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

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

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

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

== Пример ==

== Пример ==

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

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

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

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

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

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

: <math> q = \left[ \frac{n}{m} \right] = \left[\frac{13}{4} \right] = 3 </math>,  

: <math> q = \left[ \frac{n}{m} \right] = \left[\frac{13}{4} \right] = 3 </math>,

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

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

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

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

: <math>r = 1</math>,  

: <math>r = 1</math>,

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

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

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

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

== Ссылки ==

== Ссылки ==

* [http://urchin.earth.li/~twic/Golombs_Original_Paper/ S. W. Golomb «Run-length encodings» //IEEE Trans. Inf. Theor.–1996.- IT-12, No 3. – pp. 399-401]

* [http://urchin.earth.li/~twic/Golombs_Original_Paper/ S. W. Golomb «Run-length encodings» //IEEE Trans. Inf. Theor.-1996.- IT-12, No 3. — pp. 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.-IT-21, No 2. – pp. 228-230]

* [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.-IT-21, No 2. — pp. 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.– vol. 16(9), – pp. 889-897]

* [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.- vol. 16(9), — pp. 889—897]