実はDFTを高速化するアルゴリズムであるFFTは手法がいくつかある。一つではない。だが、多くの信号処理の本では一つを紹介するにとどまる。FFTの解説がメインではなくてデジタル信号処理全般の本だとそうなる。
だがデジタル信号処理全般ではなくFFTに特化した本では解説は詳しい。私が読んだ本では「高速フーリエ変換」E.ORAN BRIGHAM 宮川・今井 訳 1980年 がFFTのアルゴリズムの解説として分かりやすい本であった。
デジタル信号処理全般を扱う本ではDFTの数式から行列表示をして行列の分解をして、そこからFFTのアルゴリズムを紹介する。だが、行列の分解の規則性や回転子の指数の規則性が私には理解できなかった。 N = 4, N = 8とかの場合の数式と行列表示は計算すると確かにそうなるのだが根拠はなんだよ。天才エンジニアが数式を行列表示して行列を眺めていたら気づいたというのか。。。。。それは天才だからできる!! 凡庸な私は行列を見て、それを分解して・・・という話がわからないのだった。まー数学は徳井ではない。徳井は脱税疑惑だ。得意だ。数学は得意ではないのである。
だが、「高速フーリエ変換」を読んで、あ、そういうことかと。なるほどなあ、と。しかし、その本に書いてあるような事を書かずに行列表示からシグナルフローの一般化ができる・・人は天才ですね。数学的な基礎があるから本の行列の分解が可能なんでして。
というわけで、FFTの説明でよく出るシグナルフローは二種類ある。適当に分けた。 
左が入力、右が出力だ。バタフライ演算がある。一つのバタフライ演算は入力が2つ、出力が2つだが列によって間隔が異なる。これは規則性がある。図ではも4,2,1 だ。
これに対して次のようなものもあるのが対照的た。 
左が入力、右が出力だ。 交差の部分を見ると逆になっている。バタフライ演算は列によって1,2,4だ。入力と出力で順番が入れ替わっているのに気づく。共に。
この違いは数式を書いて説明すると簡単だが、概略は∑∑∑(数式) という場合に内側から計算するか外側から計算するかの違いである。
ここは数式を書かないと説明しづらいので略する次第である。てへ。
問題は図のWの肩の数字。指数の根拠。W^p のpの決め方というか規則性。そこらを解説する本は件の本ぐらいである。。。。。ってか、他にたくさん読んだわけではなく。
ただ、デジタル信号処理一般を扱う本では詳しい解説はない。そこらだな。やっぱ専門書は威力あるよ。入門書での説明不足を感じたら勇気をもって専門書を読みたまへ。ただし、一を知って十を知るという俊才連中は入門書の説明で理解するかもなあ。N = 8の例から一般化できるとしたら、それは素晴らしいと思う。
上は基数2の場合であるが、基数4,8・・とかも可能であるらしい。ただ劇的に高速化できるものでなければ使う側からすると基数2でいいかも知れない。用途によるだろう。
というわけでアルゴリズムの学習としてFFTを続ける。本の例題はCodeを読む。サイトの例題もCodeを読む。
そのうちデータを数万用意して計算時間の比較でもするでなって感じ。
