論文・文献徘徊メモ 160219-1 Pease FFT / Korn–Lambiotte FFT
FFTといえば,
Cooley–Tukey FFTが一番有名で, Stockham FFTが二番であろうと思います.
工学書を覗いてみると, だいたいここ2つではないでしょうか.
Cooley–Tukeyはわかりやすいとして, Stockhamはぎょっとします.
Webサイトによっては, よくよく線を辿ってみると不完全なものもありました.
そんなわけで, Stockhamの正しそうでわかりやすい説明を探し求めてみたわけです.
すると, Stockhamよりも一見してわかりやすそうな別のFFTに出会いました.
それが, Pease FFT と Korn–Lambiotte FFTでした.
Pease FFT が載っている文献
https://users.ece.cmu.edu/~franzf/papers/fft-enc11.pdf
http://csg.csail.mit.edu/Dataflow/talks/HoeTalk.pdf
Korn–Lambiotte FFT が載っている文献
https://users.ece.cmu.edu/~franzf/papers/fft-enc11.pdf
http://www.ams.org/journals/mcom/1979-33-147/S0025-5718-1979-0528051-4/S0025-5718-1979-0528051-4.pdf
Pease FFT と Korn–Lambiotte FFT は, ステージ間での配線パターンが同じです.
美しい ...
ちなみにStockham FFT は,
入出力時の並び順がin placeであることが主眼のようです.
しかし, それよりも各ステージの回転因子を乗算する周波数ビンが
(たぶん) 同じ位置, しかも後半に固まっていることの方が, 有用で美しく思います.