2D FFT using 1D FFT

Question

I am trying to implement a 2D FFT using 1D FFTs. I have a matrix of size 4x4 (row major)

My algorithm is:

1. FFT on all 16 points
2. bit reversal
3. transpose
4. FFT on 16 points
5. bit reversal
6. transpose

Is this correct?

Answer 1

No - the algorithm is:

1. do 1D FFT on each row (real to complex)
2. do 1D FFT on each column resulting from (1) (complex to complex)

So it's 4 x 1D (horizontal) FFTs followed by 4 x 1D (vertical) FFTs, for a total of 8 x 1D FFTs.