Circuito per il calcolo della radice quadrata

Circuito per il calcolo della radice quadrata

Si vuole progettare un circuito sequenziale in grado di calcolare la radice quadrata di un numero N, utilizzando il metodo iterativo di Newton-Raphson in cui ogni approssimazione successiva al risultato è espressa dalla formula:

Le operazioni descritte da questa formula devono essere iterate fin quando due risultati parziali consecutivi non diventano uguali per via dei troncamenti dovuti alla precisione finita delle rappresentazioni numeriche utilizzate nel circuito. Il numero N è un intero a 16 bit, maggiore di 1, che si intende proveniente dall'esterno. Si abbia inoltre a disposizione un circuito divisore con dividendo a 32 bit, divisore a 16 bit e quoziente ancora a 16 bit. L'approssimazione iniziale della radice quadrata cercata, ossia il valore di x₀, è un numero a 16 bit i cui 8 bit più significativi devono essere ricavati da una memoria ROM indirizzata dagli 8 bit più significativi del numero N.

Il circuito è avviato da un segnale di LOAD, alla ricezione del quale è possibile acquisire dall'esterno il numero N. Deve poi essere generato un segnale di END non appena il risultato viene reseo disponibile in uscita su un apposito registro. Occorre infine prevedere una logica di controllo in modo che il circuito ignori eventuali altri segnali di LOAD fin quando non abbia completato il calcolo in corso.

Come in molti altri problemi, anche in questo occorre prestare debita attenzione al formato dei dati. Mentre sono prescritti i vincoli sul numero N in ingresso, non è specificato in quale formato numerico debba essere rappresentata l'uscita del circuito. Il circuito divisore che si assume a disposizione, tuttavia, ha quoziente e divisore a 16 bit, e dunque appare evidente che le varie x_i devono essere tutte a 16 bit, per poter utilizzare appieno il circuito divisore e calcolare il risultato con la migliore precisione possibile.

Poiché è 0 < N < 2¹⁶, sarà sicuramente . Converrà allora, in prima ipotesi, rappresentare i valori x_i con 8 bit di parte intera ed 8 bit di parte frazionaria, in maniera da avere la massima precisione possibile sul risultato. Rappresentazioni in virgola fissa (fixed point) di questo tipo si indicano con la notazione I.F, dove I rappresenta il numero di bit assegnati alla parte intera e F è il numero di bit assegnati alla parte frazionaria; nel caso in questione, pertanto, la rappresentazione delle x_i ha formato 8.8.

Questo formato, tuttavia, comporta degli inconvenienti quando N assume il massimo valore, ossia 2¹⁶ - 1. In questo caso, poiché il valore di x_i deve essere minore di 2⁸, può accadere che il risultato di un'iterazione di Newton-Raphson assuma valori non rappresentabili nel formato 8.8. Deve infatti risultare:

ossia:

e se N vale 2¹⁶ - 1, questa relazione si traduce in 256-1 < x < 256+1, ossia in x = 256, valore che non è rappresentabile con soli 8 bit di parte intera. Di conseguenza, occorre passare al formato 9.7; la disequazione diventa allora:

e se N vale 2¹⁶ - 1, questa relazione si traduce in un intervallo di valori della x che può essere rappresentato con 9 bit di parte intera.

Una delle operazioni presenti in ciascuna iterazione della formula di Newton-Raphson è la divisione del numero N per l'approssimazione x_i della radice. Dal momento che il circuito divisore prevede un dividendo da 32 bit, e che il numero N di cui si deve calcolare la radice è espresso su 16 bit, occorre stabilire in quale posizione inserire questi 16 bit all'interno del campo da 32 bit del dividendo.

Poiché il divisore ha formato 9.7, e poiché anche il quoziente deve avere lo stesso formato, il formato del dividendo deve necessariamente essere 18.14. Di conseguenza, i due bit più significativi del dividendo devono essere nulli, i successivi 16 andranno collegati direttamente al numero N, ed i rimanenti 14 dovranno essere anch'essi nulli. Lo schema di massima del circuito che calcola il risultato di una iterazione della formula di Newton-Raphson, supponendo che il divisore sia un circuito puramente combinatorio (privo cioè di clock), è illustrato in Fig. 1, dove in corrispondenza di ogni ingresso e di ogni uscita viene indicato il formato dei dati.

È da osservare come né il sommatore né lo shifter modifichino il formato della rappresentazione. Lo shifter viene utilizzato per eseguire rapidamente la divisione per due, mediante un semplice shift verso destra dell'operando.

A partire da questo schema di massima occorre adesso approfondire tutti i punti che rimangono da chiarire. Ad esempio, occorre stabilire come collegare l'uscita x_i+1 del circuito all'ingresso x_i in modo da effettuare correttamente le varie iterazioni; inoltre, occorre anche determinare in quale istante arrestare l'elaborazione.

Per come è strutturato il circuito, non sarebbe evidentemente corretto collegare l'uscita x_i+1 direttamente all'ingresso x_i, in quanto si verrebbe così a creare un loopback combinatorio in cui i dati variano in maniera non sincronizzata. Un circuito divisore, ad esempio, impiega molto più tempo a produrre un risultato di quanto non faccia un circuito sommatore; l'uscita del sommatore varia pertanto in un tempo molto breve, e ciò provoca una ulteriore variazione dell'uscita x_i+1 prima che il divisore abbia terminato le proprie operazioni. Per evitare questo inconveniente, occorre sincronizzare i dati inserendo un registro tra l'uscita x_i+1 e l'ingresso x_i.

