有限体の勉強 〜有限体をExcel上で計算する〜 [数学]
「有限体の勉強」という記事をいくつか書いてきましたが、これらの記事を書くために多くの有限体の四則演算を実際に行う必要が生じ、手計算ではとても大変なのでスプレッドシートを使ってきました。ここでその具体的な方法を紹介します。なお、ここではスプレッドシートとは一般用語の「表計算ソフト」の意味で使っており、Excelが代表的ですが LibreOffice(Calc) や Googleスプレッドシートも同様の操作になります。
有限体といっても、本記事では標数$2$の有限体を対象とします。標数が$2$以外の有限体はビット演算関数が使えないのでかなり複雑になるからです。
例としてリード・ソロモン符号の記事でも使った $F_{256}$ の場合を考えます。
まず、この体の元をどう表現するかを決める必要があります。そのために必要なのは $F_{256}$ の原始多項式です。これは $F_2$ 上の$8$次の既約多項式で、その根が $F_{256}$ の原始元になるもののことです。一般に原始多項式は試行錯誤で探し出すことになりますが、いまの場合は、
\[ X^8+X^4+X^3+X^2+1 \]
が原始多項式になることが知られていますのでこれを使い、その一つの根を$\alpha$と書きます。このとき、
\[ \alpha^8 = \alpha^4+\alpha^3+\alpha^2+1 \]
が成り立つので（標数$2$なのでプラスとマイナスの区別はありません）、$\alpha$のべき乗について、
\begin{eqnarray*}
\alpha^0 &=& && && && && && && && \alpha^0 \\
\alpha^1 &=& && && && && && && \alpha^1 \\
&\cdots& \\
\alpha^7 &=& \alpha^7 \\
\alpha^8 &=& && && && \alpha^4 &+& \alpha^3 &+& \alpha^2 && &+& \alpha^0 \\
\alpha^9 &=& && && \alpha^5 &+& \alpha^4 &+& \alpha^3 && &+& \alpha^1 \\
&\cdots& \\
\alpha^{253} &=& && \alpha^6 && && && &+& \alpha^2 &+& \alpha^1 &+& \alpha^0 \\
\alpha^{254} &=& \alpha^7 && && && &+& \alpha^3 &+& \alpha^2 &+& \alpha^1
\end{eqnarray*}
という1対1の対応ができ、$0$を除く $F_{256}$ の元が網羅されます（$\alpha^{255} = \alpha^0 = 1$ です）。左辺をべき表現、右辺をベクトル表現といいます。
Excel上でべき表現とベクトル表現をどうデータ化するかですが、べき表現は指数をそのまま整数値で、ベクトル表現は$\alpha$を$2$に置き換えて計算した数値でデータ化するのが一番扱い易いです。後者はどういうことかというと、例えば
\[ \alpha^4+\alpha^3+\alpha^2+\alpha^0 \quad \to \quad 2^4+2^3+2^2+2^0 = 29 \]
と数値化して扱うということです。そしてExcel上ではこのベクトル表現の数値化を基本とします。なぜなら BITXOR 関数などのビット演算関数が使えることと、べき表現は$0$を扱うことができないからです。
とはいえ、後で説明するようにべき表現も頻繁に使いますので、Excel上でべき表現とベクトル表現の対応表を作ることから始めます。縦にべき表現として$0$から$254$までを並べ、その右側の列に次のようにしてベクトル表現を入れます。$1$行目にべき表現$0$に対してベクトル表現$1$を入れます。$2$行目以降は一つ上の行の数値を$2$進法のビット列とみなし、それを BITLSHIFT 関数で左に$1$ビットシフトし、BITAND 関数で下$8$ビットだけをとり、さらに一つ上の行の数値の$7$ビット目が$1$ならば（つまり$128$以上ならば）$2^4+2^3+2^2+2^0 = 29$ との排他的論理和を BITXOR 関数で入れます。これをべき表現$254$の行まで繰り返すと、対応表が出来上がります。
この対応表はべき表現順に並んでいますので、これを丸ごとコピーして値ペーストし、左右を入れ替えてベクトル表現順に並べ替えた対応表も作っておきます。
言葉ではわかりにくいので、これらの対応表を LibreOffice で作ったものをここにアップロードします。ダウンロードしてセル内の数式を確認してください。Excelでも開けます。
対応表ができあがったら、これは一つのシートとして置いておき（シート名を「対応表」とします）、本番の計算は同じファイルの別シートで行うのが便利です。
例として、セルA1とセルB1にベクトル表現で表した数値が入っており、これらの $F_{256}$ としての和、差、積、商を返す計算式は次のようになります。
和については先ほど登場した BITXOR 関数を使って
=BITXOR(A1,B1)
となります。この関数は引数の数値を$2$進法のビット列とみなして各ビット毎に排他的論理和をとる関数です。
差については標数が$2$なので和と全く同じ
=BITXOR(A1,B1)
となります。
積については、べき表現だと単に足し合わせて$255$の剰余をとるだけなので、ここで先ほど作った対応表を使ってベクトル表現からべき表現に変換し、足し合わせて$255$の剰余をとり、結果をまた対応表でべき表現からベクトル表現に戻せばできあがりです。これらの変換には、みんな大好き VLOOKUP 関数が使えます。実際に書き下すと、
=VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)
となります（対応表のセル範囲はアップロードしたファイルに対応しています）。ただし引数がどちらも$0$でなければこれで良いのですが、どちらかが$0$だとエラーが出てしまいますので、複雑にはなりますが IF 関数を使って、
=IF(A1=0,0,IF(B1=0,0,VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば完璧です。
商については、積の場合の指数の和を差に変えれば良いので、例えば、
=IF(B1=0,"ゼロ除算エラー",IF(A1=0,0,VLOOKUP(MOD(
VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)-VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE)
,255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば良いでしょう。
（続く）（前記事）
有限体といっても、本記事では標数$2$の有限体を対象とします。標数が$2$以外の有限体はビット演算関数が使えないのでかなり複雑になるからです。
例としてリード・ソロモン符号の記事でも使った $F_{256}$ の場合を考えます。
まず、この体の元をどう表現するかを決める必要があります。そのために必要なのは $F_{256}$ の原始多項式です。これは $F_2$ 上の$8$次の既約多項式で、その根が $F_{256}$ の原始元になるもののことです。一般に原始多項式は試行錯誤で探し出すことになりますが、いまの場合は、
\[ X^8+X^4+X^3+X^2+1 \]
が原始多項式になることが知られていますのでこれを使い、その一つの根を$\alpha$と書きます。このとき、
\[ \alpha^8 = \alpha^4+\alpha^3+\alpha^2+1 \]
が成り立つので（標数$2$なのでプラスとマイナスの区別はありません）、$\alpha$のべき乗について、
\begin{eqnarray*}
\alpha^0 &=& && && && && && && && \alpha^0 \\
\alpha^1 &=& && && && && && && \alpha^1 \\
&\cdots& \\
\alpha^7 &=& \alpha^7 \\
\alpha^8 &=& && && && \alpha^4 &+& \alpha^3 &+& \alpha^2 && &+& \alpha^0 \\
\alpha^9 &=& && && \alpha^5 &+& \alpha^4 &+& \alpha^3 && &+& \alpha^1 \\
&\cdots& \\
\alpha^{253} &=& && \alpha^6 && && && &+& \alpha^2 &+& \alpha^1 &+& \alpha^0 \\
\alpha^{254} &=& \alpha^7 && && && &+& \alpha^3 &+& \alpha^2 &+& \alpha^1
\end{eqnarray*}
という1対1の対応ができ、$0$を除く $F_{256}$ の元が網羅されます（$\alpha^{255} = \alpha^0 = 1$ です）。左辺をべき表現、右辺をベクトル表現といいます。
Excel上でべき表現とベクトル表現をどうデータ化するかですが、べき表現は指数をそのまま整数値で、ベクトル表現は$\alpha$を$2$に置き換えて計算した数値でデータ化するのが一番扱い易いです。後者はどういうことかというと、例えば
\[ \alpha^4+\alpha^3+\alpha^2+\alpha^0 \quad \to \quad 2^4+2^3+2^2+2^0 = 29 \]
と数値化して扱うということです。そしてExcel上ではこのベクトル表現の数値化を基本とします。なぜなら BITXOR 関数などのビット演算関数が使えることと、べき表現は$0$を扱うことができないからです。
とはいえ、後で説明するようにべき表現も頻繁に使いますので、Excel上でべき表現とベクトル表現の対応表を作ることから始めます。縦にべき表現として$0$から$254$までを並べ、その右側の列に次のようにしてベクトル表現を入れます。$1$行目にべき表現$0$に対してベクトル表現$1$を入れます。$2$行目以降は一つ上の行の数値を$2$進法のビット列とみなし、それを BITLSHIFT 関数で左に$1$ビットシフトし、BITAND 関数で下$8$ビットだけをとり、さらに一つ上の行の数値の$7$ビット目が$1$ならば（つまり$128$以上ならば）$2^4+2^3+2^2+2^0 = 29$ との排他的論理和を BITXOR 関数で入れます。これをべき表現$254$の行まで繰り返すと、対応表が出来上がります。
この対応表はべき表現順に並んでいますので、これを丸ごとコピーして値ペーストし、左右を入れ替えてベクトル表現順に並べ替えた対応表も作っておきます。
言葉ではわかりにくいので、これらの対応表を LibreOffice で作ったものをここにアップロードします。ダウンロードしてセル内の数式を確認してください。Excelでも開けます。
対応表ができあがったら、これは一つのシートとして置いておき（シート名を「対応表」とします）、本番の計算は同じファイルの別シートで行うのが便利です。
例として、セルA1とセルB1にベクトル表現で表した数値が入っており、これらの $F_{256}$ としての和、差、積、商を返す計算式は次のようになります。
和については先ほど登場した BITXOR 関数を使って
=BITXOR(A1,B1)
となります。この関数は引数の数値を$2$進法のビット列とみなして各ビット毎に排他的論理和をとる関数です。
差については標数が$2$なので和と全く同じ
=BITXOR(A1,B1)
となります。
積については、べき表現だと単に足し合わせて$255$の剰余をとるだけなので、ここで先ほど作った対応表を使ってベクトル表現からべき表現に変換し、足し合わせて$255$の剰余をとり、結果をまた対応表でべき表現からベクトル表現に戻せばできあがりです。これらの変換には、みんな大好き VLOOKUP 関数が使えます。実際に書き下すと、
=VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)
となります（対応表のセル範囲はアップロードしたファイルに対応しています）。ただし引数がどちらも$0$でなければこれで良いのですが、どちらかが$0$だとエラーが出てしまいますので、複雑にはなりますが IF 関数を使って、
=IF(A1=0,0,IF(B1=0,0,VLOOKUP(MOD(VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)
+VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE),255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば完璧です。
商については、積の場合の指数の和を差に変えれば良いので、例えば、
=IF(B1=0,"ゼロ除算エラー",IF(A1=0,0,VLOOKUP(MOD(
VLOOKUP(A1,$対応表.$D$7:$E$262,2,FALSE)-VLOOKUP(B1,$対応表.$D$7:$E$262,2,FALSE)
,255),$対応表.$A$7:$B$261,2,FALSE)))
とすれば良いでしょう。
（続く）（前記事）
有限体の勉強 〜リード・ソロモン符号の誤り訂正の原理〜 [数学]
前回の記事で、リード・ソロモン符号の符号化と誤り訂正のシミュレーションをしてみました。その中で、誤り訂正についてはWikipediaの記事どおりにやってみただけで、その原理についてはまだ理解していませんでした。今回それを若干理解できたつもりになったので紹介します。
符号化に使う有限体（ガロア体）は前回の記事どおり $F_{256}$ とし、原始元$\alpha$も前回どおり、誤りシンボルの最大数も $t=2$ として、生成多項式 $G(X)$ についても前回使った
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) \]
を使います（生成多項式はもう少し一般化できますが、そこは省略します）。$t$が大きくなると、この後に出てくる行列のサイズが大きくなりますが、原理は同じです。
送信するシンボル数を冗長化符号も含めて$N$とすると、符号多項式 $C(X)$ の次数は $N-1$ です。$C(X)$ はその作り方から生成多項式 $G(X)$ で整除できるので、
\[ C(\alpha^0) = C(\alpha^1) = C(\alpha^2) = C(\alpha^3) = 0 \]
が成り立ちます。
ここで、通信路上で誤りが生じて最大$2$シンボルの誤りが生じたとします。このとき受信した多項式 $Y(X)$ は、
\begin{eqnarray*}
Y(X) &=& C(X) + E(X) \\
E(X) &=& e_1X^{m_1} + e_2X^{m_2} \quad (\, 0 \le m_1 \le m_2 \le N-1\,)
\end{eqnarray*}
と表せます。この $E(X)$ が求まると $C(X)$ が復元できることになります。誤りシンボル数がちょうど$2$個なら $e_1 \neq 0, e_2 \neq 0, m_1 \neq m_2$ 、$1$個ならば $e_1 \neq 0, e_2=0$ 、$0$個ならば $e_1=e_2=0$ と考えます。
そこで、まずシンドロームと呼ばれる次の値を $Y(X)$ から計算します。なお、これから出てくる計算は当然ながら全て有限体 $F_{256}$ 上での四則演算です。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& E(\alpha^0) &=& e_1+e_2 \\
S_2 &=& Y(\alpha^1) &=& E(\alpha^1) &=& e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
S_3 &=& Y(\alpha^2) &=& E(\alpha^2) &=& e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
S_4 &=& Y(\alpha^3) &=& E(\alpha^3) &=& e_1\alpha^{3m_1}+e_2\alpha^{3m_2}
\end{eqnarray*}
ここで、実際に生じた誤りのシンボル数を$k$個とし、まず $k=2$ と仮定します。そして誤り位置多項式を、
\[ \sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) = 1 + \sigma_1X + \sigma_2X^2 \]
と定義します。この $\sigma(X)$ の係数 $\sigma_1, \sigma_2$ が具体的に求まれば、
\[ \sigma(\alpha^{-m_1}) = \sigma(\alpha^{-m_2}) = 0 \tag{1} \]
かつ、上記以外の $\alpha^m$ に対しては $\sigma(\alpha^m) \neq 0$ なので、$m$を$0$から $-(N-1)$ まで動かして上記の代入計算をすれば誤り位置 $m_1,m_2$ が求まります。そこで $\sigma_1, \sigma_2$ の求め方ですが、上記$(1)$より
\begin{eqnarray*}
1 + \sigma_1\alpha^{-m_1} + \sigma_2\alpha^{-2m_1} &=& 0 \\
1 + \sigma_1\alpha^{-m_2} + \sigma_2\alpha^{-2m_2} &=& 0
\end{eqnarray*}
が成り立つので、変形すると
\begin{eqnarray*}
\alpha^{m_1}\sigma_1 + \sigma_2 &=& \alpha^{2m_1} \\
\alpha^{m_2}\sigma_1 + \sigma_2 &=& \alpha^{2m_2}
\end{eqnarray*}
になります（標数$2$なので係数の$-$は$+$に置き換えできます）。これは行列でかくと、
\begin{equation*}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\tag{2}
\end{equation*}
となります。
一方、シンドロームについて、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1\alpha^{m_1}+e_2\alpha^{m_2} & e_1+e_2 \\
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} & e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\tag{3}
\end{eqnarray*}
が成り立つので、これと$(2)$より、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
e_1\alpha^{3m_1}+e_2\alpha^{3m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\tag{4}
\end{eqnarray*}
が得られます。$(3)$より行列式を計算すると、
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
=
\begin{vmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{vmatrix}
\begin{vmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{vmatrix}
= e_1e_2(\alpha^{m_2}-\alpha^{m_1})(\alpha^{m_1}-\alpha^{m_2}) \neq 0
\tag{5}
\end{equation*}
と$0$でなく、$S_1 \sim S_4$ は既知なので、$(4)$を解いて $\sigma_1, \sigma_2$ を求めることができます。
これから先述の方法で $m_1, m_2$ が求まるので、シンドロームの定義式から得られる、
\begin{equation*}
\begin{bmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
e_1 \\
e_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_1 \\
S_2 \\
\end{bmatrix}
\end{equation*}
を解いて $e_1, e_2$ を求めることができます。この計算も
\begin{equation*}
\begin{vmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{vmatrix}
= \alpha^{m_2}-\alpha^{m_1} \neq 0
\end{equation*}
と行列式が$0$でないので可能です。これで無事に $E(X)$ を求めることができたので、誤り訂正ができました。
誤りシンボル数が $k<2$ のときは、$(5)$の行列式が$0$になるのでその判定ができて、計算がもっと簡単になります。
ここまでWikipediaに載っていたピーターソン法について、その誤り訂正の原理を紹介しました。しかしこの方法は「訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある」ということだそうです。
そこで以下、より計算量の少ない方法であるユークリッド法について、J-Stageから閲覧できる開発者である平澤らの論文を参考にして、簡単に紹介します。
誤りシンボル数の最大値は一般化して$t$とし、生成多項式を
\[ G(X) = (X - \alpha^0)(X - \alpha^1) \cdots (X - \alpha^{2t}) \]
として、これから生成された $N-1$ 次の符号多項式 $C(X)$ が送信され、受信側では$k$個 $(k \le t)$ のシンボルに誤りが生じた受信多項式 $Y(X)$ を受信したとします。誤り多項式 $E(X) = Y(X) - C(X)$ を
\[ E(X) = e_1X^{m_1} + e_2X^{m_2} + \cdots + e_kX^{m_k} \quad (\, 0 \le m_1 < m_2 < \cdots < m_k \le N-1\,)\]
とすると、誤り訂正の目的はこの $E(X)$ を具体的に求めることです。
まず、$Y(X)$ からシンドローム
\[ S_j = Y(\alpha^{j-1}) \quad (j=1,2, \cdots, 2t) \]
を計算し、これらを係数とする次のシンドローム多項式 $S(X)$ を定義します。
\[ S(X) = S_1 + S_2X + S_3X^2 + \cdots + S_{2t}X^{2t-1} \]
このとき、各シンドロームの値について、
\[ S_j = E(\alpha^{j-1}) = e_1\alpha^{(j-1)m_1} + e_2\alpha^{(j-1)m_2} + \cdots + e_k\alpha^{(j-1)m_k} \quad (j=1,2, \cdots, 2t) \]
が成り立つので、$S(X)$ は次のように変形できます。
\[ S(X) = \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \]
次に、誤り位置多項式 $\sigma(X)$ を次によって定義します。
\begin{equation*}
\sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) \cdots (1 - \alpha^{m_k}X)
\end{equation*}
ここまではピーターソン法と同じですが、ここで次の関係式
\begin{equation*}
(1 - \alpha^{m_i}X)(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) = 1 - \alpha^{2tm_i}X^{2t} \quad (i=1, \cdots, k)
\end{equation*}
が成り立つので、$\sigma(X)S(X)$ について、
\begin{eqnarray*}
\sigma(X)S(X) &=& \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \prod_{1 \le j \le k}(1 - \alpha^{m_j}X) \\
&=& \sum_{i=1}^k e_i(1 - \alpha^{2tm_i}X^{2t}) \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \\
&=& \phi(X)X^{2t} + \eta(X)
\end{eqnarray*}
すなわち
\[ \sigma(X)S(X) + \phi(X)X^{2t} = \eta(X) \tag{6} \]
と表せます。ここで $\eta(X)$ は
\[ \eta(X) = \sum_{i=1}^k e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \tag{7} \]
で定まる $k-1$ 次以下の多項式で、これを誤り数値多項式といいます。
従って、誤り訂正問題は既知の多項式 $S(X)$ と $X^{2t}$ から、$(6)$をみたす多項式 $\sigma(X)$ と $\eta(X)$ とを求める問題に帰着されることになります。これを解くには、$S(X)$ と $X^{2t}$ の最大公約多項式を求めるユークリッド互除法のアルゴリズムが使えます。これが「ユークリッド法」と名付けられている理由です。このアルゴリズムはピーターソン法に比べて高速です。
$\eta(X)$ の次数が $k-1$ 次以下で $k \le t$ を前提としているので、ユークリッド互除法の剰余多項式の次数が $t-1$ 以下になれば、そこで停止すれば良いことになります。
この方法で $\sigma(X)$ と $\eta(X)$ が具体的に求まれば、まず誤りシンボル数 $k$ は $\sigma(X)$ の次数であり、誤り位置 $m_i$ は $\sigma(X)$ からピーターソン法と同様に
\[ \sigma(\alpha^{-m_i}) = 0 \quad (i=1, \cdots, k) \]
をみたす$k$個の指数が最大$N$回の代入によって求まります。
誤り数値 $e_i$ については、$(7)$に $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入して、
\[ \eta(\alpha^{-m_i}) = e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \tag{8} \]
から求まりますが、計算をもっと簡単にするためには、$\sigma(X)$ の形式微分
\[ \sigma'(X) = - \sum_{i=1}^k \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \]
をとって、これに $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入すると、
\[ \sigma'(\alpha^{-m_i}) = \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \]
となるので、これと$(8)$より
\[ e_i = \frac{ \alpha^{m_i} \eta(\alpha^{-m_i}) }{ \sigma'(\alpha^{-m_i}) } \quad (i=1, \cdots, k) \]
によっても求まります。なお、$\sigma(X)$ の形式微分は具体的には、
\[ \sigma(X) = 1 + \sigma_1X + \sigma_2X^2 + \cdots + \sigma_kX^k \]
に対して
\[ \sigma'(X) = \sigma_1 + 2\sigma_2X + \cdots + k\sigma_kX^{k-1} \]
ですが、標数$2$なので$k$が偶数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_{k-1}X^{k-2} \]
$k$が奇数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_kX^{k-1} \]
となります。
以上で受信多項式 $Y(X)$ から誤り多項式 $E(X)$ が具体的に求められたので、誤り訂正ができました。
巧妙すぎて頭がクラクラしそうです。感動しました。
（続く）（前記事）
符号化に使う有限体（ガロア体）は前回の記事どおり $F_{256}$ とし、原始元$\alpha$も前回どおり、誤りシンボルの最大数も $t=2$ として、生成多項式 $G(X)$ についても前回使った
\[ G(X) = (X-\alpha^0)(X-\alpha^1)(X-\alpha^2)(X-\alpha^3) \]
を使います（生成多項式はもう少し一般化できますが、そこは省略します）。$t$が大きくなると、この後に出てくる行列のサイズが大きくなりますが、原理は同じです。
送信するシンボル数を冗長化符号も含めて$N$とすると、符号多項式 $C(X)$ の次数は $N-1$ です。$C(X)$ はその作り方から生成多項式 $G(X)$ で整除できるので、
\[ C(\alpha^0) = C(\alpha^1) = C(\alpha^2) = C(\alpha^3) = 0 \]
が成り立ちます。
ここで、通信路上で誤りが生じて最大$2$シンボルの誤りが生じたとします。このとき受信した多項式 $Y(X)$ は、
\begin{eqnarray*}
Y(X) &=& C(X) + E(X) \\
E(X) &=& e_1X^{m_1} + e_2X^{m_2} \quad (\, 0 \le m_1 \le m_2 \le N-1\,)
\end{eqnarray*}
と表せます。この $E(X)$ が求まると $C(X)$ が復元できることになります。誤りシンボル数がちょうど$2$個なら $e_1 \neq 0, e_2 \neq 0, m_1 \neq m_2$ 、$1$個ならば $e_1 \neq 0, e_2=0$ 、$0$個ならば $e_1=e_2=0$ と考えます。
そこで、まずシンドロームと呼ばれる次の値を $Y(X)$ から計算します。なお、これから出てくる計算は当然ながら全て有限体 $F_{256}$ 上での四則演算です。
\begin{eqnarray*}
S_1 &=& Y(\alpha^0) &=& E(\alpha^0) &=& e_1+e_2 \\
S_2 &=& Y(\alpha^1) &=& E(\alpha^1) &=& e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
S_3 &=& Y(\alpha^2) &=& E(\alpha^2) &=& e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
S_4 &=& Y(\alpha^3) &=& E(\alpha^3) &=& e_1\alpha^{3m_1}+e_2\alpha^{3m_2}
\end{eqnarray*}
ここで、実際に生じた誤りのシンボル数を$k$個とし、まず $k=2$ と仮定します。そして誤り位置多項式を、
\[ \sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) = 1 + \sigma_1X + \sigma_2X^2 \]
と定義します。この $\sigma(X)$ の係数 $\sigma_1, \sigma_2$ が具体的に求まれば、
\[ \sigma(\alpha^{-m_1}) = \sigma(\alpha^{-m_2}) = 0 \tag{1} \]
かつ、上記以外の $\alpha^m$ に対しては $\sigma(\alpha^m) \neq 0$ なので、$m$を$0$から $-(N-1)$ まで動かして上記の代入計算をすれば誤り位置 $m_1,m_2$ が求まります。そこで $\sigma_1, \sigma_2$ の求め方ですが、上記$(1)$より
\begin{eqnarray*}
1 + \sigma_1\alpha^{-m_1} + \sigma_2\alpha^{-2m_1} &=& 0 \\
1 + \sigma_1\alpha^{-m_2} + \sigma_2\alpha^{-2m_2} &=& 0
\end{eqnarray*}
が成り立つので、変形すると
\begin{eqnarray*}
\alpha^{m_1}\sigma_1 + \sigma_2 &=& \alpha^{2m_1} \\
\alpha^{m_2}\sigma_1 + \sigma_2 &=& \alpha^{2m_2}
\end{eqnarray*}
になります（標数$2$なので係数の$-$は$+$に置き換えできます）。これは行列でかくと、
\begin{equation*}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
=
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\tag{2}
\end{equation*}
となります。
一方、シンドロームについて、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1\alpha^{m_1}+e_2\alpha^{m_2} & e_1+e_2 \\
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} & e_1\alpha^{m_1}+e_2\alpha^{m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\tag{3}
\end{eqnarray*}
が成り立つので、これと$(2)$より、
\begin{eqnarray*}
\begin{bmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{bmatrix}
\begin{bmatrix}
\sigma_1 \\
\sigma_2 \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
\alpha^{2m_1} \\
\alpha^{2m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
e_1\alpha^{2m_1}+e_2\alpha^{2m_2} \\
e_1\alpha^{3m_1}+e_2\alpha^{3m_2} \\
\end{bmatrix}
\\
\\
&=&
\begin{bmatrix}
S_3 \\
S_4 \\
\end{bmatrix}
\tag{4}
\end{eqnarray*}
が得られます。$(3)$より行列式を計算すると、
\begin{equation*}
\begin{vmatrix}
S_2 & S_1 \\
S_3 & S_2 \\
\end{vmatrix}
=
\begin{vmatrix}
e_1 & e_2 \\
e_1\alpha^{m_1} & e_2\alpha^{m_2} \\
\end{vmatrix}
\begin{vmatrix}
\alpha^{m_1} & 1 \\
\alpha^{m_2} & 1 \\
\end{vmatrix}
= e_1e_2(\alpha^{m_2}-\alpha^{m_1})(\alpha^{m_1}-\alpha^{m_2}) \neq 0
\tag{5}
\end{equation*}
と$0$でなく、$S_1 \sim S_4$ は既知なので、$(4)$を解いて $\sigma_1, \sigma_2$ を求めることができます。
これから先述の方法で $m_1, m_2$ が求まるので、シンドロームの定義式から得られる、
\begin{equation*}
\begin{bmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{bmatrix}
\begin{bmatrix}
e_1 \\
e_2 \\
\end{bmatrix}
=
\begin{bmatrix}
S_1 \\
S_2 \\
\end{bmatrix}
\end{equation*}
を解いて $e_1, e_2$ を求めることができます。この計算も
\begin{equation*}
\begin{vmatrix}
1 & 1 \\
\alpha^{m_1} & \alpha^{m_2} \\
\end{vmatrix}
= \alpha^{m_2}-\alpha^{m_1} \neq 0
\end{equation*}
と行列式が$0$でないので可能です。これで無事に $E(X)$ を求めることができたので、誤り訂正ができました。
誤りシンボル数が $k<2$ のときは、$(5)$の行列式が$0$になるのでその判定ができて、計算がもっと簡単になります。
ここまでWikipediaに載っていたピーターソン法について、その誤り訂正の原理を紹介しました。しかしこの方法は「訂正するシンボル数が多いときは計算量が増大するため大規模な復号には使えないという欠点がある」ということだそうです。
そこで以下、より計算量の少ない方法であるユークリッド法について、J-Stageから閲覧できる開発者である平澤らの論文を参考にして、簡単に紹介します。
誤りシンボル数の最大値は一般化して$t$とし、生成多項式を
\[ G(X) = (X - \alpha^0)(X - \alpha^1) \cdots (X - \alpha^{2t}) \]
として、これから生成された $N-1$ 次の符号多項式 $C(X)$ が送信され、受信側では$k$個 $(k \le t)$ のシンボルに誤りが生じた受信多項式 $Y(X)$ を受信したとします。誤り多項式 $E(X) = Y(X) - C(X)$ を
\[ E(X) = e_1X^{m_1} + e_2X^{m_2} + \cdots + e_kX^{m_k} \quad (\, 0 \le m_1 < m_2 < \cdots < m_k \le N-1\,)\]
とすると、誤り訂正の目的はこの $E(X)$ を具体的に求めることです。
まず、$Y(X)$ からシンドローム
\[ S_j = Y(\alpha^{j-1}) \quad (j=1,2, \cdots, 2t) \]
を計算し、これらを係数とする次のシンドローム多項式 $S(X)$ を定義します。
\[ S(X) = S_1 + S_2X + S_3X^2 + \cdots + S_{2t}X^{2t-1} \]
このとき、各シンドロームの値について、
\[ S_j = E(\alpha^{j-1}) = e_1\alpha^{(j-1)m_1} + e_2\alpha^{(j-1)m_2} + \cdots + e_k\alpha^{(j-1)m_k} \quad (j=1,2, \cdots, 2t) \]
が成り立つので、$S(X)$ は次のように変形できます。
\[ S(X) = \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \]
次に、誤り位置多項式 $\sigma(X)$ を次によって定義します。
\begin{equation*}
\sigma(X) = (1 - \alpha^{m_1}X)(1 - \alpha^{m_2}X) \cdots (1 - \alpha^{m_k}X)
\end{equation*}
ここまではピーターソン法と同じですが、ここで次の関係式
\begin{equation*}
(1 - \alpha^{m_i}X)(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) = 1 - \alpha^{2tm_i}X^{2t} \quad (i=1, \cdots, k)
\end{equation*}
が成り立つので、$\sigma(X)S(X)$ について、
\begin{eqnarray*}
\sigma(X)S(X) &=& \sum_{i=1}^k e_i(1 + \alpha^{m_i}X + \alpha^{2m_i}X^2 + \cdots + \alpha^{(2t-1)m_i}X^{2t-1}) \prod_{1 \le j \le k}(1 - \alpha^{m_j}X) \\
&=& \sum_{i=1}^k e_i(1 - \alpha^{2tm_i}X^{2t}) \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \\
&=& \phi(X)X^{2t} + \eta(X)
\end{eqnarray*}
すなわち
\[ \sigma(X)S(X) + \phi(X)X^{2t} = \eta(X) \tag{6} \]
と表せます。ここで $\eta(X)$ は
\[ \eta(X) = \sum_{i=1}^k e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \tag{7} \]
で定まる $k-1$ 次以下の多項式で、これを誤り数値多項式といいます。
従って、誤り訂正問題は既知の多項式 $S(X)$ と $X^{2t}$ から、$(6)$をみたす多項式 $\sigma(X)$ と $\eta(X)$ とを求める問題に帰着されることになります。これを解くには、$S(X)$ と $X^{2t}$ の最大公約多項式を求めるユークリッド互除法のアルゴリズムが使えます。これが「ユークリッド法」と名付けられている理由です。このアルゴリズムはピーターソン法に比べて高速です。
$\eta(X)$ の次数が $k-1$ 次以下で $k \le t$ を前提としているので、ユークリッド互除法の剰余多項式の次数が $t-1$ 以下になれば、そこで停止すれば良いことになります。
この方法で $\sigma(X)$ と $\eta(X)$ が具体的に求まれば、まず誤りシンボル数 $k$ は $\sigma(X)$ の次数であり、誤り位置 $m_i$ は $\sigma(X)$ からピーターソン法と同様に
\[ \sigma(\alpha^{-m_i}) = 0 \quad (i=1, \cdots, k) \]
をみたす$k$個の指数が最大$N$回の代入によって求まります。
誤り数値 $e_i$ については、$(7)$に $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入して、
\[ \eta(\alpha^{-m_i}) = e_i \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \tag{8} \]
から求まりますが、計算をもっと簡単にするためには、$\sigma(X)$ の形式微分
\[ \sigma'(X) = - \sum_{i=1}^k \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}X) \]
をとって、これに $\alpha^{-m_i} \ (i=1, \cdots, k)$ を代入すると、
\[ \sigma'(\alpha^{-m_i}) = \alpha^{m_i} \prod_{1 \le j \le k, i \neq j}(1 - \alpha^{m_j}\alpha^{-m_i}) \quad (i=1, \cdots, k) \]
となるので、これと$(8)$より
\[ e_i = \frac{ \alpha^{m_i} \eta(\alpha^{-m_i}) }{ \sigma'(\alpha^{-m_i}) } \quad (i=1, \cdots, k) \]
によっても求まります。なお、$\sigma(X)$ の形式微分は具体的には、
\[ \sigma(X) = 1 + \sigma_1X + \sigma_2X^2 + \cdots + \sigma_kX^k \]
に対して
\[ \sigma'(X) = \sigma_1 + 2\sigma_2X + \cdots + k\sigma_kX^{k-1} \]
ですが、標数$2$なので$k$が偶数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_{k-1}X^{k-2} \]
$k$が奇数の場合は
\[ \sigma'(X) = \sigma_1 + \sigma_3X^2 + \cdots + \sigma_kX^{k-1} \]
となります。
以上で受信多項式 $Y(X)$ から誤り多項式 $E(X)$ が具体的に求められたので、誤り訂正ができました。
巧妙すぎて頭がクラクラしそうです。感動しました。
（続く）（前記事）
有限体の勉強 〜リード・ソロモン符号のシミュレーション〜 [数学]
有限体の勉強を始めてちょっとわかった気になってきましたが、ここで有限体の応用の一つである「誤り訂正符号」、その中でも誤り訂正能力が高い方式である「リード・ソロモン符号」について、その原理をシミュレートしてみたいと思います。
誤り訂正能力がどのくらい高いのかというと、
「送りたいシンボルに2t個の冗長なシンボルを追加するだけで、t個までならどのシンボルにどんな誤りが生じても正しく復元することができる」
というくらい高いのです。QRコードがある程度まで汚損しても正しく読み取れるのはこの符号方式を使っているからであり、他にもCDや衛星通信など様々な場面で使われています。
このリード・ソロモン符号については、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}$ の元はべき表現で扱うことを基本とするので、乗法演算は指数を足し合わせて$\mod 255$ をとることで行えます。加法演算はちょっと手間ですが、変換表を用いてベクトル表現にしてから各ビット毎にXORを取って、再び変換表を用いてべき表現にすれば求まります。実際にはこれらの計算は全部スプレッドシート上で関数を駆使して行いました。
では、実際に文字列 "Hello!" をリード・ソロモン符号で符号化し、通信路上で生じた誤りが受信側で復元できることを見てみましょう。以下ではWikipediaの記事の方法に従ってシミュレートします。
リード・ソロモン符号では、符号を $F_{256}$ の元を係数とする多項式で表します。"Hello!" の6文字をASCIIコード16進で表すと、
となりますが、これを $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$までのどのような数字を入れても、復号した緑のセルは元の青いセルの値が正しく表示されることが確認できると思います。
有限体の四則演算が自由自在にできることを利用した巧妙な符号化方式であることが実感できました。考えた人（リードさんとソロモンさん）は天才ですね。
（続く）（前記事）
誤り訂正能力がどのくらい高いのかというと、
「送りたいシンボルに2t個の冗長なシンボルを追加するだけで、t個までならどのシンボルにどんな誤りが生じても正しく復元することができる」
というくらい高いのです。QRコードがある程度まで汚損しても正しく読み取れるのはこの符号方式を使っているからであり、他にもCDや衛星通信など様々な場面で使われています。
このリード・ソロモン符号については、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$までのどのような数字を入れても、復号した緑のセルは元の青いセルの値が正しく表示されることが確認できると思います。
有限体の四則演算が自由自在にできることを利用した巧妙な符号化方式であることが実感できました。考えた人（リードさんとソロモンさん）は天才ですね。
（続く）（前記事）
