線形符号 (特に projective codes) の符号語と射影空間の超平面には深い繋がりがあるのでまとめていきます。
今回はわかりやすくするために 2 元符号を使いますが、基本的にどの有限体上でも同じです。
r r r シンプレックス符号 (simplex codes) は P G ( r − 1 , q ) {\rm PG}(r-1, q) PG ( r − 1 , q ) [ 2 r − 1 , r , 2 r − 1 ] 2 [2^r-1, r, 2^{r-1}]_2 [ 2 r − 1 , r , 2 r − 1 ] 2
ここでは例として、[ 7 , 3 , 4 ] 2 [7, 3, 4]_2 [ 7 , 3 , 4 ] 2 C C C C C C G G G
G = ( 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 ) . 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}. G = ⎝ ⎛ 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 ⎠ ⎞ . 次に射影空間の超平面について考えていきます。
射影空間 P G ( r − 1 , q ) {\rm PG}(r-1, q) PG ( r − 1 , q ) H H H v ∈ P G ( r − 1 , q ) v \in {\rm PG}(r-1, q) v ∈ PG ( r − 1 , q )
H = { p ∈ P G ( r − 1 , q ) ∣ v ⋅ p = 0 } . H = \{p \in {\rm PG}(r-1, q) \mid v \cdot p = 0\}. H = { p ∈ PG ( r − 1 , q ) ∣ v ⋅ p = 0 } . つまり、点 v v v P G ( 2 , 2 ) {\rm PG}(2, 2) PG ( 2 , 2 ) v = ( 1 , 1 , 1 ) T v=(1, 1, 1)^\mathsf{T} v = ( 1 , 1 , 1 ) T H H H
H = { ( 1 1 0 ) , ( 1 0 1 ) , ( 0 1 1 ) } . H = \left\{
\begin{pmatrix}
1 \\ 1 \\ 0
\end{pmatrix},
\begin{pmatrix}
1 \\ 0 \\ 1
\end{pmatrix},
\begin{pmatrix}
0 \\ 1 \\ 1
\end{pmatrix}
\right\}. H = ⎩ ⎨ ⎧ ⎝ ⎛ 1 1 0 ⎠ ⎞ , ⎝ ⎛ 1 0 1 ⎠ ⎞ , ⎝ ⎛ 0 1 1 ⎠ ⎞ ⎭ ⎬ ⎫ . ファノ平面で考えると確かに超平面である直線になってることがわかります:
ファノ平面 勘のいい方は気付いたかもしれませんが、シンプレックス符号の生成行列は射影空間の全ての点を並べたものであるため、v T G v^\mathsf{T}G v T G 0 0 0 シンプレックス符号における符号語 c = v T G c=v^\mathsf{T}G c = v T G (符号語の情報ベクトルの直交補空間が超平面になる)
具体的には、生成行列の i i i g i g_i g i c = v T G c=v^\mathsf{T}G c = v T G s u p p ( c ) : = { i ∣ c i ≠ 0 } {\rm supp}(c) := \{i \mid c_i \neq 0\} supp ( c ) := { i ∣ c i = 0 } E n : = { 1 , 2 , … , n } E_n:=\{1, 2, \dots, n\} E n := { 1 , 2 , … , n }
H = { p ∈ P G ( r − 1 , q ) ∣ v ⋅ p = 0 } = { g i ∣ i ∈ E n ∖ s u p p ( 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} H = { p ∈ PG ( r − 1 , q ) ∣ v ⋅ p = 0 } = { g i ∣ i ∈ E n ∖ supp ( c )} となります。
このことから、次の事が射影幾何から示すことができます:
定理
r r r 2 r − 1 2^{r-1} 2 r − 1
証明
シンプレックス符号の零ベクトルを除く任意の符号語 c c c 0 0 0 P G ( r − 1 , q ) {\rm PG}(r-1, q) PG ( r − 1 , q ) H H H
w t ( c ) = 2 r − 1 − ∣ H ∣ = 2 r − 1 − ( 2 r − 1 − 1 ) = 2 r − 1 . \begin{aligned}
wt(c) &= 2^{r} - 1 - |H| \\
&= 2^{r} - 1 - (2^{r-1} - 1) \\
&= 2^{r-1}.
\end{aligned} wt ( c ) = 2 r − 1 − ∣ H ∣ = 2 r − 1 − ( 2 r − 1 − 1 ) = 2 r − 1 . projective codes とは、射影空間上の点を列ベクトルとして集めたものを生成行列とする符号です。
最大な projective codes がシンプレックス符号になります。
シンプレックス符号から列ベクトルを削除しただけのものなので、符号語 c c c 0 0 0
また、次のような命題を示すことができます:
命題
[ n , r ] q [n, r]_q [ n , r ] q C C C G G G P G ( r − 1 , q ) {\rm PG}(r-1, q) PG ( r − 1 , q ) G G G S S S k k k c 1 , c 2 , … , c k c_1, c_2, \dots, c_k c 1 , c 2 , … , c k ⋃ i = 0 k s u p p ( c i ) = E n \bigcup_{i=0}^{k} {\rm supp}(c_i) = E_n ⋃ i = 0 k supp ( c i ) = E n P G ( r − 1 , q ) ∖ S {\rm PG}(r-1, q)\setminus S PG ( r − 1 , q ) ∖ S r − k − 1 r-k-1 r − k − 1
証明
P G ( r − 1 , q ) {\rm PG}(r-1, q) PG ( r − 1 , q ) r − k − 1 r-k-1 r − k − 1 Π r − k − 1 \Pi_{r-k-1} Π r − k − 1 k k k H i H_i H i k k k r − k − 1 r-k-1 r − k − 1
ここで、P G ( r − 1 , q ) ∖ S {\rm PG}(r-1, q) \setminus S PG ( r − 1 , q ) ∖ S G G G G ′ G' G ′ G ′ G' G ′ C ′ C' C ′ [ n ′ , r ] [n', r] [ n ′ , r ] c i ′ c'_i c i ′ H i H_i H i E n ′ ∖ s u p p ( c i ′ ) E_{n'} \setminus {\rm supp}(c'_i) E n ′ ∖ supp ( c i ′ )
⋂ i = 0 k H i = ⋂ i = 0 k { g j ′ ∣ j ∈ E n ′ ∖ s u p p ( c i ′ ) } = { g j ′ | j ∈ E n ′ ∖ ⋃ i = 0 k s u p p ( c i ′ ) } . \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} i = 0 ⋂ k H i = i = 0 ⋂ k { g j ′ ∣ j ∈ E n ′ ∖ supp ( c i ′ )} = { g j ′ ∣ ∣ j ∈ E n ′ ∖ i = 0 ⋃ k supp ( c i ′ ) } . したがって、
∃ c 1 , c 2 , … , c k ∈ C s . t . ⋃ i = 0 k s u p p ( c i ) = E n ⇔ ∃ c 1 ′ , c 2 ′ , … , c k ′ ∈ C ′ s . t . E n ′ ∖ ⋃ i = 0 k s u p p ( c i ′ ) ⊆ E n ′ ∖ E n ⇔ ∃ Π r − k − 1 ⊆ P G ( r − 1 , 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} ∃ c 1 , c 2 , … , c k ∈ C s.t. i = 0 ⋃ k supp ( c i ) = E n ⇔ ∃ c 1 ′ , c 2 ′ , … , c k ′ ∈ C ′ s.t. E n ′ ∖ i = 0 ⋃ k supp ( c i ′ ) ⊆ E n ′ ∖ E n ⇔ ∃ Π r − k − 1 ⊆ PG ( r − 1 , q ) ∖ S . 線形符号 (特に projective codes) の符号語と射影空間の超平面の関係について説明しました。
線形符号と射影幾何の繋がりをこれからもまとめていければなと思います。🙃