FPGAで作るHyperFFTのアルゴリズム

FPGAでハードウェアFFTを行う回路を作りたいわけなのですが、事情により、0.8ms以内に32768ポイントのFFTを行わなければなりません。

32768ポイントのFFTは、245760回のバタフライ演算が必要ですが、クロック400MHzで1クロック=1演算として動かしたとしても614μ秒かかってしまいます。実際にはメモリの読み出しと書き込みが入るので、1クロックでメモリに読んだり書いたりした場合、2.4msかかってしまうことが予想されます。

普通にFFTをしていては絶対に間に合わないわけなのです。

FFTの計算上のボトルネックは何かを考えてみましょう。

よくある通常のFFT(時間軸間引き、Radix-2のクリーチューキー型)のアルゴリズムを考えてみます。

この例では16ポイントのFFTなので、ステージは4まであります。

• 最初のステージ
  • 隣のデータとバタフライ演算
  • 1回の繰り返しを8回繰り返す
• ステージ2
  • 2つ隣のデータとバタフライ演算
  • 2回の繰り返しを4回繰り返す
• ステージ3
  • 4つ隣のデータとバタフライ演算
  • 4回の繰り返しを2回繰り返す
• ステージ4
  • 8つ隣のデータとバタフライ演算
  • 8回の繰り返しを1回繰り返す

このようになります。

このアルゴリズムの欠点は2個あって、計測に応用するのであれば入力データは時系列でならんでいるから、ビットリバースを行うと時間がかかってしまいます。

また、大きなサイズのFFTでは、後ろのステージにいくほど計算すべきデータのアドレスが離れてしまうので、一度に読み出せなくなります。DDRメモリの読み出しなどでメモリの読み出し時間が長くなってしまいます。

読み出すべきアドレスがバラバラに変わるので、メモリのバス幅を広くしようとしても、複数のデータを同時に読み出すことができません。

メモリの利用効率が悪いので遅くなります。

最初の問題は、私が考えた改良型FFTのアルゴリズムを使うと、解決できます。

データの流れはこのようになるので、

すべてのステージで

• 隣のデータとバタフライ演算をする
• N/2離れたアドレスに書き込み

という、アドレスの規則性が出てきます。

常に隣合うデータを読み込んで計算すればよいので、バタフライ演算回路とメモリの関係は下の図のようになります。

J=A*W+B、K=A*W-B

というバタフライ演算を行う場合、演算結果のJとKを2つのブロックRAMに分けてかき、ブロックRAMから次のAとBを読み出す際には2倍のバス幅で読み出すことができます。

このため、メモリの利用効率が良くなり、バタフライ演算器を止めることなく回すことができます。

一方、計測データなど、入力データが時系列で並んでいる場合には、周波数間引きというアルゴリズムを使うと良いでしょう。

周波数間引きのアルゴリズムでは、入力は順番に並んでいて、結果がビットリバースになります。

周波数間引きの場合は、バタフライ演算の式は

J=A+B

K=(A-B)*W

となります。

上で紹介したアルゴリズムはFFTのための演算回数を減らすことはありませんでした。そのため、32768ポイントのFFTでは、依然として245760回のバタフライ演算が必要です。

この演算回数を劇的に減らすのがRadix-4やRadix-8という計算手法です。

普通のアルゴリズムで8ポイントのFFTをすると、2つのデータを12回のバタフライ演算で処理してやる必要がありました。

バタフライ演算は入力が決まってしまえば出力は一意に決まるので、この計算を8入力8出力の関数として考えることができます。

つまり、

ということです。

中間の結果をメモリにストア/ロードしなくてよいので、速くなります。

Radix2の場合のバタフライ演算量は 245760回で、メモリの読み書きが491520回必要だったので、400MHzでメモリを読み書きした場合は1.2msかかりましたが、

Radix8にすると、、バタフライ演算量は32768/8×5= 20480となって、メモリの読み書きが20480回になります。400MHzで動かし、1クロックで8個分のデータを一気に読みだせば、51usで計算できることになります。

なんと、24倍に高速化できる計算になります。

ただし、この高速化の恩恵を受けるには、8個分のデータを1クロックでメモリから取ってきたり、1クロックで書き込まなければならないので、通常のFFTのアルゴリズムではできません。私の考えた改良型FFTでなければ、メモリが詰まってしまうことになるでしょう。

やりたいことは、

• Radix-8で高速化し
• 改良型FFTで、メモリのボトルネックを解消し、
• 周波数間引きで、計測データを時間ロスせずに連続して変換する

ということです。

32768ポイントのFFTをわずか51μ秒で実行する超高速FFT。

はたして、できるでしょうか？