Metodo di Quine e MC-Cluskey 2/2 -...

Fondamenti di Informatica II Ingegneria Informatica e Biomedica

I anno, II semestre A.A. 2005/2006

Prof. Mario Cannataro Università degli Studi “Magna Graecia” di Catanzaro

Metodo di Quine e MC-Cluskey 2/2

Fondamenti Informatica II - Lez. 04 08.05.2007 2

Indice

1.  Riepilogo 2.  Soluzione esercizio 3.  Tabelle cicliche 4.  Esercizi


Riepilogo 1

1.  Si ordinano per peso crescente (numero di 1 presenti nella configurazione) i mintermini formando delle classi (mintermini con lo stesso peso);

2.  Ogni configurazione di una classe viene confrontata con tutte quelle

della classe successiva; le coppie di configurazioni che differiscono per un bit vengono fuse creando una nuova tabella;

3.  Si ripete il punto 2 per la nuova tabella fino a quando non sia più

possibile fondere le configurazioni; le configurazioni che non sono state usate per la fusione sono tutti implicanti primi.

Data una funzione f come sommatoria di

∑m (p0, p1,……..,pn)


Riepilogo 2

Realizzazione della tabella di copertura: n  Essa viene realizzata mediante la tabella degli implicanti

primi. n  La tabella degli implicanti primi è una matrice binaria

dove: - Gli indici delle righe sono gli implicanti primi individuati - Gli indici delle colonne sono i mintermini della funzione - L’elemento aij della matrice assume il valore X se il

mintermine della colonna j è coperto dall’implicante della riga i.


Criteri di minimizzazione della tabella di copertura: n  Questa fase procede finchè sono possibili le regole: - dominanza - essenzialità n  Regola della dominanza di riga: si verifica ogniqualvolta un implicante pi copre

tutti i mintermini coperti dall’implicante pj più almeno uno. Si dice in tal caso che l’implicante pi domina l’implicante pj. L’implicante dominato può essere cancellato.

Riepilogo 3


n  Regola della dominanza di colonna: si verifica ogniqualvolta ogni implicante primo che copre la colonna cj copre anche la colonna ci ma non viceversa. Si dice in tal caso che la colonna ci domina la colonna cj. La colonna dominante ci può in questo caso essere eliminata.

Riepilogo 4


n  Regola dell’essenzialità: se p è un implicante essenziale allora: - la riga p viene eliminata dalla tabella; - l’implicante p viene memorizzato;

- tutte le colonne contrassegnate con X sulla riga p vengono cancellate.

Riepilogo 4


Soluzione esercizio Funzione: ∑4 (0,1,4,5,7,12,13,15)

X4 X3 X2 X1

0 0 0 0 0

1 0 0 0 1

4 0 1 0 0

5 0 1 0 1

7 0 1 1 1

12 1 1 0 0

13 1 1 0 1

15 1 1 1 1

Configurazioni Corrispondenti:

⌐X4 ⌐X3 ⌐X2 ⌐X1 ⌐X4 ⌐X3 ⌐X2 X1 ⌐X4 X3 ⌐X2 ⌐X1 ⌐X4 X3 ⌐X2 X1 ⌐X4 X3 X2 X1

X4 X3 ⌐X2 ⌐X1 X4 X3 ⌐X2 X1

X4 X3 X2 X1

Mintermini (1) della funzione:

23 22 21 20


Ogni configurazione di una classe viene confrontata con tutte quelle della classe successiva, fondendo le sole configurazioni che differiscono di 1 bit.

Fase 1

X4 X3 X2 X1

0 0 0 0 0

1 0 0 0 1

4 0 1 0 0

5 0 1 0 1

12 1 1 0 0

7 0 1 1 1

13 1 1 0 1

15 1 1 1 1

X4 X3 X2 X1 0/1 0 0 0 - 0/4 0 - 0 0 1/5 0 - 0 1 4/5 0 1 0 -

4/12 - 1 0 0 5/7 0 1 - 1

5/13 - 1 0 1 12/13 1 1 0 - 7/15 - 1 1 1

13/15 1 1 - 1


Le iterazioni terminano fino a quando non è più possibile fondere nessuna riga.

Quando una stessa combinazione è generata da più righe, si riporta una sola volta la combinazione e si marcano tutte le righe.

Fase 1

