Accumulatore e unità di calcolo 3

3

Accumulatore e unità di calcolo

Questo capitolo è dedicato all’analisi dell’accumulatore e dell’unità di calcolo utilizzati assieme al sistema a due livelli d’interpolazione per realizzare il DDS complessivo. Per ovvie ragioni l’insieme dei due blocchi nel seguito verrà indicato con l’appellativo “sistema sincrono”.

3.1 Descrizione complessiva del sistema sincrono

La struttura di un sistema DDS è composta da un accumulatore e un generatore di ritardo (vedi paragrafo 1.4), quest’ultimo a sua volta è realizzato, nella sua implementazione digitale, da una unità di calcolo e un sistema di interpolazione. Il compito dell’unità di calcolo è quello di determinare, in funzione del dato al suo ingresso, il ritardo che deve essere introdotto sul segnale MSB prodotto dall’accumulatore. Il risultato di tale unità è una parola di controllo digitale che imposta il sistema d’interpolazione affinché il ritardo introdotto da questo su MSB sia effettivamente pari al valore desiderato. Innanzitutto ricordiamo che l’unita di calcolo deve svolgere la relazione (1-18), dove nel nostro caso N = 4095, infatti abbiamo che il nostro sistema ha 4096 livelli d’interpolazione. Abbiamo già detto che il risultato della relazione (1-18) è appartenente all’intervallo [0, 4095]; anche se questo risulta essere ovvio in quanto il sistema dovrà selezionare necessariamente uno dei livelli d’interpolazione possibili, cerchiamo di capire il perché da un punto di vista analitico. Tale risultato è dovuto al legame presente fra il dato ₂n−1 _{−ϑ1, e ∆Ph; infatti si ha che una volta fissato ∆Ph i valori}

assumibili da ₂n−1 _{−ϑ1 sono tutti quelli appartenenti all’intervallo [0, ∆Ph].} Questo si capisce se osserviamo che per avere un transizione di MSB a livello logico alto, la distanza fra ϑ e _{1 2}n−1_{, deve essere inferiore a ∆Ph, di modo che al} ciclo successivo sommando a ϑ₁ la quantità ∆Ph, si abbia che il contenuto dell’accumulatore divenga superiore a ₂n−1_{, e quindi appunto il segnale MSB} passi a livello logico alto. Per quanto detto si intuisce che anche tutti i valori di

1 1

2n− −ϑ _{inferiori a ∆Ph portano alla generazione alla transizione da 0 ad 1 del} segnale MSB, da cui sono tutti valori possibili. Dunque avremo che il risultato della relazione (1-18) è espresso su 12 bit, i quali costituiscono i segnali di comando del sistema d’interpolazione. Come visto nel capitolo precedente i 5 bit più significativi saranno inviati al primo livello d’interpolazione, mentre i 7 meno significativi al secondo.

Vediamo adesso quali siano i vincoli temporali ai quali è soggetta l’unità di calcolo. Poiché il dato ϑ₁ è pronto solamente un ciclo di clock prima della transizione di MSB dal livello logico basso a quello alto avremo che la logica di calcolo deve essere in grado di risolvere la relazione (1-18) in un unico ciclo di clock. Questo porta a vincoli temporali di calcolo molto stretti ed avrà notevole effetto sulla scelta delle architetture dell’unità di calcolo. Una prima conseguenza architetturale risiede nella scelta del metodo di risoluzione della relazione (1-18). Notiamo come questa si componga di una moltiplicazione e una divisione; in generale le operazioni di divisione sono maggiormente complesse rispetto a quelle di moltiplicazione, e richiedono tempi di calcolo notevolmente superiori, risulta quindi difficile riuscire a realizzare la divisone in un unico ciclo di clock, a meno di non ricorrere a sistemi con un elevato livello di pipeline. Si può notare però che i tempi di variazione di ∆Ph sono notevolmente maggiori al ciclo di clock, infatti tale quantità è variata solamente quando si desidera modificare il valore della frequenza sintetizzata. Da cui possiamo pensare di effettuare dapprima la divisione fra 4095 e ∆Ph e poi la moltiplicazione per ₂n−1_{−ϑ1. In questo modo} l’operazione di divisione viene svolta una volta per tutte nel momento in cui varia ∆Ph, mentre ad ogni transizione di MSB da 0 ad 1 svolgiamo solamente l’operazione di moltiplicazione. Anche se tale scelta è risultata essere ottimale dal

punto di vista della velocità , bisogna notare che l’aritmetica di calcolo utilizzata è una aritmetica intera, da cui il risultato che si ottiene effettuando dapprima la divisione e poi la moltiplicazione è profondamente diverso da quello ottenibile effettuando prima la moltiplicazione e poi la divisione intera. Nel caso da noi scelto si avrebbe infatti un errore di calcolo troppo grande e non ammissibile. Di seguito svolgeremo una breve analisi dell’errore di calcolo che si ottiene, facendo vedere la soluzione adottata per eliminarlo.

Riportiamo per maggiore chiarezza del lettore la relazione (1-18).

(

)

_⎥⎦⎥ ⎢⎣ ⎢ ∆ ⋅ − = − Ph CK P n i 4095 2 1 _{ϑ ( 3-1 )}

Si capisce facilmente che l’errore commesso nel calcolo risulta essere inferiore ad 1, ossia commettiamo un errore che in termini temporali è inferiore alla risoluzione del sistema d’interpolazione. Tuttavia abbiamo visto che per effettuare tale calcolo svolgiamo dapprima la divisione 4095/∆Ph _{e poi il prodotto tra il}

risultato di questa divisione e P n−1 −ϑ

2 _{; questo comporta un errore di calcolo} superiore a quello visto precedentemente, che non è tollerabile. Consideriamo il seguente esempio di calcolo tra i due algoritmi in modo da mettere in luce la differenza dei due risultati. Supponiamo di avere:

500 = ∆Ph 4882 −1 _{− =} P n ϑ

