C++ Program to Compute Discrete Fourier Transform using Fast Fourier Transform Approach

This is a C++ Program to perform Fast Fourier Transform. 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++ Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <iostream>
  2. #include <complex>
  3. #include <cmath>
  4. #include <iterator>
  5. using namespace std;
  6.  
  7. unsigned int bitReverse(unsigned int x, int log2n)
  8.  
  9. {
  10.     int n = 0;
  11.     int mask = 0x1;
  12.     for (int i = 0; i < log2n; i++)
  13.  
  14.     {
  15.         n <<= 1;
  16.         n |= (x & 1);
  17.         x >>= 1;
  18.     }
  19.     return n;
  20. }
  21. const double PI = 3.1415926536;
  22. template<class Iter_T>
  23. void fft(Iter_T a, Iter_T b, int log2n)
  24. {
  25.     typedef typename iterator_traits<iter_t>::value_type complex;
  26.     const complex J(0, 1);
  27.     int n = 1 << log2n;
  28.     for (unsigned int i = 0; i < n; ++i)
  29.     {
  30.         b[bitReverse(i, log2n)] = a[i];
  31.     }
  32.  
  33.     for (int s = 1; s <= log2n; ++s)
  34.  
  35.     {
  36.         int m = 1 << s;
  37.         int m2 = m >> 1;
  38.         complex w(1, 0);
  39.         complex wm = exp(-J * (PI / m2));
  40.         for (int j = 0; j < m2; ++j)
  41.  
  42.         {
  43.             for (int k = j; k < n; k += m)
  44.  
  45.             {
  46.                 complex t = w * b[k + m2];
  47.                 complex u = b[k];
  48.                 b[k] = u + t;
  49.                 b[k + m2] = u - t;
  50.             }
  51.             w *= wm;
  52.         }
  53.     }
  54. }
  55. int main(int argc, char **argv)
  56. {
  57.     typedef complex cx;
  58.     cx a[] = { cx(0, 0), cx(1, 1), cx(3, 3), cx(4, 4), cx(4, 4), cx(3, 3), cx(
  59.             1, 1), cx(0, 0) };
  60.     cx b[8];
  61.     fft(a, b, 3);
  62.     for (int i = 0; i < 8; ++i)
  63.         cout << b[i] << "\n";
  64.  
  65. }

Output:

$ g++ FFT.cpp
$ a.out
 
(16,16)
(-4.82843,-11.6569)
(0,0)
(-0.343146,0.828427)
(0,0)
(0.828427,-0.343146)
(0,0)
(-11.6569,-4.82843)

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.