本記事で説明する内容:
- 符号化
- 誤り検出
- その他、全体の大まかな内容
本記事で説明しない内容:
- 誤り数および誤り位置の検出
- 誤り訂正
- その他、厳密な数学的な内容
0. まとめ
リード・ソロモン符号を用いると、データの誤りを検出したり訂正したりできます。
リード・ソロモン符号では、有限体またはガロア体と呼ばれる特殊な計算方法を使います。
符号化は、有限体上で割り算しその余りを元のデータに付け加えます。
ここで使用する有限体の計算上、足し算と引き算が同じ意味になるので、割り算の余りを足すことは割り算の余りを引くことと同じ意味になり、割り算で割り切れるようになります。
よって、符号化されて送られたデータが割り算で割り切れれば誤りがないとみなすことができ、割り算で割り切れなければ誤りがあるとみなすことができます (実際は割り算をしなくても誤り検出可能。詳細は後述) 。
1. 有限体
有限体に関しては別記事にしました。
参考「有限体の例: GF(2^4) と GF(2^8) - Qiita」
2. 多項式の割り算の余りの計算方法
リード・ソロモン符号では符号化時に多項式の割り算の余りを計算します。
多項式の割り算自体は通常の計算と同様に筆算等で行えますが、その過程で係数の四則演算は有限体上で行います。
例えば、原始多項式を $x^8 + x^4 + x^3 + x^2 + 1$ とする有限体 $GF(2^8)$ 上で計算すると、$\alpha^6 x^3 + \alpha^5 x^2$ 割る $x^2 + \alpha^{25} x + \alpha$ は
\require{enclose}
\begin{align}
\hspace{0.25em} \alpha^6 x^\phantom{3} \hspace{0.25em} + \hspace{0.25em} \alpha^{203} \phantom{x^2} \hspace{0.25em} \phantom{{} + \hspace{0.25em} \alpha^{000} x \hspace{0.25em} + \hspace{0.25em} \alpha^{000} \hspace{0.25em}} \\
x^2 \hspace{0.25em} + \hspace{0.25em} \alpha^{25} x \hspace{0.25em} + \hspace{0.25em} \alpha \hspace{0.25em} \rlap{\enclose{longdiv}{\phantom{ \hspace{0.25em} \alpha^6 x^3 \hspace{0.25em} + \hspace{0.25em} \alpha^{5\phantom{00}} x^2 \hspace{0.25em} }}} \hspace{0.5em} \hspace{0.25em} \alpha^6 x^3 \hspace{0.25em} + \hspace{0.25em} \alpha^{5\phantom{00}} x^2 \hspace{0.25em} \phantom{{} + \hspace{0.25em} \alpha^{000} x \hspace{0.25em} + \hspace{0.25em} \alpha^{000} \hspace{0.25em}} \\
\rlap{\underline{\phantom{ \hspace{0.25em} \alpha^6 x^3 \hspace{0.25em} + \hspace{0.25em} \alpha^{31\phantom{0}} x^2 \hspace{0.25em} + \hspace{0.25em} \alpha^{7\phantom{00}} x \hspace{0.25em} }}} \hspace{0.25em} \alpha^6 x^3 \hspace{0.25em} + \hspace{0.25em} \alpha^{31\phantom{0}} x^2 \hspace{0.25em} + \hspace{0.25em} \alpha^{7\phantom{00}} x \hspace{0.25em} \phantom{{} + \hspace{0.25em} \alpha^{000} \hspace{0.25em}} \\
\hspace{0.25em} \alpha^{203} x^2 \hspace{0.25em} + \hspace{0.25em} \alpha^{7\phantom{00}} x \hspace{0.25em} \phantom{{} + \hspace{0.25em} \alpha^{000} \hspace{0.25em}} \\
\rlap{\underline{\phantom{ \hspace{0.25em} \alpha^{203} x^2 \hspace{0.25em} + \hspace{0.25em} \alpha^{228} x \hspace{0.25em} + \hspace{0.25em} \alpha^{204} \hspace{0.25em} }}} \hspace{0.25em} \alpha^{203} x^2 \hspace{0.25em} + \hspace{0.25em} \alpha^{228} x \hspace{0.25em} + \hspace{0.25em} \alpha^{204} \hspace{0.25em} \\
\hspace{0.25em} \alpha^{109} x \hspace{0.25em} + \hspace{0.25em} \alpha^{204} \hspace{0.25em}
\end{align}
のように計算できます。ただし
\begin{alignat}{6}
&\alpha^6 & x \times (x^3 + \alpha^{25} x^2 + \alpha) &= \alpha^6 & x^3 + {} &\alpha^{31} & &x^2 & {} + {} &\alpha^7 & x \\
&\alpha^{203} & \times (x^3 + \alpha^{25} x^2 + \alpha) &= \alpha^{203} & x^2 + {} &\alpha^{228} & &x & {} + {} &\alpha^{204} &
\end{alignat}
\begin{alignat}{2}
&\alpha^5 - \alpha^{31} & &= 00100000_{(2)} - 11000000_{(2)} = 11100000_{(2)} = \alpha^{203} \\
&\alpha^7 - \alpha^{228} & &= 10000000_{(2)} - 00111101_{(2)} = 10111101_{(2)} = \alpha^{109}
\end{alignat}
です。
この例では商は
Q(x) = \alpha^6 x + \alpha^{203}
になり、余りは
\begin{align}
R(x) &= (\alpha^6 x^3 + \alpha^5 x^2) \bmod (x^2 + \alpha^{25} x + \alpha) \\
&= \alpha^{109} x + \alpha^{204}
\end{align}
となります。
3. リード・ソロモン符号
ここでは、原始多項式を $x^8 + x^4 + x^3 + x^2 + 1$ とする有限体 $GF(2^8)$ を使用することにします。
3.1. 誤り訂正符号の長さ
誤り訂正符号の長さは誤りを訂正したい長さの 2 倍にします。
例えば、3 バイトのデータに 4 バイトの誤り訂正符号を加えると、合計 7 バイト中 2 バイトのデータが誤っても訂正可能です。
(※本記事では深く触れませんが、最小ハミング距離は誤り訂正符号の長さ足す 1 になります。)
3.2. 生成多項式
長さが $d'$ バイトの誤り訂正符号を生成したいとき、生成多項式
G_{d'}(x) = \prod_{i = 0}^{d'-1} (x - \alpha^i)
を使用します。
(場合によっては生成多項式
G_{d'}(x) = \prod_{i = b}^{d'-1+b} (x - \alpha^i)
が使用されることもあります。)
例えば、$d' = 4$ のとき生成多項式は
\begin{align}
G_4(x) &= \prod_{i = 0}^3 (x - \alpha^i) \\
&= x^4 ＋ \alpha^{75} x^3 ＋ \alpha^{249} x^2 ＋ \alpha^{78} x ＋ \alpha^6
\end{align}
になります。
3.3. 符号化
3.3.1. 多項式で計算する場合
符号化したいデータを情報多項式 $M(x)$ として扱います。
例えば、10 進数で 16 240 80 という 3 バイトのデータ符号があるとき、情報多項式は
M(x) = 16 x^2 + 240 x + 80
になります。
長さが $d'$ バイトの誤り訂正符号を生成したいとき、情報多項式 $M(x)$ に $x^{d'}$ をかけた式を $G_{d'}(x)$ で割った余り $R(x)$ が誤り訂正符号を表す多項式になります。
例えば、長さが 4 バイトの誤り訂正符号は多項式
\begin{align}
R(x) &= x^{d'} M(x) \bmod G_{d'}(x) \\
&= x^4 M(x) \bmod G_4(x) \\
&= x^4 M(x) \bmod (x^4 ＋ \alpha^{75} x^3 ＋ \alpha^{249} x^2 ＋ \alpha^{78} x ＋ \alpha^6) \\
\end{align}
で表されます。
情報多項式 $M(x)$ を代入すると
\begin{align}
R(x) &= (16 x^6 + 240 x^5 + 80 x^4) \bmod (x^4 ＋ \alpha^{75} x^3 ＋ \alpha^{249} x^2 ＋ \alpha^{78} x ＋ \alpha^6) \\
&= 14 x^3 + 177 x^2 + 166 x + 169
\end{align}
となり、誤り訂正符号は 14 177 166 169 になります。
リード・ソロモン符号は情報多項式 $M(x)$ と割り算の余り $R(x)$ を合わせて符号多項式
\begin{align}
C(x) &= x^{d'} M(x) + R(x) \\
&= x^4 M(x) + R(x) \\
&= 16 x^6 + 240 x^5 + 80 x^4 + 14 x^3 + 177 x^2 + 166 x + 169
\end{align}
で表され、バイト列は 16 240 80 14 177 166 169 (単に、データ符号 16 240 80 と誤り訂正符号 14 177 166 169 を連結したもの) になります。
3.3.2. 多項式の係数のみで計算する場合
理論上はリード・ソロモン符号の計算は多項式で行いますが、符号化に関しては多項式の割り算をするだけで $x$ に値を代入しないため、多項式の各係数のみに着目して計算することができます。
データ符号 16 240 80
16 240 80 0 0 0 0
生成多項式の係数 1 15 54 120 64
誤り訂正符号 14 177 166 169
符号 16 240 80 14 177 166 169
3.4. 誤り検出
3.4.1. 誤りを含まない符号多項式は生成多項式で割り切れる
$x^{d'} M(x)$ を $G_{d'}(x)$ で割った余りの多項式が
R(x) = x^{d'} M(x) \bmod G_{d'}(x)
になるということは、割り算の商を多項式 $Q(x)$ とおくと
x^{d'} M(x) = Q(x) G_{d'}(x) + R(x)
が成り立つため、符号多項式は
\begin{align}
C(x) &= x^{d'} M(x) + R(x) \\
&= Q(x) G_{d'}(x) + R(x) + R(x) \\
&= Q(x) G_{d'}(x)
\end{align}
より
C(x) \bmod G_{d'}(x) = 0
となり生成多項式で割り切れることが分かります。
3.4.2. 生成多項式が 0 のとき誤りを含まない符号多項式も 0 になる
符号多項式は $C(x) = Q(x) G_{d'}(x)$ より
G_{d'}(x) = 0 \rightarrow C(x) = 0
となります。
生成多項式は前述の通り
G_{d'}(x) = \prod_{i = 0}^{d'-1} (x - \alpha^i)
で表されるため
\begin{alignat}{2}
\forall x \in \{ \alpha^0, \alpha^1, \dots , \alpha^{d'-2}, \alpha^{d'-1} \} &, {} \; & G_{d'}(x) &= 0 \\
\forall x \in \{ \alpha^0, \alpha^1, \dots , \alpha^{d'-2}, \alpha^{d'-1} \} &, {} \; & C(x) &= 0
\end{alignat}
が成り立ちます。
3.4.3. 誤りを含む可能性のある符号多項式が生成多項式で割り切れるか調べる
誤りを含む可能性のある符号多項式 $D(x)$ に $x \in \{ \alpha^0, \alpha^1, \dots , \alpha^{d'-2}, \alpha^{d'-1} \}$ を代入して全て $0$ になれば生成多項式で割り切れることになり、誤りを含まないと考えられます。
1 つでも $0$ 以外の値になれば誤りを含むと考えられます。
ここでの $D(\alpha^i)$ の値は「シンドローム」と呼ばれます。
例えば、情報多項式
M(x) = 16 x^2 + 240 x + 80
と生成多項式
G_4(x) = \prod_{i = 0}^3 (x - \alpha^i)
より符号多項式
\begin{alignat}{8}
C(x) &= {} & 16 x^6 &+ {} & 240 x^5 &+ {} & 80 x^4 &+ {} & 14 x^3 &+ {} & 177 x^2 &+ {} & 166 x &+ {} & 169 \\
&= {} & \alpha^4 x^6 &+ {} & \alpha^{79} x^5 &+ {} & \alpha^{54} x^4 &+ {} & \alpha^{199} x^3 &+ {} & \alpha^{86} x^2 &+ {} & \alpha^{207} x &+ {} & \alpha^{135}
\end{alignat}
が得られるとき、符号多項式 $C(x)$ のシンドローム $C(\alpha^0)$ は
\begin{align}
C(\alpha^0) &= \alpha^4 + \alpha^{79} + \alpha^{54} + \alpha^{199} + \alpha^{86} + \alpha^{207} + \alpha^{135} \\
&= 16 + 240 + 80 + 14 + 177 + 166 + 169 \\
&= 00010000_{(2)} + 11110000_{(2)} + 01010000_{(2)} + 00001110_{(2)} + 10110001_{(2)} + 10100110_{(2)} + 10101001_{(2)} \\
&= 00000000_{(2)} \\
&= 0
\end{align}
のように計算できます。
同様に他のシンドロームも計算すると
\begin{align}
C(\alpha^0) &= 0 \\
C(\alpha^1) &= 0 \\
C(\alpha^2) &= 0 \\
C(\alpha^3) &= 0
\end{align}
となり、全て $0$ になることが分かります。
誤りを含む符号多項式を $D(x) = C(x) + x^4$ とすると
\begin{alignat}{8}
D(x) &= {} & 16 x^6 &+ {} & 240 x^5 &+ {} & 81 x^4 &+ {} & 14 x^3 &+ {} & 177 x^2 &+ {} & 166 x &+ {} & 169 \\
&= {} & \alpha^4 x^6 &+ {} & \alpha^{79} x^5 &+ {} & \alpha^{208} x^4 &+ {} & \alpha^{199} x^3 &+ {} & \alpha^{86} x^2 &+ {} & \alpha^{207} x &+ {} & \alpha^{135}
\end{alignat}
よりシンドロームは
\begin{align}
D(\alpha^0) &= 1 \neq 0 \\
D(\alpha^1) &= 2 \neq 0 \\
D(\alpha^2) &= 4 \neq 0 \\
D(\alpha^3) &= 8 \neq 0
\end{align}
と計算でき、誤りを含むことを確認できます。