Editing Golomb coding (section)

== Use for run-length encoding ==

:''Note that {{mvar|p}} and {{math|1 – p}} are reversed in this section compared to the use in earlier sections.''

Given an alphabet of two symbols, or a set of two events, ''P'' and ''Q'', with probabilities ''p'' and ({{math|1 &minus; ''p''}}) respectively, where {{math|''p'' ≥ 1/2}}, Golomb coding can be used to encode runs of zero or more ''P''&prime;s separated by single ''Q''&prime;s. In this application, the best setting of the parameter ''M'' is the nearest integer to <math>- \frac{1}{\log_{2}p}</math>.  When ''p'' = 1/2, ''M'' = 1, and the Golomb code corresponds to unary ({{math|''n'' ≥ 0}} ''P''&prime;s followed by a ''Q'' is encoded as ''n'' ones followed by a zero).  If a simpler code is desired, one can assign Golomb–Rice parameter {{mvar|b}} (i.e., Golomb parameter <math>M=2^b</math>) to the integer nearest to <math>- \log_2(-\log_2 p)</math>; although not always the best parameter, it is usually the best Rice parameter and its compression performance is quite close to the optimal Golomb code.  (Rice himself proposed using various codes for the same data to figure out which was best.  A later [[Jet Propulsion Laboratory|JPL]] researcher proposed various methods of optimizing or estimating the code parameter.<ref>{{Cite tech report | last1 = Kiely | first1 = A. | title = Selecting the Golomb Parameter in Rice Coding | number = 42-159 | institution = [[Jet Propulsion Laboratory]] | year = 2004}}</ref>)

Consider using a Rice code with a binary portion having {{mvar|b}} bits to run-length encode sequences where ''P'' has a probability {{mvar|p}}.  If <math>\mathbb{P}[\text{bit is part of }k\text{-run}]</math> is the probability that a bit will be part of an {{mvar|k}}-bit run (<math>k-1</math> ''P''s and one ''Q'') and <math>(\text{compression ratio of }k\text{-run})</math> is the compression ratio of that run, then the expected compression ratio is
<!-- below mostly comes from above reference (Kiely), but not exactly, so leave uncited for now -->
:<math>\begin{align}
\mathbb{E}[\text{compression ratio}]
&= \sum_{k=1}^\infty (\text{compression ratio of }k\text{-run}) \cdot \mathbb{P}[\text{bit is part of }k\text{-run}] \\
&= \sum_{k=1}^\infty \frac{b+1+\lfloor 2^{-b}(k-1) \rfloor}{k} \cdot kp^{k-1} (1-p)^2  \\
&= (1-p)^2 \sum_{j=0}^\infty (b+1+j) \cdot \sum_{i=j2^b+1}^{(j+1)2^b} p^{i-1} \\
&= (1-p)^2 \sum_{j=0}^\infty (b+1+j) \cdot \left(p^{2^b j} - p^{2^{b} (j+1)}\right) \\
&= (1-p) \cdot \left (b + \sum_{m=0}^\infty p^{2^b m} \right ) \\
&= (1-p) \cdot \left(b + {\left (1-p^{2^b} \right )}^{-1}\right ) \\
\end{align}</math>

Compression is often expressed in terms of <math>1-\mathbb{E}[\text{compression ratio}]</math>, the proportion compressed.  For <math>p \approx 1</math>, the run-length coding approach results in compression ratios close to [[Entropy (information theory)|entropy]].  For example, using Rice code <math>b=6</math> for <math>p=0.99</math> yields {{val|91.89|u=%}} compression, while the entropy limit is {{val|91.92|u=%}}.