고속 푸리에 변환

 

이산 푸리에 변환

이산 푸리에 변환 글을 참고하면 좋다.

void FFT(std::vector<std::complex<double>> &x)
{
    unsigned int N = x.size(), k = N, n;
    std::complex<double> phiT(cos(M_PI / (double) N), -sin(M_PI / (double) N)), T;

    while (k > 1)
    {
        n = k;
        k >>= 1;
        phiT = phiT * phiT;
        T = 1.0L;

        for (int i = 0; i < k; ++i)
        {
            for (int a = i; a < N; a += n)
            {
                int b = a + k;
                std::complex<double> t = x.at(a) - x.at(b);
                x.at(a) += x.at(b);
                x.at(b) = t * T;
            }
            T *= phiT;
        }
    }

    unsigned int m = (unsigned int) log2(N);
    for (int a = 0; a < N; ++a)
    {
        unsigned int b = a;

        b = (((b & 0xaaaaaaaa) >> 1) | ((b & 0x55555555) << 1));
        b = (((b & 0xcccccccc) >> 2) | ((b & 0x33333333) << 2));
        b = (((b & 0xf0f0f0f0) >> 4) | ((b & 0x0f0f0f0f) << 4));
        b = (((b & 0xff00ff00) >> 8) | ((b & 0x00ff00ff) << 8));
        b = ((b >> 16) | (b << 16)) >> (32 - m);
        if (b > a)
        {
            std::swap(x.at(a), x.at(b));
        }
    }
}

void fft_r(std::valarray<std::complex<double>>& x)
{
    const int N = x.size();
    if (N <= 1)
        return;

    std::valarray<std::complex<double>> even = x[std::slice(0, N / 2, 2)];
    std::valarray<std::complex<double>> odd = x[std::slice(1, N / 2, 2)];

    fft_r(even);
    fft_r(odd);

    for (int i = 0; i < N / 2; ++i)
    {
        std::complex<double> t = std::polar(1.0, -2 * M_PI * i / (double) N) * odd[i];
        x[i] = even[i] + t;
        x[i+N / 2] = even[i] - t;
    }
}

고속 푸리에 변환 C++ 코드이다.

일단, 아주 간단히 설명하자면 위 코드는 반복 알고리즘과 재귀 알고리즘으로 다르게 구현할 수 있다.

 

맞다 분할정복이다.

대충 러시아 농사꾼 알고리즘을 함수 영역으로 확장시켰다 보면 된다.

 

행렬을 쪼개서 2*2정도의 작은 행렬로 만들고 다시 결합하는 방식인데 이 블로그를 참고하면 좋다.

helloworldpark.github.io/mathematics/2017/02/26/FFT_02.html

푸리에 분석 - 고속 푸리에 변환 증명하기

본인은 선형대수 실력이 Boas수리물리책에 나오는 수준으로 한정되므로 이해하기 힘들었다.

나중에 설명할 수 있는 정도가 되면 설명해보겠다.

 

stackoverflow.com/questions/28009590/understanding-the-radix-2-fft-recursive-algorithm

Understanding the radix-2 FFT recursive algorithm

위의 블로그를 봤다면 여기도 참조해보자 구조가 좀 보일것이다.