FFTのFPGAによる実装(改良版)
前項の実装では、バタフライ演算が2クロックに1回しか実行できないが、毎クロック実行できるように改良する。
◇
ボトルネックになっているのはRAMから1クロックに1ワードずつしか読み書きできない点なので、RAMを2個に分けて1クロックに2ワード読み書きできるようにすればよい。RAMの分け方は、データフロー図の上半分と下半分で分ける。
こうすると、バタフライ演算は、最後のステージ以外はそれぞれのRAM内で、最後のステージだけ2個のRAM間で実行することになる。
まずRAM内でバタフライ演算するときは、前項と同様でRAMから順に読み出した0番目と1番目のワードを横から縦にする。これを2個のRAMに対して交互にすれば、バタフライ演算が毎クロック実行できる。すなわちRAMから読み出す回路は次のようになる。
この回路では2行2列の転置をしているので、縦から横に戻すのも全く同じ回路で同じ動作をさせればよい。
次にRAM間でバタフライ演算するときは、それぞれのRAMの出力をそのままバタフライ演算のain,binとすればよいから、RAMから読み出す回路次のようになる。
RAMに書き込む回路もこれと同じでよい。
結局、バタフライ演算を毎クロック実行できるようにした改良版の回路は次のようになる。
◇◇
さらに高速化するためにバタフライ演算器を2個並列にするには、データフロー図を縦に4等分して4個のRAMに分ければできる。