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

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

アルゴリズム

まずデータを値の列として用意し、また合同式の法をと定義する。チェックサム用の変数を用意し、数列を以下のように計算する。

この時  と  の値を並べたものがフレッチャーのチェックサムである。

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

 バリエーション  データの幅  合同式の法  チェックサムのビット数  Fletcher-16  8bit    16bit Fletcher-32  16bit    32bit Fletcher-64  32bit    64bit

また、剰余演算を避けるため、法をの形へと簡略化した独自実装がなされる事がある。
 FreeBSD 9.1R ソースコード zfs_fletcher.c rev243808 2013年7月1日閲覧

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

 ………

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

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

脚注

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

Category:誤り検出訂正
Category:エポニム