FPGA向きのFFTアルゴリズム - なひたふJTAG日記

今、FPGAでハードウェアFFTを行わなければならない案件を2つ抱えています。そのうちの1つは、65536ポイント～1Mポイント程度のFFTをつなぎ目なく行うというものです。 FFTのアルゴリズムですが、もっとも基本的な基数2のCooley-Tukeyアルゴリズムを考えてみます。 これは基数2の16ポイントFFTなので、ステージ0,1,2,3と4つあります。 ごく普通のFFTなのですが、これを65536ポイントや1Mポイントでやろうとした場合、厄介なことが生じます。それは、FFTする途中経過のデータを格納するアドレスが連続しないという問題です。 最初のステージでは、データの0と1、2と3・・を演算します。 次のステージでは、データの0と2、1と3・・を演算します。 ・・ だんだんバラバラになってきます。 1Mポイントとかとなると、 ・アドレス0とアドレス524288を計算 ・アドレス1とア