# Can I take piecewise FFT of a larger input sample?

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

• Thank you Matt. That helped a lot. Can you add this as an answer so that I can Vote-up? – kviggy0 Dec 16 '14 at 13:05

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.

• 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 – kviggy0 Dec 31 '14 at 10:21
• @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. – kviggy0 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. – kviggy0 Dec 31 '14 at 10:57