CRCの覚書

☆☆☆☆☆☆☆☆☆CRCの覚書☆☆☆☆☆☆☆☆☆

【注意】
本内容は、最近CRCについてカジった人間の浅い知識が記載されています。文中説明に間違いがあるかもしれません。ご容赦ください。

◎まえがき

仕事で低消費電力のZigBee無線モジュールを使う事になった。
低消費電力という事の強調で、よく電池１ケで何年も使えるみたいなセールストークがあるけど、あれば間欠動作する無線送信側の話で、何秒に１回数バイト送信の定義によっていくらでも電池寿命は長くなる。受信側はまた別の話。
．．．とそんな話ではなく、
ZigBeeのファームウェアを外注に依頼し実際にZigBee無線モジュールを使ってみたのだけど、データ落ちがあったりした。ZigBeeプロトコルスタックの中で、データの誤り検出機能がないとは思えないのだが、実際には、それほど高い通信の信頼性での通信を確保出来なかった。
外注もアプリケーションレベルでの誤り検出を求めてくる．．．。
ユーザー側としては、通信の信頼性の高い無線モジュールを使用したいだけなのだが、アプリレベルでもデータの誤り検出しなくてはならないなんて今時アリなのか？と思った。
そんなこんなで使えない無線モジュールが切っ掛けで皮肉にも誤り検出について気になり出していた。
簡単なのは、パリティチェック、チェックサムなど。
誤り検出に絶大な効果を期待出来るとはイマイチ思えない。ないよりまし程度。
しばらくして某Ｎ社の2.4ＧＨｚ独自プロトコルの無線モジュールを触る機会があった。
この無線モジュールは、ユーザーの送信フォーマットには特に誤り検出部がないのだが、ファームウェアでＣＲＣにて誤り検出している事が取説に記載されていた。
（そうそうユーザーに意識させないコレだよね。）
大メーカーも使っているＣＲＣってどういう方式なのだろう？

◎とりあえずネットで調べる

CRCについてググる。
やや！なんか面倒臭い感じだ。
CRCと言っても色々あるらしい。生成多項式ってなんじゃ？
ｘ16+ｘ12+ｘ5+１
？？？
大体数学なんて社会人になったら殆ど反復しないので忘れた。
やさしい解説やさしい解説と．．．。うーん。文が長いな。なんか論理回路で組むと簡単らしい。
生成多項式のｘは２で良いらしい。
２＾16+２＾12+２＾5+１＝１１０２１ｈ
これなら判る。

自分はハードよりなのでハードよりのイメージでＣＲＣ１６　ＩＴＵ－Ｔについてメモっておく。

一言で言うとＣＲＣは、データ列を１ビット左シフト(右シフトもある)しながら、キャリーが発生したら生成多項式の値をＸｏｒするだけ。
生成多項式は、ＩＴＵ－Ｔでは、上記の１１０２１ｈの１６ビット分の１０２１ｈを使用する。
データは、仮に
FF EE DD CC BB AA 99 88 77 66 55 44 33 22 11
の１５バイトとする。

16ビットの計算部を先頭にし、その後にデータが続くような構造。
リングのイメージで良いと思う。
計算部の初期値は、”００００ｈ”でクリアしておく。

１ビットづつ左シフトして計算部にキャリー（桁上げ）が発生したら、
計算部に１０２１ｈをＸｏｒする。
計算部は初期値”００００”だったので、
当然１６ビット左シフトまでキャリーは発生しない。
初期値の”００００ｈ”が、そのままシフトしているのがミソ。

１７ビット目の左シフトで初めて計算部にキャリーが発生する。
キャリーが発生したら計算部と１０２１ｈをXorし結果を計算部に代入する。
キャリーが発生しない場合は何もしない。
この処理を単純に続ける。

１５バイト＝１２０ビットまで終了した状態。
ここで終わりではなく計算部の初期値だった”００００ｈ”までシフトを続ける。

”００００ｈ”まで処理を終了した結果
”２Ｂ８７ｈ”
がＣＲＣとなる。
データ
FF EE DD CC BB AA 99 88 77 66 55 44 33 22 11
を送る場合、
FF EE DD CC BB AA 99 88 77 66 55 44 33 22 112B 87
とする。

受信側でのデータ誤り検出方法は、初期値なしとして、計算部に上記データの”FF EE”を入れて同じ方式で末尾”87”まで順次処理すると、
結果は、”００００ｈ”になり正しいデータが受信出来た事が判る。

◎実際の通信

これでCRCの計算方法は判った。しかしイキナリデータを送っても受信側は、どこからがデータの始まりで何バイト送られてくるのか判らない。
そこで通常はヘッダーという固定フォーマットをデータの前に付ける。
最低下記内容が必要。
・ヘッダー先頭を意味する固定のバイト。→これでスタートが判る。
・全体の送信バイト数（CRCを含め）→全体のバイト数＝ｎが判れば、ｎバイト分ＣＲＣ１６　ＩＴＵ－Ｔの処理をした結果が、”００００ｈ”となればＯＫ。
・データ番号↓
受信側で、ＣＲＣエラー（結果が００００ｈにならない。）が発生した場合、受信側は送信側にエラーを返さないと送信側は判らない。
従って受信側は何かしらのレスポンスを返す必要がある。
通信は、データが正しくとも誤りでも送受信間でハンドシェ－クする必要がある。
受信側からのレスポンスが正しく送信側に受信出来ない事もある。
その場合、送信側がエラーと認識し再度データの再送を行うと、受信側は正常終了したのに、また同じデータを受け取る事になる。
従って受信側が、データが前回と同じかどうかを判断出来る為にヘッダーにデータ番号を付ける。

他にヘッダーの有用性として、CRC計算はデータの初めに”００ｈ”が連続すると”０”の数に関わらず結果が一致してしまう欠点があるのだけどヘッダーを用いる事でその欠点を排除する事が出来る。

右シフトでの計算方法

HOME

	16ビットの計算部を先頭にし、その後にデータが続くような構造。リングのイメージで良いと思う。計算部の初期値は、”００００ｈ”でクリアしておく。
	１ビットづつ左シフトして計算部にキャリー（桁上げ）が発生したら、計算部に１０２１ｈをＸｏｒする。計算部は初期値”００００”だったので、当然１６ビット左シフトまでキャリーは発生しない。初期値の”００００ｈ”が、そのままシフトしているのがミソ。
	１７ビット目の左シフトで初めて計算部にキャリーが発生する。キャリーが発生したら計算部と１０２１ｈをXorし結果を計算部に代入する。キャリーが発生しない場合は何もしない。この処理を単純に続ける。
	１５バイト＝１２０ビットまで終了した状態。ここで終わりではなく計算部の初期値だった”００００ｈ”までシフトを続ける。
	”００００ｈ”まで処理を終了した結果 ”２Ｂ８７ｈ” がＣＲＣとなる。データ FF EE DD CC BB AA 99 88 77 66 55 44 33 22 11 を送る場合、 FF EE DD CC BB AA 99 88 77 66 55 44 33 22 112B 87 とする。受信側でのデータ誤り検出方法は、初期値なしとして、計算部に上記データの”FF EE”を入れて同じ方式で末尾”87”まで順次処理すると、結果は、”００００ｈ”になり正しいデータが受信出来た事が判る。