Editing Golomb coding (section)

== Overview ==
[[File:Golomb code example.png|thumb|upright 1.5|Golomb coding example for a source x with geometric distribution, with parameter {{math|''p''(0) {{=}} 0.2}}, using Golomb code with {{math|''M'' {{=}} 3}}.  The 2-bit code 00 is used 20% of the time; the 3-bit codes 010, 011, and 100 are used over 38% of the time; 4 bits or more are needed in a minority of cases.  For this source, entropy = 3.610 bits; for this code with this source, rate = 3.639 bits; therefore redundancy = 0.030 bits, or efficiency = 0.992 bits per bit.]]

===Construction of codes===

Golomb coding uses a tunable parameter {{mvar|M}} to divide an input value {{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.

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 example figure shows the position {{mvar|q}} and offset {{mvar|r}} for the encoding of integer {{mvar|x}} using Golomb–Rice parameter {{math|''M'' {{=}} 3}}, with source probabilities following a geometric distribution with {{math|''p''(0) {{=}} 0.2}}.

Formally, the two parts are given by the following expression, where {{mvar|x}} is the nonnegative integer being encoded:

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

and

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

[[File:GolombCodeRedundancy.svg|thumb|upright 1.5|This image shows the redundancy, in bits, of the Golomb code, when {{mvar|M}} is chosen optimally, for {{math| 1 − ''p''(0) &ge; 0.45}}]]

Both {{mvar|q}} and {{mvar|r}} will be encoded using variable numbers of bits: {{mvar|q}} by a unary code, and {{mvar|r}} by {{mvar|b}} bits for Rice code, or a choice between {{mvar|b}} and {{math|{{var|b}}+1}} bits for Golomb code (i.e. {{mvar|M}} is not a power of 2), with <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]]. {{mvar|M}} 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>
which are solved by 
: <math>M = \left\lceil -\frac{\log(2 -p)}{\log(1-p)}\right\rceil</math>.

For the example with {{math|''p''(0) {{=}} 0.2}}:
: <math>M = \left\lceil -\frac{\log(1.8)}{\log(0.8)}\right\rceil  = \left\lceil 2.634 \right\rceil = 3</math>.

The Golomb code for this distribution is equivalent to the [[Huffman code]] for the same probabilities, if it were possible to compute the Huffman code for the infinite set of source values.

===Use with signed integers===

Golomb's scheme was designed to encode sequences of non-negative numbers. However, it is easily extended to accept sequences containing negative numbers using an ''overlap and interleave'' scheme, in which all values are reassigned to some positive number in a unique and reversible way. The sequence begins: 0, −1, 1, −2, 2, −3, 3, −4, 4,&nbsp;... The ''n''-th negative value (i.e., {{tmath|-n}}) is mapped to the ''n''<sup>th</sup> odd number ({{tmath|2n-1}}), and the ''m''<sup>th</sup> positive value is mapped to the ''m''-th even number ({{tmath|2m}}). This may be expressed mathematically as follows: a positive value {{mvar|x}} is mapped to (<math>x' = 2|x| = 2x,\ x \ge 0</math>), and a negative value {{mvar|y}} is mapped to (<math>y' = 2|y| - 1 = -2y - 1,\ y < 0</math>). Such a code may be used for simplicity, even if suboptimal. Truly optimal codes for two-sided geometric distributions include multiple variants of the Golomb code, depending on the distribution parameters, including this one.<ref>{{Cite journal | last1 = Merhav | first1 = N. | last2 = Seroussi | first2 = G. | last3 = Weinberger | first3 = M. J. | title = Coding of sources with two-sided geometric distributions and unknown parameters | journal = [[IEEE Transactions on Information Theory]]| volume = 46 | issue = 1 | pages = 229–236 | year = 2000 | doi=10.1109/18.817520}}</ref>