読み方：せいせいたこうしき

生成多項式【generator polynomial】

生成多項式とは？

通信やデータ記録における誤り検出・訂正の仕組みで用いられる多項式。CRC（巡回冗長検査）などの方式で検査符号の生成に使われ、データの整合性を確認するための基準として機能する。

誤り検出符号や誤り訂正符号はデータが伝送や記録の前後で変化していないかを確かめる仕組みで、元のデータから一定の規則に基づいて算出した符号を付加し、読み込み時に同じ箇所のデータから同じ符号が算出できるかどうかで誤りを検出する。

符号の算出方法には様々なものがあるが、CRCなどの手法では、ある長さのビット列を多項式の係数が並んだものとみなし、これを生成多項式で割った余り（剰余）を検査符号とする。生成多項式は、通常「x」を変数とする多項式の形で表現される。ビット列は2進数の数列とみなすことができるため、係数は「0」（項が存在しない）か「1」（存在する）のみである。

例えば、4ビットの「1011」を多項式で表すと「x³＋x¹＋1」のようになる。x²の項に対応する2ビット目のみが「0」であるため、この項だけ存在せず、他の項の係数は「1」である。実際の演算はXOR演算などのビット演算を組み合わせて実行され、論理回路を用いて効率よく実行することができる。

どの生成多項式を選ぶかによって、検出できる誤りのパターンや範囲が変わる。バースト誤り（連続したビット誤り）への対応能力も生成多項式の設計に依存しており、用途ごとに標準化された多項式が定められている。イーサネットで使われるCRC-32やUSBで用いられるCRC-5など、通信規格ごとに異なる生成多項式が採用されている。