Golomb coding

From Wikipedia, the free encyclopedia

Golomb coding is a form of entropy encoding invented by Solomon W. Golomb that is optimal for alphabets following geometric distributions, that is, when small values are vastly more common than large values. If negative values are present in the input stream then a overlap and interleave scheme is used, where all non-negative inputs are mapped to even numbers ( $x^\prime=2|x|=2x, x\ge0$ ), and all negative numbers are mapped to odd numbers ( $x^\prime=2|x|+1=-2x+1, x<0$ ).

Golomb coding can also be used (as in Golomb's original article) to encode an alphabet of two symbols, where one is more likely than the other. In this case it can be thought of as a kind of run-length encoding.

Rice coding is a special case of Golomb coding first described by, and independently invented by, Robert F. Rice. It is equivalent to Golomb coding where the tunable parameter is a power of two. This makes it extremely efficient for use on computers, since the division operation becomes a bitshift operation and the remainder operation becomes a bitmask operation.

Rice coding is used as the entropy encoding stage in a number of lossless image compression and audio data compression methods.

1 Overview
2 Simple Algorithm
3 Example
4 Example code
- 4.1 Encoding
- 4.2 Decoding
5 Use for Run-Length Encoding
6 Applications
7 References

[edit] Overview

Golomb coding uses a tunable parameter M to divide an input value into two parts: $q$ , the result of a division by M, and $r$ , the remainder. The quotient is sent in unary coding, followed by the remainder in truncated binary encoding. When $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 the bin (q), and the offset within the bin (r). The above figure shows the position q, and offset r for the encoding of integer N using Golomb-Rice parameter M.

Formally, the two parts are given by the following expression, where $x$ is the number being encoded: $q = \left \lfloor \frac{\left (x-1 \right )}{M} \right \rfloor$ and $r = x - q M - 1$ The final result looks like: $\left (q+1 \right ) r$

Note that $r$ can be of a varying number of bits, and is specifically only b bits for Rice code, and switches between b-1 and b bits for Golomb code (i.e M is not a power of 2): Let $b = \lceil\log_2(M)\rceil$ . If $0 \leq r < 2^b-M$ , then use b-1 bits to encode r. If $2^b-M \leq r < M$ , then use b bits to encode r. Clearly, $b = log 2 (M)$ if M is a power of 2 and we can encode all values of r with b bits.

The parameter M is a function of the corresponding Bernoulli process, which is parameterized by $p = P (X = 0)$ the probability of success in a given Bernoulli Trial. $M$ and $p$ are related by these inequalities:

$(1-p)^M + (1-p)^{M+1} \leq 1 < (1-p)^{M-1} + (1-p)^M$

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.

[edit] Simple Algorithm

Note below that this 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 the M parameter is a power of 2, it becomes equivalent to the simpler Golomb encoding.

Fix the parameter M to an integer value.
For N, the number to be encoded, find
1. quotient = q = int[N/M]
2. remainder = r = N%M
Generate Codeword
1. The Code format : <Quotient Code><Remainder Code>, where
2. Quotient Code (in unary coding)
  1. Write a q-length string of 1 bits
  2. Write a 0 bit
3. Remainder Code (in truncated binary encoding)
  1. If M is power of 2, code remainder as binary format. So $log 2 (M)$ bits are needed. (Rice code)
  2. If M is not a power of 2, set
    1. Code the first $2 b - M$ values of r as plain binary using b-1 bits.
    2. Code the rest of the values of r by coding the number $r + 2 b - M$ in plain binary representation using b bits.

[edit] Example

Set M = 10. Thus $b = \lceil\log_2(10)\rceil = 4$ . The cutoff is $2 b - 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
...	111...10

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-Colomb encoding of parameter M=10, the decimal number 42 would first be split into q=4,r=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 the q code is enough to say when q ends and r begins ; both the qcode and rcode are self-delimited).

[edit] Example code

