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

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

まずデータを値の列${\displaystyle d_{i}(1<i<n)}$として用意し、また合同式の法を${\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 d}$の幅	合同式の法${\displaystyle m}$	チェックサムのビット数
Fletcher-16	8bit	${\displaystyle 2^{8}-1}$	16bit
Fletcher-32	16bit	${\displaystyle 2^{16}-1}$	32bit
Fletcher-64	32bit	${\displaystyle 2^{32}-1}$	64bit

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

フレッチャーのチェックサムを強化したものとして、変数を${\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用のチェックサムのオプションとしても規格化されている。 ^[2]

1. ^ [1] FreeBSD 9.1R ソースコード zfs_fletcher.c rev243808 2013年7月1日閲覧
2. ^ [2] J. Zweig, C. Partridge, "TCP Alternate Checksum Options", RFC1146, 1990.

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