巡回冗長検査の数学

巡回冗長検査(CRC) は、 GF(2) ( 2を法とする整数の有限体)上の多項式環における除算後の剰余の検査です。つまり、各係数が 0 または 1 で、算術演算がラップアラウンドする多項式の集合です。

任意のビット文字列は、この種の多項式の係数として解釈でき、合意された生成多項式で割り切れる（つまり、 の倍数である）場合、メッセージは有効な CRC を持ちます。CRC は、エラー検出特性が優れているため便利で人気があります。また、このような倍数は、ビットの剰余多項式を追加してを生成することで、任意のメッセージ多項式 から簡単に構築できます。ここで、は生成多項式の次数です。 ${\displaystyle M(x)}$${\displaystyle n}$ ${\displaystyle R(x)}$${\displaystyle W(x)=M(x)\cdot x^{n}+R(x)}$${\displaystyle n}$

をメッセージ部分とチェックサム部分に分離することはCRC の使用に便利ですが、エラー検出特性では区別がないため、 内のどこでもエラーが同様に検出されます。 ${\displaystyle W(x)}$${\displaystyle M(x)}$${\displaystyle R(x)}$${\displaystyle W(x)}$

一般に、CRCの計算はGF(2)上の多項式の ユークリッド除算に対応する。

${\displaystyle M(x)\cdot x^{n}=Q(x)\cdot G(x)+R(x).}$

ここで は元のメッセージ多項式であり、は次数生成多項式です。 のビットは、末尾にゼロが追加された元のメッセージです。 CRC「チェックサム」は、次数が より小さい剰余多項式の係数によって形成されます。商多項式は重要ではありません。を法とする演算を使用すると、次のように表すことができます。 ${\displaystyle M(x)}$${\displaystyle G(x)}$${\displaystyle n}$${\displaystyle M(x)\cdot x^{n}}$${\displaystyle n}$${\displaystyle R(x)}$${\displaystyle n}$${\displaystyle Q(x)}$

${\displaystyle R(x)=M(x)\cdot x^{n}\,{\bmod {\,}}G(x).}$

通信では、送信者はR のビットを M の元のメッセージ ビットの後に添付します。これは(コードワード) を送信することと同等であることが示されます。 受信者は を知っているので、を で割り、余りがゼロであることを確認します。 余りがゼロである場合、受信者は(最後のビット) を破棄し、受信したメッセージ ビットが正しいと想定します。 ${\displaystyle n}$${\displaystyle W(x)=M(x)\cdot x^{n}-R(x)}$${\displaystyle G(x)}$${\displaystyle W(x)}$${\displaystyle G(x)}$${\displaystyle R(x)}$${\displaystyle n}$${\displaystyle M(x)}$

ソフトウェア実装では、メッセージを部分に分割し、受信したメッセージを受信メッセージから再構築した値と比較することがありますが、ハードウェア実装では、常に上記の全長の除算の方が簡単であることがわかります。 ${\displaystyle R(x)}$

実際の CRC 計算は、減算で上位桁から借りるのではなく、排他的論理和演算になることを除けば、2 進数の長除算に最もよく似ています。

CRC は厳密な数学的な意味でのチェックサムであり、ビットごとのシンドロームの重み付きモジュロ 2 の合計として表現できますが、この単語は通常、10、256、65535 などのより大きなモジュロを使用して計算された合計に対してより具体的に使用されます。

CRC は、エラー訂正コードの一部としても使用できます。エラー訂正コードを使用すると、送信エラーの検出だけでなく、正しいメッセージの再構築も可能になります。これらのコードは、密接に関連した数学的原理に基づいています。

係数は 1 ビットに制限されているため、CRC 多項式に対する数学演算では、結果の係数を 0 または 1 にマッピングする必要があります。たとえば、次のようになります。

${\displaystyle (x^{3}+x)+(x+1)=x^{3}+2x+1\equiv x^{3}+1{\pmod {2}}.}$

係数の加算は2を法として実行されるため、上記の式では はゼロと等しくなることに 注意してください。${\displaystyle 2x}$

${\displaystyle 2x=x+x=x\times (1+1)\equiv x\times 0=0{\pmod {2}}.}$

2 を法とする多項式加算は、ビット単位の XORと同じです。XOR は自身の逆数なので、2 を法とする多項式減算もビット単位の XOR と同じです。

