Editing Fibonacci coding (section)

==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 {{math|''F''(''i'')}} is the {{math|''i''}}th [[Fibonacci number]], and so {{math|''F''(''i''+2)}} is the {{math|''i''}}th 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 (that is, ''d''(''k''&minus;1) and ''d''(''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-called [[Universal code (data compression)#Relationship to practical compression|''implied probability'']], the value for each number that has a minimum-size code in Fibonacci coding.

{|class="wikitable" style="text-align:right;"
! Symbol !! Fibonacci representation !! Fibonacci code word !! Implied probability
|-
| 1 || <math>F(2)</math>        || 11     || 1/4
|-
| 2 || <math>F(3)</math>        || 011    || 1/8
|-
| 3 || <math>F(4)</math>        || 0011   || 1/16
|-
| 4 || <math>F(2) + F(4)</math> || 1011   || 1/16
|-
| 5 || <math>F(5)</math>        || 00011  || 1/32
|-
| 6 || <math>F(2) + F(5)</math> || 10011  || 1/32
|-
| 7 || <math>F(3) + F(5)</math> || 01011  || 1/32
|-
| 8 || <math>F(6)</math>           || 000011 || 1/64
|-
| 9 || <math>F(2) + F(6)</math>    || 100011 || 1/64
|-
| 10 || <math>F(3) + F(6)</math>   || 010011 || 1/64
|-
| 11 || <math>F(4) + F(6)</math>   || 001011 || 1/64
|-
| 12 || <math>F(2)+F(4)+F(6)</math>|| 101011 || 1/64
|-
| 13 || <math>F(7)</math>   || 0000011 || 1/128
|-
| 14 || <math>F(2) + F(7)</math>   || 1000011 || 1/128
|-
|}

To encode an integer {{Mvar|N}}:
# Find the largest [[Fibonacci number]] equal to or less than ''{{Mvar|N}}''; subtract this number from ''{{Mvar|N}}'', keeping track of the remainder.
# If the number subtracted was the {{Mvar|i}}th Fibonacci number {{Math|''F''(''i'')}}, put a 1 in place {{Math|''i'' &minus; 2}} in the code word (counting the left most digit as place 0).
# Repeat the previous steps, substituting the remainder for ''{{Mvar|N}}'', until a remainder of 0 is reached.
# 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 number]]s) to the bits in the code word, and sum the values of the "1" bits.