I know how to compute the 1D FFT (and interpret values from 0 to Nyq). When computing the 2D FFT, do we compute the FFT of row[1] then the FFT of row[2] then the FFT of row[3] up to the last row. And then compute the FFT of col[1] col[2] for each of columns across ? But to report the RESULT of the 2D FFT ( do we report the complex value of each final row from col[0] to col[N/2] for each row from top to bottom ?

What INFO does the 2D complex FFT result convey ?


1 Answer 1


Yes, due to the separability of the kernel :

$$e^{-j \left(\frac{2\pi}{N_1} n_1 k_1 + \frac{2\pi}{N_2} n_2 k_2 \right) } = e^{-j \frac{2\pi}{N_1} n_1 k_1} \cdot e^{-j \frac{2\pi}{N_2} n_2 k_2}$$

the 2D-DFT sum $$X[k_1,k_2] = \sum_{n_1} \sum_{n_2} f[n_1,n_2] e^{-j \frac{2\pi}{N_1} n_1 k_1} e^{-j \frac{2\pi}{N_2} n_2 k_2} $$

can be implemented using row-column (or column-row) decompositions.

$$X[k_1,k_2] = \sum_{n_1} \left( \sum_{n_2} f[n_1,n_2] e^{-j \frac{2\pi}{N_2} n_2 k_2} \right) e^{-j \frac{2\pi}{N_1} n_1 k_1} $$

The following MATLAB/OCTAVE code shows how to apply :

N = 8;            % length of columns-rows 
x = randn(N,N);   % row data

X = fft(x,N) ;    % 1D-fft along columns of x[n1,n2]
X = fft(X.',N).' ;% 1D-fft along rows of intermediate X[k1,k2]
  • $\begingroup$ For 3d-grid, how to perform FFT? X = fft(X.',N).' ;% 1D-fft along rows of intermediate X[k1,k2] This I do no understand. $\endgroup$
    – jomegaA
    Feb 7, 2020 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.