Blocchi funzionali combinatori

(1)

Università degli Studi dell’Insubria Corso di Laurea in Informatica

Architettura degli elaboratori

Il Livello Logico-Digitale Blocchi funzionali combinatori

Marco Tarini

Dipartimento di Scienze Teoriche e Applicate marco.tarini@uninsubria.it

Blocchi funzionali combinatori

Coi metodi visti fin’ora (che usano la tavola di verità o le mappe di Karnaugh) possiamo fare solo reti piccole, con pochi input.

La realizzazione di moderni circuiti integrati richiede la sintesi di reti molto più grande

Idea: combinare reti piccole in reti più grandi sotto rete piccola = blocco funzionale

Nel tempo, si è stabilita una “libreria” di blocchi funzionali standard che realizzano funzioni comuni,

cioè che risultano utili in contesti diversi.

Esiste dunque una ben nota e ormai stabilizzata libreria di blocchi funzionali combinatori

Questo include anche blocchi funzionali di tipo sequenziale (che vedremo poi)

(2)

Blocchi funzionali combinatori

Architettura degli elaboratori - 3 -

Decoder (decodificatore)

Il blocco funzionale decodificatore ha:

n  1 ingressi 2ⁿuscite

Le uscite sono numerate a partire da 0 k = 0, 1, 2, …, 2^{n  1}

Se sugli ingressi è presente il numero binario k la k-esima uscita assume il valore 1

e

le restanti uscite assumono il valore 0

Decoder a 2 ingressi

U0 U1 U2 U3 I0

I1 DEC 1

0 0

0 0 1

Codifica binaria

del numero 2 L’uscita 2 è

attivata

(3)

Decoder a 2 ingressi

Tabella delle verità I1 I0 U0 U1 U2 U3

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

U0 U1 U2 U3 I1

I0 DEC

Decoder a 2 ingressi: realizzazione

I0 I1

U0 U1 U2 U3

U0 U1 U2 U3 I0

I1 DEC

(4)

Multiplexer (multiplatore)

Il blocco funzionale multiplatore ha 2 gruppi di ingressi:

n  1 ingressi di selezione 2ⁿingressi dati

almeno due, poiché n non può essere nullo e un’uscita

Sempre unica

Gli ingressi dati sono numerati a partire da 0 k = 0, 1, 2, …, 2ⁿ 1

Se sugli ingressi di selezione è presente il numero binario k, il k-esimo ingresso dati viene inviato in uscita

Multiplexer a 2 ingressi di selezione

I0 I1 I2 I3

S1 S0 U A

B C D

0 1

B Ingressi

Dati

Uscita Ingressi di selezione

MUX

(5)

Multiplexer a 2 ingressi di selezione

Tabella delle verità

I0 I1 I2 I3

S1 S0 U A

B C D

S1 S0 I0 I1 I2 I3 U 0 0 A X X X A 0 1 X B X X B 1 0 X X C X C 1 1 X X X D D MUX

Multiplexer a 2 ingressi di selezione:

realizzazione

DEC S0

S1

A B C D

U

(6)

Multiplexer a 2 ingressi di selezione:

realizzazione alternativa

S0 S1

A

B C D

U

Il Multiplexer a un ingresso di selezione è l’ “if” dell’hardware

I0 I1

S0 U A

B

MUX

if S0

then U = B else U = A

(7)

Il Multiplexer a un ingresso di selezione è l’ “if” dell’hardware

Software

if A>B then C=A else C=B

Hardware

A B

0

1

C

A>B

Il Multiplexer a un ingresso di selezione è l’ “if” dell’hardware

Software

if A>B

then C=g(X) else C=f(X)

Hardware

A B

0

1

C

A>B

X f

g

Entrambe le funzioni sono calcolate, ma solo un risultato alla volta viene usato!

(8)

Il Multiplexer a k ingressi di selezione (e ingressi dati a n bit)

I⁰ I¹

S U A0

MUX k n

A1 n

IM

AM n

... ...

n AB

con M = 2

^k

– 1

B

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

(9)

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

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

(10)

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 00 01 11 10

00 01 A1A0

B1B0

1

10 11

A<B

1 1

0 1 0

0 0 0 0

0 0 0

0 A<B= /A1B1 + /A1/A0B0 + /A0B1B0

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)

(11)

Ripasso: operatore booleano NXOR

Porte logiche

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

(«fa il contrario di XOR»)NXOR 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

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

(12)

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

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!)

(13)

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.

Ripasso: operatore XOR

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

1 1 0

(«or esclusivo»)XOR

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)

(14)

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

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

(15)

Sommatore

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

AB + Cin (A



B) S= A



B



Cin

A

B S

Cin Cout

Sommatore

A

B S

Cin Cout

Sum 1 bit

BA Cin

S Cout

(16)

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!

Sommatore a 3 bit: realizzazione

Sum 1 bit

BA

Cin S

Cout

Sum 1 bit

BA

Cin S

Cout

S1 S0 S2

Cout(ultimo riporto) A1

A0 A2

B1B0 B2

Ritardo?

0

Sum

1 bit

BA

Cin S

Cout

(17)

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

1 1 0 0 1 0

0

0 1

1

2 3

5

0

⁰

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

⁰

(18)

Sommatore bit a bit?

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

Ottimizzare un sommatore a 2 bit

Nota: Totale: 5 ingressi, 3 uscite Usare Karnaugh

(esercizio, per ogni uscita!)

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

SUM2 bit BA

Cin S

Cout 2

2

A + B + Cin ultimo riporto

Sommatore a 8 bit: realizzazione

Cout(l’ultimo riporto) A2,3

A0,1 A4,5 Cin

SUM2 bit BA

Cin S

Cout SUM2 bit BA

Cin S

Cout SUM2 bit BA

Cin S

Cout SUM2 bit BA

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

(19)

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 A⁷== B⁷ma A⁷=/= S⁷allora overflow Esercizio (facile):

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

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 :-)

(20)

Soluzione 1

+

B

+

0MUX 1 A

cambio segno

C

Z

n n

n

n n

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

Soluzione 2

B

+

0MUX 1

A

cambio segno

C

Z n

n

n Meno costosa della precedente: abbiamo risparmiato un sommatore!

(21)

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

+

0MUX 1

A

C

Z n

n

0 ^Cin

+

cambio 1 segno

Spreco: un SUM solo per sommare 1!

(22)

Soluzione 2 (ottimizzata)

B

+

0MUX 1

A

C

Z n

n

Cin

Left Shift (moltiplicazione per 2, 4, 8 …)

Ricorda: uno shift a sinistra in base 2 = raddoppio del numero Notazione: <<

Esempi:

|11011|₂= 27

|11011|2<< 1 = |110110|2= 27x2 = 54

|11011|₂<< 2 = |1101100|₂= 27x4 = 108

|11011|₂<< 3 = |11011000|₂= 27x8 = 216

(23)

Left Shift

(con secondo parametro costante)

Blocchi funzionale per shift: (usano…. zero porte!) Esempi per 4 bit:

X0 X1 X2 X3

X0 X1 X2 X3 0

4 4

<< 1

X 2X

X0 X1 X2 X3

X0 X1 X2 X3 0

4 4

<< 2

X 4X

Left Shift

(con secondo parametro variabile)

n n

A

_k

A << B

B <<

A

n

B

2

<<1

<<2

<<3

I0 I1

S

U

MUX

I2 I3 n n

n

n n

2 Realizzazione con K = 2

(24)

Prodotto: algoritmo delle scuole elementari (ma in base 2)

100011 × 1011 = 1× 100011 + 1× 100011 + 0× 100011 + 1× 100011 = 110000001 B

A B

A x B

1 1 1 1 1 1