§D3.21線形符号と誤り訂正

証明. 1について。$G\vec c = \sum_{i} c_i \vec b_i$であるから、$\operatorname{Im}G$は$\vec b_1, \dots, \vec b_k$が張る空間、すなわち$C$である。また$G\vec c = \vec 0$は$\sum_i c_i\vec b_i = \vec 0$であり、基底の一次独立性から$\vec c = \vec 0$である。

2について。$C$の基底$\vec b_1, \dots, \vec b_k$を取り、§D3.11 補題 1.2により$\mathbb{F}_2^n$の基底$\vec b_1, \dots, \vec b_n$へ延長する。この補題は§D3.20 命題 3.2の3により$\mathbb{F}_2$の上でも成り立つ。§D3.8 命題 2.3より、各$\vec x \in \mathbb{F}_2^n$は$\vec x = \sum_{i=1}^{n} c_i(\vec x)\,\vec b_i$とただ一通りに書くことができる。写像

を定める。$\vec x + \vec y$と$a\vec x$の座標は、表し方の一意性から$c_i(\vec x) + c_i(\vec y)$と$a\,c_i(\vec x)$に等しいので、$\pi$は線形写像である。$\pi(\vec b_{k+j})$は$\mathbb{F}_2^{n-k}$の第$j$標準基底ベクトルであるから$\pi$は全射である。また$\pi(\vec x) = \vec 0$は$\vec x = \sum_{i\le k}c_i(\vec x)\vec b_i$と同値であり、これは$\vec x \in C$と同値であるから$\operatorname{Ker}\pi = C$である。$H$を、$\mathbb{F}_2^n$と$\mathbb{F}_2^{n-k}$の標準基底に関する$\pi$の表現行列（§D3.9 定理 2.2）とすると、すべての$\vec x$について$H\vec x = \pi(\vec x)$であるから、$\operatorname{Ker}H = C$かつ$\operatorname{Im}H = \mathbb{F}_2^{n-k}$である。$H$は$(n-k)\times n$行列である。

3について。検査行列の定義そのものである。▨

証明. 1と2は、個数が$0$以上であることと、$x_i \ne y_i$という条件が$\vec x$と$\vec y$について対称であることによる。

3を示す。$x_i \ne z_i$を満たす添字$i$を取る。$x_i = y_i$かつ$y_i = z_i$とすると$x_i = z_i$となって矛盾するから、$x_i \ne y_i$または$y_i \ne z_i$である。したがって、$x_i \ne z_i$を満たす添字の集合は、$x_i \ne y_i$を満たす添字の集合と$y_i \ne z_i$を満たす添字の集合の和集合に含まれる。集合の要素の個数を比べて3を得る。

4を示す。$\mathbb{F}_2$では$x_i \ne y_i$と$x_i - y_i \ne 0$が同値であるから、両辺は同じ添字の個数を数えている。▨

証明. 右辺を$\mu$と書く。$C$には$\vec 0$でない要素があるから$\mu$は定まる。

$d(C) \le \mu$を示す。$w(\vec c) = \mu$を満たす$\vec c \in C$、$\vec c \ne \vec 0$を取ると、命題 2.2の4により$d(\vec c, \vec 0) = w(\vec c) = \mu$であり、$\vec 0 \in C$、$\vec c \ne \vec 0$であるから$d(C) \le \mu$である。

