Implementazione VHDL dell'algoritmo CORDIC Vectoring
Obiettivo del progetto
Progettare un circuito digitale che realizzi la trasformata da coordinate cartesiane a polari implementando l’algoritmo CORDIC (COordinate Rotation DIgital Computer) in modalità Vectoring.
Pre-requisiti di progetto
Il progetto richiede, oltre che una pre-documentazione sull'algoritmo, anche la scelta del numero di iterazioni da effettuare (e quindi anche il numero di valori di arctan da memorizzare nella ROM) - CORDIC è un algoritmo iterativo; creare un testbench apposito per testare le componenti implementate; confrontare i risultati approssimati dell'implementazione con i risultati dell'algoritmo reale (libero da problemi di rappresentazione numerica).
Cosa è CORDIC
Il CORDIC (COordinate Rotation DIgital Computer) è un algoritmo hardware-efficient per eseguire la rotazione di un vettore su un piano. Con questo metodo è possibile calcolare funzioni trigonometriche ed eseguire conversioni di coordinate da cartesiane a polari e vice-versa. E' un algoritmo iterativo estremamente efficiente dal punto di vista hardware perchè richiede solo operazioni di somma, sottrazione, shift e lettura da ROM. E' quindi particolarmente adatto in sistemi come microcontrollori e architetture FPGA, o in generale per implementazioni hardware in cui non sono disponibili moltiplicatori.
Le equazioni iterative del CORDIC sono:
I valori di arctan(2-i) possono essere calcolati una volta per tutte ed essere ricavati, ad ogni passo, per esempio, da una tabella di look-up. Gli angoli possono essere indifferentemente espressi in radianti o in gradi.
I valori di di, x0, y0 e z0 vengono opportunamente decisi a seconda della modalità in cui si vuole che l’algoritmo operi: rotation o vectoring. La modalità vectoring ruota un vettore (x0, y0) dell’angolo necessario per allinearlo all’asse x. I risultati sono: la fase del vettore, leggibile nell’accumulatore dopo l’ultima iterazione (zn) e il modulo del vettore (scalato a causa del guadagno), corrispondente a xn. Ad ogni passo la direzione di rotazione è quella che permette di minimizzare il modulo della componente y del vettore, cioè è scelta in base al segno di yi. Perciò di = 1 se yi < 0, -1 altrimenti. Dopo n iterazioni si ottengono:
con
Scegliendo in maniera opportuna la modalità CORDIC e il valore degli ingressi è possibile ottenere diversi risultati con l’applicazione del medesimo algoritmo: calcolo del seno, coseno o arcotangente di un angolo, rotazione di un vettore di un certo angolo, calcolo del modulo di un vettore, trasformazione da coordinate cartesiani a coordinate polari e viceversa.
In genere, se è possibile calcolare una certa funzione con CORDIC (ad esempio il seno e il coseno) è possibile anche calcolare la sua inversa (ad esempio arcoseno e arcocoseno). Inoltre, effettuando alcune modifiche all’algoritmo è possibile estenderlo per il calcolo di funzioni lineari e per il calcolo di funzioni iperboliche.
Riguardo il progetto, per la trasformazione da coordinate cartesiane a coordinate polari la modalità da impiegare è la modalità Vectoring e i parametri vanno così inizializzati:
Architetture realizative
Esistono diversi modi per realizzare in hardware l’algoritmo CORDIC; la scelta sulla configurazione da utilizzare è un trade-off fra la velocità e l’area occupata. La prima soluzione viene direttamente dalle tre equazioni di base del CORDIC ed è detta bit-parallel iterative.
Il segnale di rappresenta il segnale di decisione per ogni ciclo e il suo valore viene deciso in base al segno di yi. Alla prima iterazione i valori degli ingressi x0, y0 e z0 devono essere caricati nei corrispettivi registri; nelle iterazioni successive i registri contengono invece i valori xi, yi e zi calcolati. Questa discriminazione viene fatta per mezzo dei multiplexer, che devono essere comandati da un segnale che indichi se ci troviamo alla prima iterazione o no. Gli shifter traslano di un numero di posizioni variabile corrispondente alla iterazione corrente. Allo stesso modo l’indirizzo della ROM che contiene gli angoli deve essere incrementato ad ogni iterazione. All’ultima iterazione le uscite possono essere prelevate direttamente dagli adder. Il problema di questa soluzione è rappresentato dagli shifter variabili, che richiedono un alto numero di celle logiche per essere implementati e rendono il dispositivo lento.
Una seconda soluzione è detta bit-serial iterative.
Sono presenti tre adder/subtractor bit-serial, tre shift registrer di dimensione uguale alla dimensione degli ingressi x0, y0 e z0 e una ROM, che contiene i valori dell’arcotangente. Ogni iterazione richiede esattamente n cicli di clock (n = precisione degli adder/subtractor). Inizialmente i dati vengono caricati nei registri un bit alla volta, ed ovviamente questa operazione richiede n periodi di clock. Dopo aver caricato i dati questi vengono shiftati di un bit per volta e inviati ai sommatori/sottrattori ed il risultato viene reinserito nel registro. E' necessaria una rete che all’inizio di ogni ciclo legga il segno di yi e setti il sommatore/sottrattore alla giusta modalità di funzionamento. All’ultima iterazione i risultati possono essere letti mentre i nuovi ingressi vengono caricati nei registri.
Un ultima soluzione è detta bit-parallel unrolled.
Con questa soluzione si ottengono diverse semplificazioni rispetto ai casi precedenti:
- gli shifter non sono più variabili ma fissi e quindi possono essere realizzati sotto forma di collegamenti;
- la ROM viene suddivisa in diverse costanti, che quindi possono essere anch’esse realizzate con logica cablata;
- l’intera rete è combinatoria e non è quindi necessario utilizzare registri.
Si ottiene in sostanza una soluzione a massima performance che richiede però uno spazio proporzionale in qualche modo al numero di passi dell’algoritmo che si vogliono/devono implementare. In tutte le realizzazioni, fatta eccezione dell’ultima, è necessaria una rete che tenga il conto del numero di iterazioni e si occupi di pilotare i multiplexer di ingresso in modo da inviare nei registri o i dati di ingresso o i dati provenienti dall’anello. Una rete apposita (o sempre la stessa) deve controllare ad ogni iterazione il segno di yi, in modo da definire in maniera appropriata il segnale che imposti la modalità di funzionamento degli adder/subtractor.
Schemi dei moduli implementati in VHDL*
L’obiettivo del progetto è quello di realizzare tramite CORDIC la funzionalità di conversione da coordinate cartesiane a coordinate polari. Guardando la tabella si può vedere che occorre usare CORDIC in modalità Vectoring ponendo come ingresso le coordinate x ed y da convertire. z0 in questo caso non è un ingresso significativo, in quanto funge da offset per l’angolo finale, quindi è conveniente porlo pari a 0. Il modulo risultante del vettore è scalato del guadagno An. L’angolo corrispondente è contenuto nell’accumulatore. Si è scelto di implementare due versioni dell’algoritmo, una come rete sincronizzata ed una come rete combinatoria.
Indipendentemente dal tipo di rete, la figura mostra lo spazio degli ingressi (x0, y0) ammessi (area A).
A causa delle limitazioni dell’algoritmo, in assenza di un circuito per la correzione degli input, la componente x del vettore di ingresso non può assumere valori negativi (area B). Se l’uscita è rappresentata su 16 bit in complemento a due e in virgola fissa (8 bit per la parte intera e 8 per la parte frazionaria), il modulo massimo del vettore di ingresso per evitare problemi di overflow deve essere contenuto in un’area di raggio 27 - 2-8 (A + C + D). Però, dato che l’algoritmo introduce un guadagno, l’area valida viene ulteriormente ristretta (A + D). Per essere sicuri di non provocare overflow si può limitare x all’intervallo[0, 25 - 2-8] e y all’intervallo [-25, 25 - 2-8] , imponendo quindi che il vettore di ingresso debba trovarsi nell’area A. Si è scelto di dimensionare ingressi e uscite sullo stesso numero di bit (16), lasciando all’utilizzatore l’onere di rispettare questi vincoli. Nel caso in cui l’utente volesse calcolare modulo e fase di un vettore a componente x negativa, dovrebbe cambiare il segno sia di x che di y e sommare 180' alla fase ottenuta. Gli angoli possono essere espressi indifferentemente sia in gradi che in radianti. Una volta stabilita una dimensione di 8 bit per la parte frazionaria, si è scelto di utilizzare i gradi in quanto usando i radianti si sarebbe ottenuta minore precisione. Volendo scegliere i radianti sarebbe stato più conveniente utilizzare un minor numero di bit per la parte intera e un numero maggiore per la parte decimale (ad esempio 4 e 12). La dimensione della ROM è determinata, oltre che dal formato di rappresentazione dell’angolo, anche dal numero di iterazioni che l’algoritmo deve compiere, in quanto deve contenere tante entrate quante sono le iterazioni. In teoria, più è alto il numero delle iterazioni e più è alta la precisione che i risultati raggiungono. In realtà però dopo 16 iterazioni gli shifter annullano completamente i valori al loro ingresso, quindi il numero di iterazioni massimo equivale proprio a 16, cioè il numero di bit su cui si lavora all’interno del modulo. Anche il valore del guadagno è influenzato dal numero delle iterazioni in quanto si è già detto che questo si calcola con
e il suo valore limite è 1.647. In realtà si è visto che, per ingressi a 16 bit, il guadagno tende a stabilizzarsi a questo valore dopo appena 10 iterazioni.
CORDIC combinatorio
Questa architettura implementa lo schema unrolled CORDIC.
Ogni modulo step_unrolled implementa un livello della terza architettura vista nel paragrafo Architetture realizative. La ROM è stata suddivisa in 16 costanti. L’ingresso z è sempre posto a 0. I vari moduli sono collegati in cascata.
Il bit più significativo di yi (il segno di yi) viene usato per impostare la modalità di lavoro degli adder/subtractor.
CORDIC sincronizzato
Il CORDIC sincronizzato è strettamente correlato alle equazioni di base dell’algoritmo. Esso ha la seguente struttura
La rete ctrl gestisce:
- il contatore delle iterazioni i incrementandolo ad ogni clock;
- il segnale load_iterate, che pilota i multiplexer affinchè carichino il valore degli ingressi alla prima iterazione e i valori in uscita dal sottomodulo step durante tutte le altre iterazioni.
z viene forzato a 0, secondo quanto precedentemente detto. La rete combinatoria step implementa le tre equazioni CORDIC ed ha la seguente struttura
I moduli shifter sono variabili in dipendenza del numero di iterazione i. Il bit più significativo di yi (il segno di yi) viene usato per impostare la modalità di lavoro degli adder/subtractor. La ROM rom16 contiene i 16 valori degli angoli. La temporizzazione è la seguente
Ogni ciclo di clock corrisponde ad un’iterazione dell’algoritmo, quindi per eseguire una conversione completa sono necessari 16 cicli. I dati di ingresso vengono caricati dal modulo al colpo di clock che conclude l’ultima iterazione della conversione precedente, quando il valore di load_iterate è zero. Contemporaneamente è possibile leggere i risultati della conversione appena conclusa sulle porte di uscita.
Test delle unità e testbench
Entrambe le architetture sono state testate con ModelSim, fornendo lo stesso insieme di input. I due moduli hanno prodotto gli stessi risultati, e pertanto sono stati riportati in tabella alla stessa voce ’CORDIC’. I risultati sono stati confrontanti con valori calcolati con altri procedimenti software, realizzati in ambiente Python: sqrt(x^2+y^2), atan2(y,x) e l’algoritmo CORDIC operante su numeri in virgola mobile. Gli ingressi x e y e le uscite ’CORDIC’ sono state riportate sia in decimale che in esadecimale. E' importante ricordare che i valori del modulo restituiti dagli algoritmi CORDIC sono comprensivi del guadagno A16.
Nei casi indicati con 1,2,4,5 si è verificato overflow, come previsto. Nel caso 6 dato che x < 0 sia i moduli realizzati che l’algoritmo operante in virgola mobile hanno ritornato valori errati. Nel caso 3 sono stati scelti come ingressi i numeri positivi più piccoli rappresentabili.
Conclusioni
I moduli realizzati operano come previsto dall’algoritmo, ma presentano alcune limitazioni. Un possibile sviluppo futuro potrebbe affrontare la questione della correzione degli ingressi realizzando una rete che, dato il segno dell’ingresso x, si preouccupi di cambiare il segno a entrambi gli ingressi e di caricare una costante di 180' nell’accumulatore degli angoli. Un altro studio interessante sarebbe quello di osservare il variare della precisione del risultato facendo scelte progettuali differenti, ad esempio in relazione al numero di bit e di iterazioni. Infine, il modulo potrebbe essere generalizzato in modo da rendere possibile operare in una modalità scelta dinamicamente tra vectoring e rotation, dato che le due modalità possono essere implementate condividendo la maggior parte dei componenti.
* Per motivi di spazio il codice VHDL non è riportato. Potete richiederlo usando il modulo Contattami, indicando chiara motivazione.
Compatibile con
Ris. min. 1024x768
© 2008-2010 Alessio Amato