> From: nogueira <nogueira@MANDIC.COM.BR>
>
> Hi,
> This time I need help from the gurus, like Andy.

If you can accomplish this, consider yourself a 'guru'.

> I have a 16C62, a graphic lcd display, an A/D and 4K external RAM.
> I can digitalize 4K of analog data at 100ns rate, I can show the
> wave on the display. Now what I whant is to do FFT to show the
> spectrun. Does any one have done this before? Have any piece
> of code?
> I will be very thankfull for any help.
>
> Cheers,
>
> Octavio

The essential elements you need for FFT are:

.  A table of (or ability to calculate) 'twiddle factors' which are
basically sines and cosines of an angular increment.

.  Multiplication and addition routines.  This also involves scaling
of the intermediate results to avoid overflow, since you will
probably be using fixed point arithmetic.

.  A bit-reversal algorithm for performing the 'butterfly' algorithm.

.  In your case, because you are only interested in the spectrum not
the phases, you need to be able to massage the FFT result so that
the unnecessary information is removed.

.  FFTs generally transform complex data.  Since you have real data,
it needs to be preprocessed so the FFT thinks it is operating on
complex data.  There are efficient algorithms for this.

Fortunately, the FFT can be performed in-place i.e. not requiring much
additional storage (except that you will have to expand it into higher
precision - see below).  The original data (time) gets replaced with
the transformed data (frequency).  If your time data is 8-bits per
sample, you will need to use more bits for all intermediate
calculations.  16 bits is overkill for 8-bit data, however this is
probably easier than trying to pack it in to 12 bits.

So the first step will be to expand your original data into an array
of 16-bit values (the LSBs will be zeros).  While doing this, subtract
a 'straight line' function from the data so that the first and last
elements in the array have the same value, and the average value of all
the data is zero.  This removes any DC offset in the data, and reduces
spurious high frequencies from the spectrum which are caused by the
'glitch' at the data boundaries.  Although this step is not strictly
necessary, doing it is fairly easy and worthwhile.

Each 16-bit value will be a number from -16384 to 16384.  For the
purposes of the arithmetic, this is actually treated as a number
between -1.0 <= x <= 1.0.  Note that the full range (+-32768/7) is not
used so as to prevent problems with overflow in the intermediate
results, and the troublesome 'missing value' of +32768.  This is
acceptable for 8-bit data.

Now for the tricky bit!  Transform the data in-place using FFT
algorithm.  Proper FFT devices use a table lookup for the twiddle
factors.  I can't remember precisely, but the butterfly technique
minimises the number of twiddle factors which need to be stored.  Since
they are all in the range -1.0 <= t <= 1.0, they are also stored using
the +-16384 convention.  Hopefully you have some ROM available for this.

Bit reversal of a 16-bit value is quite easy with PIC devices and takes
about as long as 8-bit reversal.  Paraphrasing my previous posting re
bit reversal, if r1 and r2 are the registers comprising the 16-bit
value to reverse, then

        rlf     r2,w    ; Prime carry-out from MSB(r2)

        rrf     r1
        rlf     r2
        ... (the above 2 instructions repeated 8 times total)

accomplishes 16 bit reversal.  However, some algorithms use other
information to accomplish this task rather than explicit reversal
as presented above.

Regarding the algorithm and bookkeeping details, I would refer you
to your local library since I am rapidly getting out of my depth.
FFTs are really the domain of specialised processors or more powerful
micros.  However, if you manage this monumental task, please post the
code into the public domain for our edification.

Regards,
SJH
Canberra, Australia