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