Изменения
Перейти к навигации
Перейти к поиску
Строка 1:
Строка 1: − Код Голомба позволяет представить последовательность символов в виде последовательности двоичных слов. Это представление будет оптимальным при условии, что [[распределение вероятности]] символов подчиняется геометрическому закону:+ − : <math> P(i) = (1-p)p^{i} </math>, − где ''i'' — номер символа, а ''p'' — параметр [[Геометрическое распределение|геометрического распределения]]. Также должно соблюдаться условие:+ + + + + + + + + + + + + + + + + − : <math>p^m = \frac 1 2 </math>, − где ''m'' — основной параметр кода Голомба.+ − Для кодирования символа с номером ''n'' необходимо представить ''n'' в виде: − : <math> n = qm + r </math>,+ − где ''q'' и ''r'' — целые неотрицательные числа, <math> 0 \le r < m </math>. Затем ''q'' кодируется унарным кодом, а ''r'' — бинарным. Полученные двоичные последовательности объединяются в результирующее слово.+ − Пример:+ − основной параметр кода − : <math> m = 4 </math> − кодируемое число − : <math> n = 13 </math> − + − + − : <math> 1110 </math>+ + − + − бинарный код+ − : <math> 01 </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>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>p</math> всегда найдётся не более одного значения <math>m</math>, удовлетворяющего такому неравенству.
== Пример ==
Пусть <math>p = 0.85</math>, <math>n = 13</math>.
Удовлетворяющее двойному неравенству Галлагера - Ван Вурхиса значение <math>m = 4</math>.
частное
частное
: <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> 1110 </math>,
остаток
остаток
: <math> r = n \mod m = 13 \mod 4 = 1 </math>
: <math>r = 1</math>,
код <math> 01 </math>.
Результирующее кодовое слово
: <math> 1110|01 </math>
: <math> 1110|01 </math>
== Ссылки ==
* [http://urchin.earth.li/~twic/Golombs_Original_Paper/Golomb1966.djvu Golomb S.W. 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 Gallager R.G., Van Voorhis D.C. Optimal source codes for geometrically distributed integer alphabets //IEEE Trans. Inf. Theor.–1975.-IT-21, No 2. – pp. 228-230]
{{методы сжатия}}
{{методы сжатия}}