数理解析研究所講究録
第 1873 巻 2014 年 52-58

52

Generalizations of cyclic codes over finite fields
大阪樟蔭女子大学児童学部 松岡 学
Manabu Matsuoka
Faculty of Child Science,
Osaka Shoin Women’s University

1

はじめに有限体 $F$ 上のベクトル空間 $F^{n}=\{(a_{0}, \cdots, a_{n-1})|a_{i}\in F\}$ の部分空間 $C$ のことを長が条件さの線形符号という。 線形符号
$C\subseteq F^{n}$$n$$(a_{0}, a_{1}, \cdots, a_{n-1})\in C$

ならば $(a_{n-1}, a_{0}, a_{1}, \cdots, a_{n-2})\in C$を満たすとき、 巡回符号であるという。 巡回符号の概念には様々な拡張の方法がある。 $C$の線形符号とし，$c=(c_{0}, c_{1}, \cdots, c_{n-1})\in F^{n}$ を固定する。 このを有限体 $F$ 上の長さがとき，任意の $(a_{0}, a_{1}, \cdots, a_{n-1})\in C$ に対して、$n$$(a_{1}, a_{2}, \cdots, a_{n-1}, a_{0}c_{0}+a_{1}c_{1}+\cdots+a_{n-1}c_{n-1})\inC$に誘導される逐次符号と呼ぶ。
S. R. L\’opez-Permouth と B. R. Parra-Avila, S. Szabo は多巡回符号と逐次符号の関係を [5] において調べた。彼らの結果を踏まえて、ここでは逐次符号を多項式環の剰余環のが成り立つとき， を$C$$c$イデアルとして具体的に実現する方法を考える。また、巡回符号の有限環上への拡張方法についても考察する。
以後特に断らない限り、 $F$ は $1\neq 0$ である有限体、$n$は 2 以上の自然数、 $(g)$ は $g\in F[X]$によって生成される両側イデアルを表すものとする。

2多重巡回符号$F$を有限体とする。

$F^{n}$

における$k$次元部分空間 $C$ のことを線形 $[n, k]$ 符号という。

$c=$ $(c_{0}, c_{1}, \cdots, 砺- 1)$
定義 1. $C$ を有限体 $F$ 上の長さが の線形符号とし，する。 このとき、 任意の $(a_{0}, a_{1}, \cdots , a_{n-1})\in C$ に対して
$n$$\in F^{n}$を固定

53$(0, a_{0}, a_{1}, \cdots, a_{n-2})+a_{n-1}(c_{0}, c_{1}, \cdots, c_{n-1})\in C$が成り立つとき， を$C$$c$によって誘導される多重巡回符号と呼ぶ。

巡回符号と同じように多重巡回符号も多項式環の剰余環のイデアルとして表現される。 $c=(c_{0}, c_{1}, \cdots, c_{n-1})\in F^{n}$ 固定し $f(X)=X^{n}-c(X)$ とおく、 ここで $c(X)=$砺ー $1X^{n-1}+\cdots+c_{1}X+$ 偽である。 このとき、 $F$ -線形同形写像: $F^{n}arrow F[X]/(f(X))$ をに対し $a_{n-1}X^{n-1}+\cdots+a_{1}X+a_{0}$ を対応させる写像として定める。

$a=$ $(a_{0}, a_{1}, \cdots , a_{n-1})$

このとき、 この写像$\rho$に誘導される多重巡回符号と剰余環 $F[X]/(f(X))$ のイデアルを同一視することができる。 すなわち、 $C$ を $F[X]/(f(X))$ における多巡回符号とすると、 モニックな多項式 とが存在して $C=(g)/(f)$ と表せる。 ただし、 $f=hg$ で$\rho$によって$c$$h$$g$ある。

命題 2. 線形符号が に誘導される多重巡回符号であるための必要十分条件は$C$ が次のような形の $k\cross n$生成行列をもつことである$C\subseteq F^{n}$$c$$G=(\begin{array}{lllllll} \end{array})$であり$g_{n-k}\neq 0$。このとき、$\rho(C)=(\overline{g_{n-k}X^{n-k}+\cdots+g_{1}X+g_{0}})$は $F[X]/(f(X))$ のイデアルとなる。
$c=(c_{0}, c_{1}, \cdots, c_{n-1})\in F^{n}$に対して、$D_{c}=$$D_{c}$$(c_{0}00$を次の形の正方行列とする。

$c_{n-1}01)$$c_{1}1$.

