Post on 15-Feb-2019
00.b
Reti Logiche CombinatorieReti Logiche Combinatorie
AnalisiMinimizzazione booleana
Sintesi
Testo di riferimento: [Congiu] - 2.4 (pagg. 37–57)
34
2
Architettura degli Elaboratori © 2009
Rete logica combinatoria: definizioneRete logica combinatoria: definizione
Una rete logica combinatoria è una rete logica nella quale, in ogni istante, i valori presenti alle uscite sono determinati unicamente dai valori presenti agli ingressinel medesimo istante.
Una rete logica combinatoria è quindi• priva di stato
(non contiene elementi di memoria);• interamente descritta dalla sua
tabella di verità
34
3
Architettura degli Elaboratori © 2009
Primo esempio: il decodificatore 3/8Primo esempio: il decodificatore 3/8
Un decodificatore è una rete combinatoria che attival’i-esima uscita se e solo seil valore binario codificato dagli ingressi è i
Tabella di verità per un decodificatore con 3 ingressi e 23=8 uscite:
34
4
Architettura degli Elaboratori © 2009
Decodificatore: realizzazioneDecodificatore: realizzazione
Sono rappresentatesolo le funzioniF0, F1 e F4.
Le porte NOTsono rappresentatecon circoletti “ ”.
34
5
Architettura degli Elaboratori © 2009
Porte logiche: notazione algebricaPorte logiche: notazione algebrica
Nome Simbolo grafico
Tabelladi verità
Notazione algebrica
AND Y = A·B
OR Y = A+B
NOT Y = A
XOR Y = A⊕B
34
6
Architettura degli Elaboratori © 2009
Reti logiche: rappresentazioniReti logiche: rappresentazioni
• …mediante uno schema grafico• …mediante una tabella di verità• …mediante una espressione algebrica
Sceglieremo in ciascun caso la rappresentazione più opportuna per quel caso.
Quanto abbiamo visto per le porte logiche vale in generale per le reti logiche.In altre parole, sono tra loro equivalentile tre rappresentazioni…
34
7
Architettura degli Elaboratori © 2009
Funzione di equivalenza (1 di 3)Funzione di equivalenza (1 di 3)
E= A•B+A•B
È possibile ottenere E attraverso la“somma di prodotti”
34
8
Architettura degli Elaboratori © 2009
Funzione di equivalenza (2 di 3)Funzione di equivalenza (2 di 3)
E= (A+B) •(A+B)
...è possibile ottenere E anche attraverso il “prodotto di somme”
34
9
Architettura degli Elaboratori © 2009
Funzione di equivalenza (3 di 3)Funzione di equivalenza (3 di 3)
Diversi circuiti logici equivalenti che realizzano la stessa funzione logica
34
10
Architettura degli Elaboratori © 2009
Algebra di Algebra di BooleBoole o booleanao booleana
L’analisi delle proprietà delle espressioni algebriche costruite da variabili binarie e operatori logici, si deve al matematico G. Boole(1815-1864), ed è nota come algebra booleana.
S = B•(A•B) + A•(A•B) ?
34
11
Architettura degli Elaboratori © 2009
Algebra di Algebra di BooleBoole: propriet: proprietàà (1 di 2)(1 di 2)
A
A·1 = A A·0 = 0 A·A = A A·A = 0
A = A A+0 = A A+1 = 1 A+A = A
A+A = 1
Proprietà commutativa, associativa e distributiva:
A·B = B·A A+B = B+A A·(B·C) = (A·B)·C
A+(B+C) = (A+B)+C A·(B+C) = A·B+A·C
A+(B·C) = (A+B)·(A+C)
34
12
Architettura degli Elaboratori © 2009
Algebra di Algebra di BooleBoole: propriet: proprietàà (2 di 2)(2 di 2)
A
Legge di De Morgan:
A + B = A · B
A · B = A + B
34
13
Architettura degli Elaboratori © 2009
S’ = A•B+A•B = A⊕BC’ = A•B
Sintesi di un Sintesi di un halfhalf--adderadder (1 di 2)(1 di 2)
34
14
Architettura degli Elaboratori © 2009
Sintesi di un Sintesi di un halfhalf--adderadder (2 di 2)(2 di 2)
S’ = A•B + A•B
S’ = A•B • A•B
S’ = (A•B+B•B) • (A•B+A•A)
S’ = B•(A+B) • A•(A+B)
S’ = B•(A•B) • A•(A•B)
Utilizziamo l’algebra booleana e le sue proprietàper riscrivere S’ utilizzando solo porte NAND:
34
15
Architettura degli Elaboratori © 2009
HalfHalf--adderadder con sole porte NANDcon sole porte NAND
S’ = B•(A•B) • A•(A•B)
C’ = A•B
34
16
Architettura degli Elaboratori © 2009
Sintesi di un Sintesi di un fullfull--adderadder (1 di 2)(1 di 2)
S = A•B•C” + A•B•C” + A•B•C” + A•B•C”
S = (A•B + A•B)•C” + (A•B + A•B)•C”
S = (A⊕B)•C” + (A⊕B)•C” = (A⊕B) ⊕ C”
S = S’ ⊕ C”C = A•B•C” + A•B•C” + A•B•C” + A•B•C”
C = (A•B + A•B)•C” + A•B•(C” + C”) = (A⊕B)•C” + A•B
C = S’•C” + C’
S’ = (A⊕B)
C’ = A•B
Half-Adder
34
17
Architettura degli Elaboratori © 2009
Sintesi di un Sintesi di un fullfull--adderadder (2 di 2)(2 di 2)
S = S’ ⊕ C”
C = S’•C” + C’
34
18
Architettura degli Elaboratori © 2009
FullFull--adderadder con sole porte NANDcon sole porte NAND
C = S’•C” + C’ = S’•C” • C’
34
19
Architettura degli Elaboratori © 2009
Sommatore binario da 4 bitSommatore binario da 4 bit
34
20
Architettura degli Elaboratori © 2009
Sommatore binario da 16 bitSommatore binario da 16 bit
34
21
Architettura degli Elaboratori © 2009
Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (1/7)(1/7)
Tra le proprietà dell’algebra di Boole, le seguenti consentono di semplificare notevolmente le espressioni booleane:A•B + A•B = A•(B + B) = AA•(B•C + B•C + B•C + B•C) = ALe mappe di Karnaugh sono una particolare forma di tabella di verità, che consente di individuare immediatamente la possibilità di fare queste semplificazioni.
34
22
Architettura degli Elaboratori © 2009
Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (2/7)(2/7)
Ad esempio, la seguente tabella di verità della funzione Y=Y(A,B,C) A B C Y A 0 0 1 1 0 0 0 0 B 0 1 1 0 0 0 1 0 può essere ridisegnata così: C 0 1 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 Mappa di Karnaugh della funzione Y 1 1 1 1 Nelle mappe di K. i valori della funzione sono scritti dentro le caselle.
Dalla tabella di verità o dalla mappa di Karnaugh è immediato ottenere l’espressione booleana della funzione Y come “somma” di “prodotti”, cioè come OR di tanti termini AND quante sono le caselle in cui la funzione vale 1; ciascuno di questi termini AND (detti minterm) è costituito dall’AND delle variabili di ingresso, negate oppure no a seconda che il valore della variabile associato a quella casella sia 0 oppure 1: Y = A•B•C + A•B•C + A•B•C + A•B•C
34
23
Architettura degli Elaboratori © 2009
Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (3/7)(3/7)Nel caso di funzioni di 4 variabili, ad es. Z=Z(A,B,C,D), la mappa di Karnaugh ha 4 righe e quattro colonne:
CD
AB 0 0
0 1
1 1
1 0
00 0 0 1 0
01 1 0 1 1
11 1 1 1 1
10 1 1 1 0
Mappa di Karnaugh della funzione Z
I valori delle variabili A,B,C,D individuano le “coordinate” delle caselle:le coppie di valori di A e B (di C e D) associate alle colonne (alle righe)sono ordinate in modo che tra due caselle adiacenti (della medesima riga o della medesima colonna) cambi il valore di una sola delle variabili, mentre quello di tutte le altre rimane lo stesso; ciò vale anche tra le caselle estreme di ciascuna riga e di ciascuna colonna (che possono quindi essere considerate “adiacenti”, in senso circolare).
34
24
Architettura degli Elaboratori © 2009
Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (4/7)(4/7)In questo modo a ciascuna coppia di caselle adiacenti contrassegnate con il valore 1 corrispondono, nella espressione booleana, due termini “prodotto” (minterm) nei quali una variabile è presente negata in uno e non negata nell’altro, mentre tutte le altre variabili hanno lo stesso valore.
E` allora possibile semplificare l’espressione sostituendo quei due termini con un unico termine nel quale non è più presente la variabile che cambia valore.
Ad esempio le ultime due caselle della seconda riga nella mappa della funzione Y portano alla seguente semplificazione:
A•B•C + A•B•C = A•C
34
25
Architettura degli Elaboratori © 2009
Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (5/7)(5/7)Allo stesso modo, quaterne di caselle adiacenti tutte con il valore 1 (sulla stessa riga o sulla stessa colonna) corrispondono a quattro termini che si riducono ad uno; ad esempio le quattro caselle della terza riga nella mappa della funzione Z portano alla seguente semplificazione:
C•D•(A•B + A•B + A•B + A•B) = C•D
le quattro caselle della terza colonna nella mappa della funzione Z portano alla seguente semplificazione:
A•B•(C•D + C•D + C•D + C•D) = A•B
Così pure quaterne adiacenti disposte secondo un quadrato producono un unico termine; ad esempio le quattro caselle in basso a sinistra nella mappa della funzione Z portano alla seguente semplificazione:
A•C•(B•D + B•D + B•D + B•D) = A•C
Analogo discorso vale per gruppi di otto caselle adiacenti tutte con il valore 1.
34
26
Architettura degli Elaboratori © 2009
Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (6/7)(6/7)Per semplificare l’espressione di una funzione, si individuano, nella mappa di K., i gruppi di (2 o 4 o 8) caselle adiacenti con il valore 1. Spesso conviene sfruttare la proprietà A+A=A, che consente di utilizzare più volte la stessa casella (lo stesso minterm), per formare gruppi diversi e ottenere il maggior numero di semplificazioni possibile. Individuando un insieme di gruppi (da 1, 2, 4 o 8) che copra tutte le caselle in cui compare il valore 1, si ottiene una espressione semplificata, costituita dall’OR dei termini corrispondenti a ciascun gruppo. Ad es. per la funzione Z, si possono individuare i gruppi segnati in figura:
CDAB0 0
0 1
1 1
1 0
00 0 0 1 0
01 1 0 1 1
11 1 1 1 1
10 1 1 1 0
A•C A•B B•D
Si ottiene, immediatamente, l’espressione semplificata: Z=A•C+A•B+B•D
34
27
Architettura degli Elaboratori © 2009
Minimizzazione: Mappe di Minimizzazione: Mappe di KarnaughKarnaugh (7/7)(7/7)Funzioni booleane parzialmente definite: il loro valore è specificato solo per alcune combinazioni dei valori delle variabili. Le altre combinazioni o non si verificano mai o il valore della funzione non interessa: don’t care conditions (d.c.c.). In una mappa di K. è spesso utile inserire un valore 1 al posto di d.c.c. (per formare ulteriori raggruppamenti). Es. Funzione parzialmente definita W (i trattini individuano d.c.c.): A B C W A 0 0 1 1 0 0 0 - B 0 1 1 0 0 0 1 1 C 0 1 0 - 0 - - - 1 0 1 1 - 1 0 0 1 1 1 - 0 - 1 0 1 - 1 1 0 - 1 1 1 0 A 0 0 1 1 Si possono sostituire due B 0 1 1 0 d.c.c. con altrettanti 1: C 0 1 - - 1 1 1 - 0 1
si forma la quaterna con cui si ottiene l’espressione semplificata: W = B
34
28
Architettura degli Elaboratori © 2009
EncoderEncoder
X0
X1
X2
X3
Y0
Y1Analogamente:Y1 = X2 + X3
X0 0 0 1 1X1 0 1 1 0X2 X3
0 0 - 1 - 0
0 1 1 - - -
1 1 - - - -
1 0 0 - - -
Y0 = X1 + X3
Y0
34
29
Architettura degli Elaboratori © 2009
MultiplexerMultiplexer
0 1 2 3 4 5 6 7
DEC 3/8
X0
X1
X7
C2 C1 C0
Y
34
30
Architettura degli Elaboratori © 2009
X
C1 C0
0 1 2 3
DEC 2/4
Y0
Y1
Y2
Y3
DemultiplexerDemultiplexer
34
31
Architettura degli Elaboratori © 2009
Sintesi a due livelliSintesi a due livelli
Sintesi come “somma di prodotti”
34
32
Architettura degli Elaboratori © 2009
Sintesi tramite PLASintesi tramite PLA
PLA = “Programmable Logic Array”
Tipicamente, p < 2i
34
33
Architettura degli Elaboratori © 2009
Sintesi tramite ROM (1 di 2)Sintesi tramite ROM (1 di 2)
34
34
Architettura degli Elaboratori © 2009
Sintesi tramite ROM (2 di 2)Sintesi tramite ROM (2 di 2)