CALCOLO DELLA DFTCALCOLO DELLA DFT

Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010

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

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

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

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

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

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