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"

[edit] See also

[edit] References

[edit] Further reading

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


Full article ▸

related documents
Heap (data structure)
Bijection
Alexandroff extension
Pseudometric space
Degenerate distribution
Waring's problem
Domain (mathematics)
Static code analysis
Zeta distribution
Bernoulli process
Iteration
Geometric mean
Closed set
Binary operation
Currying
General number field sieve
Alternating group
Quadratic programming
Hamming distance
Graph of a function
Differential cryptanalysis
Extractor
Sharp-P-complete
Algebraic extension
Abstract factory pattern
Byte-order mark
Residue (complex analysis)
Concatenation
Subtraction
Lex programming tool