이산 푸리에 변환

푸리에 해석을 모른다면 슬쩍 보고 오자

푸리에 해석

이산 푸리에 변환의 C++ 코드이다.

#define M_PI 3.14159265358979323846

void DFT(const std::vector<double> &input, std::vector<std::complex<double>> &output)
{
    int N = input.size();
    std::complex<double> img(0.0, 1.0);

    for (int i = 0; i < N; ++i)
    {
        std::complex<double> tmp(0.0, 0.0);

        for (int j = 0; j < N; ++j)
        {
            tmp += input.at(j) * std::exp(-2.0 * M_PI * i * j * img / (double) N);
        }

        output.push_back(tmp);
    }
}

일단 푸리에 급수 식을 한번 써 보자

$c_n = \frac{1}{2}\int_{-1}^{1} f(x) e^{-i\pi n x}dx$

 

여기서 구하고자 하는 게 $e^{i\pi n x}$의 계수인$c_n$이다.

$f(x) = \sum c_n e^{i\pi n x}$

 

그런데 여기서 구하고자 하는 것은 이산적인 데이터들에 대한 변환이다.

정확히 그래프를 맞추는 대신 적은 수의 항으로 최대한 비슷하게 알고 싶다는 것이다.

컴퓨터는 연속적인 데이터를 처리하는데에는 한계가 있기 때문이다.

 

대충 이렇게 되겠다.

$\hat v_n = \frac{1}{\sqrt{N}}\sum_{n = 0}^{N-1} v_k e^\frac{-2i\pi n k}{N}$

여기서 $v_n$은 푸리에 계수이고 $v_k$는 변환하고자 하는 값이다.

간단히 설명하자면, 푸리에 계수 방법에서 k개의 항으로 푸리에 계수를 구하는 것으로 생각하면 된다. 그걸 입력된 수만큼(N) 하면 된다. (입력된 만큼만 출력하고 싶으므로 $N=k$)

 

위에서 $c_n$에서 적분은 특정 구간에서 합 형태로 쓸 수 있고 $c_n$이 다시 여러 주기함수들의 합으로 구해져서 $f(x)$가 되는 거다.

 

행렬 형태로 쓰면 다음과 같다.

$\hat v = Wv$

 

여기서 W는

대충 이렇게 생겼다.($w^n$는 $e^{\frac{-2\pi i n}{N}k}$이다)

앞에서 이중합을 말한 걸 생각해보면 뭐 하나 떠오르지 않는가? 이중 for문이다.

 

이제 아주 쉽게 구현할 수 있다. 시간복잡도는 $O(n) = n^2$이다.

아주 비 수학적이고 엄밀하지 않게 썼다. 자세한 건 알아서 찾아보기 바란다.

(사실 수학적으로 쓸 여력도 없다 이제 물리학과 학식 2학년 따리가 뭘 안다고)