Calcolo numerico - DFT, definizioni e proprietà

Dalla trasformata continua alla trasformata

discreta di Fourier

Troncamento, campionamento, quadratura ed errori

1 Il problema numerico

La trasformata di Fourier è definita da un integrale esteso a tutta la retta reale. In un

calcolo concreto, però, il segnale viene osservato solo per un tempo finito e in un numero

finito di istanti. Per trasformare la definizione teorica in un algoritmo occorre quindi

effettuare tre passaggi: limitare il dominio di integrazione, sostituire la funzione continua

con campioni e approssimare l’integrale mediante una formula di quadratura. Questi

passaggi non sono semplici dettagli implementativi, perché determinano la precisione e

il significato del risultato.

Si consideri +∞

Z −iωt

(ω) =

F u(t)e dt.

−∞

Il primo passaggio consiste nel scegliere un intervallo finito [a, e approssimare

b]

b

Z −iωt

≈

(ω) (ω) =

F F u(t)e dt.

[a,b] a

La differenza tra integrale infinito e integrale troncato è l’errore di troncamento. Esso

è piccolo quando il segnale è trascurabile fuori da [a, oppure quando l’intervallo

b],

comprende la parte fisicamente rilevante dell’osservazione. Se il segnale non decade,

il troncamento equivale a moltiplicarlo per una finestra rettangolare, con conseguenze

importanti sullo spettro.

2 Campionamento uniforme

Si divide l’intervallo in sottointervalli di ampiezza

N −

b a

=

h ,

N

e si definiscono i nodi = + = 0, 1,

t a jh, j . . . , N.

j 1

I dati disponibili sono i valori = ). Il campionamento elimina l’informazione tra

u u(t

j j

due nodi consecutivi e introduce il problema di capire quali frequenze possano essere

rappresentate correttamente.

Se la frequenza di campionamento è = 1/h, il teorema di Nyquist–Shannon stabilisce,

f s

in forma ideale, che un segnale limitato in banda può essere ricostruito senza perdita

quando la frequenza di campionamento è maggiore del doppio della frequenza massima

presente. La frequenza è detta frequenza di Nyquist. Componenti superiori vengono

f /2

s

interpretate come frequenze più basse, generando il fenomeno di aliasing.

L’aliasing non è un errore che si possa correggere dopo aver acquisito i dati, perché

campioni identici possono provenire da sinusoidi di frequenza differente. Per evitarlo,

occorre scegliere una frequenza di campionamento adeguata e, nei sistemi reali, applicare

prima dell’acquisizione un filtro passa-basso anti-aliasing.

3 Quadratura numerica

Per una frequenza fissata si deve approssimare l’integrale della funzione complessa

−iωt

(t) =

g u(t)e .

ω

Applicando la formula dei trapezi composita si ottiene 

 −1

N (t )

(t )

b g

g

Z ω N

ω 0 X

≈ (t ) +

+

(t) g .

g dt h ω j

ω 

 2 2

a j=1

Se si lavora su un intervallo periodico e il primo e l’ultimo campione rappresentano lo

stesso punto del periodo, la formula assume una struttura ciclica e si evita di contare

due volte lo stesso valore. La periodicità è proprio ciò che consente di ottenere la forma

standard della DFT.

L’errore della regola dei trapezi dipende dalla regolarità dell’integranda. Per funzioni

2

sufficientemente lisce, l’errore globale è dell’ordine di . Nel caso di funzioni periodiche

h |ω|,

molto regolari, la convergenza può essere molto più rapida. Tuttavia, al crescere di

il fattore esponenziale oscilla più velocemente e la funzione da integrare diventa più

difficile da approssimare con una griglia fissata.

2

4 Scelta delle frequenze discrete

Per ottenere una trasformazione finita si scelgono anche frequenze discrete. Ponendo

−

= e assumendo, per semplicità, = 0, si considerano

L b a a

2πk −

= 0, 1, 1.

= , k . . . , N