FFTは複素信号を処理します。入力は複素信号であり、出力も複素信号です。ところが、実数しか必要としないアプリケーションはたくさんあります。そのような場合、虚部を0としてFFTを行うわけですが、もったいない点は否めません。何とかならないかと思うのが…

ついでにVisualDSP++ 5.0のライブラリに入っているFFT関数も評価してみました。これはダイナミック・スケーリングとスタティック・スケーリングを選べる豪華な仕様です。 試したところ、入出力の配列および係数配列をすべて別のメモリ・サブブロックに配置す…

うじのすけさんから計算時間についてコメントがありましたので、FFTの計算時間について書いておきます。FFTの計算時間はバタフライの"radix"（底）によって激変します。分かりやすいようにここではradix=2の場合について説明します。教科書で初頭向けに説明…

3月に16bit複素FFTルーチンを作ったのを思い出して、VisualDSP++に載せてみました。ついでにVisualDSP++ 5.0をインストール。 結果は1024点で15万サイクルです。ちょっと扱いに困る数値です。というのは、これはBlackfinの理論性能の大体1/10です。DSP屋とし…

前回で演算と係数の固定小数点化、およびshort型でのエミュレートが完了しました。しかし、そのままではFFTに自然信号をかけても十中八九うまく行きません。多くの場合、値が途中で飽和してしまいます。 これを理解するには、FFTアルゴリズムの中核となるバ…

前回、残しておいたcos/sin関数を固定小数点化しましょう。FFTに限った話をするならば、これはテーブル参照にするのが一般的です。おそらくはFFTがベンチマークに使われた影響が大きいのですが、関数近似にして雑音の影響が大きくなるのはたまらんといった点…

前回の話を元に、大浦さんのFFTを書き換えてみましょう。下のコードは前半をとりだしたものです。 /* based on http://momonga.t.u-tokyo.ac.jp/~ooura/fftman/ftmn1_2.html#sec1_2_1 */ void fft(int n, double theta, double ar[], double ai[]) { int m, …

前回、16bit固定小数点数と整数のフォーマットの違いを見ました。これで両者の差がわかったわけですが、C/C++言語で固定小数点数を使えないことに変わりはありません*1。 そこで、代表的な操作について一つ一つどうすれば良いのか見て行きましょう。 入れ物 …

大浦さんのFFTコードを固定小数点化する企画の第二回です。こういう企画は大事ですよ。自分がいつのたれ死にしても良い様に、知っていることはどんどん吐き出しておかねば。いや、すぐ死ぬ予定はないですが。 浮動小数点型とは何かと聞かれれば、答えはさほ…

ネットで便利な信号処理プログラムを拾ってきたら、それが浮動小数点数に基づくものだったというのは良くある話です。 嘘です。 良くある話なんて甘っちょろいものじゃありません。全部が全部浮動小数点数で書かれていると言っても過言ではない21世紀。この…

本来FFTアルゴリズムは再帰的です。すなわち、 2N点FFTは、二つのN点FFTをN個のバタフライ演算で束ねたものである 実際、再帰的アルゴリズムに基づいてFFTを書くと、とてもシンプルなプログラムになります。アルゴリズムの基本を覚えている人ならば、「はは…