$\mu \le d(C)$を示す。$d(\vec c, \vec c') = d(C)$を満たす相異なる符号語$\vec c, \vec c'$を取る。$C$は部分空間であるから$\vec c - \vec c' \in C$であり、$\vec c \ne \vec c'$より$\vec c - \vec c' \ne \vec 0$である。命題 2.2の4により$w(\vec c - \vec c') = d(\vec c, \vec c') = d(C)$であるから$\mu \le d(C)$である。▨

証明. 1の十分性を示す。$\delta \ge 2t+1$とする。$\vec c \in C$、$w(\vec e) \le t$とし$\vec y = \vec c + \vec e$とおく。命題 2.2の4により$d(\vec y, \vec c) = w(\vec e) \le t$である。$\vec c' \in C$、$\vec c' \ne \vec c$とすると、同命題の3により

であるから$d(\vec y, \vec c') \ge \delta - t \ge (2t+1) - t = t+1 > t \ge d(\vec y, \vec c)$である。よって$\vec c$は$\vec y$の最近符号語であり、他のどの符号語も$\vec y$との距離が真に大きいから、最近符号語は$\vec c$ただ一つである。

1の必要性を、対偶によって示す。$\delta \le 2t$とする。$d(\vec c_1, \vec c_2) = \delta$を満たす相異なる符号語$\vec c_1, \vec c_2$を取り、$S$を$\vec c_1$と$\vec c_2$の成分が異なる添字の集合とする。$|S| = \delta$である。$\delta \le 2t$と$t$が整数であることから$\lceil \delta/2\rceil \le t$である。$S$の部分集合$T$で$|T| = \lceil \delta/2\rceil$を満たすものを一つ取り、$\vec y$を、$T$に属する添字では$\vec c_2$の成分に等しく、それ以外の添字では$\vec c_1$の成分に等しいベクトルとする。このとき

である。$\vec e = \vec y - \vec c_1$とおくと$w(\vec e) = \lceil\delta/2\rceil \le t$であり、$\vec y = \vec c_1 + \vec e$である。ところが$d(\vec y, \vec c_2) = \lfloor\delta/2\rfloor \le \lceil\delta/2\rceil = d(\vec y, \vec c_1)$であり、$\vec c_2 \ne \vec c_1$であるから、$\vec y$の最近符号語は$\vec c_1$ただ一つではない。よって$C$は$t$個以下の誤りを訂正することができない。

2の十分性を示す。$\delta \ge s+1$とする。$\vec c \in C$、$1 \le w(\vec e) \le s$とし、$\vec c + \vec e \in C$と仮定する。$C$は部分空間であるから$\vec e = (\vec c + \vec e) - \vec c \in C$であり、$w(\vec e) \ge 1$より$\vec e \ne \vec 0$である。命題 2.3により$w(\vec e) \ge \delta \ge s+1$となり、$w(\vec e) \le s$に矛盾する。よって$\vec c + \vec e \notin C$である。

2の必要性を、対偶によって示す。$\delta \le s$とする。命題 2.3により$w(\vec e) = \delta$を満たす$\vec e \in C$、$\vec e \ne \vec 0$が存在する。$\vec c = \vec 0 \in C$とすると$1 \le w(\vec e) = \delta \le s$であり、$\vec c + \vec e = \vec e \in C$であるから、$C$は$s$個以下の誤りを検出することができない。▨

証明.$\vec x \in \mathbb{F}_2^n$に対し、$x_j = 1$を満たす添字$j$の集合を$S(\vec x)$と書くと、$\mathbb{F}_2$の成分は$0$か$1$であるから$H\vec x = \sum_{j \in S(\vec x)} \vec h_j$である。したがって、重みが$w$である$0$でない符号語が存在することと、$H$の相異なる$w$本の列で和が$\vec 0$になるものが存在することは同値である。

また、$\mathbb{F}_2$の上では、相異なる列の組$\vec h_{j_1}, \dots, \vec h_{j_m}$が一次従属であることと、その中の空でない部分の和が$\vec 0$になることは同値である。実際、一次関係$\sum_{i} c_i \vec h_{j_i} = \vec 0$で係数がすべて$0$ではないものを取ると、各$c_i$は$0$か$1$であるから、$c_i = 1$となる添字だけを集めた空でない部分の和が$\vec 0$になる。逆も同様である。

以上より、$d(C) \le \delta - 1$であること、すなわち命題 2.3により重みが$\delta - 1$以下の$0$でない符号語が存在することは、$H$の相異なる$\delta-1$本以下の列で一次従属になるものが存在することと同値である。$\delta - 1$本より少ない本数の従属な組は、列を付け加えても従属のままであり、$H$の列は$n \ge \delta - 1$本あるから、これは「$H$の相異なる$\delta-1$本の列で一次従属になるものが存在する」ことと同値である。対偶を取れば主張を得る。▨

証明. 1について。$\mathbb{F}_2^r$の標準基底ベクトルはいずれも$\vec 0$でないから、$H$の列として現れる。したがって$\operatorname{Im}H$は$\mathbb{F}_2^r$の標準基底を含む部分空間であり、$\operatorname{Im}H = \mathbb{F}_2^r$、$\dim \operatorname{Im}H = r$である。§D3.11 定理 2.1より$\dim C_r = \dim\operatorname{Ker}H = n - r$である。$r \ge 2$のとき$n - r = 2^r-1-r \ge 1$であるから、$C_r$には$\vec 0$でない符号語があり、最小距離が定まる。

2について。まず$d(C_r) \ge 3$を示す。$H$の相異なる$2$本の列$\vec h_i, \vec h_j$（$i \ne j$）を取る。$c_1\vec h_i + c_2\vec h_j = \vec 0$とする。$c_1 = 1$、$c_2 = 0$とすると$\vec h_i = \vec 0$となって矛盾し、$c_1 = 0$、$c_2 = 1$の場合も同様である。$c_1 = c_2 = 1$とすると$\vec h_i = -\vec h_j = \vec h_j$となり、列が互いに異なることに反する。よって$c_1 = c_2 = 0$であり、$2$本の列は一次独立である。命題 2.7を$\delta = 3$として適用すると$d(C_r) \ge 3$を得る。

次に$d(C_r) \le 3$を示す。$r \ge 2$であるから、$\mathbb{F}_2^r$には相異なる$\vec 0$でないベクトル$\vec u, \vec v$が存在する。$\vec u + \vec v = \vec 0$とすると$\vec u = \vec v$となって矛盾するから$\vec u + \vec v \ne \vec 0$であり、$\vec u + \vec v$も$H$の列として現れる。$\vec u + \vec v = \vec u$とすると$\vec v = \vec 0$となって矛盾し、$\vec u + \vec v = \vec v$の場合も同様であるから、$\vec u$、$\vec v$、$\vec u+\vec v$は互いに異なる$3$本の列である。これらの和は$\vec u + \vec v + (\vec u+\vec v) = \vec 0$である。この$3$本に対応する添字だけが$1$であるベクトル$\vec x$を取ると、$H\vec x = \vec 0$であるから$\vec x \in C_r$であり、$w(\vec x) = 3$である。命題 2.3より$d(C_r) \le 3$である。以上より$d(C_r) = 3$である。

3について。$d(C_r) = 3 = 2\cdot 1 + 1$であるから定理 2.5の1により$1$個以下の誤りを訂正することができ、$3 = 2 + 1$であるから同定理の2により$2$個以下の誤りを検出することができる。▨

証明.$H\vec c = \vec 0$であるから$H\vec y = H\vec e$である。$w(\vec e) \le 1$であるから、$\vec e = \vec 0$であるか、ある$j$について$\vec e = \vec e_j$であるかのいずれかである。

$\vec e = \vec 0$のとき$H\vec y = \vec 0$である。$\vec e = \vec e_j$のとき$H\vec y = H\vec e_j = \vec h_j \ne \vec 0$である。よって$H\vec y = \vec 0$と$\vec e = \vec 0$は同値であり、1が従う。

$H\vec y \ne \vec 0$のときは$\vec e = \vec e_j$であり$H\vec y = \vec h_j$である。定義 3.1により$\vec h_j$は$j$の$2$進表示であるから、$H\vec y$を$2$進表示と読んで得られる整数が$j$に等しい。$\vec y - \vec e_j = \vec c$であり、$\mathbb{F}_2$では$-1 = 1$であるから、第$j$成分を反対の値に変える操作が$\vec e_j$を引く操作である。▨

証明. 互いに交わらないことを示す。$\vec y \in B(\vec c) \cap B(\vec c')$、$\vec c \ne \vec c'$とすると、命題 2.2の3により$d(\vec c, \vec c') \le d(\vec c, \vec y) + d(\vec y, \vec c') \le 2$となり、定理 3.2の2の$d(C_r) = 3$に反する。

要素の個数を数える。$|B(\vec c)| = 1 + n$である。$\vec c$自身と、$n$個の成分のうち一つだけを変えたものが該当するからである。符号語は定理 3.2の1と定義 1.1の直後の計算により$2^{n-r}$個ある。互いに交わらないから、和集合の要素の個数は

である。$|\mathbb{F}_2^n| = 2^n$であり、和集合は$\mathbb{F}_2^n$に含まれるから、両者は一致する。▨