FFT with input in real time, is it possible?

I am new to FFT, but I found that if input is from ADC, the FFT can
only start when half of the data is read in (Assume 1024 point, it starts
when 511st is sampled, i.e. Butter(0, 511), Butter(1, 512), Butter(2, 513),

Is it possible to decompose the sequence to allow Rad-2 butterfly operations
as early as possible, say Butter(0, 1), Butter(2, 3), Butter(4, 5), .. ?

Mr. Ken wrote:

> I am new to FFT, but I found that if input is from ADC, the FFT can
> only start when half of the data is read in (Assume 1024 point, it starts
> when 511st is sampled, i.e. Butter(0, 511), Butter(1, 512), Butter(2, 513),
> 
> Is it possible to decompose the sequence to allow Rad-2 butterfly operations
> as early as possible, say Butter(0, 1), Butter(2, 3), Butter(4, 5), .. ?
> 

Yes, but it's probably not what you want.
You can do "segmented" FFT, processing eg the first 128 samples,
then the second 128-batch and so on, and then combine pairs of sub-FFT's
to the next larger level (256 samples), and so on up to any FT size.

The sub-batches are FFT's of shorter time slices. This means they represent
a cruder frequency resolution, and have higher cut-off of representable frequencies.
And I think you can't do windowing on the input, which is a common technique to
make FT's more palatable. (Or can you? - I tried to think what happens if
one windows the sub-batches then do FFT, then combine pairs. I couldn't
figure it out, but the pictures I got didn't look nice. Research topic there?)

The windowed short-time FT is probably more like what you want, it's perhaps
what you already got... If so, I think you can't make it shorter than required by
the frequency resolution you want.

Searching this some time ago turned up some issues of Parallel Computing
from the 1980's. Some articles can be found online, I just found
"A segmented FFT algorithm for vector computers", by Mike Ashworth.
http://www.informatik.uni-trier.de/~ley/db/journals/pc/pc6.html

Also, a Paul Swartztrauber published on this topic. Google him if you like.


(Not an expert, grateful for any corrections.)

	re