Thank you very much for all the replies.

Actually when I thought more the sliding DFT or Geortzel algorithm do not
work for me since I need to find a lot more than one bin of the FFt at a
time.

I do have a question on the scalable FFT. I will post a different thread
on that since its not related to this.

Thank you very much.

Greg Berchin  <gberchin@comicast.net.invalid> wrote:

><eric.jacobsen@ieee.org> wrote:

>>The sliding DFT makes use of recursion to reduce the computational
>>load for the special case of windows advancing a sample at a time. If
>>the window advances by more than one sample, the computations are no
>>longer valid due to the missed steps in the recursion.

>A similar recursion can be formulated for "hops" greater than one
>sample.  It's a straightforward derivation.

I do not think OP stated he needed a sliding DFT; just a DFT with low
latency.  Perhaps this could be clarified.

Steve

On Wed, 18 Feb 2009 12:54:08 -0700, Eric Jacobsen
<eric.jacobsen@ieee.org> wrote:

>The sliding DFT makes use of recursion to reduce the computational
>load for the special case of windows advancing a sample at a time. If
>the window advances by more than one sample, the computations are no
>longer valid due to the missed steps in the recursion.

A similar recursion can be formulated for "hops" greater than one
sample.  It's a straightforward derivation.

Greg

On Wed, 18 Feb 2009 01:35:04 -0600, "m26k9"
<maduranga.liyanage@gmail.com> wrote:

>I was looking at 'sliding DFT' approach.. looks like it has some hope..
>but I want to see if I can do it for steps larger than one. I.e. rather
>than advancing the window by one sample, advance it by say N/2 samples. 

The sliding DFT makes use of recursion to reduce the computational
load for the special case of windows advancing a sample at a time. If
the window advances by more than one sample, the computations are no
longer valid due to the missed steps in the recursion.

Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.ericjacobsen.org

Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php

Thank you for the help Steve.

right now I am looking for how the scalable FFT is implemented in
hardware. Because my interleaving factor is not a constant. It can change
up to some maximum value. So having a hardwired approach maybe not be
possible. Appreciate the help a lot Steve.

Cheers.

m26k9 <maduranga.liyanage@gmail.com> wrote:

>That method would work as a 'paper based' approach like I said. But seems
>its a complete re-work of the FFT module.

>I guess it is not readily possible to achieve the interleaved FFT. I mean
>to achieve it with minimal modification (if possible from outside of the
>FFT)...

Sure, if there's an existing FFT block, say in verilog, a reasonable
verilog designer could modify it into an interleaved version in
pretty short order... depending upon requirements.  But, it
is a mod, it would have to be tested and verified and 
timing-verified etc.

>I was looking at 'sliding DFT' approach.. looks like it has some hope..
>but I want to see if I can do it for steps larger than one. I.e. rather
>than advancing the window by one sample, advance it by say N/2 samples. 

The sliding DFT is simple, and as you are doing it from scratch
you can design in the interleaving from the outset.  It will be
more logic gates than an FFT-based version.  Maybe not by a huge
ratio but by a significant one.

Steve

Thank you Steve.

That method would work as a 'paper based' approach like I said. But seems
its a complete re-work of the FFT module.

I guess it is not readily possible to achieve the interleaved FFT. I mean
to achieve it with minimal modification (if possible from outside of the
FFT)...

I was looking at 'sliding DFT' approach.. looks like it has some hope..
but I want to see if I can do it for steps larger than one. I.e. rather
than advancing the window by one sample, advance it by say N/2 samples. 

Thank you again Steve.

m26k9 <maduranga.liyanage@gmail.com> wrote:

>Thank you Tim.
>
>Actually the real requirement is the efficient processing of the
>interleaved samples. And what I am interested is being able to do this with
>(minimal) modification to the radix-2 type FFT. I am actually not trying to
>implement this at this on Simulink or FPGA  at the moment. I'm trying to
>find a paper based method.

The goal in processing an interleaved stream is often to
avoid having too much parallel hardware, that is idle on
most clock cycles.

Speaking generally again, if you have a hardware block
that performs processing on an uninterleaved data stream, 
and you can get inside that block and replace every instance
of data-path register state with N instances and the appropriate 
timing chain, you can then process an N-way interleaved data stream.

If the basic un-interleaved block has been synthesized, and you can 
count the cell instances of registers vs. other types of gates, you
can roughly put together an estimate of the larger, interleaved
version.

Such an approach might serve the purposes of a paper design.

Steve

Thank you Tim.

Actually the real requirement is the efficient processing of the
interleaved samples. And what I am interested is being able to do this with
(minimal) modification to the radix-2 type FFT. I am actually not trying to
implement this at this on Simulink or FPGA  at the moment. I'm trying to
find a paper based method.

For example, like I gave in the previous post about the Rick lyons way to
break up a large DFT to smaller FFT's. Like that I want to find a way to
manipulate the standard FFT to perform the interleaved FFT. 

Basically, trying to find out a way to efficiently do it rather than
waiting for all the samples and arranging them and FFT'ing separately. 

Thank you.

On Tue, 17 Feb 2009 22:35:18 -0600, m26k9 wrote:

> Hello,
> 
> I don't know if its possible to do this with a FFT block, but I hope
> someone could shed some light on.
> 
> So basically I receive a train of pulse, say
> x(t)=x(0),x(1),x(2),x(3),...,x(7).
> 
> What I want to do is to perform 2x4-point FFT's in this order:
> 
> FFT{x(0),x(2),x(4),x(6)}, and;
> FFT{x(1),x(3),x(5),x(7)}.
> 
> Now I was wondering if there's anyway I can do this, without waiting for
> the whole 8 points to arrive, and then dividing them into their
> respective sets, and performing two separate 4-point FFT's.
> 
> Suppose if I have a FFT module that support larger FFT points, is there
> any trick to this faster than doing two separate 4-points FFT's?
> 
> Any leads are greatly welcome.
> 
> Thank you.

What framework does this "FFT block" come from?  Simulink?  Some FPGA 
tool?  What?

Whether you can do something with someone's specific implementation of an 
algorithm (i.e. a block) depends both on their implementation and the 
algorithm.

-- 
http://www.wescottdesign.com