Fibonacci coding
From Wikipedia, the free encyclopedia
| Numeral systems by culture | |
|---|---|
| Hindu-Arabic numerals | |
| Western Arabic Eastern Arabic Khmer |
Indian family Brahmi Thai |
| East Asian numerals | |
| Chinese Japanese |
Korean |
| Alphabetic numerals | |
| Abjad Armenian Cyrillic Ge'ez |
Hebrew Ionian/Greek Sanskrit |
| Other systems | |
| Attic Etruscan Roman |
Babylonian Egyptian Mayan |
| List of numeral system topics | |
| Positional systems by base | |
| Decimal (10) | |
| 2, 4, 8, 16, 32, 64, 128 | |
| 3, 9, 12, 24, 30, 36, 60, 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. 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.
[edit] Comparison with other universal codes
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.
