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

数学とコンピューターにおいて、フィボナッチ コーディングは、正の整数を 2 進コード ワードにエンコードする汎用コード^[要出典]です。これは、フィボナッチ数に基づく整数の表現の一例です。各コード ワードは「11」で終わり、末尾より前に「11」のインスタンスは含まれません。

フィボナッチ コードは、ゼッケンドルフ表現と密接に関連しています。ゼッケンドルフ表現は、ゼッケンドルフの定理を使用し、連続する 1 で表現される数字がないという特性を持つ位置記数法です。特定の整数のフィボナッチ コード ワードは、その整数のゼッケンドルフ表現の桁の順序が逆になり、末尾に「1」が追加されたものです。

数値 について、が を表すコードワードの数字を表す場合、次の式が得られます。 ${\displaystyle N\!}$${\displaystyle d(0),d(1),\ldots ,d(k-1),d(k)\!}$${\displaystyle N\!}$

${\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番目の異なるフィボナッチ数です。最後のビットは常に 1 が追加され、位の値を持ちません。 ${\displaystyle 1,2,3,5,8,13,\ldots }$${\displaystyle d(k)}$

このようなコーディングは一意であり、コードワード内で「11」が出現するのは最後、つまりd ( k −1) とd ( k ) のみであることが示されています。最後から 2 番目のビットが最上位ビットで、最初のビットが最下位ビットです。また、先頭のゼロは、たとえば 10 進数のように省略することはできません。

以下に、最初のいくつかのフィボナッチ コードと、いわゆる暗黙の確率 (フィボナッチ コードで最小サイズのコードを持つ各数値の値) を示します。

整数Nをエンコードするには:

1. N以下の最大のフィボナッチ数を見つけ、その数をNから減算し、余りを記録します。
2. 減算した数がi番目のフィボナッチ数F ( i )だった場合、コードワードのi −2番目の桁に1を入れます（左端の桁を0番目の桁として数えます）。
3. 剰余が 0 になるまで、Nに剰余を代入して前の手順を繰り返します。
4. コードワードの右端の数字の後に 1 を追加します。

コードワードをデコードするには、最後の「1」を削除し、残りの値 1、2、3、5、8、13... (フィボナッチ数) をコードワードのビットに割り当て、「1」ビットの値を合計します。

フィボナッチ コーディングには、他のユニバーサル コードと比較して魅力的になることがある便利な特性があります。それは、自己同期コードの例であり、破損したストリームからデータを回復しやすくなります。他のほとんどのユニバーサル コードでは、1 つのビットが変更されると、その後のデータは正しく読み取られません。一方、フィボナッチ コーディングでは、変更されたビットによって 1 つのトークンが 2 つとして読み取られたり、2 つのトークンが誤って 1 つとして読み取られたりしますが、ストリームから "0" を読み取ると、エラーがそれ以上伝播するのを止めます。"0" が含まれない唯一のストリームは "11" トークンのストリームであるため、1 ビット エラーによって破損したストリームと元のストリームとの間の合計編集距離は最大で 3 です。

このアプローチは、いくつかのパターン（「11」など）が禁止されているシンボルのシーケンスを使用してエンコードするものであり、自由に一般化できます。^[1]

次の表は、65 = 2 + 8 + 55であるため、数値 65 がフィボナッチ コードで 0100100011 として表されることを示しています。最初の 2 つのフィボナッチ数 (0 と 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}}}$

正の整数のフィボナッチ エンコーディングは、"11" で終わり、"11" が他に含まれないバイナリ文字列です。これは、N 個の連続する 1 で終わり、N 個の連続する 1 が他に含まれないバイナリ文字列に一般化できます。たとえば、N = 3 の場合、正の整数は 111、0111、00111、10111、000111、100111、010111、110111、0000111、1000111、0100111、… とエンコードされます。この場合、文字列の長さの関数としてのエンコードの数は、トリボナッチ数 のシーケンスによって与えられます。

特定のシンボルの後にどのシンボルが許可されるかを定義する一般的な制約については、まず最大エントロピーランダムウォークを使用して最適な遷移確率を見つけ、次にエントロピーコーダ（デコーダ付きスイッチエンコーダ付き）を使用して、見つかった最適な遷移確率を満たすシンボルのシーケンスとしてメッセージをエンコードすることで、最大情報レートを取得できます。

• 黄金比ベース
• ネガフィボナッチコーディング
• オストロフスキー記数法
• ユニバーサルコード
• バリコード、実用的なアプリケーション
• ゼッケンドルフの定理
• 最大エントロピーランダムウォーク

• アルーシュ、ジャン=ポール、シャリット、ジェフリー(2003)。自動シーケンス: 理論、アプリケーション、一般化。ケンブリッジ大学出版局。p. 105。ISBN 978-0-521-82332-6.ZBL1086.11015  。​
• Fraenkel, Aviezri S.; Klein, Shmuel T. (1996). 「送信と圧縮のための堅牢なユニバーサル完全コード」.離散応用数学. 64 (1): 31–55. CiteSeerX  10.1.1.37.3064 . doi :10.1016/0166-218X(93)00116-H. ISSN  0166-218X. Zbl  0874.94026.

• Stakhov, AP (2009). 『調和の数学：ユークリッドから現代数学およびコンピュータサイエンスまで』 シンガポール：World Scientific Publishing .