問題タブ [kissfft]

Kiss_fftは非常に単純な FFT 実装です。ほぼ教科書です。FFT サイズを因数分解することにより、大きな DFT を繰り返し小さな FFT に分解します。基数 2、3、4、および 5 のバタフライ関数が最適化されています。

2、3、および 5 のバタフライは小さな素数であり、因数分解で一般的に見られますが、基数 4 のバタフライは最適化されたケースであり、基数 2 を 2 回使用する場合と比較して、いくつかの乗算を節約できます*。たとえば、32 ポイントの FFT の場合、サイズ 32 は 4x4x2 に分解されますkf_bfly4。kf_bfly2

kf_bfly2ただし、これはステージが 1 つしかないことを意味します。FFT サイズが 4 の倍数の場合、kf_bfly2ステージは 2 つではなく、1 つのkf_bfly4ステージになります。kf_bfly2また、これは、関数が長さ 1 の「配列」で機能することも意味します。

コードでは、宣言は

ここFoutで、 はサイズ の「配列」m、つまり常に 1 です。バタフライは をループします。Foutもちろん、コンパイラは数値解析を行って を表示することはできませんm==1。しかし、これは最後のバタフライなので、かなり頻繁に呼び出されます。

Q1)私の分析は正しいですか？kf_bfly2実際に呼び出されるのm==1は?

Q2)これが実際に最適化の失敗であると仮定すると、2 つの可能なアプローチがあります。mからパラメーターを削除するkf_bfly2か、因子分析を 2x4x4 のように因子 32 に変更することができます (kf_bfly2前に移動し、サイズ 4x4=16 の配列のトップ レベルで 1 回呼び出します)。何が一番いいでしょうか？

[*] 基数 4 のバタフライは、係数 +1、-1、+i、および -i を持つことになり、代わりに加算と減算として実装できます。kiss_fft の順方向と逆方向の基数 4 の計算が異なるのはなぜですか?を参照してください。