Reti logiche
Logica a 2 livelli
Capitolo 2:
Logica combinatoria a due livelli
Reti Logiche
Contemporary Logic Design
Randy H. Katz
University of California, Berkeley
May 1993
Trasparenze tradotte da:
Luciano Lavagno
Universita’ di Udine
Settembre 1998
© R.H. Katz 2-1
Motivazione
Reti logiche
Logica a 2 livelli
Ulteriore estensione dei concetti del Capitolo 1:
• Tecniche di prototipazione rapida
Uso di strumenti CAD: espresso
• Tecniche di progetto adatte per diverse tecnologie
Transistor-Transistor Logic (TTL)
Complementary Metal on Oxide Silicon (CMOS)
• Diverse rappresentazioni di un progetto
Tabelle di verita’
Modelli statici di porte logiche
Forme d’onda dinamiche
© R.H. Katz 2-2
Sommario del capitolo
Reti logiche
Logica a 2 livelli
• Funzioni logiche ed interruttori
Not, AND, OR, NAND, NOR, XOR, XNOR
• Porte logiche
Leggi e teoremi dell’algebra booleana
Forme canoniche a due livelli
Funzioni non completamente specificate
• Semplificazione a due livelli
Cubi booleani
Mappe di Karnaugh
Metodo di Quine-Mc Cluskey
Metodo di “espresso”
© R.H. Katz 2-3
Reti logiche
Logica a 2 livelli
Funzioni logiche: algebra booleana
Struttura algebrica composta da:
Insieme di elementi B
Operazioni binarie {+, •}
Operazione unaria {'}
che soddisfano i seguenti assiomi (di Huntingdon):
1. B contiene almeno due elementi differenti
2. Chiusura: a,b in B,
(i) a + b in B
(ii) a • b in B
5. Distributive:
(i) a + (b • c) = (a + b) • (a + c)
(ii) a • (b + c) = a • b + a • c
3. Commutative: a,b in B,
(i) a + b = b + a
(ii) a • b = b • a
6. Complemento:
(i) a + a' = 1
(ii) a • a' = 0
4. Identita’: 0, 1 in B
(i) a + 0 = a
(ii) a • 1 = a
© R.H. Katz 2-4
Reti logiche
Logica a 2 livelli
Funzioni logiche: algebra booleana
B = {0,1}, + = OR, • = AND, ' = NOT e’ un’algebra booleana
verifichiamo che soddisfa gli assiomi:
P.es., commutativita’:
0 + 1 = 1 + 0?
0 • 1 = 1 • 0?
1=1
0=0
Teorema: ogni funzione logica che puo’ essere scritta come tabella di
verita’ puo’ essere scritta come un’espressione algebrica booleana ', +, •
Descrizione
Se X =0 alloraX' = 1
Se X=1 allora X' = 0
Tabella di verita’
Porta
X
X
X
0
1
X
1
0
Interruttori
Vero
NOT
X
Falso
X
Ripasso
dal
capitolo 1
Descrizione
Z = 1 se X ed Y
sono entrambi 1
Descrizione
Z = 1 se X o Y
X
(o entrambi) sono 1 Y
Porta
X
Y
Z
Porta
Z
Tabella di verita’
Interruttori
X Y Z
falso
0 0 0
0 1 0
1 0 0
vero
1 1 1
X
Y
Tabella di verita’
Interruttori
X
0
0
1
1
Y
0
1
0
1
Z
0
1
1
1
AND
X•Y
Falso
X+Y
Vero
X
OR
Y
© R.H. Katz 2-5
Funzioni logiche: dalle espressioni alle porte
Reti logiche
Logica a 2 livelli
Molti modi per passare da un’espressione ad
una rete logica
T2
P.es., Z = A' • B' • (C + D) = (A' • (B' • (C + D)))
T1
porta a tre ingressi
A
Z
B
B
T1
C
T
D
A
2
Z
C
D
Letterale: ogni variabile o complemento che appare in un’espressione
P.es., Z = A B' C + A' B + A' B C' + B' C
3 variabili, 10 letterali
© R.H. Katz 2-6
Reti logiche
Logica a 2 livelli
Funzioni logiche: NAND, NOR, XOR, XNOR
Esistono 16 funzioni logiche di 2 variabili:
X Y
0 0
0 1
1 0
1 1
F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 0 0 0 0 1 1
1
1
1
1
1
1
0 0 0 0 1 1 1 1 0 0
0
0
1
1
1
1
0 0 1 1 0 0 1 1 0 0
1
1
0
0
1
1
0 1 0 1 0 1 0 1 0 1
0
1
0
1
0
1
0
X• Y
X, X', Y, Y', X•Y, X+Y, 0, 1 sono
solo meta’ delle funzioni possibili
1
X
NAND
Y
X+Y
Y
Descrizione
Z = 1 se X e’ 0
o Y e’ 0
X
Tabella di verita’
Porta
X
Y
X Y Z
0 0 1
0 1 1
1 0 1
1 1 0
Z
Interruttori
Vero
X• Y
Falso
X
NOR
Descrizione
Z = 1 se sia X
sia Y sono 0
Tabella di verita’
Porta
X
Y
Z
X
0
0
1
1
Y
0
1
0
1
Z
1
0
0
0
Y
Interruttori
Vero
X+Y
Falso
X
Y
© R.H. Katz 2-7
Funzioni logiche: realizzazione con porte NAND, NOR
Reti logiche
Logica a 2 livelli
Le porte NAND, NOR sono molto piu’ numerose delle
AND, OR nei progetti normali
sono piu’ facili da costruire usando transistor
Qualsiasi espressione logica puo’ essere realizzata con porte
NAND, NOR, NOT
In realta’, NOT e’ inutile
(NOT = NAND o NOR con gli ingressi collegati insieme)
X
0
Y
0
X NOR Y
1
X
0
Y
0
X NAND Y
1
1
1
0
1
1
0
© R.H. Katz 2-8
Reti logiche
Logica a 2 livelli
Funzioni logiche: XOR, XNOR
XOR: X o Y ma non tutti e due (”disuguaglianza", "differenza")
XNOR: X ed Y sono uguali (”uguaglianza", ”coincidenza")
Descrizione
Z = 1 seX ha un valore
diverso da Y
Descrizione
Z = 1 seX ha lo stesso
valore di Y
Porta
Porta
X
Z
Y
Tabella di verita’
X
0
0
1
1
X
Z
Y
Tabella di verita’
Y
0
1
0
1
(a) XOR
X Y = X Y' + X' Y
Z
0
1
1
0
X
0
0
1
1
Y
0
1
0
1
Z
1
0
0
1
(b) XNOR
X  Y = X Y + X' Y'
© R.H. Katz 2-9
Funzioni logiche: perche’ semplificare?
Reti logiche
Logica a 2 livelli
Minimizzazione logica: ridurre la complessita’ di una realizzazione
con porte logiche
• ridurre il numero di letterali (ingressi di porte)
• ridurre il numero di porte
• ridurre il numero di livelli di porte
meno ingressi vuole dire porte piu’ veloci in alcune tecnologie (CMOS)
il fan-in (numero di ingressi) e’ limitato in alcune tecnologie (CMOS)
meno livelli di porte significano minori ritardi di propagazione
configurazioni con minimo ritardo di solito richiedono piu’ porte
il numero di porte (o di circuiti integrati) influenza il costo di produzione
Metodi tradizionali:
ridurre i ritardi aumentando le porte
Nuovi metodi:
bilanciare il minor ritardo ed il maggior numero di porte
© R.H. Katz 2-10
Funzioni logiche: realizzazioni differenti di una funzione
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Z
0
1
0
1
0
1
1
0
Reti logiche
Logica a 2 livelli
0 1 0 1 0 1
A
B
C
0
Realizzazione a due livelli
(gli invertitori non contano)
Z1
0
Realizzazione multi-livello
Vantaggio: meno
fan-in per porta
Z2
0
Z3
Porte logiche complesse: XOR
Vantaggio: minimo numero di porte
Numero di circuiti TTL:
Z1 - tre circuiti (1x 6 invertitori, 1x AND a 3 ingressi, 1x OR a 3 ingressi)
Z2 - tre circuiti (1x 6 invertitori, 1x AND a 2 ingressi, 1x OR a 2 ingressi)
Z3 - due circuiti (1x AND a 2 ingressi, 1x XOR a 2 ingressi)
© R.H. Katz 2-11
Funzioni logiche: verifica tramite simulazione
Reti logiche
Logica a 2 livelli
Per qualsiasi stimolo in ingresso, le tre realizzazioni hanno
praticamente lo stesso comportamento in termini di
forme d’onda
Leggere differenze dovute al diverso numero di livelli di porte
Le tre realizzazioni sono logicamente equivalenti
© R.H. Katz 2-12
Porte logiche: leggi dell'algebra booleana
Reti logiche
Logica a 2 livelli
Dualita’: l’espressione duale e’ ottenuta sostituendo le operazioni AND
con OR, le operazioni OR con AND, le constanti 0 con 1, ed
1 con 0s (i letterali non sono modificati).
Ogni risultato valido per un’espressione e’ valido anche per la duale!
I teoremi piu’ utili dell’algebra booleana:
Operazioni con 0 ed 1:
1D. X • 1 = X
1. X + 0 = X
2D. X • 0 = 0
2. X + 1 = 1
Idempotenza:
3. X + X = X
3D. X • X = X
Involuzione:
4. (X')' = X
Complemento:
5. X + X' = 1
5D. X • X' = 0
Commutativita’:
6. X + Y = Y + X
6D. X • Y = Y • X
© R.H. Katz 2-13
Reti logiche
Porte logiche: leggi dell'algebra booleana
Logica a 2 livelli
Associativita’:
7D. (X • Y) • Z = X • (Y • Z)
7. (X + Y) + Z = X + (Y + Z)
=X•Y•Z
=X+Y+Z
Distributivita’:
8. X • (Y+ Z) = (X • Y) + (X • Z)
8D. X + (Y• Z) = (X + Y) • (X + Z)
Teoremi della semplificazione:
9. X • Y + X • Y' = X
10. X + X • Y = X
11. (X + Y') • Y = X • Y
9D. (X + Y) • (X + Y') = X
10D. X • (X + Y) = X
11D. (X • Y') + Y = X + Y
Legge di DeMorgan:
12. (X + Y + Z + ...)' = X' • Y' • Z' • ... 12D. (X • Y • Z • ...) ' = X' + Y' + Z' + ...
13. {F(X1,X2,...,Xn,0,1,+,•)}' = {F(X1',X2',...,Xn',1,0,•,+)}
Dualita’:
14. (X + Y + Z + ...) D = X • Y • Z • ...
14D. (X •FY • Z • ...)D = X + Y + Z + ...
15. {F(X1,X2,...,Xn,0,1,+,•)}D = {F(X1,X2,...,Xn,1,0,•,+)}
Teoremi per moltiplicare e fattorizzare:
16. (X + Y) • (X' + Z) = X • Z + X' • Y 16D. X • Y + X' • Z = (X + Z) • (X' + Y)
Teorema del consenso
17. (X • Y) + (Y • Z) + (X' • Z) =
X • Y + X' • Z
17D. (X + Y) • (Y + Z) • (X' + Z) =
(X + Y) • (X' + Z)
© R.H. Katz 2-14
Porte logiche: leggi dell'algebra booleana
Dimostrazione di teoremi usando le leggi dell’algebra:
Reti logiche
Logica a 2 livelli
P.es. dimostrare il teorema: X • Y + X • Y' = X
P.es. dimostrare il teorema: X + X • Y
= X
© R.H. Katz 2-15
Porte logiche: leggi dell'algebra booleana
Dimostrazione di teoremi usando le leggi dell’algebra:
Reti logiche
Logica a 2 livelli
P.es. dimostrare il teorema : X • Y + X • Y' = X
distributivita’ (8)
X • Y + X •Y' = X • (Y + Y')
complementarieta’ (5)
X • (Y + Y')
= X • (1)
identita’ (1D)
X • (1)
=X
P.es. dimostrare il teorema : X + X • Y
= X
identita’ (1D)
X + X•Y
= X•1 + X•Y
distributivita’ (8)
X • 1 + X • Y = X • (1 + Y)
identita’ (2)
X • (1 + Y)
= X • (1)
identita’ (1)
X • (1)
= X
© R.H. Katz 2-16
Reti logiche
Logica a 2 livelli
Porte logiche: leggi dell'algebra booleana
Legge di DeMorgan
(X + Y)' = X' • Y'
NOR e’ come AND
con ingressi complementati
(X • Y)' = X' + Y'
NAND e’ come OR
con ingressi complementati
X
0
0
1
1
Y
0
1
0
1
X
1
1
0
0
Y
1
0
1
0
X
0
0
1
1
Y
0
1
0
1
X
1
1
0
0
Y
1
0
1
0
X +Y
1
0
0
0
X•Y
1
0
0
0
X•Y X +Y
1
1
1
1
1
1
0
0
Le legge di DeMorgan puo’ essere usata per convertire espressioni AND/OR
ad espressioni OR/AND
Esempi:
Z = A' B' C + A' B C + A B' C + A B C'
Z' = (A + B + C') • (A + B' + C') • (A' + B + C') • (A' + B' + C)
© R.H. Katz 2-17
Porte logiche: leggi dell'algebra booleana
Reti logiche
Logica a 2 livelli
Usare le leggi ed i teoremi per semplificare le equazioni booleane
Esempio: la funzione di riporto in uscita del sommatore
Cout = A' B Cin + A B' Cin + A B Cin' + A B Cin
© R.H. Katz 2-18
Reti logiche
Logica a 2 livelli
Porte logiche: leggi dell'algebra booleana
Usare le leggi ed i teoremi per semplificare le equazioni booleane
Esempio: la funzione di riporto in uscita del sommatore
identita’
Cout = A' B Cin + A B' Cin + A B Cin' + A B Cin
= A' B Cin + A B' Cin + A B Cin' + A B Cin + A B Cin
= A' B Cin + A B Cin + A B' Cin + A B Cin' + A B Cin
= (A' + A) B Cin + A B' Cin + A B Cin' + A B Cin
= (1) B Cin + A B' Cin + A B Cin' + A B Cin
= B Cin + A B' Cin + A B Cin' + A B Cin + A B Cin
= B Cin + A B' Cin + A B Cin + A B Cin' + A B Cin
= B Cin + A (B' + B) Cin + A B Cin' + A B Cin
associativita’
= B Cin + A (1) Cin + A B Cin' + A B Cin
= B Cin + A Cin + A B (Cin' + Cin)
= B Cin + A Cin + A B (1)
= B Cin + A Cin + A B
© R.H. Katz 2-19
Reti logiche
Logica a 2 livelli
Porte logiche: equivalenze usando gli interruttori
A + 0= A
A • A=A
A + 1= 1
A+A =A
A
A
A
=
A
=
A
A
A
A
0
1
=
=
1
A
Identita’
Idempotenza
XY + XY = X
A• A =0
A+A=1
A
A
A
A
=
=
1
0
Complementarieta’
X + XY = X
X
Y
X
Y
X
Y
X
=
=
X
X
Teoremi di semplificazione
© R.H. Katz 2-20
Porte logiche: forme canoniche a due livelli
Reti logiche
Logica a 2 livelli
La tabella di verita’ e’ una “firma” univoca per le funzioni logiche
Diverse espressioni (e realizzazioni) possono avere la stessa
tabella di verita’
Forma canonica: forma standard per un’equazione booleana
fornisce una firma univoca in forma algebrica
Forma in somma di prodotti
anche detta forma normale disgiuntiva o espansione in mintermini
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
F
0
0
0
1
1
1
1
1
F
1
1
1
0
0
0
0
0
011
100
101
110
111
F = A' B C + A B' C' + A B' C + A B C' + A B C
F' = A' B' C' + A' B' C + A' B C'
© R.H. Katz 2-21
Porte logiche: forme canoniche a due livelli
Somma di prodotti
A
B
C
Minterms
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
A
A
A
A
A
A
A
A
B
B
B
B
B
B
B
B
C = m0
C = m1
C = m2
C = m3
C = m4
C = m5
C = m6
C = m7
Notazione abbreviata per
mintermini di 3 variabili
mintermine (uno speciale termine prodotto)
prodotto (AND) di letterali in cui ogni
variabile appare esattamente una volta,
complementata o no (ma non tutte e due)
F in forma canonica:
F(A,B,C) = m(3,4,5,6,7)
= m3 + m4 + m5 + m6 + m7
= A' B C + A B' C' + A B' C
+ A B C' + A B C
forma canonica e forma minima
F = A B' (C + C') + A' B C + A B (C' + C)
= A B' + A' B C + A B
= A (B' + B) + A' B C
B
C
Reti logiche
Logica a 2 livelli
F
A
Realizzazione
a 2 livelli AND/OR
= A + A' B C
=A + BC
F = (A + B C)' = A' (B' + C') = A' B' + A' C'
© R.H. Katz 2-22
Porte logiche: forme canoniche a due livelli
Reti logiche
Logica a 2 livelli
Prodotti di somme / forma canonica congiuntiva / espansione in maxtermini
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
Maxterms
A + B + C = M0
A + B + C = M1
A + B + C = M2
A + B + C = M3
A + B + C = M4
A + B + C = M5
A + B + C = M6
A + B + C = M7
maxtermine (uno speciale termine somma):
somma (OR) di letterali in cui ogni
variabile appare esattamente una volta,
complementata o no (ma non tutte e due)
Forma di maxtermini:
Trovare le righe in cui F e’ 0
0 nella colonna di ingresso implica
letterale non complementato
1 nella colonna di ingresso implica
letterale complementato
Notazione abbreviata per
maxtermini di 3 variabili
F(A,B,C) = M(0,1,2)
= (A + B + C) (A + B + C') (A + B' + C)
F’(A,B,C) = M(3,4,5,6,7)
= (A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' + C')
© R.H. Katz 2-23
Porte logiche: forme canoniche a due livelli
Somme di prodotti, prodotti di somme e legge di DeMorgan
Reti logiche
Logica a 2 livelli
F' = A' B' C' + A' B' C + A' B C'
Usare DeMorgan per ottenere F:
(F')' = (A' B' C' + A' B' C + A' B C')'
F = (A + B + C) (A + B + C') (A + B' + C)
F' = (A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' + C')
Usare DeMorgan per ottenere F:
(F')' = {(A + B' + C') (A' + B + C) (A' + B + C') (A' + B' + C) (A' + B' + C')}'
F = A' B C + A B' C' + A B' C + A B C' + A B C
© R.H. Katz 2-24
Porte logiche: forme canoniche a due livelli
Reti logiche
Logica a 2 livelli
Quattro realizzazioni alternative di F:
A
B
Forma canonica in somme di prodotti
F1
C
Forma minimizzata in somme di prodotti
F2
Forma canonica in prodotti di somme
F3
Forma minimizzata in prodotti di somme
F4
© R.H. Katz 2-25
Porte logiche: forme canoniche a due livelli
Reti logiche
Logica a 2 livelli
Verifica per simulazione delle quattro alternative
100
200
A
B
C
F1
F2
F3
F4
Otto combinazioni diverse
di tre ingressi
Eccetto per alee dovute ai ritardi,
le forme d’onda delle quattro
realizzazioni sono quasi identiche
© R.H. Katz 2-26
Porte logiche: forme canoniche a due livelli
Trasformazioni tra le varie forme
1.
Reti logiche
Logica a 2 livelli
Conversione da mintermini a maxtermini:
riscrivere la notazione abbreviata a mintermini con quella a
maxtermini e sostituire gli indici con quelli non usati
E.g., F(A,B,C) = m(3,4,5,6,7) = M(0,1,2)
2.
Conversione da maxtermini a mintermini:
riscrivere la notazione abbreviata a maxtermini con quella a
mintermini e sostituire gli indici con quelli non usati
E.g., F(A,B,C) = M(0,1,2) = m(3,4,5,6,7)
3.
Da espansione in mintermini di F ad espansione in mintermini di F':
nella notazione abbreviata, usare gli indici non usati in F
E.g., F(A,B,C) = m(3,4,5,6,7)
= M(0,1,2)
4.
F'(A,B,C) = m(0,1,2)
= M(3,4,5,6,7)
Da espansione in mintermini di F ad espansione in maxtermini di F':
riscrivere usando i maxtermini, usando gli stessi indici di F
E.g., F(A,B,C) = m(3,4,5,6,7)
= M(0,1,2)
F'(A,B,C) = M(3,4,5,6,7)
= m(0,1,2)
© R.H. Katz 2-27
Reti logiche
Logica a 2 livelli
Porte logiche: logica positiva e negativa
Convenzione normale: logica positiva / attiva alta
tensione bassa = 0; tensione alta = 1
Talvolta si usa la convenzione opposta: logica negativa / attiva bassa
F
Tavola di verita’ usando tensioni Logica positiva
A
bassa
bassa
alta
alta
B
bassa
alta
bassa
alta
F
bassa
bassa
bassa
alta
Comportamento in
termini di livelli elettrici
A
0
0
1
1
B
0
1
0
1
Logica negativa
F
0
0
0
1
A
1
1
0
0
B
1
0
1
0
F
1
1
1
0
Due interpretazioni alternative
Logica positiva: AND
Logica negativa: OR
Operatori duali
© R.H. Katz 2-28
Reti logiche
Logica a 2 livelli
Porte logiche: logica positiva e negativa
Conversione da logica positiva a negativa
F
Tavola di verita’ usando tensioni Logica positiva
A
bassa
bassa
alta
alta
B
bassa
alta
bassa
alta
F
alta
bassa
bassa
bassa
A
0
0
1
1
B
0
1
0
1
Logica negativa
F
1
0
0
0
A
1
1
0
0
B
1
0
1
0
F
0
1
1
1
Logica positiva NOR: A + B = A • B
Logica negativa NAND: A • B = A + B
Operazioni duali:
AND diventa OR, OR diventa AND
il complemento rimane tale e quale
© R.H. Katz 2-29
Reti logiche
Logica a 2 livelli
Porte logiche: logica positiva e negativa
Esempio pratico
Usare OR se gli ingressi
sono in logica negativa
Change
Reques t
(active high)
Change
Reques t
(active low )
Ac tiv e
High
Usare AND
se attivo alto
Ac tiv e
Low
Change
Lights
(active high)
Timer
Expired
(active high)
(a)
Timer
Expired
(active low )
(b)
Change
Reques t
(active low )
Change
Reques t
(active low )
Change
Lights
(active low )
Differenza tra
polarita’ di
ingressi ed uscite
Timer
Expired
(active low )
(c )
Bubble
Mismatch
Change
Lights
(active low )
Change
Lights
(active low )
Timer
Expired
(active low )
Bubble
Match
(d)
Usare NAND con ingressi
invertiti se logica negativa
© R.H. Katz 2-30
Porte logiche: funzioni non completamente specificate
Funzioni di n ingressi hanno 2n
Reti logiche
Logica a 2 livelli
possibili configurazioni di ingresso
Data una funzione, non tutte le configurazioni di ingresso sono possibili
Questo fatto puo’ essere sfruttato durante la minimizzazione!
P.es. incrementare di un una cifra BCD (Binary Coded Decimal)
I numeri BCD codificano le cifre 0 - 9
con le stringhe di bit 00002 - 10012
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
W
0
0
0
0
0
0
0
1
1
0
X
X
X
X
X
X
X
0
0
0
1
1
1
1
0
0
0
X
X
X
X
X
X
Y
0
1
1
0
0
1
1
0
0
0
X
X
X
X
X
X
Z
1
0
1
0
1
0
1
0
1
0
X
X
X
X
X
X
Off-set di W
On-set di W
Don't care (DC) set di W
Queste stringhe di bit
non dovrebbero mai
comparire in pratica,
quindi “non importano”
(sono dei "Don't Care”)
© R.H. Katz 2-31
Porte logiche: funzioni non completamente specificate
Don't care e forme canoniche
Reti logiche
Logica a 2 livelli
Forme canoniche della funzione incremento di 1 in BCD:
Z = m0 + m2 + m4 + m6 + m8 + d10 + d11 + d12 + d13 + d14 + d15
Z = m(0, 2, 4, 6, 8) + d(10, 11, 12 ,13, 14, 15)
Z = M1 • M3 • M5 • M7 • M9 • D10 • D11 • D12 • D13 • D14 • D15
Z= M(1, 3, 5, 7, 9) • D(10, 11, 12, 13, 14 ,15)
© R.H. Katz 2-32
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Semplificazione algebrica:
non e’ un algoritmo (procedura sistematica)
come fare a sapere che e’ stata trovata la forma minima?
Strumenti CAD:
soluzioni esatte richiedono molto tempo di calcolo,
specialmente con funzioni con molti ingressi (>10)
in pratica si usano metodi “euristici”:
“tirano ad indovinare” (con criterio) per ridurre i tempi di calcolo
forniscono soluzioni “buone”, non necessariamente le migliori
Serve ancora studiare i metodi manuali:
capire come funzionano i programmi CAD,
i loro vantaggi e svantaggi
riuscire a controllare i risultati (per esempi piccoli…)
durante gli esami non potrete usare un calcolatore!
© R.H. Katz 2-33
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Strumento base: il teorema di unificazione — A (B' + B) = A
A
0
0
1
1
B
0
1
0
1
F
0
0
1
1
F = A B' + A B = A (B' + B) = A
I valori di B cambiano tra righe dell’on-set
B puo’ essere eliminata, A rimane
I valori di A non cambiano tra righe dell’on-set
A
0
0
1
1
B
0
1
0
1
G
1
0
1
0
G = A' B' + A B' = (A' + A) B' = B'
I valori di B non cambiano tra righe dell’on-set
A puo’ essere eliminata, B rimane
I valori di A cambiano tra righe dell’on-set
Essenza della semplificazione:
trovare sottoinsiemi di due elementi dell’on-set in cui solo una
variabile cambia valore. La variabile puo’ essere eliminata!
© R.H. Katz 2-34
Porte logiche: semplificazione a due livelli
Cubi booleani
Tecnica visuale per identificare quando
si puo’ usare il teorema dell’unificazione
0
1
XYZ
111
011
X
Un altro modo di rappresentare
la tabella di verita’
1-cube
010
XY
11
01
110
Y
Y
00
001
Z
101
000
10
2-cube
n variabili di ingresso =
“cubo” ad n dimensioni
100
X
X
Reti logiche
Logica a 2 livelli
3-cube
WXYZ
1011
1111
0111
0011
1010
1110
0010
0110
Y
0001
1001
0101
1101
Z
1100
W
0000
X
1000
0100
4-cube
© R.H. Katz 2-35
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Come trasformare tabelle di verita’ in cubi booleani
ON-set = vertici pieni
OFF-set = vertici vuoti
DC-set = vertici ad X
l’espressione ridotta
(termine prodotto)
contiene n-1 variabili
F
01
11
Cubo con n-1 dimensioni
A e’ vera e non cambia
B
B cambia
00
10
A
G
01
A cambia
B e’ falsa e non cambia
11
B
00
10
A
© R.H. Katz 2-36
Porte logiche: semplificazione a due livelli
Esempio a tre variabili: riporto in uscita del sommatore
Reti logiche
Logica a 2 livelli
(A' + A) B Cin
011
A B Cin
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Cout
0
0
0
1
0
1
1
1
111
010
L’ON-set e’ coperto
dall’OR dei sotto-cubi
di dimensione piu’ piccola
110
001
B
A B (Cin' + Cin)
101
Cin
000
100
A
A (B + B') Cin
Cout = B Cin + A B + A Cin
© R.H. Katz 2-37
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Sotto-cubi di dimensione maggiore di due
011
111
L’on-set costituisce un rettangolo,
cioe’ un cubo a due dimensioni
010
110
B
001
101
C
000
A
F(A,B,C) = m(4,5,6,7)
rappresenta un’espressione (prodotto)
con una sola variabile,
cioe’ 3 dimensioni - 2 dimensioni
100
A e’ vera e non cambia
B e C cambiano
Questo sottocubo rappresenta
il letterale A
© R.H. Katz 2-38
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
In un 3-cubo (cubo a 3 dimensioni):
uno 0-cubo (un solo vertice) e’ un termine con tre letterali
un 1-cubo (una linea con due vertici) e’ un termine con due letterali
un 2-cubo (un piano con quattro vertici) e’ un termine con un letterale
un 3-cubo (un cubo con otto nodi) e’ la costante 1
In generale,
un m-sottocubo dentro un n-cubo (m < n) e’ un termine con
n - m letterali
© R.H. Katz 2-39
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Metodo delle mappe di Karnaugh
Difficile disegnare cubi con piu’ di 4 dimensioni
La mappa di Karnaugh e’ un metodo alternativo di disegnarli,
che serve a visualizzare le adiacenze fino a 6 dimensioni
Oltre 6 variabili, servono i calcolatori...
A
0
B
1
0
mappa a
2 variabili
0
1
1
A
AB
00
CD
2
00
01
11
00
0
4
12
8
1
5
13
9
3
7
15
11
2
6
14
10
3
01
A
AB
C
mappa a
3 variabili
00
01
11
11
10
10
0
1
C
0
2
6
4
1
3
7
5
B
D
mappa a
4 variabili
B
Schema di numerazione: 00, 01, 11, 10
Codice di Gray — cambia solo 1 bit da una
parola alla successiva
© R.H. Katz 2-40
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Metodo delle mappe di Karnaugh
Adiacenze nella mappa
00
C
01
11
111
011
A
AB
10
010
0
000
010
110
100
1
001
011
111
101
110
B
001
101
C
B
000
100
A
Richiudere:
il lato sinistro sul destro
l’ultima riga sulla prima
© R.H. Katz 2-41
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempi di applicazione del metodo delle mappe
A
0
1
0
0
1
1
0
1
B
A
A vera, non cambia
B varia
B falsa, non cambia
A varia
F=
1
0
1
1
1
0
0
G=
A
AB
00
01
11
10
0
0
0
1
0
1
0
1
1
1
Cin
0
B
B
Cout =
AB
C
A
00
01
11
10
0
0
0
1
1
1
0
0
1
1
B
F(A,B,C) =
© R.H. Katz 2-42
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempi di applicazione del metodo delle mappe
A
0
1
0
0
1
1
0
1
B
A
A vera, non cambia
B varia
0
1
0
1
1
1
0
0
B
B falsa, non cambia
A varia
F=A
G = B'
A
AB
00
01
11
10
0
0
0
1
0
1
0
1
1
1
Cin
B
Cout = A B + B Cin + A Cin
AB
C
A
00
01
11
10
0
0
0
1
1
1
0
0
1
1
B
F(A,B,C) = A
© R.H. Katz 2-43
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Altri esempi del metodo delle mappe, in 3 variabili
A
AB
C
0
00
01
11
10
1
0
0
1
F(A,B,C) = m(0,4,5,7)
F=
1
0
0
1
1
B
AB
C
A
00
01
11
10
0
0
1
1
0
F'(A,B,C) = m(1,2,3,6)
1
1
1
0
0
F' =
F' sostituisce soltanto 1 con 0 e viceversa
B
© R.H. Katz 2-44
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Altri esempi del metodo delle mappe, in 3 variabili
A
AB
C
0
00
01
11
10
1
0
0
1
F(A,B,C) = m(0,4,5,7)
F = B' C' + A C
1
0
0
1
1
Nella mappa, l’adiacenza continua tra
sinistra e destra e tra alto e basso
B
AB
C
0
A
00
01
11
10
0
1
1
0
F' sostituisce soltanto 1 con 0 e viceversa
F'(A,B,C) = m(1,2,3,6)
1
1
1
0
0
F' = B C' + A' C
B
Confrontate con il metodo che usa DeMorgan
e l’algebra booleana per minimizzare il complemento!
© R.H. Katz 2-45
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Altri esempi del metodo delle mappe in 4 variabili
AB
00
CD
F(A,B,C,D) = m(0,2,3,5,6,7,8,10,11,14,15)
A
01
11
10
00
1
0
0
1
01
0
1
0
0
F=
D
11
1
1
1
1
10
1
1
1
1
C
B
© R.H. Katz 2-46
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Altri esempi del metodo delle mappe in 4 variabili
A
AB
00
CD
01
11
10
00
1
0
0
1
01
0
1
0
0
F(A,B,C,D) = m(0,2,3,5,6,7,8,10,11,14,15)
F = C + A' B D + B' D'
Trovate il minimo numero
di cubi piu’ grandi possibile
che coprano tutto l’ON-set
D
11
1
1
1
1
10
1
1
1
1
C
B
1011
1111
0111
0011
1010
1110
0010
0110
1001
0001
C
D
0000
1100
A
B
1101
0101
Adiacenza degli angoli
della mappa
per 4 variabili
1000
0100
© R.H. Katz 2-47
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Metodo delle mappe: copertura degli zeri
AB
00
CD
A
01
11
10
00
1
0
0
1
01
0
1
0
0
F = (B + C + D) (A + C + D) (B + C + D)
D
11
1
1
1
1
10
1
1
1
1
C
B
Sostituendo F con F, 0 diventa 1 e viceversa
F=BCD+ACD+BCD
F=BCD+ACD+BCD
F = (B + C + D) (A + C + D) (B + C + D)
© R.H. Katz 2-48
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Metodo delle mappe: don’t care
I don’t care possono essere trattati sia come 0 sia come 1,
a seconda di come sia piu’ vantaggioso
AB
00
CD
A
01
11
10
00
0
0
X
0
F(A,B,C,D) = m(1,3,5,7,9) + d(6,12,13)
01
1
1
X
1
F=
senza don’t care
D
11
1
1
0
0
10
0
X
0
0
F=
con don’t care
C
B
© R.H. Katz 2-49
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Metodo delle mappe: don’t care
I don’t care possono essere trattati sia come 0 sia come 1,
a seconda di come sia piu’ vantaggioso
AB
00
CD
A
01
11
10
F(A,B,C,D) = m(1,3,5,7,9) + d(6,12,13)
00
0
0
X
0
F = A'D + B' C' D senza don’t care
01
1
1
X
1
F = C' D + A' D con don’t care
D
11
1
1
0
0
10
0
X
0
0
C
B
Trattando questo DC come "1", possiamo
creare un 2-cubo invece di uno 0-cubo
A
AB
CD
00
01
11
10
00
0
0
X
0
01
1
1
X
1
In forma PdS: F = D (A' + C')
Stessa funzione di prima, ma
meno letterali!
D
11
1
1
0
0
10
0
X
0
0
C
B
© R.H. Katz 2-50
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio di progetto: comparatore a 2 bit
A
B
C
D
N1
F1 A B = C D
=, >, < F2 A B < C D
F3 A B > C D
N2
A
0
0
1
1
B C D
0 0 0
0 1
1 0
1 1
1 0 0
0 1
1 0
1 1
0 0 0
0 1
1 0
1 1
1 0 0
0 1
1 0
1 1
F1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
F2
0
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
F3
0
0
0
0
1
0
0
0
1
1
0
0
1
1
1
0
Diagramma a blocchi
e tabella di verita’
Mappa a 4 variabili
per ognuna delle
3 funzioni
© R.H. Katz 2-51
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio di progetto: comparatore a 2 bit
AB
CD
A
00
01
11
10
00
1
0
0
0
01
0
1
0
0
AB
CD
A
00
01
11
10
00
0
0
0
0
01
1
0
0
0
D
11
0
0
1
0
10
0
0
0
1
C
A
00
01
11
10
00
0
1
1
1
01
0
0
1
1
D
11
1
1
0
1
10
1
1
0
0
C
B
K-map for F1
AB
CD
D
11
0
0
0
0
10
0
0
1
0
C
B
K-map for F2
B
K-map for F3
F1 =
F2 =
F3 =
© R.H. Katz 2-52
Reti logiche
Logica a 2 livelli
Porte logiche:semplificazione a due livelli
Esempio di progetto: comparatore a 2 bit
AB
CD
A
00
01
11
10
00
1
0
0
0
01
0
1
0
0
AB
CD
A
00
01
11
10
00
0
0
0
0
01
1
0
0
0
D
11
0
0
1
0
10
0
0
0
1
C
A
00
01
11
10
00
0
1
1
1
01
0
0
1
1
D
11
1
1
0
1
10
1
1
0
0
C
B
K-map for F1
AB
CD
D
11
0
0
0
0
10
0
0
1
0
C
B
K-map for F2
B
K-map for F3
F1 = A' B' C' D' + A' B C' D + A B C D + A B' C D'
F2 = A' B' D + A' C + B’ C D
F3 = B C' D' + A C' + A B D'
(A xnor B) (C xnor D)
© R.H. Katz 2-53
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Esempio di progetto: sommatore a 2 bit
A
B
C
D
N1
+
N2
N3
X
Y
Z
A B C D
0 0 0 0
0 1
1 0
1 1
0 1 0 0
0 1
1 0
1 1
1 0 0 0
0 1
1 0
1 1
1 1 0 0
0 1
1 0
1 1
X Y Z
0 0 0
0 0 1
0 1 0
0 1 1
0 0 1
0 1 0
0 1 1
1 0 0
0 1 0
0 1 1
1 0 0
1 0 1
0 1 1
1 0 0
1 0 1
1 1 0
Schema a blocchi
e tabella di verita’
Mappa a 4 variabili
per ognuna delle
3 funzioni
© R.H. Katz 2-54
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio di progetto: sommatore a 2 bit
AB
00
CD
A
01
11
10
AB
CD
A
00
01
11
10
AB
00
CD
A
01
11
10
00
0
0
0
0
00
0
0
1
1
00
0
1
1
0
01
0
0
1
0
01
0
1
0
1
01
1
0
0
1
D
11
0
1
1
1
10
0
0
1
1
C
D
11
1
0
1
0
10
1
1
0
0
C
D
11
1
0
0
1
10
0
1
1
0
C
B
B
B
K-map for X
K-map for Y
K-map for Z
X=
Z=
Y=
© R.H. Katz 2-55
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio di progetto: sommatore a 2 bit
AB
00
CD
A
A
01
11
10
AB
CD
00
0
0
1
1
01
0
1
0
1
00
0
0
0
0
01
0
0
1
0
00
01
11
10
D
11
0
1
1
1
10
0
0
1
1
C
AB
00
CD
A
01
11
10
00
0
1
1
0
01
1
0
0
1
D
11
1
0
1
0
10
1
1
0
0
C
D
11
1
0
0
1
10
0
1
1
0
C
B
B
B
K-map for X
K-map for Y
K-map for Z
X=AC + BCD + ABD
Z = B D' + B' D = B xor D
Gli 1 sulla diagonale suggeriscono XOR!
realizzazione a 2 livelli non e’ il meglio
Y = A' B' C + A B' C' + A' B C' D + A' B C D' + A B C' D' + A B C D
= B' (A xor C) + A' B (C xor D) + A B (C xnor D)
= B' (A xor C) + B (A xor B xor C)
Si possono usare
meno porte se l’XOR
e’ disponibile
© R.H. Katz 2-56
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio di progetto: sommatore a 2 bit
A
B
\A \B \C \D
Due realizzazioni di Y,
con e senza XOR
C
D
Y1
Nota: spesso l’XOR
e’ realizzato con
4 NAND!
X
X XOR Y
Y
Y2
© R.H. Katz 2-57
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio di progetto: incremento di 1 in BCD
AB
00
CD
W
A
01
11
10
00
0
0
X
1
01
0
0
X
0
AB
00
CD
D
11
0
1
X
X
10
0
0
X
X
X
C
A
01
11
10
00
0
1
X
0
01
0
1
X
0
D
11
1
0
X
X
10
0
1
X
X
C
B
AB
00
CD
Y
B
A
01
11
10
00
0
0
X
0
01
1
1
X
0
AB
00
CD
D
11
0
0
X
X
10
1
1
X
X
C
Z
A
01
11
10
00
1
1
X
1
01
0
0
X
0
D
11
0
0
X
X
10
1
1
X
X
C
B
B
W=
Y=
X=
Z=
© R.H. Katz 2-58
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
AB
00
CD
W
A
01
11
10
00
0
0
X
1
01
0
0
X
0
AB
00
CD
D
11
0
1
X
X
10
0
0
X
X
X
C
A
01
11
10
00
0
1
X
0
01
0
1
X
0
D
11
1
0
X
X
10
0
1
X
X
C
B
AB
00
CD
Y
B
A
01
11
10
00
0
0
X
0
01
1
1
X
0
AB
00
CD
D
11
0
0
X
X
10
1
1
X
X
C
Z
A
01
11
10
00
1
1
X
1
01
0
0
X
0
D
11
0
0
X
X
10
1
1
X
X
C
B
B
W = B C D + A D'
Y = A' C' D + C D'
X = B C' + B D' + B' C D
Z = D'
© R.H. Katz 2-59
Porte logiche: semplificazione a due livelli
Definizione dei termini
Reti logiche
Logica a 2 livelli
implicante: elemento dell’ON-set, o gruppo di elementi che
possono essere combinati in una mappa
(termine prodotto in SdP)
implicante primo: implicante che non e’ contenuto in un altro
implicante
(non puo’ essere combinato con un altro implicante)
implicante (primo) essenziale: implicante primo che copre un
elemento dell’ON-set non coperto da nessun altro
Obiettivo:
“far crescere” gli implicanti fino a diventare primi
coprire l’ON-set con il minimo numero di implicanti
gli essenziali devono essere presenti in ogni copertura
© R.H. Katz 2-60
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempi per spiegare i termini
AB
00
CD
A
01
11
10
00
0
1
1
0
01
1
1
1
0
6 implicanti primi:
A' B' D, B C', A C, A' C' D, A B, B' C D
D
11
1
0
1
1
10
0
0
1
1
essenziali
Copertura minima = B C' + A C + A' B' D
C
B
AB
00
CD
A
01
11
10
00
0
0
1
0
01
1
1
1
0
5 implicanti primi:
B D, A B C', A C D, A' B C, A' C' D
D
11
0
1
1
1
10
0
1
0
0
C
essenziali
Gli implicanti essenziali sono la copertura minima
B
© R.H. Katz 2-61
Porte logiche: semplificazione a due livelli
Reti logiche
Logica a 2 livelli
Un altro esempio
AB
00
CD
A
01
11
10
00
0
0
0
0
01
0
1
1
0
Implicanti primi:
B D, C D, A C, B' C
Essenziali
D
11
1
1
1
1
10
1
0
1
1
Gli implicanti essenziali sono la copertura minima
C
B
© R.H. Katz 2-62
Reti logiche
Porte logiche: semplificazione a due livelli
Logica a 2 livelli
Algoritmo: generare una somma di prodotti minima da una mappa
Passo 1: Scegliere un elemento dell’ON-set non ancora coperto
Passo 2: Trovare tutti i massimi gruppi di 1 ed X adiacenti all’elemento.
(ricordandosi di usare le adiacenze destra/sinistra e alto/basso)
Questo crea gli implicanti primi (numero di elementi e’ sempre
una potenza di 2)
Ripetere i passi 1 e 2 per trovare tutti gli implicanti primi
Passo 3: Riconsiderare ogni 1 nella mappa. Se e’ coperto da un solo primo,
allora il primo e’ essenziale e sara’ nella copertura. Ogni 1 coperto
non deve piu’ essere considerato.
Passo 4: Se rimangono 1 non coperti, coprirli con un numero minimo
di implicanti primi.
© R.H. Katz 2-63
Porte logiche: semplificazione a due livelli
Esempio: ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15)
Reti logiche
Logica a 2 livelli
A
AB
CD
00
01
11
10
00
X
1
0
1
01
0
1
1
1
D
11
0
X
X
0
10
0
1
0
1
C
B
Mappa iniziale
© R.H. Katz 2-64
Porte logiche: semplificazione a due livelli
Esempio : ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15)
A
AB
CD
00
01
11
10
00
X
1
0
1
01
0
1
1
1
AB
00
CD
A
01
11
10
00
X
1
0
1
01
0
1
1
1
D
11
0
X
X
0
10
0
1
0
1
C
Reti logiche
Logica a 2 livelli
D
11
0
X
X
0
10
0
1
0
1
C
B
Mappa iniziale
B
Primi intorno a
A' B C' D'
© R.H. Katz 2-65
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio : ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15)
A
AB
CD
00
01
11
10
00
X
1
0
1
01
0
1
1
1
AB
00
CD
A
01
11
10
AB
CD
00
X
1
0
1
01
0
1
1
1
D
11
0
X
X
0
10
0
1
0
1
C
Mappa iniziale
00
01
11
10
00
X
1
0
1
01
0
1
1
1
D
D
11
0
X
X
0
10
0
1
0
1
11
0
X
X
0
10
0
1
0
1
C
C
B
A
B
Primi intorno a
A' B C' D'
B
Primi intorno a
A B C' D
© R.H. Katz 2-66
Porte logiche: semplificazione a due livelli
Esempio
AB
00
CD
Reti logiche
Logica a 2 livelli
A
01
11
10
00
X
1
0
1
01
0
1
1
1
D
11
0
X
X
0
10
0
1
0
1
C
B
Primi intorno a
A B C' D
© R.H. Katz 2-67
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio
AB
00
CD
A
01
11
10
00
X
1
0
1
01
0
1
1
1
AB
00
CD
A
01
11
10
00
X
1
0
1
01
0
1
1
1
D
11
0
X
X
0
10
0
1
0
1
C
D
11
0
X
X
0
10
0
1
0
1
C
B
Primi intorno a
A B C' D
B
Primi intorno a
A B' C' D'
© R.H. Katz 2-68
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Esempio
AB
00
CD
A
01
11
10
00
X
1
0
1
01
0
1
1
1
AB
00
CD
A
01
11
10
00
X
1
0
1
01
0
1
1
1
D
11
0
X
X
0
10
0
1
0
1
C
Primi intorno a
A B C' D
A
01
11
10
00
X
1
0
1
01
0
1
1
1
D
11
0
X
X
0
10
0
1
0
1
C
B
AB
00
CD
D
11
0
X
X
0
10
0
1
0
1
C
B
Primi intorno a
A B' C' D'
B
Primi essenziali
e copertura minima
© R.H. Katz 2-69
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Mappe a 5 variabili
BC
DE
00 01 11
10
A =0
00
0
4
12
8
01
1
5
13
9
11
3
7 15 11
10 2
6
14 10
BC
DE
00
A=0
A =1
00
01
11
1
11
1
1
1
1
10
10
1
01
1
BC
DE
00
BC
00
01
11
16
20
28
10
24
01 17 21 29 25
11
19 23 31 27
10
18 22 30 26
DE
00
A=1
00
1
01 1
11
1
01
1
11
10
1
1
1
10
ƒ(A,B,C,D,E) = m(2,5,7,8,10,
13,15,17,19,21,23,24,29 31)
=
© R.H. Katz 2-70
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Mappe a 5 variabili
BC
DE
00 01 11
10
A =0
00
0
4
12
8
01
1
5
13
9
11
3
7 15 11
10 2
6
14 10
BC
DE
00
A=0
A =1
00
01
11
1
11
1
1
1
1
10
10
1
01
1
BC
BC
DE
00
00
01
11
16
20
28
DE
00
10
24
01 17 21 29 25
11
19 23 31 27
10
18 22 30 26
A=1
00
1
01 1
11
1
01
1
11
10
1
1
1
10
ƒ(A,B,C,D,E) = m(2,5,7,8,10,
13,15,17,19,21,23,24,29 31)
= C E + A B' E + B C' D' E'
+ A' C' D E'
© R.H. Katz 2-71
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Mappe a 6 variabili
CD
EF
00
00
CD
EF
00
AB=00
01
01
11
10
0
4
12
8
1
11
10
00
5
3
7
2
6
13
15
14
AB=00
10 1
11
10
01
11
10
01
11
16
20
28
17
19
18
21
23
22
29
31
30
26
CD
01
11
11
32
36
44
33
35
10 34
37
39
38
45
47
46
10
40
41
43
42
11
10
1
11
27
01
01
01
24
25
00
1
CD
EF
00
00
AB=01
10
CD
EF
00 01
11
10
00
AB =11
48 52
60 56
01 49 53
61 57
11
51 55
63 59
10 50 54
62 58
EF
AB =10 00
10
1
11
9
00
11
01
CD
EF
AB =01 00
01
ƒ(A,B,C,D,E,F) =
m(2,8,10,18,24,
26,34,37,42,45,50,
53,58,61)
=
10 1
1
CD
EF
00
00
AB=11
01
1
01
11
10
1
11
10
1
1
CD
EF
00 01 11
AB=10 00
01
1
1
10
11
10
1
1
© R.H. Katz 2-72
Reti logiche
Logica a 2 livelli
Porte logiche: semplificazione a due livelli
Mappe a 6 variabili
CD
EF
00
00
CD
EF
00
AB=00
01
01
11
10
0
4
12
8
1
11
10
00
5
3
7
2
6
13
15
14
AB=00
10 1
11
10
01
11
10
01
11
16
20
28
17
19
18
21
23
22
29
31
30
26
CD
01
11
11
32
36
44
33
35
10 34
37
39
38
45
47
46
10
40
41
43
42
11
10
1
11
27
01
01
01
24
25
00
1
CD
EF
00
00
AB=01
10
CD
EF
00 01
11
10
00
AB =11
48 52
60 56
01 49 53
61 57
11
51 55
63 59
10 50 54
62 58
EF
AB =10 00
10
1
11
9
00
11
01
CD
EF
AB =01 00
01
ƒ(A,B,C,D,E,F) =
m(2,8,10,18,24,
26,34,37,42,45,50,
53,58,61)
= D' E F' + A D E' F
+ A' C D' F'
10 1
1
CD
EF
00
00
AB=11
01
1
01
11
10
1
11
10
1
1
CD
EF
00 01 11
AB=10 00
01
1
1
10
11
10
1
1
© R.H. Katz 2-73
Porte logiche: strumenti CAD per la semplificazione
Metodo di Quine-McCluskey
Reti logiche
Logica a 2 livelli
Metodo tabellare per trovare tutti gli implicanti primi
ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15)
Fase 1: Trovare tutti gli implicanti
Tavola degli implicanti
Passo 1: Riempire la col. 1 con mintermini Colonna I
di ON-set e DC-set, raggruppati
0000
in base al numero di 1
0100
1000
0101
0110
1001
1010
0111
1101
1111
© R.H. Katz 2-74
Porte logiche: strumenti CAD per la semplificazione
Metodo di Quine-McCluskey
Reti logiche
Logica a 2 livelli
Metodo tabellare per trovare tutti gli implicanti primi
ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15)
Fase 1: Trovare tutti gli implicanti
Tavola degli implicanti
Passo 1: Riempire la col. 1 con mintermini
di ON-set e DC-set, raggruppati
Colonna I Colonna II
in base al numero di 1
0000 ¦
0-00 *
-000 *
Passo 2: Usare il teorema dell’unificazione: 0100 ¦
Confrontare gli elementi del gruppo 1000 ¦
010- ¦
con N 1 con quelli con N+1 1.
01-0 ¦
Differenza su un bit => adiacenza.
0101 ¦
100- *
Eliminare la variabile e mettere
0110 ¦
10-0 *
nella colonna seguente.
1001 ¦
1010 ¦
01-1 ¦
P.es.., 0000 e 0100 da’ 0-00
-101 ¦
0000 e 1000 da’ -000
0111 ¦
011- ¦
1101 ¦
1-01 *
Quando usato in combinazione,
segnare con |. Se non combinabile, 1111 ¦
-111 ¦
segnare con *. Questi sono gli
11-1 ¦
implicanti primi.
Ripetere il passo 2 finche’ non si possono piu creare combinazioni
© R.H. Katz 2-75
Porte logiche: strumenti CAD per la semplificazione
Metodo di Quine-McCluskey
Reti logiche
Logica a 2 livelli
Metodo tabellare per trovare tutti gli implicanti primi
ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15)
Fase 1: Trovare tutti gli implicanti
Tavola degli implicanti
Passo 1: Riempire la col. 1 con mintermini
di ON-set e DC-set, raggruppati
Colonna I Colonna II Colonna III
in base al numero di 1
0000 ¦
0-00 *
01-- *
-000 *
Passo 2: Usare il teorema dell’unificazione: 0100 ¦
-1-1 *
Confrontare gli elementi del gruppo 1000 ¦
010- ¦
con N 1 con quelli con N+1 1.
01-0 ¦
Differenza su un bit => adiacenza.
0101 ¦
100- *
Eliminare la variabile e mettere
0110 ¦
10-0 *
nella colonna seguente.
1001 ¦
1010 ¦
01-1 ¦
P.es.., 0000 e 0100 da’ 0-00
-101 ¦
0000 e 1000 da’ -000
0111 ¦
011- ¦
1101 ¦
1-01 *
Quando usato in combinazione,
segnare con |. Se non combinabile, 1111 ¦
-111 ¦
segnare con *. Questi sono gli
11-1 ¦
implicanti primi.
Ripetere il passo 2 finche’ non si possono piu creare combinazioni
© R.H. Katz 2-76
Porte logiche: strumenti CAD per la semplificazione
Metodo di Quine-Mc Cluskey
AB
00
CD
00 X
01
0
A
Reti logiche
Logica a 2 livelli
Implicanti primi:
01
11
10
1
0
1
0-00 = A' C' D'
-000 = B' C' D'
1
1
1
100- = A B' C'
10-0 = A B' D'
01-- = A' B
D
11
0
X
X
0
1-01 = A C' D
10
0
1
0
1
-1-1 = B D
C
B
© R.H. Katz 2-77
Reti logiche
Logica a 2 livelli
Porte logiche: strumenti CAD per la semplificazione
Metodo di Quine-Mc Cluskey
AB
00
CD
00 X
01
0
A
Implicanti primi:
01
11
10
1
0
1
0-00 = A' C' D'
-000 = B' C' D'
1
1
1
100- = A B' C'
10-0 = A B' D'
01-- = A' B
D
11
0
X
X
0
1-01 = A C' D
10
0
1
0
1
-1-1 = B D
C
B
Fase 2: Trovare il minimo insieme di primi che copre l’ON-set
(ricordando che gli essenziali devono essere sempre presenti)
Un altro metodo tabellare: la tabella degli implicanti primi
© R.H. Katz 2-78
Porte logiche: strumenti CAD per la semplificazione
Tabella degli implicanti primi
Reti logiche
Logica a 2 livelli
m4 m5 m6 m8 m9 m10 m13
0-00
-000
x
x
100-
x x
x
10-0
1-01
01--1-1
x
x
x
x
x
x
x
x
righe = implicanti primi
colonne = elementi dell’ON-set
inserire un’X se l’elemento dell’ON-set
e’ coperto dall’implicante primo
© R.H. Katz 2-79
Reti logiche
Logica a 2 livelli
Porte logiche: strumenti CAD per la semplificazione
Tabella degli implicanti primi
m4 m5 m6 m8 m9 m10 m13
0-00
-000
x
100-
-1-1
0-00
-000
x x
100-
x x
10-0
x
x
x
1-01
01--
x
x
10-0
x
x
x
m4 m5 m6 m8 m9 m10 m13
x
x
righe = implicanti primi
colonne = elementi dell’ON-set
inserire un’X se l’elemento dell’ON-set
e’ coperto dall’implicante primo
x
-1-1
x
x
1-01
01--
x
x
x
x
x
x
x
x
Se una colonna ha un solo 1,
l’implicante associato con la riga
e’ essenziale. Deve essere parte
di ogni copertura.
© R.H. Katz 2-80
Porte logiche: strumenti CAD per la semplificazione
Tabella degli implicanti primi
Reti logiche
Logica a 2 livelli
m4 m5 m6 m8 m9 m10 m13
0-00
-000
x
x
100-
x
10-0
x
-1-1
x
x
1-01
01--
x
x
x
x
x
x
x
Eliminare le colonne coperte
dagli implicanti essenziali
© R.H. Katz 2-81
Reti logiche
Logica a 2 livelli
Porte logiche: strumenti CAD per la semplificazione
Tabella degli implicanti primi
m4 m5 m6 m8 m9 m10 m13
0-00
-000
x
x
10-0
x
1-01
01--1-1
0-00
-000
x
100-
x
x
x
x
x
m4 m5 m6 m8 m9 m10 m13
x
x
x
Eliminare le colonne coperte
dagli implicanti essenziali
x
100-
x
10-0
x
-1-1
x
x
x
1-01
01--
x
x
x
x
x
x
x
x
Trovare il minimo insieme di righe
che coprono le colonne rimaste
ƒ = A B' D' + A C' D + A' B
© R.H. Katz 2-82
Porte logiche: strumenti CAD per la semplificazione
Metodo di “espresso”
Reti logiche
Logica a 2 livelli
Problema di Quine-McCluskey: il numero di primi cresce
troppo rapidamente con il numero di ingressi
limite massimo: 3 n / n, con n ingressi
trovare copertura minima e’ NP-completo, cioe’ un problema
complesso, che molto probabilmente non avra’ mai
una soluzione efficiente
Espresso (Brayton-SanGiovanni ‘84):
trova soluzione in fretta, a spese della minimalita’
non genera tutti i primi (fase 1 di Quine-McCluskey)
sceglie attentamente un sottoinsieme di primi che coprono l’ON-set
lavora quasi come una persona che cerca i primi in una mappa
© R.H. Katz 2-83
Porte logiche: strumenti CAD per la semplificazione
Reti logiche
Logica a 2 livelli
Cenni sul metodo di “espresso”
1. Espandere gli implicanti alla loro dimensione massima
Implicanti coperti non sono piu’ considerati
La qualita’ dei risultati dipende dall’ordine di espansione
Metodo euristico usato per decidere l’ordine
Il passo e’ chiamato EXPAND
2.
Estrarre una copertura non ridondante (cioe’ nessun sottoinsieme
e’ una copertura) dall’insieme degli implicanti.
Simile alla fase 2 di Quine-McCluskey (tabella dei primi)
Identificare gli implicanti essenziali
Il passo e’ chiamato IRREDUNDANT COVER
3.
A questo punto la soluzione e’ buona, ma migliorabile
Puo’ esistere una copertura con meno primi o meno letterali
Ridurre ogni primo alla minima dimensione che copre l’ON-set
Il passo e’ chiamato REDUCE
4.
Ripetere REDUCE/EXPAND/IRREDUNDANT COVER per trovare
(se possibile) altri implicanti primi
Ripetere l’operazione finche’ ci sono miglioramenti
© R.H. Katz 2-84
Porte logiche: strumenti CAD per la semplificazione
Ingresso ed uscita di espresso
Reti logiche
Logica a 2 livelli
ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15)
Ingresso di espresso
.i 4
.o 1
.ilb a b c d
.ob f
.p 10
0100 1
0101 1
0110 1
1000 1
1001 1
1010 1
1101 1
0000 0111 1111 .e
Uscita di espresso
-- # ingressi
-- # uscite
-- nomi ingressi
-- nomi uscite
-- numero termini prodotto
-- A'BC'D'
-- A'BC'D
-- A'BCD'
-- AB'C'D'
-- AB'C'D
-- AB'CD'
-- ABC'D
-- A'B'C'D' don't care
-- A'BCD don't care
-- ABCD don't care
-- fine lista
.i 4
.o 1
.ilb a b c d
.ob f
.p 3
1-01 1
10-0 1
01-- 1
.e
ƒ = A C' D + A B' D' + A' B
© R.H. Katz 2-85
Reti logiche
Logica a 2 livelli
Porte logiche: strumenti CAD per la semplificazione
Espresso: perche’ iterare Expand / Irredundant cover / Reduce?
A
AB
00
01
11
10
00
1
1
0
0
01
1
1
1
1
CD
A
AB
00
01
11
10
00
1
1
0
0
01
1
1
1
1
CD
D
11
0
0
1
D
1
C
11
0
0
1
1
10
1
1
1
1
C
10
1
1
1
B
Insieme iniziale di primi
trovato dai passi 1 e 2
di espresso
4 primi, non ridondante,
ma non minima!
1
B
Risultato di REDUCE:
riduzione dei primi
mantenendo la copertura
dell’ON-set
La scelta dell’ordine di riduzione
e’ importante!
© R.H. Katz 2-86
Reti logiche
Logica a 2 livelli
Porte logiche: strumenti CAD per la semplificazione
Iterazione in espresso
A
AB
00
01
11
10
00
1
1
0
0
01
1
1
1
1
CD
A
AB
00
01
11
10
00
1
1
0
0
01
1
1
1
1
CD
D
11
0
0
1
D
1
C
11
0
0
1
1
10
1
1
1
1
C
10
1
1
1
1
B
Il secondo EXPAND genera
un insieme diverso di primi
B
IRREDUNDANT COVER genera
il risultato finale
Solo tre implicanti primi!
© R.H. Katz 2-87
Sommario logica a due livelli
Reti logiche
Logica a 2 livelli
Blocchi logici di base:
INVERTER (NOT), AND, OR, NAND, NOR, XOR, XNOR
Forme canoniche
Somme di prodotti, prodotti di somme
funzioni non completamente specificate/don't care
Minimizzazione logica
Obiettivo: realizzazione logica a due livelli con minimo numero
di porte e minimo numero di ingressi
Ottenuto usando:
o le leggi ed i teoremi dell’algebra booleana
o i cubi booleani ed il teorema dell’unificazione
o il metodo delle mappe (fino a 6 variabili)
o l’algoritmo di Quine-McCluskey
o lo strumento CAD Espresso
© R.H. Katz 2-88