Jeremy Purcell作成、最終2012年6月22日改定
特徴
- CRC（ゼロ追加法を含む）の基本的な説明
- CRCの力ずくの計算に関するショートディスカッション
- CRCサムの計算例
- CRCの簡単な実装のためのCコード
はじめに
巡回冗長検査（CRC）は、送信されるデータが伝送中に破損していないことを確認するために使用される検証方法です。WiFiやEthernetなど、デジタルデータを伝送する通信媒体では、CRCの使用が一般的です。組み込みシステムでは、より大きなデータパケットを高速かつ複雑に作成して送信できる技術が求められているため、通信エラーをチェックする必要があります。本アプリケーションノートでは、CRCの計算と検証の方法について説明します。
背景
CRCアルゴリズムは、CRCを介して送信される特定のデータセットごとにチェックサムを計算します。このアルゴリズムは、多項式キーと伝送されたデータを利用します。
送信システムは、チェックコードまたは検証コードを計算し、それを送信メッセージに追加します。受信側では、データは同じプロセスにかけられます。受信側で生成されたCRCが送信されたCRCと一致しない場合、データが破損している可能性があります。受信機は、データの再送信を要求するか、単にデータを無視することができます。生成されたCRCが受信したバージョンと一致すれば、ユーザーは伝送が破損していないことをかなり確信することができます。
CRCの実装には、2種類の異なる方法があります。力ずくの方法は、より多くの計算リソースを必要とし、より多くの時間がかかる可能性があります。ルックアップテーブル方式は、より多くのメモリリソースを必要としますが、定義されたデータセットや繰り返しのあるデータセットに有効です。
応用
このアプリケーションでは、CRCを計算する力ずくな方法について説明します。CRC計算は、データをシフトするか、または多項式キーをシフトしてから計算を実行することにより、ソフトウェアで実行できます。CRCチェックサムを計算するにはいくつかの方法があります。
CRC多項式
多項式キーはCRCの重要なパーツです。キーは単にランダムな多項式ではありません。これらは一連の数式を使用して生成され、CRCプロセスで特定されるエラーの数を増やすことを目的としています。多項式は通常、ネットワークプロトコルまたは外部デバイスによって定義されます。十分に確立されたキーのセットが利用可能であるため、キーを定義するプロセスについてはここでは説明しません。
多項式は2進数表示に変換されます。これは、多項式を拡張してから係数を取得することによって行われます。多項式から2進数への変換の例を以下に示します。
多項式：
拡張多項式：
多項式係数（キー）：100110001
上に示される多項式の最大の累乗は8であり、これは一般にCRC-8と呼ばれる8ビットCRCになります。4、8、16、32ビットは、CRCで使用される非常に一般的な多項式サイズです。
CRCチェックサムの計算
送信側デバイスは、データに正しい数のゼロを追加することによってCRCを計算します。ここで、データはバイナリ演算で処理され、通信チャンネルに送出されます。この方法は、図1に示す「ゼロ追加」の実装です。付録の例1は、この手法を示しています。
まず、データのパケット全体にゼロが追加されます（上記例では8個）。多項式をデータの左端の1に揃えます。データは多項式とXOR（エクスクルーシブオア）で演算されます。その結果が新しいデータです。再び多項式をデータの左端の1に合わせます。このプロセスは、データが多項式より小さくなるまで続きます。このCRCは、送信前にデータストリームに付加されます。
図1.ゼロ追加アルゴリズム
CRCの検証
システムの受信側では、CRCを検証する方法として、ここで説明する「追加ゼロ」の実装と「結果ゼロ」の実装の2つの方法があります。
「追加ゼロ」の実装では、CRCが除去され、データにn個のゼロが追加されます。n は多項式の最大の累乗です。CRC-8では、8つのゼロがデータの最後に追加されます。次に、図1に示すようにCRCが計算され、受信したCRC値と比較されます。
「結果ゼロ」の実装では、ゼロが追加されず、データに受信したCRCが含まれることを除いて、図1に示すプロセスと同様のプロセスが実行されます。プロセスが完了すると、データがCRCと一致する場合、結果はゼロになります。付録の例2は、この手法を示しています。
ルックアップテーブルは計算リソースが少なくて済むため、多くのアプリケーションで使われています。これらのルックアップテーブルには、特定のデータセットに対応するCRC値が格納されています。この方法は、定義されたデータ送信や繰り返しのデータ送信を行うアプリケーションに効果的です。
考察
エンディアンとは、データのバイト順序を示すのに使われる用語です。ビッグエンディアンとは、データが最上位ビット（MSB）を最初に送信することを意味します。逆に、リトルエンディアンは最下位ビット（LSB）を先に送信します。エンディアンが重要なのは、バイトがMSBファーストからLSBファーストに反転したときにCRCが変化するためです。
結論
CRCは、ノイズの多い媒体を介して送信されるデータのエラーをチェックするためのシンプルで効果的な方法です。このアプリケーションノートでは、CRCの仕組みについて説明し、CRCの計算と検証の方法を紹介しました。CRCは、ほとんどの組み込みシステムに簡単に実装することができます。
付録：例
例1：ゼロ追加法
MSBファーストの受信データは、01101010 10101111（2バイト）です。この例では、多項式キー：x8 + x2 + x1 + 1 または 100000111 を使用します。8ビットのCRC-8の場合、キーは実際には9ビットです。
011010101010111100000000 Data appended with 8 zeros
100000111 Right shift polynomial key
1.10101E+22
100000111 XOR data with key and right shift
1.01011E+21
100000111 XOR and right shift
1.0111E+19
100000111 Right shift
1.0111E+19
100000111 XOR and right shift
1.11011E+17
100000111 Right shift
1.11011E+17
100000111 XOR and right shift
1.10111E+16
100000111 XOR and right shift
1.01111E+14
100000111 XOR and right shift
1.11101E+13
100000111 Right shift
1.11101E+13
100000111 XOR and right shift
1.1101E+12
100000111 XOR and right shift
1.101E+11
100000111 XOR and right shift
10100101000
100000111 XOR and right shift
100110100
100000111 Right shift
100110100
100000111 XOR
000110011 Result < Polynomial Key
その結果、データ0x6AAFのチェックは0x33です。この例では、送信機から出力されるデータストリーム（HEX）は34（xx）6A AF 33となります。最初の1バイトは送信のためのプロトコル、次の2バイトはデータ、最後の1バイトはCRCです。
例2：ゼロ結果法
TMSBファーストの受信データは、01101010 10101111（2バイト）です。この例では、多項式キー：x8 + x2 + x1 + 1 または 100000111 を使用します。8ビットのCRC-8の場合、キーは実際には9ビットです。
011010101010111100110011 Data and CRC received
100000111 Right shift polynomial key
1.10101E+22
100000111 XOR data with key and right shift
1.01011E+21
100000111 XOR and right shift
1.0111E+19
100000111 Right shift
1.0111E+19
100000111 XOR and right shift
1.11011E+17
100000111 Right shift
1.11011E+17
100000111 XOR and right shift
1.10111E+16
100000111 XOR and right shift
1.01111E+15
100000111 XOR and right shift
1.11101E+13
100000111 Right shift
1.11101E+13
100000111 XOR and right shift
1.1101E+12
100000111 XOR and right shift
1.101E+11
100000111 XOR and right shift
10100011011
100000111 XOR and right shift
100000111
100000111 Right shift
100000111
100000111 XOR
000000000 Result < polynomial Key
0x6AAF のチェックは、「ゼロ結果法」で 0x00 となり、正常なデータを受信したことが確認されます。
質問/コメント
質問やコメントがございましたら、Digi-KeyのTechForumへどうぞお寄せ下さい。