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:

Is this correct?

score 27 · Accepted Answer · answered Jul 04 '12 at 17:50

27

No - the algorithm is:

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

answered Jul 04 '12 at 17:50

Paul R

Thank you for your prompt answer!! I will try that – user1459175 Jul 04 '12 at 17:59
1

Yes I have created my version of 2d ffts using 1d fft and compared it against fftw and the results match. Thanks for helping. – user1459175 Jul 09 '12 at 18:33
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

1 Answers1