乗算も同様です（繰り上がりのない積）。

${\displaystyle (x^{2}+x)(x+1)=x^{3}+2x^{2}+x\equiv x^{3}+x{\pmod {2}}.}$

多項式を2を法として割り算し、商と余りを求めることもできます。例えば、を で割るとします。 ${\displaystyle x^{3}+x^{2}+x}$${\displaystyle x+1}$

${\displaystyle {\frac {x^{3}+x^{2}+x}{x+1}}=(x^{2}+1)-{\frac {1}{x+1}}.}$

言い換えると、

${\displaystyle (x^{3}+x^{2}+x)=(x^{2}+1)(x+1)-1\equiv (x^{2}+1)(x+1)+1{\pmod {2}}.}$

割り算の結果、商は-1 となり、余りは奇数なので最後のビットは 1 になります。 ${\displaystyle x^{2}+1}$

上記の式では、 は元のメッセージ ビット を表し、は生成多項式、剰余(つまり) は CRC です。生成多項式の次数は 1 なので、まずメッセージに を掛けてを取得します。 ${\displaystyle x^{3}+x^{2}+x}$111${\displaystyle x+1}$${\displaystyle 1}$${\displaystyle x^{0}}$${\displaystyle x^{1}}$${\displaystyle x^{3}+x^{2}+x}$

CRC にはいくつかの標準的なバリエーションがあり、その一部またはすべてを任意の CRC 多項式で使用できます。 エンディアンや CRC の表現などの実装のバリエーションは、ビット文字列をおよびの係数にマッピングする場合にのみ影響し、アルゴリズムの特性には影響しません。 ${\displaystyle M(x)}$${\displaystyle R(x)}$

• 割り算の余りは 0 である必要はありません。 これまでのテキストはすべて生成多項式で割り切れるかどうかで書かれていますが、任意の固定の余りを使用でき、余りが 0 の場合と同じように機能します。最も一般的には、すべて 1 の多項式が使用されますが、たとえば、非同期転送モードヘッダーのエラー制御フィールドの余りは です。 1 つの複雑な問題は、 を見つけて CRC を生成する同じハードウェアを使用して、 の全幅の割り算で CRC をチェックする場合に発生します 。後者では、0 や の余りは生成されず、 の余りが生成されます。 これによって CRC チェックが難しくなるわけではなく、予想されるパターンを知っておくだけで済みます。${\displaystyle S(x)}$${\displaystyle (x^{n}+1)/(x+1)}$${\displaystyle x^{6}+x^{4}+x^{2}+1.}$${\displaystyle R(x)=M(x)\cdot x^{n}{\bmod {G}}(x)+S(x)}$${\displaystyle W(x)\cdot x^{n}{\bmod {G}}(x).}$${\displaystyle S(x)}$${\displaystyle S(x)\cdot x^{n}{\bmod {G}}(x).}$
• 長除算は、非ゼロの剰余から始まる場合があります。 剰余は通常、現在の剰余を保持するビットのシフト レジスタを使用して計算され、メッセージ ビットが追加され、縮約法が実行されます。通常の除算では、シフト レジスタはゼロに初期化されますが、非ゼロ値に初期化される場合もあります。(この場合も、すべて 1 が最も一般的ですが、任意のパターンを使用できます。) これは、アルゴリズムに入力する前に、メッセージの最初のビットに初期化パターンを追加 (XOR) することと同じです。CRC 方程式は になります。ここで、 はビット単位のメッセージの長さです。これが に課す変更は、生成多項式とメッセージ長 の関数です。${\displaystyle n}$${\displaystyle G(x)}$${\displaystyle n}$${\displaystyle M(x)\cdot x^{n}+\sum _{i=m}^{m+n-1}x^{i}=Q(x)\cdot G(x)+R(x)}$${\displaystyle m>\deg(M(x))}$${\displaystyle R(x)}$${\displaystyle \sum _{i=m}^{m+n-1}x^{i}\,{\bmod {\,}}G(x)}$

これら 2 つのバリエーションは、メッセージに追加されたゼロ ビットを検出するために使用されます。先行するゼロ ビットは、値を変更しない先行ゼロ係数を追加するため、生成多項式による割り切れる度合いは変わりません。メッセージの最初のビットに固定パターンを追加することで、このような余分なゼロ ビットを検出できます。 ${\displaystyle W(x),}$

