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

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

アルゴリズム

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

$A_{i}=A_{i-1}+d_{i}$$A_{i}=A_{i-1}+d_{i}$

$B_{i}=B_{i-1}+A_{i}$$B_{i}=B_{i-1}+A_{i}$

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

バリエーション

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

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

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

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

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

$A_{i}=A_{i-1}+d_{i}$$A_{i}=A_{i-1}+d_{i}$

$B_{i}=B_{i-1}+A_{i}$$B_{i}=B_{i-1}+A_{i}$

$C_{i}=C_{i-1}+B_{i}$$C_{i}=C_{i-1}+B_{i}$

$D_{i}=D_{i-1}+C_{i}$$D_{i}=D_{i-1}+C_{i}$

………

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

使用例

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

関連項目

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