Esercizio 1: soluzione 1

(1)

Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Circuiti combinatori e funzioni di libreria - esercizi Marco Tarini

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

Esercizio 1

Date 5 variabili booleane x4, x3, x2, x1, x0, e altre due variabili y0 ed y1, progettare il circuito che,

se y1,y0=0,0 , esegue x4 and x0, se y1,y0=0,1 , esegue x4 and x1, se y1,y0=1,0 , esegue x4 and x2, se y1,y0=1,1 , esegue x4 and x3

Osservazione: la sintesi del circuito a partire dalla tavola delle verità non è praticabile senza strumentazione adeguata

(la tavola ha 128 righe!)

(2)

Esercizi - Funzioni combinatorie

Architettura degli elaboratori - 3 -

Esercizio 1: soluzione 1

Realizziamo tutte le funzioni e selezioniamo con un MUX quella da mandare in uscita.

F

x0 x1 x2 x3 x4

I0 I1 I2 I3

S1 S0 U y0 y1

Esercizio 1: soluzione 2

Poiché le funzioni possibili sono sempre del tipo x4 and un secondo ingresso

Possiamo selezionare l’ingresso con un MUX, mandarlo alla porta and e ottenere così il risultato.

x0

F

x1x2 x3 x4

I0 I1 I2 I3

S1 S0 U y0 y1

(3)

Esercizio 2:

Progettare un circuito che conti il numero di 1 presenti su 12 ingressi utilizzando 11 «full adder» (da un bit).

Ricordare: un full adder prende tre bit (due addendi e un riporto ingresso)

e restituisce due bit: somma e riporto in uscita

Contatore 12

I

4

O

Esercizio 2: Soluzione “divide et impera”

Partizioniamo l’insieme degli ingressi in 2 insiemi da 6 ingressi ciascuno.

Contiamo gli uni di ciascun insieme (max 6: output da 3 bit) Sommiamo i due numeri da 3 bit ottenuti (servono 3 FA)

Contatore a 6 6 Contatore a 6

6

I

5

..I

0

I

₁₁

..I

₆

3 3

SUM 4

O

(4)

Esercizio 2: Soluzione

Per soddisfare la richiesta iniziale rimangono solo 4 FA per realizzare ciascuno dei due Contatore. Si Può?

Contatore

FA

₂

O

₁

O

₀

0

Contatore a 6

sommatore

a 2 bit

(5)

Esercizio 3

Progettare un circuito che confronti due numeri senza segno su 8 bit (A e B) e produca due uscite:

U (U=1 sse i numeri sono uguali) M (M=1 sse A>B and U=0)

Suggerimento: prima costruire una iterare una semplice struttura che confronta una coppia di bit nella stessa posizione dei due numeri, tenendo conto dei risultati dei confronti dei bit meno significativi).

Esercizio 3: Soluzione matematica

U(An..A0, Bn..B0)  An= Bn U(An-1..A0, Bn-1..B0) U(A0, B0)  A0=B0

M(An..A0, Bn..B0)  An>Bn [An=Bn M(An-1..A0, Bn-1..B0)]

M(A0, B0)  A0>B0

Ai = Bi  /(Ai  Bi) Ai>Bi  Ai /Bi

Espresso a parole:

A e B sono uguali se:

lo sono sia le loro cifre più significative sia quelle meno significative A è maggiore di B se:

le cifre più significative di A sono maggiori di quelle di B, oppure

le cifre più significative di A e B sono uguali e contemporanemente le cifre meno significative di A sono maggiori di quelle di B,

(6)

Esercizio 3: soluzione sequenziale

> = U

A

₇

B

₇

> = A

₆

B

₆

M

> = A

₀

B

₀

> = A

₁

B

₁

. . . . . .

U(A₆..A₀, B₆..B₀)

M(A₆..A₀, B₆..B₀)

_i-1

(7)

Esercizio 3: soluzione ricorsiva (divide et impera)

Implementiamo il comparatore a 8 bit usando due comparatori a 4 bit:

B

0..3

B

4..7

A

_0..3

A

_4..7

4 4 4 4

> =

₁

> =

Co m pa rato re d a 2 bit

