Fibonacci coding

Numeral systems by culture
Hindu-Arabic numerals
Western Arabic (Hindu numerals) Eastern Arabic Indian family Tamil	Burmese Khmer Lao Mongolian Thai
East Asian numerals
Chinese Japanese Suzhou	Korean Vietnamese Counting rods
Alphabetic numerals
Abjad Armenian Āryabhaṭa Cyrillic	Ge'ez Greek Georgian Hebrew
Other systems
Aegean Attic Babylonian Brahmi Egyptian Etruscan Inuit	Kharosthi Mayan Quipu Roman Sumerian Urnfield
List of numeral system topics
Positional systems by base
Decimal (10)
2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 20, 24, 30, 36, 60, 64
Non-positional system
Unary numeral system (Base 1)
List of numeral systems

In mathematics, Fibonacci coding is a universal code which encodes positive integers into binary code words. Each code word ends with "11" and contains no other instances of "11" before the end.

Definition

For a number $N\!$, if $d(0),d(1),\ldots,d(k)\!$ represent the digits of the code word representing $N\!$ then we have:

$N = \sum_{i=0}^{k-1} d(i) F(i+2),\text{ and }d(k)=d(k-1)=1.\!$

where F(i) is the ith Fibonacci number.

It can be shown that such a coding is unique, and the only occurrence of "11" in any code word is at the end i.e. d(k−1) and d(k).

The code begins as follows:

Symbol	Fibonacci representation	Fibonacci code word
1	F(2)	11
2	F(3)	011
3	F(4)	0011
4	F(2) + F(4)	1011
5	F(5)	00011
6	F(2) + F(5)	10011
7	F(3) + F(5)	01011
8	F(6)	000011

The Fibonacci code is closely related to the Zeckendorf representation, a positional numeral system that uses Zeckendorf's theorem and has the property that no number has a representation with consecutive 1s. The Fibonacci code word for a particular integer is exactly the integer's Zeckendorf representation with the order of its digits reversed and an additional "1" appended to the end.

To encode an integer N:

1. Find the largest Fibonacci number equal to or less than N; subtract this number from N, keeping track of the remainder.
2. If the number subtracted was the ith Fibonacci number F(i), put a 1 in place i−2 in the code word (counting the left most digit as place 0).
3. Repeat the previous steps, substituting the remainder for N, until a remainder of 0 is reached.
4. Place an additional 1 after the rightmost digit in the code word.

To decode a code word, remove the final "1", assign the remaining the values 1,2,3,5,8,13... (the Fibonacci numbers) to the bits in the code word, and sum the values of 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 an example of a self-synchronizing code, making it 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].

Example

The following table shows that the number 65 is represented in Fibonacci coding as 0100100011, since 65 = 2 + 8 + 55. The first two Fibonacci numbers (0 and 1) are not used, and an additional 1 is always appended.

0	1	1	2	3	5	8	13	21	34	55	–
F(0)	F(1)	F(2)	F(3)	F(4)	F(5)	F(6)	F(7)	F(8)	F(9)	F(10)	additional
–	–	0	1	0	0	1	0	0	0	1	1

A method to encode any integer is shown in the following Python program.

def encode_fib(n):
    # Return string with Fibonacci encoding for n (n >= 1).
    result = ""
    if n >= 1:
        a = 1
        b = 1
        c = a + b   # next Fibonacci number
        fibs = [b]  # list of Fibonacci numbers, starting with F(2), each <= n
        while n >= c:
            fibs.append(c)  # add next Fibonacci number to end of list
            a = b
            b = c
            c = a + b
        result = "1"  # extra "1" at end
        for fibnum in reversed(fibs):
            if n >= fibnum:
                n = n - fibnum
                result = "1" + result
            else:
                result = "0" + result
    return result
 
print encode_fib(65)  # displays "0100100011"

See also

• Golden ratio base
• Zeckendorf's theorem
• Universal code

References

• Fraenkel A, Klein S. (1996). "Robust universal complete codes for transmission and compression". Discrete Applied Mathematics 64: 31–55. doi:10.1016/0166-218X(93)00116-H. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.3064. 

Further reading

• Stakhov, A. P. (2009). The Mathematics of Harmony: From Euclid to Contemporary Mathematics and Computer Science. Singapore: World Scientific Publishing.