高速じゃないけどちょっと高速なフーリエ変換

　正数演算で離散フーリエ変換してみた。

void DFT(const int* f, int N, int *result) {
    int n, nEnd, k;
    nEnd = N /2;

    for (n = 0; n < nEnd; n++) {
        int re = 0;
        int q = n * 1000;
        for (k = 0; k < N; k++) {
            int p = q * k / N;
            re += f[k] * CosTable[p % 1000];
        }
        result[n] = re;
    }
}

　他に1キロバイト分の余弦波テーブル(int8_t CosTable[1000])が必用。テーブルは0.01フェーズステップで、エクセルとかで作っておけばok。ROMを節約したい場合は0.25フェーズ分で250バイトでも良いけど、実行時間とのトレードオフになる。
　虚数は計算しないので、離散フーリエ変換の半分のみだが、それでもO^2/2の計算量なので結構時間がかかる。例えば高速なフーリエ変換と比較して、128ポイントならおよそ9.2倍、512ポイントなら30倍、1024ポイントなら52倍くらいの差がある。とはいえ、72MHzのARMで128ポイント計算するのに必用なのは5msec未満程度だったので、ポイント数が少ない場合はFFTのややこしいアルゴリズム通すより楽だと思う。あとポイント数が自由に選べるというのも地味に嬉しいかも？ま、FFTのほうが明らかに早いんですけどね。