CRCバースト誤り訂正能力の証明

CRC(Cyclic Redundancy Code)では、送信するデータをあらかじめ決めておいた特定の数で割り、その余りを検査ビットとして使う。受信側では検査ビット
除算は $${ F2[x] }$$ である多項式除算である。

CRCには、生成多項式C(x)がm次多項式のとき、連続したmビット内における任意の誤りを検出できる。すなわちmビットのバースト誤りを検出できる。本noteではそのことの証明をする。

送信データは $${ f(x)+g(x)x^n, g(x)はm−1次以下の多項式 }$$ とする。
検査ビットはr(x)とする。すなわち、 $${ f(x) + g(x)x^n = C(x)q(x) +  r(x), r(x)はm-1次以下 }$$ が成り立つ。
証明のためには、g(x)がエラーによって変化して別のm−1次以下の多項式h(x)になったとき、$${f(x)+g(x)x^n}$$と$${f(x)+h(x)x^n}$$の検査ビットが必ず一致しないことを証明すればよい。

まず、