CRC – 巡回冗長性検査

Facebooktwittergoogle_plustumblrmail
CRC を手計算で検算してみる。 ASCII 文字 ‘y’ の 8bit 用 CRC (CRC-8) を手計算したい。どうしてこの文字にしたのか ? だって y は yes にも含まれていて前向きな感じがするし、その上僕の名前の一部でもあるし、つまりその、何かと縁起の良い文字なので。 じゃあ早速。 CRC を計算する時に必要な物は…
  • 計算対象データ (当たり前だ)
  • 生成多項式 (Polynomial)
  • 初期値
  • 仕上げの XOR 値 (計算結果の CRC と XOR 取る場合に使う)
  • 比較方向
で、今回の条件は以下…
  • 計算対象データ : ‘y’ (== 0x79 == 0y01111001)
  • 生成多項式 : x8 + x5 + x4 + 1 (Maxim の 1-Wire で使っている版→ WikiPedia より)
  • 初期値 : 0x00 (== 0y00000000)
  • XOR 値 : 無し
  • 比較方向 : 若い番地のバイトから順番に

ヒント : 生成多項式中の各項 x[1-9]+ の数字部分はビット位置を表していて、例えば「 x5 」だったら bit-5 が 1 という意味と見れば良いです。定数項っぽく見える「 + 1 」は x0 の事、つまり bit-0 が 1 っていう事なんだと捉えれば OK 。

ここからは全部 2 進数に直して計算。計算対象は 0y01111001 で、これの bit-0 の後ろに初期値 0y00000000 をドッキングさせて「 0y0111100100000000 」 (*1) にする。また生成多項式は「 x8 + x5 + x4 + 1 」だから、 2 進数で表現すれば「 0y100110001 」 (*2) 。この (*1) を (*2) で割り算よろしく、ビットの比較方向に沿って xor していけば良い (今回は計算対象が 1 バイトだけなので比較方向は気にしなくて良いね) 。
【CRC の計算】
                     1110000  <- 割り算では商にあたる所
          ------------------    (CRC 計算では無視して良い)
100110001 ) 0111100100000000
         xor)100110001
         -------------
             0110101010
          xor)100110001
         -------------
              0100110110
           xor)100110001
           -----------------
                     1110000 <- 割り算では余りにあたる所
                               (これが計算結果の CRC)
これで CRC は 0x70 と分かった。 さて次は、データ化けが無いかどうかを確かめる為の検算方法を。検算の時は、 CRC を初期値にして再度 CRC を計算し直し、その結果が 0 になる事を確認すれば良い。さっきと同様、計算対象 0y01111001 に初期値 0y01110000 をドッキングさせて「 0y0111100101110000 」 (*3) 、この (*3) を (*2) で xor していけば良い。
【 CRC を使ったデータの検算 (正常の場合) 】
                     1110000
          ------------------
100110001 ) 0111100101110000
         xor)100110001
         -------------
             0110101001
          xor)100110001
          -------------
              0100110001
           xor)100110001
           -----------------
                           0 <- 検算 OK!
一方、計算対象にデータ化け有ると、検算結果は 0 にならない。もし ‘y’ (== 0y01111001) が ‘z’ (== 0y01111010) に化けてたらどうなるか…
【 CRC を使ったデータの検算 (異常の場合) 】
                     1110011
          ------------------
100110001 ) 0111101001110000
         xor)100110001
         -------------
             0110110001
          xor)100110001
          -------------
              0100000001
           xor)100110001
           -------------
               000110000000
              xor)100110001
              -------------
                  0101100010
               xor)100110001
               -------------
                     1010011 <- 検算 NG!
                               (0 にならない)
…これって、割り算したら余る分を、予め計算対象から差し引いてから同じ割り算をすれば、余りを出さずに割り切れる、というのに似てるよねえ。
Facebooktwittergoogle_plustumblrmail
Yusuke Dada K.
Yusuke Dada K.
台湾の現地企業で主に組み込みソフトウエアの研究開発をしている日本人です。我人是個日本人,負責軟體的研究開發。在臺灣的科技公司工作。

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です