Logiche e reti logiche

VHDL

linguaggi di questo tipo più diffusi sono essenzialmente due, e

Verilog, che differiscono per la sintassi utilizzata. Per gli esempi in

questo episodio userò Verilog, di cui potete trovare un compilatore

libero qui: https://github.com/steveicarus/iverilog.

In un HDL, ogni blocchetto hardware è chiamato modulo. Alcuni

moduli, come le porte and, or, not e altre, sono incorporate nella

sintassi del linguaggio. A partire da quei moduli possiamo

descrivere circuiti più complessi. Per esempio, in Verilog possiamo

descrivere il circuito in Figura 1 con il codice in Listing 1.

Osservate che alla Linea 1 abbiamo definito il nome del nostro

modulo, “example”, inserendo come parametri le variabili che

indicano gli input e l’output del circuito, e alle Linee 2 e 3 abbiamo

specificato quali dei parametri indicano gli input e quale l’output.

Logica e Reti Logiche 109

Nel circuito in Figura 1 l’output della porta not è uno degli input

della porta and e l’output della porta and è uno degli input della

porta xor. Per specificare ciò senza ambiguità alla Linea 5 definiamo

w1 w2,

due nuove variabili, e di tipo WIRE, che serviranno a indicare

rispettivamente l’output della porta not e l’output della porta and.

Infine, nelle Linee 7, 8 e 9 specifichiamo quali sono gli input e gli

output delle tre porte logiche del circuito. Si noti che il primo dei

parametri indica sempre l’output della porta, i successivi parametri

gli input.

Esercizio 16.2. Scrivere un modulo Verilog per il circuito seguente

Una volta definito un modulo, possiamo poi richiamarlo per

costruire altri moduli più complessi. Per esempio, nel Listing 2

definiamo prima un Half Adder e poi definiamo un Full Adder

costruendolo con due Half Adder e una porta or.

Si noti che quando abbiamo istanziato i due half adder, alle Linee

15 e 16, abbiamo anche specificato a cosa sono collegate le loro

.nome

porte di input e output (a,b,sum ,carry), usando la notazione

porta(espressione).

Logica e Reti Logiche 110

Esercizio 16.3. Disegnare il circuito corrispondente al modulo

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