斐波那契编码

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