I would suggest one of two approaches:

1. Try Walsh transforms that use relatively lightweight mathematics, but
give only frequency data in the bins.

2. Do a full FFT which consists of a) "butterflying" (which eliminates
redundant calculations and is the main difference between the DFT and the
FFT, then b) performing some seemingly complex multiplication by
transendental functions. As Imre suggests, the use of tables can be used if
your sampling frequency stays fixed. (Actually most DSP filters, etc. can be
approximated fairly closely using the table lookup methods if one knows the
coefficients, etc.) The 17C42 note is a good starting place.

In both cases, the number of bins is a concern because of the limited
memory.

Tom

> -----Original Message-----
> From: pic microcontroller discussion list
> [mailto:PICLIST@MITVMA.MIT.EDU]On Behalf Of MILTON MEDICINTEKNIK KB
> Sent: Monday, August 30, 1999 3:53 PM
> To: PICLIST@MITVMA.MIT.EDU
> Subject: Cheat-cheap FFT:
>

> Hello everyone out there ,
>
> Is it my turn now? I have been on this list for a few months;
> find it very interesting, and have learnt a lot. I also hope
> I have added a few cents worth...
>
> Competence is very high amongst contribituors, and I guess
> the following issue can be solved - or already have been
> solved by a few of you: A suggestion for approoach would be
> appreciated:
>
> I would like to measure the frequency of signals in the 1 --
> 20 Hz range, not using a DSP or anything other that the
> already engaged PIC 16C711. It uses a timer interrupt
> routine, that is it idles most of the time, but every
> millisecond it jumps out of the loop and polls the AD RES.
> The A/D is of course picking up the low freq. "AC" (actually
> 0 -- 5V) to be measured.
>
> My idea was to see on each sample if the previous sample was
> smaller. If so, the voltage is ascending. When descending
> (implementing 3 bits of noice reducing "backlash") I have
> found a point in time when the peak was found.
> Correspondingly, I find the "valley". The idia is based on a
> counter that is stepped up every ms, and is used to measure
> the time between peaks and valleys. In other words, if there
> are 100 counts between a valley and a peak, we have =
> wavelength being 100 ms long. 5Hz - right ?
>
> I have 20 registers. If the frequency is 1.5 -- 2.5 Hz, I add
> one to the "2 Hz register". If the frequency is 18.5 -- 19.5
> Hz, I call it 19Hz. After a few seconds of measurement, I
> should have a handfull of values in the registers, to
> correspond to the frequency components of the signal.
>
> This should work for pretty and clear sinewaves. But these
> signals are actually noisy with - for instance - long "flats"
> to consider, when finding a correct point in time. Actually
> the signal can be considered a random pink noice.
>
> The signal is in other words a bit complex for finding
> frequency components in a FFT-type fashion. If it is 5 Hz
> with a dent in it, it is maybe 80 % 5 Hz, 15 % 15 Hz . . so
> to speak. This is not imortant in detail. I would like to
> know that the base is 5 Hz.
>
> Now to the problem. It doesn't  __  work. Am I too optimistic
> ? Should I realize that a PC or a DSP of some quick sort is
> needed for this? Am I better off "zero cross-detecting" at 2.5 Volts?
>
> So - the question is -  has anyone been walking this path
> before ? Am I on the right track ?
>
> Sven
>