C Sharpの基礎 - CRC - 版の履歴

Wiki: /* CRC-16 */

2025-02-16T16:17:57Z

CRC-16

@@ 149行目: / 149行目: @@
   // 結果を4桁の16進数として表示
   Console.WriteLine($"CRC-16: 0x{crcValue:X4}");
   </syntaxhighlight>
 <br><br>

Wiki: /* CRCの生成多項式 */

2025-02-16T16:00:29Z

CRCの生成多項式

← 古い版		2025年2月17日 (月) 01:00時点における版
38行目:		38行目:
	<br>		<br>
	この多項式の各項の係数は0か1のみであり、<math>GF(2)</math> 上の要素となっている。<br>		この多項式の各項の係数は0か1のみであり、<math>GF(2)</math> 上の要素となっている。<br>
			<br><br>

			== CRCの計算手順 ==
			# データにCRCのビット数分の0を付加する。
			# データを生成多項式で除算する。
			# 余りがCRC値となる。
	<br><br>		<br><br>

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

CRCでは、データを2進多項式として扱う。
例えば、データビット列 1101 は、多項式 $x^{3} + x^{2} + 1$ として表…」

2025-02-16T07:25:26Z

ページの作成:「== 概要 == CRC (Cyclic Redundancy Check) は、データ通信やストレージシステムにおいて使用されているエラー検出技術である。 送信データに対して特定の数学的な演算を行い、チェックサムと呼ばれる値を生成することである。 CRCでは、データを2進多項式として扱う。 例えば、データビット列 1101 は、多項式 <math>x^{3} + x^{2} + 1</math> として表…」

新規ページ

== 概要 ==
CRC (Cyclic Redundancy Check) は、データ通信やストレージシステムにおいて使用されているエラー検出技術である。 
送信データに対して特定の数学的な演算を行い、チェックサムと呼ばれる値を生成することである。 
 
CRCでは、データを2進多項式として扱う。 
例えば、データビット列 1101 は、多項式 <math>x^{3} + x^{2} + 1</math> として表現される。 
この多項式に対して、あらかじめ決められた生成多項式による除算を行い、その余りをCRC値として使用する。 
 
生成多項式の選択は、CRCの性能を大きく左右する重要な要素である。 
 
標準的なCRCとして、CRC-16やCRC-32がある。 
CRC-16では、<math>x^{16} + x^{15} + x^{2} + 1</math>のような生成多項式が使用され、16ビットのチェックサムを生成する。 
CRC-32では、32ビットのチェックサムを生成して、より高い信頼性を提供する。 
 
CRCの計算過程では、ガロア体 <math>GF(2)</math> 上での演算が行われる。 
この体では加算は排他的論理和 (XOR) に対応し、乗算は通常の多項式乗算を <math>GF(2)</math> 上で行う。 
これにより、効率的なハードウェア実装が可能となっている。 
 
CRCのメリットは、実装が簡単であり、ハードウェアでの高速な処理が可能なことである。 
また、バースト誤りの検出に効果的である。 
しかし、誤り訂正能力はなく、検出のみが可能という制限がある。 
 
イーサネット通信、ZIPファイル、ディスクドライブ等の様々な場面でCRCが使用されている。 
 
CRCの実装方法としては、直接的な多項式除算の他に、ルックアップテーブルを使用する方法も一般的であり、ソフトウェアでの処理速度を大幅に向上させることができる。 
 

== CRCの生成多項式 ==
CRCの生成多項式は、ガロア体 <math>GF(2)</math> 上の多項式である。 
係数が0か1のみの2進多項式を使用する。 
 
CRCでは、以下に示すような特徴がある。 
* 演算は全て <math>GF(2)</math> 上で行われ、加算は排他的論理和 (XOR) に対応する。
* 乗算は <math>GF(2)</math> 上の多項式乗算として実行される。
* 生成多項式g(x)は、誤り検出能力を決定する要素である。
 
例えば、CRC-16の生成多項式は、<math>x^{16} + x^{15} + x^{2} + 1 \quad (\mbox{0x18005})</math> である。 
 
この多項式の各項の係数は0か1のみであり、<math>GF(2)</math> 上の要素となっている。 
 

== CRC-16 ==
CRC-16では、生成多項式として0xA001 (反転された0x8005, 2[byte]で行うためMSBである1を捨てる) を使用する。 
これは、一般的なCRC-16-IBMの規格である。 
 
実際には、ルックアップテーブルを使用することにより、計算を高速化する。 
ルックアップテーブルは初期化時に1度だけ生成され、以降の計算で再利用する。 
これにより、ビット単位の演算を減らし、パフォーマンスを向上させることができる。 
 
* エラー検出能力
*: 単一ビットエラーを100%検出可能
*: 2ビットエラーも多くの場合で検出可能
*: バースト (連続) エラーも高い確率で検出可能
 
CRC値の計算を以下に示す。 
# 初期値として0xFFFFを使用する。
# データの各バイトに対して、現在のCRC値との演算を行う。
# ルックアップテーブルを使用して、次のCRC値を計算する。
 
CRC-16は、データ通信やストレージシステムでの一般的なエラー検出に適している。 
また、異なる多項式や初期値を使用することにより、他のCRC-16バリアントも実装可能である。 
 
<syntaxhighlight lang="c#">
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;
}
}
</syntaxhighlight>
 
<syntaxhighlight lang="c#">
// 使用例

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

{{#seo:
|title={{PAGENAME}} : Exploring Electronics and SUSE Linux | MochiuWiki
|keywords=MochiuWiki,Mochiu,Wiki,Mochiu Wiki,Electric Circuit,Electric,pcb,Mathematics,AVR,TI,STMicro,AVR,ATmega,MSP430,STM,Arduino,Xilinx,FPGA,Verilog,HDL,PinePhone,Pine Phone,Raspberry,Raspberry Pi,C,C++,C#,Qt,Qml,MFC,Shell,Bash,Zsh,Fish,SUSE,SLE,Suse Enterprise,Suse Linux,openSUSE,open SUSE,Leap,Linux,uCLnux,Podman,電気回路,電子回路,基板,プリント基板
|description={{PAGENAME}} - 電子回路とSUSE Linuxに関する情報 | This page is {{PAGENAME}} in our wiki about electronic circuits and SUSE Linux
|image=/resources/assets/MochiuLogo_Single_Blue.png
}}

__FORCETOC__
[[カテゴリ:C_Sharp]]