Teoria ed elaborazione dei segnali/DFT e FFT

Da WikiAppunti.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è B4. DFT e FFT.
Gtk-go-back-ltr.svg  B3. Trasformata di Fourier a tempo discretoGtk-home.svg  Teoria ed elaborazione dei segnali (Elaborazione numerica dei segnali)B5. Analisi in frequenza di segnali a tempo continuo campionati  Gtk-go-forward-ltr.svg

Trasformata di Fourier discreta (DFT)[modifica]

Definizione di DFT[modifica]

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

DFT interpretation.png

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

3-7 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]

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

Estensioni periodiche[modifica]

5-8 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]

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

10 Dimostrazione

Siccome ha per ipotesi durata finita :

12-13 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

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

DFT zero-padding technique example (N) - Sequence.pdf   DFT zero-padding technique example (N) - DFT.pdf

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

DFT zero-padding technique example (2N) - Sequence.pdf   DFT zero-padding technique example (2N) - DFT.pdf

DFT zero-padding technique example (4N) - Sequence.pdf   DFT zero-padding technique example (4N) - DFT.pdf

19
DFT zero-padding technique example (100N) - DFT.pdf

Aliasing nel tempo[modifica]

22 Partendo dalla sequenza di durata non finita:

23 la sua DTFT campionata nel primo periodo :

non coincide esattamente con la DFT calcolata sulla sequenza troncata:

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

25 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]

Accorgimenti[modifica]

30 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]

32 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]

DFT circular shift.png

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]

34 La convoluzione circolare tra due sequenze e è definita:

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

Proprietà commutativa

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

Linearità[modifica]

Ritardo[modifica]

Modulazione[modifica]

Convoluzione circolare[modifica]

33
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]

41 Se la sequenza è reale:

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

Trasformata di Fourier veloce (FFT)[modifica]

7-46 La DFT ha complessità quadratica ().

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

DFT[modifica]

50 La DFT può essere rappresentata in termini di matrici:

dove:

Algoritmo della decimazione nel tempo[modifica]

52 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
Divide[modifica]

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]

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

Dimostrazione

Siccome :

Complessità[modifica]

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

57 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]

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

59-60 Esempio con campioni
Dimostrazione
61 Schema circuitale a farfalla

IDFT[modifica]

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

Note[modifica]

  1. Si noti che la sequenza di partenza non era periodica, ma aveva durata finita.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è B4. DFT e FFT.
Gtk-go-back-ltr.svg  B3. Trasformata di Fourier a tempo discretoGtk-home.svg  Teoria ed elaborazione dei segnali (Elaborazione numerica dei segnali)B5. Analisi in frequenza di segnali a tempo continuo campionati  Gtk-go-forward-ltr.svg