[c++] FFT 및 역FFT

07 Dec 2023

이 게시물에서는 FFT(Fast Fourier Transform)와 역FFT에 대해 소개하고, C++에서의 구현 방법을 살펴보겠습니다.

FFT란 무엇인가요?

FFT는 주어진 시계열 데이터를 주파수 영역으로 변환하는 수학적 기술입니다. 일반적으로 시간 도메인의 데이터를 주파수 도메인으로 변환하여 주파수 성분을 분석합니다. 이를 통해 주파수 성분에 따른 데이터의 특성을 파악할 수 있습니다.

C++에서 FFT 구현하기

C++에서 FFT를 구현하려면 주로 FFTW나 Boost C++ Libraries와 같은 외부 라이브러리를 사용합니다. 하지만 FFT 알고리즘을 직접 구현하는 것도 가능합니다.

다음은 C++에서 FFT를 구현하는 간단한 예제 코드입니다.

#include <complex>
#include <valarray>

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

const double PI = 3.141592653589793238460;

// Cooley-Tukey FFT (in-place, divide-and-conquer)
// Higher memory requirements and redundancy although more intuitive
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;
    }
}

// inverse fft (in-place)
void ifft(CArray& x)
{
    // conjugate the complex numbers
    x = x.apply(std::conj);

    // forward fft
    fft( x );

    // conjugate the complex numbers again
    x = x.apply(std::conj);

    // scale the numbers
    x /= x.size();
}

요약

이 게시물에서는 FFT 및 역FFT의 개념과 C++에서의 구현 방법을 살펴보았습니다. FFT를 사용하면 주파수 성분을 분석하여 다양한 시계열 데이터의 특성을 파악할 수 있습니다. C++에서 FFT를 구현할 때는 외부 라이브러리를 사용하거나 직접 알고리즘을 구현할 수 있습니다.

참고문헌: GeeksforGeeks - Fast Fourier Transform (FFT), wikipedia - Fast Fourier transform

역FFT 구현 예제