巡回冗長検査の計算

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

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

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

バイト値 57 _{16 は、}使用されるビット順序規則に応じて、2 つの異なる順序で送信できます。それぞれが異なるメッセージ多項式を生成します。Msbit が先の場合は= 01010111 で、lsbit が先の場合は = 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)}$

各減算後、ビットが 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 を法として加算します。つまり、両方の多項式から一致する各項の係数 を排他的論理和します。x xor

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

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

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

ソフトウェアでは、各ビットの を最後の瞬間まで遅らせることもできますが、それより早く行うことも可能であることを覚えておくと便利です。一度に 1 ビットずつ実装する場合でも、 を一度に 1バイトずつ実行すると便利です。 ここでは、入力を 8 ビット バイトで取得します。xorxor

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

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

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

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

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

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

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

もう一つの一般的な最適化は、の最高次の係数でインデックス付けされたルックアップテーブルremを使用して、反復ごとに1ビット以上の被除数を処理する。^[3] 最も一般的なのは、256エントリのルックアップテーブルが使用され、外側のループ本体（ 上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: テーブルベースの除算のコア

最も一般的に使用される CRC アルゴリズムの 1 つはCRC-32として知られており、イーサネット、FDDI、ZIPおよびその他のアーカイブ形式、PNG 画像形式などで使用されています。その多項式は、msbitファーストで 0x04C11DB7 と記述するか、lsbit ファーストで 0xEDB88320 と記述できます。PNG に関する W3C の Web ページには、CRC-32 の C による短くてシンプルなテーブル駆動型の実装を含む付録が含まれています。^[4]このコードは、ここに示す lsbit ファーストのバイト単位の疑似コードに対応しており、テーブルはビット単位のコードを使用して生成されていることがわかります。

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

テーブルを生成するソフトウェアは非常に小さく高速なので、通常は、プログラム起動時にテーブルを計算する方が、ストレージから事前計算されたテーブルをロードするよりも高速です。 1 つの一般的な手法は、ビット単位のコードを 256 回使用して、256 個の可能な 8 ビット バイトの CRC を生成することです。 ただし、 という特性を利用することで、この手法を大幅に最適化できます。 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 テーブル生成、MSB ファースト

リトルエンディアンテーブル[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 テーブル生成、LSB ファースト

これらのコード サンプルでは、​​テーブル インデックスはi + jと同等です。どちらの形式も便利です。 i xor j

これはCRCのCRC-32バリアントの実用的なアルゴリズムです。^[5] CRCTableは、メッセージの各バイトに対して繰り返す必要がある計算を メモ化したものです（巡回冗長検査の計算§マルチビット計算）。

関数CRC32
   入力: 
      data: Bytes      // バイト配列
   出力: 
      crc32: UInt32     // 32ビット符号なしCRC-32値

// CRC-32を開始値に初期化
crc32 ← 0xFFFFFFFFデータ内の

各バイト
   nLookupIndex ← (CRC32 XORバイト) および 0xFF
   crc32 ← (crc32 shr 8) xor CRCTable[nLookupIndex]   // CRCTableは256個の32ビット定数の配列です

// すべてのビットを反転してCRC-32値を確定します
crc32 ← crc32 排他的論理和 0xFFFFFFFF
crc32
を返す

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

#include <inttypes.h> // uint32_t、uint8_t 

uint32_t CRC32 ( const uint8_t data [], size_t data_length ) { uint32_t crc32 = 0xFFFFFFFFu ; for ( size_t i = 0 ; i < data_length ; i ++ ) { const uint32_t lookupIndex = ( crc32 ^ data [ i ]) & 0xff ; crc32 = ( crc32 >> 8 ) ^ CRCTable [ lookupIndex ]; // CRCTable は 256 個の 32 ビット定数の配列です} // すべてのビットを反転して CRC-32 値を確定しますcrc32 ^= 0xFFFFFFFFu ; return crc32 ; }      
	   
	
	         
		        
		        
	
	
	
	  
	 

スライスバイn（CRC32の場合は通常スライスバイ8）アルゴリズムがあり、これは通常Sarwateアルゴリズムに比べて2倍または3倍のパフォーマンスを発揮します。このアルゴリズムは一度に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 ビットのメッセージと XOR すると、結果の半分は単にメッセージのコピーになります。注意深くコーディングすれば (誤ったデータ依存性を作成しないように)、スライス テーブルのロードの半分は、前のループ反復が完了する前に開始できます。その結果、プロセッサのメモリ サブシステムを継続的にビジー状態にするのに十分な作業となり、最大のパフォーマンスが得られます。前述のように、2000 年以降のマイクロプロセッサでは、このレベルに到達するには一般にスライス バイ 8 で十分です。

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

一度に1バイトまたは1ワードずつの並列更新も、テーブルを使わずに明示的に行うことができます。^[11]これは通常、高速ハードウェア実装で使用されます。各ビットについて、8ビットがシフトインされた後に方程式が解かれます。次の表は、次の記号を使用して、いくつかのよく使用される多項式の方程式を示しています。

CRC-32 多項式には多数の項があるため、一度に 1 バイトずつ剰余を計算する場合、各ビットは前の反復の最大 8 ビットに依存します。バイト並列ハードウェア実装では、8 入力またはカスケード接続された XOR ゲートのいずれかが必要になり、伝播遅延が増加します。

計算速度を最大化するために、まずメッセージのCRCをx ¹²³ + x ¹¹¹ + x ⁹² + x ⁸⁴ + x ⁶⁴ + x ⁴⁶ + x ^{23 + 1を}法として計算することで中間剰余を計算できます。これは、項（フィードバックタップ）が少なくとも8つの位置離れるように慎重に選択されたCRC-32多項式の倍数です。したがって、123ビットのシフトレジスタは、2入力XORゲートのみを使用して、反復ごとに8ビット進めることができ、これは可能な限り高速です。最後に、中間剰余を2番目のシフトレジスタで標準多項式を法として減算すると、CRC-32剰余が得られます。^[12]

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

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

メッセージに CRC を追加する場合、送信された CRC を切り離して再計算し、再計算した値を送信された値と照合することができます。ただし、ハードウェアではより単純な手法が一般的に使用されます。

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

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

実際には、ほとんどの標準では、レジスタをすべて 1 にプリセットし、送信前に CRC を反転するように指定しています。これは、CRC の変更されたビットを検出する機能には影響しませんが、メッセージに追加されたビットを通知する機能を提供します。

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

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

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

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

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

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

一般カテゴリー

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

非CRCチェックサム

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

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

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