From Wikipedia, the free encyclopedia

In mathematics, Fibonacci coding is a universal code which encodes positive integers into binary code words. All tokens end with "11" and have no "11" before the end. The code begins as follows:

1  11
2  011
3  0011
4  1011
5  00011
6  10011
7  01011
8  000011
9  100011
10 010011
11 001011
12 101011

The Fibonacci code is closely related to Fibonacci representation, a positional numeral system sometimes used by mathematicians. The Fibonacci code for a particular integer is exactly that of the integer's Fibonacci representation, except with the order of its digits reversed and an additional "1" appended to the end.

To encode an integer X:

1. Find the largest Fibonacci number equal to or less than X; subtract this number from X, keeping track of the remainder.
2. If the number we subtracted was the Nth unique Fibonacci number, put a one in the Nth digit of our output.
3. Repeat the previous steps, substituting our remainder for X, until we reach a remainder of 0.
4. Place a one after the last naturally-occurring one in our output.

To decode a token in the code, remove the last "1", assign the remaining bits the values 1,2,3,5,8,13... (the Fibonacci numbers), and add the "1" bits.

Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is easier to recover data from a damaged stream. With most other universal codes, if a single bit is altered, none of the data that comes after it will be correctly read. With Fibonacci coding, on the other hand, a changed bit may cause one token to be read as two, or cause two tokens to be read incorrectly as one, but reading a "0" from the stream will stop the errors from propagating further. Since the only stream that has no "0" in it is a stream of "11" tokens, the total edit distance between a stream damaged by a single bit error and the original stream is at most three.

• Golden ratio base
• Zeckendorf's theorem