algebra booleana e logica combinatoria

Circuiti combinatori e sequenziali
X1
X2
Xm
Switching
Network
Z1
Z2
Zm
Circuito combinatorio: un circuito senza “memoria”. L’output è
completamente determinato dai valori dell’input.
Circuito sequenziale: il circuito possiede uno stato interno.
L’output è determinato dall’input e dallo stato interno.
1
Funzioni logiche: algebra booleana
INVERTER
X
X’
C=A·B
B
0
1
0
1
C
0
0
0
1
se A=1 E B=1 allora C=1
altrimenti C=0
C=A+B
A
0
0
1
1
B
0
1
0
1
C
0
1
1
1
se A=1 O B=1 allora C=1
altrimenti C=0
OR
A
B
se X=0 allora X’=1
se X=1 allora X’=0
A
0
0
1
1
AND
A
B
X’
1
0
X
0
1
2
gate AND
Diagrammi
temporali
3
gate OR
OR Gate
4
inverter
Inverter
5
Il contatore binario sincrono a due bit
Possiamo generare automaticamente questa sequenza?
tempo
Usiamo il segnale di clock della scheda per scandire il tempo
clk
1 per un ciclo di clock, 0 per un ciclo di clock
Y=q0
1 per due cicli di clock, 0 per due ciclo di clock
X=q1
6
q1q0: numero a due bit
Campioniamo q1q0 numero a un tempo prefissato dopo il bordo di salita di clk
 campionamento sincrono
Y=q0
X=q1
0
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
1
0
2
3
0
0
1
1
2
3
Numero binario a due bit La cifra più grande di un
che aumenta di 1 a ogni numero a 2 bit è tre
ciclo di clock
 al ciclo successivo la
