# Fibonacci coding

 related topics {math, number, function} {system, computer, user}

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.

For a number $N\!$, if $d(0),d(1),...,d(k)\!$ represent the digits of the coded form of $N\!$ then we have:

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

where F(i) is the ith Fibonacci number. No two adjacent coefficients d(i) can be 1.

It can be shown that such a coding is unique, and in the code "11" never appears anywhere but the end.

The code begins as follows:

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 1's. The Zeckendorf representation 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:

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.

## Contents

### 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.

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"