<< Chapter < Page
  Digital signal processing - dsp     Page 14 / 14
Chapter >> Page >

Case C output in numeric form

The output produced by the code in Listing 7 is shown in Figure 14 .

Figure 14. Case C output in numeric form.
Case C Real:0.0 0.999 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0imag: 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.00.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0

If you plot the real and imaginary input values from Listing 7 , you will see that they match the input values in Figure 13 . If you plot the real and imaginary output values in Figure 14 , you will see that they match the output values shown in Figure 13 .

Listing 7 signals the end of the main method.

The display method

Listing 8 shows the code for a simple method named display . The purpose of the display method is to display a real series and an imaginary series, each contained in an incoming array object of type double . The double values are truncated to no more than four digits before displaying them. Then they aredisplayed on a single line.

Listing 8. The display method.
static void display(double[] real,double[] imag){System.out.println("Real: "); for(int cnt=0;cnt<real.length;cnt++){ System.out.print(((int)(1000.0*real[cnt])) /1000.0 + " ");}//end for loop System.out.println();System.out.println("imag: "); for(int cnt=0;cnt<imag.length;cnt++){ System.out.print(((int)(1000.0*imag[cnt])) /1000.0 + " ");}//end for loop System.out.println();}//end display }//end class Fft02

Listing 8 also signals the end of the controlling class named Fft02 .

Run the program

I encourage you to copy and compile the program that you will find in Listing 9 . Experiment with different complex input series.

I also encourage you to download the applet from (External Link) or from here and experiment with it as well. Compare the numeric output produced by this program with the graphic output produced by theapplet.

Finally, I encourage you to examine the source code for the applet. Concentrate on that portion of the source code that performs the FFT. Hopefully,what you have learned in this module will make it easier for you to understand the source code for the FFT.

Summary

In this module, I have explained some of the underlying signal processing concepts that make the FFT possible. I illustrated those concepts in a programdesigned specifically to be as simple as possible while still illustrating the concepts.

Now that you understand those concepts, you should be able to better understand explanations of the mechanics of the FFT algorithm that appear onvarious websites.

Complete program listings

A complete listing of the program is provided in Listing 9 below.

Listing 9. Fft02.java.
/*File Fft02.java Copyright 2004, R.G.Baldwin Rev 4/30/04This program DOES NOT implement an FFT algorithm. Rather,this program illustrates the underlying FFT concepts in a form that is much more easilyunderstood than is normally the case with an actual FFT algorithm. The steps in theimplementation of a typical FFT algorithm are as follows:1. Decompose an N-point complex series into N individual complex values, each consisting of asingle complex sample. The order of the decomposition in an FFT algorithm is rathercomplicated. It is this order of decomposition, and the order of the subsequent recombination oftransform results that causes the FFT to be so fast. It is also that order that makes thealgorithm somewhat difficult to understand. This program does not implement that order ofdecomposition and recombination. 2. Calculate the transform of each of the Ncomplex samples, treating each as if it were located at the beginning of the complex series.This step is trivial. The real part of the transform of a single complex sample located atthe beginning of the series is a complex constant whose values are proportional to the real andimaginary values that make up the complex sample. 3. Correct each of the N transform results toreflect the actual position of the complex sample in the series. This involves the application ofsine and cosine curves to the real and imaginary parts of the transform. This step is usuallycombined with the recombination step that follows.4. Recombine the N transform results into a single transform result that represents thetransform of the original complex series. This is a very complicated operation in a real FFTalgorithm. It must reverse the order of decomposition in the first step describedearlier. As mentioned earlier, it is the order of the decomposition and subsequent recombinationthat minimizes the arithmetic operations required and gives the FFT its tremendous speed. Thisprogram does not implement the special order of decomposition and recombination used in an actualFFT algorithm. This program creates three separate complexseries, applies the processes listed above to each of those series, and displays the results onthe screen. No attempt is made to manage the decomposition and the subsequent recombination inthe manner of a true FFT algorithm. Therefore, this program is designed to illustrate theprocesses involved, and is not designed to provide the speed of a true FFT algorithm.The decomposition process in this program takes the complex samples in the order that they appearin the input complex series. The transform of each complex sample is simplythe sample itself. This is the result that would be obtained by actually computing the transformof the complex sample if the sample were the first sample in the series.The transform result for each complex sample is then corrected by applying sine and cosine curvesto reflect the actual position of the complex sample within the complex series.The real and imaginary parts of the corrected transform results are then added to accumulatorsthat are used to accumulate the corrected real and imaginary parts from the correctedtransforms for all of the individual complex samples.Once the real and imaginary parts have been accumulated for all of the complex samples, thereal part of the accumulator represents the real part of the transform of the original complexseries. The imaginary part of the accumulator represents the imaginary part of the transform ofthe original complex series. Tested using SDK 1.4.2 under WinXP************************************************/ class Fft02{public static void main(String[] args){//Instantiate an object that will implement // the processes used in an FFT, but not in// the order required by an FFT algorithm. Transform transform = new Transform();//Prepare the input data and the output // arrays for Case A. Note that for this// case, the input complex series contains // non-zero values only in the real part.// Also, most of the values in the real part // are zero.System.out.println("Case A"); double[]realInA = {0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1};double[] imagInA ={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; double[]realOutA = new double[16];double[] imagOutA = new double[16]; //Perform the transform and display the// transformed results for the original // complex series.transform.doIt(realInA,imagInA,2.0,realOutA, imagOutA);display(realOutA,imagOutA); //Process and display the results for Case B.// Note that the input complex series // contains non-zero values in both the real// and imaginary parts. However, most of the // values in the real and imaginary parts are// zero. System.out.println("\nCase B");double[] realInB ={0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1}; double[]imagInB = {0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,-1};double[] realOutB = new double[16]; double[]imagOutB = new double[16];transform.doIt(realInB,imagInB,2.0,realOutB, imagOutB);display(realOutB,imagOutB); //Process and display the results for Case C.// Note that the input complex series // contains non-zero values in both the real// and imaginary parts. In addition, very // few of the values in the complex series// have a value of zero. (The values of the // complex samples actually describe a cosine// curve and a sine curve.) System.out.println("\nCase C");double[] realInC ={1.0,0.923,0.707,0.382,0.0,-0.382,-0.707, -0.923,-1.0,-0.923,-0.707,-0.382,0.0,0.382,0.707,0.923}; double[]imagInC = {0.0,-0.382,-0.707,-0.923,-1.0,-0.923,-0.707,-0.382,0.0,0.382,0.707,0.923, 1.0,0.923,0.707,0.382};double[] realOutC = new double[16]; double[]imagOutC = new double[16];transform.doIt(realInC,imagInC,16.0,realOutC, imagOutC);display(realOutC,imagOutC); }//end main//===========================================// //The purpose of this method is to display// a real series and an imaginary series, // each contained in an incoming array object// of type double. The double values are // truncated to no more than four digits// before displaying them. Then they are // displayed on a single line.static void display(double[] real,double[] imag){System.out.println("Real: "); for(int cnt=0;cnt<real.length;cnt++){ System.out.print(((int)(1000.0*real[cnt])) /1000.0 + " ");}//end for loop System.out.println();System.out.println("imag: "); for(int cnt=0;cnt<imag.length;cnt++){ System.out.print(((int)(1000.0*imag[cnt])) /1000.0 + " ");}//end for loop System.out.println();}//end display }//end class Fft02//=============================================// //This class applies the processes normally used// in an FFT algorithm. However, this class does // not apply those processes in the special order// required of an FFT algorithm. It is that // special order that minimizes the arithmetic// requirements of an FFT algorithm and causes it // to be very fast. The purpose of an object of// this class is to illustrate the processes in a // more easily understood fashion that is often// the case with an actual FFT algorithm. class Transform{void doIt(double[] realIn,double[]imagIn, double scale,double[]realOut, double[]imagOut){ //Each complex value in the incoming arrays// represents both a complex sample and the // transform of that complex sample under the// assumption that the complex sample appears // at the beginning of the series.//Correct the transform result for each of // the complex samples in the series to// reflect the actual position of the complex // sample in the series. Add the corrected// transform result into accumulators in // order toproduce the transform of the // original complex series.for(int cnt = 0;cnt<realIn.length;cnt++){ correctAndRecombine(realIn[cnt], imagIn[cnt], cnt,realIn.length, scale,realOut, imagOut);}//end for loop }//end doIt//===========================================// //This method accepts an incoming complex// sample value and the position in the series // associated with that sample. The method// calculates the real and imaginary transform // values associated with that complex sample// when it is located at the specified // position. Then it updates the corresponding// real and imaginary values contained in array // objects used to accumulate the real and// imaginary values for all of the samples. // References to the array objects are received// as input parameters. Outgoing results are // scaled by an incoming parameter in an// attempt to cause the output values to fall // within a reasonable range in case someone// wants to plot them. void correctAndRecombine(double realSample,double imagSample, int position,int length,double scale,double[] realOut,double[]imagOut){ //Calculate the complex transform values for// each sample in the complex output series. for(int cnt = 0; cnt<length; cnt++){ double angle =(2.0*Math.PI*cnt/length)*position; //Calculate output based on real inputrealOut[cnt] +=realSample*Math.cos(angle)/scale; imagOut[cnt]+= realSample*Math.sin(angle)/scale;//Calculate output based on imag input realOut[cnt]-= imagSample*Math.sin(angle)/scale;imagOut[cnt] +=imagSample*Math.cos(angle)/scale; }//end for loop}//end correctAndRecombine }//end class transform

Miscellaneous

This section contains a variety of miscellaneous information.

Housekeeping material
  • Module name: Java1486-Fun with Java, Understanding the Fast Fourier Transform (FFT) Algorithm
  • File: Java1486.htm
  • Published: 01/04/05

Baldwin explains the underlying signal processing concepts that make the Fast Fourier Transform (FFT) algorithm possible.

Disclaimers:

Financial : Although the Connexions site makes it possible for you to download a PDF file for thismodule at no charge, and also makes it possible for you to purchase a pre-printed version of the PDF file, you should beaware that some of the HTML elements in this module may not translate well into PDF.

I also want you to know that, I receive no financial compensation from the Connexions website even if you purchase the PDF version of the module.

In the past, unknown individuals have copied my modules from cnx.org, converted them to Kindle books, and placed them for sale on Amazon.com showing me as the author. Ineither receive compensation for those sales nor do I know who does receive compensation. If you purchase such a book, please beaware that it is a copy of a module that is freely available on cnx.org and that it was made and published withoutmy prior knowledge.

Affiliation : I am a professor of Computer Information Technology at Austin Community College in Austin, TX.

-end-

Questions & Answers

where we get a research paper on Nano chemistry....?
Maira Reply
what are the products of Nano chemistry?
Maira Reply
There are lots of products of nano chemistry... Like nano coatings.....carbon fiber.. And lots of others..
learn
Even nanotechnology is pretty much all about chemistry... Its the chemistry on quantum or atomic level
learn
Google
da
no nanotechnology is also a part of physics and maths it requires angle formulas and some pressure regarding concepts
Bhagvanji
hey
Giriraj
Preparation and Applications of Nanomaterial for Drug Delivery
Hafiz Reply
revolt
da
Application of nanotechnology in medicine
what is variations in raman spectra for nanomaterials
Jyoti Reply
I only see partial conversation and what's the question here!
Crow Reply
what about nanotechnology for water purification
RAW Reply
please someone correct me if I'm wrong but I think one can use nanoparticles, specially silver nanoparticles for water treatment.
Damian
yes that's correct
Professor
I think
Professor
Nasa has use it in the 60's, copper as water purification in the moon travel.
Alexandre
nanocopper obvius
Alexandre
what is the stm
Brian Reply
is there industrial application of fullrenes. What is the method to prepare fullrene on large scale.?
Rafiq
industrial application...? mmm I think on the medical side as drug carrier, but you should go deeper on your research, I may be wrong
Damian
How we are making nano material?
LITNING Reply
what is a peer
LITNING Reply
What is meant by 'nano scale'?
LITNING Reply
What is STMs full form?
LITNING
scanning tunneling microscope
Sahil
how nano science is used for hydrophobicity
Santosh
Do u think that Graphene and Fullrene fiber can be used to make Air Plane body structure the lightest and strongest. Rafiq
Rafiq
what is differents between GO and RGO?
Mahi
what is simplest way to understand the applications of nano robots used to detect the cancer affected cell of human body.? How this robot is carried to required site of body cell.? what will be the carrier material and how can be detected that correct delivery of drug is done Rafiq
Rafiq
if virus is killing to make ARTIFICIAL DNA OF GRAPHENE FOR KILLED THE VIRUS .THIS IS OUR ASSUMPTION
Anam
analytical skills graphene is prepared to kill any type viruses .
Anam
Any one who tell me about Preparation and application of Nanomaterial for drug Delivery
Hafiz
what is Nano technology ?
Bob Reply
write examples of Nano molecule?
Bob
The nanotechnology is as new science, to scale nanometric
brayan
nanotechnology is the study, desing, synthesis, manipulation and application of materials and functional systems through control of matter at nanoscale
Damian
Is there any normative that regulates the use of silver nanoparticles?
Damian Reply
what king of growth are you checking .?
Renato
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
Stoney Reply
why we need to study biomolecules, molecular biology in nanotechnology?
Adin Reply
?
Kyle
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
Adin
why?
Adin
what school?
Kyle
biomolecules are e building blocks of every organics and inorganic materials.
Joe
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!





Source:  OpenStax, Digital signal processing - dsp. OpenStax CNX. Jan 06, 2016 Download for free at https://legacy.cnx.org/content/col11642/1.38
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital signal processing - dsp' conversation and receive update notifications?

Ask