2D FFT using 1D FFT

signal-processing fft
user1459175 picture user1459175 · Jul 4, 2012 · Viewed 11.1k times · Source

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

Paul R picture Paul R · Jul 4, 2012

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.

Related questions

How do I obtain the frequencies of each value in an FFT?

I have an FFT result. These are stored in two double arrays: a real part array and an imaginary part array. How do I determine the frequencies that correspond to each element in these arrays? In other words, I would …

Read More
An implementation of the fast Fourier transform (FFT) in C#

Where can I find a free, very quick, and reliable implementation of FFT in C#? That can be used in a product? Or are there any restrictions?

Read More
Calculate autocorrelation using FFT in Matlab

I've read some explanations of how autocorrelation can be more efficiently calculated using the fft of a signal, multiplying the real part by the complex conjugate (Fourier domain), then using the inverse fft, but I'm having trouble realizing this in …

Read More