ユークリッド復号法のハードウェア実装

上記noteの続き。BBC WHP031を参照。

ユークリッド復号法の回路概要

この回路では下側が多項式除算器、上側が$${m_{22}}$$の計算回路となっている。各レジスタは以下のように使われる。

A: 除数
B: 被除数
C: 前回の$${m_{22}}$$
D: 今回の$${m_{22}}$$計算途中結果

初期値)
　Aレジスタにシンドローム多項式をセットする。
　Bレジスタに$${x^4}$$として最上位桁$${B_3}$$に1をセットする。
　Cレジスタに1をセットする
　Dレジスタに0をセットする

各ステップで$${B_3}$$を$${A_3}$$で割る。そのために$${A_3}$$の逆元を計算して(inv)、$${B_3}$$とかけている。その結果が上側の計算にも使用され、Bレジスタ(被除数)やDレジスタの中間値計算に使われる。

step1→step2)  
　$${B_3}$$を$${A_3}$$で割る値(X)の計算を行い、X$${\times}$$AとBのガロア体加算を行う。また、X$${\times}$$CとDのガロア体加算を行う。こうしたできた中間値がstep2においてセットされる（シフトされて）。
B←X$${\times}$$A$${\oplus}$$B
D←X$${\times}$$C$${\oplus}$$D

step2→step3)
　先ほど同様にXの値を求めて、次の値を求めるが、ここで除算は完了するので、セットされる対象が変わる。
A←X$${\times}$$A$${\oplus}$$B
B←A
C←X$${\times}$$C$${\oplus}$$D
D←C

step3→step4)
　同様にXの値を求めて、次の値を求める。中間値の計算なので次のように更新される。
B←X$${\times}$$A$${\oplus}$$B
D←X$${\times}$$C$${\oplus}$$D

step4での演算の結果剰余の次数がt=2より小さくなり、本回路の計算は終了する。

回路は$${A_3}$$が0の場合を省略しているが、少しの回路追加で対応可能である。

最後にstep4での演算の結果に対して定数項$${\gamma}$$の逆元をかけることで$${\sigma(x)}$$が得られる。また、Bレジスタの演算結果に同じく$${\gamma}$$の逆元をかけることで$${\eta}$$が得られる。

全乗算器

回路中で片側定数でない全乗算器が登場している。全乗算器は片側定数の時と同様の考えで回路化できる。

左から、初めのANDの各列は、$${b}$$の各桁の部分積を表してる。これがbの桁数である4列分ある。
AND列の右のXORの1列は、ガロア体の原始多項式に従ったキャリーの戻しを行う前の部分積の各桁ごとの値を求めている。
その右のXORの3列は、ガロア体の原始多項式に従ったキャリーの戻しを行い、各桁の最終的な演算結果を求めている。

逆元を求める回路

LUTを用いて逆元を求める。ほかの方法はBBC WHP031には示されていない。対応を組み合わせ回路のcase文として記述すれば最適化によってLUTを用いるより単純な回路が得られるのではないかと思う。