Circuiti combinatori notevoli

In questa pagina 6

Blocchi combinatori (vedi Reti combinatorie e mappe di Karnaugh) che si ritrovano in ogni processore: nel datapath, nella ALU, nella decodifica degli indirizzi di memoria.

Multiplexer (MUX)

Formula (multiplexer 2:1). Sceglie uno tra $2^n$ ingressi dati in base a $n$ ingressi di selezione. MUX 2:1:

$Y = \overline{S}\,I_0 + S\,I_1$

Esempio. Con $I_0=0$ , $I_1=1$ e $S=1$ : $Y=\overline1\cdot0+1\cdot1=1$ .

Formula (multiplexer 4:1). MUX 4:1 con selezione $S_1S_0$ : $Y = \overline{S_1}\,\overline{S_0} I_0 + \overline{S_1}S_0 I_1 + S_1\overline{S_0} I_2 + S_1 S_0 I_3$ . Con un MUX a $2^n$ ingressi si realizza qualsiasi funzione di $n$ variabili, mettendo sugli ingressi dati i valori della tabella di verità. Un MUX a 32 bit sono 32 MUX in parallelo con la stessa selezione: nel datapath sceglie per esempio se il secondo operando dell'ALU è un registro o una costante.

Esempio. Con $S_1S_0=10$ resta solo il termine $S_1\overline{S_0}I_2$ , quindi $Y=I_2$ .

Decodificatore e codificatore

Definizione (decoder ed encoder)

Decoder $n \to 2^n$ : attiva una sola delle $2^n$ uscite, quella il cui numero è l'ingresso. Decoder 2→4: $D_0 = \overline{A_1}\,\overline{A_0}$ , $D_1 = \overline{A_1}A_0$ , $D_2 = A_1\overline{A_0}$ , $D_3 = A_1A_0$ . Usi: selezionare la cella di memoria o il chip dall'indirizzo, il registro di destinazione dal campo dell'istruzione.

Encoder $2^n \to n$ : l'inverso, dà il numero dell'unico ingresso attivo. L'encoder con priorità dà il numero dell'ingresso attivo più importante (usato per scegliere tra più richieste di interrupt).

Esempio. Decoder $2\to4$ con $A_1A_0=10$ : $D_2=1$ e $D_0=D_1=D_3=0$ .

Sommatori

Formula (semisommatore). Semisommatore (half adder): somma due bit.

$S = A \oplus B \qquad C = AB$

Esempio. Con $A=B=1$ : $S=1\oplus1=0$ e $C=1\cdot1=1$ , cioè $1+1=10_2$ .

Sommatore completo (full adder): somma due bit e il riporto in ingresso.

$A$	$B$	$C_{in}$	$S$	$C_{out}$
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

Formula (sommatore completo)

$S = A \oplus B \oplus C_{in} \qquad C_{out} = AB + C_{in}(A \oplus B) = AB + AC_{in} + BC_{in}$

Esempio. Con $A=B=C_{in}=1$ : $S=1$ e $C_{out}=1$ , cioè $1+1+1=11_2$ .

Formula (ritardo del sommatore a propagazione del riporto). Sommatore a propagazione del riporto (ripple carry) a $n$ bit: $n$ full adder in cascata, il $C_{out}$ di ognuno è il $C_{in}$ del successivo. Il bit $i$ è corretto solo quando è arrivato il riporto dal bit $i-1$ : il ritardo cresce linearmente con $n$ (circa $2n$ porte). Se una porta ritarda 20 ps, a 32 bit servono circa $64 \cdot 20 = 1280$ ps, cioè più di un ciclo di un clock a 1 GHz.

Esempio. A $16$ bit con porte da $20$ ps il ritardo è circa $2\cdot16\cdot20=640$ ps.

Definizione (anticipo del riporto). Anticipo del riporto (carry lookahead): si definiscono per ogni bit $g_i = A_iB_i$ (il bit genera un riporto) e $p_i = A_i + B_i$ (lo propaga), e si calcolano i riporti direttamente dagli ingressi:

