Minimizzazione di reti/funzioni logiche

con le Mappe di Karnaugh

12 ottobre 2015

Punto della situazione

• Stiamo studiando le reti logiche costruite a partire dalle porte logiche AND, OR, NOT per progettare l’ALU (Unità Logico Aritmetica), componente essenziale del calcolatore.

• Reti logiche = espressioni booleane

• Obiettivo di oggi: minimizzazione di espressioni SOP con le mappe di Karnaugh

Operatori logici

• Una funzione di variabili binarie e a valore binario viene detta funzione logica o di commutazione.

• Ogni funzione logica può essere definita in termini di semplici operatori logici di 1 o 2 variabili: AND, OR, NOT.

• Esistono però degli altri operatori logici importanti: XOR, NAND, NOR.

La combinazione delle variabili e degli operatori viene chiamata espressione logica o booleana.

Espressione SOPLetterale = variabile o la sua negazione

• Un’espressione booleana è in forma normale SOP(Sum Of Products) quando è l’OR/somma di AND/prodotto di letterali

• Mintermine = prodotto di letterali in cui compare ognivariabile o vera o negata

• Una espressione normale SOP è in forma canonica SOP se i suoi termini sono tutti mintermini

Scambiando Somma con Prodotto si definiscono le espressioni POS

3131321 xxxxxxx

321321321 xxxxxxxxx

Risultati principali

Corrispondenza fra funzioni logiche e reti logiche:

Analisi: data una rete determinare la funzione calcolata

Sintesi: data una funzione logica costruire una rete che la calcola

• Per ogni funzione logica possiamo costruire una rete logica che la realizza e viceversa

• Ogni funzione logica può essere espressa in termini soltanto di AND, OR, NOT.

Analisi e Sintesi di reti

• Analisi è abbastanza semplice:– Calcola per ogni porta logica di cui sono specificati

tutti gli input l’espressione booleana associataall’output• Fino ad ottenere l’espressione associata al terminale d’uscita

della rete

• Per la sintesi di una funzione logica f:1. Da f alla tavola di verità2. Dalla tavola di verità all’espressione «SOP»3. Dall’espressione «SOP» ad una rete a due stadi: il primo di

porte AND, il secondo con una sola porta OR

Tavole di verità di minterminiPer ogni mintermine, la tavola di verità ha un solo valore 1.

Per esempio:

se f = x3 x2 x1 allora avrà un solo 1 in corrispondenza di x3=0, x2=1, x1=1.

• Ricorda:

• Il prodotto è 1 sse ogni fattore è 1x3 x2 x1 f

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 0

Viceversa, se la tavola di verità di f ha un solo valore 1 necessariamente f è un mintermine.

f = x3 x2 x1

Dalla tavola di verità alla SOP: esempio 1Supponiamo di avere una funzione f data tramite la sua tavola di verità

Espressione canonica SOP

x3 x2 x1 f

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 1

1 1 1 0

x3 x2 x1

x3 x2 x1

x3 x2 x1

x3 x2 x1

f(x3,x2 ,x1) = x3 x2 x1 + x3 x2 x1 + x3 x2 x1 + x3 x2 x1

Nota

Dall’espressionecanonica SOP alla rete a due livelli SOP /AND-to-OR: nel primo livello varie porte AND, nel secondo livello solo una porta OR

Nota: le porte sono state estese in modo da poter avere più di 2 ingressi

Minimizzazione di reti combinatorie

Sinonimi:Reti logiche, reti combinatorieFunzioni logiche, booleane, di commutazione

Valutazione delle Prestazioni di una Rete Combinatoria

• Per ogni funzione di commutazione esistonodiverse reti combinatorie che la realizzano– Qual è la migliore?

• Quella che ha le migliori prestazioni

• Le prestazioni di una rete combinatoria vengonomisurate in termini di– Velocità– Costo

• Obiettivo: una tecnica che ci permetta di sintetizzare la rete in modo da massimizzare le prestazioni

15

Costo di una rete/espressione logica

• Il costo della rete dipende da– Numero di porte logiche– Numero di linee di input

• Tra tutte le reti AND-to-OR (SOP) che realizzano unacerta funzione di commutazione una rete è minimale se– Ha il minor numero di porte AND– Tra tutte quelle che hanno il minor numero di porte AND ha

il minor numero di linee di input

• Un’ espressione in forma normale SOP è minimale se– Ha il minor numero di termini prodotto possibile– Tra tutte le espressioni equivalenti che hanno il minor

numero di prodotti ha il minor numero di letterali

16

Minimizzazione di espressioni booleane

• La minimizzazione di espressioni booleane non è un processo semplice e diretto. Si possonoutilizzare le identità o regole dell’algebra booleana.

• Per poche variabili invece è possibile utilizzare la Mappa di Karnaugh per semplificare il processo

– una rappresentazione particolare delle tavole di veritàche consente di individuare facilmente i minterminiadiacenti

