書記が数学やるだけ#757 巡回符号の性質

巡回符号についていくつか性質を見ていく。

問題

説明

巡回符号とは，巡回シフトしても符号であるものを指し，その性質は多項式により表される。

解答

符号多項式について，符号多項式×任意の多項式をx^n-1で割った余りは，いずれも符号多項式となる。

生成多項式について，全ての符号多項式は生成多項式で割り切れる。

符号多項式であることの必要十分条件について。

また，生成多項式はx^n-1で割り切れ，定数項1の多項式である。

(n,k)巡回符号の生成多項式について。

検査多項式について，符号多項式との関係を示す。

シンドローム多項式から，誤りの有無が判断できる。

最後に具体例として，(7,4)巡回符号について。生成多項式はx^7-1の因数で，検査ビットは7-4=3ビットであることから決まる。この生成多項式は4つの基底で表すことができ，整理することで生成行列Gが求められる。あとは前回の公式から，情報検査ビット関連行列Pと検査行列Hを求める。

本記事のもくじはこちら：