Fondamenti di informatica - Laurea triennale Informatica/Funzioni booleane e sintesi dei circuiti
Un circuito viene costruito per svolgere un compito preciso. Quando si vuole progettare un circuito combinatorio, il problema può essere descritto specificando quali devono essere gli input e quali gli output.
Per esempio, immaginiamo di voler costruire un circuito combinatorio che calcoli l’operazione AND tra due variabili, indicate con a e b. In questo caso, possiamo descrivere il problema elencando tutte le possibili combinazioni di valori in ingresso e il corrispondente valore in uscita.
Questo equivale a costruire la tabella logica desiderata, cioè una tabella che stabilisce il comportamento del circuito per ogni possibile combinazione degli input.
Definizione di porta logica
[modifica | modifica sorgente]Una porta logica viene definita come una funzione che prende in ingresso uno o più bit e produce un bit in uscita. Esempi semplici sono:
- la porta AND, che restituisce 1 solo se tutti gli ingressi sono 1;
- la porta NOT, che inverte il valore del bit.
Queste porte sono considerate come funzioni matematiche applicate a valori binari.
Completezza funzionale
[modifica | modifica sorgente]Un insieme di porte è detto funzionalmente completo se permette di costruire un circuito combinatorio capace di calcolare qualunque funzione booleana.
L’insieme formato da AND, OR e NOT è funzionalmente completo: con queste tre porte si può realizzare qualsiasi funzione booleana.
Eliminazione di alcune porte
[modifica | modifica sorgente]Un risultato importante è che non è sempre necessario usare tutte e tre le porte AND, OR e NOT in quanto anche gli insiemi:
- AND e NOT
- OR e NOT
sono funzionalmente completi.
Questo è possibile perché una porta può essere ricostruita usando le altre. Per esempio, una porta OR può essere ottenuta usando solo AND e NOT tramite le leggi di De Morgan, quindi, ogni circuito che usa AND, OR e NOT può essere trasformato in un circuito equivalente che usa solo AND e NOT.
La porta NAND
[modifica | modifica sorgente]La porta NAND corrisponde alla negazione della porta AND.
La NAND restituisce 0 solo quando entrambi gli ingressi sono 1; in tutti gli altri casi restituisce 1.
La sola porta NAND è funzionalmente completa.Questo significa che usando esclusivamente porte NAND si possono costruire circuiti equivalenti a quelli realizzati con AND, OR e NOT.
Il motivo è che con la NAND si possono costruire:
- la porta NOT;
- la porta OR;
- e, di conseguenza, anche le altre funzioni booleane.
La porta NOT può essere ottenuta collegando x a entrambi gli ingressi di una porta NAND,
La porta AND si può costruire negando la NAND
La porta OR si ottiene unendo mediante una NAND a due ingressi precedentemente negati con a porte NOT (deducibile mediante le leggi di De Morgan)
Efficienza dei circuiti
[modifica | modifica sorgente]Una funzione booleana può essere realizzata in forma normale disgiuntiva, ma il circuito ottenuto potrebbe essere molto grande o poco efficiente. Per questo motivo, nella progettazione dei circuiti è utile cercare forme equivalenti più semplici, con meno porte e meno collegamenti.
Half adder
[modifica | modifica sorgente]Un half adder, o mezzo sommatore, è un circuito che prende in ingresso due bit, indicati con x e y, e produce due uscite:
- il bit di somma s;
- il bit di riporto c, detto anche carry.
Il risultato della somma tra x e y è quindi rappresentato dal numero binario a due bit cs. Per esempio, se x=1 e y=1, la somma è 10: quindi c=1 e s=0.
Dal comportamento del circuito si osserva che:
s=x⊕y
cioè il bit di somma è dato dall’OR esclusivo, mentre:
c=xy
cioè il riporto si ottiene con una porta AND.
Full adder
[modifica | modifica sorgente]Il full adder, o sommatore completo, estende il mezzo sommatore. Prende in ingresso tre bit:
x,y,z
dove z rappresenta di solito il riporto proveniente da una somma precedente.
Anche il full adder produce due uscite:
- il bit di somma s;
- il bit di riporto c.
Il bit di somma si ottiene calcolando l’OR esclusivo tra i tre ingressi:
s=x⊕y⊕z
Per il riporto c, invece, si parte dalla forma normale disgiuntiva e poi si semplifica l’espressione logica per ottenere un circuito più efficiente, con meno porte logiche.
Somma di numeri binari a più bit
[modifica | modifica sorgente]E' possibile usare circuiti half adder e full adder per costruire un circuito che somma due numeri binari di tre bit.
L’idea è la stessa dell’algoritmo tradizionale della somma:
- si sommano i bit meno significativi con un half adder;
- il riporto prodotto viene passato alla colonna successiva;
- le colonne successive vengono sommate con full adder, perché devono considerare tre valori: i due bit da sommare e il riporto precedente.
Per due numeri a tre bit, il circuito usa:
- un half adder per la prima colonna;
- due full adder per le colonne successive.
Il risultato può avere quattro bit, perché la somma di due numeri a tre bit può produrre un riporto finale.
Overflow
[modifica | modifica sorgente]Se si lavora con registri a tre bit, il quarto bit del risultato può essere interpretato come flag di overflow.
Se il quarto bit vale 1, significa che il risultato non può essere rappresentato con soli tre bit, quindi si è verificato overflow. Se invece vale 0, non c’è overflow.