This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(January 2013) (Learn how and when to remove this message)

Inmathematics and computing,Fibonacci coding is auniversal code^[1] which encodes positive integers into binarycode words. It is one example of representations of integers based onFibonacci numbers. Each code word ends with "11" and contains no other instances of "11" before the end.

The Fibonacci code is closely related to theZeckendorf representation, a positionalnumeral system that usesZeckendorf'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.

For a number${\displaystyle N}$, if${\displaystyle d(0),d(1),\dots ,d(k-1),d(k)}$ represent the digits of the code word representing${\displaystyle N}$ then we have:

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

whereF(i) is theithFibonacci number, and soF(i+2) is theith distinct Fibonacci number starting with${\displaystyle 1,2,3,5,8,13,\dots }$. The last bit${\displaystyle d(k)}$ 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 (that is,d(k−1) andd(k)). The penultimate bit is the most significant bit and the first bit is the least significant bit. Also, leading zeros cannot be omitted as they can be in, for example, decimal numbers.

The first few Fibonacci codes are shown below, and also their so-calledimplied probability, the value for each number that has a minimum-size code in Fibonacci coding.

Symbol	Fibonacci representation	Fibonacci code word	Implied probability
1	${\displaystyle F(2)}$	11	1/4
2	${\displaystyle F(3)}$	011	1/8
3	${\displaystyle F(4)}$	0011	1/16
4	${\displaystyle F(2)+F(4)}$	1011	1/16
5	${\displaystyle F(5)}$	00011	1/32
6	${\displaystyle F(2)+F(5)}$	10011	1/32
7	${\displaystyle F(3)+F(5)}$	01011	1/32
8	${\displaystyle F(6)}$	000011	1/64
9	${\displaystyle F(2)+F(6)}$	100011	1/64
10	${\displaystyle F(3)+F(6)}$	010011	1/64
11	${\displaystyle F(4)+F(6)}$	001011	1/64
12	${\displaystyle F(2)+F(4)+F(6)}$	101011	1/64
13	${\displaystyle F(7)}$	0000011	1/128
14	${\displaystyle F(2)+F(7)}$	1000011	1/128

To encode an integerN:

1. Find the largestFibonacci number equal to or less thanN; subtract this number fromN, keeping track of the remainder.
2. If the number subtracted was theith Fibonacci numberF(i), put a 1 in placei − 2 in the code word (counting the left most digit as place 0).
3. Repeat the previous steps, substituting the remainder forN, 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... (theFibonacci numbers) to the bits in the code word, and sum the values of the "1" bits.

Fibonacci coding has a useful property that sometimes makes it attractive in comparison to other universal codes: it is an example of aself-synchronizing code, making it easier to recover data from a damaged stream. With most other universal codes, if a singlebit is altered, then 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 totaledit 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.^[2]

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

The Fibonacci encodings for the positive integers are binary strings that end with "11" and contain no other instances of "11". This can be generalized to binary strings that end withN consecutive 1s and contain no other instances ofN consecutive 1s. For instance, forN = 3 the positive integers are encoded as 111, 0111, 00111, 10111, 000111, 100111, 010111, 110111, 0000111, 1000111, 0100111, …. In this case, the number of encodings as a function of string length is given by the sequence oftribonacci numbers.

For general constraints defining which symbols are allowed after a given symbol, the maximal information rate can be obtained by first finding the optimal transition probabilities using amaximal entropy random walk, then using anentropy coder (with switched encoder and decoder) to encode a message as a sequence of symbols fulfilling the found optimal transition probabilities.

• Golden ratio base
• NegaFibonacci coding
• Ostrowski numeration
• Universal code
• Varicode, a practical application
• Zeckendorf's theorem
• Maximal entropy random walk

• Allouche, Jean-Paul;Shallit, Jeffrey (2003).Automatic Sequences: Theory, Applications, Generalizations.Cambridge University Press. p. 105.ISBN 978-0-521-82332-6.Zbl 1086.11015.
• Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). "Robust universal complete codes for transmission and compression".Discrete Applied Mathematics.64 (1):31–55.CiteSeerX 10.1.1.37.3064.doi:10.1016/0166-218X(93)00116-H.ISSN 0166-218X.Zbl 0874.94026.

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

• Non-standard positional numeral systems
• Lossless compression algorithms
• Fibonacci numbers
• Data compression

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from January 2013
• All articles lacking in-text citations
• Pages using sidebar with the child parameter