The Fibonacci code 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:
To convert an integer x to its Fibonacci representation:
Replace x with the difference between x and the largest Fibonacci number less than or equal to x and let the output be 1
If the previous (next smaller) Fibonacci number is less than or equal to x, replace x with the difference, and append 1 to the output. Else, append 0 to the output. Repeat this step until the Fibonacci number 1 is encountered.
This method guarantees that there are no consecutive 1's in the Fibonacci representation of any number.
Encoding
To encode an integer x as little-endian:
Convert x to its Fibonacci representation
Change the representation to little endian and append a 1 after the last 1
Example: 46 -> 10010101 -> 10101001 -> 101010011
To encode an integer x as big-endian:
Convert x to its Fibonacci representation
Remove the leading 10 and appending a trailing 011
The Fibonaccicode 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.
Fibonaccicoding 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 Fibonaccicoding, 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.
Feeds |
Contact