Reti Logiche
Logica multi-livello
Capitolo 3:
Logica combinatoria multi-livello
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 3-1
Sommario
Reti Logiche
Logica multi-livello
• Logica multi-livello
Conversione a reti in forma NAND-NAND e NOR-NOR
La legge di DeMorgan e l’eliminazione delle inversioni
Blocchi funzionali AND-OR-Invert
Strumenti CAD per ottimizzazione multi-livello
• Risposta nel tempo delle reti logiche combinatorie
Ritardi delle porte e forme d’onda nel tempo
Alee e come evitarle
© R.H. Katz 3-2
Reti Logiche
Logica multi-livello
Logica multi-livello: vantaggi
Forma di somme di prodotti minimizzata:
x=ADF + AEF + BDF + BEF + CDF + CEF + G
6 x AND a 3 ingressi + 1 x OR a 7 ingressi (potrebbe non esistere!)
25 fili (19 letterali + 6 fili interni)
A
D
F
A
E
F
B
D
F
B
E
F
C
D
F
C
E
F
G
1
2
3
4
5
7
x
A
B
C
1
D
E
2
3
4
x
F
G
Forma fattorizzata:
6
x = (A + B + C) (D + E) F + G
1 x OR a 3 ingressi, 2 x OR a 2 ingressi,
1 x AND a 3 ingressi
10 fili (7 letterali + 3 fili interni)
© R.H. Katz 3-3
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Reti NAND-NAND e NOR-NOR
Leggi di DeMorgan:
(A + B)' = A' • B';
Scritte diversamente: A + B = (A' • B')';
(A • B)' = A' + B'
(A • B) = (A' + B')'
In altre parole:
OR e’ come NAND con ingressi complementati
AND e’ come NOR con ingressi complementati
NAND e’ come OR con ingressi complementati
NOR e’ come AND con ingressi complementati
Equivalenza
OR/NAND
A
0
0
1
1
A
1
1
0
0
B
0
1
0
1
B
1
0
1
0
A +B
0
1
1
1
A• B
0
1
1
1
A +B
1
1
1
0
A• B
1
1
1
0
A
B
OR
A
B
Nand

A
B
OR

A
B
Nand
© R.H. Katz 3-4
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Equivalenza
AND/NOR
A
0
0
1
1
A
1
1
0
0
B
0
1
0
1
B
1
0
1
0
A• B
0
0
0
1
A+ B
0
0
0
1
A• B
1
0
0
0
A +B
1
0
0
0
A
B
AND
A
B
NOR

A
B
AND

