C ++ Thực hiện tới một 2D FFT Inplace Cho một mảng 2D phức tạp

Biến đổi Fourier nhanh (FFT) là một thuật toán để tính toán biến đổi Fourier rời rạc (DFT) và nghịch đảo của nó. Về cơ bản, phân tích Fourier chuyển đổi thời gian (hoặc không gian) thành tần số và ngược lại. FFT nhanh chóng tính toán các phép biến đổi bằng cách phân tích nhân tử của ma trận DFT thành tích của các thừa số thưa thớt (hầu hết là 0).

Thuật toán

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

Mã mẫu

#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";
         }
      }
   }
}

Đầu ra

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)