Fast Fourier Transform

Rifat Aras, Duc T. Nguyen
Old Dominion University
United States of America
dnguyen@odu.edu
Website: http://numericalmethods.eng.usf.edu
Version: Mathematica 8; Last Revised: November, 9, 2011

Initialization

Clearing the definitions of all symbols in the current context:

ClearAll[Evaluate[Context[]<>"*"]];
dataPointsR={};
dataPointsI={};
nDataPoints=0;

Introduction

The following worksheet demonstrates how to compute unknown complex Fourier coefficients by using the Fast Fourier Transform (FFT) algorithm. The user inputs the complex data points to the text fields provided followed by clicking “Record Data Point”. When all the data is input, “Calculate Coefficients” button is clicked.

Section 1: Function Definitions

Find the complex coefficients Cn. Input parameters are: number of data points entered by the user, list of the real parts of the input data points, and list of the imaginary parts of the input data points. The FFT algorithm requires the number of input data points to be a power of 2. This function checks the number of data points, and if it is not a power of 2, the function fills the remaining data points with 0 values to obtain a power of 2.

findCoefficients[numDataPoints_, realDataPoints_, imagDataPoints_]:=(
bigN=2^Ceiling[Log[2,numDataPoints]];
prealDataPoints=PadRight[realDataPoints,bigN];
pimagDataPoints=PadRight[imagDataPoints,bigN];
Print["Original real vector is: ",prealDataPoints];
Print["Original imaginary vector is: ",pimagDataPoints];
smallR=Log[2,bigN];
Do[
separationDistance=bigN/(2^l);
k=0;
While[k<bigN,
Do[
binaryK=Reverse[PadLeft[IntegerDigits[BitShiftRight[k,smallR-l],2],smallR]];
bigP=FromDigits[binaryK,2];
theta=2*Pi*bigP/bigN;
cosTheta=Cos[theta];
sinTheta=Sin[theta];
kIndex=k+1;
kDualIndex=kIndex+separationDistance;
partReal=cosTheta*prealDataPoints[[kDualIndex]]+sinTheta*pimagDataPoints[[kDualIndex]];
partImag=cosTheta*pimagDataPoints[[kDualIndex]]-sinTheta*prealDataPoints[[kDualIndex]];
prealDataPoints[[kDualIndex]]=prealDataPoints[[kIndex]]-partReal;
pimagDataPoints[[kDualIndex]]=pimagDataPoints[[kIndex]]-partImag;
prealDataPoints[[kIndex]]=prealDataPoints[[kIndex]]+partReal;
pimagDataPoints[[kIndex]]=pimagDataPoints[[kIndex]]+partImag;
k++;
,{i,1,separationDistance}];
k+=separationDistance;];
Print["\tLevel ",l," is completed.\n\t\tThe intermediate real vector is: ",prealDataPoints];
Print["\t\tThe intermediate imaginary vector is: ",pimagDataPoints];
,{l,1,smallR}];
unscramble[bigN,prealDataPoints,pimagDataPoints,smallR];
);

After the FFT algorithm terminates, the resultant vector of coefficients have to be unscrambled. This function takes care of unscrambling process.

unscramble[numDataPoints_, realDataPoints_, imagDataPoints_,smallR_]:=(
prealDataPoints=realDataPoints;
pimagDataPoints=imagDataPoints;
Do[
m=k-1;
ii=FromDigits[Reverse[PadLeft[IntegerDigits[m,2],smallR]],2];
i=ii+1;
If[i≤k,,
temporeal=prealDataPoints[[k]];
tempoimag=pimagDataPoints[[k]];
prealDataPoints[[k]]=prealDataPoints[[i]];
pimagDataPoints[[k]]=pimagDataPoints[[i]];
prealDataPoints[[i]]=temporeal;
pimagDataPoints[[i]]=tempoimag;];
,{k,1,numDataPoints}];
Print["Real results: ",N[prealDataPoints]];
Print["Imag results: ",N[pimagDataPoints]];
);

Section 2: Graphical User Interface Definition

Definition of the graphical user interface.

userInterface = Panel[
Dynamic[
Column[
{
"Fast Fourier Transform Demonstration",
Row[{"Enter data point: ",InputField[Dynamic[realPart],FieldSize->Tiny]," + ",InputField[Dynamic[imagPart],FieldSize->Tiny]," i"}],
Row[{Button["Record Data Point",{AppendTo[dataPointsR,realPart],AppendTo[dataPointsI,imagPart],nDataPoints++}],"Number of data points: ",nDataPoints}],
Row[{Button["Calculate Coefficients",findCoefficients[nDataPoints, dataPointsR, dataPointsI]]}]
}
]
]
];

Section 3: Dynamic Module for Coefficient Computation

Dynamic[userInterface]

Conclusion

This worksheet shows how to compute the unknown coefficients of a discrete data set made up of complex numbers with Fast Fourier Transform (FFT). The FFT algorithm is an efficient way of computing Fourier Transform in terms of both number operations performed and memory spent.

References

CEE 305 course notes by Duc T. Nguyen, http://www.lions.odu.edu/~skadi002/fft1.1.pdf

Legal Notice: The copyright for this application is owned by the author(s). Neither Wolfram Research nor the author(s) are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.