Marco Tarini - Università dell'Insubria A.A. 2017-1018
Architettura degli elaboratori - Circuiti combinatori - 5 1
Esempio:
una funzione numerica
Obiettivo:
scrivere un circuito combinatorio per calcolare la funzione (da numeri a numeri) espressa dalla tabella qui accanto.
Nota:
e’ una tabella da numeri [0..15] ai numeri: 0,1,2
Primo passo, riscriviamola come funzione da n bit (quanti?)
a m bit (quanti?)
Funzioni e circuiti combinatori
Architettura degli elaboratori - 107 -
A F(A)
0 0
1 0
2 1
3 1
4 0
5 0
6 1
7 0
8 0
9 0
10 0
11 2
12 0
13 0
14 1
15 1
Funzioni e circuiti combinatori
Architettura degli elaboratori - 108 -
ABCD XY
0000 00
0001 00
0010 01
0011 01
0100 00
0101 00
0110 01
0111 00
1000 00
1001 00
1010 00
1011 10
1100 00
1101 00
1110 01
1111 01
A F(A)
0 0
1 0
2 1
3 1
4 0
5 0
6 1
7 0
8 0
9 0
10 0
11 2
12 0
13 0
14 1
15 1
Marco Tarini - Università dell'Insubria A.A. 2017-1018
Architettura degli elaboratori - Circuiti combinatori - 5 2
Esempio: Note
Per implementare una funzione da n bit a m bit,
possiamo semplicemente implementare m funzioni da n bit a 1 bit
In questo caso, due funzioni, Fx e Fy:
Fx: dai bit A,B,C,D al bit X Fy: dai bit A,B,C,D al bit Y E’ un metodo accettabile, ma non necessariamente ottimo
stiamo perdendo la possibilità
di ottimizzare il calcolo congiunto di X e Y ad esempio,
una sottoespressione usata per X potrebbe essere forse riutilizzata per il calcolo di Y
Funzioni e circuiti combinatori
Architettura degli elaboratori - 109 -
ABCD XY
0000 00
0001 00
0010 01
0011 01
0100 00
0101 00
0110 01
0111 00
1000 00
1001 00
1010 00
1011 10
1100 00
1101 00
1110 01
1111 01
Funzioni e circuiti combinatori
Architettura degli elaboratori - 110 -
Implementazione di Y = Fy(A,B,C,D) con Karnaugh (in 1ma forma)
C D A B
0 0
0 1
1 1
1 0
0 0 0 0 1 1
0 1 0 0 0 1
1 1 0 0 1 1
1 0 0 0 0 0
\A \B C + B C \D
+
A B C
Marco Tarini - Università dell'Insubria A.A. 2017-1018
Architettura degli elaboratori - Circuiti combinatori - 5 3
Funzioni e circuiti combinatori
Architettura degli elaboratori - 111 -
Implementazione di Y = Fy(A,B,C,D) con Karnaugh (in 2da forma)
C D A B
0 0
0 1
1 1
1 0
0 0 0 0 1 1
0 1 0 0 0 1
1 1 0 0 1 1
1 0 0 0 0 0
( C ) x
( A + \B + \D ) x
( \A + B )
Implementazione di X = Fx(A,B,C,D) in prima forma normale
Banalmente (c’è un solo 1):
Fx (A,B,C,D) = ( A \B C D )
Esercizio interessante:
come sarebbe stato, calcolandolo in 2nda forma normale con Karnaugh?
Provare!
Funzioni e circuiti combinatori
Architettura degli elaboratori - 112 -
ABCD X
0000 0
0001 0
0010 0
0011 0
0100 0
0101 0
0110 0
0111 0
1000 0
1001 0
1010 0
1011 1
1100 0
1101 0
1110 0
1111 0
Marco Tarini - Università dell'Insubria A.A. 2017-1018
Architettura degli elaboratori - Circuiti combinatori - 5 4
Implementazione del circuito finale (a 4 ingressi e 2 uscite)
Funzioni e circuiti combinatori
Architettura degli elaboratori - 113 -
A
/A A
B
/B B
C
CY
X = A \B C D Y = C x
( A + \B + \D ) x ( \A + B )
D
/B B
X
Esempio: Note e Osservazioni
Le due espressionitrovate per Y sono equivalenti (se abbiamo fatto bene i conti)
cioè… calcolano la stessa funzione booleana
Abbiamo scelto di implementare la 2nda forma normale perché (in questo caso) ha prodotto la formula più ottimizzata (contando le porte OR e AND e NOT)
In generale, con Karnaugh,
non è facile «prevedere» a-priori quale delle due forme risulterà nell’espressione migliore (es. meno costosa)
Il circuito combinatorio finale calcola le due uscite (X e Y)in parallelo mentre viene calcolato X, viene calcolato anche Y
X e Y appaiono nelle uscite indipendentemente uno dall’altro Questo è tipico delle computazioni in Hardware (a circuito) Velocità: il tempo di commutazione del circuito finale è
il maggiore dei tempi dei due sottocircuiti (che calcolano X e Y)
Funzioni e circuiti combinatori
Architettura degli elaboratori - 114 -