Any FFT trick to do this?

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