...
が $c\in F^{n}$ に誘導される多重巡回符号であるための必要十分条件は線形符号の右からの乗法で $C$ が閉じていることである。
$C\subseteq F^{n}$$D_{c}$

543

逐次符号の線形符号とし、 $c=(c_{0}, c_{1}, \cdots, c_{n-1})\in F^{n}$ を固定する。 この
定義 3. $C$ を $R$ 上長さとき、 任意の $(a_{0}, a_{1}, \cdots , a_{n-1})\in C$ に対して
$n$$(a_{1}, a_{2}, \cdots, a_{n-1}, a_{0}c_{0}+a_{1}c_{1}+\cdots+a_{n-1}c_{n-1})\inC$が成り立つとき $C$ を$c$によって誘導される逐次符号と呼ぶ。に誘導される逐次符号であるための必要十分が $c=$
線形符号
条件は次の行列の右からの乗法で $C$ が閉じていることである。
$(c_{0}, c_{1}, \cdots , c_{n-1})$$C\subseteq F^{n}$$tD_{c}=(\begin{array}{lllll}0\ddots 0 c_{0}1 \ddots c_{1} \ddots \vdots 0 1 c_{n-1}\end{array})$$F^{n}$

上に次のような標準的な内積を定義する。

$x=(x_{0}, x_{1}, \cdots, x_{n-1}),$ $y=(y_{0}, y_{1}, \cdots, y_{n-1})\in F^{n}$に対して$<x, y>= \sum_{i=0}^{n-1}x_{i}y_{i}$線形符号 $C$ の双対符号$C^{\perp}$を次のように定義する。

$C^{\perp}=\{a\in F^{n}|$明らかに$C^{\perp}$

任意の $c\in C$ に対して〈 c, $a>=0\}.$は $F$ 上の線形符号になる。関係式 $\dim C^{\perp}=n-dimC$ はよく知られている。

を線形符号とする。 このとき、 $C$ が多重巡回符号 (逐次符号) であるた定理 4.
が逐次符号 (多重巡回符号) であることである。
めの必要十分条件は$C\subseteq F^{n}$$C^{\perp}$4

逐次符号の多項式表現$F$-線形同型写像$\tau$: $F^{n}arrow F[X]/(X^{n}-c_{n-1}X^{n-1}-\cdots-c_{0})$ を$\tau(a_{0}, a_{1}, \cdots, a_{n-1})=\overline{b_{n-1}X^{n-1}+\cdots+b_{1}X+b_{0}}$ただし、$b_{i}=a_{n-i-1}-a_{n-i-2}c_{n-1}-a_{n-i-3}c_{n-2}-\cdots-a_{0}c_{i+1},$$(i=0,1, \cdots, n-2),$ $b_{n-1}=a_{0}$と定める。
定理 5. $C$ がにより誘導された逐次符号のとき、$\tau(C)$ は $F[X]/(X^{n}-c_{n-1}X^{n-1}-\cdots-co)$ のイデアルである。
$c$55
定理 5 より、 次の系が成り立つ。
系 6. 任意の逐次符号に対して、 $\tau(C)=(g)/(f)$ かつ $f=hg$ . を満たす適当なモニックな多項式 $g,$ $h\in F[X]$ が存在する。
$C\subseteq F^{n}$例 7. $n=5$ の場合、 $f(X)=X^{5}-c_{4}X^{4}-c_{3}X^{3}-c_{2}X^{2}-c_{1}X-c_{0}$ とすると、$\tau$: $F^{5}arrow F[X]/(f(X))$ は$(a_{0}, a_{1}, a_{2}, a_{3}, a_{4})$を $b_{4}X^{4}+b_{3}X^{3}+b_{2}X^{2}+b_{1}X+b0$ に移す。

ここで、
$b_{4}=a_{0},$$b_{3}=a_{1}-a_{0}c_{4},$$b_{2}=a_{2}-a_{1}c_{4}-a_{0}c_{3},$$b_{1}=a_{3}-a_{2}c_{4}-a_{1}c_{3}-a_{0}c_{2},$$b_{0}=a_{4}-a_{3}c_{4}-a_{2}c_{3}-a_{1}c_{2}-a_{0}c_{1},$である。 逐次符号

5$C\subseteq F^{5}$に対して、 $\tau(C)$ は $F[X]/(f(X))$ のイデアルとなる。

有限可換 $QF$ 環上の符号$R$を (必ずしも可換とは限らない) 環とする。 左 $R$ . 加群 $P$ は、 任意の全射 $R$. 準同型

写像 $g:Marrow N$ と任意の $R$ -準同型写像 $f:Parrow N$ に対して、 $f=goh$ を満たすような適当な $R$-準同型写像 : $Parrow M$ が存在するとき、 射影加群と呼ばれる。
$h$

左 $R$-加群 $Q$ は任意の単射 $R$-準同型写像: $Narrow M$ と任意の -準同型写像 : $Narrow Q$に対して、 $f=h\circ g$ を満たすような適当な -準同型写像: $Marrow Q$ が存在するとき、$R$$g$$R$$f$$h$

入射加群と呼ばれる。
環 $R$ は左 (右) $R$-加群として入射加群であるとき、 左 (右) 自己入射と呼ばれる。 $R$が左かつ右自己入射であるとき、 単に自己入射と呼ばれる。
左 $R$-加群 $M$ は部分加群に関する降鎖条件を満たすとき、 アルティン加群と呼ばれる。
環 $R$ は左 (右) $R$-加群としてアルティン加群のとき、 左 (右) アルティン環という。 環$R$ が左かつ右アルティン環のとき、単にアルティン環と呼ばれる。
明らかに有限環はアルティン環である。
定義 8. $R$ を (必ずしも可換とは限らない) 環とする。 $R$ が左アルティンかつ左自己入射であるとき、 $R$ は $QF$ (quasi-Frobenius) 環と呼ばれる。
$QF$環になるための条件は左-右対象であることがよく知られている。

任意の $R$ -部分加群$C\subseteq R^{n}$に対して、$c\circ$は次のように定義される。

$C^{O}=\{\lambda\in Hom_{R}(R^{n}, R)|\lambda(C)=0\}.$定理 9. $R$ を (必ずしも可換とは限らない) 環とする。 次の条件は同値である。
は $QF$ 環である。
(1)(2) 任意の部分加群$R$$M\subseteq R^{n}$に対して、 $M^{oo}=M$ が成り立つ。

56$QF$環は射影加群や入射加群を用いて、次のように特徴づけることもできる。

定理 10. $R$ を (必ずしも可換とは限らない) 環とする。 次の条件は同値である。
(1) $R$ は $QF$ 環である。

(2) 左加群が射影加群であること入射加群であることは同値である。の部分加群 $C$ を上の加群の自由加群のとき、 $C$ を階数 の自由次に可換有限環上の符号について考える。 可換有限環$R$$R^{n}$の線形符号という。 $C$ が階数符号と呼び rank $C=r$ と表す。
以後特に断らない限り、 $R$ は可換有限環を表すものとする。
有限体の場合と同様に、 可換有限環においても巡回符号、 多重巡回符号、 逐次符号、 双対符号などが定義される。 多重巡回符号と逐次符号の関係について、 次が成り立つ。
環 $R$ 上の長さ

$r$$n$

定理 11. 線形符号

$C\subseteq R^{n}$$r$に対して、 次が成り立つ

は逐次符号である。
(1) $C$ が多重巡回符号ならば、は多重巡回符号である。
(2) $C$ が逐次符号ならば、$C^{\perp}$$C^{\perp}$$R$-加群準同型写像$\delta_{x}$: $R^{n}arrow R$ を任意の $x\in R^{n}$ に対して $\delta_{x}(y)=<y,$ $x>$ であるように定義する。
を
命題 12.
像である。
$x$$\delta_{x}$へ対応させるような準同型写像$\delta$:$C^{\perp}arrow c\circ$

は $R$ -加群の間の準同型写

可換有限 $QF$ 環上の多重巡回符号や逐次符号の代数的な性質を調べたい。
定理 13. $R$ を可換有限 $QF$ 環とする。 任意の部分加群が成り立つ。

$C\subseteq R^{n}$に対して、 $(C^{\perp})^{\perp}=C$

定理 11 と定理 13 から、 次の系が成り立つ。
系 14. $R$ を可換有限 $QF$ 環とする。 このとき、分条件は$C^{\perp}$$C$が多重巡回符号であるための必要十が逐次符号であることである。

が有限階数の自由 $R$ -加群であるとき、定理 15. $R$ を可換有限 $QF$ 環とする。
も有限階数の自由 $R$ -加群であり、 $rankC^{\perp}=n-$ rank $C$ が成り立つ。
$C\subseteq R^{n}$$C^{\perp}$

有限体上の多項式環は単項イデアル整域であったが、 一般に可換有限環においてはそうではない。 ここでは、 1 つの多項式から生成される線形符号について考える。
定義 16. $R$ を可換有限環とし、 $C$ を $R[X]/(f(X))$ における多重巡回符号とする。 モニックな多項式 $g,$ が存在して $\rho(C)=(g)/(f)$ かつ $f=hg$ を満たすとき、 $C$ を単項多重巡回符号と呼ぶ。 さらに、 の定数項が可逆のとき、 $C$ を可逆な定数項をもつ単項多重巡回$h$$g$符号という。

