Изменения

то оптимальным посимвольным кодом (то есть кодом, ставящим в соответствие каждому кодируемому символу определённое кодовое слово) для такого источника будет код, построенный в соответствии с предложенной С. Голомбом процедурой, согласно которой для любого кодируемого числа <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>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>p</math>, удовлетворяющих приведённому выше критерию, но и для любых <math>p</math>, для которых справедливо двойное неравенство

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

: <math>p^{m} + p^{m+1} \le 1 < p^{m} + p^{m-1}</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> — целое положительное число. Поскольку для любого <math>p</math> всегда найдётся не более одного значения <math>m</math>, удовлетворяющего приведённому выше неравенству, предложенная С. Голомбом процедура кодирования геометрического источника оказывается оптимальной для любого значения <math>p</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|номер=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.-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|номер=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.- 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|volume=16(9)|pages=889—897}}

 

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

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