CRC（巡回冗長検査）をやさしく理解する

　CRCをとにかくシンプルにわかりたい腑に落ちたい

#やること
送信されたデータが正しいかどうかをチェックする仕組みにCRC（巡回冗長検査）という方式があるそうです。ZIPやPNG、ネット通信のさまざまなところで使われているようです。
仕組みとしては、送信したデータが正確に送られているかどうかを検証するためのデータ（CRC値）も元データにくっつけて一緒に送信し、受信側で確認できるようにするものらしいです。

そのCRC値というのが一体どうやって作られているのかが気になって眠れません。
ということでCRCの概要を調べて理解するとともに、基本的な計算方法をpythonで可視的にコード化してみようと思います。

#環境

• Python (コードはColab環境やJupyterNotebookでも動きます）
• Python等の初歩的な理解（リスト型が何なのかを知っている）

#わからないポイント
まずCRCの理解を妨げているポイントを絞って行きます。

• そもそものしくみがわからない
• ２進数の割り算がわからない
• 計算アルゴリズムがわからない

以上が分かればCRCの基本が理解できそうです。

##理解を助けるサイト
さっそく上記のわからないポイントをクリアしていきます。ネットで調べた結果、以下のサイトが非常に解りやすいと感じました。ありがたいです。
まったく初めてという方でも、順に読むことで理解できるようになると思います。たぶん。

###CRCの概要を理解するためのサイト

• 【一陸技】無線工学A CRC、生成多項式、剰余
  → 陸上無線技術士資格の問題を解く動画です。約7分。とてもわかりやすいです。

• CRC-32
  → CRCについて解説スライドシェアです。p6-p23のページが脳にやさしいです。

###CRCの計算方法を理解するためのサイト

• CRC の計算方法
  → CRCの解説です。2進数の割り算について丁寧な解説があり、非常に理解が深まります。

上記を読んで概要を理解できたら、あとはコード化してくだけです。
が、ネットで紹介されているコードは初心者にはちょっと難しいと感じました。
そこで、解説通りに実直にコード化してみることにしました。

##上記サイトで学んだ基本原理をコードに落とし込む

pythonとリストを使います。

###コード
間違っている箇所があったらすみません。
解説はコードの中に書き込みました。

crc.py

#対象データの設定（解説書で多項式と呼ばれているもの）
msg ="0b111010110111100110100010101"
#生成多項式の設定　※必ず最上位桁が１になるように指定
poly ="0b1011"

#バイナリデータを扱いやすい形にフォーマットし、画面に表示する
msg = format(int(msg,2),'0'+str(len(msg)-2)+'b')#データをフォーマット（左端は０パディング）
print("対象データ(多項式) : "+msg)
poly = format(int(poly,2), '0'+str(len(poly)-2)+'b')#生成多項式をフォーマット
print("生成多項式 : "+poly)

#計算用の変数やリストを準備する
msg_list = [] #データ用リスト
poly_list = [] #生成多項式用リスト
crc_list = [] #CRC結果用リスト
crc = 0  #CRCの結果（crc_listの数値）

#バイナリデータをリストに格納していく
for i in msg:#データをリスト化
  msg_list.append(int(i))

for i in poly:#生成多項式をリスト化
  poly_list.append(int(i))

for i in range(len(poly_list)-1):#生成多項式の次数分、多項式にゼロをつける処理
  msg_list.append(0)

#計算前の対象データを表示する
print(str(msg_list)+" 対象データ(多項式)")#

#XOR計算を行う（メイン処理）
for i in range(len(msg_list) - len(poly_list)+1):#計算の最大回数を算出
  #print(i, end=" ")
  if msg_list[i] == 1:#データの左端から調べ、1を見つけたら生成多項式でXOR計算
    for j in range(len(poly_list)):
      msg_list[i+j] = msg_list[i+j] ^ poly_list[j]
    print(msg_list, end=" ")
    print("左から"+ str(i+1) +"桁目のXOR算結果")#計算結果の経過報告

#CRC値の計算結果（データを生成多項式で割った余りの値）をリストと変数に格納する。
for i in range(len(poly_list)-1):#生成多項式の左端が1なので、CRC値の桁は生成多項式-1になる
  crc_list.append(msg_list[len(msg_list) - len(poly_list)+1+i])#余りの部分をCRCのリストに格納
  crc = crc + 2**(len(poly_list)-2-i)*crc_list[i]#CRCのリストから数値に変換
  #↑CRCの桁数は生成多項式の左端が1なので生成多項式より1桁以上少なくなる。
  #↑またリストのインデックスが0から始まるため、len(poly_list)-2
  #↑その数値を2の乗数としてバイナリの各要素に順にかけて数値に戻す。

print(str(crc_list)+" : CRCの計算結果 （多項式 / 生成多項式 の余りの値）")
print("CRCのバイナリ : " + str(bin(crc)))
print("CRCのHEX   　  : " + str(hex(crc)))
print("CRCの整数      : " + str(crc))

###使い方
チェックの対象となるデータを、冒頭のmsgの"0b"に続けてバイナリ形式で挿入してください。
同じく、生成多項式を、polyの"0b"に続けてバイナリ形式で挿入してください。
pythonの実行方法については割愛します。

##実行結果例

手で計算したときと同じような感じで、経過を表示しつつCRC値を求めます。

送信者はこのCRC値を元のデータにくっつけて送信すればよいわけですね。
データを受信した側は受け取ったデータからCRC値を外したものに対して生成多項式で同じ計算を行い、結果がCRCと合致すれば検算OK、ということになるかと思います。

##このあと
実践的に使う場合にはビットシフトを使って計算したり、計算を簡略化する方法があるようです。
また、同様に検証する場合にも実直に計算するのではなくマジックナンバーという数値を求めて検証するという方法などが主流のようです。
この記事はあくまでCRCの基本ということですので、一旦ここで終了します。

##まちがっているかも
間違っている箇所や変な箇所があったらすみません。修正しますのでぜひご指摘ください。

参考

下記のサイトを参考にさせていただきました。ありがとうございました。

• 【一陸技】無線工学A CRC、生成多項式、剰余
• CRC-32
• CRC の計算方法
• CRC32の逆演算Pythonコード
• Cyclic Redundancy Check(CRC)を理解する
• Wikipedia:CRC（巡回冗長検査）
• 巡回冗長検査(CRC)のよくある実装の説明