shingoushori's dialy

音信号処理を専ら研究していた元博士後期課程の学生によるメモ

論文・文献徘徊メモ 160219-1 Pease FFT / Korn–Lambiotte FFT

FFTといえば,
Cooley–Tukey FFTが一番有名で, Stockham FFTが二番であろうと思います.
工学書を覗いてみると, だいたいここ2つではないでしょうか.
Cooley–Tukeyはわかりやすいとして, Stockhamはぎょっとします.
Webサイトによっては, よくよく線を辿ってみると不完全なものもありました.

そんなわけで, Stockhamの正しそうでわかりやすい説明を探し求めてみたわけです.
すると, Stockhamよりも一見してわかりやすそうな別のFFTに出会いました.
それが, Pease FFTKorn–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 FFTKorn–Lambiotte FFT は, ステージ間での配線パターンが同じです.
美しい ...

ちなみにStockham FFT は,
入出力時の並び順がin placeであることが主眼のようです.
しかし, それよりも各ステージの回転因子を乗算する周波数ビンが
(たぶん) 同じ位置, しかも後半に固まっていることの方が, 有用で美しく思います.