Per quanto riguarda la fase iniziale del processo di calcolo, è specificato che le operazioni vengano avviate da un segnale di LOAD che, avendo natura non meglio precisata, si può ragionevolmente supporre di tipo impulsivo; si può anche assumere che la sua durata sia maggiore del tempo di setup di un registro, e che in corrispondenza del suo fronte di discesa il numero N in ingresso sia stabile. Poiché non si hanno informazioni su quanto tempo N rimanga stabile in ingresso, sarà necessario memorizzarne il valore in un registro e mantenerlo per tutta la durata delle operazioni. In seguito a queste considerazioni, il circuito si modifica come illustrato in Fig. 2, dove è anche messo in evidenza come i due bit più significativi e i 14 bit meno significativi del dividendo debbano essere sempre pari a 0.

Il collegamento del segnale di LOAD andrà in seguito ulteriormente modificato al fine di ignorare l'arrivo di eventuali altri impulsi durante le fasi di calcolo, come specificato dal problema. Gli 8 bit più significativi del numero N andranno anche usati come indirizzi per una ROM che fornirà il valore degli 8 bit più significativi di x₀. Questa ulteriore modifica è illustrata in Fig. 3.

Il multiplexer che è stato aggiunto nello schema, e di cui si vedrà tra breve come collegare il bit di selezione, provvede ad inviare al divisore il valore prelevato dalla ROM quando il circuito sta eseguendo la prima iterazione della formula di Newton-Raphson, oppure il valore prodotto in uscita dal circuito (che, come anticipato più sopra, dovrà provenire da un registro) nelle iterazioni successive. Gli 8 bit in uscita dalla ROM devono costrituire gli 8 bit meno significativi della parte intera di x₀; in altri termini, come è anche evidenziato nello schema, il bit più significativo della parte intera e i 7 bit che rappresentano la parte decimale dovranno essere nulli.

Si osservi a questo punto che lo shifter diventa in realtà inutile, visto che lo shift avviene sempre in una sola direzione e di una sola posizione: è sufficiente difatti connettere l'uscita del sommatore ad un normale registro a 16 bit in modo che il dato sia già shiftato di una posizione verso destra. Di conseguenza, il bit meno significativo dell'uscita del sommatore non verrà collegato, i successivi 15 bit andranno connessi ai 15 bit meno significativi del registro, e il carry-out del sommatore andrà collegato al bit più significativo del registro; il carry-in del sommatore deve essere ovviamente pari a 0. In tal modo, è possibile collegare l'uscita del registro direttamente al multiplexer. Lo schema così modificato appare in Fig. 4, dove la sigla LSB sta per bit meno significativo (least significant bit):

L'iterazione della formula deve proseguire fintanto che il risultato in uscita dal sommatore non uguaglia il valore precedente di x_i. Basterà quindi inserire un comparatore di uguaglianza che confronti l'ingresso e l'uscita del registro, e che fornisca come risultato 1 se questi valori sono uguali. Non è possibile, tuttavia, utilizzare l'uscita di questo comparatore per generare il segnale di END richiesto dal problema, in quanto essa non sarà stabile finché il sommatore ed il divisore non abbiano completato le proprie operazioni, e potrebbe generare impulsi spuri di END = 1 che provocherebbero l'arresto anomalo del circuito. È necessario dunque connettere l'uscita del comparatore ad un flip-flop di tipo D che possa campionarla in corrispondenza del fronte di salita dello stesso clock che si invia al registro: il segnale di END verrà allora prelevato dall'uscita di questo flip-flop. L'inattività di questo segnale potrà anche essere sfruttata per proteggere il circuito da eventuali ulteriori comandi di LOAD al registro di ingresso; le connessioni necessarie sono illustratre in Fig. 5.

Si noti come il segnale di END sia stato collegato con un AND al segnale di LOAD: in tal modo, quando END è inattivo il segnale di LOAD non può più raggiungere il registro. Quando END diventa pari ad 1, cioè quando il circuito ha completato le proprie operazioni ed è inattivo, è invece possibile ricevere altri comandi di LOAD, i quali andranno anche a resettare il flip-flop mediante l'ingresso di clear provocando così anche il reset del segnale END. Si noti inoltre che il circuito in realtà non si arresta, ma continua i suoi calcoli anche dopo che END diventa pari ad 1: la cosa non presenta particolari inconvenienti, dal momento che, una volta raggiunta la convergenza, l'uscita continuerà ad assumere sempre lo stesso valore. Si lasciano al lettore i dettagli, peraltro banali, su come collegare l'ingresso di selezione del multiplexer affinché possa inviare al divisore ed al sommatore l'uscita della ROM nella prima iterazione e l'uscita del registro nelle altre.

Circuito per il calcolo della radice quadrata

© 1997-2003 Paolo Marincola (Rome, Italy)
e-mail: pmaNOSPAM@acm.org (eliminare i caratteri "NOSPAM" per ottenere l'indirizzo esatto)
Commenti, osservazioni e suggerimenti sono estremamente graditi.

Last revised: 2003-12-06 19:50