This sectionneeds additional citations forverification. Relevant discussion may be found on thetalk page. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed. Find sources: "Golomb coding" – news ·newspapers ·books ·scholar ·JSTOR(October 2024) (Learn how and when to remove this message)

Golomb coding is alossless data compression method using a family ofdata compression codes invented bySolomon W. Golomb in the 1960s. Alphabets following ageometric distribution will have a Golomb code as an optimalprefix code,^[1] making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.

Rice coding (invented byRobert F. Rice) denotes using a subset of the family of Golomb codes to produce a simpler (but possibly suboptimal) prefix code. Rice used this set of codes in anadaptive coding scheme; "Rice coding" can refer either to that adaptive scheme or to using that subset of Golomb codes. Whereas a Golomb code has a tunable parameter that can be any positive integer value, Rice codes are those in which the tunable parameter is a power of two. This makes Rice codes convenient for use on a computer, since multiplication and division by 2 can be implemented more efficiently inbinary arithmetic.

Rice was motivated to propose this simpler subset due to the fact that geometric distributions are often varying with time, not precisely known, or both, so selecting the seemingly optimal code might not be very advantageous.

Rice coding is used as theentropy encoding stage in a number of losslessimage compression andaudio data compression methods.

Golomb coding uses a tunable parameterM to divide an input valuex into two parts:q, the result of a division byM, andr, the remainder. The quotient is sent inunary coding, followed by the remainder intruncated binary encoding. When${\displaystyle M=1}$, Golomb coding is equivalent to unary coding.

Golomb–Rice codes can be thought of as codes that indicate a number by the position of thebin (q), and theoffset within thebin (r). The example figure shows the positionq and offsetr for the encoding of integerx using Golomb–Rice parameterM = 3, with source probabilities following a geometric distribution withp(0) = 0.2.

Formally, the two parts are given by the following expression, wherex is the nonnegative integer being encoded:

$${\displaystyle q=\lfloor \frac{x}{M}\rfloor }$$

and

$${\displaystyle r=x-qM.}$$

Bothq andr will be encoded using variable numbers of bits:q by a unary code, andr byb bits for Rice code, or a choice betweenb andb+1 bits for Golomb code (i.e.M is not a power of 2), with${\displaystyle b=\lfloor {\log }_2(M)\rfloor }$. If, then useb bits to encoder; otherwise, useb+1 bits to encoder. Clearly,${\displaystyle b={\log }_2(M)}$ ifM is a power of 2 and we can encode all values ofr withb bits.

The integerx treated by Golomb was the run length of aBernoulli process, which has ageometric distribution starting at 0. The best choice of parameterM is a function of the corresponding Bernoulli process, which is parameterized by${\displaystyle p=P(x=0)}$ the probability of success in a givenBernoulli trial.M is either the median of the distribution or the median ±1. It can be determined by these inequalities:which are solved by$${\displaystyle M=\lceil -\frac{\log (2-p)}{\log (1-p)}\rceil .}$$

For the example withp(0) = 0.2:$${\displaystyle M=\lceil -\frac{\log (1.8)}{\log (0.8)}\rceil =\lceil 2.634\rceil =3.}$$

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

Golomb's scheme was designed to encode sequences of non-negative numbers. However, it is easily extended to accept sequences containing negative numbers using anoverlap 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, ... Then-th negative value (i.e.,⁠${\displaystyle -n}$⁠) is mapped to then^th odd number (⁠${\displaystyle 2n-1}$⁠), and them^th positive value is mapped to them-th even number (⁠${\displaystyle 2m}$⁠). This may be expressed mathematically as follows: a positive valuex is mapped to (${\displaystyle x^{\prime }=2|x|=2x,x\ge 0}$), and a negative valuey is mapped to (). 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.^[2]

