Elias Delta Code
Elias delta coding applies gamma coding a second time to the length part of gamma code, making it more compact than gamma for large integers; it is a universal prefix code.
Purpose
It encodes integers more efficiently than gamma coding when the range of values is wide, with a code length of log2(n)+2*log2(log2(n))+O(1).
Mechanism
Let k = floor(log2(n)); output gamma(k) followed by the low k bits of n. The length itself is thus variably encoded, reducing the overhead for large integers.
Use cases
- Variable-length coding of wide-range integers
- Universal compression
- Information theory teaching