sequenza riparte da zero
7
Un circuito che produce questa sequenza che si ripete all’infinito è il contatore
sincrono a due bit
numero binario di output
q1
q[1..0]
q0
Diversa rappresentazione:
raggruppamento in un bus
Segnale di input: clk
clk
res
segnale di input: reset
ogni volta che è asserito la
sequenza riparte da zero
0
1
2
3
0
1
2
3
0
8
Nel circuito reale il conteggio cambia sempre un pò dopo il bordo del clock
Più input
• Funzionano allo stesso modo
• Com’è l’output?
9
Espressioni booleane e circuiti logici
Qualunque espressione booleana può essere implementata come un circuito
logico.
F = [A(C+D)]’+BE
C+D
C
D
[A(C+D)]’
A(C+D)
[A(C+D)]’+BE
A
BE
B
E
F=Y’Z+X
Y
Y’
Z
Y’Z+X
X
10
Rappresentazione: tavola della verità
F=Y’Z+X
Y
Y’
Z
Y’Z+X
X
• 2n righe
• dove n # di
• variabili
11
Teoremi fondamentali: operazioni con 0 e 1
X+0 = X
X
0
X+1 = 1
C=X
X
0
1
0
0
0
C
0
1
X
1
1
1
1
C
1
1
C=X
X
0
1
1
1
1
C
0
1
X·1 = X
X·0 = 0
X
0
C=1
X
0
1
C=0
X
0
1
0
0
0
C
0
0
X
1
12
Teoremi fondamentali: leggi idempotenti
X+X = X
X
X
C=X
X
0
1
X
0
1
C
0
1
C=X
X
0
1
X
0
1
C
0
1
X·X = X
X
X
13
Teoremi fondamentali: legge di involuzione
(X’)’=X
X
B
C=X
X
0
1
B
1
0
C
0
1
14
Teoremi fondamentali: legge di complementarità
X+X’ = 1
X
X’
C=1
X
0
1
X’
1
0
C
1
1
C=0
X
0
1
X’
1
0
C
0
0
X·X’ = 0
X
X’
15
Semplificazione delle espressioni usando i teoremi
fondamentali
X può essere una funzione arbitrariamente complessa.
Semplifichiamo le seguenti espressioni booleane il più possibile
usando i teoremi fondamentali.
(AB’ + D)E + 1 = 1
(AB’ + D)(AB’ + D)’ = 0
(AB + CD) + (CD + A) + (AB + CD)’ = 1
16
Legge associativa
(X+Y)+Z = X+(Y+Z)
X
Y
C
Z
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
X+Y
0
0
1
1
1
1
1
1
Y
Z
(X+Y)+Z
0
1
1
1
1
1
1
1
X
Y+Z
0
1
1
1
0
1
1
1
C
X+(Y+Z)
0
1
1
1
1
1
1
1
17
Legge associativa
(XY)Z = X(YZ)
X
Y
C
Z
X
0
0
0
0
1
1
1
1
Y
Z
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
XY
0
0
0
1
0
0
1
1
(XY)Z
0
0
0
0
0
0
0
1
X
YZ
0
0
0
1
0
0
0
1
C
X(YZ)
0
0
0
0
0
0
0
1
18
Prima legge distributiva
X(Y+Z) = XY+XZ
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
Y+Z
0
1
1
1
0
1
1
1
X(Y+Z)
0
0
0
0
0
1
1
1
XY
0
0
0
0
0
0
1
1
XZ
0
0
0
0
0
1
0
1
XY+XZ
0
0
0
0
0
1
1
1
19
Prima legge distributiva
X(Y+Z) = XY+XZ
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
Y+Z
0
1
1
1
0
1
1
1
X(Y+Z)
0
0
0
0
0
1
1
1
XY
0
0
0
0
0
0
1
1
XZ
0
0
0
0
0
1
0
1
XY+XZ
0
0
0
0
0
1
1
1
20
Prima legge distributiva
X(Y+Z) = XY+XZ
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
Y+Z
0
1
1
1
0
1
1
1
X(Y+Z)
0
0
0
0
0
1
1
1
XY
0
0
0
0
0
0
1
1
XZ
0
0
0
0
0
1
0
1
XY+XZ
0
0
0
0
0
1
1
1
21
Prima legge distributiva
X(Y+Z) = XY+XZ
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
Y+Z
0
1
1
1
0
1
1
1
X(Y+Z)
0
0
0
0
0
1
1
1
XY
0
0
0
0
0
0
1
1
XZ
0
0
0
0
0
1
0
1
XY+XZ
0
0
0
0
0
1
1
1
22
Prima legge distributiva
X(Y+Z) = XY+XZ
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
Y+Z
0
1
1
1
0
1
1
1
X(Y+Z)
0
0
0
0
0
1
1
1
XY
0
0
0
0
0
0
1
1
XZ
0
0
0
0
0
1
0
1
XY+XZ
0
0
0
0
0
1
1
1
23
Seconda legge distributiva
X+YZ = (X+Y)(X+Z)
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
YZ
0
0
0
1
0
0
0
1
X+YZ
0
0
0
1
1
1
1
1
X+Y
0
0
1
1
1
1
1
1
X+Z
0
1
0
1
1
1
1
1
(X+Y)(X+Z)
0
0
0
1
1
1
1
1
24
Seconda legge distributiva
X+YZ = (X+Y)(X+Z)
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
YZ
0
0
0
1
0
0
0
1
X+YZ
0
0
0
1
1
1
1
1
X+Y
0
0
1
1
1
1
1
1
X+Z
0
1
0
1
1
1
1
1
(X+Y)(X+Z)
0
0
0
1
1
1
1
1
25
Seconda legge distributiva (una dimostrazione
alternativa)
(X + Y)(X + Z) = X(X + Z) + Y(X + Z)
(usando la prima legge distributiva)
= XX + XZ + YX + YZ
(usando la prima legge distributiva)
= X + XZ + YX + YZ
= X·1 + XZ + YX + YZ
= X(1 + Z + Y) + YZ
= X·1 + YZ
= X + YZ
(usando la legge idempotente)
(usando X1=X)
(usando la legge distributiva)
(usando 1+Z+Y=1)
(usando X1=X)
26
Teoremi per semplificare
XY + XY’ = X
XY + XY’ = X(Y + Y’) = X·1 = X
X + XY = X
X(1 + Y) = X·1 = X
(X + Y’)Y = XY
XY + Y’Y = XY + 0 = XY
(X + Y)(X + Y’) = X
(X + Y)(X + Y’) = XX + XY’ + YX + YY’
= X + X(Y’ + Y) + 0
= X + X·1
=X
X(X + Y) = X
X(X + Y) = XX + XY = X·1 + XY
= X(1 + Y) = X·1 = X
XY’ + Y = X + Y
(using the second distributive law)
XY’ + Y = Y + XY’ = (Y + X)(Y + Y’)
= (Y + X)·1 = X + Y
27
Teoremi per semplificare e dualità
Qualunque teorema o identità in algebra booleana resta vero se 0 e 1 sono
scambiati e • e + sono pure scambiati ovunque.
DUALE
XY
+
(X + Y)

XY’
+
X
 (X + Y)
