Exponential-Golomb coding

<h2 id="extension-to-negative-numbers">Extension to negative numbers</h2>
Exp-Golomb coding is used in the <a href="/facts/H.264/MPEG-4_AVC/soCzKcmJ">H.264/MPEG-4 AVC</a> and H.265 <a href="/facts/High_Efficiency_Video_Coding/6gp7DC1a">High Efficiency Video Coding</a> 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
...<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

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 <a href="/facts/Dirac_(video_compression_format)/RJGIIss7">Dirac video codec</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="generalization-to-order-k">Generalization to order k</h2>
To encode larger numbers in fewer bits (at the expense of using more bits to encode smaller numbers), this can be generalized using a <a href="/facts/Nonnegative_integer/u65og8JE">nonnegative integer</a> parameter  k. To encode a nonnegative integer x in an order-k exp-Golomb code:

<ol><li>Encode ⌊x/2k⌋ using order-0 exp-Golomb code described above, then</li>
<li>Encode x mod 2k in binary with k bits</li></ol>
An equivalent way of expressing this is:

<ol><li>Encode x+2k−1 using the order-0 exp-Golomb code (i.e. encode x+2k using the Elias gamma code), then</li>
<li>Delete k leading zero bits from the encoding result</li></ol>
Exp-Golomb-k coding examples<table><tbody><tr><th> x </th><th>k=0</th><th>k=1</th><th>k=2</th><th>k=3</th><td rowspan="11"></td><th> x </th><th>k=0</th><th>k=1</th><th>k=2</th><th>k=3</th><td rowspan="11"></td><th> x </th><th>k=0</th><th>k=1</th><th>k=2</th><th>k=3</th></tr><tr><td>0</td><td>1</td><td>10</td><td>100</td><td>1000</td><td>10</td><td>0001011</td><td>001100</td><td>01110</td><td>010010</td><td>20</td><td>000010101</td><td>00010110</td><td>0011000</td><td>011100</td></tr><tr><td>1</td><td>010</td><td>11</td><td>101</td><td>1001</td><td>11</td><td>0001100</td><td>001101</td><td>01111</td><td>010011</td><td>21</td><td>000010110</td><td>00010111</td><td>0011001</td><td>011101</td></tr><tr><td>2</td><td>011</td><td>0100</td><td>110</td><td>1010</td><td>12</td><td>0001101</td><td>001110</td><td>0010000</td><td>010100</td><td>22</td><td>000010111</td><td>00011000</td><td>0011010</td><td>011110</td></tr><tr><td>3</td><td>00100</td><td>0101</td><td>111</td><td>1011</td><td>13</td><td>0001110</td><td>001111</td><td>0010001</td><td>010101</td><td>23</td><td>000011000</td><td>00011001</td><td>0011011</td><td>011111</td></tr><tr><td>4</td><td>00101</td><td>0110</td><td>01000</td><td>1100</td><td>14</td><td>0001111</td><td>00010000</td><td>0010010</td><td>010110</td><td>24</td><td>000011001</td><td>00011010</td><td>0011100</td><td>00100000</td></tr><tr><td>5</td><td>00110</td><td>0111</td><td>01001</td><td>1101</td><td>15</td><td>000010000</td><td>00010001</td><td>0010011</td><td>010111</td><td>25</td><td>000011010</td><td>00011011</td><td>0011101</td><td>00100001</td></tr><tr><td>6</td><td>00111</td><td>001000</td><td>01010</td><td>1110</td><td>16</td><td>000010001</td><td>00010010</td><td>0010100</td><td>011000</td><td>26</td><td>000011011</td><td>00011100</td><td>0011110</td><td>00100010</td></tr><tr><td>7</td><td>0001000</td><td>001001</td><td>01011</td><td>1111</td><td>17</td><td>000010010</td><td>00010011</td><td>0010101</td><td>011001</td><td>27</td><td>000011100</td><td>00011101</td><td>0011111</td><td>00100011</td></tr><tr><td>8</td><td>0001001</td><td>001010</td><td>01100</td><td>010000</td><td>18</td><td>000010011</td><td>00010100</td><td>0010110</td><td>011010</td><td>28</td><td>000011101</td><td>00011110</td><td>000100000</td><td>00100100</td></tr><tr><td>9</td><td>0001010</td><td>001011</td><td>01101</td><td>010001</td><td>19</td><td>000010100</td><td>00010101</td><td>0010111</td><td>011011</td><td>29</td><td>000011110</td><td>00011111</td><td>000100001</td><td>00100101</td></tr></tbody></table>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Elias_gamma_coding/kcNSUnBg">Elias gamma (γ) coding</a></li>
<li><a href="/facts/Elias_delta_coding/LoDaPWqx">Elias delta (δ) coding</a></li>
<li><a href="/facts/Elias_omega_coding/uxHF9zyx">Elias omega (ω) coding</a></li>
<li><a href="/facts/Universal_code_(data_compression)/9zn1cM2M">Universal code</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Richardson, Iain (2010). The H.264 Advanced Video Compression Standard. Wiley. pp. 208, 221. ISBN 978-0-470-51692-8. <a href="978-0-470-51692-8" target="_blank">978-0-470-51692-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Rupp, Markus (2009). Video and Multimedia Transmissions over Cellular Networks: Analysis, Modelling and Optimization in Live 3G Mobile Networks. Wiley. p. 149. ISBN 9780470747766. <a href="9780470747766" target="_blank">9780470747766</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Richardson, Iain (2010). The H.264 Advanced Video Compression Standard. Wiley. pp. 208, 221. ISBN 978-0-470-51692-8. <a href="978-0-470-51692-8" target="_blank">978-0-470-51692-8</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">"Dirac Specification" (PDF). BBC. Archived from the original on 2015-05-03. Retrieved 9 March 2011. <a href="https://web.archive.org/web/20150503015104/http://diracvideo.org/download/specification/dirac-spec-latest.pdf" target="_blank">https://web.archive.org/web/20150503015104/http://diracvideo.org/download/specification/dirac-spec-latest.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

Exponential-Golomb coding open-in-new

Exponential-Golomb coding