SSブログ

有限体の勉強 〜リード・ソロモン符号のシミュレーション〜 [数学]

 有限体の勉強を始めてちょっとわかった気になってきましたが、ここで有限体の応用の一つである「誤り訂正符号」、その中でも誤り訂正能力が高い方式である「リード・ソロモン符号」について、その原理をシミュレートしてみたいと思います。

 リード・ソロモン符号については、Wikipediaの記事にその原理が記述されていたり、他にも書籍を含めてたくさんの解説がありますが、数式を眺めてもなかなか理解できるものではありません。そこで実際に手を動かして、符号化と復号の推移を見てみることにします。

 リード・ソロモン符号は有限体を係数とする多項式を本格的に使います。まずはその有限体を定めますが、8ビットで表現できる $F_{2^8} (= F_{256})$ を使うことが多いようなので、本記事でも $F_{256}$ を使います。

 例によって $F_{256}$ の乗法群 $F_{256}^\times$ の原始元を見つけることから始めなければいけませんが、そこからするのはもうしんどいのでWikipediaから答えを頂きます。次の多項式
\[ X^8+X^4+X^3+X^2+1 \]
は $F_2$ 上で既約で、その根$\alpha$が $F_{256}^\times$ の原始元を与えます。これさえわかれば、スプレッドシートを使って $F_{256}$ の全ての元について $\alpha$ の指数表現と $(\alpha^7, \alpha^6, \cdots , \alpha, 1)$ を基底とするベクトル表現との対応づけをすることができます。スプレッドシート上は単純な縦長の表になりますが、全体を見やすくするためベクトル表現を$16$進で表してここに掲載します。

$F_{256}$ の変換表(ベクトル表現16進 → 指数表現)

0 1 2 3 4 5 6 7 8 9 A B C D E F
0x * 0 1 25 2 50 26 198 3 223 51 238 27 104 199 75
1x 4 100 224 14 52 141 239 129 28 193 105 248 200 8 76 113
2x 5 138 101 47 225 36 15 33 53 147 142 218 240 18 130 69
3x 29 181 194 125 106 39 249 185 201 154 9 120 77 228 114 166
4x 6 191 139 98 102 221 48 253 226 152 37 179 16 145 34 136
5x 54 208 148 206 143 150 219 189 241 210 19 92 131 56 70 64
6x 30 66 182 163 195 72 126 110 107 58 40 84 250 133 186 61
7x 202 94 155 159 10 21 121 43 78 212 229 172 115 243 167 87
8x 7 112 192 247 140 128 99 13 103 74 222 237 49 197 254 24
9x 227 165 153 119 38 184 180 124 17 68 146 217 35 32 137 46
Ax 55 63 209 91 149 188 207 205 144 135 151 178 220 252 190 97
Bx 242 86 211 171 20 42 93 158 132 60 57 83 71 109 65 162
Cx 31 45 67 216 183 123 164 118 196 23 73 236 127 12 111 246
Dx 108 161 59 82 41 157 85 170 251 96 134 177 187 204 62 90
Ex 203 89 95 176 156 169 160 81 11 245 22 235 122 117 44 215
Fx 79 174 213 233 230 231 173 232 116 214 244 234 168 80 88 175


$F_{256}$ の変換表(指数表現 → ベクトル表現16進)

