Home

Federica EU

1/12

Sergio Cavaliere » 13.Analisi di Fourier per sequenze finite: la DFT

Serie discrete di Fourier

Le considerazioni fatte relative alle sequenze periodiche, rappresentabili mediante combinazione lineare di tutte le sequenze esponenziali complesse (in numero finito, pari ad N), possono però essere estese ad un caso più generale, quello delle sequenze a supporto finito (durata finita).
Riprendiamo in considerazione la coppia di relazioni della Serie Discreta di Fourier

sintesi

$x[n]=\sum_{k\in\langle N\rangle}a_k\varphi_N^k[n]=\sum_{k\in \langle N\rangle}a_ke^{jk\frac{2\pi}N n }~~~n=0...N-1$

Analisi

$a_k=\frac 1 N \sum_{n\in\langle N\rangle}x[n]\overline{\varphi_N^k[n]}=\frac 1 N \sum_{n\in\langle N\rangle}x[n]e^{-jk\frac{2\pi}N n}$

Se una sequenza x[n] ha durata finita N con supporto ad esempio [0 N-1], è semplice renderla periodica, ripetendola identicamente su tutto l’asse dei numeri interi. La sua versione periodica $\tilde x[n]$ si può quindi rappresentare con la semplice convoluzione:

$\tilde x[n]=x[n]\otimes \sum_{k=-\infty}^{k=\infty}\delta[n-kN]$

Da $\tilde x[n]$ viceversa, isolando un periodo, si può riottenere il segnale di partenza di durata finita x[n].

Si tratta in sostanza dello stesso oggetto matematico per definire il quale bastano N campioni, in un caso e nell’altro.

Dalla DFS alla DFT

Il segnale ottenuto $\tilde x[n]$ come versione periodica del segnale di durata finita $x[n]$ può essere sviluppato in serie di Fourier:

$\tilde x[n]=\sum_{k\in\langle N\rangle}a_k\varphi_k[n]=\sum_{k\in \langle N\rangle}a_ke^{jk\frac{2\pi}N n}~~~~n=0...N-1$

$a_k=\frac 1 N \sum_{n\in\langle N\rangle}x[n]\overline{\varphi_N^k[n]}=\frac 1 N \sum_{n\in\langle N\rangle}x[n]e^{-jk\frac{2\pi}N n}$

E’ evidente quindi che è possibile rappresentare sequenze di durata finita mediante le formule riportate sopra, che definiscono una trasformata che prende il nome di Trasformata Discreta di Fourier (Discrete Fourier Transform or DFT).

La DFT non va confusa con la DTFT (Discrete Time Fourier Transform) che, come vedremo trasforma il segnale nel dominio delle frequenze, anche nel caso più generale di segnale non periodico o segnale a durata infinita.

La DFT è una sequenza finita di campioni che rappresentano un segnale di durata finita
La DTFT è una funzione complessa definita nella variabile ω continua mediante un integrale

Nel contesto della discussione sulla DTFT avremo modo di tornare sull’argomento per vedere la DFT come caso particolare della DTFT, quando appunto la durata del segnale è finita.

La trasformata Discreta di Fourier

Passando dalla serie di Fourier alla DFT si preferisce fare le posizioni

$X[k]=Na_k~~~~~~~~W_N=e^{j\frac{2\pi}N}$

Le formule così vanno riscritte come:

analisi

$X[k]=\sum_{n\in\langle N\rangle}x[n]W_N^{nk}$

sintesi

$x[n]=\frac 1 N \sum_{k\in\langle N\rangle}X[k]W_N^{-kn}$

La trasformata Discreta di Fourier (segue)

La Trasformata Discreta di Fourier (DFT) è una semplice trasformazione lineare finita tra due spazi ad N dimensioni, del tipo di trasformazioni cioè rette dai sistemi di equazione lineari usati in geometria analitica, ben noti e semplici.

Infatti l’equazione di analisi definisce una relazione lineare tra le sequenze x[n] ed X[n] di durata finita N, perfettamente identica a quella che mette in relazione, in un sistema di equazioni lineari, il vettore delle incognite con il vettore delle variabili di ingresso mediante una matrice di coefficienti:

$a_{00}x_0+a_{01}x_1+a_{02}x_2=y_0~~~~~~a_{10}x_0+a_{11}x_1+a_{12}x_2=y_1~~~~~~a_{20}x_0+a_{21}x_1+a_{22}x_2=y_2$

$\overline{\overline A}\cdot \overline x= \overline y$

$\overline{\overline A}=\left( \begin{array}{ccc} a_{00} & a_{01} & a_{02}\\a_{10} & a_{11} & a_{12}\\ a_{20} & a_{21} & a_{22} \end{array} \right)$

$\bar x=(x_0~~x_1~~x_2)$

$\bar y=(y_0~~y_1~~y_2)$

La DFT come trasformazione lineare

Resta definita quindi la matrice unitaria W_N della trasformazione lineare che permette di ricavare dai campioni del segnale a durata finita N, x[n] le componenti in frequenza del segnale X[n], mediante la relazione: $X=W_Nx$

e viceversa con: $x=\overline{W_N^T}X$

(con il simbolo A^T si intende la trasposta di A=(a_ij) cioè A^T =(b_ij) con b_ij =a_ij).
(Allo stesso modo sono in relazione i campioni di un segnale periodico ed i coefficienti dello sviluppo in serie discreta di Fourier)
Nel nostro caso abbiamo

$\overline{W_N^{nk}}=\overline{e^{jk\frac{2\pi}N n}}=e^{-jk\frac{2\pi}N n}=W_N^{-kn}$

$\varphi_N^k(n)=W_N^{nk}$

ed abbiamo l’ulteriore simmetria della matrice w_ij=w_ji che la caratterizza come matrice diagonale cioè simmetrica rispetto alla diagonale.

$W_N=\left| \begin{array}{cccc} W_N^0 & W_N^0 & W_N^0 & W_N^0 \\ W_N^0 & W_N^1 & W_N^2 & W_N^3 \\ W_N^0 & W_N^2 & W_N^4 & W_N^6 \\ W_N^0 & W_N^3 & W_N^6 & W_N^6 \end{array} \right|$ $=\left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & W_N^1 & W_N^2 & W_N^3 \\ 1 & W_N^2 & W_N^4 & W_N^6 \\ 1 & W_N^3 & W_N^6 & W_N^6 \end{array} \right|$

Le righe e le colonne di questa matrice sono gli N esponenziali periodici di periodo N già visti nella prima lezione.

La matrice DFT: il caso n=4

Per esteso, nel caso N=4 avremo per la Matrice di Trasformazione da segnale del tempo a segnale in frequenza:

$W_N=\left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & e^{j\frac {2\pi}4} & e^{j\frac {4\pi}4} & e^{j\frac {6\pi}4}\\ 1 & e^{j\frac {4\pi}4} & e^{j\frac {8\pi}4} & e^{j\frac {12\pi}4} \\ 1 & e^{j\frac {6\pi}4} & e^{j\frac {12\pi}4} & e^{j\frac {18\pi}4}\end{array}\right|$ $=\left|\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & e^{j\frac {\pi}4} & e^{j\pi} & e^{j\frac {3\pi}2}\\ 1 & e^{j\pi} & e^{j2\pi} & e^{j3\pi} \\ 1 & e^{j\frac{3\pi}2} & e^{j3\pi} & e^{j\frac{9\pi}2}\end{array}\right|$ ……….. $WN=\left|\begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 &1 & -1 \\ 1 & -j & -1 & 1\end{array}\right|$