57$C$を $R[X]/(f(X))$ における多重巡回符号とする。 $f=X^{n}-\alpha\in R[X]$ の形のとき、 $C$を定数的巡回符号と呼ぶ。
可換有限 $QF$ 環上の定数的巡回符号のパリティ検査行列を決定する。
命題 17. $R$ を可換有限 $QF$ 環とし、 $f=X^{n}-\alpha\in R[X]$ とする。 $f=hg\in R[X]$ であとり、はそれぞれ次数が $n-k$ との多項式であるとする。 $C$ を $R[X]/(X^{n}-\alpha)$
$h$

$g$

$k$

において $g$ により生成されるイデアルに対応する線形 $[n, k]$ -符号とし、 $h(X)=h_{k}X^{k}+$$h_{k-1}X^{k-1}+\cdots+h_{1}X+h_{0}$とする。 このとき、 $C$ は次のような $(n-k)\cross n$ パリティ検

査行列 $H$ をもつ$H= (h_{k}000 h_{k}..

h_{1}0^{\cdot} h_{k}h_{1}h_{0}.

定義 18. $R$ を可換有限 $QF$ 環とし、

h_{0}0.

h_{1}.

h_{0}000)$.

を逐次符号とする。 $C$ は、が単項多重巡回符号であるとき、 単項逐次符号と呼ばれる。 さらに、が可逆な定数項をもつ単項$C^{\perp}$$C\subseteq R^{n}$$C^{\perp}$

多重巡回符号であるとき、 $C$ を可逆な定数項をもつ単項逐次符号という。
最終的に、 次の定理が成り立つ。
定理 19. $R$ を可換有限 $QF$ 環とし、 $C$ を$R^{n}$における自由符号とする。 このとき、 次の条件は同値である。
(1) $C$ とは共に可逆な定数項をもつ単項多重巡回符号である。
$C$と(2)は共に可逆な定数項をもつ単項逐次符号である。
$C$(3)は可逆な定数項をもつ単項多重巡回符号であり、 可逆な定数項をもつ単項逐次符号$C^{\perp}$$C^{\perp}$である。

(4)$C^{\perp}$は可逆な定数項をもつ単項多重巡回符号であり、 可逆な定数項をもつ単項逐次符号である。

(5) $C=(g)/(X^{n}-\alpha)$ は可逆なをもつ定数的巡回符号である。
(6) $C^{\perp}=(q)/(X^{n}-\beta)$ は可逆な をもつ定数的巡回符号である。
$\alpha$$\beta$

これまで可換有限 $QF$ 環上の多重巡回符号や逐次符号の代数的な性質を調べてきたが、有限体の場合と同様に、 逐次符号と多項式環の剰余環との関係を可換有限 $QF$ 環上で構築することが今後の課題である。

参考文献[1] M. Greferath, M. E. ’Sullivan, On bounds for codes over Frobenius rings under homogeneous weights, Discrete Math, 289 (2004), 11-24.
$O$58[2] Y. Hirano, On admissible rings, Indag. Math. 8 (1997), 55-59.
[3] S. Ikehata, On separable polynomials and Frobenius polynomials in skew polynomialrings, Math. J. Okayama. Univ. 22 (1980), 115-129.
[4] T. Y. Lam, Lectures on Modules and Rings, Graduate Texts in Mathematics, Vol. 189,Springer-Verlag, New York, 1999.

[5] S. R. L\’opez-Permouth, B. R. Parra-Avila and S. Szabo, Dual generalizations of theconcept of cyclicity of codes, Advances in Mathematics of Communications, Volume3, No. 3 (2009), 227-234.
[6] M. Matsuoka, Polycyclic codes and sequential codes over finite commutative $QF$ rings,$JP$ Journal of Algebra, Number Theory and Applications, Vol. 23 (2011), No. 1,

77-85.
[7] M. Matsuoka, Polynomial realization of sequential codes over finite fields, SUT Journalof Mathematics, Vol. 48 (2012), No. 1, 47-53.

[8] B. R. McDonald, Finite Rings With Identity, Pure and Applied Mathematics, Vol. 28,Marcel Dekker, Inc., New York, 1974.
[9] J. A. Wood, Duality for modules over finite rings and applications to coding theory,
Amer. J. Math, 121 (1999), 555-575.