Note: this basic code assumes that the M parameter is a power of 2; it does not implement the case where truncated bit encoding of division remainders will be preferable (when M is not a power of 2, like in the previous example).

[edit] Encoding

void golombEncode(char* source, char* dest, int M)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    int num;
    int c = 0;
    while(intreader.hasLeft())
    {
        num = intreader.getInt();
        int q = num / M;
        for (int i = 0 ; i < q; i++)
            bitwriter.putBit(true);   // write q ones
        bitwriter.putBit(false);      // write one zero
        int v = 1;
        for (int i = 0 ; i < log2(M); i++)
        {
            bitwriter.putBit( v & num );
            v = v << 1;
        }
    }
    bitwriter.close();
    intreader.close();
}

[edit] Decoding

void golombDecode(char* source, char* dest, int M)
{
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    int q = 0;
    int nr = 0;
    while (bitreader.hasLeft())
    {
        while (bitreader.getBit()) q++;     // potentially dangerous with malformed files.
        for (int a = 0; a < log2(M); a++)   // read out the sequential log2(M) bits
            if (bitreader.getBit())
                nr += 1 << a;
        nr += q*M;                          // add the bits and the multiple of M
        intwriter.putInt(nr);               // write out the value
    }
    bitreader.close();
    intwriter.close();
}

[edit] Use for Run-Length Encoding

Given an alphabet of two symbols, or a set of two events, P and Q, with probabilities p and (1-p) respectively, where p >= 1/2, Golomb coding can be used to encode runs of zero or more P's separated by single Q's. In this application, the best setting of the parameter M is the nearest integer to $\frac{-1}{\log_{2}p}$ . When p = 1/2, M = 1, and the Golomb code corresponds to binary (n>=0 ones followed by a zero codes for n P's followed by a Q).

[edit] Applications

The FLAC audio codec uses Rice coding to represent linear prediction residues (because these residues are modeled into a near-geometric distribution, with small residues being more frequent than large residues, and are then encoded with less bits using a predefined Rice-Golomb encoding, without requiring more complex variable-length encodings like Huffmann or arithmetic codings). However, this assumption is wrong for a simple sinusoidal signal, 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 occurences, only the median positive and negative residues occur less often).

Apple's ALAC audio codec uses modfied Rice coding after its Adaptive FIR filter.

The Golomb-Rice coder is used in the entropy coding stage of Rice Algorithm based lossless image codecs. One such experiment yields a compression ratio graph given below. See other entries in this category at the bottom of this page. in those compression, the progresive space differential data yields an alternating suite of positive and negative values around 0, which are remapped to positive-only integers (by doubling the absolute value and adding one if the input is negative), and then Rice-Colomb coding is applied by varying the divisor which remains small.

Note that in those results, the Rice coding may create very long sequences of one-bits for the quotient ; for practical reasons, it is often necessary to limit the total run-length of 1-bits, so a modified version of the Rice-Colomb encoding consists in replacing the long string of one-bits by encoding its length by a recursive Rice-Colomb encoding; this requires reserving some values in addition to of the initial divisor k to allow the necessary distinction.

[edit] References

Golomb, S.W. (1966). , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401
R. F. Rice, "Some Practical Universal Noiseless Coding Techniques, " Jet Propulsion Laboratory, Pasadena, California, JPL Publication 79--22, Mar. 1979.
Witten, Ian Moffat, Alistair Bell, Timothy. "Managing Gigabytes: Compressing and Indexing Documents and Images." Second Edition. Morgan Kaufmann Publishers, San Francisco CA. 1999 ISBN 1-55860-570-3
David Salomon. "Data Compression",ISBN 0-387-95045-1.
http://ese.wustl.edu/class/fl06/ese578/GolombCodingNotes.pdf

Data compression

v • d • e

Lossless compression methods

Theory

Entropy · Complexity · Redundancy

Entropy encoding