巡回符号と多項式環

巡回符号は多項式環の言葉で表現することができる. $\sigma : {\bf F}_2^n\to{\bf F}_2[X]/(X^n-1)$を

$${\bf F}_2^n\ni{\mathbf a}=(a_1,a_2,\dots,a_n) \longmapsto \sum^n_{i=1}a_iX^{i-1}\in {\bf F}_2[X]/(X^n-1)$$

で定義される線形写像とすると, これは同型写像となる. これによって, まず, ${\bf F}_2^n$と ${\bf F}_2[X]/(X^n-1)$を同一視する.

この同一視において, ${\bf F}_2^n$での作用Sは, ${\bf F}_2[X]/(X^n-1)$の方では 「Xをかける」ということに相当する. つまり,

$$\begin{CD} {\bf F}_2^n @>{\sigma}>> {\bf F}_2[X]/(X^n-1) \\ ... ...ot}V \\ {\bf F}_2^n @>{\sigma}>> {\bf F}_2[X]/(X^n-1) \end{CD}$$

が可換(Sをやってから$\sigma$で移すのと, $\sigma$で移してからXをかけるのとでは結果は同じ)ということである. ちょっと確認してみよう.

$$X\cdot\sigma({\mathbf a}) =X\sum^n_{i=1}a_iX^{i-1} =a_1X+a_... ... a_n+a_1X+a_2X^2+\cdots+a_{n-1}X^{n-1} =\sigma(S({\mathbf a}))$$

ほらね.

上の同一視のもとで, 巡回符号について次のことが成り立つ.

補題 2.1   上の$\sigma$による巡回符号Cの像$\sigma(C)$は ${\bf F}_2[X]/(X^n-1)$のイデアルである.

この補題から,

$$\left\{ \text{巡回符号}\subset{\bf F}_2^n \right\} = \left\{ \text{イデアル}\subset{\bf F}_2^n[X]/(X^n-1)\right\}$$

となる. したがって, 今後はイデアルの性質を調べていくことになるが, その前に, 多項式環のイデアルについての重要な事実を述べておこう.

補題 2.2   ${\bf F}_2[X]/(X^n-1)$は主イデアル環, つまり, すべてのイデアルは唯一つの元から生成される.

この事実から, (n,k)-巡回符号は次のように表現されることがわかる.

$$\begin{CD} {\bf F}_2^n @>{\cong}>> {\bf F}_2[X]/(X^n-1) @.\\... ...)=(g(X))@.=\{q(X)g(X) \vert \deg q(X)\le n-1-\deg g\} \end{CD}$$

ただし, g(X), q(X)は, $\deg g=n-k, \deg q=k-1$なる多項式である.