Difference between revisions of "Fibonacci coding"

Revision as of 06:23, 13 September 2015

In mathematics and computing, Fibonacci coding is a universal code which encodes positive integers into binary code words.

(TO DO: fix math, expand, organize, cross-reference, illustrate.)

Description

It is one example of representations of integers based on Fibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.

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.

Definition

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

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

where Template:Math is the Template:Mathth Fibonacci number, and so Template:Math is the Template:Mathth distinct Fibonacci number starting with <math>1,2,3,5,8,13,\ldots</math>. The last bit <math>d(k)</math> is always an appended bit of 1 and does not carry place value.

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). Note that the penultimate bit is the most significant bit and the first bit is the least significant bit. Note also that leading zeros cannot be omitted as they can in e.g. decimal numbers.

The first few Fibonacci codes are shown below, and also the so-called implied distribution, the distribution of values for which Fibonacci coding gives a minimum-size code.

See also

• Fibonacci sequence
• Mathematics

External links

• Fibonacci coding @ Wikipedia