Sommario

Reti LogicheLogica multi-livello

© R.H. Katz 3-1

Capitolo 3: Logica combinatoria multi-livello

Reti Logiche Contemporary Logic Design

Randy H. KatzUniversity of California, Berkeley

May 1993

Trasparenze tradotte da:Luciano Lavagno

Universita’ di UdineSettembre 1998


© R.H. Katz 3-2

Sommario

• 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-3

Logica multi-livello: vantaggi

Forma di somme di prodotti minimizzata:

x = A D F + A E F + B D F + B E F + C D F + C E F + G

6 x AND a 3 ingressi + 1 x OR a 7 ingressi (potrebbe non esistere!) 25 fili (19 letterali + 6 fili interni)

1

2

3

4

5

6

7

1

2 3 4

A

A

A

B

B

B

C

C

C

D

D

D

D

E

E

E

E

F

F

F

F

F

F

F

G

G

x x

Forma fattorizzata:

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-4

Logica multi-livello: conversione tra forme

Reti NAND-NAND e NOR-NOR

Leggi di DeMorgan: (A + B)' = A' • B'; (A • B)' = A' + B'

Scritte diversamente: 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

EquivalenzaOR/NAND

A A B B

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 A

B B

A + B 1 1 1 0

A • B 1 1 1 0

OR OR

Nand Nand


© R.H. Katz 3-5


EquivalenzaAND/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

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

A A B B

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 A

B B

A • B 1 0 0 0

A + B 1 0 0 0

AND AND

NOR NOR


© R.H. Katz 3-6

A A B B

C C D D

A B

C D

A B

C D


Esempio: trasformare rete AND/OR in rete NAND/NAND

NAND

NAND

NAND

AND

AND

OR

NAND

NAND

NAND

(A)

(C)

(B)

(D)


© R.H. Katz 3-7


Esempio: trasformare rete AND/OR in rete NAND/NAND

Z = [(A•B)' (C•D)']'

= [(A' + B') (C' + D')]'

= [(A' + B')' • (C' + D')']

= (A • B) + (C • D) ¦

Verificare l’equivalenzadelle due forme:

Questa e’ la conversione facile!!

NAND

NAND

NAND

AA

BB

CC

DD

ZZ


© R.H. Katz 3-8

Logica multi-livello: conversione tra formeEsempio: trasformare rete AND/OR in rete NOR/NOR

Passo 1 Passo 2

NOR

NOR

Mantenerele ”bolle"

NOR

NOR

NOR


Verificare l’equivalenzadelle due forme

Z =

A \A

B\B

C

\CD

\D

ZZ


© R.H. Katz 3-9

Logica multi-livello: conversione tra formeEsempio: trasformare rete AND/OR in rete NOR/NOR

Passo 1 Passo 2Mantenerele ”bolle"



