Golomb coding: Difference between revisions

Revision as of 23:47, 10 July 2021

Revision as of 23:55, 10 July 2021

Line 19:

Golomb–Rice codes can be thought of as codes that indicate a number by the position of the ''bin'' (''q''), and the ''offset'' within the bin (''r''). The above figure shows the position ''q'' and offset ''r'' for the encoding of integer ''N'' using Golomb–Rice parameter ''M''.

Formally, the two parts are given by the following expression, where <math>x</math> is the numberinteger being encoded:

:<math>q = \left \lfloor \frac{\left (x-1 \right )}{M} \right \rfloor</math>

and

:<math>r = x -1- qM</math>.

The final result looks like: <math>\left (q+1 \right ) r</math>.

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

NoteBoth that''q'' <math>and ''r</math>'' canwill be ofencoded ausing varyingvariable numbernumbers of bits. Specifically– ''q'' by a unary code, and <math>r</math> is onlyby ''b'' bits for Rice code, andor a switcheschoice 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 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>