Golomb coding: Difference between revisions

Revision as of 23:57, 10 July 2021

Revision as of 03:05, 11 July 2021

Line 29:

[[Image:GolombCodeRedundancy.svg|300px|This image shows the redundancy of the Golomb code, when M is chosen optimally for ''p'' ≥ 1/2.|thumb|right]]

Both ''q'' and ''r'' will be encoded using variable numbers of bits – ''q'' by a unary code, and <math>r</math> by ''b'' bits for Rice code, or a choice between ''b''-1 and ''b''+1 bits for Golomb code (i.e. ''M'' is not a power of 2). Let <math>b = \lceillfloor\log_2(M)\rceilrfloor</math>. If <math>0 \leq r < 2^{b+1} - M</math>, then use ''b''-1 bits to encode ''r''.; If <math>2^b-M \leq r < M</math>otherwise, then use ''b''+1 bits to encode ''r''. Clearly, <math>b=\log_2(M)</math> if ''M'' is a power of 2 and we can encode all values of ''r'' with ''b'' bits.

The integer ''x'' treated by Golomb was the run length of a [[Bernoulli process]], which has a [[geometric distribution]] starting at 0. The best choice of parameter ''M'' is a function of the corresponding Bernoulli process, which is parameterized by <math>p = P(X=0)</math> the probability of success in a given [[Bernoulli trial]]. <math>M</math> is either the median of the distribution or the median +/− 1. It can be determined by these inequalities: