CRC（Cyclic Redundancy Check）の初期値とかシフト方向とか出力とか
CRC（Cyclic Redundancy Check）について
巡回冗長検査（じゅんかいじょうちょうけんさ、英: Cyclic Redundancy Check, CRC）は、誤り検出符号の一種で、主にデータ転送などに伴う偶発的な誤りの検出によく使われている。送信側は定められた生成多項式で除算した余りを検査データとして付加して送信し、受信側で同じ生成多項式を使用してデータを除算し、その余りを比較照合することによって受信データの誤り・破損を検出する。
巡回冗長検査 - Wikipedia
↑のようなちょっとググればすぐ出てくるような基本的なことは知っているつもりだったのですが、先日、仕事でとある通信プロトコルの仕様書に書かれているCRCの仕様に、こんなことが書かれていました。
- 生成多項式：X^16 + X^12+ X^5 + 1
- 初期値：0xFFFF
- シフト方向：右
- 出力：反転
生成多項式ならよく知っているけど、
初期値？
シフト方向？
出力？
はて、何のことやら・・・
だったので、あれこれ調べた内容を備忘録として書き留めます。
手計算によるCRC計算の流れ
まず、これまでに私が知っていたネットでググればすぐに出てくるCRC計算の流れについて、簡単にまとめます。
ここでは、0x31、0x32（0011000100110010）という16bitデータに対して、上記の生成多項式X^16 + X^12+ X^5 + 1（10001000000100001）でCRCを計算する場合を例として扱います。
以下に、CRCの計算の流れを図示します。
図1 手計算によるCRC計算の流れ
CRC計算対象のデータの後部に16bitのゼロパディングを行い、生成多項式のビット列で筆算の除算のような計算を行っていきます。
ただしこのとき、桁の繰り上げ、繰り下げは行わないので、各桁の計算はXOR算と等価となります。
そして、これ以上割り切れなくなった状態の余りの下位16bit（0x20B5）がCRCの計算結果となります。
しかしこれだけ見ていても、何が初期値で、シフト方向とは何をシフトする方向で、出力とはどの部分の計算結果なのかがいまいちよくわかりません。
ですので、次に上記の計算をプログラムで実装してみます。
プログラムによるCRC計算の流れ
今回はPythonを使って、上記のCRC計算を実装してみます。
コードの例は↓な感じです。
def calc_crc16(data): crc = 0x0000 # 初期値（使用するのは下位16bitのみ） poly = 0x1021 # 生成多項式（X^16 + X^12 + X^5 + 1)。図1の緑ハッチ部分16bit length = len(data) for i in range(0, length): crc = crc ^ (data[i] << 8) # CRCの上位8bitと入力データのXOR算 for j in range(0, 8): if(crc & 0x8000 == 0x8000): # crcの先頭ビットが1のとき、crcを「左に1bit」シフトし、生成多項式とXOR算 crc = poly ^ ( crc << 1) else: # crcの先頭ビットが0のとき、crcを「左に1bit」シフトするのみ crc = (crc << 1) return crc & 0xffff #下位16bitのみが有効な計算値なので、0xffffでANDを取る data = [ 0x31, 0x32] crc = calc_crc16(data) print("CRC16:" + hex(crc))
コード内のコメントに先に結論を書いてしまっていますが、あれこれ調べまわった結果、
- 初期値：CRC計算結果を格納する変数の初期値
- シフト方向：割られる数のビットシフトの方向
なのでした。
これは実際にコード書いて実装してみないとなかなか意味を理解するのが難しいと思います・・・
ちなみに上記のコードの計算の流れを図式化するとこんな感じになります。
図2 プログラムによるCRC計算の流れ
プログラム上では8bitずつCRC計算を行っていくことになるため、こんな計算のやり方で手計算の場合と結果が一致するのかと初めは疑問でしたが、図式化するとイメージが湧きやすくなりました。
初期値は無意識のうちに0x0000にしてしまっていましたのですね(;^_^A
さて、ここまでで初期値とシフト方向：左の意味は分かりましたが、
- シフト方向：右
- 出力：反転
についてはこれだけではまだわかりません。
シフト方向：右とは
冒頭で示した図1で示した筆算形式のCRC演算では、シフト方向が左というのは容易に理解できましたが、シフト方向が右というのは果たしてどういうことなのか、最初は全く意味が不明でした。あれこれネットで調べていたら、またWikipediaで気になる記事を見つけました。
「シリアルポートでは最下位ビットを先に転送する」という一文で全ての謎が解けました。
まず、この場合のCRCの手計算の流れを図示すると以下のようになります。
図3 手計算によるCRC計算の流れ（LSBから伝送）
先ほどの図1との違いは、CRC計算対象のデータ0x31、0x32の各バイトのビットの並びがLSBが先頭となっている点です。
違いはこれだけです。
後の計算の流れは全く同じです。（計算結果はもちろん異なりますが・・・）
次にこの計算をプログラムで実行する場合を考えます。
Pythonのコードは以下のようになります。
def calc_crc16(data): crc = 0x0000 # 初期値（使用するのは下位16bitのみ） poly = 0x8408 # 生成多項式（X^16 + X^12 + X^5 + 1) length = len(data) for i in range(0, length): crc = crc ^ data[i] # CRCの下位8bitと入力データのXOR算 for j in range(0, 8): if(crc & 0x0001 == 0x0001): # crcの最下位が1のとき、crcを「右に1bit」シフトし、生成多項式とXOR算 crc = poly ^ ( crc >> 1) else: # crcの最下位ビットが0のとき、crcを「右に1bit」シフトするのみ crc = (crc >> 1) return crc & 0x0000ffff data = [ 0x31, 0x32] crc = calc_crc16(data) print("CRC16:" + hex(crc))
図1と図3ではCRC計算対象の各バイトデータのビットの並びが逆転しているだけの違いでしたが、これをプログラムのコードに書き下すと以下の点が異なってきます。
シリアルポートでは各バイトデータがLSBから流れてきても、コンピュータのプログラム上では、0x31、0x32は先頭がMSBとなる形式で扱われるため、上記は値を読む方向、ビットシフトの方向が全て逆となります。
シフト方向：右とは、最下位ビットから転送されるデータに対するCRC計算をプログラム上で実施する際のCRCの計算結果のビットシフトの方向のことを指しているのでした。
これでシフト方向：右についてもすっきりしました。
出力：反転とは
さて最後に、出力：反転の意味です。これは調べたらすぐにわかりました。
出力：反転を実施する場合のpythonのコードを以下に示します。
（このコードでは初期値を0xFFFFとしています。）
def calc_crc16(data): crc = 0xFFFF # 初期値（使用するのは下位16bitのみ） poly = 0x8408 # 生成多項式（X^16 + X^12 + X^5 + 1) length = len(data) for i in range(0, length): crc = crc ^ data[i] # CRCの下位8bitと入力データのXOR算 for j in range(0, 8): if(crc & 0x0001 == 0x0001): # crcの最下位が1のとき、crcを「右に1bit」シフトし、生成多項式とXOR算 crc = poly ^ ( crc >> 1) else: # crcの最下位ビットが0のとき、crcを「右に1bit」シフトするのみ crc = (crc >> 1) return crc ^ 0x0000ffff # 除算完了後にCRCの各ビットの0,1を反転 data = [ 0x31, 0x32] crc = calc_crc16(data) print("CRC16:" + hex(crc))
先ほどのシフト方向：右の解説のコードとの違いは、CRC計算の関数の最後の行です。
全ての除算が完了した後に、CRCの各ビットの0、1を反転させています。
ただこれだけです、（何でこんなことをする必要があるのかはよくわかりません・・・）
ちなみにこのコードを実行した結果、計算されるCRCの値は0xB2ACとなります。
これでCRC計算に関する初期値、シフト方向、出力の謎は全て解けてすっきりしました♪
