somma di prodotti

(1)

Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Il Livello Logico-Digitale:

Trasformazione di Espressioni Booleane

Marco Tarini

Dipartimento di Scienze Teoriche e Applicate [email protected]

Idea: ottimizzare l’espressione prima di implementarla in un circuito

Funzione booleana (tav. verita)

espressione booleana prodotto di somme OPPURE somma di prodotti

sintesi di espressione in 1ma oppure 2da forma canonica

rete combinatoria ottimizzata

Ottimizzazione usando regole di riscrittura delle espr. booleane

espressione booleana più semplice

implementazione dell’espressione booleana in un circuito combinatorio

(2)

Rete combinatoria Rete combinatoria

Trasformazione di espressioni booleane

Porte logiche

Architettura degli elaboratori - 39 -

Espressione booleana

A + /A /B

Transfor- mazione

passare da una

espressione booleana ad una equivalente (stessa funzione booleana)

con lo scopo di ridurne la complessità

Regole di trasformazione delle espressioni booleane

Porte logiche

con AND 1 A = A 0 A = 0 A A = A A /A = 0 A B = B A (A B) C = A (B C) A + B C = (A + B) (A + C)

A (A + B) = A /(A B) = /A + /B

con OR (duale) 0 + A = A 1 + A = 1 A + A = A A + /A = 1 A + B = B + A (A + B) + C = A + (B + C)

A (B + C) = A B + A C A + A B = A /(A + B) = /A /B Legge

Identità Elemento nullo Idempotenza Inverso Commutativa Associativa Distributiva Assorbimento De Morgan

Tertium non datur / / A = A

(3)

Porte logiche

Regole di trasformazione: note

Le regole di trasformazione (o «di riscrittura»)

ci consentono di passare da una espressione ad un’altra, equivalente.

l’equivalenza è garantita dalla teoria!

Obiettivo delle riscritture: ottimizzare l’espressione di partenza Cioè: rendere il circuito associato piú economico, o piú veloce, etc Gli A, B nelle regole rappresentano sotto-espressioni qualsiasi

