Real time FFT?

Hello all. 

Is it feasable to do an fft in 'real time' on different 'blocks' of data?

(i understand the nomenclature real time may be inappropriate). 


Im thinking, in general usage of an FFT, some x[n] comes in one sample at
a time and fills up a buffer and when that buffer (lets call it 128 time
domain samples) is filled a FFT is taken and the 'output' is 128 points of
frequncy domain data.

Now.. instad of somthing like a sliding DFT where a window evaluates the
previous 127 samples along with one new one, i have a situation where i
want to give the 'fft buffer' 128 NEW data points... so every single 'time
instant'...128 new x[n] data are available.

If this were done would I get a new FFT output at every time instant?

On 29 Jun, 20:24, "westocl" <cwest...@hotmail.com> wrote:
> Hello all.
>
> Is it feasable to do an fft in 'real time' on different 'blocks' of data?

You need to look at the times:

- How often do you want / need a result?
- How long does the computations take?
- What latency is acceptable?

If you have a sampling rate of 1/T, then the limitig factor
is how much work your CPU can get done in T seconds. You
need to get the job done, shuffle the result away and
be ready to start filling the buffer again by the time
the next sample is available T seconds after the buffer is
full.

Rune

>On 29 Jun, 20:24, "westocl" <cwest...@hotmail.com> wrote:
>> Hello all.
>>
>> Is it feasable to do an fft in 'real time' on different 'blocks' of
data?
>
>You need to look at the times:
>
>- How often do you want / need a result?
>- How long does the computations take?
>- What latency is acceptable?
>
>If you have a sampling rate of 1/T, then the limitig factor
>is how much work your CPU can get done in T seconds. You
>need to get the job done, shuffle the result away and
>be ready to start filling the buffer again by the time
>the next sample is available T seconds after the buffer is
>full.
>
>Rune


I need an output at every 'time' instance. Is there any 'pipelined' type
FFT algoritms available that you know of?

I am going to have new data at every sample (im assuming i can run the
clock much faster than the sampling rate)... but at any rate, im thinking
NlogN is still too many calculations unless i have some kind of pipelined
type structure.

westocl wrote:
> Hello all. 
> 
> Is it feasable to do an fft in 'real time' on different 'blocks' of data?
> 
> (i understand the nomenclature real time may be inappropriate). 
> 
> 
> Im thinking, in general usage of an FFT, some x[n] comes in one sample at
> a time and fills up a buffer and when that buffer (lets call it 128 time
> domain samples) is filled a FFT is taken and the 'output' is 128 points of
> frequncy domain data.
> 
> Now.. instad of somthing like a sliding DFT where a window evaluates the
> previous 127 samples along with one new one, i have a situation where i
> want to give the 'fft buffer' 128 NEW data points... so every single 'time
> instant'...128 new x[n] data are available.
> 
> If this were done would I get a new FFT output at every time instant?

You confused me. 128 new instances of x[n] for every n? How?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

>westocl wrote:
>> Hello all. 
>> 
>> Is it feasable to do an fft in 'real time' on different 'blocks' of
data?
>> 
>> (i understand the nomenclature real time may be inappropriate). 
>> 
>> 
>> Im thinking, in general usage of an FFT, some x[n] comes in one sample
at
>> a time and fills up a buffer and when that buffer (lets call it 128
time
>> domain samples) is filled a FFT is taken and the 'output' is 128 points
of
>> frequncy domain data.
>> 
>> Now.. instad of somthing like a sliding DFT where a window evaluates
the
>> previous 127 samples along with one new one, i have a situation where
i
>> want to give the 'fft buffer' 128 NEW data points... so every single
'time
>> instant'...128 new x[n] data are available.
>> 
>> If this were done would I get a new FFT output at every time instant?
>
>You confused me. 128 new instances of x[n] for every n? How?
>
>Jerry
>-- 
>Engineering is the art of making what you want from things you can get.
>�����������������������������������������������������������������������


You are right...My notation is somewhat confusing by using x[n].  But
imagine we had a  switch that will switch to an already full buffer at
every 'sample interval'. Then at the next instant we go to the next 128
buffer and we call that x[n] and so on..

"westocl" <cweston_@hotmail.com> writes:
> [...]
> Is it feasable to do an fft in 'real time' on different 'blocks' of
> data?

What processor? What sample rate? How big of an FFT? 
--
Randy Yates                      % "And all that I can do
Digital Signal Labs              %  is say I'm sorry, 
mailto://yates@ieee.org          %  that's the way it goes..."
http://www.digitalsignallabs.com % Getting To The Point', *Balance of Power*, ELO

>"westocl" <cweston_@hotmail.com> writes:
>> [...]
>> Is it feasable to do an fft in 'real time' on different 'blocks' of
>> data?
>
>What processor? What sample rate? How big of an FFT? 
>--
>Randy Yates                      % "And all that I can do
>Digital Signal Labs              %  is say I'm sorry, 
>mailto://yates@ieee.org          %  that's the way it goes..."
>http://www.digitalsignallabs.com % Getting To The Point', *Balance of
Power*, ELO
>

Im not sure what state of the art is.. but lets say i had maybe a power pc
running at maybe 300 Mhz?? And i think would need a sample rate of maybe
100MHz.  

FFT size of ATLEAST 64.  i would love to have 128.

