Cenni sull ’ uso delle Mappe di Karnaugh

Mappe di Karnaugh 1

Cenni sull

’

uso delle

Mappe di Karnaugh

PROF. MASSIMO DE SANTO

A B 0 1 0 1 0 1 2 3 0 1 2 3 6 7 4 5 AB C 0 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 A B AB CD A 00 01 11 10 0 1 00 01 11 00 00 01 11 10 C B D

Il Metodo delle Mappe di Karnaugh (K-map)

La K-map è un metodo alternativo per rappresentare la Tabella di Verità che aiuta a visualizzare le adiacenze fino a 6 dimensioni

Oltre questo numero occorre ricorrere a metodi automatizzati

2-variabili

3-variabili

4-variabili

Schema di Numerazione : 00, 01, 11, 10

Mappe di Karnaugh 3

Adiacenze nelle K-Map

Si “avvolge” la mappa dalla prima all’ultima colonna e dalla prima all’ultima riga

000 001 010 01 1 1 10 1 1 1 100 101 00 01 11 10 0 1 AB C A B 011 010 000 001 100 110 101 111 B C A

ESEMPI

F =

A asserita, non cambia B varia

G = B negata, non cambia

A varia Cout = _{F(A,B,C) =} A B 0 1 0 1 0 1 0 1 A B 0 1 1 1 0 0 0 1 A B A B Cin 00 01 11 10 0 1 0 0 0 1 1 1 0 1 AB C A 00 01 11 10 0 1 0 0 0 0 1 1 1 1 B

Mappe di Karnaugh 5

ESEMPI (2)

F = A

A asserita, non cambia B varia

G = B’ B negata, non cambia

A varia

Cout = A B + B Cin + A Cin _{F(A,B,C) = A}

A B 0 1 0 1 0 1 0 1 A B 0 1 1 1 0 0 0 1 A B A B Cin 00 01 11 10 0 1 0 0 0 1 1 1 0 1 AB C A 00 01 11 10 0 1 0 0 0 0 1 1 1 1 B

dalla Tabella alla Mappa

0

A

0

1

B

1

F = F(A, B)

ogni punto della Mappa

rappresenta un mintermine

A

B

F

0

1

0

1

0

0

1

1

-A’B’

Mappe di Karnaugh 7 F(A,B,C) = Σm(0,4,5,7) F = F'(A,B,C) = Σm(1,2,3,6) F' = La duale di F, F'

Semplicemente sostituisce 1 con 0 e viceversa

00 C AB 01 11 10 1 0 0 1 1 1 0 0 A B 0 1 00 C AB 01 11 10 0 1 1 0 0 0 1 1 A B 0 1

ESEMPI (3)

F(A,B,C) = Σm(0,4,5,7) F = B' C' + A C

abbiamo adiacenza da sinistra a destra e dall’alto in basso

F'(A,B,C) = Σm(1,2,3,6) F' = B C' + A' C

Osservate come sia più semplice che usare il Teorema di DeMorgan e l’Algebra Booleana per calcolare il complemento!

La duale di F, F'

Semplicemente sostituisce 1 con 0 e vice versa

00 C AB 01 11 10 1 0 0 1 1 1 0 0 A B 0 1 00 C AB 01 11 10 0 1 1 0 0 0 1 1 A B 0 1

ESEMPI (4)

Mappe di Karnaugh 9

Ancora Esempi: 4 variabili

F(A,B,C,D) = Σm(0,2,3,5,6,7,8,10,11,14,15) F = AB 00 01 11 10 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 00 01 11 10 C CD A D B

F(A,B,C,D) = Σm(0,2,3,5,6,7,8,10,11,14,15)

Trovare il minor numero

possibile di sottocubi

di area massima che

ricoprono il cosiddetto

ON-set della Funzione

AB 00 01 11 10 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 00 01 11 10 C CD A D B

Ancora Esempi: 4 variabili

C + A' B D + B' D' F =

Mappe di Karnaugh 11

La II forma Canonica sulla K-Map

AB 00 01 11 10 1 0 0 1 0 1 0 0 1 1 1 1 1 1 1 1 00 01 11 10 C CD A D B F = (B + C + D) (A + C + D) (B + C + D) F = B C D + A C D + B C D F = B C D + A C D + B C D F = (B + C + D) (A + C + D) (B + C + D) Sostituendo F con F, 0 diventa 1 e viceversa

