Appunti Logiche e reti logiche

HDL

“mycirc” descritto nel seguente codice

Le variabili che usiamo all’interno del codice possono anche essere

vettrici. Per esempio, possiamo descrivere in HDL un Multiplexer 2:1

come in Figura 1

Il modo di descrivere i circuiti che abbiamo visto finora si chiama

structural: specifica esattamente come è la struttura di un circuito.

Gli HDL consentono anche di descrivere un circuito in modo

behavioral, ossia specificandone la funzione. Per esempio, avremmo

potuto descrivere il multiplexer in Figura 1 anche nel modo

seguente

Logica e Reti Logiche 111

Si noti che con l’istruzione alla Linea 6 stiamo dicendo al

programma di assegnare a y il valore di x[1] se s = 1 e il valore di

x[0] se s = 0.

Esercizio 16.4. Descrivere in Verilog un Multiplexer 4:1, sia in

modo structural che in modo behavioral.

Paragrafo 16.2 Esercizi Svolti

Esercizio 16.2.1. disegnare il circuito corrispondente al modulo “mycirc”

descritto nel seguente codice HDL:

il circuito corrispondente:

Episodio 17. Lezione 14 dicembre 2023. Rif. Capitolo 5 libro.

Nello studio dei circuiti finora abbiamo sempre assunto che la

propagazione del segnale lungo i fili sia pressochè “istantanea”.

Tuttavia, sappiamo dalla fisica che nessun segnale può propagarsi

Logica e Reti Logiche 112

più velocemente della luce. Per quanto la velocità della luce sia

enorme 1 rispetto alle velocità con cui siamo abituati a confrontarci

quotidianamente, anche le frequenze di clock dei circuiti sono

enormi (3GHz o anche più).

Esercizio 17.1. Si consideri il semplice

circuito sequenziale qui sotto. Supponendo

che il segnale si propaghi da Q a D alla

5

velocità della luce (circa 3 · 10 km/s) e che

il clock del Flip-Flop sia a 3GHz (passa da 0

9

a 1 circa 3 · 10 volte al secondo), quanto

può essere lungo, al massimo, il cavo indicato dalla freccia affinché

il Flip-Flop lavori correttamente?

Devo garantire che il segnale arrivi in D prima che il clock sia

variato di stato. Al massimo deve essere lungo:

1

la velocità della luce, i cicli di clock al secondo. Il

5

3∗10 km/ s 9

3∗10

1 1

km= m=10 cm

risultato è 10

4

10

Paragrafo 17.1 Addizionatore/Sottrattore a propagazione di riporto

Quando abbiamo iniziato a parlare di circuiti abbiamo visto come sia

semplice, usando solo porte logiche elementari, costruire un

circuito, il Full-Adder (vedi Fig. 1), che faccia la somma di tre bit (a,

b e c ) restituendoci in output un bit che indica la somma e uno che

in

indica il riporto (s e c , rispettivamente).

out

Esercizio 17.2. Ricostruire un Full-Adder usando solo porte logiche

elementari

Logica e Reti Logiche 113

Mettendo in serie k Full-Adder, con k ∈ N, otteniamo quindi un

circuito che fa la somma in binario di numeri a k bit (vedi Fig. 2 per

un Adder a 4 bit).

Se si interpreta il bit c come il quinto bit della somma, allora il

out

circuito in Figura 2 calcola correttamente la somma di qualunque

coppia di numeri in binario a quattro bit (a , a , a , a ), (b , b , b , b )

3 2 1 0 3 2 1 0

restituendo di fatto un numero a cinque bit (c , s , s , s , s ).

out 3 2 1 0

Interpretando le sequenze di bit come numeri in complemento a

due, con una piccola modifica al circuito possiamo fare in modo che

lo stesso circuito calcoli sia la somma che la sottrazione fra numeri

in complemento a due a k bit, a seconda che il bit cin sia 0 oppure 1

(vedi Fig. 3 per un Adder/Subtractor a 4 bit).

Adder Adder/Subtractor