同様に、非ゼロの剰余を使用すると、メッセージに追加された末尾のゼロ ビットが検出されます。CRC 保護されたメッセージにゼロ ビットが追加された場合、受信多項式は 、前者が生成多項式で割り切れる場合は、後者も割り切れます。非ゼロの剰余を使用すると、ゼロ ビットが追加されると、異なる剰余が生成され、余分なビットが検出されます。 ${\displaystyle W(x)}$${\displaystyle W(x)\cdot x.}$${\displaystyle S(x)}$${\displaystyle S(x)\cdot x{\bmod {G}}(x)}$

実際には、これら 2 つのバリエーションは常に一緒に使用されます。これらは送信される CRC を変更するため、送信側と受信側の両方で実装する必要があります。両端で除算回路をすべて 1 にプリセットする必要があり、送信側は結果に末尾の反転パターンを追加する必要があります。受信側は CRC をチェックするときにこのパターンを想定する必要があります。受信側がフルレングスの除算で CRC をチェックする場合、CRC が既に含まれている完全なコードワードの CRC の剰余はゼロではなくなります。代わりに、1 の反転パターンの CRC である固定の非ゼロ パターンになります。 ${\displaystyle n}$

これらの反転は非常に一般的ですが、CRC-32 または CRC-16-CCITT 多項式の場合でも、普遍的に実行されるわけではありません。可変長メッセージを送信する場合はほぼ常に反転が含まれますが、固定長メッセージを通信する場合は、ゼロ ビットの追加の問題が発生する可能性が低いため、省略されることがよくあります。

すべての実用的な CRC 生成多項式には、ゼロ以外の係数があります。係数を省略してこれをバイナリ ビットの文字列に変換することは非常に一般的です。 ${\displaystyle x^{n}}$${\displaystyle x^{0}}$${\displaystyle n}$${\displaystyle x^{n}}$

このビット文字列は、次の 2 つの規則のいずれかを使用して 2 進数に変換できます。

• msbit ファースト表現では、 の係数が最上位ビットとなり、 の係数(常に 1) が最下位ビットとなります。${\displaystyle x^{n-1}}$${\displaystyle x^{0}}$
• lsbit-first 表現では、 の係数が最下位ビットとなり、 の係数(常に 1) が最上位ビットとなります。${\displaystyle x^{n-1}}$${\displaystyle x^{0}}$

文献では、msbit-first 形式が通常表現と呼ばれることが多く、lsbit-first 形式は逆表現と呼ばれます。CRC を実装するときは、正しい形式を使用することが重要です。係数がたまたまゼロになった場合、どちらの端にビットが設定されているのかを見れば、形式を一目で区別できます。 ${\displaystyle x^{n-1}}$

たとえば、説明されている形式の 16 次 CCITT 多項式 (角括弧内のビットはワード表現に含まれ、外側のビットは 1 ビットとして暗示され、縦棒はニブル境界を示します)。

16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 係数
 1 [0 0 0 1 |0 0 0 0 |0 0 1 0 |0 0 0 1] 正常                        
   [ 1 | 0 | 2 | 1 ] 普通のニブル
0x1021

 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
[1 0 0 0 |0 1 0 0 |0 0 0 0 |1 0 0 0] 1 逆                       
[ 8 | 4 | 0 | 8 ] リバースのニブル
0x8408

16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
 1 [0 0 0 0 |1 0 0 0 |0 0 0 1 |0 0 0 1] 逆数                    
   [ 0 | 8 | 1 | 1 ] 相互のニブル
0x0811

 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 逆数
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 クープマン
[1 0 0 0 |1 0 0 0 |0 0 0 1 |0 0 0 0] 1    
[ 8 | 8 | 1 | 0 ] ニブル
0x8810

よく知られている 度の CRC 生成多項式には、2 つの一般的な 16 進表現があります。どちらの場合も、 の係数は省略され、1 であると解釈されます。 ${\displaystyle n}$${\displaystyle x^{n}}$

