ITTO20010818A1 - Circuito per elevare a potenza. - Google Patents

Description

DESCRIZIONE dell'invenzione industriale dal titolo:

"Circuito per elevare a potenza"

TESTO DELLA DESCRIZIONE

La presente invenzione si riferisce ai circuiti per elevare a potenza, ossia ai circuiti che, a partire da un segnale d'ingresso X rappresentativo di un numero dato, generano in uscita un segnale Y = Xk rappresentativo della k-esima potenza del dato di ingresso .

Nella applicazione più corrente k = 2 ed il circuito si configura come un circuito quadratore.

Circuiti quadratori veloci, in grado di sfruttare in modo efficiente l'area di semiconduttore su cui sono integrati, costituiscono blocchi essenziali per i sistemi per il trattamento digitale dei segnali.

Ad esempio, nel settore delle telecomunicazioni esistono molti circuiti (stimatori di canale, delay locked loop o DLL, rilevatori di potenza, ecc.) che richiedono di calcolare in modo veloce il quadrato di un valore numerico.

Al riguardo si può far utilmente riferimento al ben noto volume di J. G. Proakis, "Digital Communications", 3rd edition, McGraw-Hill, 1995.

Sempre nello stesso settore sono anche note applicazioni che richiedono il calcolo di potenze di ordine più elevato: è il caso, ad esempio, dei cosiddetti predistorcitori utilizzati per compensare i fenomeni di distorsione dei segnali indotti dagli stadi di potenza a microonde .

In tutte le applicazioni considerate, i circuiti devono essere sufficientemente piccoli da poter essere integrati in numero elevato anche su un singolo chip.

Oltre alla velocità ed alle dimensioni (occupazione di area), un altro fattore da tenere in considerazione è dato dalla precisione o accuratezza del risultato conseguito. Esistono infatti diverse applicazioni che richiedono solo un'approssimazione e non già la determinazione assoluta del valore esatto del risultato dell'elevamento a potenza.

Le soluzioni di circuito di elevamento a potenza note nella tecnica si rifanno perlopiù allo schema del moltiplicatore a schiera (array multiplier): si veda ad esempio il documento US-A-5629 885.

In modo indipendente da ogni altra considerazione, tali soluzioni presentano in misura più o meno estesa carattere di rigidità di configurazione e di funzionamento. In particolare, tali soluzioni note non sono facilmente programmabili in termini di precisione desiderata e non consentono - ad esempio - di "scambiare" il grado di accuratezza o precisione del risultato conseguito e/o l'occupazione di area con il tempo di calcolo .

Al riguardo va ancora notato il fatto che, almeno in alcune applicazioni, un circuito di elevamento a potenza (ad es. un quadratore) particolarmente veloce può rivelarsi - a fronte della notevole occupazione di area -in una risorsa ampiamente inutilizzata. Questo in quanto, dopo aver svolto rapidamente la sua funzione, il circuito in questione è poi costretto ad attendere (dando origine ad un tempo di inutilizzo o idle time) il completamento di operazioni di trattamento svolte in modo più lento da altri circuiti a cui è associato.

La presente invenzione si prefigge lo scopo di fornire un circuito di elevamento a potenza in grado di superare gli inconvenienti intrinseci della soluzione secondo la tecnica nota.

Secondo la presente invenzione tale scopo viene raggiunto grazie ad un circuito avente le caratteristiche richiamate in modo specifico nelle rivendicazioni che seguono .

In sintesi, la soluzione secondo l'invenzione sfrutta ai fini della semplificazione e della riduzione dell'onere computazionale il fatto di ricondurre parte dell'operazione di elevamento a potenza ad operazioni condotte su numeri che sono potenze di 2. Questo concetto è stato di per sé già utilizzato in WO-A-00/33174 , dove il quadrato di un certo numero viene stimato tramite un'approssimazione lineare della funzione y=x<2 >condotta fra due punti di riferimento (anchor points) corrispondenti a potenze di 2.

