3 日でわか(らせ)る符号理論(2 日目・夜の部第 2 部)

数学・代数

\mathbb{F}_{16} と BCH コードと誤りの訂正(続き)

2 ビット誤っていた場合

今度は i+1 ビット目と j+1 ビット目(i\neq j)が誤って送られた場合を考えます。このときは
H(\vec{a}+\vec{e_{i+1}}+\vec{e_{j+1}})=H\vec{e_{i+1}}+H\vec{e_{j+1}}=\begin{pmatrix}\alpha^i+\alpha^j\\\alpha^{3i}+\alpha^{3j}\end{pmatrix}
となります。以下、s_1=\alpha^i+\alpha^j,s_2=\alpha^{3i}+\alpha^{3j} とおきます。
\begin{align}s_2&=(\alpha^i)^3+(\alpha^j)^3\\&=(\alpha^i+\alpha^j)\{(\alpha^i)^2+\alpha^i\alpha^j+(\alpha^j)^2\}\\&=(\alpha^i+\alpha^j)\{(\alpha^i+\alpha^j)^2+\alpha^i\alpha^j\}\\&=s_1({s_1}^2+\alpha^i\alpha^j)\end{align}
故
\alpha^i\alpha^j=s_2/s_1+{s_1}^2
が成り立ちます。よって \alpha^i,\alpha^j は二次方程式
x^2+s_1 x+(s_2/s_1+{s_1}^2)=0
の解です。これを解けば \alpha^i,\alpha^j が求まり、どのビットが誤りかわかるので、訂正ができます。
二次方程式、と言っても、\mathbb{F}_{16} 係数の方程式ですから 2=0 の世界なので、通常の解の公式はもちろん使えません。以下、二つの実例で、実際のやり方を見てみましょう。
\vec{b}={}^t\begin{pmatrix}0&0&1&1&0&0&0&1&0&1&1&0&0&0&0\end{pmatrix}
が送られてきたとしましょう。このとき
H\vec{b}=\begin{pmatrix}\alpha^2+\alpha^3+\alpha^7+\alpha^9+\alpha^{10}\\\alpha^6+\alpha^9+\alpha^6+\alpha^{12}+1\end{pmatrix}=\begin{pmatrix}\alpha^3+\alpha\\\alpha^2\end{pmatrix}=\begin{pmatrix}\alpha^9\\\alpha^2\end{pmatrix}
となります。そして
\begin{align}s_2/s_1+{s_1}^2&=\alpha^2/\alpha^9+\alpha^{18}\\&=\alpha^8+\alpha^3\\&=\alpha^3+\alpha^2+1\\&=\alpha^{13}\end{align}
となるので、二次方程式
x^2+\alpha^9 x+\alpha^{13}=0
を解くことになります。\alpha^{i+j}=\alpha^{13} となる組み合わせを i=0,1,2,\dots と調べていくと
\alpha^2+\alpha^{11}=\alpha^3+\alpha=\alpha^9
となるので、x=\alpha^2,\alpha^{11} となることがわかりますので、3 ビット目と 12 ビット目が誤りで、正しくは
\vec{a}={}^t\begin{pmatrix}0&0&0&1&0&0&0&1&0&1&1&1&0&0&0\end{pmatrix}
となります。
もう一つ実例を計算しましょう。
\vec{b}={}^t\begin{pmatrix}1&0&1&1&1&0&1&1&0&0&0&1&0&0&0\end{pmatrix}
が送られてきたとしましょう。このとき
H\vec{b}=\begin{pmatrix}1+\alpha^2+\alpha^3+\alpha^4+\alpha^6+\alpha^7+\alpha^{11}\\1+\alpha^6+\alpha^9+\alpha^{12}+\alpha^3+\alpha^6+\alpha^3\end{pmatrix}=\begin{pmatrix}\alpha^2+\alpha+1\\\alpha^2\end{pmatrix}=\begin{pmatrix}\alpha^{10}\\\alpha^2\end{pmatrix}
となります。そして
\begin{align}s_2/s_1+{s_1}^2&=\alpha^2/\alpha^{10}+\alpha^{20}\\&=\alpha^7+\alpha^5\\&=\alpha^3+\alpha^2+1\\&=\alpha^{13}\end{align}
となるので、二次方程式
x^2+\alpha^{10}x+\alpha^{13}=0
を解くことになります。\alpha^{i+j}=\alpha^{13} となる組み合わせを i=0,1,2,\dots と調べていくと
\alpha^6+\alpha^7=\alpha^2+\alpha+1=\alpha^{10}
となるので、x=\alpha^6,\alpha^7 となることがわかりますので、7 ビット目と 8 ビット目が誤りで、正しくは
\vec{a}={}^t\begin{pmatrix}1&0&1&1&1&0&0&0&0&0&0&1&0&0&0\end{pmatrix}
となります。