Post on 12-Feb-2021
2 Reti Combinatorie
1
Fondamenti di Informatica P2 Ingegneria Meccatronica
Stefano MattocciaDipartimento di Informatica
Università di Bologna
I fenomeni di natura combinatoria non dipendonodal passare del tempo e/o da quanto avvenuto inprecedenza ma solo dagli stimoli in ingresso alsistema.
Esempio: la somma tra 6 e 9 è sempre 15
Al contrario, un fenomeno si configura dinatura sequenziale se dipende dagli stimoli iningresso, da quanto avvenuto in precedenza eanche dal passare del tempo.
Esempio: la spesa di un’attività commercialefino al giorno X, è data dalle spese sostenuteil giorno X (ingresso) sommate alla speseaccumulate fino al giorno X-1 (stato,memorizzato da qualche parte).
Talvolta, come nel caso delle spese, fenomenidi natura potenzialmente combinatoria (a)possono essere descritti persemplicità/efficienza anche con sistemi di tiposequenziale (b), sempre dotati di memoria
Spese giorno XSpese giorno X-1
…Spese giorno 0
RCXX-1…0
T Totale
RCASpese giorno X
MEM
Z TotaleB
DQ
(a)
(b)
La memoria serve per ricordareil totale delle spese sostenutedal giorno 0 al giorno X-1
Tuttavia, alcuni comportamenti, sonoassimilabili indiscutibilmente a fenomeni dinatura sequenziale.
Un esempio notevole di (b) è una orologiodigitale. Ora sono le 12.39 perché sono passatiK minuti da quando è stato impostato l’orarioin accordo a un orologio di riferimento.
Ovviamente è anche necessario un segnale chescandisca il tempo che passa (clock)
clock
Altro esempio notevole di (b) è un comuneimpianto semaforico: il colore della luce(verde, gialla e rossa) dipende da:
1) Come è stato avviato (eg, appena avviato èimpostata la luce rossa?)
2) Da quanto tempo è stato avviato
3) La durata del ciclo semaforico (eg, verdeper 20 s, giallo per 5 s e rosso per 20 s ?)
Ovviamente è necessario avere la percezione deltempo che passa (eg, clock di 1 s ?)
La luce mostrata in un determinato istante daun semaforo, in generale, non dipende solodalle cause mostrate in precedenza ma anche daeventuali segnali di ingresso (eg, richiesta diattraversamento pedonale?)
Inoltre, potrebbe essere programmabile persvolgere diversi compiti in base a determinateesigenze (eg, ciclo regolare diurno e ciclo congiallo lampeggiante durante la notte?).
Per il momento ci concentreremo sulle reticombinatorie perché sono essenziali per poterprogettare reti sequenziali
Tuttavia, è bene anticipare che le retisequenziali sono il nostro vero obiettivo
In particolare, ci focalizzeremo su retisequenziali sincrone, ovvero reti logichedotate di memoria e di un segnale diriferimento periodico, di durata T, denominatoclock
Per il momento pensiamo alle reti combinatorie
tClockT T T T
Esempi di semplici elaborazioni combinatorie con interruttori
SW1 SW0
Solo se SW0 è premuto e SW1 è premuto lalampadina è accesa. Questo operatore logico,chiamato AND, elabora i due bit in ingresso(SW1 e SW0) e genera un uscita binaria (lalampadina è ON oppure OFF)
SW0SW1
Equivalente circuitoidraulico(AND)
A B Y0 0 00 1 01 0 01 1 1
AND ()
Possiamo descrivere il funzionamento di un operatorelogico (gate) mediante una tabella della verità
Possiamo anche usare la seguente espressione: Y = AB
SW1
SW0
Se SW0 è premuto o SW1 è premuto la lampadina è accesa. Questo operatore logico, chiamato OR, elabora i due bit in ingresso (SW1 e SW0) e genera un uscita binaria (la lampadina è ON oppure OFF)
SW0
SW1
Equivalente circuitoidraulico
(OR)
A B Y0 0 00 1 11 0 11 1 1
OR (+)
La tabella della verità di un gate OR è la seguente
Possiamo anche usare la seguente espressione: Y = A+B
NOT (*)
La tabella della verità di un gate NOT è la seguente
A Y0 11 0
Possiamo anche usare la seguente espressione: Y = A*
A B Y0 0 00 1 11 0 11 1 0
XOR (Å)
La tabella della verità di un gate XOR è la seguente
Possiamo anche usare la seguente espressione: Y = AÅB
Esempio• Combinando questi semplici operatori logici,possiamo descrivere una certa classe diproblemi (denominati combinatori)
• In realtà, vedremo presto che usando anchedispositivi di memorizzazione potremorisolvere qualsiasi tipo di problema
• Esempio: “avvia il motore dello scooter se èpremuto almeno un freno (anteriore oposteriore) e se è premuto il tasto diaccensione”
RLANT
POST
ON
ANT
POST
ON
START
RLANT
POST
ON
ANT
POST
ON
START
Una possibile rete logica risulta:
O meglio, in modo del tutto equivalente:
START = ON(ANT + POST)
ANTPOST
ONSTART
ON ANT POST START
0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1
Vedremo come ottenere (sintesi) la rete logica ma peril momento scriviamo la tabella della verità dellarete logica della pagina precedente, valutandol’espressione per qualsiasi ingresso (sono 3 -> 8combinazioni). Questo è il processo di analisi di unarete logica.
START = ON(ANT + POST) è
ON ANT POST START
0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1
Osservando la tabella della verità dell’esempioprecedente, possiamo notare che l’uscita (START) vale1 solo in corrispondenza di 3 su 8 specificheconfigurazioni di ingresso (mintermini):
ON=1ANT=0POST=1 oON=1ANT=1POST=0 oON=1ANT=1POST=1
Se avessimo a disposizione una rete che decodifica ognipossibile configurazioni in ingresso potremmoimmediatamente passare da una tabella della verità allasua implementazione semplicemente mettendo in OR tutti imintermini.Tale rete esiste e si chiama decoder:
I2I1I0
Decoder3:8
I2I1I0
110101100011010001
I2=0,I1=0,I0=0
Y7 (1 se I2I1I0)Y6 (1 se I2I1I0*)Y5 (1 se I2I1*I0)Y4 (1 se I2I1*I0*)Y3 (1 se I2*I1I0)Y2 (1 se I2*I1I0*)Y1 (1 se I2*I1*I0)Y0 (1 se I2*I1*I0*)
Decoder n:2n
Un decoder con n ingressi ha 2n uscite, pari al numerodi diverse configurazioni degli ingressi (e.g., 3:23 inquesto caso).
Esercizio: progettare un decoder 3:8 con gate
111
Decoder 3:8 con gate
I2 I1 I0
Y7
Y6
Y5
Y4
Y3
Y2
Y1
Y0
Utilizzando il decoder 3:8 della pagina precedentepossiamo sintetizzare la tabelle di verità della retedell’esempio dello scooter in modo molto semplice:
ONANT
POST
START = Y5 + Y6 + Y7= ONANT*POST + ONANTPOST* + ONANTPOST
Questa rete è più complessa (più gate) rispetto a
START = ON(ANT + POST)
perchè non è in forma minima
Decoder3:8
I2I1I0
76543210
Y7Y6Y5Y4Y3Y2Y1Y0 ON=0,ANT=0,POST=0
Vediamo come sarebbe possibile ottenere la forma minimacon una semplice manipolazione algebrica:
START = ONANT*POST + ONANTPOST* + ONANTPOST
vale la proprietà distributiva (verificate) è
= ON(ANT*POST + ANTPOST* + ANTPOST)= ON(ANT*POST + ANT(POST* + POST))
osservazione, X + X* = 1 (verificate) è
= ON(ANT*POST + ANT(1))= ON(ANT*POST + ANT)
X + X*Y = X + Y (verificate) è
= ON(ANT + POST)
Esiste un metodo rapido (Karnaugh) per ottenere la formaminima che non vedremo per questioni di tempo*
Messaggio importante
Data una tabella della verità, è possibile eseguire la sintesi della rete(combinatoria) utilizzando un decodere e un OR a k ingressi (dove k è ilnumero di mintermini).
L’espressione/rete ottenuta non è generalmente in forma minima mapotremmo sempre minimizzarla (oggi, processo raramente utilizzato inpratica) se proprio necessario.
Meglio scrivere espressioni piuttosto che disegnare reti con gate connessi traloro:
ANTPOST
ONSTART START = ON(ANT + POST)Vs
Esercizio
1) Individuare la tabella della verità corrispondentealla seguente espressione logica:
Z = A(B+C*) + BC + A*C
2) Data la tabella della verità ottenuta nel puntoprecedente, effettuare la sintesi con decoder
A B C Z0 0 0 0 (Y0)0 0 1 1 (Y1)0 1 0 0 (Y2)0 1 1 1 (Y3)1 0 0 1 (Y4)1 0 1 0 (Y5)1 1 0 1 (Y6)1 1 1 1 (Y7)
CON DECODER: Z = Y1 + Y3 + Y4 + Y6 + Y7
NotazionePuò essere utile concatenare più variabilibinarie possiamo usare il simbolo # (che non èun operatore logico). Esempio, indicando con:
S[2..0] = ON#ANT#POST
significa che S[2..0] = 010 corrisponde a ON=0,ANT=1 e POST=0.
Se vogliamo fare riferimento al segnale binarioANT possiamo indicare S1 (il bit 1 di S[2..0])
Dal punto di vista grafico:
ONANTPOST
ONANTPOST
S[2..0] S[2..0]3
Multiplexer (Mux)In molte circostanze è utile poter scegliere inl’uscita di una rete tra più segnali diingresso.In linguaggio C: if (S==0) U=A
else U=B
La rete (combinatoria) che consente realizzaretale comportamento è il multiplexer (Mux):
S1
0
U
S
B
AU
S A B U
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1Mux a 2S vie
EsercizioProgettare un Multiplexer a 2 vie con un decoder
S A B U
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
L’uscita U corrisponde all OR tra la decodifica delleconfigurazioni di ingresso di S#A#B per le qualil uscita del Mux vale 1. Tali configurazioni sono: Y2,Y3, Y5 e Y7. Pertanto,
U = Y2 + Y3 + Y5 + Y7
In realtà, servono meno risorse per un Mux a 2 vie…
SA
Decoder3:8
I2I1I0
76543210
B
Y7Y6Y5Y4Y3Y2Y1Y0
E possibile realizzare il Mux a due vie, con gate, nelmodo seguente:
S
A
B
U
O meglio: U = S· B + S*·A
Useremo il Mux prevalentemente per inviare sull’uscita unodegli ingressi in base al valore dei segnali selezione (in modosimile all’operatore if di un linguaggio di programmazione).
Tuttavia, come vedremo tra poco, il Mux può essere usato ancheper la sintesi
Ovviamente esistono mux con un numero di viemaggiori. Dato il numero di bit di selezione n,il numero di vie è pari a 2n:
n=1, 2 vie
se S=0 è U=Ase S=1 è U=B
n=2, 4 vie
se S1S0=00 è U=I0se S1S0=01 è U=I1se S1S0=10 è U=I2se S1S0=11 è U=I3
S1
0
U
S
B
AU
S03
0
U
S1
U
S0
S1
21
I3
I0
I2I1
Esercizio: risolvere l’esercizio dello scooter con un MUX
ON ANT POST START
0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 11 1 0 11 1 1 1
START vale 0
START vale 1
Gli ingressi sono 3, un’unica uscita U. Possiamo usare unmux con tre segnali di selezione (mux a 8 vie). Le tre vie nel nostro caso saranno S2,S1,S0 = ON, ANT,POSTOsservando la tabella della verità, si identificano le configurazioni di ingresso per le quali l’uscita U vale 1e le configurazioni per le quali U vale 0.
S0
I3
I0
U
I2I1
0
0
00
I7
I4
I6I5
1
0
11
S1S2
ONANT
POST
U
Gli strumenti che abbiamo visto sono sufficienti, insiemeall’intuito, per progettare qualsiasi rete combinatoria:
Messaggio importante
S1
0U
S
B
AU
DECn:2n
A
B
3210
A
B
Y3Y2Y1Y0
Esercizio
Progettare una rete logica combinatoria ingrado di confrontare se gli ingressi A[3..0] eB[3..0] sono uguali. In caso affermativol’uscita EQUALS deve andare al valore logico 1mentre deve assumere il valore logico 0 incaso contrario. Tale rete è chiamatacomparatore.
A[3..0]
B[3..0]
4
4COMP
A[3..0]
B[3..0]Z EQUALS
• Sebbene sia possibile in linea di principiousare un decoder o un mux ci troveremmo adover utilizzare dispositivi con 256 uscite,nel caso del decoder, e a 256 + 8 ingressinel caso del mux
• Anche scrivere una tabella della verità con256 righe non sembra essere una viapraticabile. Pensate se dovessimo compararedue valori a 16 bit: tabella con 4 miliardidi righe!
Fortunatamente l’intuito ci può aiutare: comepossiamo verificare se due bit sono diversi?
AB U è U=0 se A e B sono uguali
Quindi?
A3B3
U3
A2B2
U2
A1B1
U1
A0B0
U0
EQUALS
Oppure, in modo equivalente:
EQUALS = NOT((A3ÅB3)+(A2ÅB2)+(A1ÅB1)+(A0ÅB0))
Con gate:
Codifica di numeri senza segnoDato un numero n di bit (eg, 4), possiamocodificare numeri senza segno assegnando aogni cifra un peso che dipende dalla posizione
b3 b2 b1 b0
23 22 21 20
Pertanto, il valore corrispondente a 1011 è:
1 23 + 0 22 + 1 21 + 1 20 = 8+0+2+1 = 11
Con n bit, il range di valori è compreso tra 0 e 2n-1. Con n=4, l’intervallo risulta [0,15]
Codifica di numeri con segno 1/2Nel caso di numeri relativi, si utilizza larappresentazione in complemento a 2 (C2).
Dati n bit, per gli n-1 bit meno significativivalgono i pesi visti in precedenza mentre ilbit più significativo assume valore -2n-1.
Con n bit, il range di valori è compreso tra-2n-1 e 2n-1-1. Con n=4, l’intervallo risulta[-8,7]
b3 b2 b1 b0
-23 22 21 20
Codifica di numeri con segno 2/2Esempio: quale valore rappresenta 1011 in C2?
-1 23 + 0 22 + 1 21 + 1 20 = -8+0+2+1 = -5
Esempio: quale valore rappresenta 0011 in C2?
-0 23 + 0 22 + 1 21 + 1 20 = 0+0+2+1 = 3
Perché si usa la rappresentazione in C2?
Molto efficiente, si possono fare sottrazionieseguendo solo delle somme: A – B = A + (-B).Inoltre, possiamo ottenere –A invertendo tuttii bit e sommando 1:
Es: A=0101 è -A = 1010 + 1 = 1011
Somma tra numeri binariConsideriamo la somma tra due configurazionibinarie a 3 bit A[2..0] e B[2..0] checodificano numeri senza segno.
Esempio: A[2..0] = 010B[2..0] = 110
Possiamo fare la somma bit a bit, partendo daibit meno significativi (ie, A0 e B0)
1100 riporto (carry)010 +110 =
----1000
10 + 0 + 1 + 1 +0 = 1 = 0 = 1 =--- --- --- ---0 1 1 0
Si noti che: Sum = A Å B e Cout = AB
Tuttavia, se vogliamo eseguire la somma bit abit, esclusa la somma tra la prima colonna(bit 0) dobbiamo considerare sempre il riporto(carry-in, Cin) proveniente dalla colonnaprecedente (carry-out, Cout)
A B Cout Sum
0 0 0 00 1 0 11 0 0 11 1 1 0
Cin A B Cout Sum
0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1
Sum = Cin*A*B + Cin*AB* + CinA*B* + CinAB
Cout = Cin*AB + CinA*B + CinAB* + CinAB
La sintesi con decoder e mux sarebbe immediata.Come?
Con un decoder 3:8 e due OR:
Sum = Y1 + Y2 + Y4 + Y7
Cout = Y3 + Y5 + Y6 + Y7
CinA
Decoder3:8
I2I1I0
76543210
B
Y7Y6Y5Y4Y3Y2Y1Y0
S0
I3
I0
U
I2I1
1
0
00
I7
I4
I6I5
1
0
11
S1S2
CinA
B
Cout
S0
I3
I0
U
I2I1
0
0
11
I7
I4
I6I5
1
1
00
S1S2
CinA
B
Sum
Con due mux a 8 vie:
Nonostante sia possibile in modo immediatofare la sintesi con Decoder o Mux, unasoluzione molto più semplice (in termini dinumero di gate) può essere ottenuta osservandocon attenzione la tabella della verità.
Cin A B Cout Sum
0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1
Sum è 1 solo se, con Cin=0, un solo bit tra Ae B vale 1 mentre, con Cin=1, vale 1 solo se idue bit A e B sono uguali (o entrambi 0 oentrambi 1) è Sum=Cin Å (A Å B)
Cin A B Cout Sum
0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1
AB
Cin Sum
Per la sintesi di Sum abbiamo sfruttato unaproprietà interessante dell’operatore Xor (Å):
1)se un ingresso è zero, l’uscita corrispondeall’altro ingresso
1)se un ingresso è uno l’uscita corrispondeall’altro ingresso negato
Quindi: se un ingresso è 0 l’operatore Årealizza l’operazione identità (U=B) mentre sel’ingresso è 1 lo Å equivale a un not(U=B*)
0B U è U = B
1B U è U = B*
Cout è 1 solo se, con Cin=0, A e B valgonoentrambi 1 mentre, con Cin=1, se entrambi nonsono entrambi zero è Cout=Cin*(AB)+Cin(A+B)
Cin A B Cout Sum
0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1
CinAB Cout
In realtà, il sommatore a due bit (Full-Adder)può essere ulteriormente semplificato semprefacendo riferimento alla tabella della verità.
Cout vale 1 se A=B=1, indipendentemente dalvalore di Cin, oppure se, con Cin=1, A e Bsono diversi:
AB
Cin Sum
1 se A e B diversi
Cout
FA
Mediante il FA appena progettato possiamoeseguire la somma di A[2..0] e B[2..0] comesegue:
FAAB
Cin
Cout
Sum
S0
0A0B0
FAAB
Cin
Cout
Sum
A1B1
FAAB
Cin
Cout
Sum
A2B2
S1 S2S3
La somma di due numeri a n bit (eg, 3) è un numerocodificato con n+1 bit (eg, 4). Perché?
Reti combinatorie e ritardiCome ogni sistema fisico, anche i gate allabase delle reti combinatorie sono soggetti aritardi che dipendono dalla tecnologia con laquale sono realizzati.
In ambito elettronico tali ritardi sonoestremamente ridotti (ordine dei ns) ma vannotenuti in considerazione soprattutto quandoprogetteremo reti sequenziali.
L’effetto del ritardo, di durata τ, su un gateNOT è il seguente:
tA B
A
tB τ τ
Maggiore è il numero di gate attraversati daun segnale e maggiore è il ritardo (ie, sisommano).
•Qual è il ritardo (massimo) nella somma diA[2..0] e B[2..0] dell’esempio precedente(assumendo che tutti i gate abbiano lo stessoritardo τ) a fronte di una modifica di unsegnale di ingresso?
•Con le stesse assunzioni, ritardo τ per ognigate: qual è il ritardo massimo nel caso delcomparatore?
Arithmetic and Logic Unit (ALU)
U = FP (X,Y)
ALU
X[n-1..0]
U[z-1..0]
FLAG[r-1..0]
P[k-1..0]
Y[n-1..0]
ALU - Rete combinatoria in grado di eseguirediverse operazioni di tipo aritmetico ologico. L’operazione di volta in voltaeseguita dipende dal valore attribuito a deibit di programmazione (codice operazione)
n
n
z
r
k
• eseguendo 2A si ottiene -A
• eseguendo A+B si ottiene la somma algebrica fra A e B
Siano A e B due numeri rappresentati incomplemento a 2:
• eseguendo A + 2(B) si ottiene A - B 1 0 0 1
1 1 0 1 +1 1 0 0 =
A = -3 B = -4
-7 1 1 1 1
1 1 0 0 +0 0 1 1 =
A = -4 B = +3
-1
A: 0 0 0 1 (+1)1 1 1 0 +
1A2: 1 1 1 1 (-1)
1 0 0 1 (-7)0 1 1 0 +
10 1 1 1 (+7)
Rappresentazione in complemento a 2: proprietà
Esercizio: Dato un full-adder a 4 bit,progettare una rete che esegue il complementoa 2 di A[3..0]
4
4
FA(4 bit)
A[3..0]
B[3..0]
S[3..0] 4Cin Cout
4
4
FA(4 bit)
A[3..0]
B[3..0]
S[3..0] 4Cin Cout
S[3..0]A[3..0]
‘0000’
1
Il complemento a 2 del numero A si ottieneeseguendo il Not di A e sommando 1. Pertanto,-A può essere ottenuto mediante:
Si osservi che, non sommando 1 (Cin=0) aNot(A), si ottiene –A-1.
Cosa accade per A[3..0]=1000?
Un adder/subtracter programmabile
4
4
FA(4 bit)
A[3..0]
B[3..0]
S[3..0]4
Cin Cout
S[3..0]A[3..0]
B[3..0]
Cin
1
0S4
C0
Cin C0 S[3..0]0 0 A[3..0] + B[3..0]0 1 A[3..0] – B[3..0] -11 0 A[3..0] + B[3..0] +11 1 A[3..0] - B[3..0]
4
Più operazioni aritmetiche
4
4
FA(4 bit)
A[3..0]
B[3..0]
S[3..0]4
Cin Cout
S[3..0]A[3..0]
B[3..0]
Cin
1
0S4
C0
4
1
0S
C2
1
0S
C1
4
4
4
4‘0000’
‘0000’
Consideriamo due casi (pagine seguenti):- Cin = 0- Cin = 1
C2 C1 C0 S[3..0]0 0 0 A[3..0] + B[3..0]0 0 1 A[3..0] - B[3..0] - 10 1 0 A[3..0]0 1 1 A[3..0] - 11 0 0 B[3..0]1 0 1 -(B[3..0]+1)1 1 0 01 1 1 -1
Cin = 0
In questa tabella il simbolo ‘+’ rappresenta la somma aritmetica e non l’operatore logico OR
C2 C1 C0 S[3..0]0 0 0 A[3..0] + B[3..0] + 10 0 1 A[3..0] - B[3..0]0 1 0 A[3..0] + 10 1 1 A[3..0]1 0 0 B[3..0] + 11 0 1 -B[3..0]1 1 0 11 1 1 0
Cin = 1
In questa tabella il simbolo ‘+’ rappresenta la somma aritmetica e non l’operatore logico OR
Operazioni logicheSpesso è necessario poter eseguire ancheoperazioni logiche. Vediamo cosa accade serendiamo possibile decidere se bloccare ilpropagarsi del riporto nei FA mediante unulteriore bit di programmazione M, denominatodi modalità:
FAAB
Cin
Cout
Sum
Si
AiBi
FAAB
Cin
Cout
Sum
Ai+1Bi+1
Si+1
M
Couti-1
Couti+1
Couti
- M=1: il FA agisce come visto in precedenza
- M=0: ogni FA risulta logicamente isolato dalprecedente dal successivo, in particolarerisulta:
ABCin Sum = A Å B
1 se A e B diversi
Couti
FA
0
M=0
0
M=0
Couti-1
4
4
FA(4 bit)
A[3..0]
B[3..0]
S[3..0]4
Cin Cout
S[3..0]A[3..0]
B[3..0]
Cin
1
0S4
C0
4
1
0S
C2
1
0S
C1
4
4
4
4‘0000’
‘0000’
Consideriamo due casi (pagine seguenti):- Cin = 0- Cin = 1
MM
Nel caso M=0, risultano le seguenti operazionilogiche:
C2 C1 C0 S[3..0]
0 0 0 A[3..0] Å B[3..0]
0 0 1 NOT(A[3..0] Å B[3..0])
0 1 0 A[3..0]
0 1 1 NOT(A[3..0])
1 0 0 B[3..0]
1 0 1 NOT(B[3..0])
1 1 0 00001 1 1 1111
M = 0 (Cin è ininfluente)
Aggiungendo un ulteriore bit di programmazionee delle porte logiche addizionali è possibileeseguire anche AND e OR tra A[3..0] e B[3..0]
Esercizio: Cosa accade, se inseriamo unulteriore bit di programmazione denominato C3?
FA(1 bit)
A
B
S
Cin Cout
Si
Ai
Bi
Cin
1
0S
C0
1
0S
C2
1
0S
C1‘0’
‘0’
M
C3
C2 C1 C0 S[3..0]
0 0 0 A[3..0] Å B[3..0]
0 0 1 NOT(A[3..0] Å B[3..0])
0 1 0 A[3..0]
0 1 1 NOT(A[3..0])
1 0 0 B[3..0]
1 0 1 NOT(B[3..0])
1 1 0 00001 1 1 1111
M=0,C3=0
C2 C1 C0 S[3..0]
0 0 0 A[3..0] OR B[3..0]
0 0 1 NOT(A[3..0] Å B[3..0])
0 1 0 A[3..0]
0 1 1 NOT(A[3..0]) OR B[3..0])
1 0 0 B[3..0]
1 0 1 A[3..0] OR (NOT(B[3..0]))
1 1 0 A[3..0] AND B[3..0]1 1 1 1111
M=0,C3=1
Segnali di FlagUna ALU dispone anche di ulteriori bit diuscita, denominati bit di flag, che segnalanoil verificarsi di particolari condizioni.
Ogni bit di flag può essere o menosignificativo in base all’operazione svoltadalla ALU.
ZF (Zero flag) : 1 se risultato 0SF (Sign flag) : 1 se risultato negativoCF (Carry flag) : 1 se CO ultimo FA=1OF (Overflow flag) : se 1 c’è traboccamento
in operazioni tra numeri rappresentati in C2
PF (Parity flag) : il numero di 1 è pari
Le espressioni logiche per i flag della ALU a 4 bit risultano:
ZF = NOT(S3 + S2 + S1 + S0)
SF = S3
CF = Cout3
OF = S3 Å Cout3
PF = (S3 Å S2 Å S1 Å S0)
Esercizio: Si supponga che in un edificiosiano presenti 256 appartamenti, 16 per ognipiano. Inoltre, per evitare di inserire 256pulsanti al piano terra, si è deciso diutilizzare un certo numero di interruttoribinari per attivare il campanello di unqualsiasi appartamento.
ALARM_ON
RING_ON
ALARM_ON = ?RING_ON = ?
1) Quanti interruttori binari servono percodificare tutti i 256 appartamenti?
2) Progettare una rete che, data unaconfigurazione binaria degli interruttori alpiano terra, attiva solo il campanellodell’appartamento selezionato.
3) Qual è un problema (pratico) del punto 2?
4) Nell’ipotesi che gli appartamenti sianonumerati in ordine progressivo: progettareuna rete che, dato il codice A[3..0] delpiano nel quale si è verificato un incendioe un segnale FIRE che indica tale evento,attiva contemporaneamente tutti i 16campanelli antincendio in quel piano.
i
Piano 0 (0000)
Piano 15 (1111) 15
j
0
App. 15 (1111)
App. 0 (0000)
App. j
Piano i
Conviene introdurre la rappresentazione deinumeri in esadecimale nella quale i simbolisono 16:
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
A ogni 4 cifre binarie corrisponde una cifraesadecimale -> rappresentazione più compatta
0x, h o 16 indicano comunemente che un numero èrappresentato in esadecimale
01001111001101102 4F3616 (o 0x4F36 o 4F36h)
i
Piano 0 (0h)
Piano 15 (Fh) 15
j
0
App. 15 (Fh)
App. 0 (0h)
App. j
Piano i
1) Per codificare le 256 informazioni (16 x 16appartamenti) sono necessari 8 interruttoribinari
SW7SW6SW5SW4SW3SW2SW1SW0
SW6SW5
Decoder4:16
I2I1I0
U7U6U5U4U3U2U1U0
SW4 P7P6P5P4P3P2P1P0
SW7 I3
U15U14U13U12U11U10U9U8
P15P14P13P12P11P10P9P8
2) Per prima cosa è possibile individuare ilpiano (1 su 16) dai 4 bit più significativi
Successivamente è possibile individuare, inogni piano, l’appartamento selezionato (1 su16) utilizzando un decoder 4:16 dai bit menosignificativi
SW2SW1
Decoder4:16
I2I1I0
U7U6U5U4U3U2U1U0
SW0 A7A6A5A4A3A2A1A0
SW3 I3
U15U14U13U12U11U10U9U8
A15A14A13A12A11A10A9A8
RING_ON[Pi,Aj] = PiAj
3) Nella soluzione appena mostrata è attivosempre un campanello. Per risolvere ilproblema, si potrebbe aggiungere un ulterioreinterruttore, denominato ENABLE
SW7SW6SW5SW4SW3SW2SW1SW0
ENABLE
RING_ON[Pi,Aj] = ENABLEPiAj
RING_ON
Per ragioni simili a quelle del caso in esame,spesso i decoder dispongono di un ulterioresegnale di ingresso denominato EN.Se EN=0, tutte le uscite sono 0Se EN=1, agisce come un normale decoder
Decoder4:16
I2I1I0
U7U6U5U4U3U2U1U0
I3
U15U14U13U12U11U10U9U8
EN
4) Il segnale di allarme collegato a ogniappartamento di ogni piano, può essereottenuto decodificando il codice A[3..0] delpiano nel quale è presente l’incendio.
Analogamente al punto 2), sarà presente unulteriore segnale, denominato FIRE,proveniente dalla centralina di allarme cheindica che è stato rilevato un incendio.
Nella pagina seguente è mostrata la rete cheattiva, in ogni appartamento del piano nelquale è in corso l’allarme, la segnalazioneacustica mediante il segnale ALARM_ON
ALARM_ON
A2A1
Decoder4:16
I2I1I0
U7U6U5U4U3U2U1U0
A0C7C6C5C4C3C2C1C0
A3 I3
U15U14U13U12U11U10U9U8
C15C14C13C12C11C10C9C8
Per qualsiasi appartamento del piano k-esimo, l’allarme è attivato dal segnale:
ALARM_ON[Pk] = Ck
ENFIRE
Esercizio: Partendo dalla seguente tabelladella verità che descrive una rete con treingressi A,B,C e tre uscite X,Y,Z
1) Realizzare la rete con gate (AND, OR e NOT)2) Realizzare la rete con decoder3) Realizzare la rete con multiplexer
A B C X Y Z
0 0 0 0 1 00 0 1 1 0 10 1 0 1 1 10 1 1 1 0 01 0 0 0 1 01 0 1 1 1 01 1 0 0 0 11 1 1 0 0 1