Calcolo numerico - Implementazioni della FFT

Aspetti implementativi e applicazioni della

FFT

Accuratezza, memoria, MATLAB, filtraggio e compressione

1 Dalla formula all’implementazione

Un algoritmo FFT efficiente deve considerare non soltanto il numero teorico di operazioni,

ma anche il modo in cui i dati vengono memorizzati e trasferiti. Nei calcolatori moderni

il costo degli accessi alla memoria può essere paragonabile o superiore a quello delle

operazioni aritmetiche. Per questo una implementazione ben progettata cerca di lavorare

su blocchi contigui, riutilizzare i dati presenti nella cache e ridurre allocazioni temporanee.

La versione in place sovrascrive progressivamente il vettore di ingresso con i risultati

intermedi e infine con la trasformata. Essa riduce la memoria ausiliaria, ma richiede

attenzione nell’ordine dei butterfly per non distruggere valori ancora necessari. Una

versione out of place usa array separati per ingresso e uscita ed è spesso più semplice da

parallelizzare, ma consuma più memoria e aumenta il traffico tra memoria e processore.

2 Rappresentazione dei numeri complessi

I dati complessi possono essere memorizzati in forma interlacciata, alternando parte reale

e parte immaginaria, oppure in due array separati. La scelta influenza la vettorizzazione

SIMD e il comportamento della cache. Quando l’ingresso è reale, una FFT complessa

generale esegue calcoli ridondanti, perché lo spettro ha simmetria coniugata. Le rou-

tine real-to-complex sfruttano tale simmetria per ridurre quasi della metà memoria e

operazioni.

Nel caso bidimensionale, come nelle immagini, la DFT separabile viene calcolata ap-

plicando trasformate monodimensionali prima lungo le righe e poi lungo le colonne.

Matematicamente, −1 −1

M N −2πi(km/M +ℓn/N )

X X

= e

X x .

k,ℓ m,n

m=0 n=0

La separabilità consente di evitare un calcolo quadratico in entrambe le dimensioni.

Dopo le FFT sulle righe e sulle colonne, si ottiene la stessa trasformata bidimensionale.

1

3 Scaling e aritmetica finita

In virgola mobile, l’intervallo dinamico è ampio, ma ogni operazione introduce un piccolo

errore di arrotondamento. Poiché una FFT radix-2 possiede log stadi, l’accumulo

N

2

degli errori è generalmente contenuto. In aritmetica a precisione fissa, comune nei sistemi

embedded, somme e differenze possono invece superare l’intervallo rappresentabile. Si

usa allora uno scaling per stadio, spesso dividendo per due, oppure si adottano strategie

block floating point.

Il condizionamento unitario della DFT normalizzata è favorevole, ma il risultato può

comunque apparire poco accurato quando si cerca una componente molt