CRC生成多項式の因数x+1

巡回冗長検査 - Wikipedia

Wikipediaにある、CRCの生成多項式がx+1の因数を持つとParityチェックができ奇数の誤りを検出できることについての理解のメモ書き

BCH符号で考えるとき

符号多項式が$${GF(2)}$$上であり、$${w(x) = \sum_{i=0…n-1}{ w_ix^i}}$$とおける。生成多項式$${g(x)}$$のとき、$${w(x)}$$は$${g(x)}$$で割り切れる。$${g(x)}$$が題意のように因数$${x+1}$$をもつなら、$${w(x)}$$も持つので、$${w(1)=0}$$である。したがって$${w(1) = \sum_{i=0…n-1}{ w_i} = 0}$$。これは符号語が常に偶数個のビットだけ1であることを意味する。奇数個の誤りでは必ず受信語の1であるビットの数が奇数個になり、検出可能。

RS符号で考えるとき

先ほどとの違いは、$${w_i}$$が$${GF(2^m)}$$の元になるので、$${w(1) = \sum_{i=0…n-1}{ w_i} = 0}$$がすぐに偶数シンボルだけ非ゼロであることを意味しないことだ。例えば、原始多項式$${x^4 + x + 1}$$で作る$${GF(2^4)}$$の元は$${\alpha + \alpha^2 + \alpha^5 = 0}$$のように奇数個の和がゼロになることがある。しかしシンボルのさらに各ビットに注目すれば同様にパリティを検出できる。$${w(1) = \sum_{i=0…n-1}{ w_i} = 0}$$だから、シンボルのベクトル表示における任意の桁について、全シンボルでカウントすると偶数個だけ1になっている。したがって奇数ビットの誤りがあると、受信語において1つ以上の桁でこのカウントが奇数個となり、検出可能。