0 1 2 3 4 5 6 7 8 9
0x 01 02 04 08 10 20 40 80 1D 3A
1x 74 E8 CD 87 13 26 4C 98 2D 5A
2x B4 75 EA C9 8F 03 06 0C 18 30
3x 60 C0 9D 27 4E 9C 25 4A 94 35
4x 6A D4 B5 77 EE C1 9F 23 46 8C
5x 05 0A 14 28 50 A0 5D BA 69 D2
6x B9 6F DE A1 5F BE 61 C2 99 2F
7x 5E BC 65 CA 89 0F 1E 3C 78 F0
8x FD E7 D3 BB 6B D6 B1 7F FE E1
9x DF A3 5B B6 71 E2 D9 AF 43 86
10x 11 22 44 88 0D 1A 34 68 D0 BD
11x 67 CE 81 1F 3E 7C F8 ED C7 93
12x 3B 76 EC C5 97 33 66 CC 85 17
13x 2E 5C B8 6D DA A9 4F 9E 21 42
14x 84 15 2A 54 A8 4D 9A 29 52 A4
15x 55 AA 49 92 39 72 E4 D5 B7 73
16x E6 D1 BF 63 C6 91 3F 7E FC E5
17x D7 B3 7B F6 F1 FF E3 DB AB 4B
18x 96 31 62 C4 95 37 6E DC A5 57
19x AE 41 82 19 32 64 C8 8D 07 0E
20x 1C 38 70 E0 DD A7 53 A6 51 A2
21x 59 B2 79 F2 F9 EF C3 9B 2B 56
22x AC 45 8A 09 12 24 48 90 3D 7A
23x F4 F5 F7 F3 FB EB CB 8B 0B 16
24x 2C 58 B0 7D FA E9 CF 83 1B 36
25x 6C D8 AD 47 8E


 本記事では $F_{256}$ の元は指数表現で扱うことを基本とするので、乗法演算は指数を足し合わせて$\mod 255$ をとることで行えます。加法演算はちょっと手間ですが、変換表を用いてベクトル表現にしてから各ビット毎にXORを取って、再び変換表を用いて指数表現にすれば求まります。実際にはこれらの計算は全部スプレッドシート上で関数を駆使して行いました。

 では、実際に文字列 "Hello!" をリード・ソロモン符号で符号化し、通信路上で生じた誤りが受信側で復元できることを見てみましょう。以下ではWikipediaの記事の方法に従ってシミュレートします。

 リード・ソロモン符号では、符号を $F_{256}$ の元を係数とする多項式で表します。"Hello!" の6文字をASCIIコード16進で表すと、
48, 65, 6C, 6C, 6F, 21

となりますが、これを $F_{256}$ の元のベクトル表現とみなして指数表現に変換すると、
\[ \alpha^{226}, \ \alpha^{72}, \ \alpha^{250}, \ \alpha^{250}, \ \alpha^{61}, \ \alpha^{138} \]
となり、これを表す情報多項式 $I(X)$ は、
\[ I(X) = \alpha^{226}X^5 + \alpha^{72}X^4 + \alpha^{250}X^3 + \alpha^{250}X^2 + \alpha^{61}X + \alpha^{138} \]
という$5$次多項式になります。
 これに誤り検出と訂正のための冗長化符号を追加します。ここでは最大 $t = 2$ 個のシンボルの誤りが訂正できるようにします。このため、生成多項式 $G(X)$ は
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) = X^4+\alpha^{75}X^3+\alpha^{249}X^2+\alpha^{78}X+\alpha^6 \]
によって定めればよく、これを使うと冗長多項式 $P(X)$ は
\[ P(X) = I(X) \times X^4 \mod G(X) = \alpha^{189}X^3 + \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177} \]
となって、実際に送信する符号多項式 $C(X)$ は
\begin{eqnarray*}
C(X) &=& I(X) \times X^4 + P(X) \\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 + \alpha^{61}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 + \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177}
\end{eqnarray*}
となります。この上位$6$つの項の係数が送りたい文字列 "Hello!" を表しています。

 さて、この送信符号に通信路上で誤りが混入し、受信側では
\[ Y(X) = \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 + \alpha^{138}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 + \alpha^{43}X^2 + \alpha^{42}X + \alpha^{177} \]
となったとしましょう。つまり受信側では $X^5$ の係数が $\alpha^{61}$ から $\alpha^{138}$ に化け、さらに冗長化で追加した部分も $X^2$ の係数が $\alpha^{19}$ から $\alpha^{43}$ に化けて伝わったと想定します。これでは情報部分が文字列 "Hell!!" を表すことになり、そのまま受け止めるとコミュニケーション上大変な問題が生じてしまいます。
 そこで、この受信符号から誤りを見つけ出し、訂正する必要があります。これもWikipediaの記事に従って実際に行ってみます。

 まず、シンドロームと呼ばれる $t \times 2 = 4$ 個の $F_{256}$ の値を次によって計算します。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& \alpha^{163} \\
