線形符号
概要
線形符号（linear code）とは、有限体 $\mathbb F_q$ の上の $n$ 次元数ベクトル空間 $\mathbb F_q^n$ の $k$ 次元部分空間として選んだ誤り訂正符号で、生成行列で符号化し、検査行列で符号語かどうかを判定する。最小距離 $d$ は $0$ でない符号語の重みの最小値に等しく、検査行列のどの $d-1$ 本の列も一次独立で、ある $d$ 本が一次従属になる数として読み取れ、$\lfloor(d-1)/2\rfloor$ 個以下の誤りを訂正できる。復号はシンドロームから剰余類の代表元を引く計算になり、パラメータには Singleton の限界 $d\le n-k+1$ と、存在を保証する Gilbert–Varshamov の限界がある。
雑音のある通信路で $0$ と $1$ の列を送ると、ところどころの文字が化ける。そこで、長さ $n$ の列の全体から送ってよい列（符号語）だけを選んでおき、化けた列を受け取ったら、いちばん近い符号語に直す。選ぶ列の集合が有限体の上のベクトル空間 $\mathbb F_q^n$ の部分空間になっていると、符号は数個の基底や連立一次方程式で書け、符号語どうしの距離は 1 つの行列の列の一次独立性で読み取れ、復号は剰余類の表を引く計算になる。このような符号を 線形符号（linear code）という。
この記事では、線形符号と生成行列・検査行列・双対符号を定義し、最小距離が $0$ でない符号語の重みの最小値であること（prop-lin-minwt）、最小距離が検査行列の列の一次独立性で決まること（thm-lin-columns）、最小距離から訂正できる誤りの個数が決まること（thm-lin-correct）、剰余類の代表元による復号が最も近い符号語を返すこと（thm-lin-coset-decoding）、Singleton の限界（thm-lin-singleton）と Gilbert–Varshamov の限界（thm-lin-gv）を証明する。
定義
Hamming 距離と重み
以下、$q$ は素数冪、$\mathbb F_q$ は位数 $q$ の 有限体、$n\ge1$ とし、$\mathbb F_q^n$ の元を長さ $n$ の 語 という。語 $u=(u_1,\dots,u_n)$ について $u_i\ne0$ となる $i$ の個数を 重み $\operatorname{wt}(u)$、$u_i\ne0$ となる $i$ の集合を 台 $\operatorname{supp}(u)$ という。語 $u,v$ について $u_i\ne v_i$ となる $i$ の個数を Hamming 距離 $d(u,v)$ という。
$d$ は $\mathbb F_q^n$ の上の距離であり、すべての語 $u,v,w$ について $d(u,v)=\operatorname{wt}(u-v)$ と $d(u+w,v+w)=d(u,v)$ が成り立つ。
$u_i\ne v_i$ と $u_i-v_i\ne0$ は同値なので $d(u,v)=\operatorname{wt}(u-v)$ であり、$(u+w)-(v+w)=u-v$ から平行移動で変わらない。$d(u,v)=0$ と $u=v$ は同値で、対称性は定義から明らかである。三角不等式は、$u_i\ne w_i$ なら $u_i\ne v_i$ か $v_i\ne w_i$ の少なくとも一方が成り立つので、$u_i\ne w_i$ となる $i$ の集合が、$u_i\ne v_i$ となる $i$ の集合と $v_i\ne w_i$ となる $i$ の集合の和集合に含まれることから従う。$\square$
線形符号と 2 つの行列
$\mathbb F_q^n$ の $k$ 次元の 線形部分空間 $C$ を、長さ $n$、次元 $k$ の 線形符号 といい、その元を 符号語 という。$k\ge1$ のとき、相異なる 2 つの符号語の Hamming 距離の最小値を $C$ の 最小距離 $d(C)$ といい、$d(C)=d$ のとき $C$ を $[n,k,d]_q$ 符号（$q$ が明らかなら $[n,k,d]$ 符号）という。$k/n$ を $C$ の 情報率 という。
$C$ の元は $q^k$ 個で、$k$ 個の文字の情報を $n$ 文字に引き延ばして送ることに当たる。
$C$ を長さ $n$、次元 $k$ の線形符号とする。行が $C$ の基底をなす $k\times n$ 行列 $G$ を $C$ の 生成行列 という。階数が $n-k$ の $(n-k)\times n$ 行列 $H$ で
$$
C=\{x\in\mathbb F_q^n : Hx^{\mathsf T}=0\}
$$
となるものを $C$ の 検査行列 という。
生成行列を使うと、情報 $m\in\mathbb F_q^k$ を符号語 $mG$ に写す単射の線形写像で符号化できる。検査行列は、受け取った語が符号語かどうかを $n-k$ 本の一次式で判定する。検査行列が必ずあることは次の双対符号から分かる。
$\mathbb F_q^n$ の標準の内積を $u\cdot v=\sum_iu_iv_i$ とし、$C^\perp=\{v\in\mathbb F_q^n : u\cdot v=0\ (u\in C)\}$ を $C$ の 双対符号 という。$C\subset C^\perp$ のとき $C$ は 自己直交、$C=C^\perp$ のとき 自己双対 であるという。
$C$ を長さ $n$、次元 $k$ の線形符号、$G$ をその生成行列とする。
- $C^\perp=\{v : Gv^{\mathsf T}=0\}$ であり、$\dim C^\perp=n-k$、$(C^\perp)^\perp=C$ である。
- $C^\perp$ の生成行列は $C$ の検査行列であり、$C$ の生成行列は $C^\perp$ の検査行列である。
1：$v\in C^\perp$ は、$v$ が $C$ の基底すなわち $G$ の各行と直交することと同値なので $C^\perp=\{v : Gv^{\mathsf T}=0\}$ である。$G$ の階数は $k$ なので、階数定理 により $\dim C^\perp=n-k$ である。$C$ の元は $C^\perp$ のどの元とも直交するので $C\subset(C^\perp)^\perp$ で、右辺の次元は同じ理由で $n-(n-k)=k$ だから等号が成り立つ。
2：$C^\perp$ の生成行列 $H$ は階数 $n-k$ の $(n-k)\times n$ 行列で、1 を $C^\perp$ に当てはめると $\{x : Hx^{\mathsf T}=0\}=(C^\perp)^\perp=C$ である。よって $H$ は $C$ の検査行列である。後半は 1 の $C^\perp=\{v : Gv^{\mathsf T}=0\}$ と $G$ の階数が $k=n-(n-k)$ であることから従う。$\square$
実数の上の内積と違い、$\mathbb F_q$ の上では $0$ でない語が自分自身と直交することがある。例えば $\mathbb F_2^2$ の $(1,1)$ は $(1,1)\cdot(1,1)=0$ を満たし、$C=\{00,11\}$ は自己双対である。したがって $C\cap C^\perp=\{0\}$ とは限らず、直交補空間 のような直和分解は一般には成り立たない。それでも 1 の次元の式は成り立つ。
$C$ が生成行列 $G=(I_k\mid A)$（$A$ は $k\times(n-k)$ 行列）をもつなら、$H=(-A^{\mathsf T}\mid I_{n-k})$ は $C$ の検査行列である。
$GH^{\mathsf T}=I_k(-A)+AI_{n-k}=0$ なので、$G$ の各行 $g$ は $Hg^{\mathsf T}=0$ を満たし、$C\subset\{x:Hx^{\mathsf T}=0\}$ である。$H$ は $I_{n-k}$ を含むので階数 $n-k$ で、右辺の次元は $k$ だから等号が成り立つ。$\square$
どの線形符号も、生成行列を掃き出して既約な階段行列にし、座標の並べ替えで先頭の $1$ のある列を左に集めれば、生成行列が $(I_k\mid A)$ の形の符号に移る。座標の並べ替え（と各座標の $0$ でない定数倍）で移り合う 2 つの符号は Hamming 距離を保つ全単射で結ばれるので、最小距離などの性質を調べるときは同じものとみなしてよい。
最小距離
$C$ を次元 $k\ge1$ の線形符号とすると、$d(C)=\min\{\operatorname{wt}(c): c\in C,\ c\ne0\}$ である。
相異なる符号語 $c,c'$ について $c-c'$ は $0$ でない符号語で、lem-lin-metric により $d(c,c')=\operatorname{wt}(c-c')$ である。逆に $0$ でない符号語 $c$ の重みは $d(c,0)$ で、$0\in C$ である。よって両辺の最小値をとる集合は一致する。$\square$
二元の場合は Jud25 Theorem 8.2.3（p. 145）にある。この性質のおかげで、最小距離を求めるには $\binom{q^k}2$ 組の距離ではなく $q^k-1$ 個の重みを見ればよい。次の定理は、それを検査行列の列の言葉に言い換える。
$C$ を次元 $k\ge1$ の線形符号、$H$ をその検査行列とし、$H$ の第 $j$ 列を $h_j$ とする。$1\le s\le n$ について、次は同値である。
- $C$ の $0$ でない符号語の重みはすべて $s$ 以上である。
- $h_1,\dots,h_n$ のうちのどの $s-1$ 本も一次独立である（相異なる番号の列を選ぶ）。
したがって $d(C)$ は、一次従属になる列の組（相異なる番号の列の組）の本数の最小値に等しい。
語 $x$ について $Hx^{\mathsf T}=\sum_{j=1}^nx_jh_j$ だから、$x\in C$ であることと $\sum_{j\in\operatorname{supp}(x)}x_jh_j=0$ は同値である。
1 ならば 2：ある $s-1$ 本 $h_{j_1},\dots,h_{j_{s-1}}$ が一次従属なら、少なくとも 1 つは $0$ でない係数 $a_1,\dots,a_{s-1}$ で $\sum_ia_ih_{j_i}=0$ となる。第 $j_i$ 座標が $a_i$ でほかが $0$ の語 $x$ は $0$ でない符号語で、重みは $s-1$ 以下であり、1 に反する。
2 ならば 1：重み $w$ の $0$ でない符号語 $x$ があれば、$\operatorname{supp}(x)$ の $w$ 本の列は、係数 $x_j\ne0$ の一次関係 $\sum_{j\in\operatorname{supp}(x)}x_jh_j=0$ をもち一次従属である。$w\le s-1$ なら、これに列を足した $s-1$ 本も一次従属になり 2 に反するので、$w\ge s$ である。
最後の主張は、prop-lin-minwt により $d(C)$ が 1 を満たす最大の $s$ であり、2 を満たす最大の $s$ は一次従属な組の本数の最小値であることから従う（$C\ne0$ なので一次従属な組はある）。$\square$
二元で $d\ge2$、$d\ge3$ の場合（$H$ に零の列がない、同じ列がない）は Jud25 Theorem 8.3.9・8.3.12（pp. 151–152）にある。とくに、$d(C)\ge3$ であることと、$H$ の列がどれも $0$ でなく、どの 2 本も互いの定数倍でないことは同値 である。この条件を満たす列をできるだけ多く並べた符号が Hamming符号 である。
誤りの訂正と検出
符号語 $c$ を送って語 $r$ を受け取ったとき、$e=r-c$ を 誤り、$\operatorname{wt}(e)=d(r,c)$ を化けた文字の個数という。次の定理は線形性を使わないので、$\mathbb F_q^n$ の任意の部分集合（2 元以上）について、最小距離を相異なる 2 元の距離の最小値として成り立つ。
$C$ の最小距離を $d$ とし、$t=\lfloor(d-1)/2\rfloor$ とおく。
- 符号語 $c$ と、$1\le d(r,c)\le d-1$ を満たす語 $r$ について、$r$ は符号語でない（$d-1$ 個以下の誤りは検出できる）。
- 符号語 $c$ と、$d(r,c)\le t$ を満たす語 $r$ について、$c$ は $r$ からの距離が最小の唯一の符号語である（$t$ 個以下の誤りは訂正できる）。
- $d(c,c')=d$ となる符号語 $c,c'$ について、$d(r,c)=t+1$ かつ $d(r,c')\le t+1$ となる語 $r$ がある（2 は $t+1$ 個の誤りでは成り立たない）。
1：$r$ が符号語なら、$r\ne c$ と $d(r,c)\le d-1$ が最小距離の定義に反する。
2：$c'\ne c$ を符号語とすると、三角不等式から $d(r,c')\ge d(c,c')-d(r,c)\ge d-t$ で、$2t\le d-1$ より $d-t\ge t+1>d(r,c)$ である。
3：$c$ と $c'$ が異なる座標の集合 $D$（$\lvert D\rvert=d$）から $t+1$ 個を選んで $D'$ とする（$t+1\le d$ である）。$D'$ の座標では $c'$ と同じ、ほかの座標では $c$ と同じ語を $r$ とすると、$d(r,c)=t+1$、$d(r,c')=d-t-1$ である。$d\le2t+2$ なので $d(r,c')\le t+1$ である。$\square$
シンドローム復号
最も近い符号語を探すのに $q^k$ 個の符号語をすべて調べるのは重い。線形符号では、検査行列で受け取った語を $n-k$ 文字に縮めてから表を引けば済む。$C$ を長さ $n$、次元 $k$ の線形符号、$H$ をその検査行列とし、語 $r$ の シンドローム を $s(r)=Hr^{\mathsf T}\in\mathbb F_q^{n-k}$ と定める。
$s$ は線形写像で、核は検査行列の定義により $C$ である。よって $s(r)=s(r')$ と $r-r'\in C$ すなわち $r+C=r'+C$ は同値で、写像は well-defined かつ単射である。$H$ の階数は $n-k$ なので $s$ は全射である。$\square$
各剰余類で重みが最小の元を 1 つ選び、その剰余類の 代表元（coset leader）という。prop-lin-syndrome により、代表元の表はシンドロームから引ける。
シンドローム $\sigma\in\mathbb F_q^{n-k}$ ごとに、$s(e)=\sigma$ となる剰余類の代表元 $e_\sigma$ を 1 つ選び、受け取った語 $r$ を $D(r)=r-e_{s(r)}$ に写す。
- $D(r)$ は符号語であり、$r$ からの距離が最小の符号語の 1 つである。
- 最小距離を $d$、$t=\lfloor(d-1)/2\rfloor$ とする。符号語 $c$ と重み $t$ 以下の誤り $e$ について $D(c+e)=c$ である。
1：$s(r-e_{s(r)})=s(r)-s(r)=0$ なので $D(r)\in C$ である。任意の符号語 $c$ について $r-c$ は $r$ と同じ剰余類に入るから、代表元の選び方より $d(r,c)=\operatorname{wt}(r-c)\ge\operatorname{wt}(e_{s(r)})=d(r,D(r))$ である。
2：$r=c+e$ の剰余類は $e+C$ である。この剰余類の重み $t$ 以下の元は $e$ だけである。実際、$e'\ne e$ も重み $t$ 以下なら $e-e'$ は $0$ でない符号語で $\operatorname{wt}(e-e')\le2t< d$ となり、prop-lin-minwt に反する。代表元は重みが最小なので $\operatorname{wt}(e_{s(r)})\le\operatorname{wt}(e)\le t$ で、したがって $e_{s(r)}=e$、$D(r)=c$ である。$\square$
二元の場合のシンドロームと代表元の表による復号は Jud25 §8.4（Proposition 8.4.9、p. 154）にある。
$\mathbb F_2$ の上で
$$
G=\begin{pmatrix}1&0&0&0&1&1\\0&1&0&1&0&1\\0&0&1&1&1&0\end{pmatrix},\qquad
H=\begin{pmatrix}0&1&1&1&0&0\\1&0&1&0&1&0\\1&1&0&0&0&1\end{pmatrix}
$$
とする。$G=(I_3\mid A)$ で、prop-lin-standard の $H=(A^{\mathsf T}\mid I_3)$ になっている（$\mathbb F_2$ では $-1=1$）。$H$ の 6 本の列は相異なる $0$ でない列で、第 1・5・6 列の和は $0$ なので、thm-lin-columns により $C$ は $[6,3,3]$ 符号である。
符号語 $c=(1,1,0,1,1,0)$（$G$ の第 1 行と第 2 行の和）を送り、第 3 座標が化けて $r=(1,1,1,1,1,0)$ を受け取ったとする。$s(r)=(1,1,0)^{\mathsf T}$ は $H$ の第 3 列なので、代表元は第 3 座標だけが $1$ の語で、$D(r)=(1,1,0,1,1,0)=c$ と正しく直る。
シンドロームは $2^3=8$ 個あり、$0$ と 6 本の列には重み $0,1$ の代表元が 1 つずつ対応する。残る $(1,1,1)^{\mathsf T}$ の剰余類には重み $1$ の元がなく、重み $2$ の元が 3 つ（第 1・4、第 2・5、第 3・6 座標が $1$ の語）あって、代表元は一意に決まらない。この剰余類の語は、どの符号語からも距離 $2$ 以上離れている。
最後の現象は、符号語を中心とする半径 $1$ の球が空間を埋め尽くしていないことを表す。埋め尽くす符号が 完全符号 で、そのときはすべての剰余類が重み $t$ 以下の元をちょうど 1 つ含む。
符号語の個数の限界
$[n,k,d]_q$ 符号について $d\le n-k+1$ が成り立つ。
$k=n$ なら $C=\mathbb F_q^n$ で $d=1$ である。$k< n$ なら、検査行列 $H$ の列は $\mathbb F_q^{n-k}$ の元なので、どの $n-k+1$ 本も一次従属である。thm-lin-columns により $d\le n-k+1$ である。$\square$
等号 $d=n-k+1$ を満たす符号を MDS 符号（maximum distance separable code）という。
$a_1,\dots,a_n$ を $\mathbb F_q$ の相異なる元（したがって $n\le q$）、$1\le k\le n$ とし、次数 $k-1$ 以下の多項式 $f\in\mathbb F_q[x]$ の値の列 $(f(a_1),\dots,f(a_n))$ の全体を $C$ とする。$C$ は線形で、$f\ne0$ の根は $k-1$ 個以下なので、値の列の重みは $n-k+1$ 以上である。とくに $f\mapsto(f(a_i))_i$ は単射で $\dim C=k$ であり、$C$ は $[n,k,n-k+1]_q$ 符号、すなわち MDS 符号である。$k$ 個の点での値から $f$ を復元する式が Lagrange補間 である。例えば $q=5$、$a_i=0,1,2,3,4$、$k=2$ とすると、$1$ 次以下の多項式の値の列からなる $[5,2,4]_5$ 符号が得られる。
符号語を中心とする半径 $t=\lfloor(d-1)/2\rfloor$ の球が互いに交わらないことから、Hamming の限界 $q^k\sum_{i=0}^t\binom ni(q-1)^i\le q^n$ も成り立つ（証明と等号の場合は 完全符号）。どちらも上からの限界である。逆に、よい線形符号が存在することは次の構成で保証される。
$2\le d\le n$、$1\le k\le n-1$ とし、$V_q(m,s)=\sum_{i=0}^s\binom mi(q-1)^i$ とおく。
$$
V_q(n-1,d-2)< q^{n-k}
$$
ならば、最小距離が $d$ 以上の長さ $n$、次元 $k$ の線形符号が存在する。
$\mathbb F_q^{n-k}$ の元 $h_1,\dots,h_n$ を、どの $d-1$ 本も一次独立になるように順に選ぶ。
証明を開く
$h_1,\dots,h_{j-1}$（$j\le n$）を選んだとき、そのうちの $d-2$ 本以下の一次結合として書ける元は、$i$ 本（$0\le i\le d-2$）の選び方と $0$ でない係数を数えて高々 $V_q(j-1,d-2)\le V_q(n-1,d-2)< q^{n-k}$ 個なので、そのどれでもない $h_j$ をとる。こうして選んだ列のうち $d-1$ 本以下が一次従属だったとすると、$0$ でない係数をもつ列のうち番号が最大の $h_j$ は、番号の小さい $d-2$ 本以下の一次結合になり、$h_j$ の選び方に反する。
$h_j$ を列とする $(n-k)\times n$ 行列を $H$ とし、$C'=\{x:Hx^{\mathsf T}=0\}$ とおく。$H$ の階数は $n-k$ 以下なので $\dim C'\ge k\ge1$ で、thm-lin-columns の 2 ならば 1（この向きには $H$ の階数を使わない）により $C'$ の $0$ でない元の重みは $d$ 以上である。$C'$ の $k$ 次元の部分空間 $C$ をとれば、$C$ の $0$ でない元も $C'$ の元なので、prop-lin-minwt により $d(C)\ge d$ である。$\square$
Mac03 §13.5（pp. 211–212）は、検査行列の成分を一様に無作為に選んだ二元の線形符号について重みの分布の期待値を計算し、長さが大きいとき最小距離が典型的にこの限界の与える距離（Gilbert–Varshamov 距離）に近いことを説明している。
例
| 符号 | パラメータ | 生成行列・検査行列 | 性質 |
|---|---|---|---|
| 反復符号 | $[n,1,n]_q$ | 生成行列 $(1,1,\dots,1)$ | MDS。$n$ が奇数の二元の場合は 完全符号 |
| パリティ検査符号 | $[n,n-1,2]_q$ | 検査行列 $(1,1,\dots,1)$ | MDS。二元では反復符号の双対符号 |
| Hamming 符号 | $[7,4,3]_2$ ほか | 検査行列の列が各 $1$ 次元部分空間の代表（二元では $0$ でない列すべて） | Hamming符号、完全符号 |
| 二元 Golay 符号 | $[23,12,7]_2$ | 正二十面体から作る | Golay符号、完全符号 |
| Reed–Solomon 符号 | $[n,k,n-k+1]_q$ | 多項式の値の列 | ex-lin-rs、MDS |
反復符号とパリティ検査符号の最小距離は thm-lin-columns で読める。パリティ検査符号の検査行列 $(1,\dots,1)$ の列はどれも $0$ でなく、どの 2 本も一次従属なので $d=2$ である。反復符号の検査行列は $(n-1)\times n$ 行列 $(\mathbf 1\mid-I_{n-1})$（$\mathbf 1$ はすべての成分が $1$ の列）で、どの $n-1$ 本も一次独立なので $d=n$ である。実際、第 1 列以外の $n-1$ 本は $-I_{n-1}$ の列であり、第 1 列と $-I_{n-1}$ の $n-2$ 本の組では、選ばなかった列 $-e_m$ に当たる第 $m$ 行を見ると、一次関係の第 1 列の係数が $0$ になり、残りの係数も $0$ になる。
反例
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 線形であること（prop-lin-minwt） | $\mathbb F_2^3$ の部分集合 $\{000,011,111\}$ | 最小距離が $0$ でない元の重みの最小値に等しい |
| $d\ge2t+1$（thm-lin-correct の 2、$t=1$） | パリティ検査符号 $[3,2,2]_2$ で $000$ を送り $100$ を受け取る | 最も近い符号語が一意で、送った符号語に等しい |
| $V_q(n-1,d-2)< q^{n-k}$（thm-lin-gv） | $q=2$、$n=3$、$k=2$、$d=3$ | 最小距離 $d$ 以上の線形符号の存在 |
1 行目：$d(011,111)=1$ だが、$0$ でない元の重みは $2$ と $3$ である。この集合は $011+111=100$ を含まないので線形でない。2 行目：$100$ からの距離は $000$、$110$、$101$ のどれも $1$ で、最も近い符号語が 3 つある。3 行目：$V_2(2,1)=3\ge2=2^{3-2}$ で仮定が成り立たず、実際 thm-lin-singleton により $[3,2,d]$ 符号は $d\le2$ である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
