combining small FFTs to make a larger FFT

Hello,

When combining two smaller FFTs to make a larger one, what are the
techniques. Example..I want to combine two 64 pt FFTs into a 128 pt FFT. I
have fed the first 64 data samples into the first FFT and the second 64
into the 2nd FFT. The results are output from the two FFTs into a 128
array. The problem is that the 128 pt FFT result has the same peaks as the
64 pt FFT. What is the problem here? How do I correct this in order to get
the same results as the standard 128 pt FFT?

Thank you
DJ

On Jun 1, 8:06 pm, "digintu" <digi...@gmail.com> wrote:
>
> When combining two smaller FFTs to make a larger one, what are the
> techniques.


> Example..I want to combine two 64 pt FFTs into a 128 pt FFT. I
> have fed the first 64 data samples into the first FFT and the second 64
> into the 2nd FFT.  The results are output from the two FFTs into a 128
> array. The problem is that the 128 pt FFT result has the same peaks as the
> 64 pt FFT. What is the problem here? How do I correct this in order to get
> the same results as the standard 128 pt FFT?

you're missing a step or two.  if you're gonna stuff two halves of
your length 128 data into two length 64 FFTs and post-process the
results, you have to put the even-indexed samples in one and the odd-
index samples in another.  do two 64-pt FFTs, and post process the
results with 64 butterflies that have coefficients of

   W(k) = exp(j*2*pi*k/N)    for   0 <= k < N/2

where N is 128.  this is called the Decimation-In-Time algorithm.

if you want to do this in normal order and toss the "first half" in
one FFT and the "last half" in the other FFT, that's the Decimation-In-
Frequency algorithm and instead of post-processing the results, you
*pre*-process what goes in with similar looking butterflies.  either
the DIT or DIF can be done in-place where the input is in normal or
bit-reversed order and the output would then naturally end up bit-
reversed or normal, respectively.  in fact, the DIT with normal input,
bir-reversed output, can be compared directly to the DIF with bit-
reversed input and normal order output.  a butterfly in the final
stage (or "pass") of the DIT simply has its function inverted with the
corresponding butterfly in the first pass of the DIF.  (assume the
first DIT alg is a "forward DFT" and the second DIF alg is set for
"inverse DFT".  "j" in the first becomes "-j" in the second.)

r b-j

>On Jun 1, 8:06 pm, "digintu" <digi...@gmail.com> wrote:
>>
>> When combining two smaller FFTs to make a larger one, what are the
>> techniques.
>
>
>> Example..I want to combine two 64 pt FFTs into a 128 pt FFT. I
>> have fed the first 64 data samples into the first FFT and the second
64
>> into the 2nd FFT.  The results are output from the two FFTs into a 128
>> array. The problem is that the 128 pt FFT result has the same peaks as
the
>> 64 pt FFT. What is the problem here? How do I correct this in order to
get
>> the same results as the standard 128 pt FFT?
>
>you're missing a step or two.  if you're gonna stuff two halves of
>your length 128 data into two length 64 FFTs and post-process the
>results, you have to put the even-indexed samples in one and the odd-
>index samples in another.  do two 64-pt FFTs, and post process the
>results with 64 butterflies that have coefficients of
>
>   W(k) = exp(j*2*pi*k/N)    for   0 <= k < N/2
>
>where N is 128.  this is called the Decimation-In-Time algorithm.
>
>if you want to do this in normal order and toss the "first half" in
>one FFT and the "last half" in the other FFT, that's the Decimation-In-
>Frequency algorithm and instead of post-processing the results, you
>*pre*-process what goes in with similar looking butterflies.  either
>the DIT or DIF can be done in-place where the input is in normal or
>bit-reversed order and the output would then naturally end up bit-
>reversed or normal, respectively.  in fact, the DIT with normal input,
>bir-reversed output, can be compared directly to the DIF with bit-
>reversed input and normal order output.  a butterfly in the final
>stage (or "pass") of the DIT simply has its function inverted with the
>corresponding butterfly in the first pass of the DIF.  (assume the
>first DIT alg is a "forward DFT" and the second DIF alg is set for
>"inverse DFT".  "j" in the first becomes "-j" in the second.)
>
>r b-j
>

Hi Robert,

Appreciate that Robert. Yep..That just confirms exactly what I've just
been thinking of doing. I'll go for the DIT method and see what the results
look like.

DJ  

>On Jun 1, 8:06 pm, "digintu" <digi...@gmail.com> wrote:
>>
>> When combining two smaller FFTs to make a larger one, what are the
>> techniques.
>
>
>> Example..I want to combine two 64 pt FFTs into a 128 pt FFT. I
>> have fed the first 64 data samples into the first FFT and the second
64
>> into the 2nd FFT.  The results are output from the two FFTs into a 128
>> array. The problem is that the 128 pt FFT result has the same peaks as
the
>> 64 pt FFT. What is the problem here? How do I correct this in order to
get
>> the same results as the standard 128 pt FFT?
>
>you're missing a step or two.  if you're gonna stuff two halves of
>your length 128 data into two length 64 FFTs and post-process the
>results, you have to put the even-indexed samples in one and the odd-
>index samples in another.  do two 64-pt FFTs, and post process the
>results with 64 butterflies that have coefficients of
>
>   W(k) = exp(j*2*pi*k/N)    for   0 <= k < N/2
>
>where N is 128.  this is called the Decimation-In-Time algorithm.
>
>if you want to do this in normal order and toss the "first half" in
>one FFT and the "last half" in the other FFT, that's the Decimation-In-
>Frequency algorithm and instead of post-processing the results, you
>*pre*-process what goes in with similar looking butterflies.  either
>the DIT or DIF can be done in-place where the input is in normal or
>bit-reversed order and the output would then naturally end up bit-
>reversed or normal, respectively.  in fact, the DIT with normal input,
>bir-reversed output, can be compared directly to the DIF with bit-
>reversed input and normal order output.  a butterfly in the final
>stage (or "pass") of the DIT simply has its function inverted with the
>corresponding butterfly in the first pass of the DIF.  (assume the
>first DIT alg is a "forward DFT" and the second DIF alg is set for
>"inverse DFT".  "j" in the first becomes "-j" in the second.)
>
>r b-j
>