Svolgendo il calcolo con l’algoritmo esatto otteniamo: 3996 488 500 4095 = ⎥⎦ ⎥ ⎢⎣ ⎢ _⋅

Andando invece a realizzare dapprima la divisione e poi la moltiplicazione otteniamo: 3904 488 500 4095 _{⋅ =} ⎥⎦ ⎥ ⎢⎣ ⎢

Da cui si osserva la notevole differenza fra i due risultati ottenuti. Vediamo di valutare da un punto di vista teorico quale sia l’errore commesso utilizzando i due algoritmi, prima di fare questo è necessario introdurre alcuni concetti di calcolo numerico, quali la funzione di troncamento e l’errore algoritmico.

Un generico numero reale X può essere espresso in rappresentazione in virgola mobile normalizzata nel seguente modo:

∑

∞ = − _{= ± ⋅} ± = 1 3 2 1 ... , 0 j b i j b X β α β β α α α ( 3-2 )

Dove β risulta essere la base di numerazione, b il numero di cifre significative a sinistra della virgola e αj∈

{

0,...,β −1

}

le cifre che compongono il numero.

La funzione di troncamento alla m-esima cifra significativa risulta essere:

⎩ ⎨ ⎧ ± →

∑

= − m j j j b r X t 1 : β α β ( 3-3 )

Sostanzialmente la funzione non fa altro che troncare il numero alla m-esima cifra significativa, limitando ad m il numero di cifre dopo la virgola. L’errore che si compie usando la funzione troncamento è pari a:

( )

m

rm

t ξ −ξ = β− ( 3-4 )

La relazione (3-1) corrisponde quindi alla funzione di troncamento alla cifra zero applicata al numero 2n−1⋅4095/∆Ph_{, bisogna inoltre osservare che la base di}

numerazione che utilizziamo è β=2. Adesso vediamo di applicare questi concetti al nostro algoritmo, calcolandoci l’errore sia nel caso che si effettui il calcolo esatto sia nel caso che si effettui prima la divisione tra 4095 e ∆Ph, e poi il prodotto.

Nel caso del calcolo esatto stiamo svolgendo la seguente operazione:

(

)

⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ∆ − ⋅ − Ph t P n r ϑ 1 0 2 4095 ( 3-5 ) Da cui l’errore algoritmico commesso risulta essere:

(

2

)

4095

(

2

)

_{2 1} 4095 1 ₀ 0 1 = < ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ ∆ − ⋅ − ∆ − ⋅ − − − Ph t Ph P n r P n ϑ ϑ ( 3-6 ) Che appunto coincide con l’errore che, come avevamo già osservato, poteva essere commesso. Vediamo adesso cosa accade nel caso in cui si svolga prima la divisione e poi il prodotto. In questo caso l’operazione che stiamo svolgendo è:

(

P

)

n r Ph t ⎟⋅ −ϑ ⎠ ⎞ ⎜ ⎝ ⎛ ∆ −1 0 2 4095 ( 3-7 ) Da cui l’errore algoritmico che commettiamo risulta essere:

1 2 4095 4095 ₀ 0 ⎟ < = ⎠ ⎞ ⎜ ⎝ ⎛ ∆ − ∆ − Ph t Ph r ( 3-8 )

Moltiplicando ambo i membri per P n−1 −ϑ

2 _{e portando questo dentro il valore} assoluto, ottengo appunto l’errore desiderato.

(

)

₍

₎

P n P n r P n Ph t Ph ϑ ϑ ϑ − < − ⋅ ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆ − ∆ − ⋅ − _{− −} 1 1 0 1 2 2 4095 2 4095 ( 3-9 ) Come si può osservare dalla disuguaglianza (3-10), l’errore algoritmico in questo caso risulta essere superiore ad 1, e quindi si commette un errore temporale superiore alla risoluzione del sistema d’interpolazione. Intuitivamente si capisce che per ridurre tale errore sarà necessario effettuare un troncamento sul calcolo della divisione tra 4095 e ∆Ph, ad una cifra m ≠ 0. Vediamo di determinare analiticamente il valore di m. Consideriamo l’errore algoritmico commesso utilizzando un generico troncamento alla cifra m-esima:

m rm Ph t Ph − < ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆ − ∆ 2 4095 4095 ( 3-10 )

Moltiplicando ambo i membri per P n−1 −ϑ 2 _otteniamo:

(

)

₍

₎

P n m P n rm P n Ph t Ph ϑ ϑ ϑ _{⋅ − < ⋅ −} ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ ∆ − ∆ − ⋅ 2 −1 4095 ₂ −1 ₂− ₂ −1 4095 ( 3-11 ) Dobbiamo quindi imporre che il termine a destra della disuguaglianza sia minore di 1, e quindi possiamo ricavare il valore di m.

(

P

)

n P n m P n m m ϑ ϑ ϑ < ⇒ > − ⇒ > − − ⋅ − − − − 1 2 1 1 _{1 2 2 log 2} 2 2 ( 3-12 )

Poiché abbiamo che P n−1₋ϑ

2 _{nel peggiore dei casi può valere 4095 (questo si} capisce abbastanza bene pensando al funzionamento del circuito accumulatore nel caso di ∆Ph = 4095) veniamo ad avere che m = 12. Dovrei quindi considerare anche le dodici cifre dopo la virgola del risultato del rapporto tra 4095 e ∆Ph. Poiché operiamo in base 2, questo equivale a premoltiplicare 4095 per 4096, in modo che operando la divisione intera considereremo ugualmente le dodici cifre. Cerchiamo adesso di comprendere su quanti bit sia esprimibile il risultato della divisione. Siccome il numeratore è espresso su 24 bit, mentre il denominatore su un numero di bit variabile da 1 a 12 avremo che nel peggiore dei casi,

