CRC多項式の設計
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/05 03:09 UTC 版)
CRCアルゴリズムの実装で最も重要なのは、生成多項式の選択である。生成多項式は、衝突が起きる確率を最小にしつつ、誤り検出性能を最大にするように選ぶ必要がある。 生成多項式の長さ(多項式に含まれる項の最大の次数に1を加えたもの)は算出される検査値の長さに直接影響するため、最も重要な性質となる。 よく採用される多項式の長さは次の通り。 9 ビット (CRC-8) 17 ビット (CRC-16) 33 ビット (CRC-32) 65 ビット (CRC-64) 検査値の長さがn ビットになるCRCは「n ビット CRC」と呼ばれる。長さn が与えられたとき、生成多項式が互いに異なる複数のCRCを作ることが可能である。n ビットCRCの生成多項式は最大次数がn であり、したがってn + 1個の項を含む(多項式の長さがn + 1)。剰余の長さはn となる。そのような特定のCRCを指す場合、 CRC-n-XXX という形式の呼び名が用いられる。 CRC多項式の設計には、処理速度だけでなく、保護したいブロック(データ+CRC値)の最大長、希望する誤り保護特性、またCRCを実装するのためのリソースの種類も影響する。よくある誤解として、「最良の」CRC多項式は、既約多項式かあるいは既約多項式に因子1 + xを乗じたものだ、というものがある。因子1 + xは任意の奇数個のビット誤りを検出可能にするために用いられる。実際には、その前に述べた全ての事項を考慮して多項式を選択すべきであり、その結果として既約でない多項式が選ばれることもあり得る。しかしながら、既約でない多項式がつくる剰余環は零因子を含むため、一定の割合で誤りの検出漏れが発生する。 生成多項式の特性は、アルゴリズムの定義から、以下のように導き出せる。 ゼロでない係数が複数あるCRC多項式は、入力メッセージ中のビット誤りが1つしかない場合、必ず検出できる。 多項式の最長の既約部分の長さがkビットであるCRC多項式は、入力メッセージ中のビット誤りが2つしかなく且つ、それらの間隔が両方のビット誤りを含め2k-1ビットより短い場合、必ず検出できる。 長さkビットのCRC多項式は、入力メッセージ中の最初のビット誤りと最後のビット誤りの間隔が両方のビット誤りを含めkビットより長くない（kビットより短いか、ちょうどkビットの) 場合、言い換えるとkビットより長くないバースト誤りが1つしかない場合、必ず検出できる。 x + 1 を因数に持つCRC多項式は、入力メッセージ中に奇数個のビット誤りがある場合、必ず検出できる。
※この「CRC多項式の設計」の解説は、「巡回冗長検査」の解説の一部です。
「CRC多項式の設計」を含む「巡回冗長検査」の記事については、「巡回冗長検査」の概要を参照ください。
- CRC多項式の設計のページへのリンク
