In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic , the expected lengths of the codewords are...
encoding positive integers developed by Peter Elias
Peter Elias
Peter Elias was a pioneer in the field of information theory. Born in New Brunswick, New Jersey, he was a member of the Massachusetts Institute of Technology faculty from 1953 to 1991....
. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.
A number is a mathematical object used to count and measure. In mathematics, the definition of number has been extended over the years to include such numbers as zero, negative numbers, rational numbers, irrational numbers, and complex numbers....
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
.
Subtract 1 from the number of bits written in step 1 and prepend that many zeros.
An equivalent way to express the same process:
Separate the integer into the highest power of 2 it contains (2N) and the remaining N binary digits of the integer.
The unary numeral system is the bijective base-1 numeral system. It is the simplest numeral system to represent natural numbers: in order to represent a number N, an arbitrarily chosen symbol representing 1 is repeated N times. For example, using the symbol | , the number 6 is represented as ||||||...
; that is, as N zeroes followed by a one.
Append the remaining N binary digits to this representation of N.
To represent a number , Elias gamma uses bits.
The code begins (the implied probability distribution for the code is added for clarity):
Number
Encoding
Implied probability
1 = 20 + 0
1
1/2
2 = 21 + 0
010
1/8
3 = 21 + 1
011
1/8
4 = 22 + 0
00100
1/32
5 = 22 + 1
00101
1/32
6 = 22 + 2
00110
1/32
7 = 22 + 3
00111
1/32
8 = 23 + 0
0001000
1/128
9 = 23 + 1
0001001
1/128
10 = 23 + 2
0001010
1/128
11 = 23 + 3
0001011
1/128
12 = 23 + 4
0001100
1/128
13 = 23 + 5
0001101
1/128
14 = 23 + 6
0001110
1/128
15 = 23 + 7
0001111
1/128
16 = 24 + 0
000010000
1/512
17 = 24 + 1
000010001
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 2N, 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 compress
Data compression
In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
data in which small values are much more frequent than large values.
Generalizations
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
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
An exponential-Golomb code of order k is a type of universal code, parameterized by a nonnegative integer k. To encode a nonnegative integer in an order-k exp-Golomb code, one can use the following method:...
generalizes the gamma code to integers with a "flatter" power-law distribution, just as Golomb coding
Golomb coding
Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the...
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.
Encode
void eliasGammaEncode(char* source, char* dest)
{
IntReader intreader(source);
BitWriter bitwriter(dest);
while (intreader.hasLeft)
{
int num = intreader.getInt;
int l = log2(num);
for (int a=0; a < l; a++)
bitwriter.putBit(false); //put 0s to indicate how many bits will follow
bitwriter.putBit(true); //mark the end of the 0s
for (int a=l-1; a >= 0; a--) //Write the bits as plain binary
{
if (num & 1 << a)
bitwriter.putBit(true);
else
bitwriter.putBit(false);
}
}
intreader.close;
bitwriter.close;
}
Decode
void eliasGammaDecode(char* source, char* dest)
{
BitReader bitreader(source);
IntWriter intwriter(dest);
while (bitreader.hasLeft)
{
int numberBits = 0;
while (!bitreader.getBit && bitreader.hasLeft)
numberBits++; //keep on reading until we fetch a one...
int current = 0;
for (int a=numberBits-1; a >= 0; a--) //Read numberBits bits
{
if (bitreader.getBit)
current |= 1 << a;
}
current |= 1 << numberBits; //last bit isn't encoded!
Elias delta code is a universal code encoding the positive integers developed by Peter Elias. To code a number:#Write it in binary.#Count the bits and write down that number of bits in binary ....
Elias omega coding is a universal code encoding the positive integers developed by Peter Elias. Like Elias gamma coding and Elias delta coding, it works by prefixing the integer with a representation of its order of magnitude in a universal code...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
, Elias gamma uses 
bits.