Golomb coding: Difference between revisions

Revision as of 23:55, 10 July 2021

Revision as of 23:57, 10 July 2021

Line 31:

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'' bits for Golomb code (i.e. ''M'' is not a power of 2). Let <math>b = \lceil\log_2(M)\rceil</math>. If <math>0 \leq r < 2^b-M</math>, then use ''b''-1 bits to encode ''r''. If <math>2^b-M \leq r < M</math>, then use ''b'' 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:

: <math>(1-p)^M + (1-p)^{M+1} \leq 1 < (1-p)^{M-1} + (1-p)^M,</math>