Hi Robert,

A further question....first, I'll explain what I've done so far...

I fed in the input samples into an array while bit reversing the
locations. Then I fed the stored data into 64 radix2 butterflies. The two
outputs from these butterfiles is stored sequentially in another
arrays..ie
Butterfly 1 stores it's two complex outputs in locations 0 and 1

Even though I have real and imagininary results, I want to keep it simple
and say that the first complex result (Real and Imag) from butterfly 1 is
stored in location 0 and the second complex result (Real and Imag) from
butterfly 1 is stored in location 1  

Butterfly 2 stores it's two complex outputs in locations 2 and 3
and so on.

Now how do I index this data from the Radix2 results array to present it
to the Radix4 FFT?

Also for this radix4 FFT, the output is 4-based reversed ordered....
a0a1a2a3a4a5a6a7a8a9 => a8a9a6a7a4a5aa2a3a0a1. It is the opencores cfft.
Will my initial bit reversal negate, the built in reverse-ordering so that
I get the correct order at the output?

Many thanks
DJ
  
 

>When combining two smaller FFTs to make a larger one, what are the
>techniques. Example..I want to combine two 64 pt FFTs into a 128 pt FFT.
I
>have fed the first 64 data samples into the first FFT and the second 64
>into the 2nd FFT. The results are output from the two FFTs into a 128
>array. The problem is that the 128 pt FFT result has the same peaks as
the
>64 pt FFT. What is the problem here? How do I correct this in order to
get
>the same results as the standard 128 pt FFT?
 
It is not clear from your posting how the two 64 pt sequences are related
in time.

Are they sequential, i.e., {x[n]} n=1,...,64 for the first, and
n=65,...,128 for the second?

Or are they even and odd samples of a 128 point sequence?

emre

 
>It is not clear from your posting how the two 64 pt sequences are
related
>in time.
>
>Are they sequential, i.e., {x[n]} n=1,...,64 for the first, and
>n=65,...,128 for the second?
>
>Or are they even and odd samples of a 128 point sequence?
>
>emre
>
I initially had them sequential x[n]  n = 1...64 for the first and n =
65..128 for the second.

I can change them to suit any method. If you look at my post from earlier
today in response to Robert, I currently have the input indexes bit
reversed and passed through 64 radix2 butterflys. I'm now looking for the
correct way to present that data to the radix4 ffts.

Bob

>I initially had them sequential x[n]  n = 1...64 for the first and n =
>65..128 for the second.
>
>I can change them to suit any method. 

Bob, if you take the even and odd samples as your 64-point sequences, the
result is elegantly simple.

Say x_e[n] = x[2n], and x_o = x[2n+1], n = 0,...,63.

Then, X[k] = X_e[k] + exp(-j*2*pi*k/128) * X_o[k],   k = 0,...,127,  where
X_e and X_o are the 64-point DFTs of x_e and x_o, respectively. You should
take the mod(64) values of k on the right side, i.e. rem(k,64) in Matlab
language, since X_e and X_o are periodic with 64.

You can verify this by partitioning the sum for X[k], the 128-point DFT,
into even and odd samples.

Hope this helps.

Emre

>Then, X[k] = X_e[k] + exp(-j*2*pi*k/128) * X_o[k],   k = 0,...,127, 
where
>X_e and X_o are the 64-point DFTs of x_e and x_o, respectively. You
should
>take the mod(64) values of k on the right side, i.e. rem(k,64) in Matlab
>language, since X_e and X_o are periodic with 64.

Just for the heck of it, here is the verifying Matlab code:

>> x=randn(128,1);
>> xe = x(1:2:end);
>> xo = x(2:2:end);
>> X = fft(x);
>> Xe = fft(xe);
>> Xo = fft(xo);
>> Xel = [Xe;Xe] + exp(-j*2*pi*[0:127].'/128) .* [Xo;Xo];
>> max(abs(Xel-X))

ans =

   8.8818e-15

digintu asks:

I'm trying to implement this in an FPGA so it takes a bit of time. Another
question...If I had a 256 pt FFT, would it be easier to get the results for
a 128 pt result out of it...ie have two 128 pt results.

any ideas?

>>Then, X[k] = X_e[k] + exp(-j*2*pi*k/128) * X_o[k],   k = 0,...,127, 
>where
>>X_e and X_o are the 64-point DFTs of x_e and x_o, respectively. You
>should
>>take the mod(64) values of k on the right side, i.e. rem(k,64) in
Matlab
>>language, since X_e and X_o are periodic with 64.
>
>Just for the heck of it, here is the verifying Matlab code:
>
>>> x=randn(128,1);
>>> xe = x(1:2:end);
>>> xo = x(2:2:end);
>>> X = fft(x);
>>> Xe = fft(xe);
>>> Xo = fft(xo);
>>> Xel = [Xe;Xe] + exp(-j*2*pi*[0:127].'/128) .* [Xo;Xo];
>>> max(abs(Xel-X))
>
>ans =
>
>   8.8818e-15
>
>