Punti di indifferenza o “Don't Care”

F(A,B,C,D) = Σm(1,3,5,7,9) + Σd(6,12,13) F = senza don't care

F = con don't care

I punti di Don't Care possono essere 1 o 0 a seconda di cosa è vantaggioso

AB 00 01 11 10 0 0 X 0 1 1 X 1 1 1 0 0 0 X 0 0 00 01 11 10 C CD A D B

Mappe di Karnaugh 13

F(A,B,C,D) = Σm(1,3,5,7,9) + Σd(6,12,13) F = A'D + B' C' D senza don't care

F = C' D + A' D con don't care

I punti di Don't Care possono essere 1 o 0 a seconda di cosa è vantaggioso

Trattando qt don’t care come "1", posso formare un sottocubo di area maggiore

AB 00 01 11 10 0 0 X 0 1 1 X 1 1 1 0 0 0 X 0 0 00 01 11 10 C CD A D B AB _{00 01 11 10} 0 0 X 0 1 1 X 1 1 1 0 0 0 X 0 0 00 01 11 10 C CD A D B

Nella seconda forma: F = D (A' + C') Come sopra ma con

meno letterali

ESEMPIO DI PROGETTO: Comparatore a 2 Bit (1)

Diagramma a Blocchi e

Tabella di Verità

Un K-map a 4 variabili Per ciascuna delle 3 funzioni di output F ₁ 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 F ₂ 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 F ₃ 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 B 0 1 0 1 A 0 0 1 1 =, >, < F ₁ A B = C D F ₂ A B < C D F ₃ A B > C D A B C D N ₁ N ₂

Mappe di Karnaugh 15 F1 = F2 = F3 = AB 00 01 11 10 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 00 01 11 10 C CD A D B K-map for F ₁ AB 00 01 11 10 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 00 01 11 10 C CD A D B K-map for F ₂ AB 00 01 11 10 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 00 01 11 10 C CD A D B K-map for F ₃

ESEMPIO DI PROGETTO: Comparatore a 2 Bit (2)

F1 = A' B' C' D' + A' B C' D + A B C D + A B' C D' F2 = A' B' D + A' C

F3 = B C' D' + A C' + A B D'

A xnor B xnor C xnor D

AB 00 01 11 10 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 00 01 11 10 C CD A D B K-map for F ₁ AB 00 01 11 10 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 00 01 11 10 C CD A D B K-map for F ₂ AB 00 01 11 10 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0 00 01 11 10 C CD A D B K-map for F ₃

ESEMPIO DI PROGETTO: Comparatore a 2 Bit (3)

Mappe di Karnaugh 17 + N 3 X 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 Y 0 0 1 1 0 1 1 0 1 1 0 0 1 0 0 1 Z 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 B 0 1 0 1 A 0 0 1 1 A B C D N ₁ N ₂ X Y Z Diagramma a Blocchi e Tabella di Verità Un K-map a 4 variabili Per ciascuna delle 3 funzioni di output

X = Z = Y = AB 00 01 11 10 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 00 01 11 10 C CD A D B K-map for X AB 00 01 11 10 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 00 01 11 10 C CD A D B K-map for Y AB 00 01 11 10 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 00 01 11 10 C CD A D B K-map for Z

ESEMPIO DI PROGETTO: Adder a 2 Bit (2)

Mappe di Karnaugh 19

X = AC+BCD+ABD Z = BD'+B'D=BxorD

Y = A'B'C+AB'C'+A'BC'D+A'BCD'+ABC'D'+ABCD = B'(A xor C)+A'B(C xor D)+AB(C xnor D)

= B'(A xor C)+D(A xor B xor C)

Usando XOR Si riduce il Gate count Gli 1 sulla diagonale suggeriscono XOR!

La Y K-Map non è minima

AB 00 01 11 10 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 00 01 11 10 C CD A D B K-map for X AB 00 01 11 10 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 00 01 11 10 C CD A D B K-map for Y AB 00 01 11 10 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 00 01 11 10 C CD A D B K-map for Z

ESEMPIO DI PROGETTO: Adder a 2 Bit (3)

\ D \ A \ C Y ₁ A C D \ B B Y ₂

Due implementazioni alternative di Y

(con o senza XOR)

Nota: l’XOR tipicamente richiede 4 porte NAND!

X XOR Y X

Mappe di Karnaugh 21

