C++ Program to Perform a 2D FFT Inplace Given a Complex 2D Array

This is a C++ Program to perform 2D FFT. A fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform (DFT) and its inverse. Fourier analysis converts time (or space) to frequency and vice versa; an FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors.

Here is source code of the C++ Perform to a 2D FFT Inplace Given a Complex 2D Array. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <iostream>
  2. #include <math.h>
  3.  
  4. using namespace std;
  5.  
  6. #define PI 3.14159265
  7. int n;
  8.  
  9. int main(int argc, char **argv)
  10. {
  11.     cout << "Enter the size: ";
  12.     cin >> n;
  13.     double inputData[n][n];
  14.     cout << "Enter the 2D elements ";
  15.     for (int i = 0; i < n; i++)
  16.         for (int j = 0; j < n; j++)
  17.             cin >> inputData[i][j];
  18.  
  19.     double realOut[n][n];
  20.     double imagOut[n][n];
  21.     double amplitudeOut[n][n];
  22.  
  23.     int height = n;
  24.     int width = n;
  25.  
  26.     // Two outer loops iterate on output data.
  27.     for (int yWave = 0; yWave < height; yWave++)
  28.     {
  29.         for (int xWave = 0; xWave < width; xWave++)
  30.         {
  31.             // Two inner loops iterate on input data.
  32.             for (int ySpace = 0; ySpace < height; ySpace++)
  33.             {
  34.                 for (int xSpace = 0; xSpace < width; xSpace++)
  35.                 {
  36.                     // Compute real, imag, and ampltude.
  37.                     realOut[yWave][xWave] += (inputData[ySpace][xSpace] * cos(
  38.                             2 * PI * ((1.0 * xWave * xSpace / width) + (1.0
  39.                                     * yWave * ySpace / height)))) / sqrt(
  40.                             width * height);
  41.                     imagOut[yWave][xWave] -= (inputData[ySpace][xSpace] * sin(
  42.                             2 * PI * ((1.0 * xWave * xSpace / width) + (1.0
  43.                                     * yWave * ySpace / height)))) / sqrt(
  44.                             width * height);
  45.                     amplitudeOut[yWave][xWave] = sqrt(
  46.                             realOut[yWave][xWave] * realOut[yWave][xWave]
  47.                                     + imagOut[yWave][xWave]
  48.                                             * imagOut[yWave][xWave]);
  49.                 }
  50.                 cout << realOut[yWave][xWave] << " + " << imagOut[yWave][xWave]
  51.                         << " i (" << amplitudeOut[yWave][xWave] << ")\n";
  52.             }
  53.         }
  54.     }
  55. }

Output:

$ g++ TwoDFFT.cpp
$ a.out
 
Enter the size: 
2
Enter the 2D elements 
2 3
4 2
 
2.5 + 0.0 i
5.5 + 0.0 i
-0.5 + -1.8369701987210297E-16 i
0.5 + -3.0616169978683826E-16 i
2.5 + 0.0 i
-0.5 + -3.6739403974420594E-16 i
-0.5 + -1.8369701987210297E-16 i
-1.5 + -1.8369701987210297E-16 i

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.