Tweet

CRC（巡回冗長検査）
Cyclic Redundancy Check

① 物語性を取り入れた説明: CRC（巡回冗長検査）

バスケ部のエリコがコンピュータクラブの先生にCRCについて質問しました。

エリコ: 先生、CRCって何ですか？

先生: そうだね、、CRCはデータ伝送のエラーを検出するための複雑な方法だよ。CRCはまるで、パズルを完成させるときに各ピースが正しい場所にあるかを確認するようなものだ。データの各ビットが「パズルピース」のように、正しい順序にあることを確認する方法なんだ。もしピースが一つでも間違った場所にあれば、パズルは完成しないよね。同様に、データビットの順序が間違っていれば、CRCはエラーを検出するんだ。

エリコ: なるほど、それでデータの正確性を保証するんですね。でも、具体的にはどうやってCRCを行うのですか？

先生: いい質問だね。CRCを行うには、まず送信データに生成多項式の次数分の0を追加するんだ。これは、パズルで言えば、ピースを並べるためのスペースを作るようなものだね。次に、拡張されたデータに対して、生成多項式を使って「割り算」を行うんだ。ここでの割り算は、通常の数学的な割り算とは異なって、ビット単位のXOR演算を行うんだよ。

エリコ: XOR演算って何ですか？

先生: XOR演算は、ビット単位で比較を行う論理演算だよ。同じビットが比較された場合は0を、異なるビットが比較された場合は1を出力するんだ。CRCでは、このXOR演算を使ってデータと生成多項式を「割り算」することで、最終的に「余り」を得るんだ。この余りがCRC値としてデータに添付されて送信されるんだ。

エリコ: それで受信側はどうするんですか？

先生: 受信側は同じ生成多項式を使って、受け取ったデータ全体に対して割り算を行うんだ。もしCRC値が一致すれば、データは正しいと判断される。これによって、データ送信時の誤りを検出することができるんだよ。特に、バースト誤りという、連続するビットでのエラーが発生した場合に、CRCはとても役に立つんだ。バースト誤りは、ノイズや信号の干渉などによって短い時間に多くのエラーが連続して発生する状況のことを指すよ。CRCは、こうしたエラーが含まれているかどうかを検出できるんだ。パリティチェックでは検出できない偶数個の誤りも検出できるんだよ。

CRCの計算プロセスの説明

生成多項式の次数とは何か

生成多項式は、CRCの計算に使用されるビット列です。例えば、「1011」という生成多項式があるとしましょう。この場合、最高次のビット（左端のビット）が1で、全体で4ビットあります。ここでの「次数」は、最高次のビットを含んでからのビット数を数えることを意味します。したがって、「1011」の次数は3です（全体のビット数4から1を引いた数）。

0の追加

生成多項式の次数が3であれば、送信するデータの後ろに3つの0を追加します。これは、実際のデータに生成多項式の次数分の余白を作るためです。これにより、データの長さを生成多項式の長さに合わせて、適切に割り算を行う準備をします。

具体例

送信データが「11010011101100」で、生成多項式が「1011」の場合、次数は3です。したがって、送信データの後ろに3つの0を追加します。これにより、データは「11010011101100000」となります。この拡張されたデータに対して、生成多項式「1011」を使って割り算を行い、その余りがCRC値となります。

このプロセスにより、送信データに対するCRC値が得られ、データの正確性を検証する際に使用されます。

② 実際の事例: CRCの使用例

• データストレージ: ハードディスクやSSDなどのストレージデバイスでは、保存されたデータの整合性を保つためにCRCが用いられます。
• ネットワーク通信: ネットワーク経由でデータを送受信する際、CRCはデータパケットのエラーを検出するために使用されます。
• ファイル転送: 大容量のファイルをインターネット経由で転送する際、CRCはデータの完全性を保証するために用いられることがあります。

③ クイズや小テスト

クイズ1: CRCの主な用途は何ですか？

A. データの暗号化
B. エラーの検出
C. データの圧縮

クイズ2: CRCで使用されるのはどの種類の計算ですか？

A. 加算
B. 乗算
C. 多項式計算

クイズ3: CRCが特に重要なのはどのようなシナリオですか？

A. シンプルなデータ入力
B. 大容量データ転送
C. 基本的な計算処理

回答:

クイズ1の回答: B. エラーの検出
クイズ2の回答: C. 多項式計算
クイズ3の回答: B. 大容量データ転送

応用情報技術者平成21年秋期 午前問4

正解：ウ