Minimizzazione

Mappe di Karnaugh

Tale tecnica di minimizzazione è basata sull’idea che la somma di due prodotti di letterali può essere sostituita da un singolo prodotto se i due prodotti iniziali differiscono per un solo letterale.

Mappe di Karnaugh

partiamo dalla forma canonica disgiuntiva e introduciamo apposite tabelle con 2n celle

yxz 00 01 11 10 0 0 0 0 0

1 0 1 1 1

1 se il mintermine fa parte della f.n.d.

Mappe di Karnaugh

raggruppiamo gli uno che stanno in celle adiacenti (adiacenti significa anche sopra e sotto o destra e sinistra e quelle poste ai lati opposti della mappa)

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

in gruppi di singoletti, coppie, quadruple…. potenze di 2

Mappe di Karnaugh

i gruppi sono determinati in modo euristico (cioè basato su osservazioni ed esperienza anziché su una teoria)

yx

z 00 01 11 10

0 0 0 0 0

1 0 1 1 1

i blocchi ottenuti sono i mintermini

che cerchiamo

Mappe di Karnaugh

non è possibile applicare il metodo a funzioni con più di 4 variabili in maniera semplice

cerchiamo un altro modo

per poter minimizzare funzioni con più variabili

mappe di Karnaugh: metodo grafico

Metodo di Quine - McCluskey

non è graficodetermino gli implicanti primi (vedremo

cosa sono)cerco il ricoprimento minimo di tali

implicanti

implicanti

x y z f(x, y, z) 0 0 0 10 1 0 00 0 1 00 1 1 11 0 0 01 1 0 01 0 1 01 1 1 1

f implica f

una funzione di n variabili f rico-pre un'altra funzione g (f > g) se f vale 1 dove anche g vale 1 (ma non il vice versa)

un prodotto p di m variabili (m < n)di f è un implicante per f se f > p

implicanti

x y z f(x, y, z) 0 0 0 10 1 0 00 0 1 00 1 1 11 0 0 01 1 0 01 0 1 01 1 1 1

infatti y z vale 1

un implicante p è primo per f se l'eliminazione di un letterale di pdà luogo ad un prodotto p' tale che f > p'

x y z e ~x y znon sono primi: se eliminox e ~x ottengo ancora 1

è un implicante primo

implicanti

x y z v w1 0 0 0 00 0 0 1 11 0 0 1 01 0 1 0 01 0 1 1 01 1 0 0 11 0 1 1 11 1 0 1 11 1 1 1 1

sono tutti i mintermini dellaforma canonica congiuntiva

sono ordinati per peso: numerodi 1 nella riga e peso delle variabili

w è quella che pesa di meno

implicanti

x y z v w1 0 0 0 00 0 0 1 11 0 0 1 01 0 1 0 01 0 1 1 01 1 0 0 11 0 1 1 11 1 0 1 11 1 1 1 1

due "coppie" sono unificabilise differiscono per un solo simbolo

confronto il primo con tutti glialtri, poi il secondo e cosi via... creo una nuova tabella

implicanti

x y z v w1 0 0 0 00 0 0 1 11 0 0 1 01 0 1 0 01 0 1 1 01 1 0 0 11 0 1 1 11 1 0 1 11 1 1 1 1

non unifica con nessuna

per ora la ignoriamo

implicanti

x y z v w1 0 0 0 00 0 0 1 11 0 0 1 01 0 1 0 01 0 1 1 01 1 0 0 11 0 1 1 11 1 0 1 11 1 1 1 1

x y z v w1 0 0 - 01 0 - 0 01 0 - 1 01 0 1 - 01 0 1 1 -1 1 0 - 11 - 1 1 11 1 - 1 1

AKBCDEFGH

implicanti: diamo dei nomi alle righe

x y z v w1 0 0 0 00 0 0 1 11 0 0 1 01 0 1 0 01 0 1 1 01 1 0 0 11 0 1 1 11 1 0 1 11 1 1 1 1

x y z v w1 0 0 - 01 0 - 0 01 0 - 1 01 0 1 - 01 0 1 1 -1 1 0 - 11 - 1 1 11 1 - 1 1

A BCDEFGH

ABACBDCDDFEGFHGH

implicanti: proseguiamo….

x y z v w1 0 0 - 01 0 - 0 01 0 - 1 01 0 1 - 01 0 1 1 -1 1 0 - 11 - 1 1 11 1 - 1 1

ABACBDCDDFEGFHGH

x y z v w

1 0 - - 0 ABCD

AB combina con CD

AC combina con DB

quali sono gli implicanti primi

gli implicanti primi sono quelli che non sono stati fusi con altri: K DF EG FH GH ABCD

Selezione degli implicanti primi

K A B C D E F G H

K X

DF X X

EG X X

FH X X

GH X X

ABCD X X X X

indica che l'implicante primo DF copre D

Selezione degli implicanti primi

trovare un insieme di righe di cardinalità minima tale che, per ogni colonna della tabella, vi sia almeno una riga che abbia una X in quella colonna

Due tecniche:• Dominanza• Essenzialità

Dominanza

Una riga i domina una riga j se i possiede X in tutte le posizioni di j

Essenzialità

Una riga i è essenziale se è l'unica ad avere una X in una certa posizione

Possiamo eliminare le righe essenziali e le relative colonne

Selezione degli implicanti primi

K A B C D E F G H

K X

DF X X

EG X X

FH X X

GH X X

ABCD X X X X

eliminiamo le righe e le colonne

Selezione degli implicanti primi

K A B C D E F G H

K X

DF X X

EG X X

FH X X

GH X X

ABCD X X X X

rimangono tre righe e due colonne

Selezione degli implicanti primi

K A B C D E F G H

K X

DF X X

EG X X

FH X X

GH X X

ABCD X X X X

FH domina GH e DF

Risultato finale

La forma minima è data da

K EG ABCD FH

cioè(~x ~y ~z v w) (x y ~z w)

(x ~y w) (x z v w)

Considerazioni conclusive sulla minimizzazione

Osserviamo che siamo partiti dai letterali potrebbero esserci forme più compatte

La minimizzazione è molto costosa e non sempre si riesce ad ottenere la forma minima