word

CRC(Cyclic Redundancy Check)
と表現空間の拡張





  • 本文に有るように、特定のビット列でメッセージのデータを割り、その余りをメッセージの冗長情報として使用する手法です。送信側で一度計算し、メッセージのデータと一緒に送ります。受信側では、受け取ったメッセージを、同じ特定ビット列で同じように割算し、その結果が一致すれば、メッセージは正しく受け取れたと判断するのです。

  • word062_01.jpg

  • たとえば、メッセージが8ビット(m=8)で、冗長符号が3ビット(r=3)とします。この場合、次のような処理をします。

  • メッセージ:11001100
  • 法数   :101

  • ここで少し特殊な割算をします。これはMod(2)の割算といって、桁の繰上げ繰り下げがない方法で、計算機にとって計算しやすい手法です。今回余りがきちんとメッセージと対になればよいのですから、このような計算方法でも特に問題ありません。

  • この結果上の例で計算すると、余り、つまりメッセージに付加する冗長符合は、「000」となります。もしもメッセージが化けて、「11001101」となれば、計算結果は、「001」となりますから、メッセージにデータ化けがあることがわかります。

  • 余りのバリエーションは、000~111までの8種類ありますから、ある特定のメッセージを表すビット列が、「11001100」という1種類から、8種類に増加させることが出来たと表現できます。表したいメッセージ、つまり伝えたいメッセージの量(種類)は変わりませんが、ビット列のバリエーションが8倍に増え、その差の部分はエラー(意味のない情報)として埋められることになります。

  • このように、CRCとは、意味の有るメッセージの実際のビット列がどのようなものかとは無縁に、冗長ビットの分だけ表現できるビット列の空間を均等に広げる効力が有る、といえます。

  • 3ビットならば8倍に、4ビットならば16倍に広げます。32ビットならば、均等に2 32 倍(4,294,967,296倍≒10 10 )だけ表現する空間を広げる効果があります。広がった空間の中に、意味の有る情報がまばらに散っており、その間のビット列には意味がない、すなわちそれがエラーであることが検知できるビット列であるといえるのです。

  • したがって、あるメッセージの意味を表す空間全体をAとすると、「r」ビットのCRCを付加することで、Aの空間を、以下のように拡張できたということが出来ます。

  • A → 2 × A

  • オリジナルメッセージの空間Aには、意味とビット列の表現に偏りが多少有るかもしれません。しかし、2 が大きくなれば、オリジナルの空間の散らばりよりも、CRC符号による散らばりが支配的になってきます。
  • このことより、ある特定の情報が別な意味の有る情報に変化する確率は、もともとの変化する確率がPだとした場合、CRCをつけることにより、P× 1/2 だけ小さくなった、と表現することが出来ます。


  • word062_02.jpg