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