Elias Universal Integer Codes

Worked Example: Delta Encoding

Let's see how Elias Delta coding encodes the integer 16. Delta coding encodes the length of the binary representation using Gamma coding, and then appends the binary representation without its leading 1.

1. The binary representation of 16 is 10000.
2. The length of this binary string is 5.
3. We Gamma-encode the length 5. The binary representation of 5 is 101, which has a length of 3. Thus, its Gamma code consists of 2 zeros followed by the binary string: 00101.
4. The payload is the binary representation of 16 without its leading 1: 0000.
5. Appending the payload to the Gamma-encoded length yields the full codeword: 00101 + 0000 = 001010000.

Interactive Experiment

You can test different integer values and encoding types using the Elias Universal Integer Codes module.

1. Select the Code as "Delta".
2. Set the Integer to 16. Observe the generated "Full codeword" 001010000 and how the bit trace separates the unary length from the binary size and payload.
3. Change the Truncate setting to "Drop final bit".
4. Observe that the status changes to "Truncated code" and the "Decoded integer" becomes "Unavailable", demonstrating that prefix codes rely on the complete sequence to be decodable.

Limitations

Elias codes are defined strictly for positive integers (i.e., integers greater than 0). There is no native provision for zero or negative integers unless a mapping function (like zigzag encoding) is applied first. Additionally, while universal, they are not optimal for every probability distribution. For instance, if small numbers are extremely frequent, simpler codes like unary might be shorter, whereas if the numbers are uniformly distributed over a known finite range, fixed-length binary codes are more efficient.

References

For more detailed information regarding universal codeword lengths, refer to Peter Elias' original paper on the topic: Universal Codeword Lengths and Representations.