Chương trình C++ thực hiện FFT 2D tại chỗ (inplace) cho mảng phức 2D

Biến đổi Fourier nhanh (FFT) là thuật toán để tính 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) sang tần số và ngược lại. FFT tính toán nhanh chóng các biến đổi bằng cách phân tích ma trận DFT thành tích của các ma trận thưa (hầu như bằng 0).

Thuật toán

Bắt đầu
    Khai báo kích thước mảng
    Lấy các phần tử của mảng
    Khai báo ba mảng
    Khởi tạo height = kích thước mảng và width = kích thước mảng
    Tạo hai vòng lặp ngoài để lặp trên dữ liệu đầu ra
    Tạo hai vòng lặp ngoài để lặp trên dữ liệu đầu vào
    Tính toán phần thực, phần ảo và biên độ.
Kết thúc

Mã ví dụ

#include <iostream> 
#include <math.h> 
using namespace std; 

#define PI 3.14159265 

int n; 

int main(int argc, char **argv) { 
    cout << "Nhập kích thước: "; 
    cin >> n; 
    double Data[n][n]; 
    cout << "Nhập các phần tử 2D: "; 
    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"; 
        } 
    } 
}

Kết quả

Nhập kích thước: 2 
Nhập các phần tử 2D 
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)