โปรแกรม C++ คำนวณ 2D FFT แบบ In-place สำหรับอาร์เรย์ Complex

Fast Fourier Transform (FFT) เป็นอัลกอริทึมสำหรับคำนวณ Discrete Fourier Transform (DFT) และผกผัน โดยพื้นฐาน Fourier analysis แปลงเวลา (หรือพื้นที่) เป็นความถี่ และในทางกลับกัน FFT คำนวณการแปลงอย่างรวดเร็วโดยแยกตัวประกอบเมทริกซ์ DFT เป็นผลคูณของ sparse factors (ส่วนใหญ่เป็นศูนย์)

อัลกอริทึม

Begin
    ประกาศขนาดของอาร์เรย์
    รับองค์ประกอบของอาร์เรย์
    ประกาศอาร์เรย์สามตัว
    กำหนด height = ขนาดอาร์เรย์ และ width = ขนาดอาร์เรย์
    สร้างลูปนอกสองลูปเพื่อวนบนข้อมูลเอาต์พุต
    สร้างลูปนอกสองลูปเพื่อวนบนข้อมูลอินพุต
    คำนวณ real, img และ 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)