Content deleted Content added
Citation bot (talk | contribs) Alter: url. URLs might have been internationalized/anonymized. Add: isbn. Upgrade ISBN10 to ISBN13. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked 1273/2125 |
Add distinguish from Golomb coding |
||
(6 intermediate revisions by 6 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:
# Write down ''x''+1 in binary
Line 14 ⟶ 16:
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>
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 = 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''>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 |
==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:
# Encode ⌊''x''/2<sup>''k''</sup>⌋ using order-0 exp-Golomb code described above, then
# Encode ''x'' mod 2<sup>''k''</sup> in binary with k bits
An equivalent way of expressing this is:
# Encode ''x''+2<sup>''k''</sup>−1 using the order-0 exp-Golomb code (i.e. encode ''x''+2<sup>''k''</sup> using the Elias gamma code), then
Line 103 ⟶ 109:
{{DEFAULTSORT:Exponential-Golomb Coding}}
[[Category:Entropy coding]]
[[Category:Numeral systems]]
[[Category:
|