X4 X3 X2 X1 0/1/4/5 0 - 0 - 0/4/1/5 0 - 0 - 4/5/12/13 - 1 0 - 4/12/5/13 - 1 0 - 5/7/13/15 - 1 - 1 5/13/13/15 - 1 - 1


Fase 1

X4 X3 X2 X1 0/1/4/5 0 - 0 - 4/5/12/13 - 1 0 - 5/7/13/15 - 1 - 1

X4 X3 X2 X1 0/1/4/5 0 - 0 - 0/4/1/5 0 - 0 - 4/5/12/13 - 1 0 - 4/12/5/13 - 1 0 - 5/7/13/15 - 1 - 1 5/13/13/15 - 1 - 1

Le configurazioni che generano le stesse combinazioni vengono riportate una sola volta.

Si può scegliere una configurazione piuttosto che un’altra indistintamente.


Fase 2

Tabella degli implicanti primi essenziali

X4 X3 X2 X1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1

0 - 0 - X X X X - 1 0 - X X X X - 1 - 1 X X X X

Z= (⌐X2 ⌐X4) la prima riga viene memorizzata

X4 X3 X2 X1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 1

0 - 0 - X X X X - 1 0 - X X X X - 1 - 1 X X X X

La prima riga (0 - 0 -) è Essenziale per cui :


Fase 2

X4 X3 X2 X1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1

- 1 0 - X X

- 1 - 1 X X X


Z= (⌐X2 X3)

X4 X3 X2 X1 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1

- 1 0 - X X

- 1 - 1 X X X

La prima riga (- 1 0 -) è Essenziale per cui :


Fase 2


X4 X3 X2 X1 1 0 1 0 1 1 1 1

- 1 - 1 X X

Z= (X1 X3)

Z = (⌐X2 ⌐X4) + (⌐X2 X3) + (X1 X3)

Ciò che rimane è la seguente tabella

La soluzione finale è:


Tabelle Cicliche

n  ATTENZIONE: Ci sono situazioni cicliche in cui nessuna regola (essenzialità, dominanza) è applicabile pur non avendo raggiunto una situazione di minimalità.

Si può in questo caso applicare una ricerca esaustiva scegliendo, in tutti i modi possibili, un implicante “come se” fosse essenziale e confrontando poi i risultati per determinare la soluzione minima.


Tabelle Cicliche

C1 C2 C3 C4 C5

R1 x x

R2 x x

R3 x x x

R4 x x x

Come si vede dalla tabella su riportata non è possibile applicare nessun criterio di minimizzazione.

Come si procede?


Tabelle Cicliche

C1 C2 C3 C4 C5

R1 x x R2 x x R3 x x x R4 x x x

Si procede per casi o meglio si deve costruire un albero di soluzioni per poi scegliere la tabella che ottimizza la funzione.

Fissiamo la nostra attenzione su R1 e consideriamo il caso in cui:

1.  R1 DOMINATA

2.  R1 ESSENZIALE


Tabelle Cicliche

C1 C2 C3 C4 C5 R1 x x R2 x x R3 x x x R4 x x x

C1 C2 C3 C4 C5 R2 x x R3 x x x R4 x x x

1.  R1 viene eliminata e si procede prendendo in esame la nuova tabella

R1 DOMINATA


Tabelle Cicliche


2. Come si vede R3 diventa essenziale

R1 DOMINATA C1 C2 C3 C4 C5 R2 x x R3 x x x R4 x x x

Per cui la riga R3 viene eliminata ed anche tutte le colonne coperte dalla riga R3.

Infine si memorizza R3.

Z=R3


Tabelle Cicliche


3. Come si vede R4 diventa essenziale

R1 DOMINATA

La nuova tabella ottenuta evidenzia la riga R4 come essenziale procedendo come nel caso precedente R4 viene eliminata, ed anche tutte le colonne coperte dalla riga R4.

Infine si memorizza R4.

Z=R3+R4

C1 C3 R2 x R4 x x


Tabelle Cicliche

R1 DOMINATA

C1 C3 R2 x R4 x x

Come è possibile intuire dopo l’ultima semplificazione non è più possibile effettuare altre semplificazioni per cui la nostra funzione è descritta da:

Z=R3+R4

Ma cosa succede se R1 non è Dominata ma ESSENZIALE ?


