Exponential-Golomb coding: Difference between revisions

Revision as of 23:27, 26 September 2006

Latest revision as of 16:47, 7 June 2025

(42 intermediate revisions by 37 users not shown)

Line 1:

{{distinguish|Golomb coding}}

An '''Exponential-Golomb code''' (or just '''Exp-Golomb code''') of order <math>k</math> is a [[Universal code (data compression)|universal code]], parameterized by a [[whole number]] <math>k</math>. To encode a nonnegative integer in an order-<math>k</math> exp-Golomb code, one can use the following method:

# Write all but the last <math>k</math> bits plus 1 in binary.

An '''exponential-Golomb code''' (or just '''Exp-Golomb code''') is a type of [[Universal code (data compression)|universal code]]. To encode any [[nonnegative integer]] ''x'' using the exp-Golomb code:

# Write down ''x''+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 <math>k</math> bits in binary.

ForThe <math>k=0</math>first few values 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'

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

This is identical to the [[Elias gamma code]] of ''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 = https://books.google.com/books?id=H9hUBT-JvUoC&q=Exponential-Golomb+coding&pg=PA149 }}</ref>

==Extension to negative numbers==

Exp-Golomb coding 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

...<ref name="richardson">{{cite book |last = Richardson |first = Iain |title = The H.264 Advanced Video Compression Standard |year = 2010 |publisher = Wiley |isbn = 978-0-470-51692-8 |pages = 208, 221 |url = https://books.google.com/books?id=LJoDiPnBzQ8C&q=Exponential-Golomb+coding&pg=PA221 }}</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 |access-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''==

Exp-Golomb coding for <math>k=0</math> 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.

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 coding is also used in the [[Dirac (codec)|Dirac video codec]].

|+ 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==

The <math>k=0</math> exp-Golomb code is identical to the Elias gamma code of the same number plus one. Thus it can encode zero, whereas Elias gamma can only encode numbers greater than zero.

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

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

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

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

==References==

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.

{{Reflist}}

{{Compression Methods}}

'''See also:''' [[Elias gamma coding]], [[Elias delta coding]], [[Elias omega coding]]

{{DEFAULTSORT:Exponential-Golomb Coding}}

[[Category:Numeration]]

[[Category:LosslessEntropy compression algorithmscoding]]

[[Category:Numeral systems]]

[[Category:Data compression]]