algorithm - trasformata - Perché FFT produce numeri complessi invece di numeri reali?




inverse fourier discrete transform (4)

Tutte le implementazioni FFT che abbiamo incontrato risultano in valori complessi (con parti reali e immaginarie), anche se l'input dell'algoritmo era un insieme discreto di numeri reali (interi).

Non è possibile rappresentare il dominio della frequenza solo in termini di numeri reali?


  1. La trasformata discreta di Fourier è fondamentalmente una trasformazione da un vettore di numeri complessi nel "dominio del tempo" a un vettore di numeri complessi nel "dominio della frequenza" (uso le virgolette perché se si applicano i giusti fattori di ridimensionamento, la DFT è la sua inverso). Se i tuoi input sono reali, puoi eseguire due DFT contemporaneamente: prendi i vettori di input xey e calcola F ( x + i y ). Ho dimenticato come si separa la DFT in seguito, ma ho il sospetto che si tratti di simmetria e complessi coniugati.

  2. La trasformazione discreta del coseno sort-of consente di rappresentare il "dominio della frequenza" con i real ed è comune negli algoritmi di compressione con perdita (JPEG, MP3). La cosa sorprendente (per me) è che funziona anche se sembra scartare le informazioni di fase, ma questo sembra anche renderlo meno utile per la maggior parte degli scopi di elaborazione del segnale (non sono a conoscenza di un modo semplice per fare convoluzione / correlazione con un DCT).

Probabilmente ho sbagliato alcuni dettagli;)


La FFT è fondamentalmente un cambiamento di base. La base in cui la FFT cambia il tuo segnale originale è invece un insieme di onde sinusoidali. Affinché tale base descriva tutti gli input possibili, deve essere in grado di rappresentare sia la fase che l'ampiezza; la fase è rappresentata utilizzando numeri complessi.

Ad esempio, supponiamo che FFT sia un segnale contenente solo una singola onda sinusoidale. A seconda della fase potresti ottenere un risultato FFT del tutto reale. Ma se spostate la fase del vostro input di qualche grado, in quale altro modo l'uscita FFT può rappresentare quell'input?

edit: Questa è una spiegazione un po 'sciolta, ma sto solo cercando di motivare l'intuizione.


Sì, è possibile rappresentare i risultati del dominio di frequenza FFT di input strettamente reali utilizzando solo numeri reali.

Questi numeri complessi nel risultato FFT sono semplicemente 2 numeri reali, entrambi necessari per fornire le coordinate 2D di un vettore risultato che ha sia una lunghezza che un angolo di direzione (o grandezza e una fase). E ogni componente di frequenza nel risultato FFT può avere un'ampiezza unica e una fase unica (relativa ad un certo punto nell'apertura FFT).

Un solo numero reale non può rappresentare sia la grandezza che la fase. Se si eliminano le informazioni sulla fase, ciò potrebbe facilmente distorcere il segnale in modo massiccio se si tenta di ricrearlo utilizzando un iFFT (e il segnale non è simmetrico). Quindi un risultato FFT completo richiede 2 numeri reali per bin FFT. Questi 2 numeri reali sono raggruppati insieme in alcuni FFT in un tipo di dati complesso per convenzione comune, ma il risultato FFT potrebbe facilmente (e alcuni FFT lo fanno) produrre solo 2 vettori reali (uno per le coordinate del coseno e uno per le coordinate seno).

Esistono anche routine FFT che producono direttamente grandezza e fase, ma funzionano più lentamente delle FFT che producono un risultato vettoriale complesso (o due reale). Esistono anche routine FFT che calcolano solo la magnitudine e buttano via le informazioni sulla fase, ma di solito non eseguono più velocemente di quanto si possa fare da soli dopo una FFT più generale. Forse salvano un coder poche righe di codice al costo di non essere invertibili. Ma molte librerie non si preoccupano di includere queste forme più lente e meno generiche di FFT, e permettono al codificatore di convertire o ignorare ciò di cui hanno bisogno o non hanno bisogno.

Inoltre, molti ritengono che la matematica sia molto più elegante utilizzando l'aritmetica complessa.

(Aggiunto :) E, come ancora un'altra opzione, puoi prendere in considerazione i due componenti di ciascun bin risultato FFT, anziché come componenti reali e immaginari, come componenti pari e dispari, entrambi reali.


Se il tuo coefficiente FFT per una data frequenza f è x + iy , puoi guardare x come il coefficiente di un coseno a quella frequenza, mentre y è il coefficiente del seno. Se aggiungi queste due onde per una frequenza particolare, otterrai un'onda sfasata a quella frequenza; la grandezza di questa onda è sqrt(x*x + y*y) , uguale alla grandezza del coefficiente complesso.

La Discrete Cosine Transform (DCT) è un parente della trasformata di Fourier che produce tutti i coefficienti reali. Un DCT bidimensionale viene utilizzato da molti algoritmi di compressione di immagini / video.





fft