Java Program to Compute Discrete Fourier Transform using Fast Fourier Transform Approach

«
»
This is the java implementation of performing Discrete Fourier Transform using Fast Fourier Transform algorithm. This class finds the DFT of N (power of 2) complex elements, generated randomly, using FFT. Further verification is done by taking the Inverse Discrete Fourier Transform, again using FFT.

Here is the source code of the Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. // This is a sample program to perform DFT using FFT, FFT is performed on random input sequence
  2. public class FFT 
  3. {
  4.     public static class Complex 
  5.     {
  6.         private final double re; // the real part
  7.         private final double im; // the imaginary part
  8.  
  9.         // create a new object with the given real and imaginary parts
  10.         public Complex(double real, double imag) 
  11.         {
  12.             re = real;
  13.             im = imag;
  14.         }
  15.  
  16.         // return a string representation of the invoking Complex object
  17.         public String toString() 
  18.         {
  19.             if (im == 0)
  20.                 return re + "";
  21.             if (re == 0)
  22.                 return im + "i";
  23.             if (im < 0)
  24.                 return re + " - " + (-im) + "i";
  25.             return re + " + " + im + "i";
  26.         }
  27.  
  28.         // return abs/modulus/magnitude and angle/phase/argument
  29.         public double abs() 
  30.         {
  31.             return Math.hypot(re, im);
  32.         } // Math.sqrt(re*re + im*im)
  33.  
  34.         public double phase() 
  35.         {
  36.             return Math.atan2(im, re);
  37.         } // between -pi and pi
  38.  
  39.         // return a new Complex object whose value is (this + b)
  40.         public Complex plus(Complex b) 
  41.         {
  42.             Complex a = this; // invoking object
  43.             double real = a.re + b.re;
  44.             double imag = a.im + b.im;
  45.             return new Complex(real, imag);
  46.         }
  47.  
  48.         // return a new Complex object whose value is (this - b)
  49.         public Complex minus(Complex b) 
  50.         {
  51.             Complex a = this;
  52.             double real = a.re - b.re;
  53.             double imag = a.im - b.im;
  54.             return new Complex(real, imag);
  55.         }
  56.  
  57.         // return a new Complex object whose value is (this * b)
  58.         public Complex times(Complex b) 
  59.         {
  60.             Complex a = this;
  61.             double real = a.re * b.re - a.im * b.im;
  62.             double imag = a.re * b.im + a.im * b.re;
  63.             return new Complex(real, imag);
  64.         }
  65.  
  66.         // scalar multiplication
  67.         // return a new object whose value is (this * alpha)
  68.         public Complex times(double alpha) 
  69.         {
  70.             return new Complex(alpha * re, alpha * im);
  71.         }
  72.  
  73.         // return a new Complex object whose value is the conjugate of this
  74.         public Complex conjugate() {
  75.             return new Complex(re, -im);
  76.         }
  77.  
  78.         // return a new Complex object whose value is the reciprocal of this
  79.         public Complex reciprocal() 
  80.         {
  81.             double scale = re * re + im * im;
  82.             return new Complex(re / scale, -im / scale);
  83.         }
  84.  
  85.         // return the real or imaginary part
  86.         public double re() 
  87.         {
  88.             return re;
  89.         }
  90.  
  91.         public double im() 
  92.         {
  93.             return im;
  94.         }
  95.  
  96.         // return a / b
  97.         public Complex divides(Complex b) 
  98.         {
  99.             Complex a = this;
  100.             return a.times(b.reciprocal());
  101.         }
  102.  
  103.         // return a new Complex object whose value is the complex exponential of
  104.         // this
  105.         public Complex exp() 
  106.         {
  107.             return new Complex(Math.exp(re) * Math.cos(im), Math.exp(re)
  108.                     * Math.sin(im));
  109.         }
  110.  
  111.         // return a new Complex object whose value is the complex sine of this
  112.         public Complex sin() 
  113.         {
  114.             return new Complex(Math.sin(re) * Math.cosh(im), Math.cos(re)
  115.                     * Math.sinh(im));
  116.         }
  117.  
  118.         // return a new Complex object whose value is the complex cosine of this
  119.         public Complex cos() 
  120.         {
  121.             return new Complex(Math.cos(re) * Math.cosh(im), -Math.sin(re)
  122.                     * Math.sinh(im));
  123.         }
  124.  
  125.         // return a new Complex object whose value is the complex tangent of
  126.         // this
  127.         public Complex tan() 
  128.         {
  129.             return sin().divides(cos());
  130.         }
  131.  
  132.         // a static version of plus
  133.         public static Complex plus(Complex a, Complex b) 
  134.         {
  135.             double real = a.re + b.re;
  136.             double imag = a.im + b.im;
  137.             Complex sum = new Complex(real, imag);
  138.             return sum;
  139.         }
  140.  
  141.         // compute the FFT of x[], assuming its length is a power of 2
  142.         public static Complex[] fft(Complex[] x) 
  143.         {
  144.             int N = x.length;
  145.  
  146.             // base case
  147.             if (N == 1)
  148.                 return new Complex[] { x[0] };
  149.  
  150.             // radix 2 Cooley-Tukey FFT
  151.             if (N % 2 != 0) 
  152.             {
  153.                 throw new RuntimeException("N is not a power of 2");
  154.             }
  155.  
  156.             // fft of even terms
  157.             Complex[] even = new Complex[N / 2];
  158.             for (int k = 0; k < N / 2; k++) 
  159.             {
  160.                 even[k] = x[2 * k];
  161.             }
  162.             Complex[] q = fft(even);
  163.  
  164.             // fft of odd terms
  165.             Complex[] odd = even; // reuse the array
  166.             for (int k = 0; k < N / 2; k++) 
  167.             {
  168.                 odd[k] = x[2 * k + 1];
  169.             }
  170.             Complex[] r = fft(odd);
  171.  
  172.             // combine
  173.             Complex[] y = new Complex[N];
  174.             for (int k = 0; k < N / 2; k++) 
  175.             {
  176.                 double kth = -2 * k * Math.PI / N;
  177.                 Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
  178.                 y[k] = q[k].plus(wk.times(r[k]));
  179.                 y[k + N / 2] = q[k].minus(wk.times(r[k]));
  180.             }
  181.             return y;
  182.         }
  183.  
  184.         // compute the inverse FFT of x[], assuming its length is a power of 2
  185.         public static Complex[] ifft(Complex[] x) 
  186.         {
  187.             int N = x.length;
  188.             Complex[] y = new Complex[N];
  189.  
  190.             // take conjugate
  191.             for (int i = 0; i < N; i++) 
  192.             {
  193.                 y[i] = x[i].conjugate();
  194.             }
  195.  
  196.             // compute forward FFT
  197.             y = fft(y);
  198.  
  199.             // take conjugate again
  200.             for (int i = 0; i < N; i++) 
  201.             {
  202.                 y[i] = y[i].conjugate();
  203.             }
  204.  
  205.             // divide by N
  206.             for (int i = 0; i < N; i++) 
  207.             {
  208.                 y[i] = y[i].times(1.0 / N);
  209.             }
  210.  
  211.             return y;
  212.  
  213.         }
  214.  
  215.         // display an array of Complex numbers to standard output
  216.         public static void show(Complex[] x, String title) 
  217.         {
  218.             System.out.println(title);
  219.             for (int i = 0; i < x.length; i++) 
  220.             {
  221.                 System.out.println(x[i]);
  222.             }
  223.             System.out.println();
  224.         }
  225.  
  226.         public static void main(String[] args) 
  227.         {
  228.             int N = 8;//Integer.parseInt(args[0]);
  229.             Complex[] x = new Complex[N];
  230.  
  231.             // original data
  232.             for (int i = 0; i < N; i++) 
  233.             {
  234.                 x[i] = new Complex(i, 0);
  235.                 x[i] = new Complex(-2 * Math.random() + 1, 0);
  236.             }
  237.             show(x, "x");
  238.  
  239.             // FFT of original data
  240.             Complex[] y = fft(x);
  241.             show(y, "y = fft(x)");
  242.  
  243.             // take inverse FFT
  244.             Complex[] z = ifft(y);
  245.             show(z, "z = ifft(y)");
  246.  
  247.         }
  248.  
  249.     }
  250. }

Output:

advertisement
$ javac FFT.java
$ java FFT
 
x
0.5568836254037923
0.8735842104393365
0.6099699812709252
0.5631502515566189
-0.518857260970139
-0.5946393148293805
0.47144753318047794
-0.3501597962417593
 
y = fft(x)
1.6113792298098721
1.4681239692650163 - 1.8225209872296184i
-1.0433911500177497 - 0.06595444029509645i
0.6833578034828462 - 1.545476091048724i
0.6275085279602408
0.6833578034828462 + 1.545476091048724i
-1.0433911500177497 + 0.06595444029509645i
1.4681239692650163 + 1.8225209872296184i
 
z = ifft(y)
0.5568836254037923
0.8735842104393365 - 5.652078740871965E-17i
0.6099699812709252 - 4.24102681660054E-18i
0.5631502515566189 - 5.4501515053796015E-17i
-0.518857260970139
-0.5946393148293805 + 5.4501515053796015E-17i
0.47144753318047794 + 4.24102681660054E-18i
-0.3501597962417593 + 5.652078740871965E-17i

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

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

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 & technical discussions at Telegram SanfoundryClasses.