フーリエ変換 FFT 時間間引き 周波数間引き 回転因子

FFTの、時間間引きアルゴリズムと周波数間引きアルゴリズムは、例えば、下記の書籍で解説されている。
佐川正彦、貴家仁志：高速フーリエ変換とその応用、1993、昭晃堂（解散）
三谷政昭：やり直しのための信号数学、2004、CQ出版社
時間間引きアルゴリズムは、信号系列を偶数番目と奇数番目に分けることで導かれ、バタフライ演算内で回転因子の乗算が先になる。最初の段における回転因子の乗算は実数（1）となる。
周波数間引きアルゴリズムは、信号系列を前半部分と後半部分に分けることで導かれ、バタフライ演算内で回転因子の乗算が後になる。最後の段における回転因子の乗算は実数（1）となる。

回転因子乗算段とバタフライ演算段のルーチンを分けて考えると、バタフライ演算段は対象となる組み合わせが異なるだけで回転因子乗算段は共通にも見える。バタフライ演算段の間に回転因子乗算段を挟んでメモリアクセスに注意すれば、時間間引きアルゴリズムと周波数間引きアルゴリズムを共通なプログラムにできるかもしれない。

時間間引きアルゴリズムと周波数間引きアルゴリズムは、どちらも Cooley-Tukey のアルゴリズムとして解説されることが多いが、周波数間引きアルゴリズムは Gentleman-Sande のアルゴリズムとも呼ばれるようである。
吉澤正：高速フーリエ変換とその応用、計測と制御、Vol.8 、No.12、pp.851-860、1969→J-STAGE（PDF）
尾上守夫：直交変換技術－高速フーリエ変換を中心に－、テレビジョン、Vol.31、No.9、pp.712-721、1977→J-STAGE（PDF）
James W. Cooley, John W. Tukey : An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation, Vol.19, No.90, pp.297-301, 1965→American Mathematical Society（PDF）
W. M. Gentleman, G. Sande : Fast Fourier Transforms for fun and profit, Proceedings of 1966 Fall Joint Computer Conference, American Federation of Information Processing Societies Conference Proceedings, Vol.29, pp.563-578, 1966→SemanticScholar（PDF）

Cooley-Tukey や Gentleman-Sande のような in place 型ではないアルゴリズムには、Stockham のアルゴリズムがある。
金田康正：並列数値処理、並列数値処理シリーズ9、2010、コロナ社
T. G. Stockham : High-speed convolution and correlation, Proceedings of 1966 Spring Joint Computer Conference, American Federation of Information Processing Societies Conference Proceedings, Vol.28, pp.229-233, 1966
noise-計算機科学や各種設定のメモ：Stockham アルゴリズムについて

るまぶろぐ-tomorinao：色んな人のFFT