Reed-Solomon符号の符号化と復号法 特集CD-ROM(6)（月刊ASCII 1986年6月号11)

特集記事「CD-ROM　徹底研究 CD-ROMのすべて　第3回 デジタル信号処理」をスクラップして読み返す。難しい数式が出てきて手ごわい記事だ。理解できなくても良しとする。

Reed-Solomon符号の符号化と復号法
　CIRCは、最小距離^*2 5のReed-Solomon符号^*12系列(C₁,C₂)で構成される.
　Reed-Solomon符号の符号化と復号法は次のように行う。ただし,演算はGF(2⁸)で定義されており ${\alpha }^8+{\alpha }^4+{\alpha }^3+{\alpha }^2+1=0$ かつすべての計算はGF(2⁸)の有限体演算^*3である.
$\{\begin{array}{l}p+q+r+s=\sum _{i=4}^{n-1}{W}_i\\ {\alpha }^{3}p+{\alpha }^{2}q+2r+s=\sum _{i=4}^{n-1}{\alpha }^i{W}_i\\ {\alpha }^{6}p+{\alpha }^{4}q+{\alpha }^{2}r+s=\sum _{i=4}^{n-1}{\alpha }^{2i}{W}_i\\ {\alpha }^{9}p+{\alpha }^{6}q+{\alpha }^{3}r+s=\sum _{i=4}^{n-1}{\alpha }^{3i}{W}_i\end{array}$
となり,この4元連立方程式を解くと,p,q,r,sが求まる.
$\left(\left[\begin{array}{c}p\\ q\\ r\\ s\end{array}\right]\right)=\left(\left[\begin{array}{cccc}{\alpha }^{212}& {\alpha }^{153}& {\alpha }^{152}& {\alpha }^{209}\\ {\alpha }^{156}& {\alpha }^2& {\alpha }^{135}& {\alpha }^{152}\\ {\alpha }^{158}& {\alpha }^{138}& {\alpha }^2& {\alpha }^{153}\\ {\alpha }^{218}& {\alpha }^{158}& {\alpha }^{156}& {\alpha }^{212}\end{array}\right]\right)\left(\left[\begin{array}{}\sum _{i=4}^{n-1}{W}_i\\ \sum _{i=4}^{n-1}{W}_i\\ \sum _{i=4}^{n-1}{W}_i\\ \sum _{i=4}^{n-1}{W}_i\end{array}\right]\right)$
ただし $(\begin{array}{l}{C}_1·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}n=32\\ C_2·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}n=28\end{array}$
このようにパリティを作ると当然次式が成立する。
${\displaystyle \sum _{i=0}^{n-1}{W}_i=\sum _{i=0}^{n-1}{\alpha }^i{W}_i=\sum _{i=0}^{n-1}{\alpha }^{2i}{W}_i=\sum _{i=0}^{n-1}{\alpha }^{3i}{W}_i=0}$
復号は次のように行う.まずシンドローム^*4を生成する。
$\begin{array}{lll}{S}_0& =& \sum _{i=0}^{n-1}\widehat{W_i}\\ S_1& =& \sum _{i=0}^{n-1}{\alpha }^i\widehat{W_i}\\ S_2& =& \sum _{i=0}^{n-1}{\alpha }^{2i}\widehat{W_i}\\ S_3& =& \sum _{i=0}^{n-1}{\alpha }^{3i}\widehat{W_i}\end{array}$
ここで, $C_1·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}n=32,C_2·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}·\hspace{0.5em}n=28,\widehat{W_i}$ :受信データで2シンボルエラーを想定すると,シンドロームは次のよう になる.ただし,2シンボルエラーをe_i,e_j,とする.
$\begin{array}{lll}{S}_0& =& e_i+e_j\\ S_1& =& {\alpha }^i{e}_i+{\alpha }^j{e}_j\\ S_2& =& {\alpha }^{2i}{e}_i+{\alpha }^{2j}{e}_j\\ S_3& =& {\alpha }^{3i}{e}_i+{\alpha }^{3j}{e}_j\end{array}$
$\begin{array}{lll}{C}_1の時& ：& 0\leqq i,j\leqq 31\\ C_2の時& ：& 0\leqq i,j\leqq 27\end{array}$
上式より,
$\begin{array}{lll}{\alpha }^i{S}_0+S_1& =& \left({\alpha }^i+{\alpha }^j\right)e_j\\ {\alpha }^i{S}_1+S_2& =& {\alpha }^j\left({\alpha }^i+{\alpha }^j\right)e_j\\ {\alpha }^i{S}_2+S_3& =& {\alpha }^{2j}\left({\alpha }^i+{\alpha }^j\right)e_j\end{array}$
$\therefore \hspace{0.5em}\left({\alpha }^i{S}_0+S_1\right)\left({\alpha }^i{S}_2+S_3\right)={\left({\alpha }^i{S}_1+S_2\right)}^2$
展開すると次のようなエラーロケーション方程式が得られる.
$\left(S_0{S}_2+{S_1}^2\right){\alpha }^{2i}+\left(S_1{S}_2+S_0{S}_3\right){\alpha }^i+\left(S_1{S}_2+{S_2}^2\right)=0$
ここで
$\begin{array}{lll}{S}_0{S}_2+{S_1}^2& =& A\\ S_1{S}_2+S_0{S}_3& =& B\\ S_1{S}_3+{S_2}^2& =& C\end{array}$
とおくと,次のような方法により2シンボルエラー訂正ができる.まず,エラーの大きさを判定する.
(i)　n₀エラー
$S_0=0\; ,S_3=0\; ,A=B=C=0$
(ii)　1シンボルエラー
$S_0\ne 0\; ,S_3\ne 0\; ,A=B=C=0$
(iii)　2シンボルエラー
$A\ne 0,B\ne 0,C=0$
訂正手続きは次のように行う.
(i)　1シンボルエラーエラー訂正
${\alpha }^i=\frac{S_1}{S_0},e_i=S_0$
ここで, $i=\log {\alpha }^i,{\alpha }^i={\log }^{-1i}$ と表すと,1シンボルエラーのロケーション: i は,
${\alpha }^i=\frac{S_1}{S_0}より\; ,i=\log \left(\frac{S_1}{S_0}\right)$
エラーデータe_iは,
$e_i=S_0$
訂正は,
$\widehat{W_i}=\widehat{W_i}+S_0$
とすればよい。