• msbit-first 表現は、最下位ビットが常に 1 であるビットを持つ 16 進数です。最上位ビットは の係数を表し、最下位ビットは の係数を表します。${\displaystyle n}$${\displaystyle x^{n-1}}$${\displaystyle x^{0}}$
• lsbit-first 表現は、最上位ビットが常に 1 であるビットを持つ 16 進数です。最上位ビットは の係数を表し、最下位ビットは の係数を表します。${\displaystyle n}$${\displaystyle x^{0}}$${\displaystyle x^{n-1}}$

文献では、msbit-first 形式が通常表現と呼ばれることが多く、lsbit-first 形式は逆表現と呼ばれます。CRC を実装するときは、正しい形式を使用することが重要です。係数がたまたまゼロになった場合、どちらの端にビットが設定されているのかを見れば、形式を一目で区別できます。 ${\displaystyle x^{n-1}}$

さらに混乱を招くのは、P. Koopman と T. Chakravarty の論文^{[1] [2] が}CRC 生成多項式を別の方法で 16 進数に変換していることです。つまり、msbit ファーストですが、係数を含めて係数を省略しています。この「Koopman」表現の利点は、16 進形式から次数を決定でき、左から右の順序で係数を簡単に読み取れることです。ただし、他の場所では使用されておらず、混乱の恐れがあるため推奨されません。 ${\displaystyle x^{n}}$${\displaystyle x^{0}}$

逆数多項式は、ある多項式の係数を新しい多項式の係数に割り当てることによって作成されます。つまり、次数多項式の逆数は です。 ${\displaystyle x^{n}}$${\displaystyle x^{0}}$${\displaystyle x^{0}}$${\displaystyle x^{n}}$${\displaystyle n}$${\displaystyle G(x)}$${\displaystyle x^{n}G(x^{-1})}$

CRC で使用される逆数多項式の最も興味深い特性は、逆数である多項式とまったく同じエラー検出強度を持つことです。多項式の逆数は、ビットが反転しただけで同じコードワードを生成します。つまり、元の多項式のコードワードの最初のビット以外をすべて取り、反転して新しいメッセージとして使用すると、逆数多項式でのそのメッセージの CRC は、元のコードワードの最初のビットを反転したものに等しくなります。ただし、逆数多項式は元の多項式と同じではなく、それを使用して生成された CRC は、元の多項式によって生成された CRC と同じではありません (ビット反転を法としてさえ)。 ${\displaystyle n}$${\displaystyle n}$

CRC のエラー検出能力は、その生成多項式の次数と、使用される特定の生成多項式によって異なります。「エラー多項式」は、受信したメッセージ コードワードと正しいメッセージ コードワードの対称差です。エラー多項式が CRC 多項式で割り切れる場合にのみ、CRC アルゴリズムによってエラーが検出されません。 ${\displaystyle E(x)}$

• CRC は除算に基づいているため、データの先頭にゼロの文字列が付加されたエラーや、先頭のゼロが欠落したエラーを検出できる多項式はありません。ただし、§ バリエーションを参照してください。
• すべての単一ビット エラーは、係数がゼロでない項が少なくとも 2 つある任意の多項式によって検出されます。エラー多項式は であり、の多項式によってのみ割り切れます。${\displaystyle x^{k}}$${\displaystyle x^{k}}$${\displaystyle x^{i}}$${\displaystyle i\leq k}$
• 生成多項式の因数である原始多項式の次数より小さい距離で隔てられた 2 ビット エラーはすべて検出されます。2 ビットの場合のエラー多項式は です。前述のように、項 は CRC 多項式で割り切れないため、項 が残ります。定義により、多項式で割り切れるの最小値は、多項式の次数または指数です。最大次数の多項式は原始多項式と呼ばれ、2 進係数の次数 の多項式では次数 になります。${\displaystyle E(x)=x^{i}+x^{k}=x^{k}\cdot (x^{i-k}+1),\;i>k}$${\displaystyle x^{k}}$${\displaystyle x^{i-k}+1}$${\displaystyle {i-k}}$${\displaystyle x^{i-k}+1}$${\displaystyle n}$${\displaystyle 2^{n}-1}$
• 奇数ビットのすべてのエラーは、 の倍数である多項式によって検出されます。これは、 が非ゼロ係数を持つ偶数個の項を持つ多項式と同等です。を除くすべての原始多項式は奇数個の非ゼロ係数を持つため、この能力は、生成多項式がと 次数の原始多項式の積であると想定しています。${\displaystyle x+1}$${\displaystyle x+1}$${\displaystyle n-i}$${\displaystyle x+1}$
• 長さのすべてのバースト エラーは、非ゼロ項を持つ 次数以上の任意の多項式によって検出されます。${\displaystyle n}$${\displaystyle n}$${\displaystyle x^{0}}$