Comparatore Da 1 bit

Esercizio 3: soluzione ricorsiva (divide et impera)

Infine, implementiamo un comparatore da 1 bit

A B

> =

(9)

Esercizio 3: soluzioni a confronto (note)

Entrambe le soluzioni (iterativa, ricorsiva) sono corrette Dei due circuiti risultanti nelle due soluzioni:

Quale usa meno porte?

Quale è più veloce (ha meno latenza)?

Ris pos te: sso Ste nu mer

o ndo eco Il s

Esercizio 4

Progettare una ALU elementare che esegua –a seconda del valore di due bit di controllo– le seguenti 4 funzioni sugli input A e B a 2 bit :

somma A+B, differenza A-B,

«complemento a 1» di B (cioè negazione di tutti i bit di B) inversione delle posizioni dei bit di A.

La ALU genererà anche i condition code Z (risultato zero)

N (risultato negativo)

Si trascurano invece gli overflow Il risultato sia su due bit

(10)

Esercizio 4: Soluzione banale

Naturalmente è possibile adottare un approccio banale:

Si realizzano in parallelo tutte le funzioni

Si sceglie quale mandare in uscita attraverso un MUX comandato dai segnali di controllo

+

B A

InvBit - Compl

MUX NB: manca il calcolo

di Z e N

(peraltro calcolabili facilmente sull’uscita)

F

2 2

2

Esercizio 4: Soluzione 1

+

B A

InvBit +

F 2

2 Z 2 N

^MSB

1

MUX

U=Compl(B) quando F = 00 U=A-B quando F = 01 U=A+B quando F = 10 U=A₀A₁quando F = 11

U

MSBLSB

FA a 2 bit (ottenibili banalmente con

2 FA ad un bit)

(11)

Esercizio 4: Alternativa

Si può cercare di minimizzare la circuiteria specifica da usare, impiegando quasi esclusivamente blocchi funzionali.

Di sicuro ci vogliono dei sommatori, perché bisogna calcolare A+B, quindi possiamo realizzare un circuito che somma valori diversi a seconda dei segnali di controllo:

A+B quando F = 00

A+(-B) quando F = 01

0+Compl(B) quando F = 10 (A₀A₁)+0 quando F = 11 NB:A+(-B) = A+Compl(B)+1

Esercizio 4: Circuito alternativo

MUX

A₁ A₀ B₁ B₀

FA FA

MUX MUX

F=00F=01 F=10F=11 MUX

0

F₀ F₁

O

2

O

1

O

0

Z

N

^A+B_A-B

Cpl(B) Inv A

(12)

Esercizio 4: valutazioni sul costo

Il progetto “banale” richiede 4 FA a un bit

1 MUX a 4 ingressi da 2 bit poche altre porte elementari.

Il progetto alternativo richiede 2 FA ad un bit

4 MUX a 4 ingressi da un bit poche altre porte.

Esercizio 5 (esame del 4/2/2003 )

Progettare una ALU elementare a 4 bit che esegua le seguenti 4 funzioni sugli input A e B:

somma A+B, differenza A-B, differenza B-A

uscita uguale a A (identità)

a seconda del valore di due bit di controllo La ALU genererà anche i condition codes

V (vale 1 quando gli operandi hanno lo stesso segno e il risultato è di segno opposto)

N (risultato negativo).

(13)

Esercizio 5: Soluzione non ottimizzata

Naturalmente è possibile adottare un approccio banale:

Si realizzano in parallelo tutte le funzioni

Si sceglie quale mandare in uscita attraverso un MUX comandato dai segnali di controllo

Tuttavia, questo tipo di approccio porta a una realizzazione inutilmente dispendiosa

Proprio perché si eseguono tutte le funzioni in parallelo.

Cerchiamo una soluzione alternativa basata sul fatto che:

In tutti i casi bisogna fare una somma.

Si può selezionare su quali operandi effettuare la somma.

A+BA+0

A+/B+1 (A-B) /A+B+1 (-A+B)

Esercizio 5: soluzione

A B

FA

F0

F1

FA FA FA

O

0

O

1

O

2

O

3

SEL SEL

F

SEL SEL

F0

