情報理論・符号理論の問題

$G$ の列について

$13$ 個の列は、最初の $0$ でない成分が第 $1,2,3$ 成分であるものがそれぞれ $3^2=9$ 個、$3$ 個、$1$ 個で、$9+3+1=13$。$0$ でない $\mathbf{x}\in {\mathbb{F}}_3^3$ は、スカラー倍 $\mathbf{x},2\mathbf{x}$ のうちちょうど $1$ つが「最初の $0$ でない成分が $1$」の形になる。つまり、$G$ の列は ${\mathbb{F}}_3^3$ の $0$ でないベクトルを「スカラー倍で移り合うもの」ごとに $1$ つずつ代表として選んだものである。

$k^{\perp }$

$G$ の列には $(1,0,0{)}^T,(0,1,0{)}^T,(0,0,1{)}^T$ が含まれるので $\mathrm{rank}G=3$、よって $\dim C=3$。$C^{\perp }$ は $G$ を検査行列とする符号（$G{\mathbf{y}}^T=0$ の解空間）なので
$$k^{\perp }=13-\mathrm{rank}G=13-3=10.$$

$d$

$\mathbf{u}\ne 0$ に対し、符号語 $\mathbf{u}G$ の第 $j$ 成分は $\mathbf{u}{\mathbf{x}}_j$（${\mathbf{x}}_j$ は $G$ の第 $j$ 列）である。$\mathbf{u}G$ の $0$ である成分の個数は、$\mathbf{u}\mathbf{x}=0$ をみたす列 $\mathbf{x}$ の個数に等しい。

$\mathbf{u}\ne 0$ より、$\{\mathbf{x}\in {\mathbb{F}}_3^3\mid \mathbf{u}\mathbf{x}=0\}$ は $2$ 次元の部分空間で、元の個数は $3^2=9$。そのうち $0$ でないものは $8$ 個で、これらは $\mathbf{x}$ と $2\mathbf{x}$ の組 $4$ 組に分かれる（$\mathbf{u}\mathbf{x}=0$ なら $\mathbf{u}(2\mathbf{x})=0$）。各組からちょうど $1$ つが $G$ の列なので、$\mathbf{u}\mathbf{x}=0$ となる列は $4$ 個。したがって
$$\mathrm{wt}(\mathbf{u}G)=13-4=9$$
が、$0$ でないすべての $\mathbf{u}$ について成り立つ。$C$ の $0$ でない符号語はすべて重み $9$ なので $d=9$。

$d^{\perp }$

$C^{\perp }$ の重み $w$ の符号語は、$G$ の $w$ 個の列を $0$ でない係数で結んだ $0$ の表し方に対応する。よって $d^{\perp }$ は「$G$ の列のうち $1$ 次従属になるものの最小個数」である。

• $G$ に零列はないので、重み $1$ の符号語はない。
• $2$ 列 $\mathbf{x},{\mathbf{x}}^{\prime }$ が $1$ 次従属なら ${\mathbf{x}}^{\prime }=\mathbf{x}$ または ${\mathbf{x}}^{\prime }=2\mathbf{x}$ だが、列は異なり、かつスカラー倍で移り合う $2$ つが両方とも列になることはないので、重み $2$ の符号語はない。
• ${\mathbf{x}}_1=(1,0,0{)}^T,{\mathbf{x}}_2=(0,1,0{)}^T,{\mathbf{x}}_3=(1,1,0{)}^T$ はすべて $G$ の列で、${\mathbf{x}}_1+{\mathbf{x}}_2+2{\mathbf{x}}_3=(3,3,0{)}^T=0$。対応する位置に $1,1,2$、ほかに $0$ を置いた語は $C^{\perp }$ の重み $3$ の符号語である。

よって $d^{\perp }=3$。

以上より $(k^{\perp },d,d^{\perp })=(10,9,3)$。

$G$ の列は射影空間 $PG(2,3)$ の 13 点の代表ベクトルであり、どの列も $0$ でなく、互いに他の定数倍になっていない。$G$ の階数は $3$（$e_1,e_2,e_3$ が列に含まれる）なので $\dim C=3$、よって $k^{\perp }=13-3=10$。\n\n$C$ の最小距離: $\mathbf{u}\ne 0$ に対し、符号語 $\mathbf{u}G$ の成分は各列 $\mathbf{g}$ について $\mathbf{u}\cdot \mathbf{g}$。$0$ になる列は、平面 $\{\mathbf{x}:\mathbf{u}\cdot \mathbf{x}=0\}$（${\mathbb{F}}_3^3$ の 2 次元部分空間）に含まれる列である。この平面の $0$ でないベクトルは $3^2-1=8$ 個で、$\pm$ の組で $4$ 点に対応するから、$0$ になる成分は $4$ 個。したがって重みは $13-4=9$ で、すべての非零符号語の重みが $9$（シンプレックス符号）。よって $d=9$。\n\n$C^{\perp }$ の最小距離: $\mathbf{y}\in C^{\perp }⟺G{\mathbf{y}}^T=0⟺{\sum }_i{y}_i{\mathbf{g}}_i=0$。\n- 重み $1$: $y_i{\mathbf{g}}_i=0$ は ${\mathbf{g}}_i\ne 0$ より不可。\n- 重み $2$: $y_i{\mathbf{g}}_i+y_j{\mathbf{g}}_j=0$ は ${\mathbf{g}}_i,{\mathbf{g}}_j$ が一次従属であることを意味するが、列は互いに異なる射影点なので不可。\n- 重み $3$: 同一直線上の 3 点（例: $e_1,e_2,e_1+e_2$ に対し $e_1+e_2-(e_1+e_2)=0$、すなわち $y=(1,1,2)$ を対応する位置に置く）で一次従属な組がある。\nよって $d^{\perp }=3$（ハミング符号 $[13,10,3]$）。\n\n検算: 球詰め限界 $$\begin{gathered} 3^{10} \\ cdot(1+13 \\ cdot2)=3^{10} \\ cdot27=3^{13} \end{gathered}$$ となり、$C^{\perp }$ は完全符号で $d^{\perp }=3$ と整合する。\n\n答え: $(k^{\perp },d,d^{\perp })=(10,9,3)$。