計算時間
うじのすけさんから計算時間についてコメントがありましたので、FFTの計算時間について書いておきます。FFTの計算時間はバタフライの"radix"（底）によって激変します。分かりやすいようにここではradix=2の場合について説明します。教科書で初頭向けに説明されているFFTはradix=2です。
FFTの基本演算はバタフライ演算です。これは二つの複素データを読み込んで、複素乗算を一回、複素加算を一回、複素減算を一回おこなう操作です。ここでFFTを定義すると
となります。ここでバタフライ演算の回数を計算するとN点に対して(N/2)log2(N)となります。これにバタフライ演算のサイクル数をかけると、ざっくりとしたステップ数を予測できます。
1024点のFFTについて計算してみましょう。(N/2)*log2(N)=5120です。Blackfinは最適化するとバタフライ・カーネルを3サイクルで実行できます。したがって、大雑把に言って15000サイクル程度で実行できると概算できます。
もちろん、これに対してループ・オーバーヘッドを追加しなければなりません。FFTは通常3重のループで構成します。そのオーバーヘッドは決して過小評価できません。一方で、バタフライ演算のうち(N/2)回分は複素乗算を省略できます。これはサイクル数を大きく削減できます。
これらを勘案すると、Blackfinの1024点複素FFTはおおよそ16000~17000サイクル程度までつめられるだろうと予想できます。昨日の「140000サイクルだと理想的な場合の1/10」というのは、やや過大評価です。すみません。
