FFT Program for Turbo-C

				       By

			         Steve Sampson


			   Version 2.6, November 1988


   The FFT program and test signal generators included in the archive, can be
used to perform signal analysis in the frequency domain, using samples in the
time domain.  Historically the applications have ranged from music to radar.
I recently have been doing some research in the radar field using this FFT to
perform relative velocity measurements.  This program can be further refined
to meet your needs.

   I initially uploaded a fairly basic program, and through feedback have
made some improvements.  It's pretty complete now as far as a start for making
your own specific version.  Earlier Unix compatability has been removed in
favor of IBM graphics adaptors.

   This program uses graphics to present a 256 filter window.  My current
application required complex data and resulted in 256 complex points.  You may
use this with real data which results in 128 significant points.  If you feed
the FFT real data only (Imaginary data set to zero), then the output will be a
mirror image, and you can ignore the left side.

Some papers I found on the subject of FFTs are included at the end.  There are
several books devoted to the subject also.

For an example try:

	sine in
	1000
	3000

Which will sample the 1 Khz data every 333 microseconds (1 / 3 Khz).  Note: The
sample frequency should be greater than 2 times the input frequency (Nyquist
and all that...).

Then run fft like so:

	fft in

And you should see a graphics display which has filters 0 through 255 on the
X axis, and power on the Y axis.  All DC power in the time samples will appear
in filter 128.  The fundamental display frequency is shown in filter 129 and
can be computed as follows:

	T  = Time Increment Between Samples
	N  = Number Of Samples (256)
	Tp = N * T

	Then F = 1 / Tp

	In the example above, the time increment between samples is
	1 / 3000 or 333 microseconds.  N = 256, so Tp = 85 milliseconds
	and 1 / .005333 is 11.7 Hz per filter.

	Therefore each filter is a multiple of 11.7 Hertz.

	Filter 126			-23.4 Hz
	Filter 127			-11.7 Hz
	Filter 128	DC		 00.0 Hz
	Filter 129	Fundamental	 11.7 Hz
	Filter 130	Second Harmonic  23.4 Hz

In this case you'll find the sampling interval didn't work very well for the
input frequency.  The display shows the power spread out over several filters.
This is a limitation of the Discrete Fourier Transform in representing a
continuous signal.

A better sample rate for 1000 Hz would be 4000 Hz, in which case T = 250 ms,
Tp = 64 milliseconds, and F = 15.625 Hz.  1000 / 15.625 = 64.  All of the
power should then appear in filter 192 (128 + 64) in this example.

Run it and see using:

	sine in
	1000
	4000

	fft in

By using negative frequencies in 'sine' you can generate opening targets:

	sine in
	-1000
	3000

	fft in

You can see in these examples where weighting functions would be useful.  For
instance using weighting you could greatly attenuate the sidebands.  Usually
the main lobe becomes a little wider however.  The current version does not
perform any weighting.

For generating pulses, a second program 'pulse' is provided.  It pre-loads
imaginary data with zeros.   For example:

	pulse in
	.000006
	.0000008

	fft in

Simulates a radar with a 6 microsecond pulse and 800 nanosecond range gates,
and produces the typical pulse spectrum display.


How to run the FFT program
--------------------------

The program auto-detects CGA, EGA, and VGA graphics adaptors.  The CGA version
cursor line is hard to see though.  VGA is untested.

When the program is run, a ruler line is drawn with tick marks every 5 filters.
Also "Computing FFT" is displayed at the top of the screen.  The program is now
busy computing the FFT and will not do anything useful until finished.

When the FFT computation is complete, the power plot will be performed and a
verticle cursor line will appear.  "Computing FFT" will be replaced with
"Filter # 128".  The program is then ready for input of commands.

The commands are:

	ESC		Escapes back to MS-DOS
	LEFT		Moves the cursor left
	RIGHT		Moves the cursor right
	CTRLLEFT	Moves the cursor 10 filters left
	CTRLRIGHT	Moves the cursor 10 filters right
	HOME		Moves the cursor to filter 0
	END		Moves the cursor to filter 255
	F1		Prints the display on an Epson/IBM Compatable printer

A bee-bop when F1 is pressed means the printer has a problem (paper, power...).


How to compile the programs
---------------------------

I use a Hard Disk configured per the Borland Manuals.  If this is your settup
also; do this:

	1.  Copy the archive contents into any directory.
	2.  Run \TURBOC\MAKE
	3.  Three programs are made: fft.exe, sine.exe, and pulse.exe.

If you have any other system specific changes, then consult the makefile and
Borland manuals.  I can also be reached at the address below.


FFT References
--------------

1.	Fast Fourier Transforms On Your Home Computer, William D. Stanley,
	Steven J. Peterson, BYTE Magazine, December 1978.  Basic idea comes
	from this program.

2.	8052 Microcomputer simplifies FFT Design, Arnold Rosenberg,
	Electronics, May 5, 1983.  Used a bit reverse table based on the
	routine in this program.

3.	A Fast Fourier Transform for the 8080, Robert D. Fusfeld,
	Dr. Dobbs, Number 44.  Gave me some ideas.

4.	A Guided Tour of the Fast Fourier Transform, G. D. Bergland,
	IEEE Spectrum, July 1969.

5.	FFT - Shortcut to Fourier Analysis, Richard Klahn, Richard R. Shively,
	Electronics, April 15 1968.

---
All programs are entered into the Public Domain, No rights reserved.
Steve Sampson, Box 45668, Tinker AFB, OK, 73145
75136,626