コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

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

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

フレッチャーのチェックサム(: 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]

脚注

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

関連項目

[編集]