Коды Голомба

Коды Голомба — семейство энтропийных кодов. Под кодом Голомба может подразумеваться также один из представителей этого семейства.

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

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

См. также

• Экспоненциальный код Голомба

Ссылки

• S. W. Golomb. [urchin.earth.li/~twic/Golombs_Original_Paper/ Run-length encodings] // IEEE Trans. Inf. Theor. — 1966. — № 3, IT-12. — P. 399—401.
• R. G. Gallager, D. C. Van Voorhis. [ieeexplore.ieee.org/xpl/freeabs_all.jsp?reload=true&arnumber=1055357 Optimal source codes for geometrically distributed integer alphabets] // IEEE Trans. Inf. Theor. — 1975. — № 2, IT-21. — P. 228—230.
• R. F. Rice, J. R. Plaunt. [dx.doi.org/10.1109/TCOM.1971.1090789 Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data] // IEEE Trans. on Commun. — 1971. — Vol. 16(9). — P. 889—897.

Отрывок, характеризующий Коды Голомба

– Ей пишу, – сказал он.
Он облокотился на стол с пером в руке, и, очевидно обрадованный случаю быстрее сказать словом всё, что он хотел написать, высказывал свое письмо Ростову.
– Ты видишь ли, дг'уг, – сказал он. – Мы спим, пока не любим. Мы дети пг`axa… а полюбил – и ты Бог, ты чист, как в пег'вый день создания… Это еще кто? Гони его к чог'ту. Некогда! – крикнул он на Лаврушку, который, нисколько не робея, подошел к нему.
– Да кому ж быть? Сами велели. Вахмистр за деньгами пришел.
Денисов сморщился, хотел что то крикнуть и замолчал.
– Сквег'но дело, – проговорил он про себя. – Сколько там денег в кошельке осталось? – спросил он у Ростова.
– Семь новых и три старых.
– Ах,сквег'но! Ну, что стоишь, чучела, пошли вахмистг'а, – крикнул Денисов на Лаврушку.
– Пожалуйста, Денисов, возьми у меня денег, ведь у меня есть, – сказал Ростов краснея.
– Не люблю у своих занимать, не люблю, – проворчал Денисов.
– А ежели ты у меня не возьмешь деньги по товарищески, ты меня обидишь. Право, у меня есть, – повторял Ростов.
– Да нет же.
И Денисов подошел к кровати, чтобы достать из под подушки кошелек.
– Ты куда положил, Ростов?
– Под нижнюю подушку.
– Да нету.
Денисов скинул обе подушки на пол. Кошелька не было.
– Вот чудо то!
– Постой, ты не уронил ли? – сказал Ростов, по одной поднимая подушки и вытрясая их.
Он скинул и отряхнул одеяло. Кошелька не было.
– Уж не забыл ли я? Нет, я еще подумал, что ты точно клад под голову кладешь, – сказал Ростов. – Я тут положил кошелек. Где он? – обратился он к Лаврушке.
– Я не входил. Где положили, там и должен быть.
– Да нет…
– Вы всё так, бросите куда, да и забудете. В карманах то посмотрите.
– Нет, коли бы я не подумал про клад, – сказал Ростов, – а то я помню, что положил.
Лаврушка перерыл всю постель, заглянул под нее, под стол, перерыл всю комнату и остановился посреди комнаты. Денисов молча следил за движениями Лаврушки и, когда Лаврушка удивленно развел руками, говоря, что нигде нет, он оглянулся на Ростова.
– Г'остов, ты не школьнич…
Ростов почувствовал на себе взгляд Денисова, поднял глаза и в то же мгновение опустил их. Вся кровь его, бывшая запертою где то ниже горла, хлынула ему в лицо и глаза. Он не мог перевести дыхание.
– И в комнате то никого не было, окромя поручика да вас самих. Тут где нибудь, – сказал Лаврушка.
– Ну, ты, чог'това кукла, повог`ачивайся, ищи, – вдруг закричал Денисов, побагровев и с угрожающим жестом бросаясь на лакея. – Чтоб был кошелек, а то запог'ю. Всех запог'ю!
Ростов, обходя взглядом Денисова, стал застегивать куртку, подстегнул саблю и надел фуражку.
– Я тебе говог'ю, чтоб был кошелек, – кричал Денисов, тряся за плечи денщика и толкая его об стену.
– Денисов, оставь его; я знаю кто взял, – сказал Ростов, подходя к двери и не поднимая глаз.
Денисов остановился, подумал и, видимо поняв то, на что намекал Ростов, схватил его за руку.
– Вздог'! – закричал он так, что жилы, как веревки, надулись у него на шее и лбу. – Я тебе говог'ю, ты с ума сошел, я этого не позволю. Кошелек здесь; спущу шкуг`у с этого мег`завца, и будет здесь.
– Я знаю, кто взял, – повторил Ростов дрожащим голосом и пошел к двери.
– А я тебе говог'ю, не смей этого делать, – закричал Денисов, бросаясь к юнкеру, чтоб удержать его.