corrispondente a ∆Ph =11, il risultato della divisione sarà esprimibile su 24 bit. Questo comporta l’uso di un moltiplicatore con due operandi uno a 24 bit e uno a 12 bit. Ovviamente una volta effettuata la moltiplicazione è necessario dividere per 4096, in modo da riportare il risultato sull’ordine di grandezza desiderato. Essendo in base 2 tale operazione è estremamente semplice, in quanto corrisponde ad eliminare le 12 cifre meno significative del risultato. In questo modo l’uscita del moltiplicatore è espressa sui 12 bit utili a comandare il sistema d’interpolazione. Detto questo applichiamo il metodo visto all’esempio precedentemente e vediamo il risultato che si ottiene.

3996 4096 488 4096 500 4095 = ⎥ ⎥ ⎥ ⎥ ⎦ ⎥ ⎢ ⎢ ⎢ ⎢ ⎣ ⎢ ⋅ ⎥⎦ ⎥ ⎢⎣ ⎢ _⋅

Si osservi l’uguaglianza fra questo risultato e quello ottenibile mediante l’algoritmo esatto. Siamo quindi riusciti ad effettuare il calcolo realizzando dapprima la divisione e poi la moltiplicazione, con l’errore desiderato.

Figura 3.1 Schema a blocchi del sistema sincrono.

1 _{In realtà il minimo valore di ∆Ph è zero, tuttavia in tale caso il risultato della divisione non è} significativo in quanto non si hanno transizioni del segnale MSB e quindi la frequenza sintetizzata è nulla.

La Figura 3.1 mostra lo schema a blocchi del sistema completo. In tale schema riconosciamo un accumulatore, un data-converter, una unità di calcolo composta da un divisore e un moltiplicatore, e un circuito External/Internal il quale consente il caricamento esterno dei dati di comando verso l’interpolatore, in modo da rendere il sistema maggiormente testabile.

Nel seguito andremo ad analizzare in modo dettagliato i singoli blocchi valutando le architetture utilizzate, evitando di analizzare l’accumulatore e il circuito data-converter, in quanto già trattati nel capitolo 1.

3.2 Il moltiplicatore

Per quanto visto nel paragrafo precedente l’operazione di moltiplicazione deve essere svolta in un unico ciclo di clock, da cui è necessario utilizzare un’architettura ottimizzata per la realizzazione di moltiplicazioni veloci. Per comprendere gli algoritmi di moltiplicazione veloci è utile andare ad analizzare il classico algoritmo di shift e somma in modo tale da poter comprendere quali sono i suoi limiti e dunque quali modifiche possano essergli apportate in modo da velocizzare l’operazione di moltiplicazione. Per questo motivo si è deciso di riportare in Figura 3.2 un esempio di applicazione di tale algoritmo in quanto l’analisi di questo ci consentirà di effettuare un raffronto rispetto ad algoritmi maggiormente ottimizzati.

Figura 3.2 Esempio di calcolo della moltiplicazione applicando l’algoritmo di shift e somma.

Come si può osservare in Figura 3.2 tale algoritmo richiede la somma di un numero di prodotti parziali pari al numero di bit del moltiplicando. Si capisce che maggiore è il numero di prodotti parziali, maggiore sarà il tempo che il circuito impiega per effettuare il calcolo, in quanto il tempo di calcolo totale sarà dato dal

tempo di propagazione del singolo sommatore, moltiplicato per il numero di prodotti parziali. Si intuisce che una riduzione del numero di prodotti parziali consentirebbe la riduzione del tempo di calcolo. Sulla base di questa intuizione si basano gli algoritmi per moltiplicatori veloci, in cui mediante tecniche di decodifica si riducono i prodotti parziali a discapito di una maggiore complessità dell’hardware. In questo paragrafo introdurremo due algoritmi per moltiplicatori veloci descritti in [8] e [9], normalmente utilizzati in quelle applicazioni dove la necessità di elevate velocità di elaborazione è maggiormente importante dell’occupazione finale di area del chip. E’ importante osservare che si intende introdurre solamente i concetti generali sui quali si basano i due algoritmi, in modo che la descrizione del moltiplicatore realizzato possa essere compresa dal lettore, non si intende certamente andare a descrivere in modo completo i due algoritmi per evitare di descrivere argomenti abbondantemente trattati in letteratura.

3.2.1 Algoritmo di Booth modificato

L’algoritmo di Booth modificato detto anche MBA (Modified Booth Algorithm) si basa sulla possibilità di realizzare la moltiplicazione mediante una decodifica del moltiplicatore. Senza perderci troppo nei dettagli di seguito mostreremo la teoria matematica alla base di questo algoritmo, e analizzeremo le conseguenze dell’applicazione di questo metodo sulla riduzione del numero di prodotti parziali. L’operazione di moltiplicazione può essere scritta come:

Y X

P= × ( 3-13 )

Dove X è il moltiplicatore e Y il moltiplicando, che assumeremo essere espressi su n bit. Il numero di prodotti parziali nel MBA è dato da :

pari dispari n n n n parziali prodotti di numero ⎩ ⎨ ⎧ = + 2 / 2 / 1 ( 3-14 )

Senza perdere di generalità considereremo solo il caso di n pari. Sappiamo che in rappresentazione naturale X può essere scritto nella seguente forma:

1 , 0 2 1 0 = =

∑

− = i n i i i con x x X ( 3-15 )

L’MBA permette di scrivere X in una rappresentazione differente che risulta essere:

∑

= = /2 0 4 n j j j Q X ( 3-16 )

Dove Q_j =−2x_2j+1+x_2j +x_2j−1 e x₋₁ =0, da cui il risultato del moltiplicatore è:

∑

= = /2 0 4 n j j jY Q P ( 3-17 )

Vediamo di capire come si applica in modo pratico questo algoritmo. Innanzitutto bisogna determinare i valori Q e questo può essere fatto in modo molto j

semplice ricorrendo alla Tabella 13, quindi effettuare il prodotto tra Y e Q , il j

risultato di questo prodotto rappresenta il prodotto parziale desiderato. Si osservi come tutti i prodotti parziali possano essere ottenuti con semplici operazioni di shift e complementazione.

Tabella 13 Codifica di Booth.

X Q j 000 0 001 1 010 1 011 2 100 -2 101 -1 110 -1 111 0