(non necessariamente variabili: es: (A(B+C)+ A(B+C)) = A(B+C) Tutte le regole sono in doppia copia: una per l’AND una per l’OR

una è la regola DUALEdell’altra

cioè una è ottenuta dall’altra scambiando fra di loro:

AND <==> OR e 0 <==> 1

Ciascuna regola si può usare in un verso, o nel verso opposto

XXX = YYY  posso passare da XXX a YYY… oppure viceversa Alcune regole somigliano a quelle dell’algebra numerica tradizionale

Altre sono piuttosto diverse (per esempio i due assorbimenti)!

De Morgan explained

Nel primale:

«affermare che sia vero A e-anche B significa

negare che uno qualsiasi dei due sia falso»

/(A B) = /A + /B cioè A B =/ ( /A + /B )

Nel duale:

«affermare che sia vero A oppure B (o entrambi) significa

negare che siano entrambi falsi»

/(A + B) = /A /B cioè A + B = / ( /A /B )

(4)

De Morgan: una conseguenza

DeMorgan ci mostra che possiamo, se lo vogliamo, fare a meno di porte OR .

potremmo sempre sostituirle con porte AND (più alcuni NOT) e viceversa!

ecco le leggi di De Morgan…

…a circuito:

Porte logiche



Un altro assorbimento

Porte logiche

A + /A B = A + B A (/A + B) = AB

(5)

Porte logiche

Esempio di applicazione delle regole di riscrittura

Si consideri la funzione booleana di 3 variabili G(a,b,c) espressa dalla seguente equazione:

G(a,b,c) = (/a /b /c) + (/a /b c) + (/a /b c) + (/a b c) +(a /b c) + (a b c) Semplificare l’espressione. Indicare le operazioni svolte

Espressione

(a¯ b¯ c¯) + (a¯ b¯ c) + (a¯ b¯ c) + (a¯ b c) + (a b¯ c) + (a b c)

a¯ b¯ (c¯ +c) + a¯ c (b¯ +b) + a c (b¯ +b) a¯ b¯ + a¯ c + a c

a¯ b¯ + c (a¯ + a) a¯ b¯ + c

Regola utilizzata

X + X = X XY + XZ = X (Y + Z)

X + !X = 1 e X1=X XY + XZ = X (Y + Z)

X + !X = 1 (a¯ b¯ c¯) + (a¯ b¯ c) + (a¯ b c) + (a b¯ c) + (a b c)

Teorema del consenso

Dimostrazione

(6)

Porte NAND e porte NOR

Convenienti:

Sono le porte più economiche da realizzare (solo 2 transistor) Hanno la latenza minore (vel maggiore) delle porte a 2 ingressi Molto popolari!

Nota:

A NOR A = \A B NAND B = \B

(verificare nella tabella!)

quindi: con un NAND (o un NOR) posso fare un NOT

Un NAND seguito da un NOT = AND Un NOR seguito da un NOT = OR

Porte logiche

A /A

/A A  

equivalenti

Porte NAND e porte NOR

Se ho a disposizione solo porte NAND…

(e quindi posso fare anche il NOT)

…allora posso fare anche l’AND , negando il risutato del NAND A AND B = NOT (A NAND B)

Porte logiche

A AB B

NOT

AND (con due NAND!)

(7)

Porte NAND e porte NOR

Se ho a disposizione solo porte NAND…

(e quindi posso fare anche il NOT e anche l’AND )

…allora posso fare anche l’OR , grazie a DeMorgan.

A OR B = NOT (NOT A AND NOT B) = (NOT A) NAND (NOT B)

Porte logiche

A A+B B

OR (con tre NAND!)

Operatori binari (porte logiche) universali

Come abbiamo visto, usando solo porte { AND, OR, NOT }

possiamo implementare a circuito qualsiasi funzione booleana data (con qualsiasi numero di parametri) – v. forme canoniche

Ma, come abbiamo visto, grazie a De-Morgan:

con porte AND e NOT possiamo «fare» porte OR

(e viceversa, con OR e NOT possiamo «fare» porte AND) Quindi, potremmo limitarci a porte AND e NOT e fare tutto con loro

(oppure OR e NOT )

Usando solo NAND possiamo fare NOT e AND quindi possiamo fare tutto

Usando solo NOR possiamo fare NOT e OR quindi possiamo fare tutto

per questo, NAND e NOR sono detti operatori universali (sono gli unici due!)

(8)

Avvertenza

Per progettare un buon circuito (= ottimizzato) che usa solo porte NAND (o solo NOR) non ci si può limitare ad:

costruire un circuito ottimizzato con le porte NOT, AND e OR (come abbiamo visto in questa lezione)

sostiture queste porte con i circuiti visti che usano solo NAND.

(NOT = 1 NAND, AND = 2 NAND, OR = 3 NAND)

Funzionerebbe, ma il risultato sarebbe molto lontano dall’ottimo!

Porte logiche

Funzioni e circuiti combinatori

Due reti equivalenti

F1 = AB + AC F2 = A(B + C)

F1 = AB + AC =

= A (B + C) =

= F2

A

F1 B

C

AB

AC

AB+AC

A

F2 B

C B+C

A(B+C)

Proprietà distributiva

(9)

Ottimizzazione: esempio

/A B C + A /B C + A B /C + A B C =

/A B C + A /B C + A B /C + A B C + A B C + A B C = /A B C + A B C + A /B C + A B C + A B /C + A B C = (/A + A) B C + A C (/B + B) + A B (/C + C) =

BC + AC + AB

Meno costosa e più veloce! (provare)

oppure, andando avanti con le riscritture BC + AC + AB = C (A+B) + AB

Ancora meno costosa (solo 4 porte a due ingressi, anziché 5) Velocità?

Velocità alta VS costo ridotto :

come spesso capita, possono essere due obbiettivi contrastanti

Ottimizzazione: esempio

Altro possibile svolgimento

/A B C + A /B C + A B /C + A B C= /A B C + A /B C + A B (/C + C ) =

/A B C + A /B C + A B 1= /A B C + A /B C + A B = /A B C + A ( /B C + B) = /A B C + A ( C + B ) = /A B C + A B+ A C = B ( /A C + A) + A C = B ( C + A ) + A C .

// metto in evidenza AB // regola: inversa // regola: idempotenza // metto in evidenza A // assorbimento // distribuisco A // metto in evidenza B // assorbimento

(10)

Esempio dell’intero processo 1/5

Numeri a led (cosiddetti “Seven-segment display”) : costruiamo un piccolo circuito combinatorio che calcola lo stato (acceso, spento) di uno dei 7 led del display dobbiamo accendere sul display una cifra in base 8 espresso da tre bit dati in igresso in base 2

la cifra da esprimere è espressa con tre bit A,B,C

000 ABC

001 ABC

010 ABC

011 ABC

100

ABC 101

ABC 110 ABC

111 ABC

Esempio dell’intero processo 2/5

Numeri a led (“Seven-segment display”) in base 8:

risolviamo per il led in alto

000

ABC 001

ABC 010

ABC 011

ABC 100

ABC 101

ABC 110 ABC

111 ABC

acceso spento acceso acceso spento acceso acceso acceso A B C X 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

tabella

di veritá

(11)

Esempio dell’intero processo 3/5

Come SOMMA DI PRODOTTI (1ma forma canonica)

\A \B \C + \A B \C + \A B C + A \B C + A B \C + A B C

Come PRODOTTO DI SOMME (2da forma canonica)

( A + B + \C ) ( \A + B + C)

(usiamo questa! meno 0 che 1)

A B C X 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

Esempio dell’intero processo 4/5

Ottimizzazione:

// start: 5 operatori binari, 2 not ( A + B + \C ) ( \A + B + C)

= // distributiva: ( X + Y ) ( X + Z ) = X + YZ B + ( A + \C ) ( \A + C)

= // distr (2 volte): X( Z + K ) = XZ+XK B + A \A + AC + \C \A + C \C

= // inverso (2 volte): X \X = 0 B + 0 + AC + \C \A + 0

= // elem neutro B + AC + \A \C

// end: 4 opeatori binari, 2 not

(12)

Esempio dell’intero processo 5/5

Rete combinatoria per: B + AC + \A\C

A B C

or a tre ingressi (costa due or)

Esercizi proposti

Simulare la rete che abbiamo costruito e verificare se soddisfa la tabella di verita’

Stimare la velocita’ del circuito

(tempi di latenza (nanosec): AND:2, OR:3, NOT:1)

Costruire la tabella di verita’ per l’espressione boolana ottimizzata e verificare che sia la stessa tabella di verita’

Scrivere l’espressione booleana associata al circuito e verificare che sia la stessa espressione booleana ottimizzata

Costruire la tabella di verita’ per l’espressione booleana non ottimizzata e verificare che sia la tabella dalla quale siamo partiti Ottimizzare anche l’espressione in 1ma forma normale

Scrivere il circuito risultante.

Paragonarlo con quello ottenuto dalla 2 forma.

Scrivere il circuito (ottimizzato) per qualche altro led!

Ripetere gli esercizi sopra per qualche altro led