Exponential-Golomb coding
Encyclopedia
An exponential-Golomb code (or just Exp-Golomb code) of order k is a type of universal code
Universal code (data compression)
In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic , the expected lengths of the codewords are...

, parameterized by a nonnegative integer k. To encode a nonnegative integer in an order-k exp-Golomb code, one can use the following method:
  1. Take the number in binary except for the last k digits and add 1 to it (arithmetically). Write this down.
  2. Count the bits written, subtract one, and write that number of starting zero bits preceding the previous bit string.
  3. Write the last k bits in binary.


For k = 0 the code begins:
0 => 1 => 1
1 => 10 => 010
2 => 11 => 011
3 => 100 => 00100
4 => 101 => 00101
5 => 110 => 00110
6 => 111 => 00111
7 => 1000 => 0001000
8 => 1001 => 0001001
...

Exp-Golomb coding for k = 0 is used in the H.264/MPEG-4 AVC
H.264/MPEG-4 AVC
H.264/MPEG-4 Part 10 or AVC is a standard for video compression, and is currently one of the most commonly used formats for the recording, compression, and distribution of high definition video...

 video compression standard, in which there is also a variation for the coding of signed numbers by assigning the value 0 to the binary codeword '0' and assigning subsequent codewords to input values of increasing magnitude (and alternating sign, if the field can contain a negative number).

Exp-Golomb coding is also used in the Dirac video codec.

The k = 0 exp-Golomb code is identical to the Elias gamma code
Elias gamma coding
Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.-Encoding:To code a number:#Write it in binary....

 of the same number plus one. Thus it can encode zero, whereas Elias gamma can only encode numbers greater than zero.

See also

  • Elias gamma coding
    Elias gamma coding
    Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.-Encoding:To code a number:#Write it in binary....

  • Elias delta coding
    Elias delta coding
    Elias delta code is a universal code encoding the positive integers developed by Peter Elias. To code a number:#Write it in binary.#Count the bits and write down that number of bits in binary ....

  • Elias omega coding
    Elias omega coding
    Elias omega coding is a universal code encoding the positive integers developed by Peter Elias. Like Elias gamma coding and Elias delta coding, it works by prefixing the integer with a representation of its order of magnitude in a universal code...

  • Universal code
    Universal code (data compression)
    In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic , the expected lengths of the codewords are...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK