Marco Tarini -Università dell'InsubriaA.A. 2017-18Architettura degli elaboratori -Blocchi funzionali combinatori -21

(1)

Blocchi funzionali combinatori

Architettura degli elaboratori - 20 -

Confrontatore

Il blocco funzionale confrontatore ha:

due gruppi A e B di ingressi da n  1 bit ciascuno tre uscite:

A  B A  B A  B

Il blocco confronta i due numeri binari A e B da n bit presenti sui due gruppi di ingressi, e

attiva (a 1) l’uscita corrispondente all’esito del confronto azzera le uscite corrispondenti alle condizioni false

Confrontatore di numeri a 3 bit

Esempi:

Se A = 001 e B = 010 A>B = 0

A=B = 0 A<B = 1

Se A = 101 e B = 100 A>B = 1

A=B = 0 A<B = 0

Se A = 010 e B = 010 A>B = 0

A=B = 1 A<B = 0 A>B

A=B A<B A

B COMP 3

3

(2)

Confrontatore di numeri a 2 bit

Tabella delle verità

A>B A=B A<B A0

B0

COMP A1

B1

A1 A0 B1 B0 A<B

0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0

A>B A=B

Confrontatore a 2 bit: sintesi (A<B)

Tabella delle verità

A1 A0 B1 B0 A<B

0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0

A>B

A=B 0

0 0 1

1 1

1 0

0 0

0 1 A1 A0

B1 B0

1

1 0 1 1

A<B

1 1

0 1 0

0 0 0 0

0 0 0

0

A<B= /A1 B1+ /A1 /A0 B0+ /A0 B1 B0

(3)

Confrontatore a 2 bit: sintesi (A=B)

Tabella delle verità

A1 A0 B1 B0 A<B

0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0

A>B A=B

A=B= /(A1  B1) /(A0  B0) A>B = /(A<B) /(A=B)

Ripasso: operatore booleano NXOR

Porte logiche

A B X 0 0 1 0 1 0 1 0 0 1 1 1 NXOR

(«fa il contrario di XOR»)

Significati intuitivi di A NXOR B:

uno XOR seguito da un NOT A NXOR B = \( A XOR B) cioè…

entrambi veri oppure entrambi falsi cioè…

AB + \A\B cioè…

operatore di uguaglianza fra A e B vero se A e B sono uguali.

falso se sono diversi

(4)

Confrontatore a 2 bit: possibile implementazione

A<B= /A1B1 + /A1/A0B0 + /A0B1B0 A=B= /(A1  B1) /(A0  B0) A>B = /(A<B) /(A=B) A1 A0

B0 B1

A<B

A=B A>B

Confrontatore a 4 bit realizzato con confrontatori a 2 bit

Si confrontano separatamente le parti più significative, e le parti meno significative, di X e Y.

A>B A=B A<B A0

B0 A1

B1

X = Y

Y0

Y2 Y1

Y3

COMP A>B A=B A<B A0

B0 A1

B1 X0

X2 X1

X3

COMP

X > Y

X < Y

(5)

Interpretazione dei dati

Nello stesso modo, posso costruire un confrontore per 2n bit con con due confrontatori da n bits

Due confrontatori a 2 bit = 1 confrontatore a 4 bit Due confrontatori a 4 bit = 1 confrontatore da 1 byte

Due confrontatori a 1 byte = 1 conf. da 2 byte (per short int!) Due confrontatori a 2 byte = 1 conf. da 4 byte (per int!)

Compito a casa

Si noti che circuiti come Decoder e Multiplexer non fanno alcuna ipotesi sul significato dei segnali.

Il confrontatore invece ipotizza che i dati di ingresso siano dei numeri naturali codificati in binario

(e non in CP2 o in virgola mobile…).

Realizzare un confrontatore tra numeri di tre bit in complemento a 2.

Es. se X = 011 e Y = 111, il confrontatore deve mettere a uno l’uscita X>Y e a zero le altre. Infatti in complemento a 2 011=3, mentre 111=-1.

(6)

Ripasso: operatore XOR

Porte logiche

A B X 0 0 0 0 1 1 1 0 1

1 1 0

XOR («or esclusivo»)

uno o l’altro, ma

NON entrambi

Significati intuitivi di A XOR B:

A oppure B, ma non entrambi (in latino: Aaut B)

vero se A e B diversi falso se A e B uguali vale /A se B = 1 vale A se B = 0 (e viceversa)

il contrario di A, se B vale;

A immutato, altrimenti (e viceversa)

…

somma naturale di A e B come numeri di… 1 bit!

(ignorando il bit di riporto)

Semisommatore

Dati due numeri naturali rappresentati su un solo bit, il circuito ne calcola la somma (compreso il riporto).

Tavola delle verità A B S Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1

A

B S

Carry

(7)

Sommatore

Dati due numeri naturali rappresentati su un solo bit, e il riporto della somma precedente, il circuito ne calcola la somma (compreso il riporto). Cioè in pratica la somma dei tre bit.

Tavola delle verità A B Cin S Cout 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

Cout = AB + /ABCin + A/BCin = AB + Cin (/AB+A/B) =

AB + Cin (AB) S= A B  Cin

xor

Sommatore

Cout = AB + /ABCin + A/BCin = AB + Cin (/AB+A/B) =

AB + Cin (A



B) S= A



B



Cin

A B

S

Cin Cout

(8)

Sommatore

A B

S

Cin Cout

Sum 1 bit

A B Cin

S Cout

Sommatore binario

naturale a n bit (n-bit adder)

È la generalizzazione del sommatore completo: addizione di numeri naturali binari a n bit

Ha in ingresso due numeri naturali A e B da n  1 bit ciascuno In uscita presenta la somma a n bit dei due numeri interi A e B Tipicamente: ha un riporto in ingresso e un riporto in uscita

In uscita presenta A + B + (Riporto in ingresso)

Nota: come sappiamo lo stesso circuito funziona anche per sommare due numeri in complemento a due!

(9)

Sommatore a 3 bit: realizzazione

Sum 1 bit

A B

Cin S

Cout

Sum 1 bit

A B

Cin S

Cout

S1 S0

S2

Cout

(ultimo riporto) A1

A0 A2

B1 B0 B2

Ritardo?

0

Sum 1 bit

A B

Cin S

Cout

A0

A1 B1B0

sommatore

a 3 bit ingressi

addendi

uscite di somma

A2 B2

S2 S1 S0

R_usc R_in

uscita di

riporto ingresso

di riporto

Sommatore intero binario naturale a 3 bit

1 1 0 0 1 0

0

0 1

1

2 3

5

0

⁰

(10)

A0

A1 B1B0

sommatore

a 3 bit ingressi

addendi

uscite di somma

A2 B2

S2 S1 S0

Rusc Rin

uscita di

riporto ingresso

di riporto

Sommatore intero binario naturale a 3 bit

0 1 1 1 1 0

0

1

0 1

0

3 6

1 overflow

⁰

A0

A1 B1B0

sommatore

a 3 bit ingressi

addendi

uscite di somma

A2 B2

S2 S1 S0

R_usc R_in

uscita di

riporto ingresso

di riporto

Lo stesso circuito, ma intepreato come sommatore di interi a 3 bit in CP2

0 1 1 1 1 0

0

1

0 1

0

+3 -2

+1

(ignorare)

⁰

(11)

Sommatore: Overflow Coi numeri naturali (senza segno):

l’uscita finale Cout (l’ultimo riporto) è un bit che segnala l’overflow

Con i numeri in complemento a 2:

L’uscita finale Cout non segnala overflow (va semplicemente ignorata)

L’overflow è segnalato invece da una funzione dei bit più significativi di A, B e S

(cioè quelli che rappresentano i segni dei tre numeri A B e S) Regola, per 8 bit:

se A7== B7ma A7=/= S7 allora overflow Esercizio (facile):

costruire un circuito che restituisce 1 se c’è stato overflow

Sommatore bit a bit?

Il sommatore che abbiamo visto ha una velocità bassa Possibile miglioramento:

Ottimizzare un sommatore a 2 bit

Totale: 5 ingressi, 3 uscite

Per es, usare Karnaugh (per ciascuna uscita!) (esercizio)

Poi, utilizzare sommatore a 2 bit per costruire sommatori più grandi

SUM 2 bit A

B

Cin S

Cout 2

2

A + B + Cin

ultimo riporto

(12)

Sommatore a 8 bit:

realizzazione con 4 sommatori a 2 bit

Cout

(l’ultimo riporto) A2,3

A0,1

A4,5 Cin

SUM 2 bit A B

Cin S

Cout

SUM 2 bit A B

Cin S

Cout

SUM 2 bit A B

Cin S

Cout

SUM 2 bit A B

Cin S

Cout

A6,7

B2,3 B0,1

B4,5 B6,7

2 2 2 2

S2,3 S0,1

S4,5 S6,7

sommatore a 8 bit

Semplice esempio di progetto con blocchi funzionali

Si chiede di progettare un circuito digitale combinatorio, che abbia:

in ingresso due numeri binari naturali A e B da n bit ciascuno in ingresso un segnale di comando C da un bit

in uscita un numero binario naturale Z da n bit tale che Z = A + B , quando C = 0

Z = A  B , quando C = 1 Si trascurano i riporti

In pratica:

C rappresenta il comando (ed A e B i suoi operatori), in un ipotetico, minuscolo Instruction Set di una ALU composto da due sole istruzioni: { somma , sottrazione }

il circuito è specie di una minuscola ALU capace di due sole op.

è il nostro primo passo da una calcolatrice verso un calcolatore :-)

(13)

Soluzione 1

+

B

+

MUX 0

1 A

cambio segno

C

Z

n n

n

Idea: usare un sommatore anche per la sottrazione… A – B = A + (– B)

Soluzione 2

B

+

MUX 0

1

A

cambio segno

C

Z n

n

n Meno costosa della precedente: abbiamo risparmiato un sommatore!

(14)

Flip del segno (complemento a due)

Sottoproblema: circuito che cambia segno (in complemento a due)

Ricorda: cambiare segno = flip dei bit, e aggiungere 1

+

ⁿ ^-X

X ⁿ ⁿ

0 n Cin

1 cambio

segno ⁿ -X

X ⁿ

Soluzione 2 (raffinamento)

B

+

MUX 0

1

A

C

Z n

n

0 ^Cin

+

1 cambio

segno

Spreco: un SUM solo per sommare 1!

(15)

Soluzione 2 (ottimizzata)

B

+

MUX 0

1

A

C

Z n

n

Cin