Elias Gamma Code
Elias gamma coding encodes a positive integer n as floor(log2(n)) leading 0s followed by its binary representation; it is a universal prefix code, effective for uniform distributions.
Purpose
It provides universal variable-length coding when the actual distribution is unknown, with a code length of 2*floor(log2(n))+1.
Mechanism
Let k = floor(log2(n)); output k zeros followed by the (k+1)-bit binary representation of n. To decode, count the leading zeros to get k, then read k+1 more bits to recover n.
Use cases
- Universal variable-length integer coding
- Information theory teaching
- Compact representation of small integers