Ad esempio le operazioni di sottrazione e sottrazione di due volte il moltiplicando, sono ottimizzate eseguendo operazioni di complemento a due e shift; in particolare per sottrarre una volta basta sommare il complemento a due, mentre per sottrarre due volte basta sommare il complemento a due shiftato a sinistra di una posizione. Una volta ottenuti tutti i prodotti parziali è necessario sommarli. Osservando la relazione (3-17) si evince che i singoli prodotti parziali

devono essere shiftati di 2j bit, in quanto abbiamo che ciascuno di essi è moltiplicato per j

4 .

Figura 3.3 Esempio di calcolo della moltiplicazione applicando l’algoritmo MBA.

In Figura 3.3 è possibile vedere una applicazione dell’algoritmo di Booth nel caso di moltiplicando e moltiplicatore a 5 bit. Si noti come il numero di sommatori necessario sia pari a 3 contro i 5 necessari nel caso dell’algoritmo di shift e somma. In generale possiamo affermare che se n è la dimensione in bit del moltiplicatore, abbiamo che il numero di prodotti parziali e quindi il numero di somme da effettuare è pari a _⎢⎢⎡ _⎥⎥⎤

2

n . Anche se tale algoritmo consente una drastica

riduzione del numero di prodotti parziali, per contro necessità di una complessità hardware notevole, in quanto ha bisogno di sistemi di estensione di segno, che anche se possono essere semplificati, ocme proposto da Roorda [10], risultano essere tuttavia notevolmente complessi.

3.2.2 Algoritmo con tecnica di decodifica

L’idea base di questo algoritmo è quello di scomporre il moltiplicatore in gruppi di 3 bit, dopodiché ottenere i prodotti parziali come prodotti tra il moltiplicando e i 3 bit del moltiplicatore. I prodotti del moltiplicando con il numero a 3 bit sono ottenibili mediante semplici operazioni di shift e somma. Come mostrato nella Tabella 14, la moltiplicazione per un numero a 3 bit può essere realizzata come una somma di due moltiplicandi shiftati opportunamente. Ad esempio la moltiplicazione per sei è realizzata come somma di moltiplicazione per 4 e moltiplicazione per 2 (moltiplicazioni per potenze del due sono semplici operazioni di shift). La moltiplicazione per 7 (111) richiederebbe 3 somme, tuttavia, questa operazione è rimpiazzata sottraendo il moltiplicando, al

moltiplicando moltiplicato per 8. In particolare tale operazione può essere ricondotta ad una semplice somma presettando ad uno l’LSB del moltiplicando shiftato tre volte, e quindi sommando ad esso solo l’inverso del moltiplicando. Vediamo perché: X X X X X X X ×111= ×1000+ +1= 000+ +1= 001+ ( 3-18 )

Dove X000 rappresenta tre zero concatenati con X, o X moltiplicato per 23 = . 8

Tabella 14 Conversioni delle operazioni di moltiplicazione in operazioni di shift e somma.

X X · Y

3 bit del moltiplicatore Calcolo come shift e somme

000 0 + 0 001 0 + 2° (Y) 010 0 + 2° (Y) 100 2² (Y) + 0 011 2¹ (Y) + 2¹ (Y) 101 2² (Y) + 2° (Y) 110 2² (Y) + 2¹ (Y) 111 2³ (Y) - 2° (Y)

Dal punto di vista realizzativo, dobbiamo quindi scomporre il moltiplicatore in gruppi di 3 bit,ottenere tutti i prodotti parziali sfruttando la conoscenza dei 3 bit di ciascun gruppo, infine effettuare la somma dei prodotti parziali shiftati opportunamente in base al gruppo di appartenenza. In generale se i prodotti parziali sono stati ottenuti dal gruppo i-esimo dei 3 bit del moltiplicatore, sarà necessario shiftarli di un numero di bit pari a 3·i. In Figura 3.4 è riportato un esempio di moltiplicazione fra un moltiplicando a 4 bit e un moltiplicatore a 6 bit. Utilizzando questo algoritmo il numero di operazioni di somma è notevolmente ridotto, in generale se n è la dimensione in bit del moltiplicatore il numero di somme è ridotto a _⎢⎢⎡ _⎥⎥⎤

3 2n

. La riduzione in termini di prodotti parziali da parte di questo algoritmo è inferiore rispetto a quella ottenibile con l’MBA, e tale effetto è tanto più sentito quanto più grande è il valore di n.

Figura 3.4 Esempio di calcolo della moltiplicazione applicando l’algoritmo di decodifica.

Tuttavia una implementazione di questo algoritmo è notevolmente più semplice dal punto di vista hardware, in quanto non si hanno problemi di estensioni di segno dei prodotti parziali.

3.2.3 Architettura del moltiplicatore

Abbiamo visto come il moltiplicatore presente nell’unità di calcolo debba effettuare una moltiplicazione fra due operandi Y e X rappresentati rispettivamente su 24 e 12 bit. Avremo quindi un numero di prodotti parziali nei quali può essere scomposta la moltiplicazione pari a 6 nel caso dell’algoritmo MBA e 8 nel caso dell’algoritmo a decodifica.

Poiché tale differenza non è molto elevata abbiamo preferito utilizzare l’algoritmo a decodifica, in quanto come già detto da una parte consente prestazioni in termini di velocità di elaborazione inferiori, ma dall’altra permette di ridurre la complessità hardware del sistema.

Vediamo in modo più dettagliato l’architettura utilizzata. Innanzitutto dovremo avere un circuito che generi i prodotti parziali in funzione della conoscenza del moltiplicando e del moltiplicatore. Tale circuito prende il nome di PP-cell (vedi Figura 3.5). Le PP-cell genereranno in uscita i due prodotti parziali relativi ai 3 bit del moltiplicatore. Più nel dettaglio avremo che in funzione dei 3 bit del moltiplicatore l’encoder selezionerà i due prodotti parziali che devono essere sommati, in completo accordo alla Tabella 14. Poiché il moltiplicatore è espresso su 12 bit, verremo ad avere 4 p-cell e quindi un totale di 8 prodotti parziali da sommare.

