Fibonacci coding

Fibonacci coding represents an integer N as a binary string where the i-th bit (from the right, starting at 1) has weight F_i+1 (with F₁=1, F₂=2). The representation uses the Zeckendorf representation, which is unique and contains no consecutive 1s. To encode, one finds the largest Fibonacci number not exceeding N, subtracts it, and repeats. The resulting bits are written in order from most significant to least, and a terminating '1' is appended to create the '11' delimiter. For example, 10 = 8 + 2, so the Zeckendorf representation is 10010 (bits for 8,5,3,2,1), and the Fibonacci code is 100101. The code is prefix-free because no codeword contains '11' except at the end, allowing unambiguous decoding.

Fibonacci coding is a universal code, meaning that for any probability distribution over positive integers, the expected code length is within a constant factor of the entropy. Its average code length for a uniform distribution over [1, n] is approximately log_φ(n) ≈ 1.44 log₂(n) bits, where φ is the golden ratio. This is slightly less efficient than standard binary coding but offers robustness: the '11' delimiter makes it self-synchronizing, so errors in transmission do not propagate indefinitely. The code is also monotonic — larger integers have longer or equal code lengths — and it is optimal for distributions where probabilities decay like Fibonacci numbers, such as in certain natural language models.

Fibonacci coding is used in data compression, particularly in the Fibonacci compression technique for text and image data, where it competes with Huffman coding. It is also employed in bioinformatics for representing DNA sequences, as the absence of consecutive 1s reduces the risk of misreading in error-prone environments. In error correction, the code's self-synchronizing property allows recovery from bit flips without resynchronization markers. Additionally, Fibonacci coding appears in Fibonacci search algorithms, where it is used to encode indices in a way that minimizes comparisons. The code is also a basis for Fibonacci hashing, a technique for distributing keys uniformly in hash tables.

Beyond its standard use, Fibonacci coding has niche applications. In run-length encoding, it can encode run lengths without needing a separate length field. It is also used in Fibonacci representation of real numbers via the Fibonacci numeral system, which extends to non-integer values. The code is related to the Fibonacci word, an infinite binary sequence with no consecutive 1s, which is used in combinatorics on words. A lesser-known fact: the code is asymptotically optimal for distributions with a heavy tail, such as power-law distributions, because it assigns shorter codes to small numbers. In cryptography, Fibonacci coding has been proposed as a way to obscure data length, though it is not secure on its own. The concept was first described by Solomon Golomb in the 1960s, but it gained prominence with the work of Fenwick in the 1990s on suffix arrays.

Zeckendorf representation

A unique representation of an integer as a sum of non-consecutive Fibonacci numbers.

Universal code

A prefix-free code that achieves expected length within a constant factor of entropy for any distribution.

Prefix-free

A property where no codeword is a prefix of another, enabling unambiguous decoding.

Golden ratio

The irrational number φ ≈ 1.618, related to Fibonacci numbers.