CRC実装時のポイント
データの通信や転送をおこなう際に、送信元と受信先でデータが変わってしまうことがあります。ノイズやビットの化けなどに起因するため、偶発的に発生することが多いエラーです。このデータが誤って変更されてしまった場合を検出するために、データをチェックする方法がいくつかあります。
CRCは、データのエラーチェックをおこなう代表的な方法の一つです。この記事ではCRCの特徴や実装時の注意点について、チェックサムとの相違点も含めて解説します。
CRCとは
CRCは、データ通信や転送をおこなう際に誤りが発生したことを検出する技術です。送信する側は、あらかじめ決められたルールで計算されたCRC値を送信データに付加し、受信側では送信側と同じルールで計算し、CRC値を算出します。
送信側と受信側でCRC値が一致した場合は、通信や転送の過程で誤りは検出されなかったとみなす仕組みです。一方で双方のCRC値に矛盾がある場合は、通信や転送に誤りがあったと考えます。
CRCは、チェック対象とするビットの数で種類が分かれており、マイコンのビット数とそろう8ビットや16ビット、32ビットがよく使われます。
誤り検知の方法には、チェックサムも用いられます。チェックサムは、送信データの和を求めたのち、任意の定数で割った余りで整合性チェックをする方法です。CRCはより複雑な計算をおこなって求めるため、厳密なエラーチェックを要求される場面ではCRCが使用されます。
CRCの計算方法
まず送信側と受信側でチェックに使用する数値や式を決めておきます。これが生成多項式です。使用する生成多項式はビットの長さや通信プロトコルによって決まります。
次に送信側は送りたいデータを一定間隔で区切って二進数とみなし、そのデータを生成多項式で割り算します。その後、受信側に対して、「二進数とみなしたデータ」と「生成多項式で割った余りの数字」を送信する流れです。
受信側は受信データから余りを引き、送信側が使った生成多項式と同じもので割ります。余りが先に引かれているため、割った結果は余りがないはずです。余りがないことをもってデータが変化することなく正常に受信できたと考えます。
もしくは、受信したデータから、受信側が独自にCRCを計算し、受信したCRCと一致するかを判定する、という実装をする場合もあります。いずれにしても、正しく受信できているかを受信側が判断することができます。
実装のポイント
CRCの計算も当然プログラムの一部となるため、メモリ容量や処理時間の限られる組み込み系では特に効率よく計算をしていく必要があります。実装時のポイントを示します。
テーブルを使って高速化する
事前に生成多項式の除算結果をテーブルに格納しておくことで、チェック時の毎回の除算を省略できます。毎回計算しない分、処理の高速化が可能です。テーブルの格納先はRAMでもROMでも構いません。処理の速度と、テーブルの大きさによるROM/RAMの消費を考え、効率的な方法を選びましょう。
データを逐次投入する
CRCを計算するためには送りたいメッセージと生成多項式の余りを格納する変数が必要になります。実際に使用する場合の伝送データは非常に大きくなることもあり、一度で計算しようとするとメモリの容量が足りなくなるケースも考えられるでしょう。そこでメッセージを分割して順番に処理していきます。前項で記したテーブルを使った高速化を利用する場合は、あらかじめ1バイトごとにテーブルが作成されるため、1バイト単位でデータを読み込みます。この方式であれば読み込むビット数分だけの変数があれば足りるため、メモリ容量の節約が可能です。
ビットシフトの方向を決める
計算する際に、ビットの先頭からどちらにずれていくかを決めます。右でも左でも計算可能ですが、通信方式やハードウェアの事情で決定されます。
たとえばシリアルポートの転送では、下位ビットから伝送する仕様が一般的です。効率の良い処理を考えると、シフトの方向を逆にして、右シフトで進んでいくほうが簡易で効率のいい処理となります。
CRCの落とし穴
CRCを使えば、すべてのエラーを検出できるわけではないことに注意が必要です。ここからはCRCを用いる落とし穴を取り上げ、チェックしておきたいポイントを解説します。
改ざんや誤り訂正はできない
CRCが検出する誤りはノイズや伝送エラーにともなう偶発的な誤りです。同じCRC値が計算できるように改ざんされたデータなどは検知できません。決められた生成多項式で計算していくCRCの性質上、悪意のある改ざんを検知することはできません。
CRCは、誤りを訂正できないことにも注意が必要です。CRCの検知結果をもとに、データを再送するなど、誤りを訂正するための仕組みはCRCとは別途で構築が必要です。
実装の一致を確認する必要がある
送信側と受信側で同じ多項式を使うのはもちろん、実装パラメータまで合わせないと適切な誤り検出ができません。初期値、入力ビットと出力ビットの反射、最終のXOR、CRCを付加するバイト順の4つがパラメータとなります。このパラメータは設計段階で仕様として固定すると予期せぬ実装ミスを防げます。テストベクトルを用意していつでも実装が正しいことを確認できるようにもしておきましょう。
