[Openeeg-list] Re: FFT

[Jerry J. <je...@je...>]

Attached is an attempt to get the FFTs working on an
AVR to see if its worth pursuing, so I would
appreciate any comments.

Peter, it does use a precomputed sine table, which is
moved into flash to save memory.

From the test, my conclusion is that a 16Mhz ATMega128
should be able to perform an FFT analysis on a sample
of 512 sixteen bit data points in about 100
milliseconds.  (The max number of data points is 512
because 1024 would exceed the 4k of ram available)

How I arrived at this conclusion was from tests on an
8Mhz ATMega163 using sample sizes of 8, 16, 32, and 64
sixteen bit values, which took 1, 4, 9, and 23
milliseconds respectively and then curve fitted 128,
256, and 512 sample sizes.  (This might be all wrong,
I would really like to try this out on an ATMega128 to
get the actual speed).

I agree that the PC is a far more suitable platform to
do analysis, but there might be advantages to handing
the PC the FFT results instead of the sampled data. 
This would really conform to the true raw data (analog
brain waves) a little better, and it keeps the
possibility of implementing a standalone EEG HID
device (my goal).

Jerry

--- Peter Jacobi <pet...@gm...> wrote:
> 128 sample FFT can be done with 16 bit precision.
> Easiest is to
> use the complex algorithm, making it do two segments
> in one 
> pass. This gives a working area of 128x2x2=512
> bytes. The
> normal butterfly algorithm only needs O(1) temporary
> storage,
> but you have to store precomputed sin/cos tables.
> They would
> also be 128 complex numbers = 512 bytes , but if you
> spend some 
> time for reduction to to sin(0..90), you can get
> away with one eight
> of this, i.e. 64 bytes.