Fast Fourier Transform

ver 1.2

by
Michael F.Griffin

Childrens Hospital Research Foundation
Division of Cardiology
Biomedical Engineering Laboratory
Elland & Bethesda Aves
Cincinnati,Ohio 45229





The Fast Fourier Transform (FFT) is a computationally efficient
algorithm to compute the discrete fourier transform.

There are two methods that are commonly used to compute the
FFT: Decimation in Time and Decimation in Frequency. The author
chooses to use the decimation in time.

The FFT programs written by the author assume that the user
has some background knowledge.

The FFT programs require that the number of data points be a
power of two. Some modifications would be needed to transform a
length other than a power of two. Please contact the author if
you are interested in the modifications.

If you are using real data the computational efficiency can
be further improved by modifying the transform to take advantage
of certain properties of Fourier Transforms.

Modifications:
--------------

- added Turbo Graphix Toolbox routines for plots

- magnitude and phase (-pi/2 to pi/2) are displayed versus N points

- GETDATA.PAS slightly modified ===> GETDATA2.PAS

- FFT.COM requires both 8087 & Hercules Graphics board


Problems:
---------

- If the real parts are zero, you will get a run-time error
regarding a divide by zero during phase calculations. This
will try to be corrected on future versions.



List of some Fourier Analysis Programs available
------------------------------------------------

FFT.PAS - Turbo Pascal version of a complete FFT program
with data input from files and data output to
either files or printer.
The program works but could use a little work
on the input and output sections.
It does not know if an output file already
exists and could write over another data file.

FFT.COM - Compiled version of the above.

PROCFFT.PAS - Turbo Pascal FFT 'procedure'.

CHIRPZ.COM - Evaluating the Fourier Transform along a different contour.

FFT.EXE - Compiled Basica FFT.

FFT.BAS - Source code for FFT.EXE.

DFT.EXE - Discrete Fourier Transform - Compiled Basica

DFT.BAS - Source code for DFT.EXE


Data gathering for the Turbo Pascal FFT's

GETDATA2.PAS - Crude program to enter complex data into a
random access file. This program was written
to enter test data. Although it is crude, it
works. In most cases the data will be gathered
from a source and dumped into a random access

file that can be read by the program. If
entering data by hand is desired, this file
needs to be modified so that an editing
capability is added.

GETDATA2.COM- Turbo-87 compiled version of GETDATA2.PAS.
- requires an 8087

Hopefully, the author will find time to modify some of the
problems mentioned above. If not, you are more than welcome to
modify them yourselves. If you do modify the programs, please
download them to the Biomedical Engineering RBBS.


List of some future programs
----------------------------

Two Dimensional FFT - FFT for image data.

Complex Cepstrum - Log Spectrum.


Please send any corrections, modifications, suggestions, or
ideas to the address listed or leave a message on the RBBS. If
you are having any problems, feel free to call between 9am and
6pm on weekdays.

Biomedical Engineering RBBS
---------------------------
data/voice: 513-559-8599
RBBS hours: 1800-0900 weekdays
: 24 hours weekends
: Eastern Standard Time


4/29/85