Figura 3.6 Modalità di funzionamento in parallelo dei Carry-save-Adder.

Al fine di ridurre al minimo i tempi di calcolo del sistema è stato necessario ottimizzare le operazioni di somma dei prodotti parziali. A questo fine esistono architetture ottimizzate le quali sfruttano circuiti di Carry-Save-Adder (CSA) e Wallace tree. I CSA sono sommatori senza riporto del carry che consentono di effettuare la somma di tre vettori di dati e generano in uscita un vettore di somma e uno di carry. Sostanzialmente sono composti da dei full-adder in cui non si ha

propagazione del carry, e in cui l’ingresso del carry è utilizzato come ingresso dati (vedi Figura 3.6).

Figura 3.7 Connesione dei full-adder a Wallace Tree.

Il Wallace Tree è invece una struttura di sommatori che consente di ottenere, a partire da tre vettori di somma e tre vettori di carry, un unico vettore di somma e un unico vettore di carry. La struttura di un Wallace Tree è mostrata in Figura 3.7, nella quale possiamo osservare come i bit di somma si propaghino verticalmente mentre quelli di carry diagonalmente. L’uso di tale struttura risulta essere di notevole importanza in quanto ci consente di evitare completamente l’uso di sommatori con riporto del carry. Osservando la Figura 3.8 possiamo notare come il sistema effettua la somma degli otto prodotti parziali. Come mostrato in Figura 3.6 i tre sommatori di tipo CSA siglati ADD1, ADD2 e ADD3 forniranno in uscita un vettore di somma e uno di carry realizzando quindi un primo livello di somma. In particolare si osservi il funzionamento in parallelo dei tre sommatori in modo da consentire la riduzione dei tempi di calcolo. I tre vettori di somma e di carry generati dal primo livello di somma possono essere sommati in modo ottimizzato mediante il circuito Wallace Tree. Infine si può ottenere il risultato complessivo ricorrendo ad una unico sommatore con riporto del carry, il quale

utilizza un sistema di Carry-Lookahead-Adder in modo da ridurre al minimo i tempi di propagazione di questa operazione di somma.

Figura 3.8 Struttura utilizzata per effettuare la somma degli otto prodotti parziali.

Si noti come il ritardo complessivo del circuito risulti essere dovuto al ritardo delle PP-cell, più il ritardo di cinque full-adder, più il ritardo del circuito CLA. Se avessimo realizzato il moltiplicatore utilizzando l’algoritmo di shift e somma avrei dovuto utilizzare 11 sommatori con riporto del carry, i quali anche se fossero stati realizzati con architetture di tipo CLA avrebbero introdotto un ritardo complessivo maggiore di quello ottenibile con questo circuito.

Notiamo come i prodotti parziali siano esprimibili su 27 bit, a causa del fatto che il moltiplicando è rappresentato su 24 bit e ulteriori 3 bit sono necessari nel caso dell’operazione di moltiplicazione per sette. Anche se la rappresentazione su 27 bit si ha solo nel caso peggiore, si deve considerare che il circuito deve essere dimensionato in queste condizioni, in quanto il suo funzionamento deve essere garantito per qualunque operazione di moltiplicazione. Si avrebbe quindi che il numero di full-adder che compongono i vari circuiti di somma sarebbe quello riportato in Tabella 15.

Tabella 15 Numero di full-adder per ogni circuito sommatore. Sommatore N° Full-Adder ADD1 27 ADD2 27 ADD3 27 Wallace Tree 132 CLA 35

In realtà per quanto visto nel paragrafo 3.1, sappiamo che il risultato della moltiplicazione è sempre esprimibile su 24 bit, da cui le dimensioni dei vari sommatori possono essere ridotte assumendo i valori riportati in Tabella 16. Si noti che le dimensioni di ADD2 e ADD3 sono inferiori rispetto a quelle di ADD1 rispettivamente di 3 e 6 full-adder, in quanto i prodotti parziali che devono sommare sono shiftati a sinistra appunto di 3 e 6 posizioni rispettivamente.

Tabella 16 Numero ridotto di full-adder per ogni circuito sommatore

Sommatore N° Full-Adder ADD1 24 ADD2 21 ADD3 18 Wallace Tree 96 CLA 23

In totale avremo quindi un risparmio complessivo in termini di full-adder pari a 66, con quindi una notevole riduzione di area del circuito. Si osservi infine che solamente i 12 bit più significativi dell’uscita del CLA andranno a rappresentare il risultato, infatti abbiamo detto che il risultato della moltiplicazione deve essere diviso per 4096, in modo da riportare il risultato sull’ordine di grandezza desiderato.

3.3 Il divisore

Il circuito divisore consente di realizzare la divisione fra 4095 e ∆Ph, con un errore algoritmico sufficiente a fare in modo che il calcolo complessivo della (1-18) sia affetto da un errore inferiore alla risoluzione del sistema d’interpolatore a due livelli. Si è visto come per ottenere un tale errore si moltiplichi 4095 per 4096, e quindi si effettui la divisione per ∆Ph. Nel paragrafo 3.1 si è anche osservato, che le specifiche in termini di velocità di tale circuito non sono stringenti, in quanto la variazione di ∆Ph avviene in tempi notevolmente superiori al clock del sistema. Quindi si comprende che per la realizzazione di questo circuito non è necessario andare a ricercare in letteratura architetture ottimizzate per il calcolo veloce, bensì possiamo utilizzare una architettura maggiormente lenta, ma con occupazione complessiva di area sul chip inferiore. Vogliamo fare notare che in realtà la velocità del divisore incide sulle caratteristiche del DDS, in quanto da essa dipende il tempo thopp del sistema. Infatti la variazione di ∆Ph

porterà effettivamente ad una frequenza sintetizzata differente dopo che il circuito divisore avrà terminato il calcolo e quindi avrà presentato il suo dato in ingresso al moltiplicatore. Fintanto che il divisore non è a regime i dati in uscita dal moltiplicatore sono errati e non introducono il corretto ritardo sul segnale MSB. Di seguito introdurremo il classico algoritmo di divisione e cercheremo di mettere in luce le sue principali limitazioni, dopodiché andremo ad analizzare la realizzazione del circuito divisore utilizzato.

