View source for Elias gamma coding

{{Short description|Universal encoding scheme for positive integers}}
{{Use dmy dates|date=May 2019|cs1-dates=y}}
{{Use list-defined references|date=January 2022}}
'''Elias <math>\gamma</math> code''' or '''Elias gamma code''' is a [[universal code (data compression)|universal code]] encoding positive integers developed by [[Peter Elias]].<ref name="Elias"/>{{rp|197, 199}} It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.

==Encoding==

To code a [[number]] ''x''&nbsp;≥ 1:
# Let <math>N = \lfloor \log_2 x \rfloor</math> be the highest power of 2 it contains, so 2<sup>''N''</sup> ≤ ''x'' &lt; 2<sup>''N''+1</sup>.
# Write out <math>N</math> zero bits, then
# Append the [[binary numeral system|binary]] form of <math>x</math>, an <math>(N+1)</math>-bit binary number.

An equivalent way to express the same process:
# Encode <math>N</math> in [[Unary numeral system|unary]]; that is, as <math>N</math> zeroes followed by a one.
# Append the remaining <math>N</math> binary digits of <math>x</math> to this representation of <math>N</math>.

To represent a number <math>x</math>, Elias gamma (γ) uses <math>2 \lfloor \log_2(x) \rfloor + 1</math> bits.<ref name="Elias"/>{{rp|199}}

The code begins (the [[implied probability]] distribution for the code is added for clarity):

{| class=wikitable
! Number !! Binary !! &gamma; encoding !! Implied probability
|-
| 1&nbsp;=&nbsp;2<sup>0</sup>&nbsp;+&nbsp;0 ||<code>1</code> || <code>1</code> || 1/2
|-
|colspan=4|
|-
| 2 = 2<sup>1</sup> + ''0'' || <code>1&thinsp;0</code> || <code>0&thinsp;1&thinsp;0</code> || 1/8
|-
| 3 = 2<sup>1</sup> + ''1'' || <code>1&thinsp;1</code> || <code>0&thinsp;1&thinsp;1</code> || 1/8
|-
|colspan=4|
|-
| 4 = 2<sup>2</sup> + ''0'' || <code>1&thinsp;00</code> || <code>00&thinsp;1&thinsp;00</code> || 1/32
|-
| 5 = 2<sup>2</sup> + ''1'' || <code>1&thinsp;01</code> || <code>00&thinsp;1&thinsp;01</code> || 1/32
|-
| 6 = 2<sup>2</sup> + ''2'' || <code>1&thinsp;10</code> || <code>00&thinsp;1&thinsp;10</code> || 1/32
|-
| 7 = 2<sup>2</sup> + ''3'' || <code>1&thinsp;11</code> || <code>00&thinsp;1&thinsp;11</code> || 1/32
|-
|colspan=4|
|-
| 8 = 2<sup>3</sup> + ''0'' || <code>1&thinsp;000</code> || <code>000&thinsp;1&thinsp;000</code> || 1/128
|-
| 9 = 2<sup>3</sup> + ''1'' || <code>1&thinsp;001</code> || <code>000&thinsp;1&thinsp;001</code> || 1/128
|-
| 10 = 2<sup>3</sup> + ''2'' || <code>1&thinsp;010</code> || <code>000&thinsp;1&thinsp;010</code> || 1/128
|-
| 11 = 2<sup>3</sup> + ''3'' || <code>1&thinsp;011</code> || <code>000&thinsp;1&thinsp;011</code> || 1/128
|-
| 12 = 2<sup>3</sup> + ''4'' || <code>1&thinsp;100</code> || <code>000&thinsp;1&thinsp;100</code> || 1/128
|-
| 13 = 2<sup>3</sup> + ''5'' || <code>1&thinsp;101</code> || <code>000&thinsp;1&thinsp;101</code> || 1/128
|-
| 14 = 2<sup>3</sup> + ''6'' || <code>1&thinsp;110</code> || <code>000&thinsp;1&thinsp;110</code> || 1/128
|-
| 15 = 2<sup>3</sup> + ''7'' || <code>1&thinsp;111</code> || <code>000&thinsp;1&thinsp;111</code> || 1/128
|-
|colspan=4|
|-
| 16 = 2<sup>4</sup> + ''0'' || <code>1&thinsp;0000</code> || <code>0000&thinsp;1&thinsp;0000</code> || 1/512
|-
| 17&nbsp;=&nbsp;2<sup>4</sup>&nbsp;+&nbsp;''1'' || {{nowrap|<code>1&thinsp;0001</code>}} || {{nowrap|<code>0000&thinsp;1&thinsp;0001</code>}} || 1/512
|}

