フレッチャーのチェックサム

フレッチャーのチェックサム（英: Fletcher's checksum）は、ジョン・G・フレッチャー（John G. Fletcher）が考案した誤り検出符号の一種である。単純なチェックサムより信頼性が高い。

アルゴリズム

まずデータを値の列${\displaystyle d_{i}(1$として用意し、また合同式の法を${\displaystyle m}$と定義する。チェックサム用の変数${\displaystyle A_{i},B_{i}(A_{0}=B_{0}=0)}$を用意し、数列を以下のように計算する。

${\displaystyle A_{i}=A_{i-1} d_{i}}$

${\displaystyle B_{i}=B_{i-1} A_{i}}$

この時 ${\displaystyle B_{n}{\pmod {m}}}$ と ${\displaystyle A_{n}{\pmod {m}}}$ の値を並べたものがフレッチャーのチェックサム${\displaystyle S}$である。

バリエーション

フレッチャーのチェックサムには、エンディアン、データの分割幅および変数${\displaystyle A,B}$の法${\displaystyle m}$ごとにいくつかのバリエーションがある。

また、剰余演算を避けるため、法を${\displaystyle 2^{n}}$の形へと簡略化した独自実装がなされる事がある。

多次のフレッチャーのチェックサム

フレッチャーのチェックサムを強化したものとして、変数を${\displaystyle A,B}$の2変数から、3変数以上に自然に拡張したものがある。この場合の計算は下のように行われる。

${\displaystyle A_{i}=A_{i-1} d_{i}}$

${\displaystyle B_{i}=B_{i-1} A_{i}}$

${\displaystyle C_{i}=C_{i-1} B_{i}}$

${\displaystyle D_{i}=D_{i-1} C_{i}}$

………

フレッチャーのチェックサムの基本形は二次の形式であり、 単純なチェックサムは一次のフレッチャーチェックサムの一種であるとみなせる。

使用例

ZFSでは、データを64bitごとに分割し、奇数番目と偶数番目のデータを分離してそれぞれ別に Fletcher-128 を計算する fletcher2 と、データ32bit、変数幅64bitの、四次のフレッチャーチェックサムを用いる fletcher4 が使用されている。 また、TCP用のチェックサムのオプションとしても規格化されている。

脚注

関連項目

• チェックサム
• Adler-32 - Fletcher-32 を改良したもの
• 巡回冗長検査