誤り位置多項式の根を求める回路

誤り訂正において、誤り位置多項式$${\sigma(x)}$$の根を求めると誤りのあるシンボルの位置が分かるのだった。今まで根の求め方としては代入するほかないと書いていたが、代入して根を求める操作を回路にする方法としてChien Search(Chain Searchではない)がある。本noteではChien Searchを記載する。

t個の誤りがあるときの誤り位置多項式は

$$
\sigma(x) =\sigma_0 + \sigma_1x + \cdots + \sigma_tx^t 
$$

とかける。これに$${GF(2^m)}$$の元$${\alpha^i}$$を代入していって、$${\sigma(\alpha^i)=0}$$となるものを見つける。まず$${\alpha^i}$$を代入した時

$$
\sigma(\alpha^i) =\sigma_0 + \sigma_1\alpha^i + \sigma_1(\alpha^i)^2 + \cdots + \sigma_t (\alpha^i )^t \\
$$

これを求める計算を愚直にやるとすると、まず各行の$${\alpha}$$をべき表現の指数に変換して、指数を乗算して累乗時の指数を得る。次に係数$${\sigma_j}$$との積を得るため、係数を指数に変換して、指数同士の加算を行う。そして得られた和項の指数をベクトル表現に戻して、すべての和項を排他的論理和で足し合わせる。
以前の記事で乗算器を作ってしまった方が速いとしていたのは、エンコーダは片側定数の乗算だったからであった。今回は累乗が必要なのでそのあたりあまり自明ではないとはいえるだろう。

さてChien Searchでは、まず$${\gamma_{j,i}}$$は$${\sigma_j (\alpha^i)^j}$$として、誤り位置多項式を

$$
\sigma(\alpha^i) =\gamma_{0, i} + \gamma_{1, i} + \gamma_{2, i} + \cdots + \gamma_{t, i}
$$

と表す。

すると、$${\alpha^i}$$の次の探索対象の元である$${\alpha^{i+1}}$$については、

$$
\sigma(\alpha^{i+1}) =\sigma_0 + \sigma_1\alpha^{i+1} + \sigma_1(\alpha^{i+1})^2 + \cdots + \sigma_t (\alpha^{i+1} )^t \\ 

\sigma(\alpha^{i+1}) =\gamma_{0, i+1} + \gamma_{1, i+1} + \gamma_{2, i+1} + \cdots + \gamma_{t, i+1}
$$

であるが、$${\gamma_{j,i+1} = \sigma_j (\alpha^{i+1})^j = \sigma_j (\alpha^{i})^j\alpha^j = \gamma_{j,i}\alpha^j}$$だから、実は各和項に$${\alpha^j}$$をかけていくだけで次の探索用の和項が揃うことが分かる。$${\alpha^j}$$は定数だから、乗算器は単純に構成できる

したがって根を求める回路の概観は次のようになる。

Chien Search

FFのボディに書いてあるのは初期値の表現である。各和項は初期値を$${\sigma(x)}$$の係数として、最初のサイクルで$${\alpha^1}$$を代入した場合の$${\sigma(x)}$$の値を得る。次のサイクルで$${\alpha^2}$$を代入した場合の$${\sigma(x)}$$の値を得る。$${\sigma(x)}$$がゼロになる根をt個見つけるまでこの回路を動作させればよい。