Rispetto a tale soluzione nota, il circuito secondo l'invenzione offre - fra altri - il vantaggio di essere completamente programmabile in termini di precisione del risultato finale ottenuto. In particolare, la precisione può essere modificata durante il funzionamento semplicemente cambiando il numero massimo di iterazioni, parametro suscettibile di essere controllato dall'esterno, ad esempio, tramite un DSP (Digital Signal Processor) .

Vantaggio , questo, che la soluzione secondo l'invenzione condivide con un circuito moltiplicatore descritto in una domanda di brevetto per invenzione industriale depositata in pari data dalla stessa Richiedente .

La soluzione secondo l'invenzione consente altresì di ottenere una notevole riduzione in termini di area occupata rispetto alle soluzioni tradizionali.

L'invenzione verrà ora descritta, a puro titolo di esempio non limitativo, con riferimento ai disegni annessi, nei quali:

- le Figure 1 e 2 sono destinate ad illustrare in termini geometrici i principi teorici che stanno alla base dell'invenzione,

- la Figura 3 illustra sotto forma di uno schema a blocchi la struttura di un circuito secondo l'invenzione, la Figura 4 illustra i possibili criteri di realizzazione di uno dei moduli rappresentati nello schema a blocchi della figura 3, e

- la Figura 5 è un diagramma di flusso che illustra il funzionamento del circuito rappresentato nella figura 3.

A titolo di premessa della presente descrizione appare utile illustrare, facendo riferimento alle figure 1 e 2, il principio (geometrico) che sta alla base del funzionamento del circuito secondo l'invenzione. Per motivi di semplicità, l'illustrazione viene fatta con riferimento all'elevamento al quadrato: è comunque evidente che gli stessi concetti sono applicabili ed estendibili ad una potenza di ordine k qualsiasi.

Si suppone che X rappresenti il numero di cui si vuole calcolare il quadrato Y = X2. Così come avviene normalmente nei circuiti per il trattamento dei segnali di tipo digitale, il valore X è rappresentato da un segnale binario, ossia da una strìnga di bit che assumono valore "0" o "1".

Si supporrà inoltre che X sia un numero positivo qualsiasi, la gestione di un eventuale segno potendo essere agevolmente svolta con circuiti distinti, di per sé noti.

Puntando l'attenzione sulla figura 1, il valore Y = X2 rappresenta l'area del quadrato illustrato nella figura 1.

Si supponga allora che A sia il numero costituente la potenza di 2 immediatamente inferiore od uguale rispetto ad X, ossia, secondo una notazione corrente con riferimento ai numeri binari A = msb(X).

Dall'osservazione della figura 1 è immediato rendersi conto che il valore X2 può essere approssimato dal valore :

Il valore approssimato Si corrisponde alla somma di una prima, una seconda ed una terza porzione di area rispettivamente corrispondenti:

all'area A<2 >del quadrato riprodotto in basso a sinistra nella figura 1,

- all'area A-(X-A) del rettangolo in basso a destra, e - all'area A-(X-A) del rettangolo in alto a sinistra. Queste due aree risultano uguali fra loro, il che spiega la presenza del fattore 2 nella formula sopra richiamata .

