C++는 복잡한 2D 배열이 주어지면 2D FFT를 수행합니다.

FFT(고속 푸리에 변환)는 이산 푸리에 변환(DFT)과 그 역을 계산하는 알고리즘입니다. 기본적으로 푸리에 분석은 시간(또는 공간)을 주파수로 또는 그 반대로 변환합니다. FFT는 DFT 행렬을 희소(대부분 0) 요인의 곱으로 분해하여 변환을 빠르게 계산합니다.

알고리즘

Begin
   Declare the size of the array
   Take the elements of the array
   Declare three arrays
   Initialize height =size of array and width=size of array
   Create two outer loops to iterate on output data
   Create two outer loops to iterate on input data
   Compute real, img and amp.
End

예시 코드

#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)