(ii)　2シンボルエラー訂正
この時のエラーロケーション方程式は,
$A{\alpha }^{2k}+B{\alpha }^k+C=0$
ここで,B/A=D,C/A=Eとおくと,
$D={\alpha }^i+{\alpha }^j,E={\alpha }^i·{\alpha }^j（ロケーション i,j）$
であり,
${\alpha }^{2k}+D{\alpha }^k+E=0$
　すなわち ${\alpha }^i,{\alpha }^j$ は2次方式の根になっている.
　今, $j=i+a（j>iでa>0）$ とすると、
$D={\alpha }^i\left(1+{\alpha }^a\right),E={\alpha }^{2i+a}$
この時,
$\frac{D^2}{E}=\frac{{\left(1+{\alpha }^a\right)}^2·{\alpha }^{2i}}{\left({\alpha }^a·{\alpha }^{2i}\right)}={\alpha }^{\mathrm{-a}}+{\alpha }^a$
となる。そこで,
$X=1+{\alpha }^a$
とすると,8 in 8 outのPLAで“ $\frac{D^2}{E}\to X\left(a=2\sim 31\right)$ "を構成できる.さらに,
$Y=\frac{D^2}{E}+X=1+{\alpha }^{\mathrm{-a}}$
とおくと,
${\alpha }^i=\frac{D}{X},{\alpha }^j=\frac{D}{Y}$
∴ $i=\log \left(\frac{D}{X}\right),j=\log \left(\frac{D}{Y}\right)$
よって,エラーデータ, $e_i,e_j$ は
$e^i=\frac{\left({\alpha }^j{S}_0+S_1\right)}{D}=\frac{S_0}{Y}+\frac{S_1}{D}$
$e^j=\frac{\left({\alpha }^i{S}_0+S_1\right)}{D}=\frac{S_0}{X}+\frac{S_1}{D}$
訂正は,
$W_i=\widehat{W_i}+e_i,W_j=\widehat{W_j}+e_j$
とすればよい.
　以上は、2シンボルエラー訂正の方法であるが,CIRCに使言われているReed-Solomon符号は、最小距離が5の符号であるから,エラーロケーションが分かれば4シンボルまで訂正できる.
　今,エラーロケーションを,
$i,j,k,l$
とすると
$\begin{array}{lll}{S}_0& =& e_i+e_j+e_k+e_l\\ S_1& =& {\alpha }^i{e}_i+{\alpha }^j{e}_j+{\alpha }^k{e}_k+{\alpha }^l{e}_l\\ S_2& =& {\alpha }^{2i}{e}_i+{\alpha }^{2j}{e}_j+{\alpha }^{2k}{e}_k+{\alpha }^{2l}{e}_l\\ S_3& =& {\alpha }^{3i}{e}_i+{\alpha }^{3j}{e}_j+{\alpha }^{3j}{e}_k+{\alpha }^{3j}{e}_l\end{array}$
上式を変形すると,
$e_i=\frac{S_0+\left({\alpha }^{-j}+{\alpha }^{-k}+{\alpha }^{-l}\right)S_1+\left({\alpha }^{-j-k}+{\alpha }^{-k-l}+{\alpha }^{-l-j}\right)S_2+{\alpha }^{-j-k-l}{S}_3}{\left(1+{\alpha }^{i-j}\right)\left(1+{\alpha }^{i-k}\right)\left(1+{\alpha }^{i-l}\right)}$
$e_j=\frac{S_0+\left({\alpha }^{-k}+{\alpha }^{-l}+{\alpha }^{-i}\right)S_1+\left({\alpha }^{-k-l}+{\alpha }^{-l-i}+{\alpha }^{-i-k}\right)S_2+{\alpha }^{-k-l-i}{S}_3}{\left(1+{\alpha }^{j-i}\right)\left(1+{\alpha }^{j-k}\right)\left(1+{\alpha }^{j-l}\right)}$
$e_k=\frac{S_0+\left({\alpha }^{-l}+{\alpha }^{-i}+{\alpha }^{-j}\right)S_1+\left({\alpha }^{-l-i}+{\alpha }^{-i-j}+{\alpha }^{-j-l}\right)S_2+{\alpha }^{-l-i-j}{S}_3}{\left(1+{\alpha }^{k-i}\right)\left(1+{\alpha }^{k-j}\right)\left(1+{\alpha }^{k-l}\right)}$
$e_l=\frac{S_0+\left({\alpha }^{-i}+{\alpha }^{-j}+{\alpha }^{-k}\right)S_1+\left({\alpha }^{-i-j}+{\alpha }^{-j-k}+{\alpha }^{-k-i}\right)S_2+{\alpha }^{-i-j-k}{S}_3}{\left(1+{\alpha }^{l-i}\right)\left(1+{\alpha }^{l-i}\right)\left(1+{\alpha }^{l-k}\right)}$
となり、エラーデータが求められるから、訂正は,
$\{\begin{array}{lll}{W}_i& =& \widehat{W_i}+e_i\\ W_j& =& \widehat{W_j}+e_j\\ W_k& =& \widehat{W_k}+e_k\\ W_l& =& \widehat{W_l}+e_l\end{array}$
とすればよい

数学は苦手で工学方面への進めなかった。このような数式で物事を考えることができる人たちを尊敬している。よく聞く学校での勉強は役に立たないという言はできない者の悔し紛れの捨て台詞だと思っている。
理解できなくとも数式が美しいということは感じられる。