線形符号の符号語と射影空間の超平面

Article
(Updated at: )

線形符号 (特に projective codes) の符号語と射影空間の超平面には深い繋がりがあるのでまとめていきます。 今回はわかりやすくするために 2 元符号を使いますが、基本的にどの有限体上でも同じです。

2 元シンプレックス符号の符号語と超平面

rr 次元のシンプレックス符号 (simplex codes) は PG(r1,q){\rm PG}(r-1, q) の全ての点を列ベクトルとした生成行列で表される符号であり、 特に 2 元シンプレックス符号 (binary simplex codes) は、非零ベクトルを列ベクトルとして並べたものを生成行列としてもつ [2r1,r,2r1]2[2^r-1, r, 2^{r-1}]_2 線形符号です。

ここでは例として、[7,3,4]2[7, 3, 4]_2 シンプレックス符号 CC を考えます。CC の生成行列 GG は次ようになります:

G=(100110101010110010111).G=\begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \end{pmatrix}.

次に射影空間の超平面について考えていきます。 射影空間 PG(r1,q){\rm PG}(r-1, q) における任意の超平面 HH は双対性により、ある点 vPG(r1,q)v \in {\rm PG}(r-1, q) が存在して次のように書くことができます:

H={pPG(r1,q)vp=0}.H = \{p \in {\rm PG}(r-1, q) \mid v \cdot p = 0\}.

つまり、点 vv に対して直交するベクトルを集めたものになります。 例として、PG(2,2){\rm PG}(2, 2) 上の v=(1,1,1)Tv=(1, 1, 1)^\mathsf{T} に対応する超平面 HH は次のようになります:

H={(110),(101),(011)}.H = \left\{ \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} \right\}.

ファノ平面で考えると確かに超平面である直線になってることがわかります:

ファノ平面

勘のいい方は気付いたかもしれませんが、シンプレックス符号の生成行列は射影空間の全ての点を並べたものであるため、vTGv^\mathsf{T}G を計算して 00 となっている列のベクトルを集めると超平面になります。 つまり、シンプレックス符号における符号語 c=vTGc=v^\mathsf{T}G の 0 の列と超平面が対応していることがわかります。(符号語の情報ベクトルの直交補空間が超平面になる)

具体的には、生成行列の ii 列目のベクトルを gig_i、符号語 c=vTGc=v^\mathsf{T}G に対して supp(c):={ici0}{\rm supp}(c) := \{i \mid c_i \neq 0\}En:={1,2,,n}E_n:=\{1, 2, \dots, n\} とすると、

H={pPG(r1,q)vp=0}={giiEnsupp(c)}\begin{aligned} H &= \left\{p \in {\rm PG}(r-1, q) \mid v \cdot p = 0\right\}\\ &= \{g_i \mid i \in E_n \setminus {\rm supp}(c)\} \end{aligned}

となります。

2 元シンプレックス符号の符号語の重み

このことから、次の事が射影幾何から示すことができます:

定理

rr 次元の 2 元シンプレックス符号の符号語は零ベクトルを除いて重みが 2r12^{r-1} となる。

証明

シンプレックス符号の零ベクトルを除く任意の符号語 cc00 の数は、射影空間 PG(r1,q){\rm PG}(r-1, q) における超平面 HH に含まれる点の個数に対応しているため

wt(c)=2r1H=2r1(2r11)=2r1.\begin{aligned} wt(c) &= 2^{r} - 1 - |H| \\ &= 2^{r} - 1 - (2^{r-1} - 1) \\ &= 2^{r-1}. \end{aligned}

\square

projective codes の符号語と超平面

projective codes とは、射影空間上の点を列ベクトルとして集めたものを生成行列とする符号です。 最大な projective codes がシンプレックス符号になります。

シンプレックス符号から列ベクトルを削除しただけのものなので、符号語 cc00 となるものを集めたものは生成行列からなるマトロイドのフラットに対応します。

また、次のような命題を示すことができます:

命題

[n,r]q[n, r]_q projective codes CC の生成行列を GGPG(r1,q){\rm PG}(r-1, q) 上における GG の列ベクトルに対応する点の集合を SS とする。 kk 個の符号語 c1,c2,,ckc_1, c_2, \dots, c_k に対して、i=0ksupp(ci)=En\bigcup_{i=0}^{k} {\rm supp}(c_i) = E_n であることと、PG(r1,q)S{\rm PG}(r-1, q)\setminus Srk1r-k-1 次元射影空間が存在することは同値である。

証明

PG(r1,q){\rm PG}(r-1, q) における任意の rk1r-k-1 次元部分空間 Πrk1\Pi_{r-k-1}kk 個の超平面 HiH_i の交わりによって表現でき、任意の kk 個の超平面の交わりは rk1r-k-1 次元部分空間を含む。

ここで、PG(r1,q)S{\rm PG}(r-1, q) \setminus S 上の全ての点を GG の列ベクトルに加えた生成行列を GG' とすると、GG' から生成される符号はシンプレックス符号 CC' になる。 [n,r][n', r] シンプレックス符号の符号語 cic'_i に対して超平面 HiH_iEnsupp(ci)E_{n'} \setminus {\rm supp}(c'_i) に対応することから、

i=0kHi=i=0k{gjjEnsupp(ci)}={gj | jEni=0ksupp(ci)}.\begin{aligned} \bigcap_{i=0}^{k} H_i &= \bigcap_{i=0}^{k} \{g'_j \mid j \in E_{n'} \setminus {\rm supp}(c'_i)\} \\ &= \left\{g'_j\ \middle|\ j \in E_{n'} \setminus \bigcup_{i=0}^{k} {\rm supp}(c'_i)\right\}. \end{aligned}

したがって、

c1,c2,,ckC s.t. i=0ksupp(ci)=Enc1,c2,,ckC s.t. Eni=0ksupp(ci)EnEnΠrk1PG(r1,q)S.\begin{aligned} &{}^\exists c_1, c_2, \dots, c_k \in C {\rm \ s.t.\ } \bigcup_{i=0}^{k} {\rm supp}(c_i) = E_n \\ &\Leftrightarrow {}^\exists c'_1, c'_2, \dots, c'_k \in C' {\rm \ s.t.\ } E_{n'} \setminus \bigcup_{i=0}^{k} {\rm supp}(c'_i) \subseteq E_{n'} \setminus E_n \\ &\Leftrightarrow {}^\exists\Pi_{r-k-1} \subseteq {\rm PG}(r-1, q) \setminus S. \end{aligned}

\square

おわりに

線形符号 (特に projective codes) の符号語と射影空間の超平面の関係について説明しました。 線形符号と射影幾何の繋がりをこれからもまとめていければなと思います。🙃

Author

me

syakoo

気分駆動フロントエンドエンジニア