Post on 03-May-2015
University of PadovaInformation Engineering Dept. – Microelectronics Lab.
Corso di Laurea in Ingegneria dell’Informazione
Elettronica Digitale- Lezione 3 -
Andrea Gerosa - gerosa@dei.unipd.itTel. 049-827-7728
Ottimizzazione circuitale
Obiettivo: implementazione più semplice Procedura formale Definizione di un criterio di costo:
• costo di letterali (L)• costo di ingressi a porte logiche (gate) (G)• costo di ingressi negati a porte logiche (GN)
Numero di letterali che compongono un’espressione logica
Esempi:• F = BD + A C + A L=8• F = BD + A C + A + AB L=11• F = (A + B)(A + D)(B + C + )( + + D) L=10D
L
DB C
B B D C
B C
G e GN Numero di ingressi alle porte logiche di tutti i livelli (G – senza
contare le inversioni, GN – contando le inversioni)
Nel caso di SOP e POS, si trova sommando:• tutti i letterali (L)
• il numero di termini della somma o del prodotto, escludendo i termini a letterale singolo (G) e
• il numero di variabili negate (GN).
Esempio:
F = A + B C +
Costo
A
BC
F
B CL = 5G = L + 2 = 7
GN = G + 2 = 9
Esempio 2:
F = A B C + L = 6 G = 8 GN = 11 F = (A + )( + C)( + B) L = 6 G = 9 GN = 12
Costo
B C
A
ABC
F
C B
F
ABC
A
Mappe di Karnaugh (K-map)
K-map = insieme di caselle• è una rappresentazione grafica di una funzione logica• ogni casella rappresenta un mintermine• caselle adiacenti differiscono per ila valore di una sola
variabile• individuiamo la soluzione minima raggruppando
opportunamente le caselle La K-map è una rielaborazione di una tebella di
verità
K-map a 2 variabili
y = 0 y = 1
x = 0 m
0 = m1 =
x = 1 m2 =
m
3 =
yx yx
yx yx
K-Map e tabella di verità
K-Map
(x,y)
F(x,y)
0 0 a 0 1 b 1 0 c 1 1 d
y = 0 y = 1 x = 0 a b x = 1 c d
Semplificazione
F(x,y) = x
I due “1” adiacenti possono essere combinati in un unico rettangolo, sfruttando il teorema di semplificazione:
F = x y = 0 y = 1
x = 0 0 0
x = 1 1 1
xyxyx)y,x(F
Semplificazione
G(x,y) = x + y G = x+y y = 0 y = 1
x = 0 0 1
x = 1 1 1
yxyxxyyxyx)y,x(G
K-Map a tre variabili
yz=00 yz=01 yz=11 yz=10
x=0 m0 m1 m3 m2
x=1 m4 m5 m7 m6
yz=00 yz=01 yz=11 yz=10
x=0
x=1
zyx zyx zyx zyx
zyx zyx zyx zyx
Rappresentazioni alternative
y
z
x
10 2
4
3
5 67
x
y
zz
yy z
z
10 2
4
3
5 67
x
0
1
00 01 11 10
x
y
x
10 2
4
3
5 67
1
11
1
z
x
y10 2
4
3
5 671 11
1
z
(2,3,4,5) z)y,F(x, m
(3,4,6,7) z)y,G(x, m
Mappe a più variabili
ABCCBACBACBA
CBAF
,,
Semplificare le funzioni con le Mappe
7,5,2,1,, mCBAF ABC 00 01 11 10
0
1
0
1
2
3
6
7
4
5
1
1
1 1
0
0
0 0
CACB
CBA
ABCCBACBACBACBA
ACCBCBA
Come raggruppare le celle
Data la Mappa di K. di una funzione logica F a n variabili (quindi con 2n celle),
è possibile raggruppare k mintermini (cioè celle a “1”):• se in tale insieme esistono =log2k variabili che
assumo tutte le k possibili combinazioni binarie
Sono gruppi di celle adiacenti sulla Mappa Il gruppo rappresenta un termine prodotto
che dipende da n- variabili• è un implicante
yzyyz
zyxzyxzyxzyx)z,y,x(F
x
y10 2
4
3
5 671 1
11
z
m(2,3,6,7) F
Definizioni
Implicante: data la funzione F(x1,…,xn), un termine prodotto P(x1,…,xn) è un implicante di F se:• P(x1,…,xn)=1 F(x1,…,xn)=1
• qualsiasi gruppo di celle sulla K-Map
Implicante primo: un implicante è primo se:• tutti i termini prodotto ottenuti eliminando uno
dei letterali dell’implicante, non sono più implicanti della funzione F
• gruppi di celle sulla K-Map che non possono essere contenuti in gruppi più grandi
Implicanti
I 4 mintermini sono implicanti
Esistono 4 implicanti a 2 variabili (2 celle)
Esiste 1 implicante primo a 1 variabile (4 celle)
x
y10 2
4
3
5 671 1
11
z
m(2,3,6,7) F
xyzzxyyzxzyx ,,,
yzzyxyyx ,,,
y
Teorema dell’implicante primo
Def. Somma minima di una funzione F: è la realizzazione come SOP a costo minimo.
Teorema. I termini prodotto della somma minima sono tutti implicanti primi.• Dim. x assurdo: sia P(x1,…, xn) un implicante
non primo che compone la somma minima.
• esiste xk tale che P*=P(x1,…xk-1,xk+1,…, xn) è un implicante di F.
• sostituendo P con P* nella somma minima si ottiene una realizzazione di F a costo minore
Somma minima
È composta da soli implicanti primi• non necessariamente tutti gli implicanti primi
Obiettivo: individuare sulla K-Map tutti gli implicanti primi• gruppi di celle più grandi
Es. 2.2
131175321 ,,,,,,:,,, mmmmmmmsetOndcbaF
ABCD 00 01 11 10
00
01
11
10
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
111
11 1
1
Es. 2.2
Es. 2.3
151413121195431 ,,,,,,,,:,,, mmmmmmmmmmsetOndcbaF
ABCD 00 01 11 10
00
01
11
10
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
11
11 1
111
11
5 implicanti primi• vanno inclusi tutti?
La somma completa (somma di tutti gli implicanti) sicuramente copre la funzione ma non è
necessariamente minima
Es. 2.3
151413121195431 ,,,,,,,,:,,, mmmmmmmmmmsetOndcbaF
ABCD 00 01 11 10
00
01
11
10
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
11
11 1
111
11
3 implicanti sono sufficienti a coprire tutti i mintermini
Implicanti primi essenziali
Def. Data la Mappa di Karnaugh di una funzione F si definisce cella 1-distinta:• un mintermine che è contenuto in un unico
implicante primo
Def. Un implicante primo si definisce essenziale se:• sulla Mappa di Karnaugh include almeno una
cella 1-distinta
Gli implicanti primi essenziali devono essere inclusi nella somma minima.
Es. 2.4
15147543210 ,,,,,,,,:,,, mmmmmmmmmsetOndcbaF
ABCD 00 01 11 10
00
01
11
10
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
11 1
11
11 1
1
5 implicanti primi Cerchiamo le
celle 1-distinte
abccabadcbaF ,,,
Mappa ridotta
ABCD 00 01 11 10
00
01
11
10
0
1
3
2
4
5
7
6
12
13
15
14
8
9
11
10
1
Eliminiamo i mintermini già coperti e gli implicanti primi essenziali
abccabadcbaF ,,,
Chapter 2 - Part 2 30
Terms of Use All (or portions) of this material © 2008 by Pearson
Education, Inc. Permission is given to incorporate this material or
adaptations thereof into classroom presentations and handouts to instructors in courses adopting the latest edition of Logic and Computer Design Fundamentals as the course textbook.
These materials or adaptations thereof are not to be sold or otherwise offered for consideration.
This Terms of Use slide or page is to be included within the original materials or any adaptations thereof.