3.3.1 Algoritmo di divisione

Un tipico algoritmo di divisione è quello consistente nella scomposizione modulare del divisore [11].

La Figura 3.9 riporta un esempio di applicazione di tale algoritmo dove con X si è indicato il divisore e con Y il dividendo. Se chiamiamo m il numero di bit del dividendo avremo che il singolo passaggio dell’algoritmo viene realizzato considerando m + 1 cifre del divisore e le m cifre del dividendo. In tale passaggio vengono implementate le seguenti relazioni:

⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ = < − < X se X Y altrimenti Y X Y X se altrimenti R Q 0 1 ( 3-19 )

Il singolo passaggio può essere quindi realizzato con un apposito circuito che risulta essere mostrato in Figura 3.10. Se indichiamo con n il numero di bit del divisore avremo che il numero di blocchi necessari per ottenere il risultato complessivo sono n-m-1.

Figura 3.10 Circuito modulare di calcolo della divisione.

Il sistema presenta tuttavia inevitabili problemi che per essere risolti necessitano di ulteriore circuiti. Innanzitutto si deve osservare che le dimensioni del dividendo in termini di bit utili non sono costanti (vedi Tabella 17), da cui necessiteremo di un circuito apposito che effettui un controllo sul dividendo in modo da verificare il numero di bit utili sui quali è esprimibile. In funzione del risultato di tale circuito avremo che le dimensioni dei blocchi che realizzano il singolo passaggio dell’algoritmo modulare variano, e al contempo varia anche il numero di passaggi necessari ad ottenere il risultato finale.

Tabella 17 Esempio di rappresentazione del dividendo sui suoi bit utili. Dividendo (8 bit) Dividendo (bit utili) 00000001 1 00001011 1011 01110011 1110011 10000000 10000000

Tali problemi non possono essere risolti in modo banale, infatti se osserviamo la Figura 3.10, notiamo come in seguito alla variazione del numero di bit utili del dividendo, le dimensioni del sottrattore debbano essere variate.

Figura 3.11 Esempio di errore nel calcolo della divisione.

Se infatti inviamo a questo due dati espressi su un numero di bit inferiore rispetto a quelli per cui tale circuito è stato dimensionato, non si potrebbe avere mai la generazione del segnale Q, in quanto non vi sarebbe mai alcun riporto. Un ulteriore problema di tale algoritmo risiede nel fatto che non sempre i bit del divisore da considerare sono m+1, in alcuni casi possono essere solamente m. La Figura 3.11 riporta un esempio di quanto appena detto. Notiamo come il problema nasca dal fatto che al primo passaggio il dividendo deve essere confrontato con il numero minimo dei bit del divisore tali da essere maggiore del dividendo stesso2, tale numero a seconda del valore del dividendo può essere pari ad m o ad m+1. Quello che vogliamo è evitare questo in quanto il circuito di calcolo non può conoscere a priori se il numero di bit del divisore che deve considerare è m o m+1.

2 _{E’ analogo a quando si effettua la divisione in base 10, in cui si verifica se il dividendo “sta”,} nella prima cifra del divisore, se questo accade si controlla quante volte ci “sta”, altrimenti si verifica se il dividendo “sta” nelle prime due cifre del divisore, e così via.

3.3.2 Architettura del divisore

Abbiamo già visto come il circuito divisore effettui la divisione fra due numeri X e Y rispettivamente espressi su 24 e 12 bit. Notiamo che X è uguale al prodotto fra 4095 e 4096, da cui sarà un valore costante, mentre Y è uguale a ∆Ph, quindi il suo valore potrà variare fra 1 e 4095. Poiché Y varia su un tale intervallo verremo ad avere che il numero di bit utili sui quali può essere rappresentato varia da 1 a 12; dunque si presenterà il problema discusso nel capitolo precedente, e quindi dovremo apportarvi rimedio. Prima di vedere questo analizziamo l’altro problema di cui era affetto il divisore.

Figura 3.12 Esempi di calcolo con l’estensione di uno zero.

Avevamo detto che non sempre il numero di bit del divisore da considerare è

m+1, da cui dobbiamo prevedere una opportuna modifica circuitale in modo da

ovviare a questo. La modifica proposta è molto semplice, infatti consiste nell’estendere su 25 bit il divisore aggiungendo uno zero. La Figura 3.12 riporta due esempi di calcolo della divisone con la modifica apportata. Si noti come in entrambi i casi il risultato sia corretto e pari al valore desiderato.

La risoluzione dell’altro problema, ossia della variazione del numero di bit utili su cui è espresso Y può essere ottenuto con la modifica circuitale mostrata in Figura 3.13. Infatti si osservi che il sottrattore deve effettuare la differenza in modo da valutare le due relazioni (3-19). Per ottenere quindi una valutazione di queste due relazioni qualunque sia la dimensione degli operandi, e utilizzando un unico circuito di sottrazione dimensionato per funzionare con qualunque dimensione di

Y, abbiamo disposto i dati come mostrato in Figura 3.14. Sostanzialmente

qualunque siano i bit utili di Y l’ultimo full-adder che compone il circuito sottrattore è sempre utilizzato, da cui avremo sempre l’informazione sul riporto desiderata. La generazione dei dati mostrati in Figura 3.14 può essere ottenuta, una volta noti i bit utili di Y, andando ad utilizzare dei registri nei quali azzeriamo i bit non utilizzati e impostiamo i restanti in funzione dei bit necessari di X e di Y.

Figura 3.14 Metodo di disposizione dei bit all’interno dei registri A e B.

