C ++在给定复杂2D数组的情况下执行2D FFT就位
快速傅立叶变换(FFT)是一种计算离散傅立叶变换(DFT)及其逆运算的算法。基本上，傅立叶分析将时间（或空间）转换为频率，反之亦然。FFT通过将DFT矩阵分解为稀疏（大多数为零）因子的乘积来快速计算变换。
算法
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)