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

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

アルゴリズム

まずデータを値の列$d_i(1<i<n)$として用意し、また合同式の法を$m$と定義する。チェックサム用の変数$A_i,B_i(A_0=B_0=0)$を用意し、数列を以下のように計算する。

$A_i=A_{i-1}+d_i$

$B_i=B_{i-1}+A_i$

この時 $B_n(\mathrm{mod}m)$ と $A_n(\mathrm{mod}m)$ の値を並べたものがフレッチャーのチェックサム$S$である。

バリエーション

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

バリエーション	データ$d$の幅	合同式の法$m$	チェックサムのビット数
Fletcher-16	8bit	$2^8-1$	16bit
Fletcher-32	16bit	$2^{16}-1$	32bit
Fletcher-64	32bit	$2^{32}-1$	64bit

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

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

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

$A_i=A_{i-1}+d_i$

$B_i=B_{i-1}+A_i$

$C_i=C_{i-1}+B_i$

$D_i=D_{i-1}+C_i$

………

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

使用例

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

関連項目

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