この記事は誤り訂正符号の一つであるリード・ソロモン符号についての講義ノートをもとにした覚書です。詳しい説明は書籍などを当たることを推奨します (例題が語る符号理論 ― 池田 和興 著 (共立出版) は内容が詳細に記述されているためよさそうでした)。
この記事では慣例に倣いベクトル $\boldsymbol{x}$ を横ベクトル $[x_1, x_2 \ldots, x_n]$ として扱います。
線形符号
まず $q$ 元体上の $n$ 次元ベクトル空間 $\mathbb{F}_q^n := \{ \boldsymbol{x} = (x_1, \ldots, x_n) \mid x_i \in \mathbb{F}_q \}$ を考えると、$\mathbb{F}_q^n$ 上には内積 $\langle \boldsymbol{x}, \boldsymbol{y} \rangle = \boldsymbol{x} \cdot \boldsymbol{y}^\intercal$ が定義できます。このベクトル空間 $\mathbb{F}_q^n$ の部分空間 $C \subset \mathbb{F}_q^n$ を線形符号といいます (ただし $k = \dim C < n$ とします)。
符号 $C$ の基底 ${\boldsymbol{c}_1, \boldsymbol{c}_2, \ldots, \boldsymbol{c}_k}$ を取ると、$k \times n$ 行列次のような $G$ が得られます。これを $C$ の生成行列といい、$\cdot G: \mathbb{F}_q^n \rightarrow C$ です。
G=
\begin{pmatrix}
\boldsymbol{c}_1 \\
\boldsymbol{c}_2 \\
\vdots \\
\boldsymbol{c}_k
\end{pmatrix}
$C$ の直交補空間 $C^\perp := \{ \boldsymbol{x} \in \mathbb{F}_q^n \mid\ \langle \boldsymbol{x}, \boldsymbol{c} = 0 \rangle, \forall \boldsymbol{c} \in C \}$ を双対符号といい、 $C^\perp$ の生成行列 $H$ を検査符号といいます。ここで $\dim C^\perp = n - \mathrm{rank} G = n - k$ です。
定義より、$C = \mathrm{Im} G = \mathrm{Ker} H^\intercal$ です。つまり $G$ は $\mathbb{F}_q^n$ 上のベクトルを $C$ に写し、すべての $\boldsymbol{x} \in C$ に対して $\boldsymbol{x} \cdot H^\intercal = \boldsymbol{0}$ です。
符号距離
2 つの符号語の間の距離の 1 つとしてハミング距離 $d(\boldsymbol{x}, \boldsymbol{x}')$ があります。これはベクトルの各要素のうち異なるものを数えるもので、具体的には次のように定義されます ($\#$ は集合の要素数を返す演算子です)。
\begin{array}{rcl}
d(\boldsymbol{x}, \boldsymbol{0}) &:=& \#\{ i \in \{1, \ldots, n\} \mid \boldsymbol{x}_i \ne 0 \} \\
d(\boldsymbol{x}, \boldsymbol{x}') &=& d(\boldsymbol{x} - \boldsymbol{x}', \boldsymbol{0})
\end{array}
例えば 0, 0, 1, 0, 1 と 1, 0, 1, 1, 1 の距離は $2$ です。
ある符号の相異なる 2 つの符号語を取ったときの最小距離を最小符号距離 $d(C)$といいます。これは検査行列 $H$ に存在する従属な列の数 $n - \mathrm{rank} H$ に一致します。
d(C) = \min \{ d(\boldsymbol{x}, \boldsymbol{x}') \mid \boldsymbol{x}, \boldsymbol{x}' \in C, \boldsymbol{x} \ne \boldsymbol{x}' \}
誤り検出訂正能力
実際にデータを通信路を用いて送る際にはノイズなどの誤りが加わります。例えば 0 と 1 を送信できる通信路ではビットが反転する可能性があります。この節では 0 と 1 に限らずあるデータ (ベクトル) の要素の値が変わることを誤りの発生とします。
$C = \mathrm{Ker} H^\intercal$ であるため、符号語 $\boldsymbol{x}$ に誤り $\boldsymbol{e}$ が加わったもの $\boldsymbol{x} + \boldsymbol{e}$ に対し $(\boldsymbol{x} + \boldsymbol{e}) \cdot H = \boldsymbol{0}$ かどうかを確かめることで誤りの存在 ($\boldsymbol{e} = \boldsymbol{0}$ かどうか) を判定することができます。実際にどの程度の誤りを検出・訂正できるかの境界は次のようになっています。
- 誤り検出: $d(\boldsymbol{e}, \boldsymbol{0}) < d(C)$ であれば $H$ により誤りが存在するかどうかが判定できる
- 誤り訂正: $d(\boldsymbol{e}, \boldsymbol{0}) < (d(C) - 1)/2$ であれば $(\boldsymbol{x} + \boldsymbol{e})$ に対し最も近い $C$ の元 $\boldsymbol{x}$ を選ぶことで誤りを正しく訂正できる
このことから $d(C)$ が大きければ大きいほど誤り検出・訂正能力において優れた符号であると言えます。しかし $d(C)$ は無尽蔵に大きくできるわけではなく、次のような限界があることが知られています。
d(C) \le n - k + 1
これを Singleton 限界 といいます。ここで $n$ は符号を定義するベクトル空間の次元であり、$k$ はその部分空間である符号の次元です。$d(C) = n - k + 1$ である符号 $C$ を最適符号といいます。リード・ソロモン符号はその一種です。
誤り訂正の方法
双対符号 $C^\perp \ \mathrm{Im} H$ の基底 $\boldsymbol{b}_i$ を用いて、$H$ は次のように表されます。
G=
\begin{pmatrix}
\boldsymbol{b}_1 \\
\boldsymbol{b}_2 \\
\vdots \\
\boldsymbol{b}_{n-k}
\end{pmatrix}
したがって
\begin{array}{rcl}
(\boldsymbol{x} + \boldsymbol{e}) \cdot H^\intercal
&=& \boldsymbol{e} \cdot H^\intercal \\
&=& \boldsymbol{e} \cdot \boldsymbol{b}_1^\intercal + \boldsymbol{e} \cdot \boldsymbol{b}_2^\intercal + \cdot + \boldsymbol{e} \cdot \boldsymbol{b}_{n - k}^\intercal
\end{array}
となりますが、各 $\boldsymbol{b}_i$ は直交のためどの $\boldsymbol{b}_i$ と内積を取った時に $0$ でなくなるかを見ることで、すなわち $(\boldsymbol{x} + \boldsymbol{e}) \cdot H^\intercal$ の非ゼロ要素の位置を見ることで誤りを特定できます。$\boldsymbol{e}$ が特定できたら $(\boldsymbol{x} + \boldsymbol{e}) - \boldsymbol{e}$ により誤りを訂正できます。
巡回符号
線形符号のうち符号語 $\boldsymbol{c} = [c_1, c_2, \ldots, c_n] \in C$ を巡回シフトした $c' = [c_n, c_1, \ldots, c_{n-1}]$ が $C$ の元である場合、 $C$ を巡回符号といいます。
巡回符号は $q$ 元体上の剰余環によって定義されます。剰余環
R := \mathbb{F}_q[x]/(x^n-1)
= \left\{ \overline{c_0 + c_1x \cdots + c_{n-1}x^{n-1}} \;\middle|\; c_i \in \mathbb{F}_q \right\}
を考えると、$\mathbb{F}_q$ 上のベクトル空間としての $R$ は $n$ 次元で、基底として ${ 1, \overline{x}, \ldots, \overline{x}^{n-1} }$ がとれる。このベクトル空間は線形符号を定義したベクトル空間 $\mathbb{F}_q^n$ と同一視することができます。すなわち次のような同型写像が存在します。
\phi: \mathbb{F}_q^n \rightarrow R; \boldsymbol{c} = [c_0, c_1, \ldots, c_{n-1}] \mapsto \overline{c_0 + c_1x + \cdots + c_{n-1}x^{n-1}}
ここで $\mathbb{F}_q$ における分解 $x^n-1 = g(x)h(x)$ を選び、$\deg g(x) = n-k, \deg h(x) = k$ とします。このとき
\tilde{C} := \overline{g(x)}R = \left\{ \overline{g(x)a(x)} \;\middle|\; a(x) \in \mathbb{F}_q[x] \right\} \subset R
とすると、$\tilde{C}$ は $R$ の部分ベクトル空間を定めます。これにより符号 $C := \phi^{-1}(\tilde{C})$ を定めることができ、これを巡回符号といいます。この符号に対し $g(x)$ を生成多項式、$h(x)$ を検査多項式といいます。
巡回符号であることの確認
$[c_0, c_1, \ldots, c_{n-1}] \in C$ とすると
\phi([c_0, c_1, \ldots, c_{n-1}]) = \overline{c_0 + c_1x + \cdots + c_{n-1}x^{n-1}} \in \tilde{C} = \overline{g(x)}R
なので、$R$ 上で $\overline{x}^n = 1$ であることに注意すると
\begin{array}{rcl}
\overline{x} \cdot \overline{c_0 + c_1x + \cdots + c_{n-1}x^{n-1}}
&=& \overline{c_0x + c_1x^2 + \cdots + c_{n-1}x^n} \\
&=& \overline{c_{n-1} + c_0x + \cdots + c_{n-2}x^{n-1}}
\end{array}
となります。これは $\phi([c_{n-1}, c_0, \ldots, c_{n-2}])$ と等しいため、$[c_{n-1}, c_0, \ldots, c_{n-2}] \in C$ といえます。
巡回符号の誤り検査行列
説明は省きますが、 $\tilde{C} = \overline{g(x)R} \subset R$ では $\overline{g(x)}, \overline{xg(x)}, \ldots, \overline{x^{k-1}g(x)}$ と基底を取ることができます。そのため符巡回号 $C$ の基底 $\boldsymbol{c}_i$ は $\boldsymbol{c}_i = \phi^{-1}(\overline{x^i g(x)})$ と表すことができます。したがって $g(x) = c_0 + c_1 x + c_2 x + \cdots + c_{n-k} x^{n-k}$ と表すと、$C$ の生成行列 $G$ は次のように表せます。
G = \begin{pmatrix}
c_0 & c_1 & \cdots & c_{n - k} &&&\\
& c_0 & c_1 & \cdots & c_{n - k} &&\\
&& \ddots & \ddots && \ddots & \\
&&& c_0 & c_1 & \cdots & c_{n - k} \\
\end{pmatrix}
また、 $h(x) = b_0 + b_1x + \cdots + b_kx^k$ と表すと検査行列 $H$ は次のように表せます。
G = \begin{pmatrix}
b_k & \cdots & b_1 & b_0 &&&\\
& b_k & \cdots b_1 && b_0 &&\\
&& \ddots && \ddots & \ddots & \\
&&& b_k & \cdots b_1 && b_0 \\
\end{pmatrix}
リード・ソロモン符号
有限体 $\mathbb{F}_q$ の原始根 (乗法群の単位元) $\alpha \in \mathbb{F}_q$ は、 $\alpha^i \not\equiv 1, i = 1 \ldots, q - 2$ かつ $\alpha^{q - 1} = 1$ を満たします。そのため $q - 1$ の約数 $n$ をとり $\beta = \alpha^{(q - 1) / n}$ とおくと $\beta, \beta^2, \ldots, \beta^n$ は相異なる $1$ の $n$ 乗根を与えます。そのため $x^n - 1$ の分解を次のように表せます。
x^n - 1 = \prod_{i = 1}^{n} (x - \beta^i)
$n$ 項の積を $n-k$ 個と $k$ 個に分け、
g(x) = \prod_{i = 1}^{n - k} (x - \beta^i) ,\quad
h(x) = \prod_{i = n - k - + 1}^{k} (x - \beta^i)
とすると、$x^n - 1 = g(x)h(x)$ となります。$g(x)$ を生成多項式、$h(x)$ を検査多項式とする巡回符号 $C \subset \mathbb{F}_q^n$ (長さ $n$, 次元 $k$) をリード・ソロモン符号といいます。リード・ソロモン符号は最良の誤り制定能力を持ち、$(n - k + 1) / 2$ 個の誤りを訂正できます。
リード・ソロモン符号の符号化
まず $\mathbb{F}_q$ 上の線形写像 $\psi: \mathbb{F}_q[x]_{\deg < k} \rightarrow \mathbb{F}_q[x]_{\deg < n - k}$ を次のように定めます。
\psi(a(x)) := x^{n - k} a(x) \mod g(x)
すなわち $x^{n - k}a(x)$ を $g(x)$ で割った余りです。さらに線形写像 $\Phi: \mathbb{F}_q[x]_{\deg < k} \rightarrow \mathbb{F}_q^n$ を次のように定めます。
\Phi(a(x)) := \phi^{-1} \left(\overline{x^{n - k} a(x) - \psi(a(x))} \right)
なお $\phi: \mathbb{F}_q^n \rightarrow \mathbb{F}_q[x]/(x^n - 1)$ はベクトルから多項式への変換でした。$\psi$ の定義から $\overline{x^{n - k}a(x) - \psi(a(x))}$ は $g(x)$ で割り切れます。巡回符号は $g(x)$ で割り切れるものの集合であったため、これは $\tilde{C}$ に属することがわかります。このことから $\mathrm{Im}(\Phi) \subseteq C$ ですが、詳しい説明は省きますが等号は成立し、$\mathrm{Im}(\Phi) = C$ すなわち $\Phi: \mathbb{F}_q[x]_{\deg < k} \rightarrow C$ となります。これによりリード・ソロモン符号の符号化ができます。
リード・ソロモン符号の誤り符号訂正
リード・ソロモン符号の検査行列は $H$ 次のように表されます。
H :=
\pmatrix{
1 & \beta & \beta^2 & \cdots & \beta^{n - 1} \\
1 & \beta^2 & \beta^4 & \cdots & \beta^{2(n-1)} \\
\vdots & \cdots & \ddots & \vdots \\
1 & \beta^{n - k} & \beta{2(n - k)} & \cdots & \beta^{(n - k)(n - 1)}
}
ある $\boldsymbol{a} = (a_0, a_1, \ldots, a_{n - 1})$ に対し$H$ との積 $\boldsymbol{s} := \boldsymbol{a} \cdot H^\intercal$ をシンドロームといいます。$\boldsymbol{s} = (s_0, s_1, \ldots, s_{n - k - 1})$ に対し $\boldsymbol{s}(x) = s_0 + s_1 x + \cdots + s_{n - k - 1} x^{n - k - 1}$ をシンドローム多項式といいます。
ここで $d(\boldsymbol{a}, \boldsymbol{0}) \le (n - k) / 2$ を満たすとし、 $\boldsymbol{a}$ のシンドローム多項式を $\boldsymbol{a}(x)$ とすると、
\left\{
\begin{array}{l}
\boldsymbol{\sigma}(x) \boldsymbol{s}(X) \equiv \boldsymbol{\omega}(x) \mod x^{n - k} \\
\deg \boldsymbol{\sigma}(x) \le \frac{n - k}{2}, \quad \deg \boldsymbol{\omega}(x) < \deg \boldsymbol{\sigma}(x) \\
\gcd(\boldsymbol{\sigma}(x), \boldsymbol{\omega}(x)) = 1
\end{array}
\right.
を満たす $\boldsymbol{\sigma}(x), \boldsymbol{\omega(x)} \in \mathbb{F}_q[x]$ が定数倍の違いを除きただ一つに定まります。さらにこれは具体的に次のように与えられます。
\begin{array}{l}
\sigma(x) = \prod_{e_i \ne 0} (1 - \beta^i x), \\
\omega(x) = \sum_{e_i \ne 0} (e_i \beta^i \prod_{e_j \ne 0, j \ne i}(1 - \beta^j x))
= \sum_{e_i \ne 0} e_i \beta^i \frac{\boldsymbol{\sigma}(x)}{1 - \beta^i x}
\end{array}
この $\boldsymbol{\sigma}(x)$ を誤り位置検出多項式といいます。具体的に与えられた $\boldsymbol{\sigma}(x)$ から、$\boldsymbol{\sigma}(\beta^{-i}) = 0 \leftrightarrow e_i \ne 0$ であることがわかります。ここでは $\boldsymbol{\sigma}(x)$ は具体的な $\boldsymbol{e}$ によって表されていますが、この $\boldsymbol{\sigma}$ および $\boldsymbol{\omega}$ の条件は多項式に対するユークリッドの互除法そのものです。そのため実際には互助法を用いて $\boldsymbol{\sigma}(x)$ を求めます。
符号 $\boldsymbol{x} \in C$ が誤り $\boldsymbol{e} \in \mathbb{F}_q^n$ を含んで $\boldsymbol{x} + \boldsymbol{e}$ と受信された時、検査行列の性質から $\boldsymbol{x} + \boldsymbol{e}$ のシンドロームと $\boldsymbol{e}$ のシンドロームは同一となります。このため受診した $\boldsymbol{x} + \boldsymbol{e}$ のシンドロームを検査することで誤り $\boldsymbol{e}$ の非ゼロ要素の位置を求めることができます。
最後に $\boldsymbol{e}$ を求めます。シンドローム $\boldsymbol{s} = \boldsymbol{e} \cdot H^\intercal$ より $\boldsymbol{s}$ の $j$ 番目の成分 $s_j$ は次のように表せました。
s_j = e0 + e_1 \beta^j + e_2 \beta^{2j} + \cdots + e_{n - 1} \beta^{j(n - 1)}
誤りの位置がわかり、$\boldsymbol{e} = (0, \ldots, 0, e_{i_1}, 0, \ldots, 0, \ldots, 0, e_{i_2}, 0, \ldots, 0, \ldots, 0, e_{i_d}, 0)$ のように表せたとします。このときシンドロームの各成分から次の連立方程式が導かれます。
\left\{
\begin{array}{rcl}
s_1 &=& e_{i_1} \beta^{i_1} + e_{i_2} \beta^{i_2} + \cdots + e_{i_d} \beta^{i_d} \\
s_2 &=& e_{i_1} \beta^{2i_1} + e_{i_2} \beta^{2i_2} + \cdots + e_{i_d} \beta^{2i_d} \\
&\cdots& \\
s_{n-k} &=& e_{i_1} \beta^{(n - k)i_1} + e_{i_2} \beta^{(n - k)i_2} + \cdots + e_{i_d} \beta^{(n - k)i_d}
\end{array}
\right.
誤りの数は $(n - k) / 2$ 以下であったので、シンドロームから誤りを求めることができることがわかります。求めた $\boldsymbol{e}$ から $(\boldsymbol{x} + \boldsymbol{e}) - \boldsymbol{e}$ とすることで誤りを訂正することができます。