2019年11月09日

FFTというものがありましてん・・・・かーーそればっかーーー

FFTというものはね、DFTを高速化するアルゴリズムの事なんですわ。決して字句通りの高速フーリエ変換ではないのだよ。 なんちて。
というわけで古い教科書・参考書を持ち出し、図書館から借り、Amazonで351円で購入し、精読した結果、分かったことがある。
オレは一度もFFTを理解したことはなかった・・・その前にDFTを理解したこともなかった。。。それどころかフーリエ級数も理解してなかった・・・ようするに、何も分かってなかった (笑) 稲 草 竹
30年ぐらい前にC言語でプログラムを写経して動作させて、なんとか理解した気になったのだが、何も理解してなかったようだ。まー仕事と関係ないからいいけどね。

そして今、オレは理解した・・・気分になっている。以前はシグナルフローをプログラム化したもの、そのプログラムを読んで、ああシグナルフローの通りになっとるわ、このプログラムは、と納得したのだった。ところが、肝心のシグナルフローの導出が出来ない。
ディジタル信号処理の教科書でもくくらを詳しく書く本は少なくて(2,3冊しか読んでないけど)、DFTの数式を行列表現し、その行列を分解していくと最小はバタフライ演算になる。そういう説明はあるのだが、行列の分解に関して根拠は何よ?   そこがわからなかったのだ。だが本に書いてあるように分解した行列を計算すると元のDFTの数式になるのは確認した。
では、行列の分解の根拠はなんぞや。それは基数2のFFTのアルゴリズムをキチンと説明する本を探せ。それだけだった。
それ、∑がたくさん出てくるので数学が得意でないと・・・と言うほどの数学ではないな。
ただ、その場合でもデータ数が8とか16ぐらいだと図もあって分かるのだが、そこから一般化しようとすると数式に慣れてない場合には無理だろ。

まーそのような数式の解説のある本を読んでC言語でFFTのプログラムも書いてあるので読んで、FFTのアルゴリズムは一つではないので数種類を眺めて。
で、おや、と思ったのはC言語の事。
30年ぐらい前の本であり、Lattice C 3を使っているとか書いてあった。それを今のgccでコンパイルする。C++はCもカバーするから属性をcppにしてg++でコンパイルだー・・・。
するとエラーが出る場合と出ない場合がある。エラーが出るのはCとC++との違いだろよさ。

うーむ。しかし、オレとしてはOpenCVが既にCでのインターフェースは提供してないのでCを使う理由はないのだ。C++だ。C++/CLIってのも使うぞ。趣味で。
というわけで、hagahage.c という例題は hagahage.cppとrenameしてg++を使うことにしている。それでエラー出たら修正する。

そして肝心のFFTのアルゴリズムだが、基数2のFFTのアルゴリズムの一般化はやっぱり難しい。回転子の指数 p の値を決めるのが理解困難だ。ただ、列の値によって決まるのは分かっても自分でプログラム書けるほどの理解には至らぬ。なむ。

まーそういうわけで、あと一踏ん張りね。
基数4のFFTもあるぞ。それで爆速になる!!  わけではないらしい。基数8のFFTというのもあるぞ。ただ効果の程はないみたい。
で、データ数が32ぐらいであればFFTとDFTで時間差は大差はない。じゃあ、DFTでいいじゃんってか(笑)

蛇足だがFFTを使うのは・・・趣味の話で。。。LTSpiceという回路シミュレータにFFT機能があるので使う場合がある。タダのソフトである。
PCアプリで音源ボードを入力としてオーディオ帯域でのオシロ機能を実現するソフトがあるが、それにFFT機能も付いている。無償アプリである。
スマホでもそういうアプリがあるなあ。ただのが。
ようするにFFTなんて簡単なプログラムなんだよ。せいぜい20-30行だしよ・・・ってか。

FFTアルゴリズムを開発したクーリー・チューキーの両氏に感謝 しますですね。m(_ _)m

posted by toinohni at 07:55| 東京 ☁| Comment(0) | ソフト系雑学 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
コチラをクリックしてください