Elias gamma coding

related topics
{math, number, function}
{system, computer, user}
{@card@, make, design}

Elias gamma code is a universal code encoding positive integers developed by Peter Elias. It is used most commonly when coding integers whose upper-bound cannot be determined beforehand.

Contents

Encoding

To code a number:

An equivalent way to express the same process:

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

Decoding

To decode an Elias gamma-coded integer:

Uses

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.

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.

Example code

Encode

Full article ▸

related documents
Linear function
Connectedness
Regular graph
Parse tree
Inner automorphism
Earley parser
Subring
Injective function
Unitary matrix
Unit interval
Profinite group
Subset
Row and column spaces
Hausdorff maximal principle
Specification language
Euler's identity
Identity matrix
Disjunctive normal form
Class (set theory)
Additive function
Random sequence
Inequation
Inverse transform sampling
Kleene star
Sharp-P
Discrete probability distribution
Inverse functions and differentiation
Just another Perl hacker
Urysohn's lemma
Klein four-group