– Utile fino a 4 variabili

17

Sintesi di una Rete Minimale

• Data una funzione di commutazione, vogliamosintetizzare una rete combinatoria che la realizza e che

– Sia a due livelli

– Abbia costo minimo

19

MinterminiSia f una funzione su 3 variabili x3, x2, x1.

Letterale = variabile o la sua negazione

Mintermine = prodotto di letterali in cui compare ogni variabile o vera o negata

Ad ogni mintermine associamo una tripla binaria b3b2b1 dove bi=1 se xi compare in forma vera, 0 altrimenti. Per esempio:

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

x3 x2 x1

m0

m1

m2

m3

m4

m5

m6

m7

mintermini

5)101(123 101 mmxxx

5)101(123 101 mmxxx

0)000(123 000 mmxxx

Minimizzazione di una Espressione SOP

• Si parte dall’espressione in forma canonica SOP

• Due mintermini sono detti adiacenti se differiscono su unasola variabile

21

1234 xxxx1234 xxxx

2341123412341234 )( xxxxxxxxxxxxxxxx

Un’espressione che contiene due mintermini adiacenti puòessere minimizzata nel seguente modo

Da 2 prodotti e 8 occorrenze di letterali siamo passati a 1 prodotto e 3 letterali

Abbiamo bisogno di un metodo che ci permette di individuarevelocemente i mintermini adiacenti

Rappresentazione di una funzione sulla Mappa

f = m0 + m2 + m3 + m4 + m5

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

10111100

fx3 x2 x1

f0f1f2f3f4f5f6f7

m0

m1

m2

m3

m4

m5

m6

m7

mintermini f0

f1

f2

f3

f6

f7

f4

f5

1

0

1

1

0

0

1

1

1 1

Rappresentata con la tavola di verità e .... con la mappa di Karnaugh

Nella colonna i mintermini vicini non sono adiacenti: m1=001 non è adiacente di m2=010.Nella mappa invece si!

Mappe di Karnaugh• Sono tabelle a due dimensioni che rappresentano la tavola di verità della

funzione in un modo diverso.

• Hanno 2n quadrati se n è il numero di variabili

• Ogni quadrato contiene il valore fi di un mintermine mi

23

f0

f1

f0

f1

f2

f3

f0

f1

f2

f3

f6

f7

f4

f5

f0

f1

f4

f5

f12

f13

f8

f9

f3

f2

f7

f6

f15

f14

f11

f10

Mappe di Karnaugh• Etichettiamo ogni casella con la corrispondente configurazione degli

input– Ogni casella identifica un mintermine– Le etichette di caselle adiacenti sulla mappa differiscono per un solo bit

e corrispondono a mintermini adiacenti. Sono adiacenti anche le caselledella prima e ultima colonna, etc. La mappa è un toroide (o ciambella….)

24

0

1

00

01

10

11

0000

0001

0100

0101

1100

1101

1000

1001

000

001

010

011

110

111

100

101

0011

0010

0111

0110

1111

1110

1011

1010

Adiacenti

Adiacenti

Adiacenti

Mappe di Karnaugh• Etichettiamo ogni casella con la corrispondente configurazione degli

input– Ogni casella identifica un mintermine– Le etichette di caselle adiacenti sulla mappa differiscono per un solo bit

e corrispondono a mintermini adiacenti

25

0

1

00

01

10

11

000

001

010

011

110

111

100

101

0000

0001

0100

0101

1100

1101

1000

1001

0011

0010

0111

0110

1111

1110

1011

1010

x4x3

00 01 11 10x2x1

00

01

11

10

Adiacenti

x3x2

00 01 11 10x1

Adiacenti

0

1

Etichettatura delle Mappe di KarnaughLe righe sui bordi della tabelle identificano le aree dellatabella contenenti caselle in cui una certa variabile èpresente in forma vera (1)

26

x1 x1

x2

x1

x2

x3

x1

x2

x3

x4

0

1

00

01

10

11

0000

0001

0100

0101

1100

1101

1000

1001

000

001

010

011

110

111

100

101

0011

0010

0111

0110

1111

1110

1011

1010

Rappresentazione di Prodotti sulla Mappa28

x1

x2

x3

x4

23 xxf

x2

x3

Un prodotto di letterali appare sulla mappa come l’intersezionedelle regioni corrispondenti a ciascuno dei letterali Tutte le celle nella regione individuata contengono 1 e le altre

contengono 0

23 xx

…continua

x1

x2

x3

x4

0000

0001

0100

0101

1100

1101

1000

1001

0011

0010

0111

0110

1111

1110

1011

1010

0

0

1

1

1

1

0

0

0

0

0

0

0

0

0

0

23 xxf

Rappresentazione di Prodotti sulla Mappa

• Sulla mappa per 4 variabili– Un prodotto di 1 letterale identifica una regione di 8 celle– Un prodotto di 2 letterali identifica una regione di 4 celle– Un prodotto di 3 letterali identifica una regione di 2 celle– Un prodotto di 4 letterali (mintermine) identifica una singola

cella

• Le celle della regione devono essere adiacenti– Celle su bordi opposti della mappa sono adiacenti– La mappa è un toroide

• Per convenzione la regione identificata da un prodotto di letterali contenente 2k celle è detta k-cubo

30

Alcuni possibili cubi

Riprendiamo l’esempio di prima

f (x3, x2, x1) = m0 + m2 + m3 + m4 + m5

f0

f1

f2

f3

f6

f7

f4

f5x1

x3

x2

1

0

1

1

0

0

1

1x1

x3

x2

123123123123123 xxxxxxxxxxxxxxxf

2323123

11231123123 )()(

xxxxxxx

xxxxxxxxxxx

Dalla tavola di verità otteniamo la f come somma di 5 mintermini (le 5 occorrenze di 1) e poi possiamo ridurre 2 coppie di mintermini adiacenti in 2 prodotti di letterali. Sulla mappa possiamo individuare facilmente le coppie di minterminiadiacenti.

Costruzione di Espressioni SOP a partire dallaMappa di Karnaugh

• Data la rappresentazione di una funzione sulla Mappa di Karnaugh possiamo “ricoprirla” con una serie di cubi taliche– Ogni cubo contenga solo celle con valore 1

– Ogni 1 della tavola di verità sia ricoperto da almeno un cubo

33

Ogni cubo rappresentaun prodotto di letterali

L’unione dei cubi èun’espressione normalein forma SOP

1

x3

x2

1

0 1 0 1

0 1

2323123 xxxxxxxf

x1

Insiemi minimali di Cubi• Tra tutti gli insiemi di cubi che ricoprono una funzione

quelli minimali sono gli insiemi che:

– Contengono il minor numero possibile di cubi/termini prodottoe, a parità di numero, quelli più grandi

34

Insieme di cubi minimale

1

x3

x2

1

0 1 0

0

Insieme di cubi non minimale

x1

23123123123 xxxxxxxxxxxf 2323123 xxxxxxxf

1

x3

x2

1

0 1 0 1

0 1

x1 1

1

Procedura di Minimizzazione

Data la funzione di commutazione f espressa tramite la suatavola di verità rappresentata su una mappa di Karnaugh

1. Per ogni 1 nella mappa determiniamo i cubi massimali, cioè non contenuti in altri cubi, che lo contengono e che ricoprono solo celle contenenti 1

2. Individuiamo i cubi massimali essenziali– Cubi che ricoprono 1 coperti solo da quel cubo massimale

3. Scegliamo un insieme minimale di cubi massimali chericoprono gli 1 lasciati scoperti dai cubi essenziali

Esempio di Minimizzazione 1

36

),,,,,,,,,( 15141211876310 mmmmmmmmmmORf

x1

x2

x3

x4

Cubi massimali:

x1

x2

x3

x4

Cubi essenziali:

Esempio di Minimizzazione 1 (ctd.)

37

),,,,,,,,,( 15141211876310 mmmmmmmmmmORf

x1

x2

x3

x4

Cubo essenziale

4214322132 xxxxxxxxxxf

10 termini /porte AND40 letterali/ linee di input

4 termini /porte AND10 letterali/linee di input

Insieme minimale:

Esempio di Minimizzazione 2

),,,,,,,( 14111076310 mmmmmmmmORf

x1

x2

x3

x4

Cubi essenziali

x1

x2

x3

x4

Cubi massimali

Esempio di Minimizzazione 2 (ctd.)

),,,,,,,( 14111076310 mmmmmmmmORf

x1

x2

x3

x4

Cubo essenziale

432432

421321

xxxxxx

xxxxxxf

x1

x2

x3

x4

432432

321421

xxxxxx

xxxxxxf

Due soluzioni distinte minimali!

Esempio (maggioranza)Sia f(x3,x2,x1) la funzione che vale 1 se (e solo se) la maggioranza delle variabili vale 1.

Ieri abbiamo visto:

x3 x2 x1 f

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

123123123123123 ),,( xxxxxxxxxxxxxxxf

f = m3 + m5 +m6 + m7

231312 xxxxxx

Rappresentazione della funzione sulla Mappa

f0

f1

f2

f3

f6

f7

f4

f5x1

x3

x2

0

0

0

1

1

1

0

1x1

x3

x2

f = m3 + m5 +m6 + m7

0

0

0

1

1

1

0

1x1

x3

x2

231312 xxxxxxf

Riepilogo e riferimenti

• Analisi e sintesi di rete logiche

• Minimizzazione di reti logiche con le mappe di Karnaugh

[PH] appendice B.1, B.2

[PH_IIIed] appendice C.1, C.2, C.3

[P] par. 4.1, 4.2, 4.3, 4.4.