ネガフィボナッチ符号化

数学において、ネガフィボナッチ符号は、非ゼロの整数を2進コードワードに符号化する汎用符号です。フィボナッチ符号に似ていますが、正負の整数の両方を表現できる点が異なります。すべての符号は「11」で終わり、末尾の前に「11」は存在しません。

エンコード方法

次の手順では、非ゼロ整数をエンコードする方法を説明します。は負のフィボナッチ数列を表すことに注意してください。 $x$ $f$

が正の場合、 -1 から -2 のステップを持つネガフィボナッチ数列の奇数の負の項の合計がより大きいか等しい最大の奇数の負の整数を計算します。が負の場合、 0 から -2 のステップを持つネガフィボナッチ数列の偶数の負の項の合計がより小さいか等しい最大の偶数の負の整数を計算します。 $x$ $n$ $n$ $x$
$n\in \{-\left(2k+1\right),k\in [0,\infty [\},\quad \sum _{i=-1,\;i\;odd}^{n-2}f(i)<x\leq \sum _{i=-1,\;i\;odd}^{n}f(i).$
$x$ $n$ $n$ $x$
$n\in \{-2k,k\in [2,\infty [\},\quad \sum _{i=-2,\;i\;even}^{n-2}f(i)>x\geq \sum _{i=-2,\;i\;even}^{n}f(i)$
バイナリワードのビットに1を追加します。から減算します。 $|n|^{\text{th}}$ $f(n)$ $x$
xの新しい値が0 に達するまで、手順 1 からのプロセスを繰り返します。
結果のバイナリワードの左側に 1 を追加して、エンコードを終了します。

エンコードされた2進ワードをデコードするには、2進ワードの左端の1を削除します。これはエンコードされた数値の末尾を示すためだけに使用されます。次に、残りのビットに-1から始まる負のフィボナッチ数列の値（1、-1、2、-3、5、-8、13...）を割り当て、1に関連付けられたすべての値を合計します。

ネガフィボナッチ表現

ネガフィボナッチ符号は、数学者が時折用いる位取り記数法であるネガフィボナッチ表現と密接に関連しています。特定の非ゼロ整数のネガフィボナッチ符号は、その整数のネガフィボナッチ表現と全く同じですが、桁の順序が逆になり、末尾に「1」が付加されます。すべての負の数のネガフィボナッチ符号は奇数桁ですが、すべての正の数のネガフィボナッチ符号は偶数桁です。

テーブル

-11 から 11 までの整数のコードは以下のとおりです。

番号	ネガフィボナッチ表現	ネガフィボナッチコード
−11	101000	0001011
−10	101001	1001011
−9	100010	0100011
−8	100000	0000011
−7	100001	1000011
−6	100100	0010011
−5	100101	1010011
−4	1010	01011
−3	1000	00011
−2	1001	10011
−1	10	011
0	0	（エンコードできません）
1	1	11
2	100	0011
3	101	1011
4	10010	010011
5	10000	000011
6	10001	100011
7	10100	001011
8	10101	101011
9	1001010	01010011
10	1001000	00010011
11	1001001	10010011

参照

参考文献

引用文献

クヌース、ドナルド (2008).ネガフィボナッチ数と双曲平面. アメリカ数学会年次大会. カリフォルニア州サンノゼ.
ドナルド・クヌース（2009年）『コンピュータプログラミングの技法』第4巻、冊子1：ビットごとのトリックとテクニック、二分決定図、アディソン・ウェズリー社、ISBN 978-0-321-58050-4。セクション7.1.3の出版前草案では、特に36～39ページを参照してください。
マーゲンシュテルン、モーリス (2008). 双曲空間におけるセルオートマトン. 非従来型コンピューティングとセルオートマトンにおける進歩. 第2巻. 現代アーカイブ. p. 79. ISBN 9782914610834。