fibonacci coding

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:

Find the largest Fibonacci number equal to or less than X; subtract this number from X, keeping track of the remainder.
If the number we subtracted was the Nth unique Fibonacci number, put a one in the Nth digit of our output.
Repeat the previous steps, substituting our remainder for X, until we reach a remainder of 0.
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

See also