誤り訂正符号エンコーダの回路 乗算器のLUT実装
BBC WHP031では、乗算をLUTで行う方法が示されている。
ガロア体$${GF(2^4)}$$、原始多項式$${x^8+x^4+x^3+x^2+1}$$をシンボルとする(15,11)RS符号。生成多項式は$${x^4+15x^3+3x^2+x+12}$$。乗算器では最大次数以外の係数でかける必要があり、以下になる。
これをLUTを入力シンボルをインデックスとして答えを得ることもできる。
例えば入力シンボルとして9($${=1 \alpha^3 + 0\alpha^2 + 0\alpha + 1 = \alpha^{14}}$$)に対して$${\times15, \times3, \times1,\times12}$$を得るには、上から9番目のエントリを得ればよく、答えが14, 8, 9, 6が得られる。
このRS符号ではLUTは論理ゲートだけで行う方式に対して回路面積的に割りに合わない。単純な比較だが、使用されるMOSFETの数で比較しよう
LUT
6トランジスタセルのSRAMで実装したとしても、
4セル/シンボル/エントリ
4シンボル/エントリ
16エントリ
でアレイ部分だけで6 x 4 x 4 x 16 = 1536トランジスタ必要。デコーダやセンスアンプも含めるともっと多い。
論理ゲート
ゲート数11で1つあたり4トランジスタで実現できるから44トランジスタ必要。
では$${GF(2^m)}$$としてもっと巨大なガロア体を使うRS符号ならLUTの方が得になることがあるだろうか？
まず、乗算自体の数は生成多項式の最大次数を除いた項の数で決まるが、今回の比較に影響しないと考えて考慮しない。1シンボルはmビットになるから、論理ゲート方式だと、mビット入力で1ビット出力する任意の論理演算は2入力のゲートのトーナメント式の回路構造を想定すると、最大でも段数log2(m)、ゲート数はm-1あればできる。これがmビット分あり、各ゲートは4トランジスタでできるから、段数log2(m)、トランジスタ数は$${4(m-1)\times m}$$必要となる。
一方でLUT方式だと、エントリ数が$${2^m}$$。1エントリあたりのセルはm個。したがって、トランジスタ数は$${6\times 2^m \times m}$$必要となる。段数はSRAM読み出しなのでどのみち1クロックサイクル程度は必要になる。
というわけで、トランジスタ数や回路遅延的にはどうも規模的にスケールしないのはLUT方式に思える。
例えば、論理ゲート方式は配置配線が不透明であるから、配線できずに結局STAにメットしない場合はでてくるかもしれない。そういった時に配置配線は明確であるLUTが採用されるのかもしれない。この辺は良く分からない。