$c_1 = g_0 + p_0c_0, \quad c_2 = g_1 + p_1g_0 + p_1p_0c_0, \quad \dots$

Esempio. Se $g_0=1$ (cioè $A_0=B_0=1$ ) allora $c_1=g_0+p_0c_0=1$ qualunque sia $c_0$ .

Più porte, ma ritardo che cresce circa come $\log n$ .

Sommatore-sottrattore

Proprietà (sommatore-sottrattore). Un solo sommatore fa anche la sottrazione in complemento a 2 (vedi Aritmetica binaria): ogni bit di $B$ passa per una XOR con il segnale $\text{SUB}$ , che è anche il riporto iniziale.

$\text{SUB} = 0$ : $B \oplus 0 = B$ , $c_0 = 0$ → $A + B$ .

$\text{SUB} = 1$ : $B \oplus 1 = \overline{B}$ , $c_0 = 1$ → $A + \overline{B} + 1 = A - B$ .

Esempio. A $4$ bit con $\text{SUB}=1$ : $0110-0011=0110+1100+1=(1)\,0011=3$ .

Formula (overflow in complemento a 2). Overflow (complemento a 2): $V = c_n \oplus c_{n-1}$ , XOR tra il riporto che entra e quello che esce dal bit di segno.

Esempio. A $4$ bit $0101+0100$ : il riporto entrante nel segno è $1$ , quello uscente $0$ , quindi $V=1$ .

Comparatore

Formula (comparatore di uguaglianza). Uguaglianza di due numeri di $n$ bit: $E = \overline{(A_0 \oplus B_0) + (A_1 \oplus B_1) + \dots}$ , cioè NOR delle XOR bit a bit. Il confronto di ordine si fa di solito con una sottrazione guardando i flag N, Z, C, V.

Esempio. Con $A=B=1010$ tutte le XOR valgono $0$ , quindi $E=1$ .

Errori tipici

Scrivere $S = A + B + C_{in}$ con il + dell'OR: la somma di un full adder è uno XOR a tre ingressi.
Pensare che il ritardo di un sommatore ripple non dipenda dal numero di bit.

Versione ripasso

Blocchi di Reti combinatorie e mappe di Karnaugh nel datapath, nella ALU, nella decodifica degli indirizzi.

MUX 2:1: $Y = \overline{S}\,I_0 + S\,I_1$ ; un MUX a $2^n$ ingressi realizza ogni funzione di $n$ variabili.
Decoder $n \to 2^n$ : attiva una sola uscita (2 $\to$ 4: $D_0 = \overline{A_1}\,\overline{A_0}$ , ..., $D_3 = A_1A_0$ ). Encoder $2^n \to n$ , con priorità per le richieste di interrupt.
Semisommatore: $S = A \oplus B$ , $C = AB$ . Sommatore completo: $S = A \oplus B \oplus C_{in}$ , $C_{out} = AB + C_{in}(A \oplus B)$ .
Ripple carry: $n$ sommatori in cascata, ritardo lineare (circa $2n$ porte; a 32 bit con 20 ps per porta $1280$ ps).
Anticipo del riporto: $g_i = A_iB_i$ , $p_i = A_i + B_i$ , $c_1 = g_0 + p_0c_0$ , $c_2 = g_1 + p_1g_0 + p_1p_0c_0$ ; ritardo circa $\log n$ .
Sommatore-sottrattore: XOR di $B$ con $\text{SUB}$ , che è anche il riporto iniziale (Aritmetica binaria): $A + \overline{B} + 1 = A - B$ . Overflow: $V = c_n \oplus c_{n-1}$ .
Comparatore: uguaglianza $E = \overline{(A_0 \oplus B_0) + (A_1 \oplus B_1) + \dots}$ ; l'ordine si ricava con una sottrazione.

Errori tipici: la somma del sommatore completo è uno XOR a tre ingressi; il ritardo del ripple cresce con i bit.