Risposte domande per “Sistemi programmabili per telecomunicazioni”
Alberto Tibaldi 21 novembre 2010
Indice
Illustrare le diverse strutture realizzative dei filtri IIR discutendone vantaggi e svantaggi
Per quanto riguarda i filtri IIR, ossia Infinite Impulse Response, esistono alcune forme in pi`u, rispetto a quelle per filtri FIR. Nel particolare, esistono due forme dirette:
¡Disegno forma diretta 1 e 2¿
Dove ciascun ramo verticale verso l’alto converge in un nodo di somma, e i label indicano prodotti di moltiplicazione. Un filtro IIR `e pensabile come la cascata di due contributi: una parte FIR, dunque non reazionata, e una parte reazionata; la prima sar`a quella che definir`a gli zeri del filtro, la seconda i poli. La prima cosa che potremmo pensare `e: prima mettere la parte nota, ossia la parte FIR, dunque in cascata a essa la parte reazionata: questa `e la forma diretta 1. Essa non ha molto senso, rispetto alla forma diretta 2, dal momento che quest’ultima, gratuitamente, permette di ridurre il numero di registri da utilizzare: mettendo prima la parte reazionata, poi quella FIR, si riesce infatti a generare una sola volta i segnali ritardati, usando solo un gruppo di registri.
Sono applicabili le varie idee gi`a applicabili nell’ambito dei filtri FIR: for- ma trasposta (realizzata mediante una modifica della topologia del grafo), la quale potrebbe portare (quantomeno, lo faceva nel caso dei FIR) a un miglio- ramento del throughput; forma cascata: una forma in grado di realizzare un singolo filtro mediante cascate di diversi filtri pi`u semplici, soluzione che non porta giovamenti se non nell’uso di blocchi pi`u semplici. Un’ultima forma,
applicabile solo nel caso di filtri IIR, `e quella “parallela”: essa `e particolar- mente interessante dal momento che anche in questo caso riesce a scomporre una singola operazione in singole operazioni pi`u semplici, con per`o un princi- pio ben diverso rispetto a quello della forma cascata: in questo caso si preleva la trasformata Z della funzione di risposta ad impulso (dunque, la funzione di trasferimento), e, mediante l’applicazione del procedimento “fratti semplici”, si riduce la complessit`a del filtro, ottenendo una funzione di trasferimento es- primibile come somma (e non prodotto) di diversi contributi, che verranno calcolati in parallelo.
¡Esempio¿
Discutere brevemente l’applicazione della tec- nica dell’aritmetica distribuita alla realizzazione dei filtri numerici, illustrandone possibili van- taggi e svantaggi
L’aritmetica distribuita `e una tecnica atta a semplificare l’hardware neces- sario per la realizzazione di filtri. Si consideri per esempio la formula generica di un sistema realizzante la propria funzione mediante una somma di prodotti (per ora, unsigned ):
y[n] =
N −1
X
n=0
c[n]x[n]
Il principio su cui si basa questa tecnica `e ricordare che un generico numero x[n], binario, senza segno, `e rappresentabile come:
x[n] =
B−1
X
b=0
xb[n]2b
Sostituiamo dunque la seconda nella prima, ottenendo:
y[n] =
N −1
X
n=0 B−1
X
b=0
xb[n]2bc[n]
Il fatto che le due sommatorie abbiano indici finiti, permette di scam- biare senza porsi problemi ulteriori di convergenza delle medesime i due seg- ni di sommatoria; questo fatto `e dimostrabile esplicitando le sommatorie e raggruppando i contributi in 2b per ciascun bit. Si ottiene dunque:
y[n] =
B−1
X
b=0
2b
N −1
X
n=0
xb[n]c[n]
Questa cosa `e interessante dal momento che, ora, per ogni n, si ha b fermo, costante: solo quando n sar`a andato dal proprio valore iniziale a quello finale, si incrementer`a di 1 il valore di b. Questo permette di fare qualcosa di interessante: utilizzare gli xb come indirizzi per una memoria, che in uscita dar`a dunque il c[n]x[n], senza doverlo calcolare; la memoria sostanzialmente sar`a una LUT, dunque introdurr`a un ritardo piuttosto piccolo.
Per implementare hardware questa cosa, esistono alcune soluzioni; quella che probabilmente potrebbe essere la migliore, `e la seguente:
¡disegno seconda architettura SENZA il Barrel¿
In ingresso alla LUT si hanno i dati, che vengono mandati a un somma- tore, il quale `e collegato a un registro che fa da contatore, da accumulatore;
si ha dunque uno shifter verso destra, il quale continua a mandare, nel- la pratica, a sinistra numero: in questo modo al primo colpo si introduce un numero, che verr`a shiftato per tutti i colpi di clock successivi, realizzan- do dunque l’effetto 2b. Questa tecnica, per quanto semplice, `e relativamente lenta, dal momento che richiede un certo numero di colpi di clock per portare a termine l’operazione.
Per quanto riguarda il segno, si pu`o introdurre un meccanismo di com- plementazione di questo tipo:
x[n] = −2BxB[n] +
B−1
X
b=0
xb[n]2b
in questo modo, se xB[n] = 0, si ha ci`o che `e stato visto prima; se `e a 1, si ha la complementazione.
Definire e descrivere la tecnica del “retiming”
applicata alla ottimizzazione di architetture di elaborazione numerica; fornire anche uno o pi` u esempi di applicazione.
Si consideri una situazione di questo tipo (estensibile a un generico numero di nodi sia in ingresso, sia in uscita):
¡disegno con un nodo 2 ingressi 1 uscita e tot ingressi prima, 0 dopo
In una situazione di questo genere, `e possibile fare qualcosa di questo genere:
¡retiming applicato mettendo registri sull’uscita¿
In questo modo, semplicemente, si `e tolto un registro su ciascun ingresso, permetterne uno su ciascuna (in questo caso, sull’unica) uscita. L’operazione che permette di fare ci`o `e il retiming, ed `e molto interessante dal momento che permette sia di ridurre il numero di registri (se questo `e il goal: nel caso proposto, per esempio, `e stato eliminato un registro), sia di ottimizzare il throughput. Si consideri per esempio il seguente grafo:
¡Disegno di un IIR e disegno ottimizzato¿
Il retiming `e il meccanismo che permette di riposizionare un registro, in modo da tagliare i cammini critici, e aumentare dunque di fatto il periodo di clock, quindi con esso il throughput. Questo metodo pu`o tornare utile quando non `e possibile applicare il pipelining (o anche combinarlo con esso):
nell’ultimo caso analizzato, per esempio, non `e possibile introdurre un feed- forward cut set, dal momento che nel punto utile non vi sono cut set di tipo feedforward; il retiming dunque `e una soluzione migliore.
Anche per quanto riguarda il retiming esistono tecniche di attuazione pi`u formali, basate sulla teoria dei grafi: in questo caso si pu`o andare ricercando dei cut set, che per`o non siano feedforward, ossia che uniscano due sottografi in entrambi i sensi. Scelto come lavorare, `e possibile (a meno di mantenere la condizione di fisica realizzabilit`a, ossia ritardo al minimo pari a 0) sommare un certo numero di registri, di ritardi su tutti i rami che vanno dal sottografo A al sottografo B, sottraendo (come detto, facendo in modo che nessun ramo abbia un ritardo negativo) lo stesso numero nei rami che fanno dal sottografo B al sottografo A.
Esiste una tecnica pi`u sofisticata e formale, basata sulla scrittura delle equazioni di retiming per ciascun nodo: dato un generico ramo e unente due nodi u e v, si definisce il retiming per ciascun nodo come il numero di registri che viene portato dall’ingresso all’uscita; si pu`o dunque dire che il peso wr(e) del nodo e sia, dopo i retiming:
wr(e) = w(e) + r(u) − r(v)
Questo deve essere per ogni ramo ≥ 0 e, per i rami appartenenti a un percorso critico, ≥ 1: in questo modo si avr`a la certezza di spezzare i rami dei percorsi critici. Risolvendo il sistema delle equazioni che scaturiscono dal scrivere, per ogni arco, queste equazioni, si pu`o fare il retiming in modo formale ma ovviamente pi`u complicato rispetto al metodo prima presentato.
Illustrare le problematiche relative alla rapp- resentazione in aritmetica finita dei coefficienti e dei segnali in un FIR
Un generico numero, espresso in forma binaria, pu`o essere cos`ı rappresentato:
x[n] = Xm −b0 +
∞
X
i=1
xi[n]2−i
!
Cosa significa tutto ci`o? Il senso fondamentale `e che il contenuto della parentesi tonda sia ≤ 1: in questo modo Xm `e un fattore di scalamento, sostanzialmente una potenza di 2, in modo da muovere la virgola nel numero binario. Fino a qua, siamo nel mondo dell’idealit`a; nella realt`a, si ha qualcosa del genere:
x[n] = Xm −b0 +
B
X
i=1
xi[n]2−i
!
Ossia, il numero `e rappresentabile mediante un numero finito di bit;
questo significa che, per tutti i valori meno significativi di 2−B, non si avr`a informazione. Esistono due operazioni per effettuare questo tipo di approssi- mazione: il troncamento, ossia l’operazione di troncare, di eliminare sen- za prestare ulteriore attenzione la parte meno significativa del numero, e l’arrotondamento, ossia il preoccuparsi di ci`o che accade, di fatto sfasando l’errore. Gli andamenti degli errori nei due casi sono i seguenti:
¡Disegno sia degli andamenti pratici sia degli andamenti di errore¿
Come si pu`o vedere, l’ampiezza dell’intervallo `e sempre ∆, che a sua volta vale:
∆ = Xm2−B
ossia, sostanzialmente il LSB riscalato; nel caso dell’arrotondamento, per`o, il massimo errore che si pu`o commettere `e ∆/2, dal momento che lo “sfasamento” `e tale da abbassare il grafico dell’errore, portando a questo effetto. Purtroppo, se da un lato troncare ha complessit`a hardware nulla (basta non considerare pi`u dei fili da un certo punto in poi), arrotondare `e molto pi`u complicato, dunque spesso si tende a rinunciare ai benefici.
Nel caso dei filtri FIR la cosa `e molto importante dal momento che ciascun filtro FIR `e costituito dall’insieme di due operazioni: somme e moltiplicazioni.
Sia nel caso delle somme sia in quello (molto pi`u tragico) delle moltiplicazioni,
ciascuna operazione potrebbe aumentare il numero di bit necessari per rap- presentare con la massima precisione possibile i risultati parziali. A seconda della richiesta del problema, dunque, sar`a necessario introdurre uno o pi`u processi di quantizzazione in uno o pi`u punti del circuito, tra cui ingressi del circuito, ingressi dei moltiplicatori, uscite di moltiplicatori e sommatori, uscita del circuito. Ci`o che spesso si tende a fare `e, mediante un’analisi, determinare quale pu`o essere, fissato il numero di bit necessari in uscita, un coefficiente di rinormalizzazione per l’ingresso che possa evitare l’overflow in ogni punto del circuito. Si dimostra infatti che, per i FIR, questo coefficiente bsum (stima di caso peggiore) `e:
bsum=
K
X
k=1
|bk|
dove i bk sono i coefficienti che si devono utilizzare per fare le varie moltiplicazioni; essendo il filtro a K prese, si avran K coefficienti.
