Fibonacci coding

The Fibonacci code is a universal code which encodes smaller numbers into shorter 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

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.


This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.