Exponential-Golomb coding: Difference between revisions

Revision as of 04:13, 12 December 2014

Latest revision as of 16:47, 7 June 2025

(15 intermediate revisions by 13 users not shown)

Line 1:

{{distinguish|Golomb coding}}

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:

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.

Line 5 ⟶ 7:

The first few values of the code are:

0 ⇒ 1 ⇒ 1

1 ⇒ 10 ⇒ 010 in a variable nubmer

2 ⇒ 11 ⇒ 011

3 ⇒ 100 ⇒ 00100

Line 15 ⟶ 17:

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

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|url=http://books.google.com/books?id=H9hUBT-JvUoC&lpg=PA149&dq=Exponential-Golomb%20coding&pg=PA149#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'.

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

Line 28 ⟶ 34:

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

Line 92 ⟶ 98:

==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 103 ⟶ 109:

{{DEFAULTSORT:Exponential-Golomb Coding}}

[[Category:Entropy coding]]

[[Category:Numeral systems]]

[[Category:LosslessData compression algorithms]]