+ Y’)
XY’
(X + Y)(X + Y’) = X
(X + Y’)
X
( X
=X
XY
X(X + Y) = X
=X

Y
+ Y
= XY
(X + Y)
XY’ + Y = X + Y
28
Dualità
Nell’applicare il principio di dualità dobbiamo fare attenzione alla precedenza
degli operatori nell’espressione originale:
X+X•Y=X
X • (X + Y) = X (dualità)
• ha precedenza
 uso di parentesi
Esempio di applicazione non corretta del principio:
X+X•Y=X
X • X + Y = X (dualità)
X + Y = X (idempotenza) Non senso!
29
Esempi
Semplifichiamo la seguenta espressione:
W = [M + N’P + (R + ST)’][M + N’P + R + ST]
X = M + N’P
Y = R + ST
W = (X + Y’)(X + Y)
W = XX + XY + Y’X + Y’Y
W = X·1 + XY + XY’ + 0
W = X + X(Y + Y’) = X + X·1 = X
W = M + N’P
30
La prima legge di De Morgan
Il complemento della somma è uguale al prodotto dei complementi
(X+Y)’ = X’Y’
X
Y
Z

X
Z
Y
X
0
0
1
1
Y
0
1
0
1
X+Y
0
1
1
1
(X+Y)’
1
0
0
0
X’
1
1
0
0
Y’
1
0
1
0
X’Y’
1
0
0
0
31
La prima legge di De Morgan
Il complemento della somma è uguale al prodotto dei complementi
(X+Y)’ = X’Y’
X
Y
Z

X
Z
Y
X
0
0
1
1
Y
0
1
0
1
X+Y
0
1
1
1
(X+Y)’
1
0
0
0
X’
1
1
0
0
Y’
1
0
1
0
X’Y’
1
0
0
0
32
La prima legge di De Morgan
Il complemento della somma è uguale al prodotto dei complementi
(X+Y)’ = X’Y’
X
Y
Z

X
Z
Y
X
0
0
1
1
Y
0
1
0
1
X+Y
0
1
1
1
(X+Y)’
1
0
0
0
X’
1
1
0
0
Y’
1
0
1
0
X’Y’
1
0
0
0
33
La prima legge di De Morgan
Il complemento della somma è uguale al prodotto dei complementi
(X+Y)’ = X’Y’
X
Y
Z

X
Z
Y
X
0
0
1
1
Y
0
1
0
1
X+Y
0
1
1
1
(X+Y)’
1
0
0
0
X’
1
1
0
0
Y’
1
0
1
0
X’Y’
1
0
0
0
34
La prima legge di De Morgan
Il complemento della somma è uguale al prodotto dei complementi
(X+Y)’ = X’Y’
X
Y
Z

X
Z
Y
X
0
0
1
1
Y
0
1
0
1
X+Y
0
1
1
1
(X+Y)’
1
0
0
0
X’
1
1
0
0
Y’
1
0
1
0
X’Y’
1
0
0
0
35
La seconda legge di De Morgan
Il complemento del prodotto è uguale alla somma dei complementi
(XY)’ = X’ + Y’
X
Y
Z

X
Z
Y
X
0
0
1
1
Y
0
1
0
1
XY
0
0
0
1
(XY)’
1
1
1
0
X’
1
1
0
0
Y’
1
0
1
0
X’ + Y’
1
1
1
0
36
NOR e NAND e altri simboli
Abbiamo già parlato abbondantemente dei NOR e NAND
X
Y
Z
X
Y
Z

X
Y
Z

X
Y
Z
NOR
NAND
Spesso si usano abbreviazioni simili anche per gli input negati. Ad esempio
X
Z
Y

X
Z
Y
37
38
39
40
Legge di De Morgan (cont.)
La legge di De Morgan si generalizza a n variabili:
(X1 + X2 + X3 + ··· + Xn)’ = X1’X2’X3’ ··· Xn’
(X1X2X3 ··· Xn)’ = X1’ + X2’ + X3’ + ··· + Xn’
41
42
Legge di De Morgan (esempio)
Esprimiamo il complemento f’(w,x,y,z) della seguente espressione
in forma semplificata.
f(w,x,y,z) = wx(y’z + yz’)
f’(w,x,y,z) = w’ + x’ + (y’z +yz’)’
= w’ + x’ + (y’z)’(yz’)’
= w’ + x’ + (y + z’)(y’ + z)
= w’ + x’ + yy’ + yz + z’y’ + z’z
= w’ + x’ + 0 + yz + z’y’ + 0
= w’ + x’ + yz + y’z’
43
Logica positiva e negativa
Logica positiva: la tensione high (+V) rappresenta 1
e la tensione low (0V) rappresenta 0
Logica negativa: la tensione high (+V) rappresenta 0
e la tensione low (0V) rappresenta 1
44
Logica positiva e negativa (esempio)
e1
e2
e3
e1
0V
0V
0V
0V
+V
+V
+V
+V
e2
0V
0V
+V
+V
0V
0V
+V
+V
e3
0V
+V
0V
+V
0V
+V
0V
+V
eo
0V
0V
0V
0V
0V
0V
0V
+V
+
Tensioni elettriche
gate
logico
e1
0
0
0
0
1
1
1
1
e2
0
0
1
1
0
0
1
1
e3
0
1
0
1
0
1
0
1
eo
eo
0
0
0
0
0
0
0
1
+
e1
1
1
1
1
0
0
0
0
e2
1
1
0
0
1
1
0
0
e3
1
0
1
0
1
0
1
0
eo
1
1
1
1
1
1
1
0
+
Logica positiva
AND
Logica negativa
OR
 lo stesso circuito fisico implementa diverse funzioni logiche.
La funzione implementata depende dalla logica usata per
45
Interpretare gli input e gli output.
Il teorema del consenso
XY + X’Z + YZ = XY + X’Z
XY + X’Z + YZ = XY + X’Z + 1·YZ
= XY + X’Z + (X + X’)YZ
= XY + X’Z + XYZ + X’YZ
= XY + XYZ + X’Z + X’YZ
= XY(1 + Z) + X’Z(1 + Y)
= XY·1 + X’Z·1
= XY + X’Z
46
Dalla tavola della verità alla funzione
Data una tavola della verità, possiamo implementare F facendo l’OR di tutti i
termini che sono 1
Tavola della verità della
funzione F = X + Y’Z
Esempio
 F  X ' Y ' Z  XY ' Z ' XY ' Z  XYZ ' XYZ
Esercizio: semplificare questa espressione
47
Forme standard
• Questo sistema non produce necessariamente
l’espressione di F più semplice
• Ma è meccanico passare dalla tavola della
verità a F
• Definizioni:
– Termini prodotto – AND  A’BZ
– Termini somma – OR  X + A’
– Somma e prodotto logico, non aritmetico
48
Definizione: mintermine
Termine prodotto in cui tutte le variabili appaiono una
volta (complementate or no)
• Per n variabili ci saranno 2n mintermini
• Come i numeri binari da 0 to 2n-1
49
Somma di mintermini
F: OR di tutti i mintermini della
tavola della verità con un 1
 F = X’Y’Z’ + X’YZ’ + XY’Z + XYZ
Complemento di F
Sommiamo semplicemente
sugli altri mintermini
 F’= m1 + m3 + m4 + m6
Eserizio: semplificare F, scrivere l’espressione per F’ e semplificarla
50
51
Semplificazione di somme di prodotti
• La semplificazione di una somma di
mintermini può dare una somma di
prodotti
• La differenza è che ciascun termine
non ha necessariamente tutte le
variabili
• Gates risultanti 
• diversi AND e un OR
La somma di prodotti ha due
livelli di gate
52
Maxtermini
Termine somma in cui tutte la variabili appaiono una volta
(complementate o no)
In un maxtermine una variabile è complementata se il
corrispondente bit nella rappresentazione binaria di è 1
53
Prodotto di maxtermini
I mintermini e maxtermini con lo stesso indice sono complementi:
 m0’ = (X’Y’Z’)’ = X + Y + Z = M0
 Possiamo esprimere F come AND di
tutte le righe che producono un output
uguale a 0
F=
(X + Y + Z’)(X +Y’+Z’)(X’+Y+Z)(X’+Y’+Z)
 OR seguiti da un AND
54
Rivelatore di numeri primi
Data una combinazione di input a 4 bit N = N3N2N1N0 questo circuito produce
un output pari a 1 per N = 1, 2, 3, 5, 7, 11, 13 e 0 altrimenti
La tavola della verità è
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
N3 N2 N1 N0
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
F
0
1
1
1
0
1
0
1
0
0
0
1
0
1
0
0
Esercizio:
Determinare
l’espressione logica e
semplificarla
55
Progetto: visualizzazione di cifre su un display
Display: array di 7 led rossi
Sulla scheda sono presenti 4 array
56
Come si controlla ciascun array?
7 segmenti  7 segnali a, b, c, d, e, f, g controllati dalla fpga – se uno di essi è
asserito si accende il led corrispondente
led[6..0]
a
b
c
d
e
f
g
In questo progetto mandiamo la stessa cifra a tutti e
quattro gli array
Vedremo un uso più sofisticato con controllo
indipendente di ciascun array più avanti
57
Progetto: visualizzare un numero da zero a sette sugli array
Primo step scrivere la tavola della verità delle seguenti funzioni logiche:
Input: numero binario a 3 bit q[2..0]
Outputs: a, b, c, d, e, f, g richiesti per visualizzare tale numero binario
Es. Il led a è asserito quando il numero di input q[2..0] è :
0 oppure 2 oppure 3 oppure 5 oppure sei oppure 7 oppure 8 oppure 9
q2 q1 q0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
a b c d e f g
Completare la tavola per ciascuno
dei led
58
59
Secondo step: determinare le equazioni logiche a partire dalla tavola della
verità per ciascuno dei sette segnali col metodo meccanico della somma di
mintermini
Terzo step: minimizzare le espressioni logiche con i teoremi dell’algebra
booleana
Quarto step: disegnare il circuito che ha come input q2, q1, q0 e come output
a, b, c, d, e, f, g con QUARTUS
Disegno implementato con una struttura gerarchica
 vediamo cosa vuol dire e come si procede
60
Foglio principale:
Struttura
gerarchica di
uno schema
LabElettronica
61
Clickate sul menu File e selezionate New
62
Selezionare Block diagram / schematic file
63
Appare un nuovo foglio di disegno. Salvarlo col nome seven-seg-decoder
64
In questo foglio implementiamo il circuito. Cominciamo a mettere gli input
(q[2..0]) e gli output (a, b, c, d, e, f, g)
Disegnate poi tutto il circuito e salvate il file nuovamente
65
Creiamo un simbolo per il circuito corrispondente al file seven-seg-decoder
Il simbolo può essere quindi usato come componente in altri fogli di disegno
66
Torniamo al foglio di disegno principare (LabElettronica)
selezioniamo col mouse symbol tool
67
Compare la finestra che permette di selezionare simboli di componenti
Scrivere seven-seg-decoder: appare il simbolo del nuovo componente
Clickare OK
68
Il componente può essere ora posizionato nel foglio principale
69
Pilotiamo l’input q[2..0] con un valore costante attraverso un componente
lpm_constant
70
Gli output a, b, c, d, e, f, g del componente seven-seg-decoder nel foglio
LabElettronica vanno collegati ai pin di output denominati led[0], ..., led[6] che
devono essere assegnati ai numeri dei pin fisici 144, 143, 142, 141, 140, 139,
136 come da schema della scheda in figura sotto
i pin led[6..0] corrispondono ad g,
f, e, d, c, b, a
71
Ci sono altri due segnali da considerare sugli array
DP: segnale che accende la virgola
COM# segnale di abilitazione (enable): i led di un array si accendono solo se il
corrispondente segnale COM# è asserito
DIS[3..0]
COM3,
COM2,
COM1,
COM0
DP
led[7]
Teniamo deasserito permanentemente led[7]:
Collegato a massa nel foglio principale e mandato al
pin di output led[7] corrispondente al pin 135
72
Controllo dei segnali COM#
Decidiamo in quale array visualizzare la cifra controllando i segnali COM# con i
quattro tasti presenti sulla scheda
SW0
SW3
SW2
SW1
73
Nel foglio principale definiamo:
- 4 input SW0, SW1, SW2, SW3
– 4 output DIS0, DIS1, DIS2, DIS3
Collegate SW# al corrispondente DIS#
DIS[3..0]
COM3,
COM2,
COM1,
COM0
Collegati ai tasti
Attenzione: SW# sono attivi bassi
per cui vanno invertiti prima di
collegarli a DIS#
74
Quinto step: simulare il comportamento del circuito QUARTUS
Sesto step: provare il funzionamento del circuito sulla scheda
verifica: mandatemi per email tutti i file del progetto – potete
lavorare in coppia
Avete 7 giorni di tempo (prova lunedì prossimo)
75
Addizionatore a un bit
76
77
78
79
80
81
Addizionatore completo a un bit
Progettiamo un circuito logico che implementi un addizionatore a due bit.
Questo circuito ha tre input (A, B, Cin) e due output (S, Cout). L’output S è uno
se la somma è uno, cioè se il numero di input uguale a uno è dispari. L’output
del riporto è uno se la somma produce un riporto, cioè se due o più input sono
uno.
Cin
A
0
0
0
0
1
1
1
1
A
Adder
S
B
Cout
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
82
Cin
A
0
0
0
0
1
1
1
1
A
Adder
S
B
Cout
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
S = A’B’Cin + A’BCin’ + AB’Cin’ + ABCin
Cout = A’BCin + A B’Cin + ABCin’ + ABCin
= A’BCin + ABCin + AB’Cin + ABCin + ABCin’ + ABCin
= (A’ + A)BCin + (B’ + B)ACin + (Cin’ + Cin)AB
= 1·BCin + 1· ACin + 1· AB
= BCin + ACin + AB
83
Realizzare circuiti pratici
Problema: progettare un circuito logico per far funzionare in modo
automatizzato l’allarme di una macchina. Il manuale dell’allarme
fornisce i seguenti dettagli sul funzionamento.
“L’allarme si spegnerà se il sistema di allarme è attivato e una qualunque delle
due porte o il cofano sono aperti, o se il sensore di vibrazione è attivato e la
chiave non è inserita.”
Inputs:
AllarmeAttivato
PortaConducenteAperta
PortaPasseggeroAperta
CofanoAperto
Vibrazione
ChiaveInserita
84
Realizzare circuiti pratici
“L’allarme si spegnerà se il sistema di allarme è attivato e una qualunque delle
due porte o il cofano sono aperti, o se il sensore di vibrazione è attivato e la
chiave non è inserita.”
Inputs:
AllarmeAttivato
PortaConducenteAperta
PortaPasseggeroAperta
CofanoAperto
Vibrazione
ChiaveInserita
AllarmeSpento =
AllarmeAttivato • (PortaConducenteAperta + PortaPasseggeroAperta + CofanoAperto)
+ Vibrazione • (ChiaveInserita)’
85
Realizzare circuiti pratici
AllarmeSpento =
AllarmeAttivato • (PortaConducenteAperta + PortaPasseggeroAperta + CofanoAperto)
+ Vibrazione • (ChiaveInserita)’
PortaConducenteAperta
PortaPasseggeroAperta
AllarmeSpento
CofanoAperto
AllarmeAttivato
Vibrazione
ChiaveInserita
Esercizio: implementare e simulare questo circuito con QUARTUS
86
Minimizzazione di funzioni logiche: mappe di
Karnaugh
Le mappe di Karnaugh erano (relativamente) utili quando la gente
eseguiva la semplificazione a mano
Il processo di semplificazione al giorno d’oggi è completamente
eseguito da algoritmi computerizzati
Illustreremo le mappe principalmente per avere una comprensione
più profonda, non come strumento reale.
87
Anatomia delle mappe di Karnaugh
Una mappa è una rappresentazione grafica di una tavola della verità.
Un “box” per ciascuna riga della tavola contente il valore della funzione (zero
oppure uno
Indica il box corrispondente
A
Tavola della verità
ad A=1
di una funzione di
una variabile
A=0
A=1
A
F
0 cella 0
1 cella 1
Tavola della verità
di una funzione di
una variabile
A B
F
0 0 cella 0
0 1 cella 1
1 0 cella 2
1 1 cella 3
A
A=0,B=0
cella 0
0
1
A=1,B=0
cella 2
0
B
A=0,B=1
cella 1
1
A=1,B=1
cella 3
88
Mappe di Karnaugh per funzioni di tre variabili
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
cella 0
cella 1
cella 2
cella 3
cella 4
cella 5
cella 6
cella 7
Disposizione di righe e colonne: ciascuna
cella corrisponde a una combinazione di input
che differisce da quelle adiacenti in una sola
variabile
A,B
00
A=1
01 11 10
0
8 celle
C
1
B=1
89
Mappe di Karnaugh per funzioni di tre variabili
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
cella 0
cella 1
cella 2
cella 3
cella 4
cella 5
cella 6
cella 7
Disposizione di righe e colonne: ciascuna
cella corrisponde a una combinazione di input
che differisce da quelle adiacenti in una sola
variabile
AB A=0,B=1,C=0
00
A=1,B=1,C=0
A
01 11 10
A=0,B=0,C=0
0
A=1,B=0,C=0
A=0,B=0,C=1 C
1
A=1,B=0,C=1
B
A=0,B=1,C=1
A=1,B=1,C=1
90
91
Esempio d’uso delle mappe di Karnaugh:
l’addizionatore a un bit
Cin
A
0
0
0
0
1
1
1
1
A
Adder
S
B
Cout
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
Alternativamente, come
si usa una mappa di
Karnaugh
invece della
semplificazione
algebrica?
+
S = A’B’Cin + A’BCin’ + AB’Cin’ + ABCin
Equazioni
logiche
determinate con
l’algebra
booleana
Cout = A’BCin + A B’Cin + ABCin’ + ABCin
= A’BCin + ABCin + AB’Cin + ABCin + ABCin’ + ABCin
= (A’ + A)BCin + (B’ + B)ACin + (Cin’ + Cin)AB
= 1·BCin + 1· ACin + 1· AB
= BCin + ACin + AB
92
Mappa per Cout
Cin
A
0
0
0
0
1
1
1
1
A
Adder
S
B
Cout
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
Scriviamo in ogni cella il valore della funzione logica (Cout in questo caso)
A
A,B
00 01 11 10
0
0
0
1
0
Cin 1
0
1
1
1
B
93
Ciascuna cella contenente un 1 corrisponde a un mintermine da considerare
nella somma di mintermini della funzione
A
A,B
00 01 11 10
1
0
Cin 1
1
1
B
1
A=1, B=1 Cin=0 mintermine ABCin’
A=0, B=1 Cin=1 mintermine A’BCin
A=1, B=1 Cin=1 mintermine ABCin
A=1, B=0 Cin=1 mintermine AB’Cin
La funzione logica non ancora minimizzata è
Cout = ABCin’ + A’BCin + ABCin + AB’Cin
94
Passo successivo: dobbiamo ricoprire tutte le celle contenti un 1 usando
rettangoli i più grandi possibile e col minor numero di rettangoli possibile
Consideriamo ad esempio
A
Cin
0
0
1
0
0
1
1
1
Il numero di celle racchiuse deve essere
multiplo di 2 (1,2, 4, ...)
B
Ricordiamo la disposizione di righe e colonne: ciascuna cella corrisponde a una
combinazione di input che differisce da quelle adiacenti in una sola variabile
Poichè coppie di celle 1 adiacenti hanno minitermini che differiscono in una
sola variabile, possiamo combinarle (cioè combinare la somma di mintermini) in
un solo termine usando la legge dell’alegra booleana
95
XY’+XY=X
96
Regola meccanica: questo gruppo di celle
(corrispondente a una somma di 2 mintermini) è
equivalente a un singolo termine prodotto in cui:
A
Cin
0
0
1
0
0
1
1
1
B
ACin
In questo termine si considerano solo le variabili
che hanno lo stesso valore in tutte le celle del
gruppo:
In questo caso B varia per cui non si considera
Siccome A e Cin hanno entrambi valore 1 devono
apparire non complementati
97
Dobbiamo ancora finire di ricoprire tutte le celle
A
A
Cin
0
0
1
0
0
1
1
1
Cin
0
0
1
0
0
1
1
1
B
B
ABCin+ABCin’=AB
ACin
A
Cin
A
0
0
1
0
0
1
1
1
B
ABCin+A’BCin=BCin
B
0
0
1
0
0
1
1
1
Cin
Cout=ACin+BCin+AB
98
Mappa di Karnaugh per S
Cin
A
0
0
0
0
1
1
1
1
A
Adder
S
B
Cout
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
A
Cin
0
1
0
1
1
0
1
0
B
S=
Mappa di Karnaugh per S
99
A
0
0
0
0
1
1
1
1
Cin
A
Adder
S
B
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
Cout
A
Cin
0
1
0
1
1
0
1
0
B
Mappa di Karnaugh per S
S = A’B’Cin
100
A
0
0
0
0
1
1
1
1
Cin
A
Adder
S
B
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
Cout
A
Cin
0
1
0
1
1
0
1
0
B
S = A’BCin’ + A’BCin
Mappa di Karnaugh per S
101
Cin
A
0
0
0
0
1
1
1
1
A
Adder
S
B
Cout
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
A
Cin
0
1
0
1
1
0
1
0
B
S = A’BCin’ + A’B’Cin + ABCin
Mappa di Karnaugh per S
102
Cin
A
0
0
0
0
1
1
1
1
A
Adder
S
B
B Cin S
0 0
0
0 1
1
1 0
1
1 1
0
0 0
1
0 1
0
1 0
0
1 1
1
Cout
0
0
0
1
0
1
1
1
+
Cout
A
Cin
0
1
0
1
1
0
1
0
B
S = A’BCin’ + A’B’Cin + ABCin + AB’Cin’
Mappa di Karnaugh per S
103
In molte funzioni logiche la procedura di combinazione delle celle può essere
estesa per combinare più di due 1-celle in un singolo termine prodotto.
Combinazione di 2i celle possibile se:
• ci sono i variabili che assumono tutte le 2i combinazioni possibili
• Le restanti n-i hanno lo stesso valore in ogni cella
 Termine prodotto ha n-i variabili: complementata se 0 in ogni cella, non
complementata se appare come 1.
Graficamente: cerchiamo insiemi rettangolari di 2i 1-celle (sono ammessi anche
“incollaggi” su bordi opposti)
Per ciascuna variabile:
Se è zero in tutta l’area ricoperta  complementata
Se è uno in tutta l’area ricoperta  non complementata
Se è zero in una parte e uno in un’altra  non appare nel prodotto
104
L’adiacenza è cilindrica
Z’ si estende dal bordo sinistro al bordo destro
F = Z’
105
106
107
108
109
110
111
F=SA,B,C(0,1,4,5,6)
A
A
00 01 11 10
00 01 11 10
0
1
0
1
1
0
1
0
1
1
C 1
1
0
0
1
C 1
1
0
0
1
B
B
A
A
00 01 11 10
00 01 11 10
0
1
0
1
1
0
1
0
1
1
C 1
1
0
0
1
C 1
1
0
0
1
B
B
AC’
AC’+B’
112
113
Esempio di funzione a quattro variabili: rivelatore di
numeri primi
F=SN3,N2,N1,N0(1,2,3,5,7,11,13)
114
115
116
Esempio di funzione a quattro variabili: rivelatore di
numeri primi
F=SN3,N2,N1,N0(1,2,3,5,7,11,13)
N3
N3N2
00 01 11 10
N1N0
0
4
12
00
01
11
1 1 1 5 1 13
13 17
N1 10
12
6
8
N3’N0
01
9
N0
15
1 11
14
10
N3
N3N2
00 01 11 10
N1N0
00
1
1
11
1
1
N1 10
1
1
N0
1
N2
N2
N2N1’N0
N2’N1N0
N3’N2’N1
117
Implicanti primi
Un implicante primo è un insieme cerchiato di 1-celle soddisfacenti la regola di
combinazione tale che se cerchiamo di farlo più grande (ricoprendo il doppio
delle celle) copre uno o più zeri.
Una somma minima è una somma di implicanti primi.
F=SW,X,Y,Z(5,7,12,13,14,15)
W
YZ
WX
00 01 11 10
00
0
01
1
11
Y
10
3
2
4
1 12
8
1 5 1 13
9
1 7 1 15
6
1 14
X
XZ
YZ
1
00
01
Z
11
11
Y
10
W
WX
00 01 11 10
1
1
1
1
10
Z
1
X
WX
118
La somma di tutti gli implicanti primi di una funzione logica è detta la somma
completa.
La somma completa non è sempre minima però.
F=SW,X,Y,Z(1,3,4,5,9,11,12,13,14,15)
XY’
W
YZ
WX
00 01 11 10
00
01
11
Y
10
0
1 4 1 12
YZ
13
7
2
6
1 15 1 11
1 14
X
00
8
1 1 1 5 1 13 1 9
10
W
WX
00 01 11 10
Z
01
Y’Z
11
Y
1
1
1
1
1
1
1
1
1
10
WZ
Z
1
X’Z
X
WX
 5 implicanti primi, ma solo tre necessari per ricoprire tutte le 1-celle
119
Una 1-cella distinta è una combinazione di input coperta da un solo implicante
primo
Un implicante primo essenziale è uno che copre una o più 1-celle distinte
 deve essere incluso obbligatoriamente.
Dobbiamo quindi determinare come coprire le 1-celle non coperte da implicanti
primi essenziali (se ce ne sono)
XY’
YZ
W
WX
00 01 11 10
00
01
Y’Z
11
Y
XY’
1
1
1
1
1
1
1
1
1
10
WZ
YZ
W
WX
00 01 11 10
00
01
Z
11
Y
1
1
1
1
1
1
1
1
1
1
10
1
X’Z
X
Z
X’Z
X
WX
WX
120
 in questo caso i 3 implicanti primi essenziali ricoprono tutte le 1-celle
F=SW,X,Y,Z(0,1,2,3,4,5,7,14,15)
YZ
W
WX
00 01 11 10
00
1
4
12
8
01
11 15
13
9
11
Y
1
0
3
10 1 2
1
1
W’Y’
YZ
Z
7
1
15
11
6
1 14
10
X
W
WX
00 01 11 10
00
1
1
01
1
1
1
1
11
Y
10 1
Z
1
1
X
W’X’
WXY
Qui gli implicanti primi essenziali non ricoprono tutte le 1-celle
Ci sono altri due implicanti primi e dobbiamo scegliere uno dei due
121
Qui gli implicanti primi essenziali non ricoprono tutte le 1-celle
Esaminiamo gli altri due implicanti primi: dobbiamo scegliere uno dei due
W’Y’
YZ
W
WX
00 01 11 10
00
1
1
00
1
1
01
1
1
01
1
1
1
1
1
1
11
Y
YZ
W
WX
00 01 11 10
10 1
Z
11
1
Y
1
X
W’X’
10 1
Z
1
1
X
WXY
W’Z
XYZ
 usiamo il termine prodotto W’Z perchè ha meno input e quindi costa meno
122
123
124
Numeri binari
E’ importante essere in grado di rappresentare numeri nei circuiti
digitali
Ad esempio, l’output di un convertitore analogico/digitale (ADC) è
un numero a n bit, dove n tipicamente si trova nell’intervallo 8-16.
Si utilizzano varie rappresentazioni, ad es.;
- interi non segnati
- complemento a due per rappresentare numeri negativi
125
OR esclusivo
X  Y = XY’ + X’Y
X
Y
X0= X
X  1 = X’
XX= 0
X  X’ = 1
C
X
0
0
1
1
Y
0
1
0
1
C
0
1
1
0
Se X=1 OR Y=1, ma
Non entrambi, allora C=1
Legge commutativa:
XY=YX
Legge associativa:
(X  Y)  Z= X  ( Y  Z) = X  Y  Z
Legge distributiva:
X(Y  Z) = XY  XZ
126
OR esclusivo (cont.)
Legge del complemento:
(X  Y)’ = X  Y’ = X’  Y
X
0
0
1
1
Y
0
1
0
1
X’
1
1
0
0
Y’
1
0
1
0
XY
0
1
1
0
(XY)’
1
0
0
1
XY’
1
0
0
1
X’Y
1
0
0
1
Dimostrazione algebrica:
(X  Y)’ = (XY’ + X’Y)’
= (XY’)’(X’Y)’
= (X’ + Y)(X + Y’)
= X’X + X’Y’ + XY + YY’
= 0 + X’Y’ + XY + 0
= X’Y’ + XY = X’  Y
= XY + X’Y’ = X  Y’
127
Permutazione del valore in-place
Si dimostrano queste proprietà:
(XY)Y = X
(XY)X= Y
X
0
0
1
1
Dim. algebrica:
Y X1=XY Y1=X1Y X2=X1Y1
0
0
0
0
1
1
0
1
0
1
1
0
1
0
1
1
(XY) Y = (XY’ + X’Y)Y’ + (XY’ + X’Y)’Y
= XY’Y’ + X’YY’ + ((XY’)’(X’Y)’)Y
= XY’ + 0 + ((X’+Y)•(X+Y’))Y
= XY’ + X’XY + X’Y’Y +XYY + YY’Y
= XY’ + 0 + 0 + XY + 0
= X(Y’ + Y)
= X•1
=X
128
Using In-place Value Permutation
in
Assembly
The In-place Value Permutation Property of the exclusive-OR:
(XY)Y = X
(XY)X= Y
Can be used in assembly programming to exchange the
value of two registers in place:
R1  R1R2
R2  R1R2
R1  R1R2
If we do back substitution in the second and third operations,
we will find out that (assuming R1=A and R2=B initially):
R1  (A  B)
R2  (A  B)  B = A
R1  (A  B)  A = B
Thus, if initially R1 = A and R2 = B, then after this sequence
of operations, R1 = B and R2 = A.
129
Equivalence Gate
(X  Y) = XY + X’Y’
X
Y
C
X
0
0
1
1
Y
0
1
0
1
C
1
0
0
1
If X=Y then C=1,
otherwise C=0
(X  Y) = (X  Y)’
130