word

  • イーサネットに使用されているCRCは、IEEE803.2CRCという32bitのCRCです。参考文献１※によると、メッセージの大きさ（ｍ）を12,112bit（＝1,514byte）とすると、IEEE803.2CRCのHamming距離（ｄ）は、４となるようです。冗長ビット（ｒ）は32bitですから、全体のビット列（ｎ）は、12,144bitになります。

  • 数学的に均等に分布しているとして、Brute Methodで（：強引に計算する手法、単に力技で数えるという意味）計算機を用いて計算すると、補足①LinkIconに示したＡ Ｋ が（参考文献ではＷｉとあらわしている）、Ａ２=０、Ａ３=0、A4=223,059…..となることが例示されています。（すみません。筆者は検算していません。）

  • これは、このCRC計算に使用する生成多項式では、２ビット、３ビットエラーでは検知が確実にできるものの、４ビットエラーでは、223,059通りの「正しい符号」が存在することを示しています。

  • つまりイーサネットで、12,112bit（=1,514byte）のパケットを送った場合、経路上で４ビット化けると、CRCチェックでは検知できない組合せの化け方が、223,059種類有るということです。結構多い気がしますね。

  • 符号（ｒ）を含めた全体のビット数（ｎ）は、12,144bitですから、4ビット化ける組合せは、

  • word065_01.jpg

  • この組合せの総数の中で、特定の化け方が発生する確率は、

  • word065_02.jpg

  • となります。小さいといえば小さいですが、「０」ではないことがわかるかと思います。

  • 補足リンク①LinkIconで、「ｒ」ビットのCRCを付加することで、メッセージの空間を広げること、また、補足リンク②LinkIconで、残存エラーの確率が　１／２ ｒ だけ薄まることをお話しました。
  • このときの薄まり方は、３２ビットのCRCであれば、

  • word065_03.jpg

  • です。いかがでしょうか。通常メッセージが4ビット化けてしまうとおそらく何らかの別な意味のメッセージに変わってしまいますが、32ビットのCRCの効果で、そのような別のメッセージになってしまう確率が、１０ -10 すなわち、１／２ ｒ だけ薄まっているという考え方の実例でもあるといえるでしょう。




  • ※ 参考文献１
  • Philip Koopman," 32-Bit Cyclic Redundancy Codes for Internet Applications", Preprint of a regular paper to appear in The International Conference on Dependable Systems and Networks (DSN) 2002