CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a....
-
Upload
guido-quaranta -
Category
Documents
-
view
214 -
download
1
Transcript of CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a....
![Page 1: CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010.](https://reader036.fdocumenti.com/reader036/viewer/2022082702/5542eb4f497959361e8be964/html5/thumbnails/1.jpg)
CALCOLO DELLA DFTCALCOLO DELLA DFT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
![Page 2: CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010.](https://reader036.fdocumenti.com/reader036/viewer/2022082702/5542eb4f497959361e8be964/html5/thumbnails/2.jpg)
2Comlpessita’ del calcolo diretto della DFT Comlpessita’ del calcolo diretto della DFT
** complesse complesse: : N N (una per ogni addendo della sommatoria)(una per ogni addendo della sommatoria)
Calcolo di X(k) nel caso di x(n) complessa:Calcolo di X(k) nel caso di x(n) complessa:
++ complesse complesse: : N-1N-1 (dalla sommatoria di N addendi) (dalla sommatoria di N addendi)
In totale:In totale: complessecomplesse
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
![Page 3: CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010.](https://reader036.fdocumenti.com/reader036/viewer/2022082702/5542eb4f497959361e8be964/html5/thumbnails/3.jpg)
3Comlpessita’ del calcolo diretto della DFT Comlpessita’ del calcolo diretto della DFT
1 * complessa 1 * complessa = = 4 * reali 4 * reali ee 2 + reali2 + reali1 + complessa 1 + complessa = = 2 + reali2 + reali
Tenendo conto che:Tenendo conto che:
In totale:In totale:
NN2 2 * complesse * complesse = = 4 N4 N22 * reali * reali ee 2N2N22 + reali + reali
N(N-1) + complesse N(N-1) + complesse = = 2N(N-1) + reali2N(N-1) + reali
4 N4 N22 * reali * reali
2N2N22 + 2(N + 2(N22-N) = 4N-N) = 4N22- 2N + reali - 2N + reali
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
![Page 4: CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010.](https://reader036.fdocumenti.com/reader036/viewer/2022082702/5542eb4f497959361e8be964/html5/thumbnails/4.jpg)
4
Algoritmi di riduzione della complessita’Algoritmi di riduzione della complessita’
(simmetria della sequenza esponenziale)(simmetria della sequenza esponenziale)
(periodicita’ della stessa)(periodicita’ della stessa)
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
![Page 5: CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010.](https://reader036.fdocumenti.com/reader036/viewer/2022082702/5542eb4f497959361e8be964/html5/thumbnails/5.jpg)
5Algoritmi di riduzione della complessita’Algoritmi di riduzione della complessita’
a) Algoritmo di Goertzel:a) Algoritmo di Goertzel: si basa sulla sfruttamento periodicita’ si basa sulla sfruttamento periodicita’
BASEBASE MODIFICATOMODIFICATO
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
yk(n) = uscita di un sistema con ingresso x(n) e risposta all’impulso wN^(-kn)
4N² moltiplicazioni reali e 4N² addizioni reali
Metodo Base lievemente meno efficiente Metodo Diretto
![Page 6: CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010.](https://reader036.fdocumenti.com/reader036/viewer/2022082702/5542eb4f497959361e8be964/html5/thumbnails/6.jpg)
6Algoritmi di riduzione della complessita’Algoritmi di riduzione della complessita’
b) Metodo diretto per calcolo parziale in kb) Metodo diretto per calcolo parziale in k
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
![Page 7: CALCOLO DELLA DFT Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010.](https://reader036.fdocumenti.com/reader036/viewer/2022082702/5542eb4f497959361e8be964/html5/thumbnails/7.jpg)
7Algoritmi di riduzione della complessita’Algoritmi di riduzione della complessita’
c) Algoritmi veloci: c) Algoritmi veloci: sfruttano simmetria e periodicita’sfruttano simmetria e periodicita’
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010