Fibonacci coding
From Wikipedia, the free encyclopedia
| 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.
[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.
This approach - encoding using sequence of symbols, in which some patterns (like "11") are forbidden, can be freely generalized[1].
[edit] See also
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
