Exponential-Golomb coding: Difference between revisions

Revision as of 14:37, 19 April 2012

Latest revision as of 16:47, 7 June 2025

(18 intermediate revisions by 15 users not shown)

Line 1:

{{distinguish|Golomb coding}}

An '''exponential-Golomb code''' (or just '''Exp-Golomb code''') of order ''k'' is a type of [[Universal code (data compression)|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.

An '''exponential-Golomb code''' (or just '''Exp-Golomb code''') of order ''k'' is a type of [[Universal code (data compression)|universal code]],. parameterized byTo aencode any [[nonnegative integer]]  ''kx''. using Tothe encode a nonnegative integer in an order-''k'' exp-Golomb code, one can use the following method:

# Write the lastdown ''kx'' bits+1 in binary.

# 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.

ForThe ''k''first =few 0values of the code beginsare:

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

...<ref name="richardson"/>

In the above examples, consider the case 3. For 3, x+1 = 3 + 1 = 4. 4 in binary is '100'. '100' has 3 bits, and 3-1 = 2. Hence add 2 zeros before '100', which is '00100'

Exp-Golomb coding for ''k''&nbsp;=&nbsp;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

...<ref name="richardson">{{cite book|last=Richardson|first=Iain|title=The H.264 Advanced Video Compression Standard|year=2010|publisher=Wiley|isbn=978-0470516928|pages=208,221|url=http://books.google.com/books?id=LJoDiPnBzQ8C&lpg=PA208&dq=Exponential-Golomb%20coding&pg=PA221#v=onepage&q=Exponential-Golomb%20coding&f=false}}</ref>

Similarly, consider 8. '8 + 1' in binary is '1001'. '1001' has 4 bits, and 4-1 is 3. Hence add 3 zeros before 1001, which is '0001001'.

Exp-Golomb coding is also used in the [[Dirac (video compression format)|Dirac video codec]].<ref>{{cite web|title=Dirac Specification|url=http://diracvideo.org/download/specification/dirac-spec-latest.pdf|publisher=BBC|accessdate=9 March 2011}}</ref>

The ''k''&nbsp;=&nbsp;0 exp-Golomb codeThis is identical to the [[Elias gamma coding|Elias gamma code]] of the same number plus one''x''+1, (allowing it to encode 0).<ref>{{cite book |last = Rupp |first = Markus |title = Video and Multimedia Transmissions over Cellular Networks: Analysis, Modelling and Optimization in Live 3G Mobile Networks |year = 2009 |publisher = Wiley |pages = 149 |isbn = 9780470747766 |url =http https://books.google.com/books?id=H9hUBT-JvUoC&lpg=PA149&dqq=Exponential-Golomb%20coding+coding&pg=PA149#v=onepage&q=Exponential-Golomb%20coding&f=false }}</ref>

==Extension to negative numbers==

Exp-Golomb coding for ''k''&nbsp;=&nbsp;0 is used in the [[H.264/MPEG-4 AVC]] and H.265 [[High Efficiency Video Coding]] video compression standardstandards, 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−2 =>⇒ 4 ⇒ 101 =>⇒ 00101

3 =>⇒ 5 ⇒ 110 =>⇒ 00110

-3−3 =>⇒ 6 ⇒ 111 =>⇒ 00111

4 =>⇒ 7 ⇒ 1000 =>⇒ 0001000

-4−4 =>⇒ 8 ⇒ 1001 =>⇒ 0001001

...<ref name="richardson">{{cite book |last = Richardson |first = Iain |title = The H.264 Advanced Video Compression Standard |year = 2010 |publisher = Wiley |isbn = 978-04705169280-470-51692-8 |pages = 208, 221 |url =http https://books.google.com/books?id=LJoDiPnBzQ8C&lpg=PA208&dqq=Exponential-Golomb%20coding+coding&pg=PA221#v=onepage&q=Exponential-Golomb%20coding&f=false }}</ref>

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

Exp-Golomb coding is also used in the [[Dirac (video compression format)|Dirac video codec]].<ref>{{cite web |title = Dirac Specification |url = http://diracvideo.org/download/specification/dirac-spec-latest.pdf |publisher = BBC |accessdateaccess-date = 9 March 2011 |url-status = usurped |archive-url = https://web.archive.org/web/20150503015104/http://diracvideo.org/download/specification/dirac-spec-latest.pdf |archive-date = 2015-05-03 }}</ref>

==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 &nbsp;''k''. To encode a nonnegative integer ''x'' in an order-''k''&nbsp;exp-Golomb code:

# Encode ⌊''x''/2^''k''⌋ using order-0 exp-Golomb code described above, then

# Encode ''x'' mod 2^''k'' in binary with k bits

An equivalent way of expressing this is:

# Encode ''x''+2^''k''−1 using the order-0 exp-Golomb code (i.e. encode ''x''+2^''k'' using the Elias gamma code), then

# Delete ''k'' leading zero bits from the encoding result

{|class=wikitable

|+ Exp-Golomb-''k'' coding examples

! &nbsp;''x''&nbsp; || ''k''=0 || ''k''=1 || ''k''=2 ||''k''=3

|rowspan=11|

! &nbsp;''x''&nbsp; || ''k''=0 || ''k''=1 || ''k''=2 ||''k''=3

|rowspan=11|

! &nbsp;''x''&nbsp; || ''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==

*[[Elias gamma coding|Elias gamma (γ) coding]]

*[[Elias delta coding|Elias delta (δ) coding]]

*[[Elias omega coding|Elias omega (ω) coding]]

*[[Universal code (data compression)|Universal code]]

Line 44 ⟶ 109:

{{DEFAULTSORT:Exponential-Golomb Coding}}

[[Category:Entropy coding]]

[[Category:Numeral systems]]

[[Category:LosslessData compression algorithms]]

[[fr:Code exponentiel-Golomb]]

[[ru:Экспоненциальный код Голомба]]

[[zh:指数哥伦布码]]