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

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

アルゴリズム[編集]

まずデータを値の列di (1 < i < n)を用意し、また合同式のmと定義する。検査合計用の変数Ai, Bi (A0 = 0, B0 = 0) を用意し、数列を以下のように計算する。

Ai = Ai − 1 + di
Bi = Bi − 1 + di

この時Bn (mod m)An (mod m)の値を並べたものがフレッチャーの検査合計Sである。

バリエーション[編集]

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

バリエーション データdの幅 合同式の法m 検査合計のビット数
Fletcher-16 8 bit 28 − 1 16bit
Fletcher-32 16 bit 216 − 1 32bit
Fletcher-64 32 bit 232 − 1 64bit

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

多次のフレッチャーの検査合計[編集]

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

Ai = Ai − 1 + di
Bi = Bi − 1 + Ai
Ci = Ci − 1 + Bi
Di = Di − 1 + Ci
………

フレッチャーの検査合計の基本形は二次の形式であり、 単純な検査合計は一次のフレッチャー検査合計の一種であるとみなせる。

使用例[編集]

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.

関連項目[編集]