Per ottenere quest’ultima cosa si comprende la necessità di circuiti multiplexer, indispensabili a causa del fatto che il numero di bit da inviare ai registri non è sempre costante ma varia in funzione dei bit utili. La cella di Figura 3.13 costituisce il blocco base per la realizzazione del circuito divisore nella sua scomposizione modulare. Si fa notare che la determinazione dei bit utili di Y può essere semplicemente ottenuta ricorrendo ad un encoder con priorità crescenti, dove la massima priorità è associata al bit più significativo di Y. Tale circuito genera in uscita la parola digitale corrispondente al bit ad 1 di Y con priorità più elevata.

Poiché non abbiamo specifiche temporali stringenti, abbiamo deciso di utilizzare una realizzazione di tipo seriale, la quale a discapito di una minore velocità di calcolo consente di ottenere una minore complessità hardware. Tale

architettura nasce dall’osservazione che ogni passaggio dell’algoritmo di divisione può essere realizzato ricorrendo ad una cella come quella mostrata in Figura 3.13. Si può quindi pensare di utilizzare in modo iterativo tale cella per tutti i passaggi dell’algoritmo necessari al calcolo del risultato. Come osservato nel paragrafo precedente il numero di passaggi dell’algoritmo è variabile in funzione del numero dei bit utili di Y, il peggiore dei casi si ha quando questi sono pari ad 1; in tale caso avremo un numero di passaggi totale pari a 23, si capisce quindi che la struttura utilizzata consente un risparmio di 22 celle, con un notevole riduzione dell’area finale del chip. Avremo inoltre un tempo di calcolo che nel peggiore dei casi risulterà essere di 23·TCK=191.59 ns.

3.4 Il circuito External/Internal

Il circuito External/Internal consente di inviare al sistema d’interpolazione i segnali prodotti internamente o quelli prodotti esternamente. Più nel dettaglio abbiamo che se l’ingresso ext è a livello logico basso, all’interpolatore vengono inviati il segnale MSB prodotto dall’accumulatore e i segnali di comando generati dall’unità di calcolo, se invece tale ingresso è a livello logico alto, verranno inviati all’interpolatore il segnale MSB_ext e i segnali di comando esterni. La presenza di questo circuito è di notevole importanza in fase di test del chip, in quanto consente di poter testare il sistema d’interpolazione indipendentemente dal corretto funzionamento della restante parte del DDS. Internamente a questo circuito è stato inserito anche il decoder 5 to 32, il quale ha il compito di trasformare i 5 bit più significativi del risultato dell’unità di calcolo, nei segnali utili a pilotare il multiplexer, del primo livello d’interpolazione. Si è inoltre previsto l’inserimento di un registro su tutte le uscite verso l’interpolatore, in modo da stabilizzarle. Si deve infatti osservare che l’interfacciamento fra il circuito sincrono e il sistema d’interpolazione non è affatto banale, a causa dell’asincronia di quest’ultimo. Si comprende quindi, come sia utile avere dei precisi riferimenti temporali dei segnali verso l’interpolatore in funzione del clock di sistema, in modo tale da poter fissare delle precise relazioni temporali tali da consentire il funzionamento complessivo del circuito.

3.5 Sintesi e simulazione del sistema

Il flusso di progetto che ha portato alla realizzazione del circuito sincrono complessivo è quello mostrato in Figura 3.15. La descrizione del circuito è stata effettuata completamente ricorrendo al linguaggio VHDL, mentre la sintesi è stata ottenuto mediante il sintetizzatore Design Analyzer del software Synopsys, il quale utilizza il design kit del processo 0.35 um della AMS.

Figura 3.15 Flusso di progettazione VHDL.

Il primo passo da seguire ai fini di una buona progettazione dl sistema, è ricorrere ad una organizzazione di tipo gerarchico, la quale consiste nel descrivere e testare i vari blocchi in modo separato. L’operazione di test del funzionamento, ovviamente realizzata con simulazioni pre-sintesi, è stata realizzata ricorrendo a file di testbench opportunamente realizzati in modo da verificare il corretto funzionamento per qualunque valore degli ingressi. Questo risulta essere molto importante in quanto permette di valutare la presenza di eventuali errori di descrizione. Dopo avere descritto e testato il singolo blocco, li abbiamo uniti per formare il sistema complessivo; anche tale sistema, a parità degli altri blocchi,

richiede di accurate operazioni di test che permettono di verificarne il corretto funzionamento. L’operazione successiva alla descrizione è stata la sintesi per effettuare la quale si è reso necessario specificare un certo numero di direttive e constraints al sintetizzatore. Le direttive che vengono assegnate al sintetizzatore riguardano la frequenza di clock al quale vogliamo far funzionare il circuito, e i carichi capacitivi che devono pilotare le uscite; tali specifiche sono di notevole importanza in fase di sintesi, in quanto valori differenti di queste possono portare a sintesi notevolmente differenti. Per quanto riguarda invece le constraints, si è specificata la minimizzazione dell’area finale del chip, da cui il sintetizzatore in fase di sintesi verifica le direttive assegnate cercando di minimizzare l’area complessiva. E’ stato infine necessario andare a specificare le condizioni operative alle quali vogliamo effettuare la sintesi, tali condizioni sono Worst Speed (WS), Worst Power (WP) e Tipical Mean (TM). Poiché il nostro interesse è realizzare un sistema funzionante in qualunque condizione operativa, abbiamo deciso di effettuare la sintesi nelle condizioni peggiori possibili, ossia WS. A questo punto il sintetizzatore procede alla sintesi del sistema restituendo in un opportuno file di report i risultati ottenuti in funzione delle direttive, delle costraints e delle condizioni operative specificate. Da tale file possiamo valutare innanzitutto se il sintetizzatore è riuscito o meno a sintetizzare il circuito alla frequenza di clock desiderata3. Poiché nel nostro caso non ci riusciva, abbiamo dovuto apportare delle modifiche architetturali che consentissero la riduzione dei tempi di propagazione, in modo tale da rendere possibile la sintesi. Per risolvere tale problema abbiamo individuato dapprima i percorsi critici del sistema evidenziandone uno internamente al moltiplicatore e l’altro internamente al divisore. Tali percorsi critici presentavano dei tempi di propagazione della logica notevolmente elevati rispetto al clock del sistema. Per ridurre tale tempo di propagazione si è deciso di aumentare i livelli di pipeline del sistema.

