2D FFT using 1D FFT

Question

I am trying to implement a 2D FFT using a 1D FFT. I have a 4x4 matrix (some basic)

My algorithm:

• FFT at all 16 points
• U-turn bits.
• transpose
• 16 point FFT
• U-turn bits.
• transpose

Is it correct?

Answer 1

No - algorithm:

• make 1D FFT on each line (from real to complex)
• make 1D FFT on each column as a result of (1) (complex complex)

So this is a 4 x 1D (horizontal) FFT, followed by a 4 x 1D (vertical) FFT, for a total of 8 x 1D FFT.