Fibonacci Coding
Fibonacci coding is a prefix code built on the Zeckendorf representation (every positive integer is uniquely the sum of non-consecutive Fibonacci numbers); it beats unary coding for geometric distributions.
Purpose
It encodes geometrically distributed integer sequences more compactly than unary coding while staying a simple prefix code.
Mechanism
The integer n is decomposed into a sum of non-consecutive Fibonacci numbers (Zeckendorf's theorem); the corresponding positions are 1 and the rest 0, with a final 1 appended as the terminator — the only place where two consecutive 1s appear.
Use cases
- Alternative to exponential Golomb coding
- Encoding geometrically distributed integers
- Universal variable-length coding