ネガフィボナッチコーディング

数学において、ネガフィボナッチ コーディングは、ゼロ以外の整数をバイナリコード ワードにエンコードする汎用コードです。正の整数と負の整数の両方を表現できることを除いて、フィボナッチ コーディングに似ています。すべてのコードは「11」で終わり、末尾の前に「11」はありません。

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

1. が正の場合、-1 から -2 のステップでネガフィボナッチ数列の奇数の負の項の合計がより大きいか等しい最大の奇数の負の整数を計算します。が負の場合、 0 から-2 のステップでネガフィボナッチ数列の偶数の負の項の合計がより小さいか等しい最大の偶数の負の整数を計算します。${\displaystyle x}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$
   ${\displaystyle 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).}$
   ${\displaystyle x}$${\displaystyle n}$${\displaystyle n}$${\displaystyle x}$
   ${\displaystyle 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)}$
2. バイナリワードのビットに 1 を追加します。から減算します。${\displaystyle |n|^{\text{th}}}$${\displaystyle f(n)}$${\displaystyle x}$
3. xの新しい値が0 に達するまで、手順 1 からのプロセスを繰り返します。
4. 結果のバイナリ ワードの左側に 1 を追加して、エンコードを終了します。

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

ネガフィボナッチ コーディングは、数学者が時々使用する位置記数法であるネガフィボナッチ表現と密接に関連しています。特定の非ゼロ整数のネガフィボナッチ コードは、その整数のネガフィボナッチ表現とまったく同じですが、桁の順序が逆で、末尾に「1」が追加されています。すべての負の数のネガフィボナッチ コードの桁数は奇数ですが、すべての正の数のネガフィボナッチ コードの桁数は偶数です。

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

• フィボナッチ数列
• 黄金比ベース
• ゼッケンドルフの定理