C++로 DFT(이산 푸리에 변환) 계수 직접 계산하기

DFT(이산 푸리에 변환)란?

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

DFT 계수는 다음과 같은 공식으로 표현됩니다.

X(k) = Σ x(n) · e^(−j·2π·k·n / N)

여기서 x(n)은 입력 신호의 n번째 샘플, k는 주파수 인덱스, N은 전체 샘플 수를 의미합니다. 이 글에서는 C++를 사용하여 특정 주파수 k에 대한 DFT 계수의 실수부(real)와 허수부(imaginary)를 직접 계산하는 프로그램을 구현해 보겠습니다.

알고리즘

프로그램의 전체적인 흐름은 다음과 같습니다.

1. 선형 방정식의 계수 a, b, c를 입력받는다.
2. 실수부(real)와 허수부(img)를 저장할 두 변수를 가진 클래스를 정의한다.
3. 생성자에서 real과 img를 0으로 초기화한다.
4. 샘플 개수 M을 정하고, 함수값 배열 function[M]을 생성한다.
5. i = 0 ~ M-1 범위에서 function[i] = ((a × i) + (b × i)) − c 로 계산한다.
6. 사인 배열 sine[M]과 코사인 배열 cosine[M]을 선언한다.
7. i = 0 ~ M-1 범위에서 다음을 계산한다.
   cosine[i] = cos((2 × i × k × π) / M)
   sine[i]   = sin((2 × i × k × π) / M)
8. i = 0 ~ M-1 범위에서 누적 합을 계산한다.
   dft_value.real += function[i] × cosine[i]
   dft_value.img  += function[i] × sine[i]
9. 최종 DFT 계수 값을 출력한다.

C++ 예제 코드

아래 코드는 사용자로부터 선형 함수 ax + by = c의 계수와 최대 주파수 값 k를 입력받아, 해당 주파수 성분에 대한 DFT 계수를 계산하여 출력합니다.

#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 coeff 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;
    cout << "The coeffs are: ";
    for (int i = 0; i < M; i++) {
        dft_value.real += function[i] * cosine[i];
        dft_value.img += function[i] * sine[i];
    }
    cout << "(" << dft_value.real << ") - " << "(" << dft_value.img << " i)";
}

코드 설명

DFT_Coeff 클래스: DFT 결과의 실수부(real)와 허수부(img)를 저장하며, 생성자에서 두 값을 0.0으로 초기화합니다.
함수값 생성: 입력받은 계수 a, b, c를 이용해 f(i) = (a + b)·i − c 형태의 샘플 값을 M개 생성합니다.
회전 인자(Twiddle Factor) 계산: cos((2πik)/M)과 sin((2πik)/M)을 미리 계산하여 배열에 저장함으로써 연산 효율을 높입니다.
계수 누적: 각 샘플 값과 회전 인자를 곱해 실수부와 허수부를 각각 누적합하여 최종 DFT 계수를 구합니다.

실행 결과

Enter the coeff of simple linear function:
ax + by = c
4 6 7
Enter the max K value:
4
The coeffs are: (-50) - (-16.246 i)

위 실행 결과에서 계수 a=4, b=6, c=7 그리고 k=4를 입력했을 때, DFT 계수는 실수부 −50, 허수부 −16.246i로 계산되었습니다. 즉, 해당 주파수 성분의 크기와 위상 정보를 실수부와 허수부의 조합으로 확인할 수 있습니다.

마무리

이처럼 DFT는 시간 영역의 신호를 주파수 영역으로 변환하는 강력한 도구이며, 오디오 처리, 이미지 압축(JPEG), 통신 시스템 등 다양한 분야에서 활용됩니다. 본 예제는 O(M²)의 시간 복잡도를 가지는 단순한 구현이지만, 대용량 데이터를 다룰 경우 FFT(Fast Fourier Transform) 알고리즘을 적용하면 O(M log M)으로 성능을 크게 향상시킬 수 있습니다.