概要
CRC (Cyclic Redundancy Check) は、データ通信やストレージシステムにおいて使用されているエラー検出技術である。
送信データに対して特定の数学的な演算を行い、チェックサムと呼ばれる値を生成することである。
CRCでは、データを2進多項式として扱う。
例えば、データビット列 1101 は、多項式 として表現される。
この多項式に対して、あらかじめ決められた生成多項式による除算を行い、その余りをCRC値として使用する。
生成多項式の選択は、CRCの性能を大きく左右する重要な要素である。
標準的なCRCとして、CRC-16やCRC-32がある。
CRC-16では、 のような生成多項式が使用され、16ビットのチェックサムを生成する。
CRC-32では、32ビットのチェックサムを生成して、より高い信頼性を提供する。
CRCの計算過程では、ガロア体 上での演算が行われる。
この体では加算は排他的論理和 (XOR) に対応し、乗算は通常の多項式乗算を 上で行う。
これにより、効率的なハードウェア実装が可能となっている。
CRCのメリットは、実装が簡単であり、ハードウェアでの高速な処理が可能なことである。
また、バースト誤りの検出に効果的である。
しかし、誤り訂正能力はなく、検出のみが可能という制限がある。
イーサネット通信、ZIPファイル、ディスクドライブ等の様々な場面でCRCが使用されている。
CRCの実装方法としては、直接的な多項式除算の他に、ルックアップテーブルを使用する方法も一般的であり、ソフトウェアでの処理速度を大幅に向上させることができる。
CRCの生成多項式
CRCの生成多項式は、ガロア体 上の多項式である。
係数が0か1のみの2進多項式を使用する。
CRCでは、以下に示すような特徴がある。
- 演算は全て 上で行われ、加算は排他的論理和 (XOR) に対応する。
- 乗算は 上の多項式乗算として実行される。
- 生成多項式g(x)は、誤り検出能力を決定する要素である。
例えば、CRC-16の生成多項式は、 である。
この多項式の各項の係数は0か1のみであり、 上の要素となっている。
CRCの計算手順
- データにCRCのビット数分の0を付加する。
- データを生成多項式で除算する。
- 余りがCRC値となる。
CRC-16
CRC-16では、生成多項式として0xA001 (反転された0x8005, 2[byte]で行うためMSBである1を捨てる) を使用する。
これは、一般的なCRC-16-IBMの規格である。
実際には、ルックアップテーブルを使用することにより、計算を高速化する。
ルックアップテーブルは初期化時に1度だけ生成され、以降の計算で再利用する。
これにより、ビット単位の演算を減らし、パフォーマンスを向上させることができる。
- エラー検出能力
- 単一ビットエラーを100%検出可能
- 2ビットエラーも多くの場合で検出可能
- バースト (連続) エラーも高い確率で検出可能
CRC値の計算を以下に示す。
- 初期値として0xFFFFを使用する。
- データの各バイトに対して、現在のCRC値との演算を行う。
- ルックアップテーブルを使用して、次のCRC値を計算する。
CRC-16は、データ通信やストレージシステムでの一般的なエラー検出に適している。
また、異なる多項式や初期値を使用することにより、他のCRC-16バリアントも実装可能である。
public class CRC16
{
// CRC-16のルックアップテーブル
private readonly ushort[] table;
// CRC-16で使用する生成多項式 (x16 + x15 + x2 + 1 --> 0x18005)
// 0x8005を反転した値である0xA001を使用
private const ushort polynomial = 0xA001;
public CRC16()
{
// 256要素のルックアップテーブルを初期化
table = new ushort[256];
// ルックアップテーブルの生成
for (ushort i = 0; i < 256; i++)
{
ushort value = i;
// 8ビット分の処理を行う
for (int j = 0; j < 8; j++)
{
// 最下位ビットが1の場合
if ((value & 0x0001) == 1)
{
// 1ビット右シフトし、生成多項式とXOR演算を行う
value = (ushort)((value >> 1) ^ polynomial);
}
else
{
// 最下位ビットが0の場合は、単純に1ビット右シフト
value = (ushort)(value >> 1);
}
}
// 計算した値をテーブルに格納
table[i] = value;
}
}
/// <summary>
/// CRC-16値を計算するメソッド
/// </summary>
/// <param name="data">CRCを計算する対象のバイト配列</param>
/// <returns>計算されたCRC-16値</returns>
public ushort Calculate(byte[] data)
{
// CRC初期値として0xFFFFを設定
ushort crc = 0xFFFF;
// 入力データの各バイトに対してCRC計算を実行
foreach (byte b in data)
{
// 現在のCRC値の下位バイトとデータバイトのXOR演算を行い、その結果をテーブルのインデックスとして使用
byte index = (byte)(crc ^ b);
// CRC値を8ビット右シフトし、テーブルの値とXOR演算を行う
crc = (ushort)((crc >> 8) ^ table[index]);
}
// 最終的なCRC値を返す
return crc;
}
}
// 使用例
// CRC-16を計算するためのテストデータ
string text = "Hello, World!";
// 文字列をUTF-8でエンコードしてバイト配列に変換
byte[] data = System.Text.Encoding.UTF8.GetBytes(text);
// CRC-16値を計算
CRC16 crc16 = new CRC16();
ushort crcValue = crc16.Calculate(data);
// 結果を4桁の16進数として表示
Console.WriteLine($"CRC-16: 0x{crcValue:X4}");
CRC-32
標準的なCRC-32の生成多項式として0xEDB88320 (反転された0x04C11DB7, 4[byte]で行う) を使用する。
これは、一般的なCRC-32-IBM (別名 : CRC-32、PKZIP CRC-32) の規格である。
CRC-32の生成多項式は、 である。
- 最終XOR値 : 0xFFFFFFFF (ビット反転による)
- CRC計算の最後のステップとして、計算結果と0xFFFFFFFFとのXOR演算を行うことを意味する。
- この操作は、計算された値の全てのビットを反転 (0→1、1→0) することと同じである。
- 目的
- エラー検出能力を向上させる。
- 全てが0のデータの場合でも、意味のあるCRC値を生成する。
- 入力反転 : あり
- 各バイトのビット順序を反転して処理することを意味する。
- 例 : 入力バイト10110001は、10001101として処理する。
- ルックアップテーブルの生成時にこの処理が組み込まれる。
- 目的
- シリアル通信でのエンディアンの違いに対応する。
- データの送受信時のビット順序の違いを吸収する。
- 出力反転 : あり
- 最終的なCRC値のビット順序を反転することを意味する。
- これは、上記の"最終XOR値"の適用と同時に行われる。
- 目的
- ハードウェア実装との互換性を確保する。
- シフトレジスタベースの実装との整合性
上記の操作は、CRC-32-IBMの規格を定義する重要な要素であり、以下に示すようなメリットがある。
- 異なるハードウェア・ソフトウェア間での互換性の確保
- 強力なエラー検出能力の実現
- データの先頭・末尾での特殊なビットパターンへの対応
- 実装の簡略化 (特に、ハードウェア実装において)
以下の例では、ルックアップテーブルを使用して計算を高速化している。
初期値として0xFFFFFFFFを使用して、最終的にビット反転を行う。
public class CRC32
{
private readonly uint[] table;
private const uint polynomial = 0xEDB88320;
public CRC32()
{
table = new uint[256];
// CRCテーブルの生成
for (uint i = 0; i < 256; i++)
{
uint temp = i;
for (int j = 0; j < 8; j++)
{
if ((temp & 1) == 1)
{
temp = (temp >> 1) ^ polynomial;
}
else
{
temp >>= 1;
}
}
table[i] = temp;
}
}
public uint Calculate(byte[] data)
{
uint crc = 0xFFFFFFFF;
// CRC値の計算
foreach (byte b in data)
{
byte index = (byte)((crc & 0xFF) ^ b);
crc = (crc >> 8) ^ table[index];
}
return ~crc; // 最終的なビット反転
}
}
// 使用例
// CRC-32を計算するためのテストデータ
string text = "Hello, World!";
// 文字列をUTF-8でエンコードしてバイト配列に変換
byte[] data = System.Text.Encoding.UTF8.GetBytes(text);
// CRC-32値を計算
CRC32 crc32 = new CRC32();
uint crcValue = crc32.Calculate(data);
// 結果を8桁の16進数として表示
Console.WriteLine($"CRC-32: {crcValue:X8}");