斐波那契編碼

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

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

定義

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

${\displaystyle 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個相異的斐波那契數${\displaystyle 1,2,3,5,8,13,\ldots }$。最後一位${\displaystyle d(k)}$為始終是1的附加位，並且不攜帶位置值。

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

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

數字	斐波那契表述法	斐波那契編碼	隱含概率
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

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

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

在這種使用符號序列進行編碼的方法中，可以自由推廣其中某些不允許存在的模式（如「11」）。^[2]

例子

下表展示了整數65編碼到斐波那契編碼為0100100011的具體內容，表示${\displaystyle 65={{{2}+{8}}+{55}}}$。不使用前兩個斐波那契數F(0)=0和F(1)=1，且末尾必定會加上一個「1」。

${\displaystyle {\begin{array}{ccccccccccc|c}\hline 0&1&1&2&3&5&8&13&21&34&55&-\\\hline F(0)&F(1)&F(2)&F(3)&F(4)&F(5)&F(6)&F(7)&F(8)&F(9)&F(10)&\scriptstyle {\text{additional}}\\\hline -&-&0&1&0&0&1&0&0&0&1&1\\\hline \end{array}}}$

斐波那契進制

斐波那契進制（Fibonaccimal Base）是與黃金進制關係緊密的計數系統。它只用0和1表示數，每個數位的位值對應斐波那契數^[3]。和黃金進制一樣，其標準形也不連續使用兩個1。如：

30 = 1×21 + 0×13 + 1×8 + 0×5 + 0×3 + 0×2 + 1×1 + 0×1 = 10100010_fib

斐波那契進制與齊肯多夫表述法非常接近，斐波那契進制僅比齊肯多夫表述法末尾附加了一個額外的「0」。

由於最末位始終為零，因此有時會將之省去^[3]，而省去後的結果則與齊肯多夫表述法相同^[4]。

參見

• 進位制
• 黃金進制
• 負斐波那契編碼（英語：Negafibonacci coding）
• 奧斯特洛夫斯基記數系統（英語：Ostrowski numeration）
• 通用編碼（英語：Universal code (data compression)）
• 齊肯多夫定理

參考資料

1. Ayse Nalli, Cagla Ozyilmaz. The third order variations on the Fibonacci universal code. Journal of Number Theory. 2015-04, 149: 15–32 [2022-10-06]. doi:10.1016/j.jnt.2014.07.010. （原始內容存檔於2018-06-29） （英語）.
2. Duda, Jarek. Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms. 2007. arXiv:0710.3861  [cs.IT].
3. Fibonaccimal Base. onlinejudge.org. [2022-10-06]. （原始內容存檔於2022-10-09）.
4. Sloane, N.J.A. (編). Sequence A014417 (Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n)). The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

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