Login
Login

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

...

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.{{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 }}

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

...{{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 }}

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.{{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 }}

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 with k bits

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

class=wikitable

|+ Exp-Golomb-k coding examples

!  x 

k=0k=1k=2k=3

|rowspan=11|

!  x 

k=0k=1k=2k=3

|rowspan=11|

!  x 

k=0k=1k=2k=3
01101001000

| 10

000101100110001110010010

| 20

000010101000101100011000011100
1010111011001

| 11

000110000110101111010011

| 21

000010110000101110011001011101
201101001101010

| 12

00011010011100010000010100

| 22

000010111000110000011010011110
30010001011111011

| 13

00011100011110010001010101

| 23

000011000000110010011011011111
4001010110010001100

| 14

0001111000100000010010010110

| 24

00001100100011010001110000100000
5001100111010011101

| 15

000010000000100010010011010111

| 25

00001101000011011001110100100001
600111001000010101110

| 16

000010001000100100010100011000

| 26

00001101100011100001111000100010
70001000001001010111111

| 17

000010010000100110010101011001

| 27

00001110000011101001111100100011
8000100100101001100010000

| 18

000010011000101000010110011010

| 28

0000111010001111000010000000100100
9000101000101101101010001

| 19

000010100000101010010111011011

| 29

0000111100001111100010000100100101

See also

References

{{Reflist}}

{{Compression Methods}}

{{DEFAULTSORT:Exponential-Golomb Coding}}

Category:Entropy coding

Category:Numeral systems

Category:Data compression