Golomb coding: Difference between revisions

Revision as of 19:11, 24 February 2023

Revision as of 02:31, 25 July 2023

Line 137:

:''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 techreporttech 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