Tabelle Cicliche


R1 ESSENZIALE


1.  R1 essenziale per cui la riga R1 viene eliminata ed anche tutte le colonne coperte dalla riga R1. Infine si memorizza R1.

Z=R1


Tabelle Cicliche


R1 ESSENZIALE

C3 C4 C5 R2 x x R3 x x R4 x x

2. Otteniamo una nuova tabella che ci riporta al caso iniziale dobbiamo applicare nuovamente le considerazioni fissando la nostra attenzione su R2 e considerandola come:

2.1. R2 ESSENZIALE

2.2. R2 DOMINATA

Z=R1


Tabelle Cicliche

R1 ESSENZIALE C3 C4 C5

R2 x x R3 x x R4 x x

Z=R1


R2 ESSENZIALE

Z=R1+R2

Si procede sempre allo stesso modo memorizziamo R2 e cancelliamo righe e colonne.


Tabelle Cicliche

R1 ESSENZIALE

C5 R3 x R4 x

Z=R1 C3 C4 C5


R2 ESSENZIALE

Z=R1+R2+R3

In questo caso è indifferente scegliere R3 piuttosto che R4.

Ora vediamo il caso in cui scegliamo la riga R2 come DOMINATA


Tabelle Cicliche

R1 ESSENZIALE C3 C4 C5


Z=R1


R2 DOMINATA

Z=R1

Si procede sempre allo stesso modo eliminando la riga R2.


Tabelle Cicliche

R1 ESSENZIALE

Z=R1 C3 C4 C5

R3 x x R4 x x

R2 DOMINATA

Z=R1+R3+R4

Come si vede sia R3 che R4 sono essenziali per cui la nostra z è data:

C3 C4 C5 R3 x x R4 x x

Una volta ottenute le varie forme minimizzate, come detto, si sceglie quella che meglio minimizza la funzione considerata.


Esercizio 1/4

Funzione: ∑4 (0,2,4,6,7,9,11,15)

Configurazioni Corrispondenti: Mintermini (1) della funzione:

X4 X3 X2 X1 0 0 0 0 0 2 0 0 1 0 4 0 1 0 0 6 0 1 1 0 7 0 1 1 1 9 1 0 0 1 11 1 0 1 1 15 1 1 1 1

⌐X4 ⌐X3 ⌐X2 ⌐X1 ⌐X4 ⌐X3 X2 ⌐X1 ⌐X4 X3 ⌐X2 ⌐X1 ⌐X4 X3 X2 ⌐X1 ⌐X4 X3 X2 X1

X4 ⌐X3 ⌐X2 X1 X4 ⌐X3 X2 X1 X4 X3 X2 X1



X4 X3 X2 X1 0 0 0 0 0 2 0 0 1 0 4 0 1 0 0 6 0 1 1 0 9 1 0 0 1 7 0 1 1 1 11 1 0 1 1 15 1 1 1 1

X4 X3 X2 X1 0/2 0 0 - 0 0/4 0 - 0 0 2/6 0 - 1 0 4/6 0 1 - 0 6/7 0 1 1 - 9/11 1 0 - 1 7/15 - 1 1 1 11/15 1 - 1 1

Esercizio 2/4



X4 X3 X2 X1 0/2 0 0 - 0 0/4 0 - 0 0 2/6 0 - 1 0 4/6 0 1 - 0 6/7 0 1 1 - 9/11 1 0 - 1 7/15 - 1 1 1 11/15 1 - 1 1

X4 X3 X2 X1

0/2/4/6 0 - - 0

6/7 0 1 1 -

9/11 1 0 - 1

7/15 - 1 1 1

11/15 1 - 1 1

Esercizio 3/4


X4 X3 X2 X1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 - - 0 X X X X 0 1 1 - X X 1 0 - 1 X X - 1 1 1 X X 1 - 1 1 X X

Esercizio 4/4

Tabella di copertura

Z=(⌐X4 ⌐X1)+(X4 ⌐X3 X1)+(X3 X2 X1)


Esercizi

n  Minimizzare col metodo di Quine-McCluskey la seguente rete combinatoria :

( )∑415,14,13,12,8,4,3,2,1,0

Metodo di Quine e MC-Cluskey 2/2 -...

Documents

Transcript of Metodo di Quine e MC-Cluskey 2/2 -...