斐波那契编码

斐波那契編碼（Fibonacci coding）是一種僅使用兩種符號（0和1）表達數值的通用編碼（英语：Universal code (data compression)）^[1]。這種編碼是基於斐波那契數來表達整數的一個例子。這種編碼皆以「11」為結尾，並且在結尾之前不會出現連續2個1。

斐波那契編碼與齊肯多夫表述法密切相關。齊肯多夫表述法是一種基於齊肯多夫定理的进制系統，並且也具有不連續使用兩個1的特性。特定整數的斐波那契編碼正是數字順序顛倒的齊肯多夫表述法，並在末尾附加了一個額外的“1”。

定義

對於一個數字 $N\!$ ，若 $d(0),d(1),\ldots ,d(k-1),d(k)\!$ 代表 $N\!$ 在斐波那契編碼中的碼字（英语：code word），則有：

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

其中 $F (i)$ 為第 $i$ 個斐波那契數，因此 $F (i +2)$ 是第 $i$ 個相異的斐波那契數 $1,2,3,5,8,13,\ldots$ 。最後一位 $d(k)$ 為始終是1的附加位，並且不攜帶位置值。

可以看出，這樣的編碼是唯一的，並且在任何碼字中唯一出現的“11”是在末尾，即d(k−1)和d(k)。倒數第二位是最高有效位，第一位是最低有效位。許多进制可以省略前導零，如十进制，然而斐波那契編碼的前導零不能省略。

下面顯示了前幾個斐波那契編碼，以及其所謂的隱含概率，即對所有在斐波那契編碼中有最小碼值的數字而言的值。

數字	斐波那契表述法	斐波那契編碼	隱含概率
1	$F(2)$	11	1/4
2	$F(3)$	011	1/8
3	$F(4)$	0011	1/16
4	$F(2)+F(4)$	1011	1/16
5	$F(5)$	00011	1/32
6	$F(2)+F(5)$	10011	1/32
7	$F(3)+F(5)$	01011	1/32
8	$F(6)$	000011	1/64
9	$F(2)+F(6)$	100011	1/64
10	$F(3)+F(6)$	010011	1/64
11	$F(4)+F(6)$	001011	1/64
12	$F(2)+F(4)+F(6)$	101011	1/64
13	$F(7)$	0000011	1/128
14	$F(2)+F(7)$	1000011	1/128

將一個整數N編碼為斐波那契編碼的方法為：

找到小於或等於 $N$ 的最大斐波那契數，並且用 $N$ 減去這個斐波那契數，並記錄剩餘的數
如果減去的這個數為為第 $i$ 個斐波那契數 $F (i)$ ，置1到 $i -2$ 的位置（將最左邊的數字視為位置0）。
將 $N$ 替換為剩餘的數，並重複步驟1~2直到剩餘的數為0
在最右邊加一個「1」

要解碼斐波那契編碼，請刪除最後的「1」，將剩餘的位數分配給1,2,3,5,8,13...（斐波那契數），並將位數為「1」的斐波那契數加總。

與其他通用編碼的比較

斐波那契編碼有一個有用的特性，有時它與其他通用編碼（英语：Universal code (data compression)）相比更具吸引力：斐波那契編碼是自同步編碼（英语：Self-synchronizing code）的一個示例，可以更容易地從損壞的資料流中恢復數據。對於大多數其他通用編碼（英语：Universal code (data compression)），如果單個位元被更改，則其後的任何數據可能無法被正確讀取。另一方面，對於斐波那契編碼，更改位元可能會導致一個字詞（token）被讀取為兩個，或者導致兩個字詞被錯誤地讀取為一個，但從資料流中讀取“0”能阻止錯誤進一步傳播。由於唯一沒有“0”的資料流是“11”字詞的資料流，因此單個位元錯誤損壞的資料流與原始資料流之間的總編輯距離最多為3。