Esempio di Progetto: BCD Incrementato di 1

W = Y = AB 00 01 11 10 0 0 X 1 0 0 X 0 0 1 X X 0 0 X X 00 01 11 10 C CD A D B AB 00 01 11 10 0 1 X 0 0 1 X 0 1 0 X X 0 1 X X 00 01 11 10 C CD A D B AB 00 01 11 10 0 0 X 0 1 1 X 0 0 0 X X 1 1 X X 00 01 11 10 C CD A D B AB 00 01 11 10 1 1 X 1 0 0 X 0 0 0 X X 1 1 X X 00 01 11 10 C CD A D B Z Y X W X = Z =

W = BCD+AD' Y = A'C'D+CD' AB 00 01 11 10 0 0 X 1 0 0 X 0 0 1 X X 0 0 X X 00 01 11 10 C CD A D B AB 00 01 11 10 0 1 X 0 0 1 X 0 1 0 X X 0 1 X X 00 01 11 10 C CD A D B AB 00 01 11 10 0 0 X 0 1 1 X 0 0 0 X X 1 1 X X 00 01 11 10 C CD A D B AB 00 01 11 10 1 1 X 1 0 0 X 0 0 0 X X 1 1 X X 00 01 11 10 C CD A D B Z Y X W X = B C'+B D'+B'CD Z = D'

Mappe di Karnaugh 23

Definizioni

implicante: singolo elemento dell’ON-set o qualsiasi gruppo di

Elementi che possono essere combinati insieme in una K-map

primo implicante: implicante che non può essere combinato con

Un altro implicante per eliminare un termine

primo implicante essenziale: se un elemento dell’ON-set è coperto

da un singolo primo implicante, esso è un primo implicante essenziale

Obiettivo:

Aggregare implicanti in primi implicanti

Ricoprire l’ON-set col minimo numero di primi implicanti Far sì che i primi essenziali siano presenti in tutte le possibili coperture

Esempi per illustrare le definizioni

6 Primi Implicanti: A' B' D, B C', A C, A' C' D, A B, B' C D essenziali Copertura Minima = B C' + A C + A' B' D 5 Primi Implicanti: B D, A B C', A C D, A' B C, A' C' D essenziali

Implicanti essenziali che formano la Copertura minima AB 00 01 11 10 0 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 00 01 11 10 C CD A D B AB 00 01 11 10 0 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 00 01 11 10 C CD A D B

Mappe di Karnaugh 25

Ancora Esempi

Primi Implicanti: B D, C D, A C, B' C essenziali AB 00 01 11 10 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 00 01 11 10 C CD A D B

Implicanti essenziali che formano la Copertura minima

Algoritmo

: Forma Minima in Somma di Prodotti dalla K-Map

Step 1: Scegli un elemento dell’ON-set che non sia già coperto da Un implicante

Step 2: Trova il “massimo" raggruppamento di 1 e X adiacente

all’elemento. Ricorda di considerare le adiacenze alto/basso sinistra/destra. Questo forma i primi implicanti

(sempre un numero di elementi pari ad una potenza di 2).

Ripeti gli Step 1 e 2 per trovare TUTTI i primi implicanti

Step 3: Ricontrolla gli 1 nella K-map. Se coperti da un singolo primo

implicante, questo è essenziale, e partecipa alla copertura finale. Gli 1 che ricopre non devono essere ulteriormente esaminati

Step 4: Se rimangono 1 non coperti da primi implicanti essenziali, allora Scegli il minimo numero di primi implicanti che ricoprono gli

Mappe di Karnaugh 27

Esempio

: ƒ(A,B,C,D) = m(4,5,6,8,9,10,13) + d(0,7,15) K-map iniziale AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B

K-map Iniziale Primi intorno a A' B C' D' AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B

Esempio (2)

Mappe di Karnaugh 29

K-map iniziale Primi intorno a

A' B C' D' Primi intorno a A B C' D AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B

Esempio (3)

Esempio (4)

Primi intorno a A B C' D AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B

Mappe di Karnaugh 31

Esempio (5)

Primi intorno a A B' C' D' Primi intorno a A B C' D AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B

Primi intorno a A B' C' D' Primi intorno a A B C' D AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B AB 00 01 11 10 X 1 0 1 0 1 1 1 0 X X 0 0 1 0 1 00 01 11 10 C CD A D B Primi essenziali e Copertura Minima

Esempio (6)