巡回符号
cyclic code
定義
以下を満たすような$ [n,k]_q 符号$ \mathcal{C}を巡回符号と言う
$ (c_0,c_1,\cdots,c_{n-1})\in\mathcal{C}\Rightarrow (c_{n-1}, c_0,c_1,\cdots,c_{n-2})\in\mathcal{C}
前提
$ x^n-1を法とする、$ \mathbb{F}_q上の多項式環を以下のように表記する $ R_{n,q}=\mathbb{F}_q[x]/(x^n-1)
$ R_{n,q}\triangleright \mathcal{C}\ne\{0\}のとき
多項式$ a(x)=a_{0}+a_{1} x+a_{2} x^{2}+\cdots+a_{n-1} x^{n-1} \in R_{n, q}と
ベクトル$ \bm{a}=(a_0,a_1,\cdots,a_{n-1})\in\mathbb{F}^n_q
を同一視して、$ \mathcal{C}\subset\mathbb{F}^n_qとみなすと、
単項イデアルの2条件から、$ \mathcal{C}は$ \mathbb{F}^n_qの部分空間(線形符号)になる また、$ c(x)=c_0+c_1x+c_2x^2+\cdots+c_{n-1}x^{n-1}\in\mathcal{C}に対して、
$ x\cdot c(x)=c_{n-1}+c_0x+c_1x^2+\cdots+c_{n-2}x^{n-1}\in\mathcal{C}がなりたつ
$ [n,k]_q 符号$ \mathcal{C}に対して、$ \mathcal{C}が巡回符号であるための必要十分条件は$ R_{n,q}\triangleright \mathcal{C}である
定理
$ R_{n,q}\triangleright \mathcal{C}\ne\{0\}に対して以下が成り立つ
$ \mathcal{C}の中で次数最小のモニック多項式$ g(x)\in\mathcal{C}が存在する ただし$ g(x)\ne0
$ \mathcal{C}=\lang g(x)\rang
$ g(x)を巡回符号$ \mathcal{C}の生成多項式と言う $ g(x)は$ x^n-1の因子
すなわち$ g(x)は$ x^n-1を割り切る
$ \mathcal{C}=\{c(x)\in R_{n,q}|c(x)h(x)=0\;\mathrm{in}\; R_{n,q}\}
ただし、$ x^n-1=g(x)h(x)
$ \deg g(x)= n-kならば$ \mathcal{C}の次元は$ k
よって$ k=n-\deg g(x)
これは、$ [n,k,d]_q のやつの$ kmrsekut.icon
$ g(x)=g_{0}+g_{1} x+\cdots+g_{n-k-1} x^{n-k-1}+x^{n-k}のとき、以下の行列$ Gは、$ \mathcal{C}の生成行列
https://gyazo.com/5a3e9cb837fc69d826df457b44251f3b
一段ずつ右にずれていっているだけmrsekut.icon
$ h(x)=\sum^k_{i=0}h_ix^iのとき、$ h^{*}(x)=x^{k} h\left(x^{-1}\right)=h_{k}+h_{k-1} x+\cdots+h_{0} x^{k}とすると$ \mathcal{C}^\bot=\lang H^{-1}_0h^\ast(x) \rangであり
以下の行列$ Hは$ \mathcal{C}の検査行列 https://gyazo.com/00e57edcab312bf17544de00856d83c5
一段ずつ右にずれていっているだけmrsekut.icon
例
$ \mathcal{C}=\{0000,1221,2211,1122,2010,0201,0102,2112,1020\}\subset\mathbb{F}^4_3は、
$ R_{n,q}\triangleright \mathcal{C}を満たすので、巡回符号である
多項式に対応させた集合を$ Iとすると、
$ R_{4,3}\triangleright I=\{
$ 0
$ 1+2x+2x^2+x^3
$ 2+2x+x^2+x^3
$ 1+x+2x^2+2x^3
$ 2+x^2
$ 2x+x^3
$ x+2x^3
$ 2+x+x^2+2x^3
$ 1+2x^2
$ \}となる
次数最小のモニック多項式$ g(x)=2+x^2が$ \mathcal{C}の生成多項式
∵上の定理
であり、$ g(x)|(x^4-1)が成り立つ
検査多項式は$ h(x)=(x^4-1)/g(x)=1+x^2
次元は$ \dim\mathcal{C}=n-\deg g=4-2=2
生成行列は
$ G=\left[\begin{array}{llll}2 & 0 & 1 & 0 \\0 & 2 & 0 & 1\end{array}\right]
検査行列は
$ H=\left[\begin{array}{llll}1 & 0 & 1 & 0 \\0 & 1 & 0 & 1\end{array}\right]