Scopo di questo capitolo é di arrivare il più rapidamente possibile alla definizione e comprensione dei circuiti combinatori fondamentali (Multiplexer, Demultiplexer, Sommatori, ALU, ecc.) usati come blocchi costruttivi per la realizzazione di microarchitetture. La comprensione dei circuiti combinatori é anche precondizione essenziale per lo studio dei circuiti sequenziali (registri, memorie, ecc.) usati come blocchi costruttivi per la realizzazione di microarchitetture.
La trattazione parte a livello di definizione di funzioni Booleane,
e non richiede particolari prerequisiti per la comprensione oltre ad un
minimo di dimestichezza con le notazioni matematica ed algebrica.
In particolare non si esaminano i problemi di realizzazione fisica dei
dispositivi (se non quelli legati alla risposta nel tempo ed ai ritardi)
che richiederebbero nozioni di base di elettronica.
D'ora in avanti tratteremo informazioni di tipo Booleano, ossia caratterizzate da due soli valori possibili, che indicheremo per brevità coi simboli "0" e "1". In particolare cominceremo a definire una Macchina Astratta Booleana rappresentata come una scatola nera (ossia una scatola di cui non conosciamo il contenuto, ma di cui possiamo solo osservare le interazioni con l'ambiente in cui viene posta) composta da N ingressi ed M uscite di tipo booleano come rappresentato in figura:
In particolare, definiamo una Macchina Booleana Combinatoria una scatola nera tale per cui i valori di una qualunque uscita uj possono essere definiti come una funzione degli N ingressi, ossia uj=fj(i0,i1,...iN-1). Vediamo quindi come per definire il comportamento di una tale macchina combinatoria sia sufficiente studiare le funzioni Booleane di N variabili.
Cominciamo a considerare il caso più semplice di N=1. Avremo quindi a che fare con funzioni booleane di una sola variabile del tipo u=f(i) (omettiamo l'indice 0 per brevità). La cosa particolarmente interessante da notare é che sia la variabile di ingresso i che la variabile di uscita u possono assumere solo i due valori 0 oppure 1. Possiamo quindi esaurire la nostra analisi elencando semplicemente tutte le funzioni diverse una dall'altra che possiamo immaginare di scrivere:
fa: i | u fb: i | u fc: i | u fd: i | u
--+-- --+-- --+-- --+--
0 | 0 0 | 0 0 | 1 0 | 1
1 | 0 1 | 1 1 | 0 1 | 1
La cosa più interessante da osservare é che le funzioni
possibili sono solo le 4 riportate.
La prima e l'ultima (fa e fd) sono costanti (ossia il valore
in uscita é costante, indipendentemente dal valore in ingresso).
La seconda funzione (fb) é l'identità
(ossia il valore in uscita é identico al valore in ingresso), quindi
non particolarmente utile per la realizzazione di sistemi di calcolo.
La terza funzione (fc) é l'unica funzione booleana di una variabile
"interessante" dal nostro punto di vista: la chiameremo funzione
negazione, visto che il valore in uscita é sempre il valore
opposto rispetto a quello in ingresso.
Passiamo ora a considerare il caso di N=2. Avremo quindi a che fare con funzioni booleane di due variabili del tipo u=f(i0,i1). Anche in questo caso, a causa del numero finito di valori che possono assumere i due ingressi e l'uscita il numero di funzioni diverse é finito (uguale a 16):
fe: i1 i0 | u fg: i1 i0 | u fh: i1 i0 | u fj: i1 i0 | u
------+-- ------+-- ------+-- ------+--
0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0
0 1 | 0 0 1 | 0 0 1 | 0 0 1 | 0
1 0 | 0 1 0 | 0 1 0 | 1 1 0 | 1
1 1 | 0 1 1 | 1 1 1 | 0 1 1 | 1
fk: i1 i0 | u fl: i1 i0 | u fm: i1 i0 | u fn: i1 i0 | u
------+-- ------+-- ------+-- ------+--
0 0 | 0 0 0 | 0 0 0 | 0 0 0 | 0
0 1 | 1 0 1 | 1 0 1 | 1 0 1 | 1
1 0 | 0 1 0 | 0 1 0 | 1 1 0 | 1
1 1 | 0 1 1 | 1 1 1 | 0 1 1 | 1
fo: i1 i0 | u fp: i1 i0 | u fq: i1 i0 | u fr: i1 i0 | u
------+-- ------+-- ------+-- ------+--
0 0 | 1 0 0 | 1 0 0 | 1 0 0 | 1
0 1 | 0 0 1 | 0 0 1 | 0 0 1 | 0
1 0 | 0 1 0 | 0 1 0 | 1 1 0 | 1
1 1 | 0 1 1 | 1 1 1 | 0 1 1 | 1
fs: i1 i0 | u ft: i1 i0 | u fv: i1 i0 | u fw: i1 i0 | u
------+-- ------+-- ------+-- ------+--
0 0 | 1 0 0 | 1 0 0 | 1 0 0 | 1
0 1 | 1 0 1 | 1 0 1 | 1 0 1 | 1
1 0 | 0 1 0 | 0 1 0 | 1 1 0 | 1
1 1 | 0 1 1 | 1 1 1 | 0 1 1 | 1
Al solito, molte di queste 16 funzioni non sono interessanti: la prima (fe) e l'ultima (fw) sono costanti, ossia specificano una uscita indipendente dai valori di ingresso; la quarta (fj) e la sesta (fl) sono funzioni identità su una sola delle variabili di ingresso; la undicesima (fq) e la tredicesima (fs) sono funzioni negazione su una sola delle variabili in ingresso.
Le rimanenti 10 funzioni sono invece non banali. La seconda (fg) viene chiamata funzione and, la settima (fm) viene chiamata funzione or esclusivo (XOR), l'ottava (fn) viene chiamata funzione or inclusivo (OR). La loro importanza giustifica l'introduzione di una particolare simbologia per la rappresentazione grafica:
I tre simboli grafici vengono definiti come la rappresentazione delle suddette tre funzioni (indipendentemente da come queste funzioni sono realizzate in termini di circuiti elettronici).
La quindicesima (fv), la decima (fp) e la nona (fo) costituiscono la negazione delle tre funzioni base, e vengono chiamate rispettivamente NAND, XNOR e NOR, e rappresentate graficamente come illustrato in figura:
Nella figura é riportato anche il simbolo usato per la rappresentazione della funzione negazione (NOT) di una variabile. In generale si usa la regola di aggiungere un "pallino" alla connessione di un filo di ingresso oppure di uscita al simbolo che rappresenta una data funzione logica per rappresentare in forma compatta la negazione del valore.
Quanto alle rimanenti 4 funzioni (fh, fk, fr ed ft), possono essere interpretate come predicati di confronto tra i due valori di ingresso: interpretando il valore 1 in uscita come "vero" ed il valore 0 in uscita come "falso", tali funzioni definiscono i predicati (i1>i0), (i1<i0), (i1>=i0) e (i1<=i0). Normalmente non vengono introdotti ulteriori simboli per la rappresentazione grafica di queste funzioni.
In generale, per ogni N finito il numero di funzioni booleane di N variabili é finito e uguale a 2**(2**N). In linea di principio possiamo pensare di costruire tutte le tabelle di 2**N righe ed N+1 colonne (storicamente chiamate Tavole di Verità) che definiscono tutte queste funzioni.
Tuttavia, al crescere del numero delle variabili il metodo di studio mediante le tavole di verità diventa impraticabile (a causa delle dimensioni delle tabelle), per cui si preferisce far ricorso a tecniche algebriche per il trattamento manuale. Per il trattamento automatico (mediante strumenti software di supporto) si fa invece uso di strutture dati per la rappresentazione di funzioni chiamate Binary Decision Diagrams (BDD) .
La definizione delle funzioni base (And, Or, Xor) e delle loro negazioni (Nand, Nor, Xnor) viene estesa anche al caso di più di due variabili booleane di ingresso. Per questa estensione si sfrutta la proprietà matematica di commutatività delle funzioni base di due variabili (che può essere "dimostrata" in modo banale scambiando i valori delle due colonne che rappresentano gli ingressi nelle rispettive tavole di verità e poi permutando le righe, in modo da riottenere la stessa tabella di partenza). Viene in oltre assunta la proprietà associativa per la versione delle funzioni con più di due variabili.
Per esempio, la funzione And a quattro ingressi può essere definita come and4(i0,i1,i2,i3)=fg(fg(i0,i1),fg(i2,i3)). Tale composizione viene rappresentata graficamente come in figura:
Analoga estensione viene fatta per le altre funzioni logiche base.
I due valori 0 e 1, insieme con la funzione unaria Not (indicata col simbolo "¬" nelle formule) e le due funzioni binarie And e Or (indicate rispettivamente con i simboli "·" e "+" nelle formule) formano una struttura algebrica di tipo particolare, detta algebra binaria di commutazione.
Dalla definizione delle funzioni mediante tavola di verità riportate nella sezione precedente, risulta infatti semplice dimostrare le seguenti proprietà (indichiamo con a, b, c, ecc. qualunque valore booleano):
Notare che le proprietà sono state elencate in un ordine ben particolare:
ogni riga di ordine pari può essere scritta prendendo la riga dispari
immediatamente precedente e scambiando tra loro tutti i simboli di somma e
prodotto (ossia ogni somma viene sostituita da un prodotto e viceversa) ed i
simboli 0 e 1 (ossia ogni 0 viene sostituito da 1 e viceversa).
Questo evidenzia la proprietà di dualità
dell'algebra di commutazione: una volta dimostrata una qualsiasi proprietà,
allora possiamo sicuramente ritenere valida anche la proprietà duale,
ottenuta scambiando i simboli di somma e prodotto e negando le costanti
0 e 1.
Osservare tuttavia che una formula in generale
Combinando opportunamente queste proprietà di base per la definizione della struttura algebrica, possiamo arrivare a dimostrare altre proprietà interessanti (insieme alla loro formulazione duale), come per esempio:
L'insieme di queste proprietà ci permette di sostituire delle formule
complesse con altre formule equivalenti più semplici
(e quindi meglio comprensibili e maneggiabili).
Tecniche di semplificazione delle formule booleane che mantengano l'equivalenza
della funzione che definisce i valori di uscita in funzione dei valori
in ingresso assumono una particolare rilevanza quando si affronta il
problema della realizzazione di dispositivi fisici
per il calcolo di tali funzioni.
Abbiamo già visto due forme diverse per la rappresentazione di funzioni booleane: le tavole di verità e le formule algebriche basate sulle funzioni elementari And, Or e Not. Anzitutto vediamo come si può stabilire l'equivalenza tra queste due rappresentazioni, introducendo le formule normali disgiuntive. Successivamente introdurremo due ulteriori rappresentazioni usate in pratica (le mappe di Karnaugh e i Binary Decision Diagrams), mostrando anche per questi l'equivalenza concettuale con la rappresentazione mediante tavole di verità.
Costituiscono la rappresentazione di riferimento concettuale per la definizione delle funzioni booleane.
Dal punto di vista pratico, l'uso é limitato al caso di poche variabili di ingresso (max 5 o 6) a causa della crescita di dimensione del numero di righe.
Una tavola di verità viene detta in forma canonica quando le righe sono ordinate per valori crescenti degli ingressi, interpretando i valori delle variabili di ingresso come cifre di una codifica binaria.
Una formula booleana viene detta in forma normale disgiuntiva quando é formata da una sommatoria di termini, ciascuno dei quali costituito da una produttoria di letterali costituiti da nomi di variabili di ingresso oppure da negazioni di nomi di variabili di ingresso.
La formula viene detta minimale quando, applicando le proprietà algebriche di equivalenza, non é possibile ottenere una formula normale disgiuntiva equivalente contenente un numero inferiore di letterali.
Data una tavola di verità in forma canonica, scandire tutte le righe partendo dalla prima.
Per ogni riga, osservare il valore specificato per l'uscita: se é 0, allora passare alla riga seguente senza far nulla; se invece il valore specificato é 1, allora scrivere un termine da aggiungere ai termini gia scritti in precedenza composto dal prodotto di tutte le variabili di ingresso che assumono il valore 1 e della negazione di tutte le variabili di ingresso che assumono il valore 0.
Esempio: considerare la seguente tavola di verità che definisce una funzione di 3 variabili di ingresso
i0 i1 i2 | u
---------+--
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 1
1 0 1 | 0
1 1 0 | 1
1 1 1 | 1
L'algoritmo di traduzione produce quindi la somma di 4 termini (corrispondenti alle righe 4, 5, 7 e 8 della tavola):
u = ((¬i0)·i1·i2) + (i0·(¬i1)·(¬i2)) + (i0·i1·(¬i2)) + (i0·i1·i2)
A questa formula corrisponde la seguente rappresentazione grafica:
Notare che tale rappresentazione normale non é minimale. Per esempio, applicando alcune delle proprietà algebriche di trasformazione delle formule é possibile riscrivere la stessa funzione nella forma normale (più compatta):
u = (i1·i2) + (i0·(¬i2))
Tale formula non é ulteriormente trasformabile in un'altra formula normale disgiuntiva più semplice, quindi viene detta forma normale disgiuntiva minimale per la funzione considerata. La sua rappresentazione grafica risulta semplificata di conseguenza:
Esistono algoritmi per la costruzione della forma minimale, ma noi non ci soffermeremo su questo aspetto (ormai obsoleto a causa dell'uso di strumenti software per la rappresentazione di funzioni booleane).
L'algoritmo consiste nell'elencare tutte le configurazioni possibili in ingresso (in ordine crescente di valore, quando l'insieme degli ingressi viene interpretato come codifica binaria di numeri naturali). Per ogni configurazione di ingresso, valutare i valori di uscita delle funzioni elementari Not, And e Or che compongono l'espressione. L'uscita della funzione Or rappresenta il valore da inserire nella corrispondente riga della tavola di verità che si sta costruendo.
Con questo abbiamo dimostrato la perfetta equivalenza tra queste due forme di rappresentazione (in quanto ciascuna può essere tradotta automaticamente nell'altra, e viceversa.
Applicando il principio di dualità all'algoritmo di traduzione da tavola di verità a formula in forma normale disgiuntiva, si può arrivare a produrre una formula del tipo "prodotto di sommatorie di termini", detto rappresentazione in forma normale congiuntiva. In particolare si ottiene l'algoritmo:
Data una tavola di verità in forma canonica, scandire tutte le righe partendo dalla prima.
Per ogni riga, osservare il valore specificato per l'uscita: se é 1, allora passare alla riga seguente senza far nulla; se invece il valore specificato é 0, allora scrivere un termine da moltiplicare per i termini già scritti in precedenza composto dalla somma di tutte le variabili di ingresso che assumono il valore 0 e della negazione di tutte le variabili di ingresso che assumono il valore 1.
La forma normale disgiuntiva può essere immediatamente tradotta nella rappresentazione mediante funzioni logiche elementari Not And Or detta a tre livelli (perché seguendo un qualsiasi percorso da una variabile di ingresso all'uscita si possono incontrare al più tre simboli rappresentanti una funzione Not, una funzione And e una funzione Or). Analogamente, una formula in forma normale congiuntiva può essere immediatamente tradotta nella rappresentazione mediante funzioni logiche elementari Not Or And a tre livelli.
Sfruttando le proprietà di De Morgan é poi possibile trasformare la funzione Or finale in una funzione Nand preceduta da ulteriori funzioni Not. Inglobando poi queste funzioni Not aggiuntive nel livello And precedente (che viene quindi trasformato in un livello Nand), si può passare ad una realizzazione in logica a 3 livelli di solo tipo Nand (anche le funzioni Not del primo livello possono essere viste come funzioni Nand con un solo ingresso).
In questo senso, la funzione Nand (ma lo stesso ragionamento può essere ripetuto anche per la funzione Nor, partendo da una realizzazione a tre livelli del tipo Not Or And derivante da una formula normale congiuntiva) é una funzione universale, in quanto la combinazione di funzioni Nand consente di realizzare qualsiasi altra funzione booleana (rappresentata da una qualunque tavola di verità). Questa considerazione ha un impatto profondo e positivo sulla realizzazione dei circuiti combinatori. Noi non ci occuperemo qui di studiare come una singola funzione elementare (And, Or, Not, ecc.) possa essere realizzata mediante dispositivi fisici, ma ci limitiamo a sottolineare l'importanza che può avere dal punto di vista della semplicità e dell'economia di realizzazione dei dispositivi il fatto di potersi sempre ricondurre ad un unico componente universale (Nor oppure Nand).
Sempre dal punto di vista realizzativo, occorre poi notare che la tecnologia elettronica permette di realizzare funzioni di tipo Nand (o Nor) con numero di ingressi anche molto elevato praticamente nello stesso modo e con le stesse caratteristiche delle funzioni a due soli ingressi. Ciò rende particolarmente appetibile la forma di realizzazione in logica a 3 livelli derivante dalla specifica di una funzione in forma normale disgiuntiva (o congiuntiva). Infatti, la realizzazione fisica dei dispositivi induce comunque dei ritardi nel calcolo delle funzioni a seguito di variazioni dei valori in ingresso. Nel caso di realizzazione in logica a 3 livelli, il ritardo massimo per ottenere il risultato corretto in uscita dopo aver cambiato i valori di ingresso sarà comunque pari a tre volte il ritardo del componente universale Nand (o Nor), indipendentemente dalla complessità della funzione e dal numero di variabili in ingresso.
Furono originariamente introdotte come rappresentazione alternativa alla tavola di verità per supportare meglio un algoritmo di traduzione in formula normale disgiuntiva minimale. Noi non ci soffermeremo molto sull'uso delle mappe per l'identificazione di tale forma minimale, ma ci limiteremo prevalentemente ad utilizzarle come rappresentazione alternativa più compatta della tavola di verità.
L'idea base consiste nell'usare uno spazio bidimensionale per la rappresentazione delle configurazioni di ingresso, anziché monodimensionale come nel caso della tavola di verità. L'insieme delle variabili di ingresso viene partizionato in due sottoinsiemi (di dimensioni il più possibile bilanciate). Un sottoinsieme viene usato per definire una coordinata orizzontale mentre l'altro insieme viene usato per definire una coordinata verticale. La coppia di coordinate individua una casella nella quale viene scritto il valore di uscita della funzione.
Esempio: la mappa di Karnaugh equivalente alla tavola di verità della funzione usata in precedenza risulta essere:
\ i2 | 0 : 1 |
i0 i1 \ | : |
--------\--+-----:-----+
0 0 | 0 : 0 |
..........|.....:.....|
0 1 | 0 : 1 |
..........|.....:.....|
1 0 | 1 : 0 |
..........|.....:.....|
1 1 | 1 : 1 |
-----------+-----:-----+
In questo caso abbiamo scelto la coppia di ingressi i0 e i1 per comporre
la coordinata verticale (che identifica una riga tra 4) e l'ingresso i2
per determinare la coordinata orizzontale (che identifica una colonna tra 2).
Nel caso si voglia utilizzare la rappresentazione per ricavare una formula algebrica minimale, normalmente si fa ricorso ad un ordinamento delle combinazioni di valori per le variabili di ingresso diverso dall'ordine lessicografico usato per convenzione nelle Tavole di Verità. Risulta infatti piu' conveniente un ordinamento secondo il cosiddetto "Codice Gray", che é caratterizzato dalla proprietà di avere sempre distanza di Hamming unitaria tra codifiche adiacenti. Nel nostro esempio l'uso dell'ordinamento secondo il codice Gray ci porterebbe a scrivere la tabella come:
\ i2 | 0 : 1 |
i0 i1 \ | : |
--------\--+-----:-----+
0 0 | 0 : 0 |
..........|.....:.....|
0 1 | 0 : 1 |
..........|.....:.....|
1 1 | 1 : 1 |
..........|.....:.....|
1 0 | 1 : 0 |
-----------+-----:-----+
Questa proprietà permette di stabilire una relazione diretta tra
l'adiacenza "grafica" delle caselle della mappa e l'adiacenza in termini
di distanza di Hamming tra le combinazioni di valori in ingresso.
In particolare, possiamo notare che tutte le caselle contenenti "1" sono
adiacenti a due a due: questo significa che se prendiamo le loro coordinate
booleane, queste avranno distanza di Hamming unitaria, ossia differiranno
per un solo bit. Tale proprietà ci permette di identificare delle
coppie di caselle adiacenti contenenti lo stesso valore (1 in questo caso)
semplicemente omettendo la coordinata che assume valore diverso nella coppia.
Per esempio, invece di considerare separatamente le due caselle in basso nella
colonna a sinistra (quella caratterizzata da i2=0), esse hanno in comune
la coordinata i0=1, mentre differiscono per il valore di i1; possiamo quindi
identificare l'insieme di queste due caselle mediante l'espressione:
In modo analogo possiamo individuare l'insieme delle due caselle centrali
della colonna a destra (anch'esse caratterizzate dal valore "1") mediante
l'espressione:
i1·i2.
L'unione di questi due insiemi di due caselle copre
completamente tutte e sole le caselle della mappa caratterizzate dal
valore "1", quindi possiamo ritrovare la formula normale disgiuntiva
minimale della nostra funzione sommando (logicamente, ossia calcolando
la funzione OR tra) le coordinate di questi due insiemi di caselle:
(i0·(¬i2))+(i1·i2).
A differenza delle altre forme di rappresentazione, questa é nata per la rappresentazione di funzioni booleane nella memoria di un computer piuttosto che su carta per la manipolazione da parte di persone.
Il punto di partenza é una rappresentazione della tavola di verità mediante una struttura ad albero binario detta OBDT (Ordered Binary Decision Tree). Viene fissato una volta per tutte l'ordine col quale considerare le variabili di ingresso. La radice dell'albero corrisponde alla prima variabile di ingresso che si vuole considerare. Ogni altra variabile di ingresso corrisponde ad un livello dell'albero a distanza prefissata dalla radice (pari all'ordine della variabile). Ogni nodo non terminale ha due archi in uscita, uno corrispondente al valore 0 ed uno corrispondente al valore 1 per la variabile. Le foglie dell'albero rappresentano i valori assunti dall'uscita. I rami percorsi dalla radice per raggiungere le foglie corrispondono alla configurazione di ingresso che determina il valore di uscita rappresentato dalla foglia.
Consideriamo il nostro solito esempio di funzione a tre variabili. Supponiamo di fissare una volta per tutte l'ordine con cui considerare le variabili di ingresso: prima i2, poi i0, infine i1. (Notare la completa arbitrarietà di tale ordine.) La struttura OBDT diventa quindi completamente determinata, ed assume la forma illustrata in figura:
Il modo di disegnare l'albero diventa unico se stabiliamo una volta per tutte di disporre i livelli dall'alto verso il basso, e di orientare gli archi corrispondenti al valore 1 in basso a sinistra e quelli corrispondenti al valore 0 in basso a destra.
Dal punto di vista della quantità di informazioni codificate nell'albero, notiamo una fortissima ridondanza nei nodi foglia (4 nodi che rappresentano tutti il valore 1, ed altri 4 che rappresentano tutti il valore 0). Un modo per compattare la struttura dati senza alterarne il contenuto informativo consiste nel rinunciare al vincolo di struttura ad albero, ed ammettere una rappresentazione sotto forma di grafo aciclico. In particolare, prevediamo l'uso di due soli nodi terminali, uno per rappresentare il valore 1 e l'altro per rappresentare il valore 0. Si ottiene quindi la seguente struttura BDD:
Notiamo poi che i due nodi in basso a destra hanno entrambi gli archi di uscita diretti verso lo stesso nodo. Quindi, il fatto che la corrispondente variabile booleana di ingresso assuma il valore 0 oppure 1 non cambia il valore dell'uscita. Possiamo quindi semplificare la struttura del grafo eliminando quei due nodi, e connettendo direttamente gli archi che ci permettevano di raggiungere tali nodi con l'unico nodo raggiungibile da essi, ottenendo la seguente struttura BDD semplificata:
Possiamo ulteriormente notare ora che i due nodi in basso a sinistra sono identici (perché entrambi i loro archi di uscita puntano agli stessi nodi). Possiamo quindi semplificare ancora la struttura BDD mantenendo una sola copia di tali nodi (quella più a sinistra), e ridirigendo gli archi entranti nell'altro nodo sull'unica copia rimasta, come illustrato in figura:
A questo punto possiamo notare che si ripresenta per il nodo più a sinistra del livello i0 il caso di entrambi gli archi di uscita che puntano sullo stesso nodo. Procedendo quindi alla eliminazione di tale nodo ridondante (e ridirigendo i suoi archi di ingresso verso l'unico nodo di uscita) si ottiene infine la rappresentazione BDD in figura:
Tale rappresentazione é minimale, nel senso che non riusciamo più ad individuare dei criteri di semplificazione del grafo senza alterare la specifica dei valori di uscita. É stato definito un algoritmo che permette di automatizzare la costruzione di rappresentazioni OBDD minimali. In oltre é stato dimostrato formalmente che la rappresentazione OBDD minimale é unica (una volta fissato l'ordine con cui le variabili vengono elencate). Questo permette di usare rappresentazioni OBDD minimali nella memoria di un computer come rappresentazione canonica di una qualunque funzione booleana. Due funzioni saranno uguali quando hanno la stessa rappresentazione OBDD minimale in memoria.
Per saperne di più occorre rassegnarsi ad imparare a leggere l'inglese e far riferimento a un articolo di rassegna (contenente un'ampia bibliografia sull'argomento).
Poiché la rappresentazione BDD é equivalente alla rappresentazione mediante tavola di verità, é equivalente anche alle altre forme di rappresentazione. Per esempio, possiamo costruire una rappresentazione in forma normale disgiuntiva a partire dalla rappresentazione BDD. Per ottenere questa traduzione, il punto di partenza consiste nella individuazione delle funzioni identità sotto forma BDD.
I due nodi di livello i0 ed i1 nella rappresentazione BDD canonica del nostro
esempio possono essere interpretati come rappresentazione delle funzioni
identità (rispettivamente u=i0 e u=i1), poiché definiscono
un valore di uscita uguale al valore della variabile (ossia, l'arco
con etichetta 1 punta al terminale 1 e l'arco con etichetta 0 punta al
terminale 0).
D'altra parte per giungere al nodo che rappresenta la funzione identità
u=i1 occorre percorrere l'arco etichettato 1 uscente dal nodo di livello
i2, per cui questo ramo del grafo contribuisce al risultato col termine
And (i1·i2).
Analogamente, per giungere al nodo che rappresenta la funzione identità
u=i0 occorre percorrere l'arco etichettato 0 uscente dal nodo di livello
i2, per cui questo ramo del grafo contribuisce al risultato col termine
And (i0·(¬i2)).
Sommando questi due termini otteniamo la formula normale disgiuntiva:
(i0·(¬i2)) + (i1·i2)
che coincide con la rappresentazione minimale in forma normale disgiuntiva.
Occorre precisare che si tratta di una pura coincidenza.
In generale, dalla rappresentazione OBDD canonica si ottiene una forma
normale disgiuntiva "ragionevolmente compatta" ma non necessariamente
minimale (questo dipende dall'ordine con cui sono state elencate le variabili
di ingresso).
Vediamo ora i più comuni circuiti per la codifica, decodifica e commutazione di informazioni rappresentate sotto forma binaria. Tali circuiti costituiscono gli elementi costruttivi per la definizione di sistemi più complessi. Faremo riferimento alle tavole di verità per la definizione di questi circuiti, ma poi li tratteremo come unità funzionali più complesse, il cui funzionamento si intende noto senza ulteriori specificazioni a livello di tavole di verità.
L'esempio di funzione a tre ingressi e una uscita visto in precedenza é un multiplexer ad 1 bit con due ingressi dati (i0 e i1) ed un segnale di controllo (ingresso i2). Come si può facilmente notare dalla mappa che ne descrive il funzionamento, i2=0 implica u=i0, mentre i2=1 implica u=i1. Il valore dell'ingresso di controllo i2 consente quindi di riportare in uscita al multiplexer uno dei due valori in ingresso (i0 oppure i1).
L'idea di circuito multiplexer può essere estesa in diversi modi. Per esempio si può mantenere un solo ingresso di controllo, ma commutare uno tra due insiemi di variabili di ingresso su un solo insieme di variabili di uscita (ogni insieme di variabili di ingresso deve avere la stessa cardinalità dell'insieme di variabili di uscita. In figura é rappresentato lo schema realizzativo di un multiplexer operante su due insiemi di ingresso, ciascuno composto da tre variabili booleane.
La simbologia usata per la rappresentazione di un multiplexer a prescindere dalla sua realizzazione in termini di porte logiche elementari é la seguente:
Un secondo tipo di estensione del circuito multiplexer viene ottenuto utilizzando una codifica binaria su più bit per la scelta tra più di due ingressi da connettere sull'unica uscita. In figura é illustrato il caso di un multiplexer a 4 ingressi (ciascuno da un bit) comandato da due segnali di controllo in ingresso:
La combinazione degli ingressi c1 e c0 determina la scelta dell'ingresso (per esempio c1=1 e c0=1 "sceglie" i3) da connettere all'uscita u. Notare che in tal caso il numero di ingressi di controllo deve essere pari al logaritmo in base 2 del numero di ingressi che possono essere scelti per la connessione con l'uscita.
Ovviamente i due tipi di estensione del multiplexer (commutazione di più bit e scelta tra più di due ingressi) possono essere combinati in modo da formare, per esempio un multiplexer con 8 insiemi di ingresso, ciascuno da 32 bit, comandato attraverso la codifica su 3 ingressi di controllo.
Un circuito demultiplexer viene definito come l'inverso di un circuito multiplexer, ossia come un elemento funzionale capace di commutare un solo ingresso su due o più uscite. Per convenzione, le uscite "non attivate" assumono il valore costante 0, indipendentemente dal valore assunto dall'ingresso "dati". Notare che questa convenzione pone un vincolo sui codici che possono essere utilizzati per trattare le informazioni in uscita da un demultiplexer: il valore 0 deve poter essere interpretato come un valore non significativo, una condizione di riposo, ecc., in quanto questo valore viene assegnato a tutte le uscite non connesse con l'ingresso.
In figura é riportato un esempio di realizzazione di un demultiplexer a 2 uscite (comandato da un segnale di controllo c) in grado di commutare informazioni codificate su due bit.
La rappresentazione "astratta" di un tale dispositivo (prescindendo dalla sua realizzazione in termini di funzioni And e Not) é la seguente:
Circuiti demultiplexer possono essere realizzati con numero arbitrario di bit di ingresso e uscita, e con numero di ingressi di controllo pari al logaritmo in base 2 del numero di gruppi di uscite. La codifica binaria dei segnali di controllo individua univocamente l'insieme delle uscite attive che possono riprodurre inalterata la configurazione sull'insieme degli ingressi dati. Le altre uscite (quelle non corrispondenti al codice binario selezionato mediante gli ingressi di controllo) assumono il valore costante 0.
Circuiti di tipo multiplexer e demultiplexer hanno in comune tra loro una parte per la decodifica delle configurazioni booleane di controllo. Tale parte viene normalmente chiamata decoder. Un circuito di tipo decoder può essere pensato come un caso particolare di circuito demultiplexer, nel quale il segnale da commutare su una sola delle uscite é la costante 1. In figura é riportato a titolo di esempio lo schema di realizzazione di un decoder binario da 3 bit.
Circuiti di tipo decoder vengono normalmente utilizzati come componenti per la realizzazione di meccanismi di indirizzamento binario. Le uscite possono essere usate per abilitare il funzionamento di moduli simili l'uno all'altro, individuati tramite un indirizzo binario.
Notare che le uscite di un decoder possono essere messe in corrispondenza
con le righe di una tavola di verità per un circuito combinatorio
con numero di ingressi pari al numero di bit di controllo del decoder.
Per esempio, le 8 uscite del decoder riportato in figura possono essere
messe in corrispondenza con le 8 righe della tavola di verità
di un qualsiasi circuito combinatorio con 3 variabili di ingresso.
Unendo con una funzione Or tutte e sole le uscite del decoder corrispondenti
a quelle righe della tavola di verità contenenti il valore 1,
é quindi possibile realizzare in modo sistematico qualsiasi tavola
di verità.
Passiamo ora a vedere come, grazie all'uso di tecniche di codifica binaria, possiamo definire dei circuiti booleani in grado di effettuare delle manipolazioni di tipo numerico su rappresentazioni di numeri. In generale il metodo consiste nel definire un algoritmo di manipolazione su rappresentazioni binarie finite. La definizione viene data sotto forma esaustiva mediante la definizione della tavola di verità. La correttezza della realizzazione dipende dall'uso della tecnica di codifica assunta per la progettazione del circuito.
Cominciamo a considerare il caso semplice di rappresentazioni binarie di numeri su un solo bit (ossia numeri interi compresi tra 0 e 1). Notiamo subito che la somma dei valori 1+1=2 genera un valore di uscita non rappresentabile in forma binaria su un bit; per consentire la rappresentazione del risultato occorre infatti che il risultato venga rappresentato con almeno un bit in più rispetto al numero di bit usati per la rappresentazione degli addendi (in modo da poter codificare un valore massimo almeno doppio rispetto al massimo valore dei due addendi). La tavola di verità che specifica il comportamento di un tale circuito addizionatore é quindi la seguente:
s1: a b | u1 u0
------+------
0 0 | 0 0
0 1 | 0 1
1 0 | 0 1
1 1 | 1 0
Possiamo notare che la colonna u0 corrisponde alla tavola di verità
della funzione XOR, mentre la colonna u1 corrisponde a quella della funzione
AND.
Le due uscite del circuito possono quindi essere ottenute mediante l'uso
di queste due funzioni elementari applicate alla stessa coppia di ingressi
a e b.
Un tale circuito con due ingressi e due uscite viene normalmente chiamato
half adder (semi addizionatore), per il motivo che scopriremo
tra poco.
Passiamo ora al caso di somma tra due numeri rappresentati su 2 bit (con risultato
rappresentato su 3 bit).
Il funzionamento del circuito, usando la normale codifica binaria, può
essere definito mediante la seguente mappa:
\ b1 | 0 : 0 : 1 : 1 |
\ b0 | 0 : 1 : 0 : 1 |
a1 a0 \ | : : : |
--------\--+-----:-----:-----:-----+
0 0 | 000 : 001 : 010 : 011 |
..........|.....:.....:.....:.....|
0 1 | 001 : 010 : 011 : 100 |
..........|.....:.....:.....:.....|
1 0 | 010 : 011 : 100 : 101 |
..........|.....:.....:.....:.....|
1 1 | 011 : 100 : 101 : 110 |
-----------+-----:-----:-----:-----+
La realizzazione diretta di tale circuito risulta evidentemente molto più
complessa di quella di un semi addizionatore.
In oltre, la complessità di realizzazione diventa rapidamente proibitiva
se aumentiamo ulteriormente il numero di bit di rappresentazione per gli
addendi e per il risultato.
La soluzione che consente di realizzare in modo semplice ed efficiente circuiti addizionatori per rappresentazioni su due o più bit consiste nel modularizzare la realizzazione.
In questo caso la corretta modularizzazione può essere individuata facendo ricorso all'algoritmo di somma cifra per cifra: ad ogni passo consideriamo una sola cifra dell'addendo a e una sola cifra dell'addendo b, oltre all'eventuale cifra "di riporto" derivante dall'applicazione dello stesso algoritmo alle cifre precedenti. Quindi ad ogni passo operiamo su rappresentazioni binarie di un solo bit; l'unica differenza rispetto al circuito semi sommatore visto in precedenza é che ora dobbiamo considerare la presenza di 3 addendi da un bit (a, b e la cifra di riporto c).
La specifica di un circuito in grado di effettuare tale somma (chiamato full adder, o sommatore completo a 1 bit) é data dalla seguente tavola di verità:
s2: a b c | r u
---------+------
0 0 0 | 0 0
0 0 1 | 0 1
0 1 0 | 0 1
0 1 1 | 1 0
1 0 0 | 0 1
1 0 1 | 1 0
1 1 0 | 1 0
1 1 1 | 1 1
L'uscita u corrisponde ad una funzione XOR a tre ingressi, mentre l'uscita
r deve essere generata da un circuito in grado di riconoscere la condizione
"almeno due ingressi assumono il valore 1".
Indichiamo in modo compatto un circuito di tipo full-adder mediante il
seguente simbolo:
Tali moduli possono essere combinati in modo da realizzare l'operazione di
somma tra rappresentazioni binarie su più cifre, usando un modulo
per ogni cifra;
ciascun modulo genera una cifra di "riporto" verso il modulo
successivo.
In figura viene riportato lo schema di connessione di due moduli per
formare un addizionatore per addendi rappresentati su due bit (e risultato
rappresentato su 3 bit).
Notiamo che questa realizzazione di un circuito addizionatore su N bit
presenta vantaggi e svantaggi rispetto ad una realizzazione diretta mediante
logica a 3 livelli dalla tavola di verità (ammesso che questa fosse
possibile anche per grandi valori di N).
Il vantaggio principale (derivante dalla modularità della realizzazione)
é che la complessità della realizzazione cresce linearmente
all'aumentare del numero N di bit di rappresentazione degli addendi (in quanto
l'aggiunta di una cifra comporta esattamente l'aggiunta di un modulo full-adder).
Lo svantaggio principale é dovuto alla tecnica di propagazione del
riporto (chiamata ripple carry).
Questo fa sì che anche il tempo di assestamento del risultato a seguito
di una variazione dei valori in ingresso cresca linearmente al crescere del numero
N di bit della rappresentazione degli addendi.
In particolare, notiamo che il tempo di assestamento per la cifra più
significativa sarà N volte più grande di quello per la cifra
meno significativa, a causa della possibile propagazione del riporto attraverso
tutti i moduli full-adder.
Questo problema in pratica viene risolto con l'aggiunta di ulteriori circuiti
combinatori realizzati in logica a 3 livelli per la "previsione delle
cifre di riporto" (carry lookahead).
Per esempio, la cifra binaria più a sinistra nelle caselle della
mappa del circuito sommatore a 2 bit
può essere usata per specificare un
circuito di previsione del riporto sulla terza cifra.
Una possibile realizzazione della funzione di previsione del
riporto sulla terza cifra in logica a due livelli (nessuna variabile
appare in forma negata in questo esempio) potrebbe quindi essere
definita dalla formula (normale disgiuntiva):
(a1·b1)+(a0·a1·b0)+(a0·b1·b0).
Notiamo infine che un circuito sommatore su N bit progettato per operare su rappresentazioni binarie di numeri senza segno può essere usato anche per operare su rappresentazioni di numeri con segno in complemento a 2 su N bit. L'unica accortezza che occorre osservare in tal caso é quella di definire il risultato su N bit (senza considerare l'N+1-esimo bit di riporto), e quindi di accertarsi che il risultato di una operazione di somma tra numeri dello stesso segno non generi condizioni di overflow.
Un caso particolare di dispositivo sommatore é costituito dal caso
di un "incrementatore" che somma un valore costante K ad un addendo variabile A.
Nella maggior parte dei casi ci si riduce a voler sommare la costante K=1
ad un valore arbitrario in ingresso.
In tal caso il dispositivo può essere realizzato in modo molto semplice
usando N moduli di tipo "half-adder" (quello sulla vifra meno significativa
somma 1 ad a0, quelli sulle cifre successive sommano ai+ri).
In questo caso anche la funzione "carry lookahead" può
essere estremamente semplificata:
ri = a(i-1) · a(i-2) · ... · a0
Scopo di un circuito comparatore é il confronto tra due codifiche binarie. Il confronto può essere effettuato per verificare l'uguaglianza oppure una relazione d'ordine del tipo "maggiore", "minore", ecc. Il caso di confronto per stabilire l'uguaglianza può essere risolto in maniera molto semplice ed indipendente dal codice usato, con l'unica ipotesi di avere una rappresentazione unica per ogni valore. I confronti per stabilire relazioni d'ordine invece devono necessariamente tener conto del codice utilizzato.
Questi possono essere realizzati a partire dalla funzione elementare XNOR a due ingressi. Dalla tavola di verità di questa funzione vediamo che, interpretando l'uscita 0 come "falso" e l'uscita 1 come "vero", possiamo ottenere immediatamente in uscita il risultato del confronto per rilevare l'uguaglianza tra le due variabili di ingresso.
Possiamo estendere il circuito in modo da operare il confronto tra due insiemi di variabili booleane, utilizzando una funzione del tipo XNOR per ogni coppia di variabili da confrontare, calcolando poi l'AND tra i confronti di ogni cifra. Per esempio, in figura é illustrata la realizzazione di un circuito comparatore per rilevare l'uguaglianza tra due ingressi codificati ciascuno su 3 bit (usando ovviamente lo stesso codice per i due ingressi).
Cominciamo a considerare il caso di rappresentazioni di numeri senza segno su 2 bit. La seguente Mappa di Karnaugh descrive il funzionamento del circuito che vogliamo realizzare:
\ b1 | 0 : 0 : 1 : 1 |
\ b0 | 0 : 1 : 0 : 1 |
a1 a0 \ | : : : |
--------\--+-----:-----:-----:-----+
0 0 | 0 : 0 : 0 : 0 |
..........|.....:.....:.....:.....|
0 1 | 1 : 0 : 0 : 0 |
..........|.....:.....:.....:.....|
1 0 | 1 : 1 : 0 : 0 |
..........|.....:.....:.....:.....|
1 1 | 1 : 1 : 1 : 0 |
-----------+-----:-----:-----:-----+
Un esempio di realizzazione di questa mappa é dato dalla funzione:
u = a1·(¬b1) + a0·(¬b0)·(a1+(¬b1))
La complessità della realizzazione tuttavia cresce molto in funzione del numero di bit delle codifiche da confrontare. Nel caso di confronto tra numeri codificati su 3 bit otteniamo la mappa:
\ b2 | 0 : 0 : 0 : 0 : 1 : 1 : 1 : 1 |
\ b1 | 0 : 0 : 1 : 1 : 0 : 0 : 1 : 1 |
\ b0 | 0 : 1 : 0 : 1 : 0 : 1 : 0 : 1 |
a2 a1 a0 \ | : : : : : : : |
-----------\--+-----:-----:-----:-----:-----:-----:-----:-----+
0 0 0 | 0 : 0 : 0 : 0 : 0 : 0 : 0 : 0 |
.............|.....:.....:.....:.....:.....:.....:.....:.....|
0 0 1 | 1 : 0 : 0 : 0 : 0 : 0 : 0 : 0 |
.............|.....:.....:.....:.....:.....:.....:.....:.....|
0 1 0 | 1 : 1 : 0 : 0 : 0 : 0 : 0 : 0 |
.............|.....:.....:.....:.....:.....:.....:.....:.....|
0 1 1 | 1 : 1 : 1 : 0 : 0 : 0 : 0 : 0 |
.............|.....:.....:.....:.....:.....:.....:.....:.....|
1 0 0 | 1 : 1 : 1 : 1 : 0 : 0 : 0 : 0 |
.............|.....:.....:.....:.....:.....:.....:.....:.....|
1 0 1 | 1 : 1 : 1 : 1 : 1 : 0 : 0 : 0 |
.............|.....:.....:.....:.....:.....:.....:.....:.....|
1 1 0 | 1 : 1 : 1 : 1 : 1 : 1 : 0 : 0 |
.............|.....:.....:.....:.....:.....:.....:.....:.....|
1 1 1 | 1 : 1 : 1 : 1 : 1 : 1 : 1 : 0 |
--------------+-----:-----:-----:-----:-----:-----:-----:-----+
Un esempio di realizzazione di questa mappa é dato dalla funzione:
u = a2·(¬b2) + a1·(¬b1)·(a2+(¬b2)) +a0·(¬b0)·(a2·(a1+(¬b1))+(¬b2)·(a1+(¬b1)))
Si vede bene come l'estensione di questo circuito al caso di più di 3 bit di rappresentazione per i numeri da confrontare diventa improponibile (almeno dal punto di vista della derivazione manuale delle mappe e della funzione che realizza il circuito).
L'alternativa consiste quindi nell'individuare un modulo base di confronto tra una coppia di cifre, e nel replicare tale modulo tante volte quante sono le cifre delle rappresentazioni binarie da confrontare. Il confronto deve partire dalla cifra più significativa: se le due rappresentazioni differiscono nella cifra più significativa, allora possiamo subito concludere se la relazione a>b é vera o falsa, senza bisogno di considerare le cifre successive. Solo se le cifre più significative delle due rappresentazioni a confronto sono uguali, allora ddobbiamo passare all'esame delle cifre successive per arrivare a concludere il valore di verità della relazione di confronto.
Tale descrizione di massima di un algoritmo iterativo sulle cifre delle rappresentazioni può essere tradotta nella definizione di un modulo circuitale con 4 ingressi e due uscite, che realizza le operazioni di confronto su una singola cifra. Indichiamo con A e B le due variabili di ingresso al modulo corrispondenti alla cifra "corrente" da esaminare per le due rappresentazioni binarie; indichiamo con C e D due variabili di ingresso ausiliarie che ci riportano la codifica del risultato del confronto sulle cifre più significative. In particolare, stabiliamo di indicare con C=1 la condizione "i confronti precedenti non hanno portato nessun risultato definitivo", e con C=0 la condizione "l'esito del confronto é già noto a seguito del confronto delle cifre precedenti". Nel caso C=0, interpretiamo poi D=0 come risposta "no, a non é maggiore di b" ed invece D=1 come risposta "si, a>b". Indichiamo infine con E e R le due uscite che codificano l'esito del confronto. In particolare indicheremo con E=1 la condizione "neanche l'esame di questa cifra ci permette di dare una risposta definitiva", e con E=0 la condizione "la risposta é stata determinata"; in quest'ultimo caso R=0 significa "no", mentre R=1 significa "si, a>b".
Il funzionamento del modulo viene definito mediante la seguente mappa:
\ C | 0 : 0 : 1 : 1 |
\ D | 0 : 1 : 0 : 1 |
A B \ | E R : E R : E R : E R |
--------\--+-----:-----:-----:-----+
0 0 | 0 0 : 0 1 : 1 0 : 1 0 |
..........|.....:.....:.....:.....|
0 1 | 0 0 : 0 1 : 0 0 : 0 0 |
..........|.....:.....:.....:.....|
1 0 | 0 0 : 0 1 : 0 1 : 0 1 |
..........|.....:.....:.....:.....|
1 1 | 0 0 : 0 1 : 1 0 : 1 0 |
-----------+-----:-----:-----:-----+
Tale mappa può essere realizzata in forma minima in logica a 3 livelli
mediante le due funzioni:
E = (¬A)·(¬B)·C + A·B·C
R = A·(¬B)·C + (¬C)·D
Per esempio un circuito comparatore a 3 bit può essere realizzato connettendo tre repliche di tale modulo come illustrato in figura:
Per esercizio, provare a realizzare un modulo comparatore per la relazione a>=b, ed a connetterne 4 repliche per ottenere un circuito comparatore a 4 bit.
Lo stesso tipo di comparatore può essere utilizzato anche per il confronto tra numeri con segno in codice eccesso 2**(N-1). Nel caso di numeri con segno in codice complemento a 2 occorre invece invertire la cifra più significativa delle due rappresentazioni (il bit di segno).
La funzione di cambiamento di segno per un numero rappresentato in codice complemento a 2 su N bit può essere realizzata, oltre che (partendo dalla definizione) complementando a 1 e poi sommando la costante 1, anche mediante un algoritmo iterativo che esamina tutte le cifre della rappresentazione partendo da quella meno significativa. L'algoritmo prevede due comportamenti diversi in funzione di una variabile di stato. Nello stato iniziale, si esamina la cifra corrente (partendo dalla meno significativa) e la si lascia invariata; se la cifra corrente é 1 allora si passa al secondo stato, altrimenti si rimane nello stato iniziale. Nel secondo stato si complementa la cifra corrente e si permane nel secondo stato.
Tale algoritmo può essere realizzato mediante l'adozione di un modulo circuitale combinatorio a 2 ingressi (denominati I e C) e due uscite (denominate U e S), in grado di calcolare una cifra della rappresentazione del risultato. Il modulo "complementatore a 2" viene specificato mediante la seguente tavola di verità:
c2 : I C | U S
-------+------
0 0 | 0 0
0 1 | 1 1
1 0 | 1 1
1 1 | 0 1
Ovviamente la realizzazione del dispositivo può essere ottenuta mediante una funzione XOR per l'uscita U ed una funzione OR per l'uscita S.
Un circuito complementatore a 2 per rappresentazioni su N bit viene quindi ottenuto usando N copie del modulo realizzato come sopra specificato. L'ingresso I di ciascun modulo viene connesso ad una cifra della rappresentazione del numero da cambiare di segno. L'uscita U del modulo rappresenta la corrispondente cifra della rappresentazione del risultato. L'ingresso C del modulo corrispondente alla cifra meno significativa viene connesso al valore costante 0. L'ingresso C di tutti gli altri moduli viene connesso all'uscita S del modulo che calcola la cifra immediatamente precedente.
Come nel caso del sommatore con ripple carry, questo circuito ha una complessità di realizzazione che cresce linearmente col numero di bit della rappresentazione del numero, ed un tempo di assestamento dei risultati in uscita a seguito di variazioni dei valori in ingresso che cresce anch'esso linearmente col numero di bit della rappresentazione.
Anche nel caso di circuiti per la moltiplicazione tra numeri espressi in codice binario senza segno su N bit, una realizzazione in logica a tre livelli risulterebbe eccessivamente complessa per grandi valori di N. Vediamo quindi subito una realizzazione modulare. Il punto di partenza per una realizzazione modulare é il cosiddetto algoritmo di moltiplicazione per "somme e scorrimenti", versione binaria del normale algoritmo di moltiplicazione cifra per cifra a cui siamo abituati nel sistema decimale.
Cominciamo a considerare il caso semplificato di moltiplicazione di un operando A rappresentato su N cifre per un operando b rappresentato su una sola cifra binaria. L'operando b potrà assumere ovviamente solo i valori 0 e 1. Nel primo caso il risultato del prodotto sarà 0, mentre nel secondo caso il risultato sarà A. Tale risultato può essere ottenuto mediante un circuito combinatorio composto da N funzioni AND a 2 ingressi, ciascuna connessa ad una cifra diversa dell'operando A ed all'unica cifra dell'operando b. Ogni funzione AND produrrà in uscita una cifra del risultato del prodotto.
Consideriamo ora il caso di un operando A espresso su N bit, ed un operando B espresso su due bit (ovvero B=b0+2·b1). Il prodotto A·B può quindi essere decomposto in A·b0 + A·b1·2, dove l'operazione di moltiplicazione per 2 viene realizzata mediante lo "scorrimento" della rappresentazione del numero di una cifra verso sinistra, aggiungendo 0 come cifra meno significativa.
Da questo possiamo arrivare a produrre uno schema di realizzazione di un circuito moltiplicatore tra due numeri rappresentati su N bit che fa uso solo di circuiti sommatori e di funzioni AND. Un tale moltiplicatore può essere istanziato al caso di N=3 come illustrato in figura a titolo di esempio:
La complessità circuitale di un dispositivo di questo tipo cresce col quadrato del numero di bit delle rappresentazioni degli operandi (il numero di somme e di moltiplicazioni per un bit cresce linearmente col numero di bit, e la realizzazione di ciascuno cresce linearmente col numero di bit). Dal punto di vista del tempo di assestamento, questo può crescere secondo N·log(N), utilizzando uno schema di somma ad albero binario (si possono costruire degli alberi binari di sommatori di profondità logaritmica rispetto al numero di termini da sommare, ed ogni sommatore di tipo ripple carry richiede un tempo di assestamento che cresce linearmente col numero di bit).
L'unità aritmetico-logica é uno dei componenti fondamentali di un sistema di calcolo. Viene solitamente realizzata come circuito combinatorio con due insiemi di variabili di ingresso (contenenti la codifica binaria di due operandi), un insieme di variabili di controllo, un insieme di variabili di uscita (contenente la codifica di un risultato), ed eventualmente altre variabili di uscita contenenti la codifica di condizioni particolari verificatesi durante il funzionamento del circuito.
Un'ALU é in grado di produrre un risultato in uscita corrispondente all'applicazione di diversi operatori aritmetici (somma, moltiplicazione, ecc.) o logici (AND, NOT, ecc.) agli operandi codificati sulle variabili di ingresso. La scelta del tipo di operazione da effettuare avviene attraverso una codifica binaria fornita all'ALU mediante gli ingressi di controllo. Le condizioni segnalate sono solitamente overflow per operazioni aritmetiche, risultato uguale a zero, risultato negativo, ecc.
La realizzazione di un'ALU operante su rappresentazioni ad N bit
può essere ottenuta mediante l'unione di tanti circuiti
combinatori, ciascuno specializzato nel calcolo di una funzione unaria (complementatore a 2,
NOT, moltiplicatore per 2, ecc.) o binaria (sommatore, AND, OR, ecc.) su N bit,
tutti connessi alle stesse rappresentazioni di operandi in ingresso,
connessi alternativamente in uscita mediante un multiplexer comandato dai
segnali di controllo dell'ALU.
La complessità della realizzazione cresce sia al crescere del numero N di
bit di rappresentazione degli operandi, sia al crescere del numero di operatori
aritmetici e logici inclusi.