Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Immacolata Ortosecco » 10.DFT e convoluzione circolare


DFT e Convoluzione circolare

Esaminiamo:

1. la Discrete – Fourier – Transform come l’unica rappresentazione di Fourier realizzabile con un computer;

2. i dettagli della convoluzione circolare.

WN=e-j2π /N

Con questa posizione semplifichiamo la notazione per la DFT.


Discret Fourier Transform (DFT)

Correzione: inserire il fattore 1/N prima dell’ultima sommatoria

Correzione: inserire il fattore 1/N prima dell'ultima sommatoria


Calcolo della DFT in Matlab

Il calcolo della DFT di una sequenza discreta x[k] è immediatamente realizzato in Matlab mediante il prodotto di matrici .

Viene costruita  la matrice W di dimensioni  NxN  che contiene le potenze di WN. Essa viene moltiplicata per il vettore contenente la sequenza discreta x[n] di lunghezza N.
 Il risultato del  prodotto righe per colonne  di Wper  x[n] (x[n] scritto come vettore colonna) fornisce la DFT  X(k).

X[k]=\sum_{n=0}^{N-1}x[n]e^{-jk(2\pi/N)n}=\sum_{n=0}^{N-1}x[n]W_{N}^{kn}
Il calcolo viene velocizzato sfruttando le simmetrie della matrice W, realizzando così una trasformata di Fourier veloce (FFT) .
Uno dei primi algoritmi  di Fast Fourier Transform   (FFT) ed anche uno dei più noti è quello di Culey e Tukey.
Per il calcolo della DFT in Matlab viene utilizzata la function FFT con la sua inversa iFFT.
Bisogna tener conto del fatto che Matlab nella  iFFT non procede alla divisione per N, come accade nella  formula di sintesi data dalla teoria e vista nelle slides precedenti.

La DFT come campionamento dello spettro di Fourier delle sequenze discrete

Una sequenza esponenziale e la sua DTFT.

Una sequenza esponenziale e la sua DTFT.


Sequenza xp[n] da x[n]. Periodica con periodo 5


Spettro di F. X(e) e suo campionamento X(2πk/N) N=5


Dominio del tempo discreto: xp[n] e DFT della sequenza xp[n] come campionamento della DTFT


Parlando della serie di F…..

Abbiamo detto che le sequenze discrete finite le immaginiamo come un periodo di sequenze periodiche discrete e infinite. Abbiamo visto che la moltiplicazione di due sequenze periodiche corrisponde ad una convoluzione periodica delle due sequenze. Consideriamo ora, due sequenze di durata finita x1 ed x2 entrambe di lunghezza N e consideriamo le loro DFT X1[k] ed X2[k]. Se x3 è la convoluzione delle due sequenze di partenza e X3[k] la sua DFT, abbiamo X3[k]=X1[k] X2[k].

Esempio per il calcolo della convoluzione circolare

Vediamo ora il calcolo della convoluzione circolare attraverso un esempio. Date le due sequenze periodiche di periodo 4: x1=[1 2 3 4 ]  e x2=[1 1 0 2], calcoliamo graficamente la loro convoluzione circolare, che è anch’essa una sequenza periodica di periodo 4. Posizioniamo la prima sequenza in senso orario su una circonferenza. L’altra sequenza la posizioniamo in senso antiorario. Procediamo secondo le indicazioni della slide successiva.


Esempio per il calcolo della convoluzione circolare (segue)


Osservazioni

Il numero di campioni della convoluzione circolare è uguale al periodo delle due sequenze, nel caso in cui è lo stesso. Nel caso in cui i due periodi sono differenti, aggiungiamo degli zeri alla sequenza di periodo più piccolo e  in numero uguale alla differenza dei due periodi. Poi procediamo come nel caso di periodo uguale.

Coincidenza della convoluzione circolare con la convoluzione lineare

Sappiamo che nel caso di convoluzione lineare il numero di campioni della convoluzione è pari a m1+m2-1, dove m1 è il numero di campioni della prima sequenza ed m2 è il numero di campioni della seconda. Per avere una coincidenza del numero di valori delle due convoluzioni, dobbiamo rendere i due periodi uguali a m1+m2-1.Poi possiamo procedere come prima.

Inserimento di zeri nelle due sequenze


Inserimento di zeri nelle due sequenze (segue)


Inserimento di zeri nelle due sequenze (segue)


Applicazione della convoluzione circolare

Un’applicazione della convoluzione circolare riguarda la computazione veloce della convoluzione lineare intesa come filtraggio di un segnale x[n] attraverso un filtro con risposta all’impulso h[n]. L’uscita del filtro y[n] è proprio la convoluzione lineare delle due sequenze x[n] e h[n]. Per velocizzare l’operazione, quando si tratta di sequenze molto lunghe, è preferibile passare al dominio della frequenza. Si calcolano le DFT delle sequenze, si fa il loro prodotto e poi si procedere con il calcolo della DFT inversa del prodotto per ottenere la y[n] corrispondente.

Questa operazione viene realizzata su sequenze periodicizzate e se vogliamo che il risultato coincida con la convoluzione lineare, dobbiamo procedere all’inserimento di zeri nelle due sequenze, in numero tale da garantire la lunghezza di una convoluzione lineare e procedere poi come visto precedentemente.

L’inserimento di zeri viene definito ‘zero padding’, non aggiunge informazione alle sequenze, ma favorisce solo un campionamento più fitto nella trasformata di F. della sequenza.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion