Elaborazione numerica dei segnali/DFT e FFT

Indice del libro

Trasformata di Fourier discreta (DFT)Modifica

Definizione di DFTModifica

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

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

 

Estensioni periodicheModifica

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

 

Si definiscono le estensioni periodiche   e  , rispettivamente di   e  :

 

Tecnica di aggiunta degli zeriModifica

È 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 tempoModifica

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 DFTModifica

AccorgimentiModifica

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 moduloModifica

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 circolareModifica

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 circolareModifica

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:

 

LinearitàModifica

 

RitardoModifica

 

ModulazioneModifica

 

Convoluzione circolareModifica

 
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 simmetriaModifica

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

La DFT ha complessità quadratica ( ).

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

DFTModifica

La DFT può essere rappresentata in termini di matrici:

 

dove:

 

Algoritmo della decimazione nel tempoModifica

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
DivideModifica

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

  • la sottosequenza   è formata dai campioni pari:
     
  • la sottosequenza   è formata dai campioni dispari:
     
RicombinazioneModifica

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

 
ComplessitàModifica

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

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

Esempio con   campioni
 


 
Schema circuitale a farfalla

IDFTModifica

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

 

NoteModifica

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