FFT 2D con FFT 1D

Question

Sto cercando di implementare un FFT 2D utilizzando FFT 1D. Ho una matrice di dimensione 4x4 (riga maggiore)

mio algoritmo è:

1. FFT su tutti i 16 punti
2. bit inversione
3. trasposizione
4. FFT su 16 punti
5. bit inversione
6. recepire

È corretto?

Answer 1

n - l'algoritmo è:

1. fare 1D FFT su ogni riga (reale complesso)
2. fare 1D FFT su ciascuna colonna risultante da (1) (complesso a complesso)

Quindi sono 4 x FD orizzontali (orizzontali) seguiti da 4 x FD verticali (verticali), per un totale di 8 x 1 D FFT.