斐波那契编码

斐波那契编码（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。

在这种使用符号序列进行编码的方法中，可以自由推广其中某些不允许存在的模式（如“11”）。^[2]

例子[编辑]

下表展示了整数65编码到斐波那契编码为0100100011的具体内容，表示 $65={{{2}+{8}}+{55}}$ 。不使用前两个斐波那契数 $F (0)=0$ 和 $F (1)=1$ ，且末尾必定会加上一个“1”。

{\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)）
齐肯多夫定理

参考资料[编辑]

^ 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）（英语）.
^ Duda, Jarek. Optimal encoding on discrete lattice with translational invariant constrains using statistical algorithms. 2007. arXiv:0710.3861  [cs.IT].
^ ^3.0 ^3.1 Fibonaccimal Base. onlinejudge.org. [2022-10-06]. （原始内容存档于2022-10-09）.
^ 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.

[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].

[Fibonaccimal_Base-3] 3.0 ^3.1 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.

[1]

[2]

[3]

[4]