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.
For a number , if represent the digits of the coded form of then we have:
, and .
where F(i) is the ith Fibonacci number. No two adjacent coefficients d(i) can be 1.
It can be shown that such a coding is unique, and in the code "11" never appears anywhere but the end.
The code begin...
more
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.
For a number , if represent the digits of the coded form of then we have:
, and .
where F(i) is the ith Fibonacci number. No two adjacent coefficients d(i) can be 1.
It can be shown that such a coding is unique, and in the code "11" never appears anywhere but the end.
The code begins as follows:
The Fibonacci code is closely related to the Zeckendorf representation, a positional numeral system that uses Zeckendorf's theorem and has the property that no number has a representation with consecutive 1's. The Zeckendorf representation 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:
To decode a token in the code, remove the last "1", assign the remaining bits the values 1,2,3,5...
less
