0

以下は Cooley-Tukey FFT アルゴリズム (Rosetta Code にあります) の基数 2 の実装です。FFT を 1 回実行すると、データ配列は係数からポイント値表現になります。どのように係数に戻すのですか?

#include <complex>
#include <iostream>
#include <valarray>

const double PI = 3.141592653589793238460;

typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;

// Cooley–Tukey FFT (in-place)
void fft(CArray& x)
{
    const size_t N = x.size();
    if (N <= 1) return;

    // divide
    CArray even = x[std::slice(0, N/2, 2)];
    CArray  odd = x[std::slice(1, N/2, 2)];

    // conquer
    fft(even);
    fft(odd);

    // combine
    for (size_t k = 0; k < N/2; ++k)
    {
        Complex t = std::polar(1.0, -2 * PI * k / N) * odd[k];
        x[k    ] = even[k] + t;
        x[k+N/2] = even[k] - t;
    }
}

int main()
{
    const Complex test[] = { 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0 };
    CArray data(test, 8);

    fft(data);

    for (int i = 0; i < 8; ++i)
    {
        std::cout << data[i] << "\n";
    }
    return 0;
}
4

2 に答える 2

3

逆 FFT を計算する

変化する

-2 * PI * k / N

に

2 * PI * k / N

逆FFTを実行した後、出力を1/Nでスケーリングします

于 2013-03-22T08:40:16.023 に答える
1

ロゼッタ コードに追加

// inverse fft (in-place)
void ifft(CArray& x)
{
    // conjugate the complex numbers
    std::transform(&x[0], &x[x.size()], &x[0], std::conj<double>);

    // forward fft
    fft( x );

    // conjugate the complex numbers again
    std::transform(&x[0], &x[x.size()], &x[0], std::conj<double>);

    // scale the numbers
    x /= x.size();
}
于 2013-05-31T00:24:03.973 に答える