巡回冗長検査の計算

巡回冗長検査の計算は、 2を法とする多項式除算の数学から導き出されます。実際には、減算が排他的論理和演算に置き換えられていることを除けば、固定数のゼロが付加されたバイナリメッセージ文字列を「生成多項式」文字列で長除算するのと似ています。この種の除算は、ハードウェアでは修正シフトレジスタ[ ^{1 ]}によって効率的に実現され、ソフトウェアでは一連の同等のアルゴリズムによって実現されます。これらのアルゴリズム^は、数学に近い単純なコードから始まり、バイト単位の並列処理と空間と時間のトレードオフによって高速化（そしておそらくより難読化^{[ 2 ]} ）されます。

8ビットCRCを生成する例。生成器はガロア型シフトレジスタで、生成多項式におけるxのべき乗（白数）に応じてXORゲートが配置されています。メッセージストリームは任意の長さです。レジスタ内をシフトされ、8個のゼロが続く結果がチェックサムです。

受信データをチェックサムでチェックします。受信メッセージはジェネレータで使用されるのと同じレジスタを通過しますが、ゼロの代わりに受信チェックサムが付加されます。正しいデータの場合はすべてゼロの結果が返されます。メッセージまたはチェックサムのいずれかに破損したビットがある場合は、異なる結果が返され、エラーが発生したことが警告されます。

様々なCRC規格では、多項式除算アルゴリズムを拡張し、初期シフトレジスタ値、最終排他的論理和ステップ、そして最も重要なビット順序（エンディアン）を指定しています。その結果、実際に見られるコードは「純粋な」除算から大きく逸脱し、^{[ 2 ]}レジスタが左または右にシフトすることがあります。

例

ハードウェアで多項式除算を実装する例として、ASCII文字「W」（2進数では01010111 ₂、10進数では87 ₁₀、16進数では57 _{16 ）で構成される8ビットメッセージの8ビットCRCを計算したいとします。説明のために、CRC-8-ATM（} HEC）多項式を使用します。送信される最初のビット（の最高乗の係数）を左側に書き込むと、これは9ビットの文字列「100000111」に相当します。 ${\displaystyle x^{8}+x^{2}+x+1}$ ${\displaystyle x}$

バイト値 57 ₁₆は、使用されるビット順序規則に応じて、2つの異なる順序で転送できます。それぞれが異なるメッセージ多項式 を生成します。Mビットファーストの場合は = 01010111 、Lビットファーストの場合は= 11101010 です。これらを で乗算すると、2つの16ビットメッセージ多項式 が生成されます。 ${\displaystyle M(x)}$ ${\displaystyle x^{6}+x^{4}+x^{2}+x+1}$ ${\displaystyle x^{7}+x^{6}+x^{5}+x^{3}+x}$ ${\displaystyle x^{8}}$ ${\displaystyle x^{8}M(x)}$

剰余の計算は、生成多項式の倍数を減算することで行われます。これは10進数の長除算と似ていますが、各ステップで取り得る倍数は0と1のみであり、減算は上位桁を減らすのではなく「無限大から」借りているため、さらに単純です。商は気にしないので、記録する必要はありません。 ${\displaystyle G(x)}$

最上位ビットを先頭に

最下位ビットから

0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0

1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 − 1 0 0 0 0 0 1 1 1 ＝ 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 − 0 0 0 0 0 0 0 0 0 ＝ 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0

各減算後、ビットが3つのグループに分割されることに注目してください。最初のグループはすべてゼロ、最後のグループは元の値から変化しないグループ、そして中央の青い網掛けのグループは「興味深い」グループです。「興味深い」グループは8ビット長で、多項式の次数と一致しています。各ステップで、多項式の適切な倍数が減算され、ゼロのグループは1ビット長くなり、変化しないグループは1ビット短くなり、最終的に残りのビットだけが残ります。

msbit-firstの例では、剰余多項式は です。xの最大の累乗がmsbitであるという規則に従って16進数に変換すると、A2 ₁₆になります。lsbit-firstの例では、剰余は です。xの最大の累乗がlsbitであるという規則に従って16進数に変換すると、19 ₁₆になります。 ${\displaystyle x^{7}+x^{5}+x}$ ${\displaystyle x^{7}+x^{4}+x^{3}}$

実装

上記の例のように、各ステップでメッセージ全体を書き出すのは非常に面倒です。効率的な実装では、必要なビットのみを保持するビットシフトレジスタを使用します。多項式に を掛けることは、レジスタを1桁シフトすることと等価です。係数の値は変化せず、多項式の次の項に移動するだけだからです。 ${\displaystyle n}$ ${\displaystyle x}$

nビット CRC を計算するための擬似コードの最初のドラフトを以下に示します。多項式には、人造の複合データ型を使用しています。ここで は整数変数ではなく、加算、乗算、累乗が可能なPolynomialオブジェクトを生成するコンストラクタです。2つの多項式を加算するということは、2 を法として加算することを意味します。つまり、両方の多項式の各項の係数を 排他的論理和で演算することを意味します。xxor

