2

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

swallowroot
  • 63
  • 8

1 Answers1

3

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.

Community
  • 1
Matt L.
  • 89,963
  • 9
  • 79
  • 179
  • 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 – swallowroot Dec 31 '14 at 10:21
  • 1
    @viggy: OK, then just do that, you basically just transpose a matrix, no big deal. – Matt L. Dec 31 '14 at 10:27
  • 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. – swallowroot Dec 31 '14 at 10:35
  • @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. – Matt L. Dec 31 '14 at 10:48
  • 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. – swallowroot Dec 31 '14 at 10:57
  • @viggy: I added some more information to my answer about using blocks of consecutive data. – Matt L. Jan 03 '15 at 20:53
  • @viggy: Also have a look at this thread. – Matt L. Jan 04 '15 at 11:59
  • One could also think of sliding DFT with zero overlap. @Matt L. – swallowroot Jan 05 '15 at 17:15
  • If I understand correctly, the complexity for using blocks of consecutive data will be O(N^2), which makes it less efficient than computing the FFT from scratch O(N*log N) .... however, for relatively small N, maybe the constants in front of these complexities can make the N^2 solution competitive? – Olivier Sohn Oct 19 '18 at 18:04