Vai al contenuto

Elaborazione numerica dei segnali/DFT e FFT

Wikibooks, manuali e libri di testo liberi.
Indice del libro

Trasformata di Fourier discreta (DFT)

[modifica | modifica sorgente]

Definizione di DFT

[modifica | modifica sorgente]

Data una sequenza costituita da un numero finito di campioni, la sua trasformata di Fourier discreta (DFT) , all'interno del suo periodo , è definita:

e può essere interpretata come la discretizzazione in frequenza della DTFT , di cui vengono prese frequenze equispaziate:

Dal punto di vista algoritmico, la DFT è di complessità inferiore rispetto alla DTFT, e inoltre è definita in modo discreto → è rappresentabile su un calcolatore.

Inversione della DFT (IDFT)

[modifica | modifica sorgente]

L'antitrasformata della DFT, all'interno del suo periodo , è definita:

Estensioni periodiche

[modifica | modifica sorgente]

La DFT e la IDFT[1] sono periodiche di periodo :

Si definiscono le estensioni periodiche e , rispettivamente di e :

Tecnica di aggiunta degli zeri

[modifica | modifica sorgente]

È possibile teoricamente ricavare per interpolazione la DTFT partendo dagli campioni della DFT:


In pratica la DTFT viene approssimata a una DFT definita su un nuovo periodo , applicata a una sequenza che non è altro che la sequenza di partenza a cui sono stati accodati campioni nulli:

Aggiungere degli zeri in fondo alla sequenza permette di aumentare artificialmente il periodo della sua DFT senza alterare la DTFT a cui si cerca di approssimare:

e siccome il numero di campioni presi dalla DTFT è maggiore, la risoluzione della DTFT risulta molto più alta.

Esempio - Sequenza porta

Considerando solamente l'intervallo si ottiene come DFT una funzione campionata a una frequenza molto bassa:

 

Basta però aggiungere degli zeri a destra della porta per migliorare la risoluzione della DTFT:

 

 

Aliasing nel tempo

[modifica | modifica sorgente]

Partendo dalla sequenza di durata non finita:

la sua DTFT campionata nel primo periodo :

non coincide esattamente con la DFT calcolata sulla sequenza troncata:

perché vi è un effetto di aliasing nel tempo dovuto al fatto che la sequenza di partenza non ha durata finita.

Al crescere dell'ampiezza del periodo , la DFT della sequenza troncata tende sempre di più alla DTFT campionata nel primo periodo.

Proprietà della DFT

[modifica | modifica sorgente]

Accorgimenti

[modifica | modifica sorgente]

Le proprietà della DFT sono analoghe a quelle della DTFT, ma ci vogliono alcuni accorgimenti:

  • la DFT è periodica di periodo → le operazioni sulla DFT devono condurre a una sequenza periodica di periodo ;
  • la IDFT è periodica di periodo → le operazioni sulla IDFT devono condurre a una sequenza periodica di periodo .

Operatore di modulo

[modifica | modifica sorgente]

L'operatore di modulo restituisce sempre un numero compreso in :

Se è un numero negativo, si somma a tante volte fino a ottenere un numero compreso in :

Operatore di ritardo circolare

[modifica | modifica sorgente]

L'operatore di ritardo circolare restituisce una sequenza ritardata che è ancora compresa in :

in quanto i campioni che vanno al di là del primo periodo ricompaiono all'inizio del primo periodo stesso.

Modo operativo
  • si genera la sequenza periodicizzata ;
  • si applica il ritardo di campioni a : ;
  • la sequenza ritardata è pari alla sequenza periodicizzata troncata nel primo periodo ().

Convoluzione circolare

[modifica | modifica sorgente]

La convoluzione circolare tra due sequenze e è definita:

dove è la più grande tra le durate delle singole sequenze.

Proprietà commutativa

La convoluzione circolare si può rappresentare con un prodotto matrice per vettore. Ad esempio, se la durata è pari a 4:

Convoluzione circolare

[modifica | modifica sorgente]
Accorgimenti
  • la convoluzione circolare di due sequenze di durata campioni ha una uguale durata di campioni (a differenza della convoluzione lineare della DTFT, la cui sequenza risultante ha durata campioni);
  • la convoluzione circolare di due IDFT e , entrambe di periodo , è periodica di periodo :

Proprietà di simmetria

[modifica | modifica sorgente]

Se la sequenza è reale:

    • se è una sequenza pari: ;
    • se è una sequenza dispari: ;
  • per la DFT vale la simmetria hermitiana intorno a 0:
  • per la DFT vale la simmetria hermitiana intorno a ;
  • il campione in della DFT è sempre reale:

Trasformata di Fourier veloce (FFT)

[modifica | modifica sorgente]

La DFT ha complessità quadratica ().

La FFT è un algoritmo di complessità linearitmica () che implementa la DFT e la IDFT in maniera più efficiente.

La DFT può essere rappresentata in termini di matrici:

dove:

Algoritmo della decimazione nel tempo

[modifica | modifica sorgente]

L'algoritmo della decimazione nel tempo è un algoritmo di tipo "divide et impera" che riduce la complessità dell'algoritmo di DFT.

Ipotesi
è una potenza di 2

La sequenza si suddivide in due sottosequenze costituite da metà campioni:

  • la sottosequenza è formata dai campioni pari:
  • la sottosequenza è formata dai campioni dispari:
Ricombinazione
[modifica | modifica sorgente]

Ogni DFT , elemento del vettore , si ottiene dalla somma delle DFT delle singole sottosequenze e :

Complessità
[modifica | modifica sorgente]

Il numero totale di operazioni (somme e prodotti) complesse è pari a:

Si può quindi riapplicare ripetutamente il procedimento "divide et impera" sulle sottosequenze. Al passo -esimo si ha una complessità pari a:

All'ultimo passo (), quando si arriva a dover valutare le DFT su 1 punto, la complessità totale è linearitmica:

Riduzione di complessità

[modifica | modifica sorgente]

La complessità può essere ulteriormente ridotta sfruttando le proprietà di simmetria della matrice .

Esempio con campioni


Schema circuitale a farfalla

Tutte le considerazioni sulla DFT valgono anche per la IDFT: basta applicare l'algoritmo sul complesso coniugato della DFT e poi dividere per :

  1. Si noti che la sequenza di partenza non era periodica, ma aveva durata finita.