F1 A B SEL1

0

0 A B A

1

0 A B A

0

1 A B

1 /A

1 A B

A SEL0

B /B B 0 Trasforma la negazione in complento a 2

N V

LV

A₀ A₁

A₂ A₃

B0

B1

B2

B3

Cin

0 1 1 0

(14)

Esercizio 5: implementazione di SEL1

F

₀

F

₁

A B SEL

₁

0 0 A B A

1 0 A B A

0 1 A B

/A 1

1 A B

A

SEL

₀

B /B B 0

Ai

F₀ F₁

SEL1

A  0 = A A  1 = A

Esercizio 5: implementazione di SEL0

F

0

F

1

A B SEL

1

0 0 A B A

1 0 A B A

0 1 A B

1 /A

1 A B

A

SEL

0

B

/B B 0

F0

F₁

B_i 0

SEL₀

SEL

0

= B /(F1F0) + /B F1 /F0

B_i F0

F₁ SEL₀

MUX

(15)

Esercizio 5: Calcolo di V (overflow)

V vale 1 quando entrambi gli operandi hanno lo stesso segno e il risultato è di segno opposto

LV

V OP

₁

OP

0

Ris

OP

₀

OP

₁

Ris

0 0

1 0 0 1

1 1

V

0 0

1 0

0 1

1 1 0 0 0

0 1 1 1 1

1 1 0 0 0 0 0 0 OP

₁

OP

₀

Ris

V

Esercizio 5: Calcolo di V alternativo

V vale 1 quando entrambi gli operandi hanno un segno e il risultato è di segno opposto

V OP

₁

OP

0

Ris

(16)

Esercizio 6

Progettare una ALU elementare a 4 bit che esegua le seguenti 3 funzioni sugli input A e B:

somma (C=A+B), differenza (C=A-B),

prodotto logico di A e B (C= A and B) a seconda del valore di due bit di controllo.

La ALU genererà anche i condition codes N (risultato negativo)

Z (risultato zero).

Esercizio 6: soluzione

Z

c₁ c₀

f0

c₃ c₂

a₂ b₂ a₁ b₁ a₀b₀

a₃b₃

F.A.

a3b3

f1 f1

a2 b2 a1b1

f1 f1

a0b0

N

F.A. F.A. F.A.

^{b se f}/b se f⁰₀^=0,=1 a+b se f₀=0, a+/b+1 se f₀=1

MUX MUX MUX

MUX

(17)

Esercizio 7

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

Dati due numeri X e Y, il confrontatore produce due uscite:

X>Y

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

Esercizio 7: soluzione

Possiamo usare un confrontatore a 2 bit per confrontare i bit meno significativi dei due numeri, e considerare separatamente il bit più significativo.

Guardando il MSB capiamo il segno di ciascun numero.

Se i numeri sono di segno opposto è chiaramente maggiore quello che ha MSB = 0

Se i numeri sono entrambi positivi o nulli (MSB=0) il risultato del confrontatore (che riguarda i valori assoluti dei due numeri) è corretto.

Se i due numeri sono entrambi negativi, il risultato del confrontatore (che riguarda i valori assoluti dei due numeri) e corretto.

Infatti maggiore è la parte positiva, maggiore è il numero. Si ricordi che tra due numeri in complemento a due rappresentati sullo stesso numero di bit e entrambi negativi il maggiore e quello che ha la parte positiva più grande.

(18)

Esercizio 7: soluzione

A>B A=B A<B A0

B0 A1 B1 Y2

Y1 Y0

COMP U0 U1 U2 U3 I0I1

DEC X2

X1 X0

X > Y

X = Y A>B, entrambi

positivi

X0, Y<0

A=B e numeri dello stesso segno MSB

MSB

A>B, entrambi negativi

Esercizio 8

Abbiamo visto a lezione come costruire un sommatore a N bit con con N full Adders.

Mettiamo di voler costruire un circuito che somma il numero 4 ad un dato numero a 12 bit

Una soluzione banale consistre usare 12 Full Adders:

Trovare una soluzione ottimizzata.

000000000100

A

12 12

12

Rip

HA HA HA HA

HA HA HA HA HA HA