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:
- Take the number in binary except for the last k digits and add 1 to it (arithmetically). Write this down.
- Count the bits written, subtract one, and write that number of starting zero bits preceding the previous bit string.
- 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).[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.[3] Thus it can encode zero, whereas Elias gamma can only encode numbers greater than zero.
Despite the similar name, exp-Golomb is only somewhat similar to Golomb coding, which is a type of entropy coding but not a universal code.
See also
References
- ^ a b Richardson, Iain (2010). The H.264 Advanced Video Compression Standard. Wiley. pp. 208, 221. ISBN 978-0470516928.
- ^ "Dirac Specification" (PDF). BBC. Retrieved 9 March 2011.
- ^ Rupp, Markus (2009). Video and Multimedia Transmissions over Cellular Networks: Analysis, Modelling and Optimization in Live 3G Mobile Networks. Wiley. p. 149.