고속 푸리에 변환(Fast Fourier Transform, FFT)은 이산 푸리에 변환(DFT)과 그 역변환을 빠르게 계산하는 알고리즘입니다. 푸리에 분석은 본질적으로 시간(또는 공간) 영역의 신호를 주파수 영역으로 변환하거나, 그 반대로 변환하는 기법입니다.
FFT가 빠른 이유는 DFT 행렬을 대부분 0으로 이루어진 희소(sparse) 인수들의 곱으로 분해하기 때문입니다. 덕분에 순진한 DFT 계산의 O(N²) 복잡도를 O(N log N) 수준으로 크게 줄일 수 있으며, 이미지 처리·신호 분석 등 2D 데이터에 적용되는 2D FFT 역시 널리 활용됩니다.
알고리즘
주어진 2D 배열에 대해 2D FFT를 수행하는 절차는 다음과 같습니다.
- 배열의 크기(n)를 선언하고 사용자로부터 입력받습니다.
- n × n 크기의 2D 배열에 데이터 요소들을 입력받습니다.
- 결과를 저장할 실수부(real), 허수부(img), 진폭(amp) 배열 세 개를 선언합니다.
- height와 width를 배열의 크기(n)로 초기화합니다.
- 출력 데이터(주파수 영역)를 순회하는 두 개의 외부 루프를 만듭니다.
- 입력 데이터(공간 영역)를 순회하는 두 개의 내부 루프를 만듭니다.
- 각 좌표에서 코사인·사인 항을 이용해 실수부, 허수부를 누적 계산하고, 이로부터 진폭(amp)을 구합니다.
C++ 예제 코드
#include <iostream>
#include <math.h>
using namespace std;
#define PI 3.14159265
int n;
int main(int argc, char **argv) {
cout << "Enter the size: ";
cin >> n;
double Data[n][n];
cout << "Enter the 2D elements ";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> Data[i][j];
double realOut[n][n];
double imgOut[n][n];
double ampOut[n][n];
int height = n;
int width = n;
for (int yWave = 0; yWave < height; yWave++) {
for (int xWave = 0; xWave < width; xWave++) {
for (int ySpace = 0; ySpace < height; ySpace++) {
for (int xSpace = 0; xSpace < width; xSpace++) {
realOut[yWave][xWave] += (Data[ySpace][xSpace] * cos(2 *
PI * ((1.0 * xWave * xSpace / width) + (1.0 * yWave * ySpace /
height)))) / sqrt(width * height);
imgOut[yWave][xWave] -= (Data[ySpace][xSpace] * sin(2 * PI
* ((1.0 * xWave * xSpace / width) + (1.0 * yWave * ySpace / height)))) /
sqrt(width * height);
ampOut[yWave][xWave] = sqrt(
realOut[yWave][xWave] * realOut[yWave][xWave] +
imgOut[yWave][xWave] * imgOut[yWave][xWave]);
}
cout << realOut[yWave][xWave] << " + " <<
imgOut[yWave][xWave] << " i (" << ampOut[yWave][xWave] << ")\n";
}
}
}
}
실행 결과
Enter the size: 2 Enter the 2D elements 4 5 6 7 4.5 + 6.60611e-310 i (4.5) 11 + 6.60611e-310 i (11) -0.5 + -8.97448e-09 i (0.5) -1 + -2.15388e-08 i (1) 4.5 + 6.60611e-310 i (4.5) -2 + -2.33337e-08 i (2) -0.5 + -8.97448e-09 i (0.5) 0 + 5.38469e-09 i (5.38469e-09)
코드 해설 및 참고 사항
위 코드는 4중 루프를 통해 각 주파수 성분 (yWave, xWave)마다 모든 공간 좌표 (ySpace, xSpace)의 기여도를 합산하는 직접적인 2D DFT 계산 방식입니다. 코사인 항은 실수부에, 사인 항은 허수부에 더해지며, 전체 에너지를 정규화하기 위해 sqrt(width * height)로 나눕니다. 최종 진폭은 실수부와 허수부 제곱합의 제곱근으로 계산됩니다.
출력 결과에서 6.60611e-310처럼 아주 작은 이상한 값이 보이는 이유는 realOut, imgOut 배열이 0으로 초기화되지 않은 채 사용되었기 때문입니다. 실제 프로젝트에서는 배열을 반드시 {0} 또는 memset 등으로 초기화해야 정확한 결과를 얻을 수 있습니다. 또한 double Data[n][n]처럼 런타임에 크기를 정하는 가변 길이 배열(VLA)은 표준 C++이 아니므로, 이식성을 고려한다면 std::vector<std::vector<double>> 사용을 권장합니다.