検査行列と最小距離

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $6$ の線形符号 $C$ が、組織形の生成行列
$$G=(I_3\mid P)=\left(\begin{array}{cccccc}1& 0& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 1\end{array}\right)$$
で与えられている。$C$ の検査行列 $H=(-P^{\mathsf{T}}\mid I_3)$ を求め、$H$ の列の一次独立性を調べることで、$C$ の最小距離 $d$ と、ハミング重みが $d$ である符号語の個数 $A_d$ を求めよ。答えは $(d,A_d)$ の順の組で答えよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $6$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccccc}1& 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1\end{array}\right)$$
を用いて $C=\{\mathbf{x}\in {\mathbb{F}}_2^6\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ と定める。$C$ の次元 $k$、最小距離 $d$、ハミング重みが $d$ である符号語の個数 $A_d$ を、組 $(k,d,A_d)$ の形でこの順に求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $6$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccccc}1& 1& 0& 1& 0& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 1& 0& 0& 1\end{array}\right)$$
によって $C=\{\mathbf{x}\in {\mathbb{F}}_2^6\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$ と定める。$C$ の次元 $k$、最小距離 $d$、重み $d$ の符号語の個数 $A_d$ を求め、組 $(k,d,A_d)$ の形で答えよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上の符号長 $4$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccc}1& 0& 1& 1\\ 0& 1& 1& 2\end{array}\right)$$
によって
$$C=\{\mathbf{x}\in {\mathbb{F}}_3^4\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$$
と定める。符号語の重みは $0$ でない成分の個数、$C$ の最小距離 $d$ は $C$ の異なる 2 つの符号語のハミング距離の最小値とする。

$C$ の次元 $k$、最小距離 $d$、重みがちょうど $d$ である符号語の個数 $A_d$ を、組 $(k,d,A_d)$ の形でこの順に求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で考える。${\mathbb{F}}_2^4$ のベクトルのうち、ハミング重み（$1$ である成分の個数）が奇数であるものは全部で $8$ 個ある。これら $8$ 個のベクトルを列ベクトルとして、どれも $1$ 回ずつ、ある順に並べてできる $4\times 8$ 行列を $H$ とし、
$$C=\{\mathbf{x}\in {\mathbb{F}}_2^8\mid H{\mathbf{x}}^{\mathsf{T}}=0\}$$
で定まる符号長 $8$ の線形符号 $C$ を考える（$\mathbf{x}$ は行ベクトル）。$C$ の次元を $k$、最小距離を $d$、$C$ に含まれるハミング重みがちょうど $d$ の符号語の個数を $A_d$ とする。組 $(k,d,A_d)$ をこの順に求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $8$ の線形符号 $C$ を、生成行列
$$G=\left(\begin{array}{cccccccc}1& 1& 0& 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 1& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 0& 1\\ 0& 0& 0& 1& 0& 1& 1& 0\end{array}\right)$$
の行ベクトルが張る ${\mathbb{F}}_2^8$ の部分空間として定める。$C$ の双対符号を
$$C^{\perp }=\{x\in {\mathbb{F}}_2^8\mid \text{すべての }c\in C\text{ に対して }x\cdot c=0\}$$
とする（$x\cdot c$ は ${\mathbb{F}}_2$ 上の標準内積）。$C^{\perp }$ の最小距離を $d$、$C^{\perp }$ に含まれるハミング重み $d$ の符号語の個数を $A$ とするとき、組 $(d,A)$ を求めよ。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上の符号長 $8$ の線形符号 $C$ を、検査行列
$$H=\left(\begin{array}{cccccccc}1& 0& 0& 1& 0& 0& 0& 1\\ 0& 1& 0& 1& 1& 0& 0& 1\\ 0& 1& 1& 0& 0& 0& 1& 1\\ 0& 0& 1& 1& 0& 1& 0& 0\end{array}\right)$$
を用いて $C=\{\mathbf{x}\in {\mathbb{F}}_2^8\mid H{\mathbf{x}}^T=0\}$ で定める。ただし、符号語の重みとは $0$ でない成分の個数であり、$C$ の最小距離 $d$ とは $C$ の $0$ でない符号語の重みの最小値である。$C$ の最小距離 $d$ と、$C$ に含まれる重み $d$ の符号語の個数 $A_d$ を、この順に組 $(d,A_d)$ で求めよ。

3 元体 ${\mathbb{F}}_3=\{0,1,2\}$（演算は $3$ を法とする）上で考える。${\mathbb{F}}_3^3$ の $0$ でないベクトル（列ベクトル）のうち、上から見て最初に現れる $0$ でない成分が $1$ であるものは全部で $13$ 個ある。これら $13$ 個のベクトルをすべて、ある順序で列として並べた $3\times 13$ 行列を $G$ とする。

$G$ を生成行列とする符号長 $13$ の線形符号を
$$C=\{\mathbf{u}G\mid \mathbf{u}\in {\mathbb{F}}_3^3(\text{行ベクトル})\}$$
とし、その双対符号を
$$C^{\perp }=\{\mathbf{y}\in {\mathbb{F}}_3^{13}\mid \mathbf{y}\cdot \mathbf{c}=0\text{がすべての}\mathbf{c}\in C\text{について成り立つ}\}$$
とする（$\mathbf{y}\cdot \mathbf{c}$ は成分ごとの積の和を $3$ を法として計算したもの）。ハミング重みは $0$ でない成分の個数、線形符号の最小距離は $0$ でない符号語のハミング重みの最小値とする。

$C^{\perp }$ の次元 $k^{\perp }$、$C$ の最小距離 $d$、$C^{\perp }$ の最小距離 $d^{\perp }$ を求め、組 $(k^{\perp },d,d^{\perp })$ の形で答えよ。なお、答えは $G$ の列の並べ方によらない。

$q$ を素数べき、${\mathbb{F}}_q$ を $q$ 元体とし、$n,k$ を $1\le k\le n-1$ を満たす整数とする。$C\subset {\mathbb{F}}_q^n$ を $k$ 次元の線形符号とし（${\mathbb{F}}_q^n$ の元は行ベクトルとする）、
- $G$ を $C$ の生成行列、すなわち $C=\{\mathbf{u}G\mid \mathbf{u}\in {\mathbb{F}}_q^k\}$ を満たす階数 $k$ の $k\times n$ 行列、
- $H$ を $C$ の検査行列、すなわち $C=\{\mathbf{c}\in {\mathbb{F}}_q^n\mid H{\mathbf{c}}^{\mathsf{T}}=0\}$ を満たす階数 $n-k$ の $(n-k)\times n$ 行列

とする。語の重みを $0$ でない成分の個数とする。

このとき、次の 2 条件が同値であることを証明せよ。

(A) $G$ のどの $k$ 本の列ベクトルも ${\mathbb{F}}_q$ 上 1 次独立である。

(B) $H$ のどの $n-k$ 本の列ベクトルも ${\mathbb{F}}_q$ 上 1 次独立である。

なお、線形代数の基本事項（次元定理、正方行列が正則であることと列ベクトルが 1 次独立であることの同値性など）は用いてよい。

二元体 ${\mathbb{F}}_2=\{0,1\}$ 上で、次の $4\times 10$ 行列 $H$ を考える。
$$H=\left(\begin{array}{cccccccccc}1& 0& 0& 0& 1& 1& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 1& 1& 0\\ 0& 0& 1& 0& 0& 1& 0& 1& 0& 1\\ 0& 0& 0& 1& 0& 0& 1& 0& 1& 1\end{array}\right)$$
$H$ の列は、${\mathbb{F}}_2^4$ のベクトルのうちハミング重み（$1$ である成分の個数）が $1$ または $2$ であるもの全部（$10$ 個）を $1$ 回ずつ並べたものである。$H$ を検査行列とする符号長 $10$ の二元線形符号
$$C=\{x\in {\mathbb{F}}_2^{10}:H{x}^T=0\}$$
について、$C$ の最小距離を $d$ とし、$C$ に含まれるハミング重み $k$ の符号語の個数を $A_k$ とする。$d,A_d,A_{d+1}$ をこの順に組で求めよ。