World Library  
Flag as Inappropriate
Email this Article

Exponential-Golomb coding

Article Id: WHEBN0007167202
Reproduction Date:

Title: Exponential-Golomb coding  
Author: World Heritage Encyclopedia
Language: English
Subject: Elias gamma coding, Compression methods, Context tree weighting, Byte pair encoding, Elias delta coding
Collection: Lossless Compression Algorithms, Numeral Systems
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Exponential-Golomb coding

An exponential-Golomb code (or just Exp-Golomb code) is a type of universal code. To encode any nonnegative integer x using the exp-Golomb code:

  1. Write down x+1 in binary
  2. Count the bits written, subtract one, and write that number of starting zero bits preceding the previous bit string.

The first few values of the code are:

 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]

This is identical to the Elias gamma code of x+1, allowing it to encode 0.[2]

Contents

  • Extension to negative numbers 1
  • Generalization to order k 2
  • See also 3
  • References 4

Extension to negative numbers

Exp-Golomb coding for k = 0 is used in the H.264/MPEG-4 AVC and H.265 High Efficiency Video Coding video compression standards, 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 ⇒ 0 ⇒ 1 ⇒ 1
 1 ⇒ 1 ⇒ 10 ⇒ 010
−1 ⇒ 2 ⇒ 11 ⇒ 011
 2 ⇒ 3 ⇒ 100 ⇒ 00100
−2 ⇒ 4 ⇒ 101 ⇒ 00101
 3 ⇒ 5 ⇒ 110 ⇒ 00110
−3 ⇒ 6 ⇒ 111 ⇒ 00111
 4 ⇒ 7 ⇒ 1000 ⇒ 0001000
−4 ⇒ 8 ⇒ 1001 ⇒ 0001001
...[1]

In other words, a non-positive integer x≤0 is mapped to an even integer −2x, while a positive integer x>0 is mapped to an odd integer 2x−1.

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

Generalization to order k

To encode larger numbers in fewer bits (at the expense of using more bits to encode smaller numbers), this can be generalized using a nonnegative integer parameter  k. To encode a nonnegative integer x in an order-k exp-Golomb code:

  1. Encode ⌊x/2k⌋ using order-0 exp-Golomb code described above, then
  2. Encode x mod 2k in binary

An equivalent way of expressing this is:

  1. Encode x+2k−1 using the order-0 exp-Golomb code (i.e. encode x+2k) using the Elias gamma code), then
  2. Delete k leading zero bits from the encoding result
Exp-Golomb-k coding examples
 x  k=0 k=1 k=2 k=3  x  k=0 k=1 k=2 k=3  x  k=0 k=1 k=2 k=3
0 1 10 100 1000 10 0001011 001100 01110 010010 20 000010101 00010110 0011000 011100
1 010 11 101 1001 11 0001100 001101 01111 010011 21 000010110 00010111 0011001 011101
2 011 0100 110 1010 12 0001101 001110 0010000 010100 22 000010111 00011000 0011010 011110
3 00100 0101 111 1011 13 0001110 001111 0010001 010101 23 000011000 00011001 0011011 011111
4 00101 0110 01000 1100 14 0001111 00010000 0010010 010110 24 000011001 00011010 0011100 00100000
5 00110 0111 01001 1101 15 000010000 00010001 0010011 010111 25 000011010 00011011 0011101 00100001
6 00111 001000 01010 1110 16 000010001 00010010 0010100 011000 26 000011011 00011100 0011110 00100010
7 0001000 001001 01011 1111 17 000010010 00010011 0010101 011001 27 000011100 00011101 0011111 00100011
8 0001001 001010 01100 010000 18 000010011 00010100 0010110 011010 28 000011101 00011110 000100000 00100100
9 0001010 001011 01101 010001 19 000010100 00010101 0010111 011011 29 000011110 00011111 000100001 00100101

See also

References

  1. ^ a b Richardson, Iain (2010). The H.264 Advanced Video Compression Standard. Wiley. pp. 208,221.  
  2. ^ Rupp, Markus (2009). Video and Multimedia Transmissions over Cellular Networks: Analysis, Modelling and Optimization in Live 3G Mobile Networks. Wiley. p. 149. 
  3. ^ "Dirac Specification" (PDF). BBC. Retrieved 9 March 2011. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.