誤り数値の導出回路

前回のnoteの続き。

誤り数値はフォーニーの公式により

$$
e_{i_k} = \dfrac{\eta(\alpha^{-i_k})}{ \alpha^{-i_k}\sigma'(\alpha^{-i_k}) }
$$

と求められるのであった。ただし
$${i_k}$$：誤り位置
$${\alpha^{-i_k}}$$：誤りロケータ
$${\eta(x)}$$：誤り評価多項式
$${\sigma(x)}$$：誤り位置多項式

これらは誤り位置の導出と同時に行える。誤り位置導出のために誤り位置多項式の根を求めるのは、Chien Searchによって行えるのであった。回路を示す。

$${\Lambda(x)}$$は誤り位置多項式で$${\sigma(x)}$$に等しい。また、$${j = i_k}$$である。$${\gamma}$$は特に変更せずとも根を求める計算には関係ないのでそのまま用いられている。
Chien Searchでは、サイクルiにおいて$${\alpha^i}$$代入の誤り位置多項式の評価を行えるのであった。$${\gamma \Lambda_1}$$の列の結果は、誤り位置が求められたときは$${\gamma \Lambda_1 \alpha^{-j}}$$となっている。$${\Lamda'(x)}$$では奇数次数だけが次数を-1されて残るので、$${\Lamda'(x) = \Lamda_1}$$である。したがって、図に示すようにこの値はフォーニーの公式の分母($${\times \gamma}$$)に等しい値となる。

次に誤り数値を求める回路を示す。

先ほど求めたフォーニーの公式の分母の値の逆元を求めて、Chien Searchで評価した誤り評価多項式の値にかけていることが分かる。この2つの回路(誤り位置を求める回路と誤り数値を求める回路)は同時に実行できる。したがって、誤り位置多項式が求められた後は、ガロア体の位数だけのサイクル数で誤り数値を求められる。

補足として、誤り位置多項式の次数がもっと多い場合にも$${\alpha^{-i_k}\sigma'(\alpha^{-i_k})}$$の求め方が単純であるかを確認しよう。$${x^3}$$の微分は$${x^2}$$であるから、$${\alpha^{-i_k}\sigma'(\alpha^{-i_k})}$$の$${x^3}$$項成分は$${\gamma \sigma_3 (\alpha^{-j})^2\alpha^{-j}=\gamma \sigma_3 (\alpha^{-j})^3}$$である。一方で、Chien Searchにおける部分的な評価値は$${\gamma \sigma_3 (\alpha^{3})^{-j}}$$となる。したがって、実は$${\alpha^{-i_k}\sigma'(\alpha^{-i_k})}$$は、Chien Searchの奇数次数の結果だけを排他的論理和すれば得られることが分かる。