Jump to content

Fibonacci coding

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by PierreAbbat (talk | contribs) at 05:29, 7 April 2002 (start). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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