（余談ですが、ゼロ項を持つ多項式を使用する理由はありません。CRCはメッセージ多項式の剰余をCRC多項式で割ったものであることを思い出してください。ゼロ項を持つ多項式は常に因数としてを持ちます。したがって、が元のCRC多項式で、の場合、 ${\displaystyle x^{0}}$${\displaystyle x^{n}}$${\displaystyle x^{0}}$${\displaystyle x}$${\displaystyle K(x)}$${\displaystyle K(x)=x\cdot K'(x)}$

${\displaystyle M(x)\cdot x^{n-1}=Q(x)\cdot K'(x)+R(x)}$

${\displaystyle M(x)\cdot x^{n}=Q(x)\cdot x\cdot K'(x)+x\cdot R(x)}$

${\displaystyle M(x)\cdot x^{n}=Q(x)\cdot K(x)+x\cdot R(x)}$

つまり、多項式を含むメッセージの CRC は、ゼロが追加された多項式を含む同じメッセージの CRC と同じです。これは単にビットの無駄です。 ${\displaystyle K(x)}$${\displaystyle K'(x)}$

これらの要素の組み合わせは、優れた CRC 多項式が多くの場合、原始多項式 (2 ビットのエラー検出が最も優れている) または 次数の原始多項式に を乗じた式(奇数ビットエラーをすべて検出し、 次数の原始多項式の 2 ビットエラー検出能力の半分になる) であることを意味します。^[1]${\displaystyle n-1}$${\displaystyle x+1}$${\displaystyle n}$

^{ビットフィルタ[1]}を使用した解析技術により、与えられた生成多項式の特性を非常に効率的に決定することができます。結果は次のとおりです。

1. 長さが生成多項式 より長くないすべてのバースト エラー (1 つを除く) は、任意の生成多項式 によって検出できます。これには、1 ビット エラー (長さ 1 のバースト) が含まれます。最大長はで、 は生成多項式 (それ自体の長さは ) の次数です。この結果の例外は、ビット パターンが生成多項式のビット パターンと同じ場合です。${\displaystyle 1+\cdots +x^{n}}$${\displaystyle n+1}$${\displaystyle n}$${\displaystyle n+1}$
2. すべての不均等なビット エラーは、偶数項を持つ生成多項式によって検出されます。
3. 偶数パリティの最長ビットフィルタから生成多項式までの（倍数）距離にある 2 ビット エラーは検出されませんが、その他はすべて検出されます。次数が 32 までの場合、その次数と偶数の項を持つ最適な生成多項式が存在します。この場合、上記の周期は です。つまり、32,767 ビット長のブロックには未検出の 2 ビット エラーは含まれません。生成多項式の項数が奇数の場合、周期は になる可能性があります。ただし、これらの生成多項式（項数が奇数）では奇数個のエラーがすべて検出されるわけではないため、使用を避ける必要があります。対応する偶数項を持つ生成器の一覧は、このセクションの冒頭で述べたリンクにあります。${\displaystyle 2^{n-1}-1}$${\displaystyle n=16}$${\displaystyle 2^{n}-1}$
4. 前述のビットフィルタ期間内のすべての単一ビット エラー (生成多項式の偶数項) は、残差によって一意に識別できます。したがって、CRC 方式を使用して単一ビット エラーも修正できます (これらの制限内、たとえば、次数 16 の最適生成多項式を使用した 32,767 ビット)。すべての奇数エラーは奇数残差を残し、すべての偶数エラーは偶数残差を残すため、1 ビット エラーと 2 ビット エラーを区別できます。ただし、他のSECDED手法と同様に、CRC は 1 ビット エラーと 3 ビット エラーを常に区別できるわけではありません。ブロック内で 3 ビット以上のエラーが発生すると、CRC ビット エラー修正自体が誤りとなり、より多くのエラーが発生します。

• バレット縮小
• エラー訂正コード
• チェックサムアルゴリズムのリスト
• パリティ（通信）
• 巡回冗長検査の多項式表現