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

フレッチャーのチェックサム（英: Fletcher's checksum）は、ジョン・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}{\pmod {m}}$ と $A_{n}{\pmod {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 を改良したもの
• 巡回冗長検査