|
===Construction of codes===
Golomb coding uses a tunable parameter <math>{{mvar|M</math>}} to divide an input value ''{{mvar|N''}} (aka ''{{mvar|x''}}) into two parts: ''{{mvar|q''}}, the result of a division by ''{{mvar|M''}}, and ''{{mvar|r''}}, the remainder. The quotient is sent in [[unary coding]], followed by the remainder in [[truncated binary encoding]]. When <math>M=1</math>, Golomb coding is equivalent to unary coding.
[[Image:golomb rice code.svg]]
Golomb–Rice codes can be thought of as codes that indicate a number by the position of the ''bin'' (''{{mvar|q''}}), and the ''offset'' within the bin (''{{mvar|r''}}). The above figure shows the position ''{{mvar|q''}} and offset ''{{mvar|r''}} for the encoding of integer ''{{mvar|N''}} using Golomb–Rice parameter ''{{mvar|M''}}.
Formally, the two parts are given by the following expression, where <math>x</math> is the nonnegative integer being encoded:
[[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 ''{{mvar|q''}} and ''{{mvar|r''}} will be encoded using variable numbers of bits – ''{{mvar|q''}} by a unary code, and <math>{{mvar|r</math>}} by ''{{mvar|b''}} bits for Rice code, or a choice between ''{{mvar|b''}} and ''{{mvar|b''}}+1 bits for Golomb code (i.e. ''{{mvar|M''}} is not a power of 2). Let <math>b = \lfloor\log_2(M)\rfloor</math>. If <math>r < 2^{b+1} - M</math>, then use ''{{mvar|b''}} bits to encode ''{{mvar|r''}}; otherwise, use ''{{mvar|b''}}+1 bits to encode ''{{mvar|r''}}. Clearly, <math>b=\log_2(M)</math> if ''{{mvar|M''}} is a power of 2 and we can encode all values of ''{{mvar|r''}} with ''{{mvar|b''}} bits.
The integer ''{{mvar|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 ''{{mvar|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>{{mvar|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>
| 