Any FFT trick to do this?

Started by m26k9 February 18, 2009
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.
m26k9 <maduranga.liyanage@gmail.com> wrote:

> 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.
Ignoring for the moment that you want to interlave two blocks, and speaking to the general question of latency, one can sometimes perform a DFT as the data comes in, and have the result ready soon after the last datapoint arrives. The amount of computation is greater than an FFT algorithm but the latency is less. Steve
Thank you very much Steve.
But one of the problems is whether I can do this sequential DFT with an
FFT module?
I will have a look in this method. Thank you.
m26k9 <maduranga.liyanage@gmail.com> wrote:

>Thank you very much Steve. >But one of the problems is whether I can do this sequential DFT with an >FFT module?
Maybe, sort of, if you can break it up. Have a decimation-in-time stage of a small radix (like 4) ahead of a smaller FFT, in a way that saves most of the latency. (This is assuming your real problem isn't actually length 8, but something larger.) I'm sure you can get more accurate advice on this from some others here. Steve
Thank you Steve.
Yes my FFT is much larger and also I am not interleaving by one sample. It
could be more than that.

I actually found this (http://www.dsprelated.com/showarticle/63.php)
article here which mentions a way to break up FFT's in to smaller parts. I
guess it works for my case. 

But the problem now is, if there is a method to do 2 FFT's with one FFT
module. For example, do 2x4-point FFT's with one 8-point FFT.

From a radix-2 Butterfly architecture I dont think it is possible. 

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
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.
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 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:

>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