// フィボナッチ符号 - 黄金比の数学に基づく自己同期コード
追加パラメータなしで任意の正の整数に対応します。
パターン11を利用して伝送エラー後に同期を回復できます。
フィボナッチ数列とツェッケンドルフの定理に基づいています。
フィボナッチ符号はツェッケンドルフの定理を利用します。すべての正の整数は隣接しないフィボナッチ数の和として一意に表現できます。コードはこの表現を2進数で表したもので、使われるフィボナッチ数に対応する位置が1、使われない位置が0になり、その後ろに終端としてもう1ビットの1を付加します。パターン11はコード語の末尾にしか現れません。
フィボナッチ数列: 1, 2, 3, 5, 8, 13, 21... 1 = F(1) → 11 2 = F(2) → 011 3 = F(3) → 0011 4 = F(3)+F(1) → 1011 5 = F(4) → 00011 12 = F(5)+F(3)+F(1) → 101011 隣り合うフィボナッチ数は使用しない パターン11はコード末尾にのみ現れる
フィボナッチ符号は、フィボナッチ数列を用いて正の整数を表現する普遍コードです。ツェッケンドルフの定理に基づき、パターン11が終端としてのみ現れる自己同期コードを生成します。
ツェッケンドルフの定理は、すべての正の整数が隣り合わないフィボナッチ数の和として一意に表現できることを述べています。この表現がフィボナッチ符号の基礎です。
パターン11つまり連続する2つの1ビットは各コード語の末尾にしか現れません。そのため、伝送エラーの後でもデコーダは11を探すことでコード語の境界を再び見つけることができます。
フィボナッチ符号はデータ圧縮の研究、誤りに強い伝送システム、理論計算機科学などで利用されています。実用効率よりも、その数学的性質が評価されることが多い方式です。