関数crc(ビット配列bitString[1..len], int len) { residualPolynomial := polynomialForm (bitString[1..n]) // メッセージの最初の n ビット// 一般的なバリエーションは、remainderPolynomial を補完します。§ 1からlenまでのiに対して、以下の−1 にプリセットします。 残余多項式:=残余多項式 * x + bitString[i+n] * x 0 // 残余多項式の係数x nが1の場合、k>lenでbitString[k]=0と定義する { 剰余多項式 := 剰余多項式xorジェネレータ多項式 } } // ここでよく使われる変形は、remainderPolynomial を補完するものです。§後置反転については以下を 参照してください。remainderPolynomial を返します。 } 

コードフラグメント1: 単純な多項式除算

このサンプル コードでは、バイトを使用しないことでビット順序規則を指定する必要がないことに注意してください。入力は既にビット配列bitStringの形式になっており、 は多項式演算で操作されます。 による乗算は左シフトまたは右シフトになる可能性があり、 の加算はレジスタの右端または左端にある係数に対して行われます。 remainderPolynomial ${\displaystyle x}$bitString[i+n] ${\displaystyle x^{0}}$

このコードには2つの欠点があります。まず、係数をテストするために、n +1ビットのレジスタを保持する必要があります。さらに重要なのは、 nビットのゼロを埋め込む必要があることです。 remainderPolynomial ${\displaystyle x^{n}}$bitString

最初の問題は、を で乗算する前にの係数をテストすることで解決できます。 ${\displaystyle x^{n-1}}$remainderPolynomial ${\displaystyle x}$

2 番目の問題は、最後のn回の反復を異なる方法で実行することで解決できますが、ハードウェアとソフトウェアの両方の実装で普遍的に使用される、より微妙な最適化があります。

メッセージから生成多項式を減算するXOR演算は可換かつ結合的であるため、様々な入力がどのような順序で に結合されるかは問題になりませんremainderPolynomial。具体的には、 の特定のビットは、と が一致するかどうかを判定する最後の瞬間までbitStringに追加する必要はありません。 remainderPolynomialxorgeneratorPolynomial

これにより、メッセージの remainderPolynomial最初のnビットをプリロードする必要がなくなります。

関数crc(ビット配列bitString[1..len], int len) { 剰余多項式 := 0 // ここで、remainderPolynomial の一般的な変形が行われます。§ 1からlenまでのiに対して、以下の−1 にプリセットしてください。{ 剰余多項式 := 剰余多項式xor (ビット文字列[i] * x n−1 ) if (剰余多項式のx n−1の係数) = 1 { 剰余多項式 := (剰余多項式 * x ) xorジェネレータ多項式 }それ以外{ 剰余多項式 := (剰余多項式 * x ) } } // ここでよく使われる変形は、remainderPolynomial を補完するものです。§後置反転については以下を 参照してください。remainderPolynomial を返します。 } 

コードフラグメント2: 遅延メッセージXORによる多項式除算

これは標準的なビット単位のハードウェアCRC実装であり、研究する価値があります。なぜこれが最初のバージョンと全く同じ結果を計算するのかを理解すれば、残りの最適化は非常に簡単です。がnビットremainderPolynomialしかない場合、それと の係数は単に破棄されます。これが、CRC多項式が先頭の係数を省略した2進数で記述されることが多い理由です。 ${\displaystyle x^{n}}$generatorPolynomial

ソフトウェアでは、各ビットの を最後の瞬間まで遅らせることもできますが、それよりも早く行うことも可能です。通常は、ビット単位の実装であっても、 を1バイトずつ実行する方が便利です。ここでは、入力を8ビットバイトで受け取ります。 xorxor

関数crc(バイト配列string[1..len], int len) { 剰余多項式 := 0 // ここで、remainderPolynomial の一般的な変形が行われます。§ 1からlenまでのiに対して、以下の−1 にプリセットしてください。{ 剰余多項式:=剰余多項式xor polynomialForm (文字列[i]) * x n−8 ( jは1から8まで) { // 剰余多項式の係数x n−1が1の場合、1バイトあたり8ビットと仮定{ 剰余多項式 := (剰余多項式 * x ) xorジェネレータ多項式 }それ以外{ 剰余多項式 := (剰余多項式 * x ) } } } // ここでよく使われる変形は、remainderPolynomial を補完するものです。§後置反転については以下を 参照してください。remainderPolynomial を返します。 } 

コードフラグメント3: バイト単位のメッセージXORによる多項式除算

これは通常、最もコンパクトなソフトウェア実装であり、速度よりもスペースが優先される場合に マイクロコントローラで使用されます。

ビット順序（エンディアン）

ビット シリアルハードウェアで実装された場合、生成多項式はビット割り当てを一意に記述します。送信される最初のビットは常に の最高べき乗の係数であり、送信される最後のビットは の係数で始まり の係数(つまり 1 の係数) で終わるCRC 剰余 です。 ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle R(x)}$ ${\displaystyle x^{n-1}}$ ${\displaystyle x^{0}}$

ただし、パラレル伝送、 8B/10B エンコードやRS-232スタイルの非同期シリアル通信などのバイト フレーミングを使用する場合や、CRC をソフトウェアで実装する場合など、ビットが 1バイトずつ処理される場合は、データのビット順序 (エンディアン) を指定する必要があります。各バイトのどのビットが「最初」とみなされ、 のより高いべき乗の係数になるかを指定します。 ${\displaystyle x}$

データがシリアル通信用である場合、データが最終的に送信されるビット順序を使用するのが最適です。これは、CRC のバースト エラー検出能力がメッセージ多項式の近接性に基づいているためです。隣接する多項式項が連続して送信されない場合、ビットの再配置により、1 つの長さの物理エラー バーストがより長いバーストとして認識される可能性があります。 ${\displaystyle M(x)}$

たとえば、IEEE 802（イーサネット）とRS-232（シリアルポート）の両規格では、最下位ビットを先頭とする（リトルエンディアン）転送が指定されているため、このようなリンクを介して送信されるデータを保護するためのソフトウェアCRC実装では、各バイトの最下位ビットを の最高次数の係数にマッピングする必要があります。一方、フロッピーディスクやほとんどのハードドライブでは、各バイトの最上位ビットを先頭に書き込みます。 ${\displaystyle x}$

lsbit-first CRCはソフトウェア実装がやや簡単なため、やや一般的に使用されていますが、多くのプログラマーはmsbit-firstのビット順序の方が理解しやすいと考えています。例えば、ソフトウェアでCRCを初期に使用したXMODEMの-CRC拡張では、msbit-first CRCが使用されています。

これまでの擬似コードでは、擬似コード内のシフトを乗算として記述し、バイナリ形式から多項式形式への明示的な変換を記述することで、バイト内のビット順序の指定を回避してきました。実際には、CRCは特定のビット順序規則を使用して標準バイナリレジスタに保持されます。msbit-first形式では、最上位バイナリビットが最初に送信され、高次多項式係数が含まれます。一方、lsbit-first形式では、最下位バイナリビットに高次係数が含まれます。上記の擬似コードはどちらの形式でも記述できます。具体的には、16ビットのCRC-16- CCITT多項式を使用します。 ${\displaystyle x}$ ${\displaystyle x^{16}+x^{12}+x^{5}+1}$

// 最上位ビットが先（ビッグエンディアン）// (x 16 )+x 12 +x 5 +1 = (1) 0001 0000 0010 0001 = 0x1021 function crc( byte array string[1..len], int len) { 残余:= 0 // 一般的なバリエーションは、 1からlenまでのiに対してremを補完します{ rem := rem xor (string[i] leftShift (n-8)) // この例では n = 16 for j from 1 to 8 { // 1バイトあたり8ビットと仮定if rem and 0x8000 { // x 15係数をテスト rem := (rem leftShift 1) xor 0x1021 }それ以外{ rem := rem左シフト1 } rem := rem and 0xffff // 余りを16ビットにトリムする } } // 一般的なバリアントは rem を補完します。remを返します。 } 

コードフラグメント4: シフトレジスタベースの除算、MSBファースト

// 最下位ビットが先（リトルエンディアン）// 1+x 5 +x 12 +(x 16 ) = 1000 0100 0000 1000 (1) = 0x8408 function crc( byte array string[1..len], int len) { 残余:= 0 // 一般的なバリエーションは、 1からlenまでのiに対してremを補完します{ rem := rem xor string[i] for j from 1 to 8 { // 1バイトあたり8ビットと仮定if rem and 0x0001 { // x 15係数をテスト rem := (rem rightShift 1) xor 0x8408 }それ以外{ rem := rem右シフト1 } } } // 一般的なバリアントは rem を補完します。remを返します。 } 

コードフラグメント5: シフトレジスタベースの除算、LSBファースト

lsbit-first 形式を使用すると、string[i]の前にシフトする必要がなくなることに注意してくださいxor。どちらの場合でも、CRC のバイトは、選択したビット順序規則に一致する順序で送信するようにしてください。

ルックアップテーブルを使用したマルチビット計算

より高速なソフトウェア実装では、 の最高次係数でインデックス付けされたルックアップ テーブルを使用して、反復ごとに 1 ビットを超える被除数を処理しrem、ビットごとの除算手順 をメモします。

Sarwateアルゴリズム（単一ルックアップテーブル）

最も一般的な手法は、256エントリのルックアップテーブルを使用して、反復ごとに8ビットの入力を処理することです。^{[ 3 ]} これは、外側のループ（）の本体を次iのように置き換えます。

// msbit ファースト rem = (rem leftShift 8) xor big_endian_table[string[i] xor ((remの左端8ビット) rightShift (n-8))] // 下位ビット優先 rem = (rem rightShift 8) xor little_endian_table[string[i] xor (remの右端8ビット)] 

コードフラグメント6: テーブルベースの除算のコア

通常は256エントリのテーブルを使用するのが最も便利ですが、他のサイズも使用できます。小型のマイクロコントローラでは、16エントリのテーブルを使用して一度に4ビットを処理することで、テーブルを小さく保ちながら速度を大幅に向上させることができます。十分なストレージ容量を持つコンピュータでは、65 536エントリ テーブルを使用して、一度に 16 ビットを処理できます。

ルックアップテーブルの生成

ルックアップテーブルを生成するソフトウェアは非常に小さく高速であるため、通常は、事前に計算されたテーブルをストレージから読み込むよりも、プログラム起動時に計算する方が高速です。一般的な手法の一つは、ビット単位のコードを256回使用して、256通りの8ビットバイトのCRCを生成することです。^{[ 4 ]} しかし、この手法は、2の累乗に対応するテーブルエントリのみを直接計算すれば済みます。 table[i xor j] == table[i] xor table[j]

次のサンプル コードでは、crcは次の値を保持しますtable[i]。

ビッグエンディアンテーブル[0] := 0 crc := 0x8000 // 16ビット多項式を想定 私 := 1 実行する{ crcと0x8000の場合{ crc := (crc leftShift 1) xor 0x1021 // CRC多項式 } else { crc := crc左シフト1 } // crcはbig_endian_table[i]の値です。jは0からi −1までの初期化済みのエントリを反復処理します 。 big_endian_table[i + j] := crc xor big_endian_table[j]; } i := i左シフト1 } i < 256 の 場合

コードフラグメント7: バイト単位のCRCテーブル生成、msbit-first

リトルエンディアンテーブル[0] := 0 crc := 1; 私 := 128 crcと1の 場合{ crc := (crc rightShift 1) xor 0x8408 // CRC多項式 } else { crc := crc右シフト1 } // crcはlittle_endian_table[i]の値です。jは0から255までの初期化済みのエントリを 2×iで反復します。 little_endian_table[i + j] := crc xor little_endian_table[j]; } i := i右シフト1 } i > 0 の 場合

コードフラグメント8: バイト単位のCRCテーブル生成、lsbit-first

これらのコード サンプルでは、​​テーブル インデックスはi + jと同等です。どちらの形式がより便利であるかに応じて使い分けてください。 i xor j

CRC-32の例

最も一般的に使用されるCRC多項式の一つはCRC-32と呼ばれ、イーサネット、FDDI、ZIPなどのアーカイブ形式、PNG画像形式などで使用されています。この多項式は、msbit-firstで0x04C11DB7、lsbit-firstで0xEDB88320と表記されます。

これはCRCのCRC-32バリアントの実用的な例です。^{[ 5 ]}

代替の情報源としては、PNGに関するW3Cのウェブページがあります。このウェブページには、CRC-32のC言語による短くてシンプルなテーブル駆動型の実装が付録として含まれています。^{[ 4 ]}このコードは、ここで紹介したlsbit-first byte-at-a-timeアルゴリズムに対応しており、テーブルはbit-at-a-timeコードを使用して生成されていることがわかります。

関数CRC32 入力: data: Bytes  // バイト配列出力: crc32: UInt32  // 32ビット符号なしCRC-32値// CRC-32を開始値に初期化 crc32 ← 0xFFFFFFFFデータの各バイトに対してdo nLookupIndex ← (CRC32 XORバイト) かつ 0xFF crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] // CRCTableは256個の32ビット定数の配列です// すべてのビットを反転してCRC-32値を確定します crc32 ← crc32 排他的論理和 0xFFFFFFFF crc32 を返す

C では、アルゴリズムは次のようになります。

#include <stdint.h> // uint32_t, uint8_t #include <stddef.h> // size_t静的uint32_t CRCTable [ 256 ];// 複数のスレッドによる初期化は冗長ですが、安全です。static void CRC32_init ( void ) { uint32_t crc32 = 1 ; // C はすでに CRCTable[0] = 0 を保証します。for ( unsigned int i = 128 ; i ; i >>= 1 ) { crc32 = ( crc32 >> 1 ) ^ ( crc32 & 1 ? 0xedb88320 : 0 ); for ( unsigned int j = 0 ; j < 256 ; j += 2 * i ) CRCTable [ i + j ] = crc32 ^ CRCTable [ j ]; } }uint32_t CRC32 ( const uint8_t data [], size_t data_length ) { uint32_t crc32 = 0xFFFFFFFFu ;if ( CRCTable [ 255 ] == 0 ) CRC32_init (); for ( size_t i = 0 ; i < data_length ; i ++ ) { crc32 ^= data [ i ]; crc32 = ( crc32 >> 8 ) ^ CRCTable [ crc32 & 0xFF ]; } // すべてのビットを反転して CRC-32 値を確定しますcrc32 ^= 0xFFFFFFFFu ; return crc32 ; }

複数のテーブルを使用したバイトスライス

Sarwateアルゴリズムと比較して、通常2倍または3倍の性能を発揮するn分割スライス（CRC32の場合は通常8分割スライス）アルゴリズムが存在する。このアルゴリズムは、一度に8ビットを読み取るのではなく、8nビットずつ読み取る。これにより、スーパースカラープロセッサ上での性能が最大限に引き出される。^{[ 6 ] [ 7 ] [ 8 ] [ 9 ]}

このアルゴリズムを実際に誰が発明したかは不明である。^{[ 10 ]}

利点を理解するために、まずスライス2の場合から始めましょう。CRCを一度に2バイト（16ビット）ずつ計算したいのですが、標準的なテーブルベースのアプローチでは、65536エントリという非常に大きなテーブルが必要になります。§ルックアップテーブルの生成で述べたように、CRCテーブルは という特性を持っています。この恒等式を用いて、この大きなテーブルを2つの256エントリのテーブルに置き換えることができます。 table[i xor j] = table[i] xor table[j]table[i + 256 × j] = table_low[i] xor table_high[j]

つまり、大きなテーブルは明示的に保存されず、各反復処理で2つの小さなテーブルの値を結合することで、そこに格納されるCRC値が計算されます。つまり、16ビットのインデックスが2つの8ビットのインデックスに「スライス」されるのです。一見すると、これは無意味に思えます。標準的なバイト単位のアルゴリズムでは同じテーブルを2回参照するのに対し、なぜ別々のテーブルを2回参照する必要があるのでしょうか？

違いは命令レベルの並列性にあります。標準アルゴリズムでは、各検索のインデックスは前回の検索で取得された値に依存します。したがって、最初の検索が完了するまで、2番目の検索は開始できません。

スライステーブルを使用すると、両方の検索を同時に開始できます。プロセッサが2つのロードを並列に実行できる場合（2020年代のマイクロプロセッサは100以上のロード処理を処理できます）、内部ループの速度を2倍に高める可能性があります。

この手法は、プロセッサが利用できる限り多くのスライスに拡張できることは明らかです。

スライス幅がCRCのサイズと等しい場合、若干の高速化が見られます。基本的なSarwateアルゴリズムにおいて、前のCRC値がテーブル参照のサイズ分シフトされる部分では、前のCRC値が完全にシフトされ（残るのはすべてゼロ）、XOR演算がクリティカルパスから排除されます。

結果として得られるスライス バイn内部ループは次のようになります。

1. 現在のCRCとメッセージの次のnバイトのXORをとる。
2. 結果の値の各バイトをn個のスライステーブルで検索し、
3. n個の結果を XOR して次の CRC を取得します。

この方法では、次の反復処理を開始する前に第2ステップのすべてのロードを完了する必要があるという特性が依然として存在し、その結果、プロセッサのメモリサブシステム（特にデータキャッシュ）が使用されない一時停止が定期的に発生します。しかし、スライス幅がCRCサイズを超えると、第2ステップの大幅な高速化が見られます。

これは、最初のステップの結果の一部が、以前の反復処理に依存しなくなるためです。32ビットCRCと64ビットのメッセージとの排他的論理和をとると、結果の半分は単にメッセージのコピーになります。誤ったデータ依存性が生じないように注意深くコーディングすれば、スライステーブルのロードの半分は、前のループ反復処理が完了する前に開始できます。その結果、プロセッサのメモリサブシステムを継続的にビジー状態に保つのに十分な処理量となり、最高のパフォーマンスが得られます。前述のように、2000年以降のマイクロプロセッサでは、このレベルに到達するには一般的に8ビットスライスで十分です。

スライスが8ビット幅である必要は特にありません。例えば、スライスバイ9アルゴリズムを用いてCRCを64ビットずつ計算することは全く可能です。この場合、63ビットを処理するために9つの128エントリのルックアップテーブルを使用し、64番目のビットをビット単位アルゴリズム（実質的には1ビット、2エントリのルックアップテーブル）で処理します。これにより、反復処理ごとにデータ依存のロードが1つ増えるという犠牲を払って、テーブルサイズはほぼ半分（8×256 = 2048エントリから9×128 = 1152エントリ）になります。

ルックアップテーブルなしのマルチビット計算

一度に1バイトまたは1ワードずつの並列更新も、テーブルを使わずに明示的に行うことができます。^{[ 11 ]}各ビットについて、8ビットがシフトインされた後に方程式が解かれます。

複数の縮約ステップは通常、行列演算として表現されます。1回のシフトと次数生成多項式を法とする縮約は、対応する行列の乗算と等価です。 ステップは行列 として表されます。 ${\displaystyle n}$ ${\displaystyle G(x)}$ ${\displaystyle n\times n}$ ${\displaystyle A=C(G)}$ ${\displaystyle r}$ ${\displaystyle A^{r}=C(G)^{r}}$

この手法は通常、高速ハードウェア実装で使用されますが、小さいCRC多項式や疎なCRC多項式の場合はソフトウェアでも実用的です。^{[ 12 ]} 大きく密なCRC多項式の場合、コードは非現実的なほど長くなります。

疎多項式の例

次の表は、次の記号を使用して、いくつかの一般的に使用される多項式を法として一度に 8 ビットを処理する方程式を示しています。

c i	更新前のCRCビット7…0（または15…0）
r i	更新後のCRCビット7…0（または15…0）
d i	入力データビット7…0
e i = d i + c i	e p = e 7 + e 6 + … + e 1 + e 0 (パリティビット)
s i = d i + c i+8	s p = s 7 + s 6 + … + s 1 + s 0 (パリティビット)

8ビットシフト後のCRC-8多項式のビット単位の更新式

多項式:	x ( x 7 + x 3 + 1) (左シフトCRC-7-CCITT)	x 8 + x 5 + x 4 + 1 (CRC-8-ダラス/マキシム)
係数:	0x12 = (0x09 << 1) ( msbit -first)	0x8c ( lsbitが先頭)
r 0 ← r 1 ← r 2 ← r 3 ← r 4 ← r 5 ← r 6 ← r 7 ←	0 e 0 + e 4 + e 7 e 1 + e 5 e 2 + e 6 e 3 + e 7 + e 0 + e 4 + e 7 e 4 + e 1 + e 5 e 5 + e 2 + e 6 e 6 + e 3 + e 7	e 0 + e 4 + e 1 + e 0 + e 5 + e 2 + e 1 e 1 + e 5 + e 2 + e 1 + e 6 + e 3 + e 2 + e 0 e 2 + e 6 + e 3 + e 2 + e 0 + e 7 + e 4 + e 3 + e 1 e 3 + e 0 + e 7 + e 4 + e 3 + e 1 e 4 + e 1 + e 0 e 5 + e 2 + e 1 e 6 + e 3 + e 2 + e 0 e 7 + e 4 + e 3 + e 1
Cコードの一部:	uint8_t c , d , e , f , r ; … e = c ^ d ; f = e ^ ( e >> 4 ) ^ ( e >> 7 ); r = ( f << 1 ) ^ ( f << 4 );	uint8_t c , d , e , f , r ; … e = c ^ d ; f = e ^ ( e << 3 ) ^ ( e << 4 ) ^ ( e << 6 ); r = f ^ ( f >> 4 ) ^ ( f >> 5 );

8ビットシフト後のCRC-16多項式のビット単位の更新式

多項式:	× 16 + × 12 + × 5 + 1 (CRC-16-CCITT)
係数:	0x1021 (msbit-first)	0x8408 (lsbit-first)
r 0 ← r 1 ← r 2 ← r 3 ← r 4 ← r 5 ← r 6 ← r 7 ← r 8 ← r 9 ← r 10 ← r 11 ← r 12 ← r 13 ← r 14 ← r 15 ←	s 4 + s 0 s 5 + s 1 s 6 + s 2 s 7 + s 3 s 4 s 5 + s 4 + s 0 s 6 + s 5 + s 1 s 7 + s 6 + s 2 c 0 + s 7 + s 3 c 1 + s 4 c 2 + s 5 c 3 + s 6 c 4 + s 7 + s 4 + s 0 c 5 + s 5 + s 1 c 6 + s 6 + s 2 c 7 + s 7 + s 3	c 8 + e 4 + e 0 c 9 + e 5 + e 1 c 10 + e 6 + e 2 c 11 + e 0 + e 7 + e 3 c 12 + e 1 c 13 + e 2 c 14 + e 3 c 15 + e 4 + e 0 e 0 + e 5 + e 1 e 1 + e 6 + e 2 e 2 + e 7 + e 3 e 3 e 4 + e 0 e 5 + e 1 e 6 + e 2 e 7 + e 3
Cコードの一部:	uint8_t d , s , t ; uint16_t c , r ; … s = d ^ ( c >> 8 ); t = s ^ ( s >> 4 ); r = ( c << 8 ) ^ t ^ ( t << 5 ) ^ ( t << 12 );	uint8_t d , e , f ; uint16_t c , r ; … e = c ^ d ; f = e ^ ( e << 4 ); r = ( c >> 8 ) ^ ( f << 8 ) ^ ( f << 3 ) ^ ( f >> 4 );

多項式:	x 16 + x 15 + x 2 + 1 (CRC-16-ANSI)
係数:	0x8005 (MSBF/通常)	0xa001 (LSBF/逆)
r 0 ← r 1 ← r 2 ← r 3 ← r 4 ← r 5 ← r 6 ← r 7 ← r 8 ← r 9 ← r 10 ← r 11 ← r 12 ← r 13 ← r 14 ← r 15 ←	s p s 0 + s p s 1 + s 0 s 2 + s 1 s 3 + s 2 s 4 + s 3 s 5 + s 4 s 6 + s 5 c 0 + s 7 + s 6 c 1 + s 7 c 2 c 3 c 4 c 5 c 6 c 7 + s p	c 8 + e p c 9 c 10 c 11 c 12 c 13 c 14 + e 0 c 15 + e 1 + e 0 e 2 + e 1 e 3 + e 2 e 4 + e 3 e 5 + e 4 e 6 + e 5 e 7 + e 6 e p + e 7 e p
Cコードの一部:	uint8_t d , s , p ; uint16_t c , r , t ; … s = d ^ ( c >> 8 ); p = s ^ ( s >> 4 ); p = p ^ ( p >> 2 ); p = p ^ ( p >> 1 ); p = p & 1 ; t = p | ( s << 1 ); r = ( c << 8 ) ^ ( t << 15 ) ^ t ^ ( t << 1 );	uint8_t d , e , p ; uint16_t c , r , f ; … e = c ^ d ; p = e ^ ( e >> 4 ); p = p ^ ( p >> 2 ); p = p ^ ( p >> 1 ); p = p & 1 ; f = e | ( p << 8 ); r = ( c >> 8 ) ^ ( f << 6 ) ^ ( f << 7 ) ^ ( f >> 8 );

2段階計算

CRC-32多項式のような密な多項式の場合、1バイトずつ剰余を計算すると、各ビットが前の反復の最大8ビットに依存する式が生成されます。バイト並列ハードウェア実装では、これは8入力またはカスケード接続されたXORゲートを必要としますが、これらのゲートには大きなゲート遅延が発生します。

計算速度を最大化するために、まずメッセージのCRCを、そのCRC多項式の倍数である疎多項式を法として計算することで、中間剰余を算出できる。CRC-32の場合、多項式^{x 123 + x 111 + x 92 + x 84 + x 64 + x 46} + x ²³ + 1^は、その^項（フィードバック^タップ）が^{少なくとも}8ビット^離れているという特性を持つ。したがって、123ビットのシフトレジスタは、2入力XORゲートのみを使用して、反復ごとに8ビットずつ進めることができ、これが最速となる。最後に、中間剰余を、より低速な2番目のシフトレジスタ（入力バイトごとに1回ではなく、CRCごとに1回）で標準多項式を法として減算することで、CRC-32剰余を算出できる。^{[ 13 ]}

3 入力または 4 入力 XOR ゲートが許可されている場合は、それぞれ次数 71 または 53 の短い中間多項式を使用できます。

状態空間変換

上記の手法は機能しますが、大きな中間シフトレジスタを必要とします。 2000年 頃から高速ネットワークで使用されている、よりハードウェア効率の高い手法は状態空間変換です。ビット単位のCRCエンジンの内部ループは、メッセージのビット部分を反映するように中間剰余を繰り返し更新します。 ${\displaystyle r}$ ${\displaystyle y}$ ${\displaystyle r}$ ${\displaystyle y_{i}}$

${\displaystyle y_{i}=A^{r}\cdot (y_{i-1}\oplus x_{i}).}$

実装上の課題は、行列の乗算をビット時間で実行する必要があることです。一般に、が増加すると、この乗算の複雑さも増加し、最大で約^{[ 14 ]}の速度向上が期待できます。これを改善するために、まず分配法則 を用いてこの式を次のように分解します。 ${\displaystyle A^{r}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r/2.}$

${\displaystyle y_{i}=A^{r}y_{i-1}\oplus A^{r}x_{i}.}$

次に、可逆行列 を求め、基底変換 を実行し、中間状態に を乗じます。したがって、反復は次のようになります。 ${\displaystyle T}$ ${\displaystyle T^{-1}}$

${\displaystyle T^{-1}y_{i}=T^{-1}A^{r}T(T^{-1}y_{i-1})\oplus T^{-1}A^{r}x_{i}.}$

最終的な CRC は 次のように復元されます。入力の による乗算と出力の による乗算は、パフォーマンス目標を達成するために必要な任意の深さにパイプライン化できるため、時間的にクリティカルではないことに注意することが重要です。 による中央の乗算のみがビット時間内に完了する必要があります。 それをコンパニオン行列の形にする変換行列を見つけることは可能です。言い換えれば、これはビット単位のアルゴリズムと同じ（高速な）2入力 XOR ゲートを使用して実装できます。^{[ 15 ] [ 16 ]} これにより、ビットの並列 CRC は、1 ビットの直列実装の 倍の速度で 動作できます。 ${\displaystyle y=T(T^{-1}y).}$ ${\displaystyle T^{-1}A^{r}}$ ${\displaystyle T}$ ${\displaystyle T^{-1}A^{r}T}$ ${\displaystyle r}$ ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle r}$

この特性を持つ変換行列は数多く存在するため、入力行列と出力行列の複雑さも最小化する変換行列を選択することが可能である。^{[ 16 ]} ${\displaystyle n\times n}$ ${\displaystyle T^{-1}A^{r}}$ ${\displaystyle T}$

ブロック単位の計算

任意のCRC多項式に対して、剰余のブロック単位の計算は、剰余を計算するために必要な状態空間変換行列を2つのより単純なテプリッツ行列に因数分解することによってハードウェアで実行できます。^{[ 17 ]}

ワンパスチェック

メッセージにCRCを付加する場合、送信済みのCRCを切り離して再計算し、再計算した値と送信済みのCRCを検証することも可能です。しかし、ハードウェアではより単純な手法が一般的に用いられます。

CRCが正しいバイト順（選択されたビット順規則に一致）で送信されると、受信側はメッセージとCRC全体にわたってCRCを計算することができ、それらが正しければ結果はゼロになる。^{[ 18 ]}この可能性は、CRCを含むほとんどのネットワークプロトコルが終了区切り文字の前に CRCを含む理由である。CRCをチェックするためにパケットの終わりが近いかどうかを知る必要はない。

実際、いくつかのプロトコルでは CRC をメッセージの区切り文字として使用しており、この手法はCRC ベース フレーミングと呼ばれます。(この手法では、フレーミングの取得または喪失を検出するために複数のフレームが必要となるため、フレームの長さが既知であり、フレームの内容が十分にランダムであるため、位置ずれしたデータに有効な CRC が含まれることはまれであるアプリケーションに限定されます。)

CRC変異体

実際には、ほとんどの規格では、送信前にレジスタを全て1にプリセットし、CRCを反転させることが規定されています。これはCRCがビットの変化を検出する能力には影響しませんが、メッセージに追加されたビットを検知する能力を与えます。

-1にプリセット

CRCの基本的な数学では、多項式として解釈した場合にCRC多項式の倍数となるメッセージを受け入れます（正しく送信されたとみなします）。このようなメッセージの先頭に0ビットが付加されていても、多項式としての解釈は変わりません。これは、0001と1が同じ数であるという事実に相当します。

しかし、送信されるメッセージが先頭の0ビットを考慮に入れている場合、基本的なCRCアルゴリズムがそのような変化を検出できないのは望ましくありません。伝送エラーによってそのようなビットが追加される可能性がある場合、簡単な解決策は、remシフトレジスタをゼロ以外の値に設定することです。便宜上、通常はすべて1の値が使用されます。これは数学的には、メッセージの最初のnビットの補数（2進論理否定）を取ることと等価です。ここで、 nはCRCレジスタのビット数です。

CRC生成器とチェッカーの両方が同じ初期値を使用する限り、これはCRC生成とチェックに何ら影響を与えません。ゼロ以外の初期値であれば何でも構いません。いくつかの規格では特殊な値が指定されていますが^{[ 19 ]}、すべて1の値（2の補数2進数で-1）が圧倒的に一般的です。1パスCRC生成/チェックでは、メッセージが正しい場合、プリセット値に関わらず、結果はゼロになります。

反転後

同様のエラーは、メッセージの末尾でも発生する可能性がありますが、対象となるメッセージは限定されます。メッセージに0ビットを追加することは、その多項式をxで乗算することと等価です。そして、その多項式がCRC多項式の倍数であった場合、その乗算の結果も同様になります。これは、726が11の倍数であるため、7260も11の倍数であるという事実に相当します。

同様の解決策をメッセージの末尾に適用することもできます。CRCレジスタを反転してからメッセージに追加します。この場合も、ゼロ以外の変更であれば何でも構いません。すべてのビットを反転する（すべて1のパターンでXOR演算する）のが最も一般的な方法です。

これはワンパスCRCチェックに影響します。メッセージが正しい場合にゼロの結果を生成する代わりに、固定のゼロ以外の結果を生成します。（正確には、結果はゼロがプリセットされ、後置反転された反転パターンのCRCです。）この定数を取得したら（例えば、任意のメッセージに対してワンパスCRC生成/チェックを実行するなど）、同じCRCアルゴリズムを使用してチェックされた他のメッセージの正当性を検証するために直接使用できます。

参照

一般カテゴリー

• 誤り訂正コード
• ハッシュ関数のリスト
• パリティは、多項式x +1を持つ 1 ビット CRC と同等です。

CRC以外のチェックサム

• アドラー32
• フレッチャーのチェックサム

参考文献

1. Dubrova, Elena; Mansouri, Shohreh Sharif (2012年5月). 「並列CRCエンコーディングのためのLFSRS構築のためのBDDベースアプローチ」 . 2012 IEEE 42nd International Symposium on Multiple-Valued Logic . pp.  128– 133. doi : 10.1109/ISMVL.2012.20 . ISBN 978-0-7695-4673-5. S2CID  27306826 .
2. Williams, Ross N. (1996年9月24日). 「CRCエラー検出アルゴリズムの簡単なガイド V3.00」 . 2006年9月27日時点のオリジナルよりアーカイブ。 2016年2月16日閲覧。
3. Sarwate, Dilip V. (1998年8月). 「テーブルルックアップによる巡回冗長検査の計算」 . Communications of the ACM . 31 (8): 1008– 1013. doi : 10.1145/63030.63037 . S2CID 5363350 . 
4. 「Portable Network Graphics (PNG) 仕様（第2版）：付録D、巡回冗長検査コードの実装例」 W3C 2003年11月10日. 2016年2月16日閲覧。
5. 「[MS-ABS]: 32ビットCRCアルゴリズム」 msdn.microsoft.com 。 2017年11月7日時点のオリジナルよりアーカイブ。 2017年11月4日閲覧。
6. Kounavis, ME; Berry, FL (2005). 「高性能ソフトウェアベースCRCジェネレータの構築に向けた体系的なアプローチ」.第10回IEEEコンピュータと通信シンポジウム (ISCC'05) (PDF) . pp.  855– 862. doi : 10.1109/ISCC.2005.18 . ISBN 0-7695-2373-0. S2CID  10308354 .
7. Berry, Frank L.; Kounavis, Michael E. (2008年11月). 「高性能CRC生成のためのテーブルルックアップベースの新しいアルゴリズム」. IEEE Transactions on Computers . 57 (11): 1550– 1560. Bibcode : 2008ITCmp..57.1 ​​550K . doi : 10.1109/TC.2008.85 . S2CID 206624854 . 
8. Intel Slicing-by-8アルゴリズムによる高オクタンCRC生成(PDF) (技術レポート). Intel . 2012年7月22日時点のオリジナル(PDF)からのアーカイブ。
9. 「CRC計算に関する簡単なチュートリアル」。Linuxカーネルアーカイブ。
10. Menon-Sen, Abhijit (2017-01-20). 「N分割CRC32アルゴリズムを発明したのは誰か？」 .
11. Jon Buller (1996年3月15日). 「Re: 8051 and CRC-CCITT」 .ニュースグループ:  comp.arch.embedded . Usenet: [email protected] . 2016年2月16日閲覧。 
12. AVR-LibC プロジェクト (2024年3月15日). "AVR-LibC <util/crc16.h>" .
13. Glaise, René J. (1997-01-20). 「ATMネットワークにおける巡回冗長コードCRC-32の2段階計算」 . IBM Journal of Research and Development . 41 (6). Armonk, NY : IBM : 705. doi : 10.1147/rd.416.0705 . 2009年1月30日時点のオリジナルよりアーカイブ。 2016年2月16日閲覧。
14. Pei, Tong-Bi; Zukowsk, Charles (1992年4月). 「VLSIにおける高速並列CRC回路」. IEEE Transactions on Communications . 40 (4): 653– 657. Bibcode : 1992ITCom..40..653P . doi : 10.1109/26.141415 .並列計算を用いることで大幅な高速化が達成できますが、k > 2の場合、単純なk倍の演算では十分な高速化は達成されません。実際、⁠け/2⁠（より正確には[0.4 k , 0.6 k l ）は、幅広い状況において妥当なモデルであると考えられます。k = 8の場合、プロトタイプ多項式は約4.9倍の高速化を達成したと推定されます。
15. Derby, Jeff H. (2001年11月25～29日).状態空間変換を用いた高速CRC計算. Global Telecommunications Conference. 米国テキサス州サンアントニオ. pp.  166– 170. doi : 10.1109/GLOCOM.2001.965100 .
16. Kennedy, Christopher; Reyhani-Masoleh, Arash (2009年6月7日).改良された状態空間変換を用いた高速CRC計算. IEEE International Conference on Electro/Information Technology. doi : 10.1109/EIT.2009.5189575 .
17. Das, Arindam (2023年4月). 「ルックアップテーブルの代わりに因数分解テプリッツ行列を用いた巡回冗長符号のブロック単位の計算」. IEEE Transactions on Computers . 72 (4): 1110– 1121. Bibcode : 2023ITCmp..72.1110D . doi : 10.1109/TC.2022.3189574 . ISSN 0018-9340 . S2CID 250472783 .  
18. Kadatch, Andrew; Jenkins, Bob (2010年9月3日). CRCについて知っていることのすべて(PDF) (技術レポート). p. 4.メッセージのCRCとそのCRCがメッセージに依存しない定数であるという事実はよく知られており、通信業界では長年広く利用されてきました。 さらに詳しい情報源
19. 例えば、低周波 RFID TMS37157 データシート - EEPROM および 134.2 kHz トランスポンダインターフェイスを備えたパッシブ低周波インターフェイスデバイス(PDF)、Texas Instruments、2009 年 11 月、p. 39 、2016 年 2 月 16 日取得、CRC ジェネレーターは、図 50 に示すように、値 0x3791 で初期化されます。

外部リンク

• JohnPaul Adamovsky。「64ビット巡回冗長コード - XOR長除算によるバイト単位のテーブル検索」。

• Andrew Kadarch、Bob Jenkins。「効率的な（1バイトあたり約1 CPUサイクル）CRC実装」。GitHub 。

「 https://en.wikipedia.org/w/index.php?title=Computation_of_cyclic_redundancy_checks&oldid=1334498958#CRC-32_example」から取得