S_2 &=& Y(\alpha^1) &=& \alpha^{112} \\
S_3 &=& Y(\alpha^2) &=& \alpha^{2} \\
S_4 &=& Y(\alpha^3) &=& \alpha^{25}
\end{eqnarray*}
$C(X)$ が $G(X)$ で整除されるので、もし誤りがなければこれらは全て$0$になるはずのものですが、誤りが生じているためどれも$0$以外の値となっています。

 次にこれらの値を使って誤り数 $k$ を求めます。次の行列式を計算します。
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
= S_2^2 - S_1S_3 = \alpha^{247}
\end{equation*}
これは$0$ではないので、$k = 2$ すなわち誤りのあるシンボル数は$2$個です($3$個以上の誤りは想定しないものとします)。

 続いて、誤りがどの位置にあるのかを特定します。$k=2$ なので、誤り位置多項式 $\sigma(X)$ は次の形の$2$次多項式になります。
\[ \sigma(X) = \sigma_2X^2 +\sigma_1X+1 \]
ここで係数 $\sigma_1, \sigma_2$ は、
\begin{equation*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\end{equation*}
をみたすので、これを解くと $\sigma_1 = \alpha^{225}, \ \sigma_2 = \alpha^{7}$ が得られ、
\[ \sigma(X) = \alpha^{7}X^2 +\alpha^{225}X+1 \]
となります。
 この $\sigma(X)$ に $\alpha^0, \alpha^{-1}, \cdots , \alpha^{-9}$ を次々に代入すると、$\sigma(\alpha^{-2})$ と $\sigma(\alpha^{-5})$ だけが$0$となり、他は$0$ではないので、$Y(X)$ の $X^2$ と $X^5$ の係数が誤りを含んでいると特定されました。

 最後に誤りの値を計算します。誤り多項式 $E(X) = Y(X) - C(X)$ は
\[ E(X) = e_1X^5 + e_2X^2 \]
の形になることがわかりましたので、これに $\alpha^0, \alpha^1$ を代入することにより、
\begin{eqnarray*}
e_1 &+& e_2 &=& S_1 &=& \alpha^{163} \\
e_1\alpha^5 &+& e_2\alpha^2 &=& S_2 &=& \alpha^{112}
\end{eqnarray*}
これを解くと $e_1 = \alpha^{34}, \ e_2 = \alpha^{18}$ が得られるので、
\begin{eqnarray*}
C(X) &=& Y(X) + E(X) \\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 &+& \alpha^{138}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 &+& \alpha^{43}X^2 + \alpha^{42}X + \alpha^{177} \\
&& &+& \alpha^{34}X^5 &+& \alpha^{18}X^2\\
&=& \alpha^{226}X^9 + \alpha^{72}X^8 + \alpha^{250}X^7 + \alpha^{250}X^6 &+& \alpha^{61}X^5 + \alpha^{138}X^4 + \alpha^{189}X^3 &+& \alpha^{19}X^2 + \alpha^{42}X + \alpha^{177}
\end{eqnarray*}
となって、無事に送信符号と同じもの、情報部分の文字列 "Hello!" が復元されました。

 このシミュレーションを行ったスプレッドシートをそのままここにアップロードしておきます。ダウンロードしてEXCELなどで開き、2箇所の黄色のセルに$0$から$254$までのどのような数字を入れても、復号した緑のセルは元の青いセルの値が正しく表示されることが確認できると思います。

 有限体の四則演算が自由自在にできることを利用した巧妙な符号化方式であることが実感できました。考えた人(リードさんとソロモンさん)は天才ですね。

nice!(0)  コメント(0) 
共通テーマ:学問

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

※ブログオーナーが承認したコメントのみ表示されます。