1
$\begingroup$

I have a N point sequence x. Let X be the fft(x). (Assume x is arbitrary)

where,

x=[x1 x2 x3 x4 x5 x6 x7 x8] 

fft(x)=[X1 X2 X3 X4 X5 X6 X7 X8]

How do I get the result of a 8 point DFT by doing cascading 4 point DFT and 2 point DFT?

Suppose I reshape the signal 'x' (of dimensions '1 x 8') to 'x1' (of dimensions '2 x 4')

x1=[x1 x2 x3 x4;
   x5 x6 x7 x8]

fft(x1 (first row)) i.e. fft(x1 x2 x3 x4) say =  [Y1 Y2 Y3 Y4]
fft(x1 (second row)) i.e. fft(x4 x5 x6 x7)  say = [Y5 Y6 Y7 Y8]

Then again taking fft column wise

fft(Y1 Y5)  say = [Z1 Z2]
fft(Y2 Y6)  say = [Z3 Z4]
fft(Y3 Y7)  say = [Z5 Z6]
fft(Y4 Y8)  say = [Z7 Z8]

However this Z will not be equal to X. How do I proceed to get X by doing these smaller point FFTs?

Any help would be great! Thanks

Improve this question
$\endgroup$
  • 1
    $\begingroup$ This answer should also answer your question. $\endgroup$ – Matt L. Dec 16 '14 at 12:03
  • $\begingroup$ Thank you Matt. That helped a lot. Can you add this as an answer so that I can Vote-up? $\endgroup$ – kviggy0 Dec 16 '14 at 13:05
3
$\begingroup$

You need the Cooley-Tukey algorithm, which can be used to express the DFT of size $N=N_1N_2$ by DFTs of sizes $N_1$ and $N_2$. It works a bit like what you sketched in your question, but you forgot the twiddle factors. This answer explains the details of the algorithm and it also includes a simple Matlab implementation.

EDIT (see comments): If you really want to compute the FFTs of blocks of consecutive data you need to split the computation of even and odd frequency indices (assuming the DFT length $N$ is even):

$$X[2k]=\sum_{n=0}^{N/2-1}\left(x[n]+x[n+N/2]\right)W_{N/2}^{nk}\\ X[2k+1]=\sum_{n=0}^{N/2-1}\left(x[n]-x[n+N/2]\right)W_N^nW_{N/2}^{nk}\tag{1}$$

where $W_N=e^{-j2\pi/N}$. Note that you can of course compute the DFTs of the length $N/2$ sub-blocks separately instead of adding (or subtracting) the blocks before the DFT (as in (1)), but this is computationally less efficient.

Improve this answer
$\endgroup$
  • $\begingroup$ Hi Matt, Your answer stores the signal row-wise and takes the first FFT column wise. But acc to the question, it should store row-wise and take the first FFT row-wise. and then col-wise $\endgroup$ – kviggy0 Dec 31 '14 at 10:21
  • 1
    $\begingroup$ @viggy: OK, then just do that, you basically just transpose a matrix, no big deal. $\endgroup$ – Matt L. Dec 31 '14 at 10:27
  • $\begingroup$ Thanks for the fast reply. My confusion was to whether there will be a change in the twiddle factors as we are now altering the sequence? Transposing the twiddle factors to match the dimension of the (now transposed) signal doesn't give the correct answer. $\endgroup$ – kviggy0 Dec 31 '14 at 10:35
  • $\begingroup$ @viggy: OK, I see, so you don't want to interleave the time domain data (why?), but you want to use blocks of consecutive data. There's a way to do that but I'll have to come back to it a few days from now due to lack of time. $\endgroup$ – Matt L. Dec 31 '14 at 10:48
  • $\begingroup$ Thank you Matt. I don't want to interleave the data because I am assuming that I am getting the consecutive data on each time frame (t1=0, i get N2 points, t=1, i get another N2 points, where N2 is the no. of columns here.) and I have to immediately take fft of those points as they come... There is no commutator in this case. Thank you once again for taking interest. Even I will try and email you if I get the solution. $\endgroup$ – kviggy0 Dec 31 '14 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.