Exponential-Golomb coding

From Wikipedia, the free encyclopedia
Jump to: navigation, search

An exponential-Golomb code (or just Exp-Golomb code) of order k is a type of universal code, 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
...[1]

Exp-Golomb coding for k = 0 is used in the H.264/MPEG-4 AVC 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):

 0 => 1 => 1
 1 => 10 => 010
-1 => 11 => 011
 2 => 100 => 00100
-2 => 101 => 00101
 3 => 110 => 00110
-3 => 111 => 00111
 4 => 1000 => 0001000
-4 => 1001 => 0001001
...[1]

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

The k = 0 exp-Golomb code is identical to the Elias gamma code of the same number plus one (allowing it to encode 0).[3]

See also[edit]

References[edit]