C++로 배우는 이산 푸리에 변환(DFT): 순진한 접근 방식(Naive Approach)으로 계산하기

이산 푸리에 변환(Discrete Fourier Transform, DFT)은 함수의 등간격 샘플들로 이루어진 유한한 목록을, 주파수순으로 정렬된 복소 정현파(complex sinusoid)의 유한 선형 조합 계수 목록으로 변환하는 수학적 기법입니다. 이를 통해 샘플링된 함수를 원래의 도메인(주로 시간 또는 직선상의 위치)에서 주파수 도메인으로 옮길 수 있습니다.

이 글에서는 최적화 없이 정의 그대로 계산하는 '순진한 접근 방식(naive approach)'을 사용해 DFT를 구현하는 C++ 프로그램을 살펴봅니다.

DFT의 기본 원리

길이가 M인 입력 신호 x[0], x[1], ..., x[M-1]에 대해, k번째 DFT 계수는 다음과 같이 정의됩니다.

X[k] = Σ (x[n] · e^(-2πikn/M)), n = 0 ~ M-1
여기서 e^(iθ) = cos θ + i·sin θ 이므로, 실수부는 코사인 항, 허수부는 사인 항의 합으로 각각 계산할 수 있습니다.

알고리즘

시작
    정수 변수 M을 선언하고 초기화한다
    배열 function[M]을 선언한다
    i = 0 부터 M-1 까지 반복:
        function[i] = ((a * i) + (b * i)) - c
    종료
    배열 sine[M]과 cosine[M]을 선언한다
    i = 0 부터 M-1 까지 반복:
        cosine[i] = cos((2 * i * k * PI) / M)
        sine[i]   = sin((2 * i * k * PI) / M)
    종료
    DFT_Coeff 배열 dft_value[k]를 선언한다
    j = 0 부터 k-1 까지 반복:
        i = 0 부터 M-1 까지 반복:
            dft_value.real += function[i] * cosine[i]
            dft_value.img  += function[i] * sine[i]
        종료
    종료
    결과 값을 출력한다
종료

C++ 예제 코드

#include<iostream>
#include<math.h>
using namespace std;
#define PI 3.14159265

class DFT_Coeff {
public:
    double real, img;
    DFT_Coeff() {
        real = 0.0;
        img = 0.0;
    }
};

int main(int argc, char **argv) {
    int M = 10;
    cout << "Enter the coefficient of simple linear function:\n";
    cout << "ax + by = c\n";
    double a, b, c;
    cin >> a >> b >> c;

    double function[M];
    for (int i = 0; i < M; i++) {
        function[i] = (((a * (double) i) + (b * (double) i)) - c);
    }

    cout << "Enter the max K value: ";
    int k;
    cin >> k;

    double cosine[M];
    double sine[M];
    for (int i = 0; i < M; i++) {
        cosine[i] = cos((2 * i * k * PI) / M);
        sine[i] = sin((2 * i * k * PI) / M);
    }

    DFT_Coeff dft_value[k];
    cout << "The coefficients are: ";
    for (int j = 0; j < k; j++) {
        for (int i = 0; i < M; i++) {
            dft_value[j].real += function[i] * cosine[i];
            dft_value[j].img += function[i] * sine[i];
        }
        cout << "(" << dft_value[j].real << ") - "
             << "(" << dft_value[j].img << " i)\n";
    }
}

실행 결과

Enter the coefficient of simple linear function:
ax + by = c
4 5 6
Enter the max K value: 10
The coefficients are:
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)
(345) - (-1.64772e-05 i)

결과 해석 및 참고 사항

출력 값의 의미

입력 계수 a=4, b=5, c=6에 대해 각 샘플은 function[i] = 9i - 6 형태의 선형 함수가 되며, 모든 k에 대해 동일한 결과인 (345) - (-1.65e-05 i)가 출력됩니다. 허수부의 아주 작은 값(-1.65×10⁻⁵)은 부동소수점 연산 오차에 의한 것으로, 이론적으로는 0입니다. 즉, 이 신호의 에너지는 대부분 실수 성분(DC 성분)에 집중되어 있음을 보여줍니다.

시간 복잡도

이 구현은 k개의 주파수 계수 각각에 대해 M번의 곱셈·덧셈을 수행하므로, 시간 복잡도는 O(M × k)입니다. 일반적으로 M = N, k = N일 때 O(N²)이 됩니다.

실무에서의 개선점

순진한 접근 방식은 학습용으로는 적합하지만, 데이터 크기가 커지면 비효율적입니다. 실제 응용에서는 분할 정복 기법을 활용해 O(N log N)으로 계산하는 FFT(Fast Fourier Transform, 고속 푸리에 변환)를 사용하는 것이 표준입니다. 또한 VLA(가변 길이 배열) 대신 std::vector<double>을 사용하면 더 안전하고 이식성 높은 C++ 코드를 작성할 수 있습니다.