フレッチャーのチェックサム
フレッチャーのチェックサム(英: Fletcher's checksum)は、ジョン・G・フレッチャー(John G. Fletcher)が考案した誤り検出符号の一種である。単純なチェックサムより信頼性が高い。
アルゴリズム 編集
まずデータを値の列 として用意し、また合同式の法を と定義する。チェックサム用の変数 を用意し、数列を以下のように計算する。
この時 と の値を並べたものがフレッチャーのチェックサム である。
バリエーション 編集
フレッチャーのチェックサムには、エンディアン、データの分割幅および変数 の法 ごとにいくつかのバリエーションがある。
バリエーション | データ の幅 | 合同式の法 | チェックサムのビット数 |
---|---|---|---|
Fletcher-16 | 8bit | 16bit | |
Fletcher-32 | 16bit | 32bit | |
Fletcher-64 | 32bit | 64bit |
また、剰余演算を避けるため、法を の形へと簡略化した独自実装がなされる事がある。 [1]
多次のフレッチャーのチェックサム 編集
フレッチャーのチェックサムを強化したものとして、変数を の2変数から、3変数以上に自然に拡張したものがある。この場合の計算は下のように行われる。
- ………
フレッチャーのチェックサムの基本形は二次の形式であり、 単純なチェックサムは一次のフレッチャーチェックサムの一種であるとみなせる。
使用例 編集
ZFSでは、データを64bitごとに分割し、奇数番目と偶数番目のデータを分離してそれぞれ別に Fletcher-128 を計算する fletcher2 と、データ32bit、変数幅64bitの、四次のフレッチャーチェックサムを用いる fletcher4 が使用されている。 また、TCP用のチェックサムのオプションとしても規格化されている。 [2]