C Sharpの基礎 - CRC

概要

CRC (Cyclic Redundancy Check) は、データ通信やストレージシステムにおいて使用されているエラー検出技術である。
送信データに対して特定の数学的な演算を行い、チェックサムと呼ばれる値を生成することである。

CRCでは、データを2進多項式として扱う。
例えば、データビット列 1101 は、多項式 $x^{3}+x^{2}+1$ として表現される。
この多項式に対して、あらかじめ決められた生成多項式による除算を行い、その余りをCRC値として使用する。

生成多項式の選択は、CRCの性能を大きく左右する重要な要素である。

標準的なCRCとして、CRC-16やCRC-32がある。
CRC-16では、 $x^{16}+x^{15}+x^{2}+1$ のような生成多項式が使用され、16ビットのチェックサムを生成する。
CRC-32では、32ビットのチェックサムを生成して、より高い信頼性を提供する。

CRCの計算過程では、ガロア体 $GF(2)$ 上での演算が行われる。
この体では加算は排他的論理和 (XOR) に対応し、乗算は通常の多項式乗算を $GF(2)$ 上で行う。
これにより、効率的なハードウェア実装が可能となっている。

CRCのメリットは、実装が簡単であり、ハードウェアでの高速な処理が可能なことである。
また、バースト誤りの検出に効果的である。
しかし、誤り訂正能力はなく、検出のみが可能という制限がある。

イーサネット通信、ZIPファイル、ディスクドライブ等の様々な場面でCRCが使用されている。

CRCの実装方法としては、直接的な多項式除算の他に、ルックアップテーブルを使用する方法も一般的であり、ソフトウェアでの処理速度を大幅に向上させることができる。

CRCの生成多項式

CRCの生成多項式は、ガロア体 $GF(2)$ 上の多項式である。
係数が0か1のみの2進多項式を使用する。

CRCでは、以下に示すような特徴がある。

演算は全て $GF(2)$ 上で行われ、加算は排他的論理和 (XOR) に対応する。
乗算は $GF(2)$ 上の多項式乗算として実行される。
生成多項式g(x)は、誤り検出能力を決定する要素である。

例えば、CRC-16の生成多項式は、 $x^{16}+x^{15}+x^{2}+1\quad ({\mbox{0x18005}})$ である。

この多項式の各項の係数は0か1のみであり、 $GF(2)$ 上の要素となっている。

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}");

C Sharpの基礎 - CRC

目次

概要

CRCの生成多項式

CRC-16

案内メニュー

C Sharpの基礎 - CRC

概要

CRCの生成多項式

CRC-16

案内メニュー

検索