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.
To code a number: #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: #Separate the integer into the highest power of 2 it contains (2"N") 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 implied probability distribution for the code is added for clarity.
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"N", 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.
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.
Example code
Encodevoid 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 much bits that will follow } bitwriter.putBit(true);//mark the end of the 0s 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 << numberBits ) ; //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 coding *Elias omega coding
External links
[http://www.definethis.org/word/Gamma_code.html Elias gamma coding]
Elias delta coding — Elias delta code is a universal code encoding the positive integers. To code a number: #Write it in binary. #Count the bits and write down that number of bits in binary (X). #Use the binary digit written in step 1 again, remove the leading bit… … Wikipedia
Elias omega coding — is a universal code encoding the positive integers. 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. Unlike those other two codes, however,… … Wikipedia
Elias coding — is term used for one of two types of lossless coding schemes used in digital communications:* Shannon Fano Elias coding, a precursor to arithmetic coding, in which probabilities are used to determine codewords; * Universal coding using one of… … Wikipedia
Gamma (disambiguation) — Gamma is the third letter of the Greek alphabet. Gamma may also refer to:cience and mathematicsGeneral* Gamma wave, a type of brain wave * Latin gamma, used as an IPA symbol for voiced velar fricative, and in the alphabets of African languages *… … Wikipedia
Exponential-Golomb coding — An Exponential Golomb code (or just Exp Golomb code) of order k is a type of universal code, parameterized by a whole number k. To encode a nonnegative integer in an order k exp Golomb code, one can use the following method: # Take the number in… … Wikipedia
Huffman coding — Huffman tree generated from the exact frequencies of the text this is an example of a huffman tree . The frequencies and codes of each character are below. Encoding the sentence with this code requires 135 bits, as opposed of 288 bits if 36… … Wikipedia
Adaptive Huffman coding — (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one pass encoding and … Wikipedia
Modified Huffman coding — is used in fax machines to encode black on white images (bitmaps). It combines the variable length codes of Huffman coding with the coding of repetitive data in run length encoding. External links Modified Huffman coding from UNESCO . Archived… … Wikipedia
NegaFibonacci coding — Numeral systems by culture Hindu Arabic numerals Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil Burmese Khmer Lao Mongolian Thai East Asian numerals Chinese Japanese Suzhou Korean Vietnamese … Wikipedia
Universal code (data compression) — 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… … Wikipedia
