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

Output:

$ gcc FFT2D.c
$ ./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.