3 _{Non sempre il sintetizzatore riesce a sintetizzare il circuito, questo può accadere se ad esempio la} frequenza alla quale si vuol fare funzionare il circuito è troppo elevata per la tecnologia utilizzata, e l’architettura scelta.

Figura 3.16 Riduzione del tempo di propagazione dei cammini critici inserendo un livello di

pipeline.

La Figura 3.16 mostra come si può, in un sistema sincrono, spezzare i cammini critici inserendovi un registro, ossia inserendo un livello di pipeline. Tale tecnica risulta essere applicabile in quanto in generale le reti combinatorie RC1 e RC2 sono meno complesse della rete RC, da cui presenteranno anche tempi di propagazione inferiori. Dalla Figura 3.16 tuttavia si comprende che l’inserimento di un livello di pipeline, aumenta la latenza del dato in uscita di un tempo pari a un ciclo di clock. In generale l’inserimento di K livelli di pipeline aumenta la latenza del dato di K cicli di clock. Per riuscire ad ottenere la sintesi del sistema è stato necessario introdurre tre livelli di pipeline nel moltiplicatore e due nel divisore. L’aumento della latenza nel moltiplicatore porta a dover ritardare anche il tempo con cui esce il segnale MSB. Infatti si osservi che senza l’introduzione del pipeline, il dato di comando dell’interpolatore, corrispondente all’uscita dell’unità di calcolo, veniva prodotto un ciclo di clock prima dell’arrivo del fronte di MSB, in modo da poter mandare a regime la logica interna all’interpolatore. Con l’aggiunta dei tre livelli di pipeline avremo che il dato di comando dell’interpolatore è ritardato di 3 cicli di clock, da cui dovremo ritardare della stessa quantità anche il segnale MSB, in modo che le relazioni temporali fra i due siano rispettate. Per quanto riguarda il divisore si ha invece che la sua realizzazione in pipeline, presenta un tempo di calcolo doppio rispetto a quella non in pipeline, da cui il tempo di calcolo del divisore risulterà essere di

383.18 ns. Tale tempo incide sul tempo di hopping del DDS che tuttavia anche se non è piccolissimo, è molto minore di quello ottenibile con i classici sistemi a PLL. Inoltre un miglioramento di tale tempo si potrebbe ottenere ricorrendo ad una architetture maggiormente ottimizzate di divisori presenti in letteratura. In Tabella 18 si è riportata l’area complessiva stimata con Synopsys; si osservi come le dimensioni complessive del circuito siano abbastanza contenute.

Tabella 18 Stima ottenuta con Synopsys dell’area occupata dal circuito sincrono.

Area non combinatoria 0.3 mm²

Area combinatoria 0.4 mm²

Area totale 0.7 mm²

Per quanto riguarda il consumo di potenza complessivo del circuito sincrono possiamo effettuare solamente considerazioni di natura intuitiva, in quanto il design kit messo a disposizione dalla AMS, non consente la stima del consumo di potenza tramite Synopsys. Osserviamo come il circuito divisore sia attivato solamente quando si ha la necessità di modificare la frequenza sintetizzata, in questo caso sarà attivo per un numero di cicli di clock che nel peggiore dei casi è pari a 23. Avremo quindi che il suo contributo al consumo totale di potenza è relativamente basso, a meno di non utilizzare il circuito in applicazioni dove si necessità di modificare continuamente la frequenza sintetizzata. Per quanto riguarda il moltiplicatore bisogna osservare che effettivamente è abilitato solamente quando è presente una commutazione del segnale MSB da livello logico basso a livello logico alto, da cui questo circuito presenterà un consumo di potenza che è funzione della frequenza da sintetizzare. In particolare nel peggiore dei casi, corrispondente alla massima frequenza sintetizzata avremo che il moltiplicatore è attivo ogni due cicli di clock, da cui in tale condizioni avremo il massimo consumo di potenza da parte di questo. Nel complesso avremo quindi che solamente il circuito accumulatore è sempre attivo e porta ad un consumo di potenza sempre presente, in tutti gli altri casi avremo un consumo di potenza che è funzione della frequenza da sintetizzare e della velocità con la quale intendiamo variarla.

Come ultimo passo della progettazione del sistema abbiamo effettuato una simulazione post-sintesi, verificando che il circuito sintetizzato presentasse effettivamente il comportamento desiderato. Tale simulazione è mostrata in Figura 3.17.

Figura 3.17 Simulazione post-sintesi del sistema sincrono.

In figura possiamo osservare come effettivamente i segnali di comando dei due livelli d’interpolazione varino un ciclo di clock prima dell’arrivo del fronte in salita del segnale MSB, in questo modo si da il tempo alla logica interna all’interpolatore di andare a regime. Dai risultati mostrati in figura possiamo anche andare a determinare, in funzione dei segnali di comando, la distanza finale fra due fronti del segnale MSB, una volta avvenuto il riposizionamento; in questo modo possiamo controllare se l’unità di calcolo opera o meno in modo corretto. Andiamo per esempio a valutare alcune di queste quantità:

nS T T TCK (15 6) S (78 96) P 27.2969 3⋅ + − ⋅∆ + − ⋅∆ = ( 3-20 ) nS T T T_CK (24 15) _S (59 78) _P 27.2949 3⋅ + − ⋅∆ + − ⋅∆ = ( 3-21 ) nS T T T_CK (1 24) _S (42 59) _P 27.2969 4⋅ + − ⋅∆ + − ⋅∆ = ( 3-22 )

Si noti come effettivamente una volta ritardati, i fronti di MSB siano equidistanziati a meno di un errore temporale di 2 ps, pari alla risoluzione del nostro sistema.

L’ultima operazione effettuata è stata salvare il file di sintesi in formato Verilog, in quanto tale formato è quello necessario per importare il sistema nell’ambiente di progettazione di Cadence, in cui effettueremo il Place&Route finale del chip.