Article on other languages:
 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
| Numeral systems by culture | |
|---|---|
| Hindu-Arabic numerals | |
| Indian Eastern Arabic Khmer |
Indian family Brahmi Thai |
| East Asian numerals | |
| Chinese Suzhou Counting rods |
Japanese Korean |
| Alphabetic numerals | |
| Abjad Armenian Cyrillic Ge'ez |
Hebrew Greek (Ionian) Āryabhaṭa |
| Other systems | |
| Attic Babylonian Egyptian Etruscan |
Mayan Roman Urnfield |
| List of numeral system topics | |
| Positional systems by base | |
| Decimal (10) | |
| 2, 4, 8, 16, 32, 64 | |
| 1, 3, 9, 12, 20, 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 formula used to generate Fibonacci codes is:
where F(i) is the ith Fibonacci number. No two adjacent coefficients d(i) can be 1.
The code begins as follows:
| Symbol | Fibonacci representation | Fibonacci code | |
|---|---|---|---|
| 1 | F(1) | 1 | 11 |
| 2 | F(2) | 2 | 011 |
| 3 | F(3) | 4 | 0011 |
| 4 | F(1) + F(3) | 5 | 1011 |
| 5 | F(4) | 8 | 00011 |
| 6 | F(1) + F(4) | 9 | 10011 |
| 7 | F(2) + F(4) | 10 | 01011 |
| 8 | F(5) | 16 | 000011 |
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.
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.
This approach - encoding using sequence of symbols, in which some patterns (like "11") are forbidden, can be freely generalized[1].
See also
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
