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

$\mathbb{F}_{16}$ と BCH コードと誤りの訂正

さて、BCH コードを定める行列 $H$ に左から
$\begin{pmatrix}1&\alpha&\alpha^2&\alpha^3&0&0&0&0\\0&0&0&0&1&\alpha&\alpha^2&\alpha^3\end{pmatrix}$
を掛けると
$\begin{align}H&=\begin{pmatrix}1&\alpha&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&\alpha^7&\alpha^8&\alpha^9&\alpha^{10}&\alpha^{11}&\alpha^{12}&\alpha^{13}&\alpha^{14}\\1&\alpha^3&\alpha^6&\alpha^9&\alpha^{12}&1&\alpha^3&\alpha^6&\alpha^9&\alpha^{12}&1&\alpha^3&\alpha^6&\alpha^9&\alpha^{12}\end{pmatrix}\\&=\begin{pmatrix}1&\alpha&\cdots&\alpha^{14}\\1&\alpha^3&\cdots&\alpha^{3\cdot 14}\end{pmatrix}\end{align}$
となり、見通しが良くなります。

1 ビット誤っていた場合

BCH コード $\vec{a}$ に対して、 $i+1$ ビット目が誤って、 $\vec{a}+\vec{e_{i+1}}$ が送られてきたとすると
$H(\vec{a}+\vec{e_{i+1}})=H\vec{e_{i+1}}=\begin{pmatrix}\alpha^i\\\alpha^{3i}\end{pmatrix}$
となるので、誤りを検出し、かつ訂正ができます。
例として
$\vec{b}={}^t\begin{pmatrix}1&1&0&0&1&0&1&1&1&0&0&0&0&0&0\end{pmatrix}$
が送られてきたときを考えましょう。このとき
$H\vec{b}=\begin{pmatrix}1+\alpha+\alpha^4+\alpha^6+\alpha^7+\alpha^8\\1+\alpha^3+\alpha^{12}+\alpha^3+\alpha^6+\alpha^9\end{pmatrix}=\begin{pmatrix}\alpha\\\alpha^3\end{pmatrix}$
となるので、2 ビット目が誤っていることがわかります。従って正しいコードは
$\vec{a}={}^t\begin{pmatrix}1&0&0&0&1&0&1&1&1&0&0&0&0&0&0\end{pmatrix}$
です。