I originally wrote this for a Z80 back in the early '80s. I found the source
code recently in one of the boxes of printouts I've kept over the years. Good
thing too, since most of the work was on a CPM system using 128k 8inch floppies.

    In order for this to compile you need to download ALL of the files you see
listed. The .dat files are required as well as the .asm files. A zip file of
all the files is provided in FFT.ZIP. 

FFT.ASM			; main program
PERM2.ASM		; time decimation
PERT.DAT		; table for above
PLOTPAS.ASM		; plot power/amplitude spectrum using 4014
POWER.ASM		; compute power spectrum = ((real*real) + (imag*imag))
SAMPLER.ASM		; collect real data from A/D
SCALE.ASM		; scale data to prevent overflow
SINT.DAT		; sine table for FFT
SQRT.DAT		; square table for power computation
SQRUT.DAT		; square root table for amplitude spectrum = sqr(power)
SYSMPY.ASM		; special multiply routine that maintains accuracy
WAVE.ASM		; create static data

    You will have to modify the main program to have it point to the specified
routines in you monitor. They are keyboard and screen routines normally found
in any monitor. Also a 16 by 8 bit division routine is required and can be 
found on my math page. Include files can be found on my include page.

    After a few bugs have been fixed, this FFT works well. The frequency span
and cell spacing is of course dependant on the sampling frequency. Since I'm
using this to evaluate 'WAV files, My sampling rate is 8000hz. The Nyquist is 
then 4000hz. Thats the span. The number of data points is 256 so that makes 129
resultant cells (half of the real/imaginary data is redundant) and so the cell
spacing  is about 31hz (4000/128) . The test wave program allows you to create
sine or square wave data anywhere from 0 to 4000hz (assumes a 8000hz sample
rate). The fft then shows a spike at the correct frequency.

    The test hardware I used is a modem chip LM14412 which produces sine wave 
frequencies for a 300 baud modem originate/answer for USA or channel1/channel2
CCITT. This goes to a LM3900 (single supply Norton opamp) and then to a ADC804
(8-bit A/D). With the opamp properly biased and a floating input, I get noise at
a scale factor of 0. When the sine wave is connected (or you touch the input) a
spike is seen a the proper frequency (60hz if touched in the USA) at a scale
factor of 8. 

    I've tried to speed this up everyway I know how. The task now is to reduce
memory requirements. This presently requires 4k: 2k for code, 1k for tables and
1k for data. This includes the graphics routines and the create or collection
routines. I could save some by sampling right in the real data array but this
would interfere with a HAMMING window. I load a 16k wav file using KERMIT 
(see my code for file receive and transmit using the kermit protocol) and
then just copy from the wav file to the real data array. This leads to noise on
the ends. I'm working on a filter for the window.

    I'm NOT a math major though with this I wish I were. It seems one CANNOT be
a good programmer AND a math wiz :-). I have found many good sources of
information about FFT's from surfing the WEB, but all of them quit before going
into explaining implimentation. Some of my programs that involve math back in
the '80s came from an engineering student (Netherlands) working with us that was
able to put an algorithm to simple add, subtract, multiply and divide. I took it
from there and wrote the code blindly. I get them to work but don't know how.
Feel free to enlighten me.

Any questions please email me at: glp@sleepy.anest.ufl.edu.