Z = {[(A' + B')' + (C' + D')']'}'

= {(A' + B') • (C' + D')}'

= (A' + B')' + (C' + D')'

= (A • B) + (C • D) ¦Questa e’ la conversione difficile!!

Da AND/OR a NAND/NAND e’ piu’ naturaleDa AND/OR a NAND/NAND e’ piu’ naturale

NOR

NOR

NOR

NOR

NOR

A \A

B\B

C

\CD

\D

ZZ


© R.H. Katz 3-10


Esempio: trasformare rete OR/AND in rete NOR/NOR

NOR

NOR

NOR



Z =


© R.H. Katz 3-11



NOR

NOR

NOR



Z =Z = [(A + B)' + (C + D)']'

= {(A + B)'}' • {(C + D)'}'

= (A + B) • (C + D) ¦

Questa e’ la conversione facile!


© R.H. Katz 3-12



Passo 1 Passo 2

Nand

NandNand

Nand

Nand




Z =


© R.H. Katz 3-13



Passo 1 Passo 2

Nand

NandNand

Nand

Nand




Z =

Questa e’ la conversione difficile! Da OR/AND a NOR/NOR e’ piu’ naturaleDa OR/AND a NOR/NOR e’ piu’ naturale

Z = {[(A' • B')' • (C' • D')']'}'

= {(A' • B') + (C' • D')}'

= (A' • B')' • (C' • D')'

= (A + B) • (C + D) ¦


© R.H. Katz 3-14

Logica multi-livello: piu’ di 2 livelliƒ = A (B + C D) + B C'

Rete originaleAND-OR

Introduzione e mantenimentodelle inversioni (“bolle”)

La stessa rete ridisegnatain termini di porte NAND

tradizionali

C

Level 1 Level 2 Level 3 Level 4

G1 D

B

A F G5 G4

G3

B G2 \ C

C G1 D

B

A

F G5 G4 G3

B G2 \ C

C G1 D

\B A

F G5 G4 G3

B G2 \ C


© R.H. Katz 3-15

Logica multi-livello: piu’ di due livelli

Stessa rete inizialedopo l’inserzionedelle inversioni

Rete finale, disegnatain form NOR-NOR pura

C

Level 1 Level 2 Level 3 Level 4

G1 D

B

A

F G5 G4 G3

\B

C G2

\ C G1 \ D

B \ A

F G5 G4 G3

B \ C

G2


© R.H. Katz 3-16

A

B C

D

F

A

B C

\D

F

X

\ X

(a) (b)

A

B C

D

F X

(d)

A

B C

\ D

F

(c)

\ X

X

Logica multi-livello: piu’ di due livelliEsempio di conversione

Circuito originale Aggiungere doppie inversioni

Distribuire inversioni(causando mancate corrispondenze tra inversioni)

Inserire invertitori per “mettere a posto” lecorrispondenze


© R.H. Katz 3-17

Logica multi-livello: blocchi AND-OR-Invert

Funzione AOI: logica multi-livello — AND, OR, Invertitore Porte multiple ”raggruppate" in un solo blocco logico

AND OR Invertitore

Rete logica equivalente Possibile realizzazione ad interruttori

due ingressi, due gruppi

&

&

+Simbolo logico

2x2 AOI

&

&

+Simbolo logico

3x2 AOI

A B

C D

Z

T rue A C

B D Z

False

A B

C D


© R.H. Katz 3-18

Logica multi-livello: AND-OR-Invert

Esempio: realizzazione di uno XOR

A xor B = A' B + A B'

= ( ? )'

(A' B + A B')'

(A + B') (A' + B)

(A B + A' B')

forma AOI

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)'

AB

0

0

0

0

1 1

1

1


© R.H. Katz 3-19

Logica multi-livello: AND-OR-Invert

F = B C' + A C' + A B

F' = A' B' + A' C + B' C

Realizzata da porta AOI 2 ingressi 3 gruppi

F = (A + B) (A + C') (B + C')

F' = (B' + C) (A' + C) (A' + B')

Realizzata da porta OAI 2 ingressi 3 gruppi

Esempio:

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

10

1

1

0 0 0

0 1 1

B

11 01 00 AB A

C 0

1

Mappa di F'


© R.H. Katz 3-20

Logica multi-livello: AND-OR-InvertEsempio: realizzazione con AOI di uguaglianza su 4 bit

Alto se A0 <> B0, Basso se A0 = B0

A = B attivo basso

NOR

Se tutti gli ingressi sono bassi (veri in logica negativa) allora Ai = Bi, i=0,...,3L’uscita Z e’ vera

Conservazione delle inversioni


© R.H. Katz 3-21

Logica multi-livello: strumenti CAD per semplificazioneOttimizzazione 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 ...

X = (A B + B' C) (C + D (E + A C')) + (D + E)(F G)

A

B B

C C

D

E

A

C

F

G D

E

F 1

F 2

F 5 F 4

F 3

X

+

+

+

+

+

•

• • •

•

• •


© R.H. Katz 3-22

Logica multi-livello: strumenti CAD per semplificazioneOperazioni su forme fattorizzate:

• Decomposizione

• Estrazione

• Fattorizzazione

• Sostituzione

• Fusione (“collapsing”)

Manipolare la rete dando le istruzioni appropriate in modo interattivo

Non c’e’ un algoritmo che garantiscadi ottenere la rete multi-livello“migliore”


© R.H. Katz 3-23

Logica multi-livello: strumenti CAD per semplificazioneDecomposizione:

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'

F puo’ essere riscritta come:

F = X Y + X' Y' X = A B Y = C + D

(12 letterali)

(8 letterali)

Prima della decomposizione Dopo la decomposizione

FF

A

A

A

A

B

B

B

B

C

C

C

C

D

D

D

D


© R.H. Katz 3-24

Logica multi-livello: strumenti CAD per semplificazioneEstrazione: fattorizzazione di sottoespressioni comuni

F = (A + B) C D + EG = (A + B) E'H = C D E

Puo’ essere riscritta come:

F = X Y + EG = X E'H = Y EX = A + BY = C D

(11 letterali)

(11 letterali)

"Kernel": divisori primari

Prima dell’estrazione Dopo l’estrazione

X

E

E

E

GG

Y

HH

A

A

A B

B

BC

C

C D

D

D

FF


© R.H. Katz 3-25

Logica multi-livello: strumenti CAD per semplificazioneFattorizzazione: espressione a due livelli ri-espressa in forma multi-livello

F = A C + A D + B C + B D + E

puo’ essere riscritta come:

F = (A + B) (C + D) + E

(9 letterali)

(5 letterali)

Prima della fattorizzazione Dopo la fattorizzazione

AA

A

B

B

BCC

C

D

D

D

E

E

FF


© R.H. Katz 3-26

Logica multi-livello: strumenti CAD per semplificazioneSostituzione: sostituire G in F, esprimere F in funzione di G

F = A + B C G = A + B

F riscritta usando G:

F = G (A + C)

Fusione (collapsing): inverso della sostituzione. Va usata per eliminare livelli e ridurre il ritardo

F = G (A + C) = (A + B) (A + C) = A A + A C + A B + B C = A + B C

(5 letterali)

(3 letterali)


© R.H. Katz 3-27

Logica multi-livello: strumenti CAD per semplificazione

Strumento base per realizzare tutte queste operazioni: ”divisione”tra funzioni booleane

F = P Q + R

divisore quoziente resto

Esempio:X = A C + A D + B C + B D + EY = A + B

X ”diviso" Y fa:X = Y (C + D) + E

Problema: trovare divisori adatti

F = A D + B C D + EG = A + B

G non divide F usando le regole algebricheG 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 = (A + B C) D + E = A D + B C D + E

F scritta come G Q + R


© R.H. Katz 3-28

Logica multi-livello: strumenti CAD per semplificazioneSessione misII (o SIS) con sommatore (full adder)

% misIIUC Berkeley, MIS Release #2.1 (compiled 3-Mar-89 at 5:32 PM)misII> re full.addermisII> p {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' cimisII> pf {co} = a b' ci + b (ci (a' + a) + a ci') {sum} = ci (a' b' + a b) + ci' (a b' + a' b)misII> sim1 *misII> p {co} = a b + a ci + b ci {sum} = a b ci + a b' ci' + a' b ci' + a' b' cimisII> pf {co} = ci (b + a) + a b {sum} = ci (a' b' + a b) + ci' (a b' + a' b)misII> gd *misII> pf {co} = a [2] + b ci {sum} = a' [3]' + a [3] [2] = ci + b [3] = b' ci' + b ci

leggere equazioni

minimizzazione sudue livelli

decomposizione “buona”

Finora e’ indipendente dalla tecnologia...


© R.H. Katz 3-29


misII> rlib msu.genlibmisII> mapmisII> pf [361] = b' ci' + a' [328] = b' [329] = ci' {co} = [328]' [329]' + [361]' [3] = b ci' + b' ci {sum} = [3] a' + [3]' amisII> 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%

leggere la biblioteca di celle erealizzare con le porte logiche(“technology mapping”)

porte che realizzanoi vari nodie loro aree

analisi dei ritardiritardo = 1 + 0.2 * # fan-out


© R.H. Katz 3-30

Logica multi-livello: strumenti CAD per semplificazionemisII e la biblioteca MSU

Celle standard VLSINumero Nome Funzione1310 inv A'

1120 nor2 (A+B)'1130 nor3 (A+B+C)'1140 nor4 (A+B+C+D)'

1220 nand2 (A•B)'1230 nand3 (A•B•C)'1240 nand4 (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 [A+B, (A+B)']1770 or3/nor3 [A+B+C, (A+B+C)']1780 or4 (A+B+C+D)

1870 aoi22 (A•B + C•D)'1880 aoi21 (A + B•C)'1860 oai22 [(A + B)(C + D)]'1890 oai21 [A (B + C)]'

1970 ao22 A•B + D•E1810 ao222 A•B + C•D + E•F1910 ao2222 A•B + C•D + E•F + G•H1930 ao33 A•B•C + D•E•F

2310 xor2 A•B' + A'•B2350 xnor2 A•B + A'•B'

Nota: OR-AND-INVERTe’ equivalente a INVERT-AND-OR

B CI

[3]

2310

SUM

CO

1890

+ &

[361]

1890

& +

A

A

B CI

[328]

[329] 1310

1310

B

CI

2310


© R.H. Katz 3-31

Logica multi-livello: strumenti CAD per semplificazioneAltri esempi

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 sum1--0 1-1-0 1--10 1111- 1.names a b ci co11- 11-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-32


Realizzazione multi-livello del sommatore: 5 livelli!!

A

A

A

A

B

B

B

B

CI

CI

CI

CI

CO

SUM


© R.H. Katz 3-33

Logica multi-livello: strumenti CAD per semplificazioneSommatore a 2 bit

.inputs a b c d

.outputs x y z

.names a c z [22] x---1 111-- 1-10- 1.names a b c d x z [22] y1---0-- 1--1---1 1-11-0-- 1--110-- 1---100- 1.names a b c d z-0-1 1-1-0 10-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'

8 livelli logici!

Uscita di misII

[22]

B

B

B

C

C

C

C

C

C

D

DD

D

D

D

Z

\X

Y

AA

A

A

X


© R.H. Katz 3-34

Logica multi-livello: strumenti CAD per semplificazioneIncremento di 1 in BCD

.model bcd.increment

.inputs a b c d

.outputs w x y z

.names a b c d z w1---1 10111- 1.names a b c w z x01-0- 10-100 1.names a c z y-11 1000 1.names a b c d z0--0 1-000 1.end

Uscita di misII

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'

Y

A

Z

DB

B

C

C

CX

W

\A\A

\A

\A

\A\B\C

\C\D

\D


© R.H. Katz 3-35

Risposta nel tempo di reti combinatorie• 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-36

Risposta nel tempo di reti combinatorieCircuito di formazione di impulsi

A' • A = 0

F non rimane sempre a 0!

3 ritardi di porta

D rimane ad 1 per3 ritardi dopo che

A e’ salito da 0 ad 1

A B C D F


© R.H. Katz 3-37

Risposta nel tempo di reti combinatorie

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-38

Risposta nel tempo di reti combinatorieAlee e come evitarle

Tipi di alee

L’ingresso fa passare l’uscita da 1 a 0 ad 1

L’ingresso fa passare l’uscita da 0 ad 1 a 0

L’ingresso causa una doppia transizione da 0 ad 1 a 0 ad 1 OPPURE da 1 a 0 ad 1 a 0

Alea statica a 0

Aleedinamiche

Alea statica ad 1

1 1

0

1

0 0

1

0 0

1

1 1

0 0


© R.H. Katz 3-39

Risposta nel tempo di reti combinatorieEsempio di alea

F = A' D + A C'

cambiamento di ingresso entro un termine prodotto

cambiamento di ingresso che influenzapiu’ di un termine:

uscita cambia da 1 a 0 ad 1

G1

G2

G3

A\C

\AD

F

G1

G2

G3

A\C

\AD

F

1

1

1

1

1

0

0

1

1

1

1

0

0

0

ABCD = 1100 ABCD = 1101

G1

G2

G3

A\C

\AD

F

G1

G2

G3

A\C

\AD

F

0

1

0

0

1

0

0

1

1

1

1

1

0

0

ABCD = 1101 ABCD = 0101 (A is still 0)

G1

G2

G3

A\C

\AD

F

0

1

0

1

1

1

1

ABCD = 0111 (A is 1)

A AB

00 01 11 10

0 0 1 1

1 1 1 1

1 1 0 0

0 0 0 0

00

01

11

10 C

CD

D

B


© R.H. Katz 3-40

Risposta nel tempo di reti combinatorieEsempio 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)

Quest’espressione e’ equivalentealla forma in somme di prodottisenza alee di F

A AB

00 01 11 10

0 0 1 1

1 1 1 1

1 1 0 0

0 0 0 0

00

01

11

10 C

CD

D

B


© R.H. Katz 3-41

Risposta nel tempo di reti combinatorieEsempio di alee

Cominciare con espressione senza alee ad 1:

F = A C' + A' D + C' D

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!

Lavorare con il complemento:


© R.H. Katz 3-42

Risposta nel tempo di reti combinatorieProgetto di reti a 2 livelli per funzionamento senza alee

Eliminare le alee statiche per tutte le transizioni di una sola variabile:

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

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

A AB

00 01 11 10

0 0 1 1

1 1 1 1

1 1 1 0

0 0 1 0

00

01

11

10 C

CD

D

B


© R.H. Katz 3-43

Risposta nel tempo di reti combinatorieAlee statiche a 0 e ad 1

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-44

Risposta nel tempo di reti combinatorieAlee 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

Esempi: 1000 -> 0001 (alea funzionale ad 1) 1011 -> 0010 (alea funzionale a 0)

A AB

00 01 11 10

0 0 1 1

1 1 1 1

1 1 1 0

0 0 1 0

00

01

11

10 C

CD

D

B


© R.H. Katz 3-45

Risposta nel tempo di reti combinatorieCome identificare alee statiche in circuiti 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

F = A B C + (A + D) (A' + C')

F1 = A B C + A A' + A C' + A' D + C' D

Esempio:

in forma a 2 livelli

ABCD: da 1111 a 1110 coperta dal termine ABC, quindi non c’e’ alea ad 1

ABCD: da 1110 a 1100 il termine ABC va a 0 mentre AC' va ad 1

ci sono ancora alee statiche!

A AB

00 01 11 10

0 0 1 1

1 1 1 1

1 1 1 0

0 0 1 0

00

01

11

10 C

CD

D

B


© R.H. Katz 3-46

100

A B C D F F 2

Risposta nel tempo di reti combinatorie

Alee statiche ad 1

Soluzione:

aggiungere termini ridondanti per garantirela copertura di tutte le transizioni tra due 1 adiacenti

F2 = A C' + A' D + C' D + A B + B D

Alee ad 1 di Fcorrette in F2


© R.H. Katz 3-47

Risposta nel tempo di reti combinatorieProgetto di reti per funzionamento senza alee

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

Nessun termine della funzione di transitorio puo’ contenere una variabile ed il suo complemento

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

= (A' + B + C') D + A (B + C')

(fattorizzata usando l’assioma di distributivita’, che non introduce alee perche’ non dipende dall’assioma di complementarieta’)

A AB

00 01 11 10

0 0 1 1

1 1 1 1

1 1 1 0

0 0 1 0

00

01

11

10 C

CD

D

B


© R.H. Katz 3-48

Risposta nel tempo di reti combinatorieAlee dinamiche

Esempio con alee dinamiche

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...

G1

G2

G3

G5

G4

\A B

\B

\B \C

F

A

0 1

1

1 0

1

0 1

1 0

1 0 1

1 0 0

1 0

1 0 1 0

Lenta

Molto lenta


© R.H. Katz 3-49

Riassunto del capitolo

• 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

Sommario

Documents

Transcript of Sommario