Mappe di Karnaugh

Mappe di Karnaugh

Sergio PORCU 1

Mappe di Karnaugh

Minimizzazione di funzioni booleane

2

Le mappe di Karnaugh

Dette anche mappe k, servono a minimizzare una funzione booleana nel modo più semplice e soprattutto in modo grafico. Tali mappe sono costituite da tante caselle quante sono le combinazioni dei valori delle variabili d’ingresso (verificabili tramite la tavola di verità) opportunamente disposte una accanto all’altra.

Mappe di Karnaugh

Sergio PORCU 2

3


Una volta disegnata la mappa K si possono individuare, sulla tavola di verità, le righe che danno il valore 1 per la funzione Y e si inserisce un 1 nella casella corrispondente della mappa K; se la funzione è espressa in forma algebrica basterà inserire un 1 nelle caselle corrispondenti ad un minitermine.

4


Quando la mappa è completa, si può procedere al raggruppamento delle caselle adiacenti contenenti un 1 per ottenere una funzione semplificata.

Mappe di Karnaugh

Sergio PORCU 3

5

Le mappe di KarnaughRegole da rispettare:

1. i raggruppamenti possono essere di 1, 2, 4, 8, 16, … caselle adiacenti tra loro (comprese quelle situate ai bordi esterni della mappa);

2. i raggruppamenti devono essere più ampi possibili e sono sovrapponibili parzialmente;

3. una casella già raggruppata può essere unita ad un’altra se ciò forma un gruppo di 2,4,8,etc. caselle.

6


Dopo aver effettuato i raggruppamenti, la funzione viene espressa in forma semplificata come somma di prodotti; i prodotti sono costituiti dalle variabili che non cambiano di valore nel raggruppamento.

Mappe di Karnaugh

Sergio PORCU 4

7


Si ricorda che:

• l’ultima colonna è considerata adiacente alla prima colonna;

• l’ultima riga è considerata adiacente alla prima riga.

8

Esempio con 3 variabili

1111

0011

1101

0001

0110

0010

1100

0000

YCBA

1101

0000

ABC 00 01 11 10

0

1

Y = AC + B’C

Mappe di Karnaugh

Sergio PORCU 5

9

Esempio con 4 variabili

11111

00111

11011

00011

01101

00101

11001

00001

11110

00110

11010

00010

01100

00100

11000

00000

YDCBA

0110

1111

0000

0000

ABCD 00 01 11 10

00

01

11

10

Y = BD+C’D

Mappe di Karnaugh

Education

Transcript of Mappe di Karnaugh