==Decoding==
To decode an Elias gamma-coded integer:
#Read and count 0s from the stream until you reach the first 1. Call this count of zeroes ''N''.
#Considering the one that was reached to be the first digit of the integer, with a value of 2<sup>''N''</sup>, read the remaining ''N'' digits of the integer.

==Uses==
Gamma coding is used in applications where the largest encoded value is not known ahead of time, or to [[Data compression|compress]] data in which small values are much more frequent than large values.

Gamma coding can be more size efficient in those situations. For example, note that, in the table above, if a fixed 8-bit size is chosen to store a small number like the number 5, the resulting binary would be <code>00000101</code>, while the γ-encoding variable-bit version would be <code>00 1 01</code>, needing 3 bits less. On the contrary, bigger values, like 254 stored in fixed 8-bit size, would be <code>11111110</code> while the γ-encoding variable-bit version would be <code>0000000 1 1111110</code>, needing 7 extra bits.

Gamma coding is a building block in the [[Elias delta code]].

== Generalizations ==<!-- This section is linked from [[Elias delta coding]] -->
{{See also|Variable-length quantity#Zigzag encoding}}
Gamma coding does not code zero or negative integers.
One way of handling zero is to add 1 before coding and then subtract 1 after decoding.
Another way is to prefix each nonzero code with a 1 and then code zero as a single 0.

One way to code all integers is to set up a [[bijection]], mapping integers (0, −1, 1, −2, 2, −3, 3, ...) to (1, 2, 3, 4, 5, 6, 7, ...) before coding.  In software, this is most easily done by mapping non-negative inputs to odd outputs, and negative inputs to even outputs, so the least-significant bit becomes an inverted [[sign bit]]:<br/>
<math>\begin{cases}
x \mapsto 2x+1 & \mathrm{when~} x \geq 0 \\
x \mapsto -2x  & \mathrm{when~} x < 0 \\
\end{cases}</math>

[[Exponential-Golomb coding]] generalizes the gamma code to integers with a "flatter" power-law distribution, just as [[Golomb coding]] generalizes the unary code.
It involves dividing the number by a positive divisor, commonly a power of 2, writing the gamma code for one more than the quotient, and writing out the remainder in an ordinary binary code.

==See also==
* {{annotated link|Elias delta coding|Elias delta (δ) coding}}
* {{annotated link|Elias omega coding|Elias omega (ω) coding}}
* {{annotated link|Posit (number format)}}

==References==
{{Reflist|refs=
<ref name="Elias">{{cite journal |author-first=Peter |author-last=Elias |author-link=Peter Elias |title=Universal codeword sets and representations of the integers |journal=[[IEEE Transactions on Information Theory]] |volume=21 |issue=2 |pages=194–203 |date=March 1975 |doi=10.1109/tit.1975.1055349}}</ref>
}}

==Further reading==
* {{cite book |author-first=Khalid |author-last=Sayood |title=Lossless Compression Handbook |publisher=[[Elsevier]] |date=2003 |chapter=Levenstein and Elias Gamma Codes |isbn=978-0-12-620861-0}}

{{Compression Methods}}

{{DEFAULTSORT:Elias Gamma Coding}}
[[Category:Entropy coding]]
[[Category:Numeral systems]]
[[Category:Data compression]]