17

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?

Paul R
  • 208,748
  • 37
  • 389
  • 560
user1459175
  • 303
  • 1
  • 3
  • 10

1 Answers1

29

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.

Paul R
  • 208,748
  • 37
  • 389
  • 560
  • 1
    How about creating the 2D inverse FFT from two 1D inverse FFT? – djondal Jun 27 '13 at 17:13
  • Yes, the same principle applies (but in reverse). – Paul R Jun 27 '13 at 17:53
  • @PaulR Would you care to demonstrate? I believe the implementation of inverse FFT is the problem on [this question](https://stackoverflow.com/q/61718126/176769) (bounty still available). – karlphillip May 17 '20 at 19:57