A
B
NOR
Si possono convertire reti con AND ed OR in reti con NAND
e NOR, introducendo le inversioni opportune (“bolle”)
Per mantenere i livelli logici, ogni inversione deve avere
un’inversione corrispondente
© R.H. Katz 3-5
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete AND/OR in rete NAND/NAND
(A) A
(B) A
B
B
AND
OR
C
D
C
D
NAND
AND
NAND
A
(C) A
B
(D) B
C
D
C
D
NAND
NAND
NAND
NAND
© R.H. Katz 3-6
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete AND/OR in rete NAND/NAND
NAND
A
A
B
B
Z
C
C
Z
NAND
NAND
D
D
Z = [(A•B)' (C•D)']'
Verificare l’equivalenza
delle due forme:
= [(A' + B') (C' + D')]'
= [(A' + B')' • (C' + D')']
= (A • B) + (C • D) ¦
Questa e’ la conversione facile!!
© R.H. Katz 3-7
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete AND/OR in rete NOR/NOR
NOR
NOR
A
\A
\B
NOR
B
Z
C
NOR
Z
NOR
\C
D
\D
Passo 2
Passo 1
Mantenere
le ”bolle"
Mantenere
le ”bolle"
Z=
Verificare l’equivalenza
delle due forme
© R.H. Katz 3-8
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete AND/OR in rete NOR/NOR
NOR
NOR
A
\A
\B
NOR
B
Z
C
Z
NOR
NOR
\C
D
\D
Passo 2
Passo 1
Mantenere
le ”bolle"
Mantenere
le ”bolle"
Z = {[(A' + B')' + (C' + D')']'}'
Verificare l’equivalenza
delle due forme
= {(A' + B') • (C' + D')}'
= (A' + B')' + (C' + D')'
Questa e’ la conversione difficile!!
= (A • B) + (C • D) ¦
Da AND/OR a NAND/NAND e’ piu’ naturale
© R.H. Katz 3-9
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete OR/AND in rete NOR/NOR
NOR
NOR
NOR
Mantenere
le ”bolle"
Z=
Verificare l’equivalenza
delle due forme
© R.H. Katz 3-10
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete OR/AND in rete NOR/NOR
NOR
NOR
NOR
Mantenere
le ”bolle"
Z = [(A + B)' + (C + D)']'
Verificare l’equivalenza
delle due forme
= {(A + B)'}' • {(C + D)'}'
= (A + B) • (C + D) ¦
Questa e’ la conversione facile!
© R.H. Katz 3-11
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete OR/AND in rete NOR/NOR
Nand
Nand
Nand
Nand
Nand
Passo 2
Passo 1
Mantenere
le ”bolle"
Mantenere
le ”bolle"
Z=
Verificare l’equivalenza
delle due forme
© R.H. Katz 3-12
Reti Logiche
Logica multi-livello
Logica multi-livello: conversione tra forme
Esempio: trasformare rete OR/AND in rete NOR/NOR
Nand
Nand
Nand
Nand
Passo 1
Nand
Passo 2
Mantenere
le ”bolle"
Mantenere
le ”bolle"
Z = {[(A' • B')' • (C' • D')']'}'
Verificare l’equivalenza
delle due forme
= {(A' • B') + (C' • D')}'
= (A' • B')' • (C' • D')'
= (A + B) • (C + D) ¦
Questa e’ la conversione difficile!
Da OR/AND a NOR/NOR e’ piu’ naturale
© R.H. Katz 3-13
Reti Logiche
Logica multi-livello
Logica multi-livello: piu’ di 2 livelli
ƒ = A (B + C D) + B C'
Rete originale
AND-OR
Introduzione e mantenimento
delle inversioni (“bolle”)
Lev el 1
C
D
B
A
B
\C
C
D
G1
Lev el 2
Lev el 3
Lev el 4
G4
G5
F
G4
G5
F
G3
G2
G1
G3
B
La stessa rete ridisegnata
in termini di porte NAND
tradizionali
A
B
\C
G2
C
D
G1
\B
A
B
\C
G3
G4
G5
F
G2
© R.H. Katz 3-14
Reti Logiche
Logica multi-livello
Logica multi-livello: piu’ di due livelli
Lev el 1
Lev el 2
G1
G3
Lev el 3
Lev el 4
G4
G5
C
D
B
A
F
Stessa rete iniziale
dopo l’inserzione
delle inversioni
\B
G2
C
\C
\D
G1
B
\A
B
\C
G2
G3
G4
G5
F
Rete finale, disegnata
in form NOR-NOR pura
© R.H. Katz 3-15
Reti Logiche
Logica multi-livello
Logica multi-livello: piu’ di due livelli
Esempio di conversione
A
B
C
D
(a)
A
F
X
B
C
F
X
D
(b) Aggiungere doppie inversioni
Circuito originale
A
X
A
B
C
\D
(c )
F
\X
Distribuire inversioni
(causando mancate
corrispondenze tra inversioni)
B
C
F
\X
\D
(d) Inserire invertitori per
“mettere a posto” le
corrispondenze
© R.H. Katz 3-16
Reti Logiche
Logica multi-livello
Logica multi-livello: blocchi AND-OR-Invert
Funzione AOI: logica multi-livello — AND, OR, Invertitore
Porte multiple ”raggruppate" in un solo blocco logico
Rete logica equivalente
Possibile realizzazione ad interruttori
True
A
B
Z
C
D
Fals e
A
C
B
D
A
B
C
D
Z
AND
OR
Invertitore
due ingressi, due gruppi
Simbolo logico
2x2 AOI
&
+
&
Simbolo logico
3x2 AOI
&
+
&
© R.H. Katz 3-17
Reti Logiche
Logica multi-livello
Logica multi-livello: AND-OR-Invert
Esempio: realizzazione di uno XOR
A xor B = A' B + A B'
= ( ? )'
forma AOI
(A' B + A B')'
(A + B') (A' + B)
(A B + A' B')
Metodo generale per mettere in forma AOI:
Calcolare il complemento in forma di Somme di Prodotti
coprendo gli 0 nella mappa di Karnaugh
ƒ = (A' B' + A B)'
B
0
1
A 0
1
0
1
1
0
© R.H. Katz 3-18
Logica multi-livello: AND-OR-Invert
Esempio:
AB
00
C
0 1
1
1
F = B C' + A C' + A B
A
01 11 10
0
0
0
1
0
Reti Logiche
Logica multi-livello
1
B
F' = A' B' + A' C + B' C
Realizzata da porta AOI 2 ingressi 3 gruppi
F = (A + B) (A + C') (B + C')
Mappa di F'
F' = (B' + C) (A' + C) (A' + B')
Realizzata da porta OAI 2 ingressi 3 gruppi
Esempi:
Uguaglianza su 4 bit
Z = (A0 B0 + A0' B0') (A1 B1 + A1' B1') (A2 B2 + A2' B2') (A3 B3 + A3' B3')
Ognuno realizzato da una porta AOI 2x2
© R.H. Katz 3-19
Logica multi-livello: AND-OR-Invert
Esempio: realizzazione con AOI di uguaglianza su 4 bit
Reti Logiche
Logica multi-livello
Alto se A0 <> B0, Basso se A0 = B0
A = B attivo basso
Conservazione delle inversioni
NOR
Se tutti gli ingressi sono bassi
(veri in logica negativa)
allora Ai = Bi, i=0,...,3
L’uscita Z e’ vera
© R.H. Katz 3-20
Logica multi-livello: strumenti CAD per semplificazione
Reti Logiche
Logica multi-livello
Ottimizzazione multi-livello:
1. fattorizzare logica condivisa (riduce fan-in, aumenta livelli),
con vincoli di ritardo
2. Realizzare la forma fattorizzata usando una biblioteca di porte
3. Minimizzare il numero di letterali (correlato con il numero di fili)
Forma fattorizzata:
somme di prodotti di somme di prodotti ...
A
•
B
B
+
•
C C
D
E
A
•
C
•
F5
+ F
G
D
E
X = (A B + B' C) (C + D (E + A C')) + (D + E)(F G)
F1
•
+ F
2
+
X
F4
•
•
+
F3
© R.H. Katz 3-21
Logica multi-livello: strumenti CAD per semplificazione
Reti Logiche
Logica multi-livello
Operazioni su forme fattorizzate:
• Decomposizione
• Estrazione
• Fattorizzazione
• Sostituzione
Manipolare la rete dando le istruzioni
appropriate in modo interattivo
Non c’e’ un algoritmo che garantisca
di ottenere la rete multi-livello
“migliore”
• Fusione
(“collapsing”)
© R.H. Katz 3-22
Reti Logiche
Logica multi-livello: strumenti CAD per semplificazione
Logica multi-livello
Decomposizione:
Prendere un’espressione booleana e sostituirla con un insieme
di espressioni e fili:
F = A B C + A B D + A' C' D' + B' C' D' (12 letterali)
F puo’ essere riscritta come:
F = X Y + X' Y'
X=AB
Y=C+D
A
B
C
A
B
D
A
C
D
B
C
D
(8 letterali)
A
B
F
Prima della decomposizione
F
C
D
Dopo la decomposizione
© R.H. Katz 3-23
Logica multi-livello: strumenti CAD per semplificazione
Reti Logiche
Logica multi-livello
Estrazione: fattorizzazione di sottoespressioni comuni
F = (A + B) C D + E
G = (A + B) E'
H=CDE
(11 letterali)
Puo’ essere riscritta come:
(11 letterali)
F=XY + E
G = X E'
H=YE
X=A+B
Y=CD
"Kernel": divisori primari
E
A
B
F
C
D
A
B
G
C
D
E
Prima dell’estrazione
A
B
X
C
D
E
Y
F
G
H
H
Dopo l’estrazione
© R.H. Katz 3-24
Reti Logiche
Logica multi-livello: strumenti CAD per semplificazione
Logica multi-livello
Fattorizzazione: espressione a due livelli ri-espressa in forma multi-livello
F=AC + AD + BC + BD + E
(9 letterali)
puo’ essere riscritta come:
(5 letterali)
F = (A + B) (C + D) + E
A
C
A
D
B
C
A
B
F
B
D
F
C
D
E
E
Prima della fattorizzazione
Dopo la fattorizzazione
© R.H. Katz 3-25
Logica multi-livello: strumenti CAD per semplificazione
Reti Logiche
Logica multi-livello
Sostituzione: sostituire G in F, esprimere F in funzione di G
F=A+BC
G=A+B
(5 letterali)
F riscritta usando G:
F = G (A + C)
(3 letterali)
Fusione (collapsing): inverso della sostituzione.
Va usata per eliminare livelli e ridurre il ritardo
F = G (A + C)
= (A + B) (A + C)
=AA + AC + AB + B C
=A+BC
© R.H. Katz 3-26
Logica multi-livello: strumenti CAD per semplificazione
Reti Logiche
Logica multi-livello
Strumento base per realizzare tutte queste operazioni: ”divisione”
tra funzioni booleane
F = PQ + R
divisore
quoziente
resto
Esempio:
X=AC + AD + BC + BD + E
Y=A+B
X ”diviso" Y fa:
X = Y (C + D) + E
Problema: trovare divisori adatti
F=AD + BCD + E
G=A+B
G non divide F usando le regole algebriche
G divide F usando le regole booleane (moltissimi divisori!)
F/G = (A + C) D
F = [G (A + C) D] + E
= (A + B) (A + C) D + E
= (A A + A C + A B + B C) D + E
F scritta come G Q + R
= (A + B C) D + E
=AD+BCD+E
© R.H. Katz 3-27
Logica multi-livello: strumenti CAD per semplificazione
Reti Logiche
Logica multi-livello
Sessione misII (o SIS) con sommatore (full adder)
% misII
UC Berkeley, MIS Release #2.1 (compiled 3-Mar-89 at 5:32 PM)
misII> re full.adder
misII> p
leggere equazioni
{co} = a b ci + a b ci' + a b' ci + a' b ci
{sum} = a b ci + a b' ci' + a' b ci' + a' b' ci
misII> pf
{co} = a b' ci + b (ci (a' + a) + a ci')
{sum} = ci (a' b' + a b) + ci' (a b' + a' b)
minimizzazione su
misII> sim1 *
due livelli
misII> p
{co} = a b + a ci + b ci
{sum} = a b ci + a b' ci' + a' b ci' + a' b' ci
misII> pf
{co} = ci (b + a) + a b
{sum} = ci (a' b' + a b) + ci' (a b' + a' b)
misII> gd *
misII> pf
decomposizione
{co} = a [2] + b ci
“buona”
{sum} = a' [3]' + a [3]
[2] = ci + b
[3] = b' ci' + b ci
Finora e’ indipendente dalla tecnologia...
© R.H. Katz 3-28
Logica multi-livello: strumenti CAD per semplificazione
misII> rlib msu.genlib
misII> map
misII> pf
[361] = b' ci' + a'
[328] = b'
[329] = ci'
{co} = [328]' [329]' + [361]'
[3] = b ci' + b' ci
{sum} = [3] a' + [3]' a
misII> pg
[361]
1890:physical 32.00
[328]
1310:physical 16.00
[329]
1310:physical 16.00
{co}
1890:physical 32.00
[3]
2310:physical 40.00
{sum} 2310:physical 40.00
misII> pat
... using library delay model
{sum} : arrival=( 2.2 2.2)
{co}
: arrival=( 2.2 2.2)
[328] : arrival=( 1.2 1.2)
[361] : arrival=( 1.2 1.2)
[329] : arrival=( 1.2 1.2)
[3]
: arrival=( 1.2 1.2)
ci
: arrival=( 0.0 0.0)
b
: arrival=( 0.0 0.0)
a
: arrival=( 0.0 0.0)
misII> quit
%
Reti Logiche
Logica multi-livello
leggere la biblioteca di celle e
realizzare con le porte logiche
(“technology mapping”)
porte che realizzano
i vari nodi
e loro aree
analisi dei ritardi
ritardo = 1 + 0.2 * # fan-out
© R.H. Katz 3-29
Logica multi-livello: strumenti CAD per semplificazione
misII e la biblioteca MSU
Celle standard VLSI
B
CI
[3]
SUM
2310
A
2310
A
B
CI
+
[361]
&
&
1890
[328]
+
CO
1890
B
1310
[329]
CI
1310
Nota: OR-AND-INVERT
e’ equivalente a INVERT-AND-OR
Reti Logiche
Logica multi-livello
Numero Nome
1310
inv
Funzione
A'
1120
1130
1140
nor2
nor3
nor4
(A+B)'
(A+B+C)'
(A+B+C+D)'
1220
1230
1240
nand2
nand3
nand4
(A•B)'
(A•B•C)'
(A•B•C•D)'
1660 and2/nand2 [A•B, (A•B)']
1670 and3/nand3 [A•B•C, (A•B•C)']
1680 and4/nand4 [A•B•C•D, (A•B•C•D)']
1760 or2/nor2
1770 or3/nor3
1780 or4
[A+B, (A+B)']
[A+B+C, (A+B+C)']
(A+B+C+D)
1870
1880
1860
1890
aoi22
aoi21
oai22
oai21
(A•B + C•D)'
(A + B•C)'
[(A + B)(C + D)]'
[A (B + C)]'
1970
1810
1910
1930
ao22
ao222
ao2222
ao33
A•B + D•E
A•B + C•D + E•F
A•B + C•D + E•F + G•H
A•B•C + D•E•F
2310 xor2
2350 xnor2
A•B' + A'•B
A•B + A'•B'
© R.H. Katz 3-30
Logica multi-livello: strumenti CAD per semplificazione
Altri esempi
Reti Logiche
Logica multi-livello
misII e “script” di semplificazione:
misII -f script -t pla <file con tabella di verita’ espresso>
Full Adder:
.model full.adder
.inputs a b ci
.outputs sum co
.names a b ci co sum
1--0 1
-1-0 1
--10 1
111- 1
.names a b ci co
11- 1
1-1 1
-11 1
.end
Formato di uscita in stile PLA di misII
variabili di ingresso
variabile di uscita
SUM = A CO' + B CO' + CI CO' + A B CI (9 letterali)
CO = A B + A CI + B CI
(6 letterali)
Nota: A xor B xor CI = A' B' CI + A B' CI' + A' B CI' + A B CI (12 letterali!)
© R.H. Katz 3-31
Logica multi-livello: strumenti CAD per semplificazione
Reti Logiche
Logica multi-livello
A
A
B
A
CI
CO
B
SUM
CI
B
CI
A
B
CI
Realizzazione multi-livello del sommatore: 5 livelli!!
© R.H. Katz 3-32
Reti Logiche
Logica multi-livello
Logica multi-livello: strumenti CAD per semplificazione
Sommatore a 2 bit
.inputs a b c d
.outputs x y z
.names a c z [22] x
---1 1
11-- 1
-10- 1
.names a b c d x z [22] y
1---0-- 1
--1---1 1
-11-0-- 1
--110-- 1
---100- 1
.names a b c d z
-0-1 1
-1-0 1
0-10 1
.names a d z [22]
110 1
.end
Z = B' D + B D' + A' C D'
[22] = A D Z'
X = [22] + A C + C Z'
Y = A X + C [22] + B C X' + C D X' + D X' Z'
\X
B
D
A
A
C
X
B
D
A
C
D
A
D
Z
C
C
B
C
[22]
Uscita di misII
Y
C
D
D
8 livelli logici!
© R.H. Katz 3-33
Reti Logiche
Logica multi-livello
Logica multi-livello: strumenti CAD per semplificazione
Incremento di 1 in BCD
.model bcd.increment
.inputs a b c d
.outputs w x y z
.names a b c d z w
1---1 1
0111- 1
.names a b c w z x
01-0- 1
0-100 1
.names a c z y
-11 1
000 1
.names a b c d z
0--0 1
-000 1
.end
Z = A' D' + B' C' D'
Y = C Z + A' C' Z'
W = A Z + A' B C D
X = A' B W' + A' C W' Z'
A
W
\A
B
C
D
Uscita di misII
\A
\D
\B
\C
\D
Z
\A
B
C
Y
\A
\C
\A
C
X
© R.H. Katz 3-34
Risposta nel tempo di reti combinatorie
Reti Logiche
Logica multi-livello
• Consideriamo il comportamento nel tempo dei circuiti
• Usiamo le forme d’onda per visualizzarlo
• Usiamo la simulazione per creare le forme d’onda
• Rapidi cambiamenti di valore in uscita: alee
possono essere utili— circuiti di formazione di impulsi
possono essere problematiche — impulsi spuri (glitch)
Termini:
ritardo di una porta (gate delay): tempo da un cambiamento in
ingresso ad uno in uscita
ritardo minimo, medio/tipico, massimo
un buon progettista pensa al caso peggiore!!
tempo di salita (rise time): tempo per transizione in uscita
da tensione bassa ad alta
tempo di discesa (fall time): tempo per transizione in uscita
da tensione alta a bassa
© R.H. Katz 3-35
Reti Logiche
Logica multi-livello
Risposta nel tempo di reti combinatorie
Circuito di formazione di impulsi
A
B
C
D
F
A' • A = 0
3 ritardi di porta
D rimane ad 1 per
3 ritardi dopo che
A e’ salito da 0 ad 1
F non rimane sempre a 0!
© R.H. Katz 3-36
Risposta nel tempo di reti combinatorie
Reti Logiche
Logica multi-livello
Alee e come evitarle
Transizioni indesiderate sulle uscite
Accadono perche’ cammini diversi sulle uscite subiscono
ritardi di propagazione diversi
Pericolose se la logica “prende una decisione” quando l’uscita
non e’ stabile, o quando l’uscita controlla una rete sequenziale
asincrona queste rispondono immediatamente ad ogni
transizione in ingresso, senza aspettare il clock
Soluzione normale (circuiti sincroni)
aspettare (con un clock) che i segnali siano stabili
non usare mai, mai, mai circuiti con ingressi asincroni
progettare circuiti asincroni senza alee
I primi due metodi sono i piu’ sicuri, ma vale la pena conoscere
anche il terzo...
© R.H. Katz 3-37
Risposta nel tempo di reti combinatorie
Alee e come evitarle
1
Reti Logiche
Logica multi-livello
1
Alea
statica ad 1 L’ingresso fa passare l’uscita da 1 a 0 ad 1
0
1
0
0
1
Alea
statica a 0
L’ingresso fa passare l’uscita da 0 ad 1 a 0
1
0
0
1
Alee
L’ingresso causa una doppia transizione
1 dinamiche da 0 ad 1 a 0 ad 1 OPPURE
da 1 a 0 ad 1 a 0
0
0
Tipi di alee
© R.H. Katz 3-38
Reti Logiche
Logica multi-livello
Risposta nel tempo di reti combinatorie
Esempio di alea
A
\C
\A
D
1
G1
1
0
G3
1
\A
D
0
1
G1
F
G2
0
1
A
\C
1
1
0
G3
1
A
AB
00
CD
00 0
01
11
10
0
1
1
1
1
1
F
01
G2
1
0
1
D
ABCD = 1101
ABCD = 1100
C
cambiamento di ingresso
entro un termine prodotto
11
1
1
0
0
10
0
0
0
0
B
F = A' D + A C'
A
\C
\A
D
1
G1
1
0
1
A
\C
1
G3
G2
0
ABCD = 1101
1
F
\A
D
0
G1
1
0
1
0
G3
G2
0
0
A
\C
F
\A
D
ABCD = 0101 (A is still 0)
0
G1
1
1
0
G3
1
F
G2
1
1
ABCD = 0111 (A is 1)
cambiamento di ingresso che influenza
piu’ di un termine:
uscita cambia da 1 a 0 ad 1
© R.H. Katz 3-39
Reti Logiche
Logica multi-livello
Risposta nel tempo di reti combinatorie
Esempio di alea
Strategia generale: aggiungere termini ridondanti
F = A' D + A C' diventa A' D + A C' + C' D
Questo elimina alee ad 1. E le alee a 0?
Derivare F in prodotti di somme
(coprendo gli 0)
F = (A' + C')(A + D)
Anche adesso c’e’ un’alea!
Aggiungere un termine: (C' + D) C
Quest’espressione e’ equivalente
alla forma in somme di prodotti
senza alee di F
AB
00
CD
A
01
11
10
00
0
0
1
1
01
1
1
1
1
D
11
1
1
0
0
10
0
0
0
0
B
© R.H. Katz 3-40
Risposta nel tempo di reti combinatorie
Esempio di alee
Reti Logiche
Logica multi-livello
Cominciare con espressione senza alee ad 1:
F = A C' + A' D + C' D
Lavorare con il complemento:
F' = (A C' + A' D + C' D)'
= (A' + D) (A + D') (C + D')
= A C + A C D' + C D' + A' C D' + A' D'
= A C + C D' + A' D'
copre tutti gli 1 adiacenti nella mappa di Karnaugh
non ha alee ne’ a 0 ne’ ad 1!
© R.H. Katz 3-41
Risposta nel tempo di reti combinatorie
Progetto di reti a 2 livelli per funzionamento senza alee
Reti Logiche
Logica multi-livello
Eliminare le alee statiche per tutte le transizioni
di una sola variabile:
AB
00
CD
A
01
11
10
00
0
0
1
1
01
1
1
1
1
Basta realizzare la funzione in somme di prodotti
garantendo che ogni coppia di
1 adiacenti siano coperti da un termine prodotto
Sono necessari e sufficienti tutti gli implicanti primi
D
C
11
1
1
1
0
10
0
0
1
0
F(A,B,C,D) =  m(1,3,5,7,8,9,12,13,14,15)
F = A B + A' D + B D + A C' + C' D
B
© R.H. Katz 3-42
Risposta nel tempo di reti combinatorie
Alee statiche a 0 e ad 1
Reti Logiche
Logica multi-livello
Forma normale somme di prodotti:
- non ha alee ad 1 se usiamo tutti gli implicanti primi
- non ha mai alee a 0 (De Morgan e moltiplicazione
crea automaticamente tutti i termini somma)
Forma normale prodotti di somme:
- non ha alee a 0 se usiamo tutti gli implicanti primi
- non ha mai alee ad 1 (De Morgan e moltiplicazione
crea automaticamente tutti i termini prodotto)
Possiamo eliminare tutte le alee?
- no, solo quelle logiche
- alee funzionali non
possono essere eliminate
Analisi delle alee/sintesi senza alee richiede di specificare
le transizioni di interesse, rispetto a cui le alee verranno
analizzate/eliminate
© R.H. Katz 3-43
Reti Logiche
Logica multi-livello
Risposta nel tempo di reti combinatorie
Alee logiche e funzionali
Alee logiche: esiste un termine prodotto per alee ad 1
(o un termine somma per alee a 0)
che copra punto iniziale e finale della transizione
Esempi:
AB’C’D’ -> ABC’D (coperti da AC’)
A’B’CD’ -> A’BC’D’ (coperti da A’ + D’)
Alee funzionali: non esiste un termine prodotto per alee ad 1
(o un termine somma per alee a 0)
che copra punto iniziale e finale della transizione
AB
00
CD
Esempi:
1000 -> 0001
(alea funzionale ad 1)
1011 -> 0010
(alea funzionale a 0)
A
01
11
10
00
0
0
1
1
01
1
1
1
1
D
C
11
1
1
1
0
10
0
0
1
0
B
© R.H. Katz 3-44
Risposta nel tempo di reti combinatorie
Come identificare alee statiche in circuiti multi-livello:
Reti Logiche
Logica multi-livello
Calcolare la funzione di uscita per i transitori
variabili e complementi trattati come indipendenti
non si puo’ usare X + X' = 1 o X • X' = 0 per semplificare
Esempio:
F = A B C + (A + D) (A' + C')
F1 = A B C + A A' + A C' + A' D + C' D
AB
00
CD
A
01
11
10
00
0
0
1
1
01
1
1
1
1
ABCD: da 1111 a 1110 coperta dal termine
ABC, quindi non c’e’ alea ad 1
D
11
C
10
1
0
in forma a 2 livelli
1
1
0
1
0
0
ABCD: da 1110 a 1100 il termine ABC va a 0
mentre AC' va ad 1
ci sono ancora alee statiche!
B
© R.H. Katz 3-45
Reti Logiche
Logica multi-livello
Risposta nel tempo di reti combinatorie
Alee statiche ad 1
Soluzione:
aggiungere termini ridondanti per garantire
la copertura di tutte le transizioni tra due 1 adiacenti
F2 = A C' + A' D + C' D + A B + B D
100
A
B
C
D
F
F2
Alee ad 1 di F
corrette in F2
© R.H. Katz 3-46
Risposta nel tempo di reti combinatorie
Progetto di reti per funzionamento senza alee
Reti Logiche
Logica multi-livello
Basta mettere la funzione del transitorio di uscita
in una forma che garantisca che ogni coppia di
1 adiacenti siano coperti da un termine prodotto
AB
00
CD
A
01
11
10
Nessun termine della funzione di transitorio puo’
contenere una variabile ed il suo complemento
00
0
0
1
1
F(A,B,C,D) =  m(1,3,5,7,8,9,12,13,14,15)
01
1
1
1
1
F = A B + A' D + B D + A C' + C' D
D
C
11
1
1
1
0
10
0
0
1
0
B
= (A' + B + C') D + A (B + C')
(fattorizzata usando l’assioma di distributivita’,
che non introduce alee perche’ non dipende
dall’assioma di complementarieta’)
© R.H. Katz 3-47
Reti Logiche
Logica multi-livello
Risposta nel tempo di reti combinatorie
Alee dinamiche
Esempio con alee dinamiche
\A 1
B
01
\B
\C
G1
01
Lenta
G3
10
G2
1
1 01
10
A
\B
G5
1 01 0
F
0
G4
10
10
Molto lenta
Tre cammini diversi da B o B' all’uscita
ABC = 000, F = 1 to ABC = 010, F = 0
ritardi diversi lungo i cammini:
G1 lenta, G4 molto lenta
Eliminare le alee dinamiche e’ molto complicato
Non ne parleremo in questo corso...
© R.H. Katz 3-48
Riassunto del capitolo
Reti Logiche
Logica multi-livello
• Passaggio da porte semplici a blocchi piu’ complessi
• Conversione da AND/OR, OR/AND a NAND/NAND, NOR/NOR
• Logica multi-livello: meno porte e fan-in, ma piu’ ritardo
• Uso di misII per minimizzare logica multi-livello e
realizzare in una biblioteca di porte (technology mapping)
• Risposta nel tempo di logica combinatoria:
ritardo delle porte, tempi di salita e discesa
alee e progetto senza alee
© R.H. Katz 3-49