巡回冗長検査の計算

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

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

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

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

例

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

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

余りを計算するには、生成多項式の倍数を減算すればよい。 $G(x)$ これは小数による筆算とよく似ていますが、各ステップで可能な倍数は0と1のみであり、減算では上位桁を減らすのではなく「無限大から」借りるため、さらに簡単です。商は重要ではないため、記録する必要はありません。

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

msbit-first の例では、剰余多項式は次のようになります。 $x^{7}+x^{5}+x$ . xの最高次数をmsbit とする慣例を使用して 16 進数に変換すると、これは A2 ₁₆になります。 lsbit が最初の場合、余りは $x^{7}+x^{4}+x^{3}$ . xの最高べき乗が1 ビットであるという慣例を使用して 16 進数に変換すると、これは 19 ₁₆になります。

実装

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

以下は、 nビット CRC を計算するための擬似コードの最初の草案です。多項式には、整数変数ではなく、加算、乗算、べき乗が可能なPolynomialオブジェクトを生成するコンストラクタである、独自の複合データ型を使用します。2つの多項式に対しては、それらを 2 で剰余演算して加算します。つまり、両方の多項式の一致する各項の係数を排他的 OR演算します。xxor

function crc( bit array bitString[1..len], int len) { remainderPolynomial := polynomialForm (bitString[1..n]) // メッセージの最初の n ビット// 一般的なバリアントは、remainderPolynomial を補完します。§ を参照してください。i  が1からlenまでの場合、-1 にプリセットします{ remainderPolynomial := remainderPolynomial * x + bitString[i+n] * x ⁰ //残りの多項式のx ⁿの係数が 1 の場合、k>len に対して bitString[k]=0 を定義します{ remainderPolynomial := remainderPolynomial xor generatorPolynomial } } // 一般的なバリアントとして、remainderPolynomial がここにあります。§  Post -invert を参照してください。return remainderPolynomial }

コード断片1：単純な多項式の除算

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

このコードには 2 つの欠点があります。まず、実際にはn + 1 ビットのレジスタが必要でremainderPolynomial、 $x^{n}$ 係数はテストできます。さらに重要なのは、nbitStringビットのゼロでパディングする必要があることです。

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

2つ目の問題は、最後のn回の反復処理を異なる方法で行うことで解決できるが、ハードウェアとソフトウェアの両方の実装で普遍的に使用されている、より巧妙な最適化手法が存在する。

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

これにより、メッセージのremainderPolynomial最初のnビットを事前に読み込む必要もなくなります。

function crc( bit array bitString[1..len], int len) { 余り多項式 := 0 // 一般的なバリアントは、remainderPolynomial を補完します。§  iが1からlenまでの場合、以下で−1 にプリセットします{ remainderPolynomial := remainderPolynomial xor (bitstring[i] * x ⁿ⁻¹ ) if ( remainderPolynomial のx ⁿ⁻¹の係数) = 1 { remainderPolynomial := (remainderPolynomial * x ) xor generatorPolynomial }それ以外{ 残余多項式 := (残余多項式 * x ) } } // 一般的なバリアントとして、remainderPolynomial がここにあります。§  Post -invert を参照してください。return remainderPolynomial }

コード断片2：遅延メッセージXORを用いた多項式除算

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

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

function crc( byte array string[1..len], int len) { 余り多項式 := 0 // 一般的なバリアントは、remainderPolynomial を補完します。§  iが1からlenまでの場合、以下で−1 にプリセットします{ remainderPolynomial := remainderPolynomial xor polynomialForm (string[i]) * x ⁿ⁻⁸for j from 1 to 8 { // 1バイトあたり8ビットを想定if coefficient of x ⁿ⁻¹ of remainderPolynomial = 1 { remainderPolynomial := (remainderPolynomial * x ) xor generatorPolynomial }それ以外{ 残余多項式 := (残余多項式 * x ) } } } // 一般的なバリアントとして、remainderPolynomial がここにあります。§  Post -invert を参照してください。return remainderPolynomial }

コード断片3：バイト単位のメッセージXORを用いた多項式除算

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

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

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

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

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

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

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

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

// 最上位ビットを最初に (ビッグエンディアン) // (x ¹⁶ )+x ¹² +x ⁵ +1 = (1) 0001 0000 0010 0001 = 0x1021 function crc( byte array string[1..len], int len) { rem := 0 // 一般的なバリアントは、ここで rem を補完します。 iは1からlenまで{ rem := rem xor (string[i] leftShift (n-8)) // この例では n = 16 for j from 1 to 8 { // 1 バイトあたり 8 ビットを想定if rem and 0x8000 { // x ¹⁵係数をテスト rem := (rem leftShift 1) xor 0x1021 }それ以外{ rem := rem leftShift 1 } rem := rem and 0xffff // 余りを16ビットに切り詰める } } // 一般的なバリエーションは、rem を補完します 。remを返します。 }

コード断片4：シフトレジスタに基づく除算、最上位ビット優先

// 最下位ビットから開始 (リトルエンディアン) // 1+x ⁵ +x ¹² +(x ¹⁶ ) = 1000 0100 0000 1000 (1) = 0x8408 function crc( byte array string[1..len], int len) { rem := 0 // 一般的なバリアントは、ここで rem を補完します。 iは1からlenまで{ rem := rem xor string[i] for j from 1 to 8 { // 1バイトあたり8ビットと仮定if rem and 0x0001 { // x ¹⁵係数をテスト rem := (rem rightShift 1) xor 0x8408 }それ以外{ rem := rem rightShift 1 } } } // 一般的なバリエーションは、rem を補完します 。remを返します。 }

コード断片5：シフトレジスタに基づく除算、最下位ビット優先

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

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

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

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

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

// Msbit優先 rem = (rem leftShift 8) xor big_endian_table[string[i] xor ((rem の左端 8 ビット) rightShift (n-8))] // Lsbit-first rem = (rem rightShift 8) xor little_endian_table[string[i] xor (rem の右端 8 ビット)]

コード断片6：テーブルベースの除算のコア

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

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

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

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

big_endian_table[0] := 0 crc := 0x8000 // 16ビット多項式を想定 i := 1 do { if crc and 0x8000 { crc := (crc leftShift 1) xor 0x1021 // CRC多項式 } else { crc := crc leftShift 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

little_endian_table[0] := 0 crc := 1; i := 128 do { if crc and 1 { crc := (crc rightShift 1) xor 0x8408 // CRC多項式 } else { crc := crc rightShift 1 } // crcはlittle_endian_table[i]の値です。 jを0から255まで2 × iずつ反復して、既に初期化されたエントリを jで処理します{ 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多項式の1つにCRC-32があり、イーサネット、FDDI、ZIPなどのアーカイブ形式、PNG 画像形式などで使用されています。その多項式は、最上位ビットを先頭にすると0x04C11DB7、最下位ビットを先頭にすると0xEDB88320と表記できます。

これはCRCのCRC-32変異体の実例である。^{[ 5 ]}

別の情報源としては、PNG に関する W3C のウェブページがあり、そこには CRC-32 の短くシンプルなテーブル駆動型 C 実装を含む付録があります。^{[ 4 ]}このコードは、ここで紹介した lsbit-first バイト単位アルゴリズムに対応しており、テーブルはビット単位のコードを使用して生成されます。

関数CRC32 入力: data: Bytes  // バイト配列 出力: crc32: UInt32  // 32 ビット符号なし CRC-32 値// CRC-32 を初期値に初期化 crc32 ← 0xFFFFFFFF  for each byte in data do nLookupIndex ← (crc32 xor byte) and 0xFF crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex] // CRCTable は 256 個の 32 ビット定数の配列です// すべてのビットを反転して CRC-32 値を確定します crc32 ← crc32 xor 0xFFFFFFFF return crc32

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

#include <stdint.h> // uint32_t、uint8_t #include <stddef.h> // size_tstatic 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 ^= 0xFFFFFFFu ; return crc32 ; }

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

通常、Sarwate アルゴリズムと比較してパフォーマンスが 2 倍または 3 倍になるスライスバイn (CRC32 の場合は通常スライスバイ 8) アルゴリズムが存在します。このアルゴリズムは、一度に 8 ビットを読み取る代わりに、一度に8 nビットを読み取ります。これにより、スーパースカラプロセッサでのパフォーマンスが最大化されます。^{[ 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 ビットのインデックスに「分割」されます。一見すると、これは無意味に思えます。標準的な 1 バイト単位のアルゴリズムでは同じテーブルで 2 回の検索が行われるのに、なぜ別々のテーブルで 2 回の検索を行う必要があるのでしょうか。

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

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

この手法は、プロセッサが利用できる限り、当然ながら何枚でもスライスに拡張できる。

スライス幅がCRCサイズと等しい場合、わずかな高速化が実現します。基本的なSarwateアルゴリズムにおいて、前のCRC値をテーブルルックアップのサイズ分だけシフトする部分では、前のCRC値が完全に消去されるため（残る値はすべてゼロ）、XOR演算をクリティカルパスから除外できます。

結果として得られるn個のスライスからなる内部ループは、以下の要素で構成されます。

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

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

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

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

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

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

複数の縮約ステップは通常、行列演算として表現されます。1 つのシフトと次数による縮約 $n$ 生成多項式 $G(x)$ は、 $n\times n$ コンパニオンマトリックス $A=C(G)$ 。 $r$ ステップは行列として記述されます $A^{r}=C(G)^{r}$ 。

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

疎多項式の例

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

2段階の計算

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

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

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

状態空間変換

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

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

実装上の課題は、行列の乗算が $A^{r}$ 実行しなければならない $r$ ビット時間。一般的に、 $r$ が増加すると、この乗算の複雑さも増し、結果として最大で約の高速化が実現します。 $r/2.$ ^{[ 14 ]}これを改善するために、まず分配法則を用いてこの方程式を以下のように分解します。

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

次に、可逆行列を見つける。 $T$ そして基底変換を行い、中間状態を乗算する。 $\displaystyle T^{-1}}$ したがって、反復処理は次のようになります。

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

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

可能性はたくさんある $n\times n$ この性質を持つ変換行列が存在するため、入力行列と出力行列の複雑さを最小限に抑える行列を選択することが可能です。 $T^{-1}A^{r}$ そして $T$ [ ¹⁶^]

ブロック単位の計算

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

ワンパスチェック

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

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

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

CRCの変異型

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

−1にプリセット

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

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

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

ポストインバート

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

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

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

参考文献

↑ 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 .
1 2 Williams, Ross N. (1996-09-24). "A Painless Guide to CRC Error Detection Algorithms V3.00" . 2006-09-27 のオリジナルからアーカイブ済み。2016-02-16に取得。
↑ Sarwate, Dilip V. (1998年8月). 「テーブルルックアップによる巡回冗長検査の計算」 . Communications of the ACM . 31 (8): 1008–1013 . doi : 10.1145/63030.63037 . S2CID 5363350 .
1 2 「ポータブルネットワークグラフィックス（PNG）仕様（第2版）：付録D、巡回冗長コードの実装例」。W3C 。2003年11月10日。2016年2月16日取得。
↑ " [ MS-ABS ] : 32 ビット CRC アルゴリズム" . msdn.microsoft.com . 2017 年 11 月 7 日時点のオリジナルからアーカイブ済み。2017年11 月 4 日取得。
↑ 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 .
↑ 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 .
↑ Intel Slicing-by-8 アルゴリズムによる高効率 CRC 生成( PDF) (技術レポート)。Intel。2012年 7 月 22 日にオリジナル(PDF)からアーカイブされました。
↑ 「CRC計算に関する簡単なチュートリアル」。Linuxカーネルアーカイブ。
↑ Menon-Sen, Abhijit (2017-01-20). "誰がスライス-by-N CRC32アルゴリズムを発明したのか？" .
↑ Jon Buller (1996-03-15). "Re: 8051 と CRC-CCITT" .ニュースグループ: comp.arch.embedded . Usenet: 31498ED0.7C0A@nortel.com . 2016-02-16に取得.
↑ AVR-LibC プロジェクト (2024 年 3 月 15 日) "AVR-LibC <util/crc16.h>"。
↑ 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-01-30のオリジナルからアーカイブ済み。2016-02-16に取得。
↑ 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$ による単純な乗算では十分な高速化は実現されません。実際、 $⁠$ $k$ $/$ $2$ $⁠$ (より正確には $[0.4$ $k$ $, 0.6$ $k$ $l$ ) は、幅広い状況で妥当なモデルであるようです。k $= 8$ $の$ 場合、プロトタイプ多項式は約 4.9 倍の高速化を達成したと推定されます。
↑ Derby, Jeff H. (2001年11月25日～29日).状態空間変換を用いた高速CRC計算. グローバル電気通信会議. 米国テキサス州サンアントニオ. pp. 166–170 . doi : 10.1109/GLOCOM.2001.965100 .
1 2 Kennedy, Christopher; Reyhani-Masoleh, Arash (2009年6月7日).改良された状態空間変換を用いた高速CRC計算. IEEE International Conference on Electro/Information Technology. doi : 10.1109/EIT.2009.5189575 .
↑ 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 .
↑ Kadatch, Andrew; Jenkins, Bob (2010年9月3日). CRCについて私たちが知っているが忘れがちなことすべて(PDF) (技術レポート). p. 4.メッセージのCRCに続くCRCはメッセージに依存しない定数であるという事実はよく知られており、通信業界では長い間広く使用されてきました。さらに多くの情報源
↑例：低周波RFID TMS37157データシート - EEPROMと134.2kHzトランスポンダインターフェースを備えた受動低周波インターフェースデバイス（PDF）、テキサス・インスツルメンツ、2009年11月、 39ページ、2016年2月16日取得、CRCジェネレータは図50に示すように値0x3791で初期化されます。

外部リンク

JohnPaul Adamovsky。「64ビット巡回冗長コード - XOR長除算からバイト単位のテーブルルックアップ」。

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

[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 .

[williams96-2] 1 2 Williams, Ross N. (1996-09-24). "A Painless Guide to CRC Error Detection Algorithms V3.00" . 2006-09-27 のオリジナルからアーカイブ済み。2016-02-16に取得。

[3] Sarwate, Dilip V. (1998年8月). 「テーブルルックアップによる巡回冗長検査の計算」 . Communications of the ACM . 31 (8): 1008–1013 . doi : 10.1145/63030.63037 . S2CID 5363350 .

[PNGspec-4] 1 2 「ポータブルネットワークグラフィックス（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). "誰がスライス-by-N CRC32アルゴリズムを発明したのか？" .

[11] Jon Buller (1996-03-15). "Re: 8051 と CRC-CCITT" .ニュースグループ: comp.arch.embedded . Usenet: 31498ED0.7C0A@nortel.com . 2016-02-16に取得.

[12] AVR-LibC プロジェクト (2024 年 3 月 15 日) "AVR-LibC <util/crc16.h>"。

[glaise-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-01-30のオリジナルからアーカイブ済み。2016-02-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$ による単純な乗算では十分な高速化は実現されません。実際、 $⁠$ $k$ $/$ $2$ $⁠$ (より正確には $[0.4$ $k$ $, 0.6$ $k$ $l$ ) は、幅広い状況で妥当なモデルであるようです。k $= 8$ $の$ 場合、プロトタイプ多項式は約 4.9 倍の高速化を達成したと推定されます。

[15] Derby, Jeff H. (2001年11月25日～29日).状態空間変換を用いた高速CRC計算. グローバル電気通信会議. 米国テキサス州サンアントニオ. pp. 166–170 . doi : 10.1109/GLOCOM.2001.965100 .

[Kennedy2009-16] 1 2 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 .

[Kadatch2010-18] Kadatch, Andrew; Jenkins, Bob (2010年9月3日). CRCについて私たちが知っているが忘れがちなことすべて(PDF) (技術レポート). p. 4.メッセージのCRCに続くCRCはメッセージに依存しない定数であるという事実はよく知られており、通信業界では長い間広く使用されてきました。さらに多くの情報源

[19] 例：低周波RFID TMS37157データシート - EEPROMと134.2kHzトランスポンダインターフェースを備えた受動低周波インターフェースデバイス（PDF）、テキサス・インスツルメンツ、2009年11月、 39ページ、2016年2月16日取得、CRCジェネレータは図50に示すように値0x3791で初期化されます。

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]