| << Chapter < Page | Chapter >> Page > |
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.
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 .
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.
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.
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 |
This section contains a variety of miscellaneous information.
Baldwin explains the underlying signal processing concepts that make the Fast Fourier Transform (FFT) algorithm possible.
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-
Notification Switch
Would you like to follow the 'Digital signal processing - dsp' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|