Below is the Rice–Golomb encoding, where the remainder code uses simple truncated binary encoding, also named "Rice coding" (other varying-length binary encodings, like arithmetic or Huffman encodings, are possible for the remainder codes, if the statistic distribution of remainder codes is not flat, and notably when not all possible remainders after the division are used). In this algorithm, if theM parameter is a power of 2, it becomes equivalent to the simpler Rice encoding:

1. Fix the parameterM to an integer value.
2. ForN, the number to be encoded, find
   1. quotient =q = floor(N/M)
   2. remainder =r =N moduloM
3. Generate codeword
   1. The code format : <Quotient code><Remainder code>, where
   2. Quotient code (inunary coding)
      1. Write aq-length string of 1 bits (alternatively, of 0 bits)
      2. Write a 0 bit (respectively, a 1 bit)
   3. Remainder code (intruncated binary encoding)
      1. Let${\displaystyle b=\lfloor {\log }_2(M)\rfloor }$
         1. If coder in binary representation usingb bits.
         2. If${\displaystyle r\ge 2^{b+1}-M}$ code the number${\displaystyle r+2^{b+1}-M}$ in binary representation usingb + 1 bits.

Decoding:

1. Decode the unary representation ofq (count the number of 1 in the beginning of the code)
2. Skip the 0 delimiter
3. Let${\displaystyle b=\lfloor {\log }_2(M)\rfloor }$
   1. Interpret nextb bits as a binary numberr'. If holds, then the remainder${\displaystyle r=r^{\prime }}$
   2. Otherwise interpretb + 1 bits as a binary numberr', the remainder is given by${\displaystyle r=r^{\prime }-2^{b+1}+M}$
4. Compute${\displaystyle N=q\ast M+r}$

SetM = 10. Thus${\displaystyle b=\lfloor {\log }_2(10)\rfloor =3}$. The cutoff is${\displaystyle 2^{b+1}-M=16-10=6}$.

Encoding of quotient part q output bits 0 0 1 10 2 110 3 1110 4 11110 5 111110 6 1111110 ${\displaystyle ⋮}$ ${\displaystyle ⋮}$ N ${\displaystyle \underset{N}{\underbrace{111\cdots 111}}0}$

Encoding of remainder part r offset binary output bits 0 0 0000 000 1 1 0001 001 2 2 0010 010 3 3 0011 011 4 4 0100 100 5 5 0101 101 6 12 1100 1100 7 13 1101 1101 8 14 1110 1110 9 15 1111 1111

For example, with a Rice–Golomb encoding using parameterM = 10, the decimal number 42 would first be split intoq = 4 andr = 2, and would be encoded as qcode(q),rcode(r) = qcode(4),rcode(2) = 11110,010 (you don't need to encode the separating comma in the output stream, because the 0 at the end of theq code is enough to say whenq ends andr begins; both the qcode and rcode are self-delimited).

Note thatp and1 – 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 andQ, with probabilitiesp and (1 −p) respectively, wherep ≥ 1/2, Golomb coding can be used to encode runs of zero or moreP′s separated by singleQ′s. In this application, the best setting of the parameterM is the nearest integer to${\displaystyle -\frac{1}{{\log }_{2}p}}$. Whenp = 1/2,M = 1, and the Golomb code corresponds to unary (n ≥ 0P′s followed by aQ is encoded asn ones followed by a zero). If a simpler code is desired, one can assign Golomb–Rice parameterb (i.e., Golomb parameter${\displaystyle M=2^b}$) to the integer nearest to${\displaystyle -{\log }_2(-{\log }_{2}p)}$; 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 laterJPL researcher proposed various methods of optimizing or estimating the code parameter.^[3])

Consider using a Rice code with a binary portion havingb bits to run-length encode sequences whereP has a probabilityp. If${\displaystyle \mathbb{P}[\text{bit is part of }k\text{-run}]}$ is the probability that a bit will be part of ank-bit run (${\displaystyle k-1}$Ps and oneQ) and${\displaystyle (\text{compression ratio of }k\text{-run})}$ is the compression ratio of that run, then the expected compression ratio is

