Elias Omega Code
Elias omega coding recursively encodes the length parts, and is the most compact of the three Elias universal codes for large integers, with a code length of log2(n)+log2(log2(n))+...+O(1).
Purpose
It provides the optimal universal code when the upper bound of integers is unknown and large values are frequent.
Mechanism
Encoding is recursive: starting from n, output the binary representation of floor(log2(n)) and recursively encode that length, with a single 0 as the termination marker. Decoding rebuilds the value by reverse recursion.
Use cases
- Variable-length coding of very large integers
- Universal compression theory
- Recursive coding instruction