westocl wrote:
>> westocl wrote:
>>> Hello all. 
>>>
>>> Is it feasable to do an fft in 'real time' on different 'blocks' of
> data?
>>> (i understand the nomenclature real time may be inappropriate). 
>>>
>>>
>>> Im thinking, in general usage of an FFT, some x[n] comes in one sample
> at
>>> a time and fills up a buffer and when that buffer (lets call it 128
> time
>>> domain samples) is filled a FFT is taken and the 'output' is 128 points
> of
>>> frequncy domain data.
>>>
>>> Now.. instad of somthing like a sliding DFT where a window evaluates
> the
>>> previous 127 samples along with one new one, i have a situation where
> i
>>> want to give the 'fft buffer' 128 NEW data points... so every single
> 'time
>>> instant'...128 new x[n] data are available.
>>>
>>> If this were done would I get a new FFT output at every time instant?
>> You confused me. 128 new instances of x[n] for every n? How?
>>
>> Jerry
>> -- 
>> Engineering is the art of making what you want from things you can get.
> 
> 
> You are right...My notation is somewhat confusing by using x[n].  But
> imagine we had a  switch that will switch to an already full buffer at
> every 'sample interval'. Then at the next instant we go to the next 128
> buffer and we call that x[n] and so on..

What fills these nearly full buffers? When? You seem to want 128 new 
samples per sampling instant. That can't be sustained.

Jerry
-- 
Engineering is the art of making what you want from things you can get.

>westocl wrote:
>>> westocl wrote:
>>>> Hello all. 
>>>>
>>>> Is it feasable to do an fft in 'real time' on different 'blocks' of
>> data?
>>>> (i understand the nomenclature real time may be inappropriate). 
>>>>
>>>>
>>>> Im thinking, in general usage of an FFT, some x[n] comes in one
sample
>> at
>>>> a time and fills up a buffer and when that buffer (lets call it 128
>> time
>>>> domain samples) is filled a FFT is taken and the 'output' is 128
points
>> of
>>>> frequncy domain data.
>>>>
>>>> Now.. instad of somthing like a sliding DFT where a window evaluates
>> the
>>>> previous 127 samples along with one new one, i have a situation
where
>> i
>>>> want to give the 'fft buffer' 128 NEW data points... so every single
>> 'time
>>>> instant'...128 new x[n] data are available.
>>>>
>>>> If this were done would I get a new FFT output at every time
instant?
>>> You confused me. 128 new instances of x[n] for every n? How?
>>>
>>> Jerry
>>> -- 
>>> Engineering is the art of making what you want from things you can
get.
>> 
>> 
>> You are right...My notation is somewhat confusing by using x[n].  But
>> imagine we had a  switch that will switch to an already full buffer at
>> every 'sample interval'. Then at the next instant we go to the next
128
>> buffer and we call that x[n] and so on..
>
>What fills these nearly full buffers? When? You seem to want 128 new 
>samples per sampling instant. That can't be sustained.
>
>Jerry
>-- 
>Engineering is the art of making what you want from things you can get.


It seems thats exactly the case i will have... What i want to do is
analagous to having 128 antennas and a situation where i have to take the
FFT for each antenna. So some kind of rotary switch gives me the new
antenna input data at every sample... and will keep spinning.

westocl wrote:
>> westocl wrote:
>>>> westocl wrote:
>>>>> Hello all. 
>>>>>
>>>>> Is it feasable to do an fft in 'real time' on different 'blocks' of
>>> data?
>>>>> (i understand the nomenclature real time may be inappropriate). 
>>>>>
>>>>>
>>>>> Im thinking, in general usage of an FFT, some x[n] comes in one
> sample
>>> at
>>>>> a time and fills up a buffer and when that buffer (lets call it 128
>>> time
>>>>> domain samples) is filled a FFT is taken and the 'output' is 128
> points
>>> of
>>>>> frequncy domain data.
>>>>>
>>>>> Now.. instad of somthing like a sliding DFT where a window evaluates
>>> the
>>>>> previous 127 samples along with one new one, i have a situation
> where
>>> i
>>>>> want to give the 'fft buffer' 128 NEW data points... so every single
>>> 'time
>>>>> instant'...128 new x[n] data are available.
>>>>>
>>>>> If this were done would I get a new FFT output at every time
> instant?
>>>> You confused me. 128 new instances of x[n] for every n? How?
>>>>
>>>> Jerry
>>>> -- 
>>>> Engineering is the art of making what you want from things you can
> get.
>>>
>>> You are right...My notation is somewhat confusing by using x[n].  But
>>> imagine we had a  switch that will switch to an already full buffer at
>>> every 'sample interval'. Then at the next instant we go to the next
> 128
>>> buffer and we call that x[n] and so on..
>> What fills these nearly full buffers? When? You seem to want 128 new 
>> samples per sampling instant. That can't be sustained.
>>
>> Jerry
>> -- 
>> Engineering is the art of making what you want from things you can get.
> 
> 
> It seems thats exactly the case i will have... What i want to do is
> analagous to having 128 antennas and a situation where i have to take the
> FFT for each antenna. So some kind of rotary switch gives me the new
> antenna input data at every sample... and will keep spinning.

There's nothing unusual about simultaneously processing multiple 
streams. But each stream would have it's own FT. There could be 128 
samples collected at each sample interval, but probably not via a 
multiplexer (rotary switch). One of us is still confused.

Jerry
-- 
Engineering is the art of making what you want from things you can get.