Compression is often expressed in terms of${\displaystyle 1-\mathbb{E}[\text{compression ratio}]}$, the proportion compressed. For${\displaystyle p\approx 1}$, the run-length coding approach results in compression ratios close toentropy. For example, using Rice code${\displaystyle b=6}$ for${\displaystyle p=0.99}$ yields91.89% compression, while the entropy limit is91.92%.

When a probability distribution for integers is not known, the optimal parameter for a Golomb–Rice encoder cannot be determined. Thus, in many applications, a two-pass approach is used: first, the block of data is scanned to estimate a probability density function (PDF) for the data. The Golomb–Rice parameter is then determined from that estimated PDF. A simpler variation of that approach is to assume that the PDF belongs to a parametrized family, estimate the PDF parameters from the data, and then compute the optimal Golomb–Rice parameter. That is the approach used in most of the applications discussed below.

An alternative approach to efficiently encode integer data whose PDF is not known, or is varying, is to use a backwards-adaptive encoder. The RLGR encoder[1] achieves that using a very simple algorithm that adjusts the Golomb–Rice parameter up or down, depending on the last encoded symbol. A decoder can follow the same rule to track the variation of the encoding parameters, so no side information needs to be transmitted, just the encoded data. Assuming a generalized Gaussian PDF, which covers a wide range of statistics seen in data such as prediction errors or transform coefficients in multimedia codecs, the RLGR encoding algorithm can perform very well in such applications.

Numerous signal codecs use a Rice code forprediction residues.In predictive algorithms, such residues tend to fall into a two-sidedgeometric distribution, with small residues being more frequent than large residues, and the Rice code closely approximates the Huffman code for such a distribution without the overhead of having to transmit the Huffman table.One signal that does not match a geometric distribution is asine wave, because the differential residues create a sinusoidal signal whose values are not creating a geometric distribution (the highest and lowest residue values have similar high frequency of occurrences, only the median positive and negative residues occur less often).

Several losslessaudio codecs, such asShorten,^[4]FLAC,^[5]Apple Lossless, andMPEG-4 ALS, use a Rice code after thelinear prediction step (called "adaptive FIR filter" in Apple Lossless).Rice coding is also used in theFELICS lossless image codec.

The Golomb–Rice coder is used in the entropy coding stage ofRice algorithm basedlossless image codecs. One such experiment yields the compression ratio graph shown.

TheJPEG-LS scheme uses Rice–Golomb to encode the prediction residuals.

The adaptive version of Golomb–Rice coding mentioned above, the RLGR encoder[2],is used for encoding screen content in virtual machines in theRemoteFX component of the Microsoft Remote Desktop Protocol.

• Elias delta coding
• Variable-length code
• Exponential-Golomb coding

• Golomb, Solomon W. (1966).Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
• Rice, Robert F.; Plaunt, R. (1971). "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data".IEEE Transactions on Communications.16 (9):889–897.Bibcode:1971ITCoT..19..889R.doi:10.1109/TCOM.1971.1090789.
• Robert F. Rice (1979), "Some Practical Universal Noiseless Coding Techniques", Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79—22, March 1979.
• Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999ISBN 1-55860-570-3
• David Salomon. "Data Compression",ISBN 0-387-95045-1.
• H. S. Malvar,Adaptive run-length/Golomb–Rice encoding of quantized generalized Gaussian sources with unknown statistics, Proc. Data Compression Conference, 2006.
• RLGR Entropy Encoding, Microsoft MS-RDPRFX Open Specification, RemoteFX codec for Remote Desktop Protocol.
• S. Büttcher, C. L. A. Clarke, and G. V. Cormack.Information Retrieval: Implementing and Evaluating Search EnginesArchived 2020-10-05 at theWayback Machine. MIT Press, Cambridge MA, 2010.

• Entropy coding
• Data compression

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from October 2024
• All articles needing additional references
• Webarchive template wayback links