L'area del quadrato R' rappresentato come un'area tratteggiata in alto a destra costituisce l'errore di approssimazione il cui valore è pari (si osservi sempre la figura 1 per l'immediata comprensione del significato geometrico di quanto affermato) al prodotto (X-A)<2>.

Adottando gli stessi criteri visti in precedenza, il valore di questo errore (ossia in pratica l'area del quadrato R' rappresentato nella figura 1) può essere a sua volta approssimato sotto forma del prodotto seguente:

Anche in questo caso il significato dell'approssimazione è immediatamente comprensibile in termini geometrici facendo riferimento alla rappresentazione della figura 2.

In questo caso il valore B è identificato come la potenza di 2 minore od uguale rispetto a (X-A), ossia B = msb (X - A).

Anche in questo caso rimane un errore corrispondente all'area del quadrato R'' rappresentato nell'angolo in alto a destra della figura 2.

Si può tuttavia agevolmente comprendere che la procedura descritta può essere iterata M volte - con M = log2 (max (X)-1), dove max(X) rappresenta il massimo della distribuzione dei possibili valori di X in ingresso -così da ottenere il valore esatto dell'operazione di elevamento a potenza in base all'espressione:

Naturalmente, quello rappresentato nelle figure 1 e 2 (e nella successiva sequenza di passi fino al passo M concettualmente desumibile dalla rappresentazione delle figure 1 e 2) corrisponde al criterio iterativo più generale suscettibile di essere ipotizzato. In realtà M iterazioni di calcolo risultano necessarie solo per taluni valori "critici" di X, mentre in molti altri casi per ottenere il valore esatto di X<2 >è sufficiente un numero di passi anche di molto inferiore.

Così come già si è detto, il procedimento secondo l'invenzione può essere applicato anche ad un fattore di elevamento a potenza maggiore di due, ad esempio a k = 3, nel qual caso il quadrato A<2 >assume la forma di un cubo, ed i rettangoli di area la forma di parallelepipedi, ecc ..

L' invenzione si basa sul riconoscimento del fatto che l'elevamento a potenza di un qualsiasi numero può essere ricondotto ad un complesso di:

- operazioni di elevamento a potenza di numeri che sono potenze di 2, e

operazioni di prodotto di fattori i) che sono entrambi potenze di 2 o ii) di cui almeno uno è una potenza di 2 (ad esempio i prodotti

Tutte queste operazioni sono agevolmente realizzabili tramite semplici operazioni di logica combinatoria e/o di scorrimento (shift) .

Nello schema della figura 3 il riferimento numerico 10 indica nel complesso un circuito di elevamento a potenza realizzato secondo l'invenzione.

Il segnale digitale binario X destinato ad essere sottoposto ad elevamento a potenza (nel caso del presente esempio, elevamento al quadrato) viene applicato sull'ingresso indicato con 11.

Il riferimento 12 indica un commutatore che durante il primo passo del processo iterativo di quadratura si trova nella posizione indicata con 1. Il commutatore 12 passa poi nella posizione indicata con 2 durante i successivi passi del processo iterativo di affinamento del risultato finale.

Il riferimento 13 indica un modulo che, insieme ad un nodo di somma 14 ad esso associato, suddivide il rispettivo segnale di ingresso Zn in una prima parte msb(Zn) che è la potenza di 2 immediatamente inferiore od uguale ad Zn ed una seconda parte Zn - msb(Zn) corrispondente alla differenza tra il rispettivo segnale di ingresso e la suddetta prima parte.

Nel seguito della presente descrizione il simbolo Z indicherà i segnali riconducibili al segnale X, mentre il pedice n indicherà invece il generico passo del processo iterativo di quadratura.

Il modulo 13 determina in pratica la suddetta prima parte di segnale msb(Zn) estraendo il bit più significativo della stringa binaria portata al suo ingresso e mascherando (ossia ponendo a zero) I bit successivi .

Un possibile schema circuitale corrispondente è riportato nella figura 4, dove i riferimenti I e A indicano rispettivamente invertitori logici e porte logiche di tipo AND. I simboli Xn, Xn-i, Xn-2,... e An, An-1, An-2, ... indicano, in ordine a partire dal bit più significativo, i bit del segnale di ingresso e del segnale di uscita del modulo 13.

Il nodo di somma 14 riceve in ingresso - con segni opposti - i segnali presenti all'ingresso (segno positivo) ed all'uscita (segno negativo) del modulo 13 e provvede pertanto a calcolare la suddetta seconda parte di segnale. Poiché msb(Zn) è la potenza di 2 inferiore od uguale a Zn, il relativo valore è espresso da una stringa binaria contenente un solo bit ad "1". La differenza Zn -msb(Zn) può quindi essere determinata ricorrendo ad una rete combinatoria di struttura elementare.

Il riferimento 15 indica un modulo a scorrimento (shifter) di tipo programmabile che riceve in ingresso il segnale di uscita del modulo 13 ed il segnale di uscita del nodo di somma 14 così da calcolare prodotti del tipo 2. (Zn - msb (Zn))-msb (Zn), come - riferendosi agli esempi geometrici fatti in precedenza con riferimento alle figure 1 e 2 - i prodotti 2·(X - A)-A o 2·(X - A - B)-B.

Dato che i fattori A, B - o, in generale msb(Zn) sono potenze di 2, i prodotti in questione possono essere implementati con un semplice scorrimento a sinistra.

All'uscita del modulo 15 si trova un ulteriore nodo di somma 16 che alimenta a sua volta un registro 17 avente associata una linea di ricircolo 171 che riporta verso il nodo di somma 16, secondo una tipica configurazione di somma ed accumulo, il segnale d'uscita del registro 17.

Il riferimento 18 indica un modulo destinato a calcolare la componente del segnale d'uscita Y corrispondente alla somma dei termini msb(Zn)2 , ossia alla somma dei termini che, nel caso dei primi due fattori A2, B2,... identificano le aree dei quadrati in basso a sinistra delle figure 1 e 2.

I termini per calcolare tali quadrati, termini che sono potenze di 2, potrebbero essere desunti dall'uscita del modulo 13.

La forma preferita di attuazione dell'invenzione qui illustrata si basa tuttavia sul riconoscimento della seguente proprietà.

Si supponga che, anche in questo caso, i simboli Xn, Xn-i, Xn-2,..., Xo indichino, in ordine a partire dal bit più significativo, i bit del segnale di ingresso X e, in modo omologo, i simboli Q2n, CQ2n-1..., Q0 indichino, sempre in ordine a partire dal bit più significativo, i bit della somma

Valgono allora le seguenti relazioni:

Questo significa che il calcolo della somma Q implica semplicemente l'inserimento di zeri fra bit adiacenti di X.

Questo fatto può essere agevolmente compreso notando ad esempio che la sommatoria dei quadrati delle potenze di 2 (nell'ordine, 4, 2 e 1) inferiori al numero 7 -numero esprimibile in forma binaria come Olii - è pari a

Tale valore di sommatoria è

esprimibile in forma binaria come 0(0)1 (0)1(0)1, ossia come la stringa 0010101 ottenuta aggiungendo uno 0 a sinistra di ciascuna delle ultime tre cifre della stringa 1000 che esprime il numero 7.

Si apprezzerà che quanto detto in precedenza in relazione alla somma dei quadrati si applica anche alla somma delle potenze di ordine superiore (ad esempio alla somma dei valori al cubo semplicemente aumentando il numero di zeri inseriti fra i bit del valore X.

Sulla base di tale premessa, 1'implementazione del modulo 18 è evidente per l'esperto del settore.

Tornando allo schema della figura 3, con 19 è indicato un ulteriore nodo di somma che riceve in ingresso i segnali di uscita del registro di somma ed accumulo 17 e del modulo 18, producendo alla sua uscita il valore (approssimato o esatto, in funzione del numero di iterazioni svolte) del risultato Y.

Il corrispondente segnale prodotto viene presentato su una linea di uscita indicata con 20.

Il funzionamento del circuito della figura 3 può essere compreso facendo riferimento al diagramma di flusso della figura 5 ed alle indicazioni riportate sui cammini di propagazione dei segnali rappresentati nella figura 3.

Nel passo iniziale di funzionamento (fase 100 nello schema della figura 5) il dato binario X viene portato all'ingresso del circuito 10 sulla linea 11. Il commutatore 12 si trova nella posizione indicata con 1, per cui il valore X viene alimentato tanto all'ingresso del modulo 18 quanto all'ingresso del modulo 13.

Il modulo 18 elabora secondo i criteri sopra descritti la somma (fase 102).

Il modulo 13 calcola nella prima iterazioné di una fase indicata con 104 il valore A = msb (X), mentre nella prima iterazione di una fase indicata con 106, il modulo a scorrimento 15 determina, sfruttando anche il segnale di uscita del nodo di somma 14, il valore Tale valore viene accumulato nel modulo 17 in una fase indicata con 108.

Nel contempo, in una fase indicata con 110, il fattore X-A presente all'uscita del nodo di somma 14 (che identifica l'errore residuo, ossia il lato del quadrato R' nella figura 1) viene rinviato attraverso una linea di riciclo 141 verso il commutatore 13 che si è portato nella posizione indicata con 2.

Viene così avviato il successivo passo del processo iterativo di calcolo.

Alla n-esima iterazione, il processo prevede l'utilizzazione, quale ingresso verso il modulo 13, del segnale :

A questo punto si ripetono le fasi 104, 106 e 108 facendo sì che il modulo a scorrimento 15 determini il valore :

che viene accumulato nel circuito 17 in vista della somma con i segnale di uscita del modulo 18.

La relativa somma, destinata a generare il segnale di uscita presente sulla linea 20, viene realizzata nel nodo 19 durante una fase indicata con 112.

Come già detto in precedenza, il numero dei passi da svolgere nel processo iterativo di calcolo può essere imposto selettivamente dall'esterno del circuito 10, ad esempio tramite un dispositivo di controllo quale un DSP, anche in condizioni di run time.

E' anche possibile arrestare il processo di iterazione monitorando il segnale presente sulla linea di ricircolo indicata con 141 ed interrompendo le iterazioni non appena questo segnale diviene pari a zero, il che indica che sull'uscita è presente un risultato esatto. Questa soluzione appare particolarmente vantaggiosa in termini di riduzione dell'assorbimento di potenza da parte del circuito e di incremento della velocità di calcolo .

All'ottenimento del risultato finale (esatto o approssimato) , il circuito 10 viene resettato in vista dell'alimentazione di un nuovo valore di ingresso X, riportando il commutatore 12 nella posizione 1 ed azzerando il contenuto del registro di accumulo 17.

Si apprezzerà ancora che il meccanismo iterativo di affinamento del risultato appena descritto non coinvolge la somma ., il cui valore viene determinato dal modulo 18 secondo il meccanismo di inserimento di zeri fra bit adiacenti descritto in precedenza .

Ciò risulta particolarmente vantaggioso in termini di rapidità di convergenza verso il risultato finale, in quanto consente di determinare il contributo rappresentato dalla somma Q già dal primo passo del processo di calcolo.

I dati sperimentali elaborati dalla Richiedente dimostrano che la soluzione secondo l'invenzione consente di ottenere risultati particolarmente soddisfacenti con un numero ridotto di iterazioni, quali che siano le caratteristiche del dato di ingresso.

Naturalmente, fermo restando il principio dell'invenzione, i particolari di realizzazione e le forme di attuazione potranno essere ampiamente variati rispetto a quanto descritto ed illustrato, senza per questo uscire dall'ambito della presente invenzione. Ciò vale anche per quanto riguarda l'eventuale presenza, all'ingresso del circuito 10, di elementi in grado di riconoscere particolari valori del dato X tali da consentire eventualmente di aggirare o saltare una o più fasi del procedimento descritto.

Claims (12)

1. RIVENDICAZIONI 1. Circuito di elevamento a potenza (10) per generare, a partire da un segnale digitale binario (X), un segnale di uscita (Y) rappresentativo della k-esima potenza di detto segnale digitale binario (X), caratterizzato dal fatto che comprende: - un modulo di estrazione dì potenza di 2 (13, 14), suscettibile di suddividere un rispettivo segnale di ingresso (Zn) in una prima parte (msb(Zn)) che è la potenza di 2 immediatamente inferiore od uguale a detto rispettivo segnale di ingresso (Zn) ed una seconda parte (Zn - msb(Zn)) corrispondente alla differenza tra detto rispettivo segnale di ingresso e detta prima parte, uno stadio di ingresso (12) suscettibile di applicare detto segnale digitale binario (X) quale detto rispettivo segnale di ingresso a detto un modulo (13, 14) di estrazione di potenza di 2, e - un modulo a scorrimento (15) cooperante con detto modulo di estrazione di potenza di 2 (13, 14) per generare almeno una porzione di detto segnale d'uscita (Y) tramite un'operazione di scorrimento attuata su almeno un segnale desunto da detto segnale digitale binario (X).
2. 2. Circuito secondo la rivendicazione 1, caratterizzato dal fatto che detto modulo a scorrimento (15) attua detta operazione di scorrimento agendo sulla prima parte (A) e sulla seconda parte (X - A) di detto segnale digitale binario.
3. 3. Circuito secondo la rivendicazione 1 o la rivendicazione 2, caratterizzato dal fatto che comprende un modulo circuitale (18) per generare almeno una rispettiva porzione di detto segnale d'uscita (Y) tramite inserimento di zeri fra i bit adiacenti di detto segnale digitale binario (X).
4. 4. Circuito secondo una qualsiasi delle precedenti rivendicazioni, caratterizzato dal fatto che comprende un nodo di somma (19) per generare detto segnale d'uscita come somma di porzioni di segnale (18, 17) rispettivamente corrispondenti: - ad una potenza di detta prima parte (A) di detto segnale binario d'ingresso (X), detta prima parte essendo una potenza di 2, e - al prodotto (A-(X - A)) della prima parte (A) e della seconda parte (X - A) di detto segnale digitale binario (X).
5. 5. Circuito secondo una qualsiasi delle precedenti rivendicazioni, caratterizzato dal fatto che: detto stadio di ingresso (12) ha associato un cammino di ritorno (141) per riportare all'ingresso di detto modulo di estrazione di potenza di 2 (13, 14), secondo un generale schema iterativo comprendente un insieme di passi successivi, quale rispettivo segnale di ingresso (Zn) da utilizzare in un dato passo di detto schema iterativo, la suddetta seconda parte generata in un precedente passo di detto schema iterativo, e - detto modulo a scorrimento (15) ha associato un elemento di accumulo (17) per accumulare detta almeno una prima porzione di detto segnale di uscita generata da detto modulo a scorrimento (19) in successivi passi di detto schema iterativo.
6. 6. Circuito secondo la rivendicazione 4 e la rivendicazione 5, caratterizzato dal fatto che, in ciascuno di detti passi di detto schema iterativo, detto modulo a scorrimento (15) genera una porzione di detto segnale di uscita (Y) da accumulare in detto elemento di accumulo (17), tale porzione da accumulare essendo ottenuta da un segnale (Zn) desunto da detto segnale digitale binario (X).
7. 7. Circuito secondo la rivendicazione 6 caratterizzato dal fatto che detta porzione di segnale di uscita (Y) da accumulare è ottenuta a partire dal prodotto di una prima parte (msb(Zn)) e di una seconda parte di segnale generata da detto almeno un modulo di estrazione di potenza di 2 (13, 14) a partire da detto primo segnale digitale binario (X).
8. 8. Circuito secondo una qualsiasi delle rivendicazioni 5 a 7, caratterizzato dal fatto che sono previsti mezzi per controllare selettivamente il numero dei passi di detto schema iterativo.
9. 9. Circuito secondo la rivendicazione 8, caratterizzato dal fatto che detti mezzi sono sensibili al segnale presente su detto cammino di ritorno (141) ed interrompono lo schema iterativo quando la suddetta seconda parte generata in un precedente passo di detto schema iterativo e suscettibile di essere utilizzata quale rispettivo segnale di ingresso (Zn) in detto dato passo di detto schema iterativo raggiunge valore nullo.
10. 10. Circuito secondo una qualsiasi delle precedenti rivendicazioni, caratterizzato dal fatto che detto modulo di estrazione di potenza di 2 comprende: - un unità (13) che riceve detto rispettivo segnale di ingresso (Zn) e determina da esso come rispettivo segnale d'uscita (msb(Zn)) detta prima parte di segnale che è la potenza di 2 inferiore od uguale a detto rispettivo segnale d'ingresso, e - un nodo di somma (14) che riceve con segni opposti detto rispettivo segnale d'ingresso (Zn) e detto rispettivo segnale d'uscita (msb(Zn)) e determina da essi detta seconda parte di segnale (Zn - msb(Zn)).
11. 11. Circuito secondo una qualsiasi delle precedenti rivendicazioni, caratterizzato dal fatto che detta potenza è la potenza di ordine 2 di detto segnale digitale binario.
12. 12. Circuito di elevamento a potenza (10) per generare, a partire da un segnale digitale binario (X), un segnale di uscita (Y) rappresentativo della k-esima potenza di detto segnale digitale binario (X), caratterizzato dal fatto che comprende un modulo circuitale (18) per generare almeno una rispettiva porzione di detto segnale d'uscita (Y) tramite inserimento di zeri fra i bit adiacenti di detto segnale digitale binario (X).