I circuiti e costruiti così si dicono a

propagazione di riporto. Osservate infatti, per esempio, che il Full-

Adder FA in Figura 3, per calcolare s deve ricevere il riporto in

3 3

uscita da FA che, per calcolarlo, a sua volta deve ricevere il riporto

2

in uscita da FA , che deve ricevere il riporto in uscita da FA .

1 0

Se la propagazione del segnale fosse istantanea non ci sarebbe

nessun problema, ma siccome i segnali non possono viaggiare più

veloce della luce, questo significa che in un Adder/Subtractor a 64

Logica e Reti Logiche 114

bit il segnale proveniente da c impiegherebbe, per arrivare

in

all’ultimo Full-Adder, il doppio del tempo di quanto ne

impiegherebbe in uno a 32 bit. Se il circuito Adder/Subtractor è un

componente di un circuito sequenziale, passare da 32 a 64 bit,

quindi, potrebbe costringerci a dover dimezzare la velocità del

clock. Quello visto fino ad ora è chiamato Full-Adder a propagazione

di riporto.

Paragrafo 17.2 Addizionatore/Sottrattore ad anticipo di riporto

Occorre trovare un circuito che migliori il nostro funzionamento. Si

consideri un addizionatore/sottrattore a 16 bit e immaginiamolo

diviso in 4 addizionatori a 4 bit

Chiamiamo c il riporto in ingresso dell’i-esimo Full-Adder (che è

i

uguale al riporto in uscita dell’(i−1)-esimo).

Per migliorare l’efficienza del circuito, in termini di velocità di

propagazione del segnale da c fino a c , possiamo provare a fare in

0 16

precomputare

modo di in ogni blocco di quattro bit qualcosa che ci

consenta di non dover far passare i bit dei vari riporti in ognuno dei

16 Full-Adder. Vediamo come fare, anche se gli input vengono

istanziati allo stesso momento.

Consideriamo il generico Full-Adder i-esimo, per i = 0, ..., 15 e

osserviamo che:

• Se a b = 1 allora il Full-Adder genera il bit di riporto c = 1

i i i+1

indipendentemente se il suo riporto in entrata c sia 0 o 1. In questo

i

caso incide sul risultato della somma e non sul riporto;

c s

i i

• Se a ⊕ b = 1 allora il Full-Adder propaga il bit di riporto: c = c .

i i i+1 i

in questo caso propaga il riporto che si ha in ingresso. Questo

c i

influenza l’uscita come detto.

In base alle nostre osservazioni precedenti, possiamo scrivere

.

⊕b

=a +(a )c

c b

i+1 i i i i i

Esercizio 17.3. Osservare che è equivalente a

⊕b

+(a )c

a b

i i i i i

+(a +b )

a b c

i i i i i

Logica e Reti Logiche 115

Sono equivalenti perché nel caso e lo XOR vale 0. Ma

=1 =1

a b

i i

abbiamo il primo mintermine che vale 1, quindi la nostra

affermazione è verificata. (generazione del riporto)

Se per comodità chiamiamo g = a b e p =

i i i i

a + b (propagazione del riporto), dall’esercizio precedente abbiamo

i i

che deve valere la relazione di ricorrenza (1)

=g +

c p c

i+1 i i i

Applicando la relazione precedente con i = 7 abbiamo, per esempio,

che il riporto in uscita dal secondo adder a 4-bit è , e

=g +

c p c

8 7 t 7

applicandola ricorsivamente con i = 6 abbiamo che

( )

=g + =g + + =g + +

c p c p g p c p g p p c .

8 7 7 7 7 7 6 6 6 7 7 6 7 6 6

Istanziando l’equazione di ricorrenza (1) con i = 7, 6, 5, 4 verificare

che si può scrivere il riporto c in uscita dal secondo adder a 4-bit in

8

funzione del riporto c in entrata nello stesso adder in questo modo

4

( )

( ) 7 7

( )

=g + =g + + + + =g + + + + = +

c p c p g p g p g p c p g p p g p p p g p p p p c A B c

8 7 7 7 7 7 6 6 5 5 4 4 4 7 7 6 7 6 5 7 6 5 4 7 6 5 4 4 4 4 4

Dove nell’ultima uguaglianza ho chiamato

+ + +

A=g p g p p g p p p g , B= p p p p c

7 7 6 7 6 5 7 6 5 4 7 6 5 4 4

Osservare che i due bit A e B dell’esercizio precedente sono funzioni

di (g , g , g , g ) e (p , p , p , p ) che a loro volta sono funzioni di (a ,

7 6 5 4 7 6 5 4 7

a , a , a ) e di (b , b , b , b ). Quindi A e B possono essere calcolate

6 5 4 7 6 5 4

nel secondo Adder a 4-bit senza dover aspettare l’arrivo di c .

4

Una volta precomputati A e B, nel momento in cui arriva il riporto in

entrata c l’adder a 4-bit può calcolare il riporto c in uscita usando

4 8

solo una porta and e una porta or

In questo modo, quando arriva il riporto in entrata c , che è

4

necessario ai quattro Full-Adder contenuti nell’Adder 1 per calcolare

(s , s , s , s ), l’Adder 1 può anticipare (ossia, calcolare tramite un

7 6 5 4

circuito più breve, che quindi richiederà meno tempo) il riporto c 8

Logica e Reti Logiche 116

all’Adder 2, che a sua volta lo userà per calcolare (s , s , s , s ) e

11 10 9 8

per anticipare c all’Adder 3.

12

Questo metodo consente di diminuire il tempo per propagare ed

eseguire l’operazione nel nostro circuito. Si osservi che questo

metodo di implementazione del circuito si usa nelle CPU moderne,

all’interno della ALU.

Esercizio 17.4. Progettare un circuito che prenda in input (g , g ,

7 6

g , g ) e (p , p , p , p ) e restituisca in output A e B.

5 4 7 6 5 4

Esercizio 17.5. Descrivere in un Hardware Description Language

un circuito che prenda in input (a , a , a , a ) e (b , b , b , b ) e

7 6 5 4 7 6 5 4

restituisca in output A e B. La procedura vista in questa sezione per

costruire un adder a 16 bit precomputando in ogni blocco a 4 bit ciò

che serve per propagare il riporto all’adder a quattro bit successivo

si può iterare: per esempio, per costruire un Adder a 64 bit si può

dividerlo in blocchi da 16 bit e precomputare ciò che serve per fare

in modo che il riporto si propaghi da un blocco al successivo senza

dover passare attraverso tutti i Full-Adder. Un circuito

Adder/Subtractor costruito in questo modo si chiama ad anticipo di

riporto.

Episodio 18. Lezione 18 dicembre 2023. Rif. Capitolo 5 libro.

Nell’Episodio 10 abbiamo visto come possiamo rappresentare con

sequenze di bit sia numeri positivi che numeri negativi utilizzando la

codifica in complemento a due, che è molto comoda per far

eseguire somme e sottrazioni a un circuito. Come possiamo

rappresentare invece i numeri frazionari con sequenze di bit? e i

caratteri alfabetici e gli altri simboli?

Paragrafo 18.1 Un primo tentativo n

Sappiamo che le sequenze distinte di n bit sono 2 , quindi, ognuna

n

di queste potrà rappresentare uno di 2 “oggetti” diversi. Abbiamo

Logica e Reti Logiche 117

visto che, se gli “oggetti” in questione sono i numeri interi senza

segno, con la codifica binaria standard usiamo quelle sequenze di

n

bit per indicare i numeri da 0 a 2 1. Se gli oggetti che vogliamo

−

rappresentare sono i numeri interi positivi e negativi, allora con la

codifica in complemento a due a n bit indichiamo i numeri interi da

n 1 n 1

2 a 2 1.

− −

− −

Per codificare i numeri frazionari, una prima idea potrebbe essere

quella di usare una parte dei bit per la parte intera e una parte dei

bit per la p