Si osservi che la prima riga e la prima colonna sono ambedue fatte di tutti 1. Questo significa che sia nella trasformazione diretta che in quella inversa la componente di ordine zero è la media dei campioni nel dominio coniugato. Quindi la componente di ordine 0 in frequenza, tenendo conto del fattore 1/N, è proprio la media di tutti i campioni nel tempo; essa si chiama per questo componente continua o valor medio. Le altre componenti rappresentano i pesi con cui le varie armoniche sono presenti nel segnale. A differenza del caso continuo, in cui un segnale periodico è ottenuto dal contributo di un numero infinito di armoniche, nel caso discreto le armoniche contenute in un segnale di periodo N, possono essere al più N, come abbiamo già visto. Ancora, a differenza di quanto avviene nel caso del segnale continuo, il passaggio dal dominio del tempo al dominio della frequenza è retto, come visto, da una semplice trasformazione lineare tra spazi coniugati identica a quella che regge le usuali trasformazioni lineari tra spazi a 3 dimensioni, note dall’algebra lineare. Mentre però in questo caso i due spazi sono ambedue Rⁿ nel caso della DFS lo spazio dei segnali è reale lo spazio trasformato, quello della DFS è complesso. In una ovvia generalizzazione anche il segnale può essere complesso.

Il diagramma della matrice

Perché il risultato sia completo occorre dimostrare che la relazione campioni nel tempo e campioni in frequenza è biunivoca, ma questo discende dalla struttura della matrice della trasformazione DFT (matrice di Vandermonde), che però qui non occorre approfondire.
(vedi Vandermonde Matrix 1 e Vandermonde Matrix 2 )

Nelle figure a fianco sono riportati i valori della matrice del sistema di equazioni che lega campioni del segnale nel periodo e componenti in frequenza dello stesso, nel caso N=32, in particolare la componente reale.

Si può osservare il fatto che sia le colonne che le righe della matrice sono le parti reali dei segnali complessi oscillanti visti sopra.

Sono anche evidenti le simmetrie di questa matrice.

Coefficienti della matrice, parte reale.

Coefficienti della matrice, parte immaginaria.

La matrice di trasformazione

Le componenti immaginarie della matrice della trasformazione DFT in una rappresentazione in 3D.

Parte reale della matrice

In una vista ravvicinata le prime righe della matrice della trasformazione DFT, rappresentando i complessi in 3D, con le loro proiezioni reale ed immaginaria, sono nelle figure a lato.

Parte immaginaria: alcune sequenze.

Parte reale: alcune sequenze.

Caratteri della DFT

E’ interessante osservare che i risultati raggiunti sulla DFT, alcuni in comune con la simile DFS sono di una estrema semplicità.

Le frequenze contenute in un segnale sono sempre in numero finito e pari al numero di campioni (durata del segnale).
L’analisi in frequenza può essere fatta mediante un semplice prodotto dei campioni per un opportuna matrice complessa.
La risintesi del segnale può essere fatta in modo duale mediante un semplice prodotto dei campioni in frequenza per un opportuna matrice complessa (inversa della precedente).
L’analisi e la sintesi possono essere fatte in modo esatto, in quanto non coinvolgono integrali da approssimare o somme infinite da calcolare numericamente.

Naturalmente rimane la difficoltà che per segnali di interesse la matrice della trasformazione non ha dimensioni realistiche. Ad esempio 1000×1000 ma anche 1000000×1000000 o anche in più, in dipendenza della durata del segnale. Si tratta di una complessità del tipo O(N²) e nonostante le simmetrie della matrice resta comunque intrattabile

Verrà però in aiuto un algoritmo la FFT che renderà approcciabile questa mole di calcoli, riducendoli drasticamente alla complessità O(NlogN).

Esempi di sequenze semplici

Ad illustrare la semplice relazione tra spazi complessi che è la base della trasformazione finita discussa fino ad ora riportiamo alcune coppie di segnali: il segnale di partenza e la sua rappresentazione. Poiché entrambi possono appartenere al campo dei complessi C, con una ovvia generalizzazione, sia il segnale che la sua trasformata sono rappresentati come punti dello spazio a3D dove due coordinate sono parte reale ed immaginaria e la terza è il tempo n, l’indice della sequenza o di quella trasformata. Data la perfetta simmetria tra i due domini, inoltre la trasformata può diventare il segnale, e la sequenza di partenza lo spettro (caso 2).