Un circuito combinatorio, ovvero una rete combinatoria, è un sistema di porte logiche, connesse opportunamente tra loro, organizzato con un insieme di ingressi e un insieme di uscite, nel quale i valori logici delle uscite sono determinati direttamente e univocamente dai valori logici presenti negli ingressi. Il circuito combinatorio si può rappresentare, complessivamente, come una scatola composta da ingressi e da uscite, con una tabella di verità che stabilisce i valori delle uscite in base ai valori degli ingressi.
Quello raffigurato sopra è un esempio di circuito combinatorio con cinque ingressi e tre uscite, ma la proporzione tra quantità di ingressi e quantità di uscite dipende solo dalla funzione che deve realizzare tale circuito, ovvero dallo scopo che con questo ci si prefigge di raggiungere.
Si osservi che un circuito combinatorio, per essere tale, non deve essere influenzato dalla variabile tempo e nemmeno dalla variabile casuale dovuta all'accensione del circuito; pertanto, su tali circuiti non si considera il problema del tempo di propagazione, necessario a far sì che le uscite raggiungano i valori previsti in base ai valori pervenuti in ingresso. |
I circuiti combinatori più semplici sono quelli che dispongono di una sola uscita e realizzano quindi delle porte logiche, più o meno complesse.
|
Per comprendere la questione, si può osservare che un circuito composto da un solo ingresso e da una sola uscita può essere di quattro tipi differenti, come evidenziato dallo schema successivo.
Come si vede dalle annotazioni contenute nello schema, il circuito corrispondente alla funzione f1, coincide con il circuito invertente (ovvero NOT), mentre quello corrispondente alla funzione f2 coincide con il circuito non-invertente.
In un circuito combinatorio con due ingressi e un'uscita, ci sono 16 funzioni possibili, come si vede nello schema successivo, dove si evidenziano in particolare le corrispondenze con le porte logiche comuni, indicate assieme al loro nome standard.
Il decodificatore (decoder) è un circuito combinatorio che attiva una sola uscita, selezionandola in base alla combinazione di valori presenti negli ingressi, tenendo conto per ogni combinazione delle variabili di ingresso deve esserci un'uscita differente da attivare. Pertanto, per n ingressi ci sono 2n uscite. Inoltre, solitamente, tale circuito combinatore è provvisto anche di un ingresso di controllo ulteriore, disattivando il quale si fa in modo che nessuna uscita risulti attiva, indipendentemente dagli altri valori in ingresso.
|
Il demultiplatore (demultiplexer), spesso abbreviato con la sigla demux, svolge un lavoro simile al decodificatore, ma in qualità di commutatore del valore contenuto in un ingresso aggiuntivo.
In questo caso, a differenza del decodificatore, l'uscita yn selezionata riporta lo stesso valore dell'ingresso d.
|
Il demultiplatore può essere ottenuto facilmente da un decodificatore munito di ingresso di abilitazione; in modo analogo, un demultiplatore può essere ridotto a funzionare come un decodificatore.
Il multiplatore (multiplexer), spesso abbreviato con mux, è un circuito combinatorio che seleziona il valore di una sola porta di entrata e lo riproduce nell'uscita. La selezione della porta di entrata dipende dalla combinazione di valori contenuta in un insieme di porte di selezione. Per n porte di selezione si può scegliere tra 2n porte di entrata.
|
Quando i demultiplatori o i multiplatori vengono usati per commutare dati composti da più bit e quindi trasportati da più linee, servono tanti demultiplatori o multiplatori quanti sono tali bit, mettendo però assieme tutti gli ingressi di selezione e di abilitazione. Tuttavia, nel disegno di un circuito tali linee multiple si annotato in forma compatta. Le figure successive mostrano un demultiplatore e un multiplatore che trattano dati a quattro bit.
Un codificatore binario (binary encoder è un circuito combinatorio nei cui ingressi ci può essere una sola linea attiva e ha lo scopo di tradurre l'ingresso selezionato in un numero binario nelle uscite. In pratica, si tratta generalmente di 2n ingressi e di n uscite. Vengono mostrati esempi di codificatori con n pari a 1, 2 e 3.
|
|
|
|
|
Il codificatore di priorità (priority encoder) è un codificatore binario che ammette l'attivazione di qualunque ingresso, emettendo il numero corrispondente all'ingresso attivo avente priorità rispetto agli altri. In questo caso è ammissibile anche il fatto che nessun ingresso sia attivo, pertanto, può essere presente un'uscita aggiuntiva che si attiva quando in ingresso c'è almeno un valore attivo.
|
Con l'ausilio di un multiplatore è possibile ottenere facilmente un'unità logica, in grado di eseguire le operazioni logiche comuni, scegliendo quella desiderata attraverso un valore di selezione. Per esempio, si potrebbe realizzare un circuito che svolge il compito schematizzato in questo disegno:
|
Le unità logiche di questo tipo sono utili se si applicano a coppie di ingressi che dispongono, ciascuno, di più bit. Per ottenere questo risultato basta abbinare delle unità semplici, a una sola uscita.
Un tipo di operazione molto importante che si può realizzare con dei circuiti combinatori, è lo scorrimento dei bit. In pratica si ha un gruppo di n ingressi ordinati, da 0 a n-1, un gruppo di n uscite, ordinate nello stesso modo; eventualmente ci può essere un riporto in ingresso e uno in uscita. Spesso si considera lo spostamento di una sola unità, perché si possono ottenere spostamenti di più unità ripetendo la stessa operazione ciclicamente.
Il tipo più semplice di scorrimento è quello logico, nel quale lo spostamento a destra fa inserire uno zero nella posizione più significativa, mentre quello a sinistra lo fa entrare dalla parte destra. Nelle figure successive, per ottenere il valore zero si vede semplicemente un collegamento a massa, la quale si intende essere implicitamente al potenziale corrispondente allo zero.
|
Lo scorrimento aritmetico avviene come lo scorrimento logico, con la differenza che lo scorrimento a destra deve mantenere inalterato il segno. In pratica, nello scorrimento a destra di tipo aritmetico, la cifra che viene immessa nella posizione più significativa, è la copia di quella che era originariamente in quella posizione. Lo scorrimento aritmetico si chiama così perché corrisponde alla moltiplicazione o alla divisione per due (la base di numerazione); va però osservato che lo scorrimento a sinistra può provocare un'inversione indesiderata di segno.
Lo scorrimento circolare comporta il recupero della cifra che fuoriesce da una parte, dal lato opposto, sia nello scorrimento a sinistra, sia in quello a destra.
Lo scorrimento circolare con riporto, utilizza il riporto preesistente per la cifra da immettere, da un lato o dall'altro, mentre mette nel riporto in uscita la cifra che viene espulsa.
L'addizione in binario, eseguita con la stessa procedura consueta per il sistema di numerazione decimale, non genera mai un riporto superiore a uno. Lo si può verificare facilmente attraverso la tabella successiva.
|
Pertanto, il circuito combinatorio che può svolgere questo lavoro deve avere tre ingressi (primo addendo, secondo addendo, riporto preesistente) e due uscite (risultato e riporto generato). Di solito si usa la lettera c (carry) per indicare un riporto; in questo caso si distingue tra riporto in ingresso (ci) e riporto in uscita (co).
Si considera tradizionalmente che l'addizionatore completo (quello che si vede nello schema appena mostrato) sia costituito da due moduli più piccoli, noti come semiaddizionatori, ovvero half adder. Il semiaddizionatore è un circuito combinatorio con due ingressi, a e b, corrispondenti alle variabili da sommare, e due uscite, s e c, corrispondenti al risultato della somma e al suo riporto.
|
Si può intuire facilmente che, nel semiaddizionatore, l'uscita s si ottenga con una porta XOR e che il riporto si ottenga con una porta AND.
|
Per arrivare a ottenere l'addizionatore completo, occorre sommare anche il riporto precedente.
Perché l'addizionatore sia utile, è necessario che intervenga su un numero binario composto da diverse cifre, pertanto occorre assemblare in parallelo più addizionatori, passando opportunamente il riporto, dalla cifra meno significativa a quella più significativa, una cifra alla volta.
Il circuito dell'addizionatore descritto, opera correttamente per la somma di numeri positivi o negativi, quando i numeri negativi si rappresentano attraverso la tecnica del complemento a due.
Il complemento a due che serve a trasformare il sottraendo, si ottiene con il complemento a uno del suo valore, sommandogli una unità attraverso il riporto in ingresso. |
Per la sottrazione, si parte, anche in questo caso, dal semi-sottrattore, ovvero half subtractor. Trattandosi di una sottrazione, è necessario distinguere tra gli operandi il minuendo e il sottraendo; in pratica, negli esempi vengono usate queste variabili: d=m-s.
|
Al posto del riporto c'è un'uscita denominata borrow che rappresenta la richiesta del prestito di una cifra. Questa uscita diventa attiva quando il minuendo è pari a zero, mentre il sottraendo è pari a uno; ovvero quando il sottraendo è maggiore del minuendo. Il sottrattore completo ha un ingresso in più, costituito dalla richiesta di una cifra proveniente dallo stadio precedente; per gestire questo nuovo ingresso si possono usare due semisottrattori, dove il secondo sottrae al risultato del primo la richiesta di prestito.
|
Come nel caso della somma, si possono creare delle catene di sottrattori completi; tuttavia, nel confronto con il circuito della somma, modificato per effettuare la sottrazione, la linea borrow (quella della richiesta del prestito), funziona in modo inverso, in quanto se attiva, rappresenta una cifra da togliere.
Il circuito dell'addizionatore opera correttamente per la somma di numeri positivi o negativi, quando i numeri negativi si rappresentano attraverso la tecnica del complemento a due; pertanto, per trasformare l'addizionatore in un circuito che invece sottrae uno dei due operandi, è sufficiente calcolare per quello il complemento a due e per ottenerlo si devono invertire tutti gli ingressi, compreso il riporto. Va ricordato che nella sottrazione, il riporto assume il significato della richiesta di una cifra.
Eventualmente, si trasforma facilmente il circuito combinatorio in un complesso unico, in grado di sommare o di sottrarre, sfruttando una porta XOR al posto della porta NOT, aggiungendo un ingresso ulteriore che permetta di stabilire se si esegue una somma o se l'operando stabilito va invece sottratto.
Nella somma di una quantità significativa di bit, la propagazione del riporto richiede un tempo relativamente elevato, dato che la somma di una certa cifra è corretta solo se è già avvenuta la somma di quelle che la precedono. Per poter accelerare l'esecuzione della somma, è necessario che per ogni cifra si possa sapere, nel tempo più breve possibile, qual è il riporto generato fino allo stadio precedente. Nelle espressioni successive, le variabili Ai, Bi e Ci, rappresentano i due addendi e il riporto in ingresso dello stadio i; pertanto, il riporto generato da questo stadio è rappresentato dalla variabile Ci+1.
Nella figura si vede che il riporto si può sintetizzare in vari modi e in uno di questi appare anche l'uso dell'operatore XOR. Di quelle mostrate nella figura si scelgono due espressioni equivalenti:
|
Da queste espressioni, si dichiarano due variabili nuove, Gi e Pi, le quali stanno rispettivamente per «generazione» e «propagazione», per cui si definisce che il riporto Ci+1 è prodotto come funzione delle variabili Gi, Pi e Ci.
|
È evidente che Gi equivale a AiBi, mentre Pi può essere considerata pari a Ai+Bi oppure Ai⊕Bi, indifferentemente. Se il primo riporto generato (C1) si può ottenere come C1=G0+P0C0, il secondo si ottiene come C2=G1+P1(G0+C0P0), e di conseguenza si può proseguire per determinare i riporti successivi. Vengono mostrate le soluzioni per i primi quattro riporti:
|
Per semplificare le espressioni, si definiscono Pn e Gn nel modo seguente:
|
Avendo definito ciò, il riporto Cn si può definire come:
|
La figura successiva, mostra un circuito combinatorio che determina i riporti di quattro cifre binarie, partendo dal riporto iniziale e dai valori di B3..0 e G3..0, come descritto dalle equazioni che definiscono questa relazione. Il disegno contiene anche la logica necessaria a determinare il valore di B4 e G4 che possono servire per collegare assieme più moduli di questo tipo.
Avendo la necessità di disporre delle uscite G e P, si può sintetizzare un modulo per l'addizione privo della funzione che determina il riporto in uscita, dal momento che questo compito viene affidato al modulo che si vede nella figura precedente. Ci sono due soluzioni alternative, nelle quali il valore di P viene determinato nei due modi diversi già descritti con le tabelle di Karnaugh.
La figura successiva mostra un addizionatore a quattro cifre, dove si utilizzano i moduli di addizione e di determinazione del riporto già apparsi.
È possibile collegare assieme i moduli mostrati, quando non si può disporre in partenza della quantità di cifre che servono. Questo collegamento comporta un aumento del ritardo di propagazione, ma si tratta comunque di un grande miglioramento rispetto al calcolo del riporto in cascata, come mostrato nelle sezioni precedenti. Nella figura successiva, il modulo SUM4 corrisponde allo schema di figura u126.58, dal quale si prelevano solo l'ultimo e il penultimo riporto (perché in sezioni successive viene mostrato che questi due consentono di determinare la presenza di uno straripamento); invece, il modulo CLH4 corrisponde allo schema di figura u126.56, il quale viene usato per mettere assieme i moduli di addizione.
Se si ha la necessità di invertire il segno di un numero intero, rappresentato in forma binaria, c'è bisogno di costruire un circuito che esegua il complemento a uno, invertendo le cifre binarie, sommando poi una unità per trovare il complemento a due.
L'esempio proposto nella figura mostra che il dato in ingresso, viene invertito (negato) se risulta attivo il segnale minus, ma lo stesso segnale minus viene sommato, producendo alla fine il complemento a due. Se invece il segnale minus non fosse attivo, il dato in ingresso non verrebbe alterato e non ci sarebbe l'incremento di un'unità, per cui il risultato sarebbe lo stesso, senza variazione.
La moltiplicazione binaria è un procedimento che richiede la somma e lo scorrimento. Per poter tenere conto del segno, il calcolo andrebbe fatto come se si operasse su una quantità doppia di cifre; per esempio, se moltiplicatore e moltiplicando sono di sole quattro cifre binarie, il risultato deve poter essere di otto cifre e il calcolo andrebbe fatto come se anche gli operandi fossero di questo rango. Si osservino gli esempi che appaiono nella figura successiva.
Nella figura, l'esempio di sinistra mostra la moltiplicazione tra 11 e 13; trattandosi di numeri privi di segno, vanno aggiungi degli zeri nelle posizioni più significative e di conseguenza va svolta la moltiplicazione. Nel secondo esempio, i numeri vanno intesi con segno e si tratta della moltiplicazione tra -5 e +5; in questo caso, il numero che viene inteso come negativo, deve essere completato con cifre a uno, per mantenere il segno negativo, e di conseguenza la moltiplicazione ne tiene conto. Nel terzo esempio è il moltiplicatore a essere negativo: 7·-3. In tal caso è il moltiplicatore che viene completato con le cifre a uno nella parte più significativa, condizionando di conseguenza il calcolo della moltiplicazione. L'ultimo esempio è uguale al primo, con la differenza che i due valori sono intesi con segno, pertanto sono completati con cifre a uno. In conclusione, la moltiplicazione deve tenere conto del fatto che i numeri siano con segno o senza; nel caso lo siano, devono essere estesi nella porzione più significativa con la cifra necessaria a mantenere il segno che hanno.
Per risolvere il problema in forma di circuito combinatorio, occorre incrociare i valori di moltiplicando e moltiplicatore, verificando in ogni posizione utile la coincidenza di valori a uno. I due disegni successivi vanno sovrapposti idealmente, in quanto mostrano il concetto in due fasi: le uscite delle porte AND devono essere sommate verticalmente per generare il prodotto.
Per mettere assieme la moltiplicazione, svolta dall'operatore AND, e la somma, occorre costruire delle celle apposite, utilizzano un addizionatore completo. Come si vede dalla figura, uno degli addendi riceve il risultato del prodotto ottenuto con l'operatore AND, mentre l'altro addendo riporta il valore proveniente dalla riga superiore.
Le celle della figura vanno connesse per costruire le somme che costituiscono la moltiplicazione. La figura successiva mostra una soluzione limitata al caso di numeri privi di segno.
Per risolvere il problema dei valori con segno, occorre un ingresso aggiuntivo, per comunicare il fatto che si stia usando o meno numeri con segno, quindi occorrerebbe estendere la maglia come se si moltiplicassero valori con un numero doppio di cifre, estese secondo il segno che viene loro attribuito.
Si può risolvere il problema della moltiplicazione quando si hanno valori con segno, adattare un circuito moltiplicatore di valori privi di segno, provvedendo a calcolare il complemento a due (ovvero a cambiare di segno) quando i valori risultano essere negativi. Nello schema della figura successiva, la funzione mul4 corrisponde a un circuito moltiplicatore che opera solo su valori privi di segno; minus4 e minus8 sono circuiti che si occupano di invertire il segno se l'ingresso minus risulta attivo.
Nella figura si vede che dagli ingressi a e b, viene prelevato il bit più significativo, per determinare se i valori rispettivi sono negativi; se lo sono, i loro valori vengono moltiplicati per -1, prima di passare alla moltiplicazione; al termine, il risultato viene moltiplicato per -1 solo se i segni di a e b sono diversi. Naturalmente, tutto questo è subordinato al fatto che venga richiesto un calcolo che tenga conto dei segni, attraverso l'ingresso signd. Il circuito denominato minus4 corrisponde a quanto mostrato nella sezione u0.13; naturalmente, minus8 è solo un'estensione dello stesso a 8 bit.
Se invece si riduce il risultato della moltiplicazione a una quantità di cifre uguale a quelle di moltiplicando e di moltiplicatore, ammesso che il risultato non venga troncato, ciò che si ottiene è valido, indipendentemente dai segni, senza bisogno di dover comunicare la gestione dei segni al circuito. Si mostra nuovamente un esempio di calcolo della moltiplicazione, simile a quello iniziale, per dimostrare questa affermazione.
La divisione richiede la sottrazione e lo scorrimento, come si può vedere dall'esempio successivo, in cui il divisore viene confrontato con il dividendo, partendo dalle cifre più significative, sottraendo il divisore al dividendo solo quando ciò è possibile. In tal modo, il risultato intero della divisione è dato dal successo o meno di tali sottrazioni, mentre il resto è ciò che rimane dopo tutte le sottrazioni.
Per risolvere il problema attraverso un circuito combinatorio, si possono usare dei moduli per la sottrazione completa, da integrare con un controllo sul risultato, il quale deve essere prodotto solo se la sottrazione è ammissibile, altrimenti va riproposto il valore originale anche in uscita. Come nel caso della moltiplicazione, si possono costruire delle celle apposite.
Con queste celle, dopo ogni sottrazione, si ottiene l'informazione se c'è la richiesta di un prestito o meno, dall'uscita bo (borrow out: se c'è tale richiesta di prestito, significa che la sottrazione non può avere luogo, quindi, tale segnale viene invertito e usato per avvisare tutte le celle di una fila che devono riproporre il valore originale anche in uscita, rinunciando alla sottrazione.
La divisione è complicata al riguardo della gestione dei valori con segno. Si pongono i casi seguenti, con cui stabilire il segno che devono avere i risultati:
|
Per risolvere il problema della divisione di valori con segno, conviene aggiungere a ciò che divide valori senza segno, un controllo che inverta opportunamente i segni di dividendo, divisore, quoziente e resto, quando necessario.
La comparazione tra due valori espressi in forma binaria, richiede il confronto, bit per bit, partendo dalla cifra più significativa. Da ogni confronto bit per bit, occorre sapere se sono uguali o se uno dei due sia maggiore. La figura successiva mostra la realizzazione di questo confronto tra due soli valori logici.
Nel confronto tra più bit, si fanno le stesse verifiche a coppia, facendo prevalere la prima differenza a partire dal bit più significativo.
«a2» 2013.11.11 --- Copyright © Daniele Giacomini -- appunti2@gmail.com http://informaticalibera.net