|
Elias gamma code is a universal code encoding positive integers. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand. In data compression, a universal code for integers is a prefix-free code that maps the positive integers onto self-delimiting binary codewords, with the additional property that whatever the true probability distribution on integers, the lengths of the codewords are within a constant factor of the lengths that the...
To code a number: For other uses, see Number (disambiguation). ...
- Write it in binary.
- Subtract 1 from the number of bits written in step 1 and prepend that many zeros.
An equivalent way to express the same process: The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ...
- Separate the integer into the highest power of 2 it contains (2N) and the remaining N binary digits of the integer.
- Encode N in unary; that is, as N zeroes followed by a one.
- Append the remaining N binary digits to this representation of N.
The code begins: The unary numeral system is the simplest numeral system to represent natural numbers: in order to represent a number N, an arbitrarily chosen symbol is repeated N times. ...
1 = 20 + 0 = 1 2 = 21 + 0 = 010 3 = 21 + 1 = 011 4 = 22 + 0 = 00100 5 = 22 + 1 = 00101 6 = 22 + 2 = 00110 7 = 22 + 3 = 00111 8 = 23 + 0 = 0001000 9 = 23 + 1 = 0001001 10 = 23 + 2 = 0001010 11 = 23 + 3 = 0001011 12 = 23 + 4 = 0001100 13 = 23 + 5 = 0001101 14 = 23 + 6 = 0001110 15 = 23 + 7 = 0001111 16 = 24 + 0 = 000010000 17 = 24 + 1 = 000010001 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.
Gamma coding is used in applications where the largest encoded value is not known ahead of time, or to compress data in which small values are much more frequent than large values. “Source coding†redirects here. ...
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, mapping integers (0, 1, -1, 2, -2, 3, -3, ...) to (1, 2, 3, 4, 5, 6, 7, ...) before coding. A bijective function. ...
Example 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 0's to indicate how much bits that will follow } bitwriter.putBit(true);//mark the end of the 0's for (int a=0; a < l; 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); BitWriter bitwriter(dest); int numberBits = 0; while(bitreader.hasLeft()) { while(!bitreader.getBit() || bitreader.hasLeft())numberBits++; //keep on reading until we fetch a one... int current = 0; for (int a=0; a < numberBits; a++) //Read numberBits bits { if (bitreader.getBit()) current += 1 << a; } //write it as a 32 bit number current= current | 1 ; //last bit isn't encoded! for (int a=0; a < 32; a++) //Read numberBits bits { if (current & (1 << a)) bitwriter.putBit(true); else bitwriter.putBit(false); } } }
See also Elias delta code is a universal code encoding the positive integers. ...
Elias omega coding is a universal code encoding the positive integers. ...
External links Elias gamma coding | 
Feeds |
Contact