Capitolo 2
Il core FFT/IFFT
2.1 – Introduzione
La trasformata veloce di Fourier (FFT – Fast Fourier Transform) rappresenta uno tra i più largamente usati algoritmi per l'elaborazione dei segnali. Al giorno d'oggi è possibile trovare questo algoritmo implementato sia su FPGA che integrato in complessi SoC (System on a Chip) realizzati in tecnologia CMOS. Questi cores vengono dapprima sviluppati e caratterizzati a livello di linguaggio di comunicazione tra registri (RTL - Register Transfer
Level), parametrizzati in termini di lunghezza della FFT, codifica dei bit di
I/O, coefficienti della trasformata e internal data-path. Il limite intrinseco di questa soluzione è che generalmente si conoscono la lunghezza della FFT e la codifica dei bit di I/O, date dalle specifiche di sistema, ma sono del tutto sconosciuti i valori ottimali relativi alle architetture presenti all'interno del processore stesso. Per ovviare a questo stato di cose e rendere più semplice il design, si procede al dimensionamento del core utilizzando un tool software, sviluppato in C++, che modellizza il core tramite l'uso di librerie di sistema
2.2 – Algoritmo FFT/IFFT
La trasformata veloce di Fourier (FFT, Fast Fourier Transform) è largamente utilizzata per l'elaborazione dei segnali nelle comunicazioni. Si tratta, come sappiamo, di un algoritmo per calcolare la Trasformata Discreta
di Fourier (DFT) e la sua inversa. Per rinfrescare le idee, ricordiamo che la
DFT è definita attraverso la formula:
X k =
∑
n=0 N −1
x nW
nkN per k=0,1,..., N-1dove WN=e−j2/ N
indicano i coefficienti di twiddle. Valutare questa
somma direttamente, vorrebbe dire effettuare un numero di operazioni dell'ordine di N2 . La FFT consente di ridurre il numero delle operazioni ad un
ordine all'incirca pari a N log2 N.
Tra gli algoritmi per il calcolo della FFT, al fine di ridurre il numero di operazioni da compiere (somme e moltiplicazioni), l'algoritmo radix sembra essere quello che meglio si presta per implementazioni di tipo VLSI, sia per il ridotto numero di operazioni, sia per la regolarità della struttura circuitale.
Il concetto che sta alla base dell'algoritmo radix è la possibilità di dividere una DFT di N punti (con N numero non primo, N=r1r2 e r1,r2 interi
maggiori di 1) in r1 DFT, ciascuna di r2 punti, e in r2 DFT, ciascuna di r1 punti.
Con r1 e r2 non primi, l'operazione può essere ripetuta ricorsivamente n volte,
così da ottenere N=r1r2r3...rn+1. Se r1=r2=...=rn+1=r, l'algoritmo è detto radix-r,
altrimenti mixed-radix. Tipicamente vengono utilizzate soluzioni radix-2 e
radix-4, o soluzioni di tipo mixed 2/4, in quanto di semplice e più regolare
Definiamo le seguenti quantità:
N
t=
N
r
1⋅
r
2⋅
...⋅r
tper 1t−1e N
=1
W
Mk=e
−j 2 k Mcoefficienti di TWIDDLE
X
[n]sequenza di ingresso per 0≤nN −1
[
X ]
0=
[
x
[0]x
[N1]x
[2N1]⋯
x
[r1−1 N1]x
[1]x
[N11]x
[2N11]⋯
x
[ r1−1 N11 ]⋮
⋮
⋮
⋱
⋮
x
[N1−1 ]x
[2N1−1]⋯
⋯
x
[r1N1−1]]
La matrice è stata ricavata dai valori del vettore di ingresso. A questo punto si svolge il seguente calcolo:
x
1m1
=
A⋅B
dove si sono utilizzate le seguenti matrici:
A=
[
1
0
0
0
⋯
0
0 W
Nm10
0
⋯
0
0
0
W
N2m10
⋯
0
0
0
0
W
N3m1⋯
0
⋮
⋮
⋮
⋮
⋱
⋮
0
0
0
0
⋯
W
NN1−1m1]
B=
[
X
[0]]
[
1
W
Nm1W
N2m1W
N3m1⋮
W
NN1−1 m1]
Gli elementi della diagonale della matrice A sono i coefficienti di
Twiddle per il primo stadio. Otteniamo alla fine r1 vettori di lunghezza N1 . Il
procedimento viene ripetuto per lo stadio successivo, considerando come vettore d'ingresso al secondo stadio il vettore in uscita dal primo stadio, ottenendo r2 vettori di lunghezza N2 per ciascun vettore in uscita dal primo
stadio. In totale quindi avremo r1r2 vettori. In figura 2.2.1 è mostrato il flusso
dati dell'algoritmo nel caso di N=16.
Figura 2.2.1 – Flusso dei dati.
X0 X 4 X8 X 12 X 1 X5 X9 X13 X 2 X6 X 10 X 14 X3 X 7 X 11 X15 x0 x1 x2 x 3 x 4 x5 x6 x 7 x8 x 9 x10 x 11 x12 x 13 x14 x15 Stage1 Stage2 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
L'unità base di questo processo di fattorizzazione è denominata
butterfly. Dal numero di queste unità, funzionanti in parallelo, dipenderà
quindi il grado di complessità del circuito per il calcolo della FFT/IFFT. L'approccio a cascata (cascade approach) in figura 2.2.2 è quello che meglio si coniuga con la complessità del circuito e la velocità di elaborazione, unitamente ad una intrinseca flessibilità tale da renderlo adattabile a buona parte degli standard di comunicazione.
2.3 – Architettura FFT/IFFT
Il core preso in esame è basato su una fattorizzazione su radix-4 in quanto l'alta precisione degli output e il ridotto numero di addizioni/moltiplicazioni lo rende preferibile al radix-2. D'altro canto, la fattorizzazione basata su radix-4 è applicabile solo per FFT le cui lunghezze sono potenze del quattro. Questo limite è stato facilmente superato aggiungendo come ultimo uno stadio radix-2; in questo modo l'algoritmo funziona anche se la FFT ha lunghezza pari ad una potenza del due. Il numero degli stadi radix Nr è funzione della lunghezza massima della FFT/IFFT, Nmax :
Figura 2.2.2 – Approccio a cascata.
Butt
Com
Com
Butt
Stage1 Stage2
X x
N
max=4
k⋅
2
m, k 1 , m∈[0,1]
N
r=
k m
L'ultimo stadio può essere radix-4 (per m=0) oppure radix_2 (per m=1) in dipendenza del valore di Nmax .
Figura 2.3.1 – Cascata di stadi radix-2/4.
In figura 2.3.1 si può osservare l'organizzazione “a cascata” (cascade) delle unità radix. In figura 2.3.2 è mostrato in dettaglio il generico stadio radix. Il multiplexer in ingresso ad ogni stadio fa in modo che la lunghezza della FFT sia configurabile selezionando il numero di stadi che andranno posti in cascata. L'ultimo stadio può essere sia radix-4 che radix-2, a seconda della lunghezza massima della trasformata. I valori dei parametri N, k e Nr variano a
seconda dell'applicazione:
N ∈[128, 8192]
k ∈[3,6]
N
r∈[
4,7]
Grazie ad un utilizzo intensivo dell'architettura pipeline il throughput complessivo è di un campione complesso per ciclo di clock.
La struttura interna del singolo stadio radix, in figura 2.3.2, include un multiplexer per la selezione degli ingressi, un modulo butterfly, un modulo denominato data-reordering, che si occupa di riorganizzare i dati forniti dall'algoritmo, utilizzando dei banchi di memoria. Le relazioni sottostanti mostrano in dettaglio le richieste di memoria del j-mo stadio in cascata espresso come numero di banchi×bit −width×numero di locazioni :
RAM j=
{
7⋅2 IOWL⋅
N
max4⋅2
mj=1
7⋅2 SWL⋅
N
max4
jj ∈[2, N
r−1]
2 SWL
j= N
r}
dove con IOWL (Input/Output Word Length) si è indicato il bit-width (numero
di bit) per la parte reale/immaginaria dei dati in ingresso/uscita al processore,
con SWL (System Word Length) il bit-width per i dati all'interno del processore, Nmax l'ampiezza della trasformata e Nr il numero degli stadi radix.
È presente inoltre una ROM in cui vengono immagazzinati i Twiddle Factor per questo stadio. Quest'ultima può essere ottimizzata immagazzinando un
ridotto numero di coefficienti tenendo conto della simmetria del cerchio
unitario dei coefficienti stessi nel piano complesso, in modo da poter ricavare in seguito tutti i coefficienti complessi per un particolare stadio. Chiamando TWL il parametro che rappresenta in termini di numero di bit, la parte reale/immaginaria del coefficiente di twiddle, la grandezza della ROM del generico stadio j-mo può essere espressa come:
ROM j =2TWL×
N
max8⋅4
j−1j∈[1, N
r−1]
Si noti come, nel caso fosse richiesto un processore capace di compiere entrambe le operazioni di FFT e IFFT, si può inserire in uscita alla ROM un circuito che faccia il complesso coniugato del twiddle factor, a seconda del tipo di trasformata richiesto.
In figura 2.3.3 è mostrata l'architettura del blocco butterfly interno ad uno stadio radix-4. Il moltiplicatore tra numeri complessi è stato implementato con quattro moltiplicatori Both e due unità di addizione/sottrazione tra numeri reali (figura 2.3.4).
Figura 2.3.4 – Blocco moltiplicatore.
In Re + -+ + Re Im Re Twiddle Im Im Round Out Delay C Round Round Round 1 0
2.4 – Il processore FFT/IFFT
Il processore, basato sull'algoritmo descritto in precedenza, è costituito da vari blocchi:
• i commutatori;
•
le unità butterfly;• i moltiplicatori complessi;
• le ROM per i coefficienti di twiddle; • la control unit;
In figura 2.4.1 si può osservare una visione d'insieme dell'organizzazione dei vari blocchi, in cui è messa in evidenza l'architettura dello stadio j-mo. Ogni singolo commutatore riceve in ingresso un unico dato complesso per poi generarne due o quattro a seconda del tipo di stadio in cui si
trova collocato, vale a dire uno stadio radix-2 o radix-4. Le unità butterfly compiono operazioni di somma e sottrazione per arrivare a determinare il
vettore che verrà moltiplicato per i coefficienti di twiddle. Le ROM sono presenti in ogni stadio tranne l'ultimo, dove manca anche il moltiplicatore. L'unità di controllo ha il compito di generare gli indirizzi per le memorie e di sincronizzare le varie unità presenti nei vari stadi, nonché gli stadi tra loro. All'interno dell'unità di controllo è presente anche un blocco decisionale, che si occupa dello scaling rilevando eventuali variazioni di esponente. Moduli per le approssimazioni sono inseriti dopo ciascun moltiplicatore, troncando il numero di bit di interesse e sommando il più significativo tra quelli scartati. Un modulo di arrotondamento finale si occupa invece dell'esponente accumulato via via durante le elaborazioni attraverso gli stadi intermedi. Come si può vedere in figura 2.4.2, M reti selezionate a seconda del valore dell’esponente di uscita. Ciascuna di esse si occupa di troncare un numero di volta in volta crescente di bit da 1 al valore massimo di Exp. Se l’esponente vale k, viene selezionata la rete che tronca k-1 bit, che saranno successivamente privati del bit meno significativo dalla rete Ar_1 bit. In questo modo l’esponente è stato ridotto a 0. Se Exp è nullo allora un multiplexer provvede a far uscire il dato senza troncamenti.
2.5 – Aritmetica interna
La rappresentazione in virgola mobile (floating point) poco si presta ad un tipo di implementazione su singolo chip, soprattutto per FFT piuttosto grandi. Preso atto di ciò, l'impatto di una aritmetica a precisione finita diventa di importanza vitale per una efficiente configurazione del core. Le aritmetiche a precisione finita in grado di svolgere le operazioni di FFT/IFFT sono caratterizzate dai seguenti parametri:
i. DWL (Data Word Length) e OWL (Output Word Length), i quali
stabiliscono la precisione dei dati I/O del processore;
ii. SWL (System Word Length), che definisce l'ampiezza del data-path
interno del processore e determina le caratteristiche dei sommatori e dei moltiplicatori interni a ciascun blocco butterfly;
iii. TWL (Twiddle Word Length), parametro che influisce sulla grandezza
della ROM.
Un buon trade-off tra complessità e precisione numerica è perseguibile scegliendo una tra le seguenti aritmetiche: Fixed Point, Block Floating Point
(BFP) e Convergent Block Floating Point (CBFP).
L'aritmetica a virgola fissa (fixed point) è di semplice implementazione, non richiede alcun tipo di controllo logico ma porta verso alti valori il parametro SWL, a seconda della lunghezza della trasformata. Per evitare gli
overflows, SWL viene aumentato di due bit per ciascun stadio radix-4. Ad
esempio, per un input a 16 bit e una FFT su 4096 campioni (valori tipici per applicazioni xDSL) SWL all'ultimo stadio radix-4 è di 28 bit.
L'aritmetica Block Floating Point utilizza un unico valore di SWL per l'intera architettura a discapito dell'accuratezza. I dati in uscita da ogni stadio vengono traslati (right shift) di un fattore quattro, se in uscita da uno stadio radix-4, o di un fattore due, se in uscita da uno stadio radix-2. Il numero totale degli shift è quindi già noto, e dipende dal numero e dal tipo degli stadi radix.
L'aritmetica Convergent Block Floating Point si differenzia dalla BFP semplice per la sua più alta precisione; in effetti i dati sono scalati in maniera
adattiva, in relazione al numero dei bit necessari per rappresentare i dati in
uscita da ogni stadio. La rappresentazione numerica viene estesa tramite un campo esponente che tiene conto delle operazioni di scaling. Per evitare lo
scaling dove non è necessario, l'approccio CBFP ottiene gli stessi risultati del
BFP con valori più bassi di SWL e TWL, oppure una maggiore precisione con gli stessi valori. Questa maggiore precisione si paga sia in termini di complessità del circuito, che cresce di stadio in stadio per l'introduzione di unità atte a quantificare l'ampiezza dei dati in uscita da ogni stadio, sia in
termini di incremento della latenza. Sono necessari infatti tre cicli di clock per ciascuno stadio.
La scelta dell'aritmetica da utilizzare passa attraverso l'analisi in termini di rapporto segnale rumore SNR e errore quadratico medio MSE, in considerazione dei possibili valori dei parametri SWL e TWL da scegliere per raggiungere la precisione d'uscita desiderata, espressa da OWL.
