Nessun titolo diapositiva

Aritmetica Binaria
8-11-2000
Somme tra numeri binari
Nei sistemi posizionali le cifre variano da 0 a B-1, la somma di due cifre
qualunque non supera 2B-2.
Al massimo il risultato e’ costituito da una cifra di ugual peso e da un
eventuale riporto di valore 1 sulla cifra di peso immediatamente superiore.
La presenza del riporto non altera questa proprietà, portando al massimo la
somma a 2B-1. Analoghe considerazioni valgono per la sottrazione.
Consideriamo il caso della somma di due bit:
0
0
0
1
0+
0+
1+
0=
1=
0=
----
----
----
0
1
1
1+
1=
---10
A
0
0
1
1
B
0
1
1
0
C Sum
0
0
0
1
1
0
0
1
Somma di due bit (Half Adder):
Sum = A + B
Half-Adder (HA)
Dalla sintesi della tabella della verità si ricava lo schema logico dell’ Half Adder (HA).
A
0
0
1
1
B
0
1
1
0
A
B
0
1
C Sum
0
0
0
1
1
0
0
1
0
0
1
C
A
B
1
1
0
Half Adder
(HA)
Sum
B
0
Sum = A’ · B + A · B’
1
0
0
1
0
C=A·B
0
1
Full-Adder (FA)
A
Full Adder
(FA)
B
Cout
Sum
Cin
Cin
0
0
0
0
1
1
1
1
A
0
0
1
1
0
0
1
1
B
0
1
1
0
0
1
1
0
Cout Sum
0
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
Somma di tre bit (Full Adder):
Sum = A + B + Cin
BA
Cin 00 01 11 10
1 0 1
0 0
1
1
BA
Cin 00
0 0
1
0
0
1 0
01 11 10
0 1 0
1 1
1
Sum = A’·B’·Cin + A·B’·Cin’ + A·B·Cin + A’·B·Cin’
Cout=A·Cin + B·Cin + AB
Generalmente il Full-Adder si realizza utilizzando due Half-Adder ed un OR come mostrato
nello schema seguente
Esempio di somma tra numeri binari:
FA
1 1 1 0 0 0 1
1 0 1 0 0 0 12 +
1 1 1 1 1 0 12 =
------------------------------
1 1 0 0 1 1 1 02
Sottrazioni tra numeri binari
A
0
0
1
1
B
0
1
1
0
B Diff
0
0
1
1
0
0
0
1
Differenza due bit:Diff = A - B
Bin
0
0
0
0
1
1
1
1
A
0
0
1
1
0
0
1
1
B
0
1
1
0
0
1
1
0
Bout Diff
0
0
1
1
0
0
0
1
1
1
1
0
1
1
0
0
Differenza di tre bit: Diff = A - B - Bin
Esempio di sottrazione tra numeri binari:
1 1 1 1
1 0 0 1 0 10 1 1 1 1 0=
-------------------------0 0 0 1 1 1
Progetto gerarchico
Un progetto gerarchico e' un progetto suddiviso su più livelli.
Ad ogni livello è associata una descrizione funzionale o una
struttura di blocchi interconnessi
I1
Livello 0
Z1
A
I2
Z2
I3
Livello 1
I1
I2
I3
Livello 2
Livello 3
B1
B2
Z1
Z2
Progetto di un sommatore a 4 Bit
Problema: progettare in modo gerarchico una rete che esegua la somma
di due numeri codificati con codice binario da 4 bit.
Soluzione:
Il primo passo è quello di descrivere lo schema in termini di segnali di
ingresso e uscita (“descrizione ai morsetti”). Tale livello di descrizione
corrisponde al livello gerarchico 0 (o ‘entity’).
Level 0 - “Entity”
X[0..3]
COUT
4 Bit
Full Adder
Y[0..3]
Z[0..3]
Level 1
Lo schema logico di livello 0 può’ essere ulteriormento scomposto in blocchi più
semplici, come mostrato nello schema logico seguente, utilizzando 4 Full-Adder a 1 Bit.
0
X0
Y0
Z0
1 BIT
FULLADDER
Z1
X1
Y1
1 BIT
FULLADDER
Z2
X2
Y2
1 BIT
FULLADDER
Z3
X3
Y3
1 BIT
FULLADDER
Cout
Level 2
Ogni Full-Adder ad 1 Bit è descrivibile mediante il seguente
schema logico utilizzando degli Half-Adder a 1 Bit.
X
y
1 Bit
Half
Adder
C
COUT
S
CIN
C
1 Bit
Half
Adder
Z
S
Level 3
Infine, gli Half-Adder utilizzati per realizzare i Full-Adder a 1 Bit
possono essere descritti mediante il seguente schema logico.
Questo è livello di descrizione più basso del nostro progetto.
X
Y
C
S
Schema logico di un Half-Adder.
Per l’inserimento del progetto all’interno del simulatore partiremo
da questo livello di descrizione e ripercorreremo la gerarchia fino
ad arrivare al livello 0.
Design Entry
Sintesi
(Compilazione)
Simulazione
Funzionamento
previsto ?
NO
SI
Trasferimento al Chip
(Target FPGA)
Aritmetica binaria: i numeri relativi
Nella rappresentazione binaria di numeri dotati di segno viene tipicamente usato
un bit per discriminare tra valori positivi e valori negativi. Dati n bit per la
rappresentazione il bit usato per il segno è quello più significativo (MSB, in
posizione n-1).
Rappresentazione Segno-Valore Assoluto (S-VA)
In questo rappresentazione al valore assoluto del numero viene prefisso un
bit per indicarne il segno.
Il valore 0 di questo bit codifica il segno più e il valore 1 il segno meno.
Esempio n=8:
+5710 = 001110012
segno
modulo
-5710 = 101110012
La rappresentazione S-VA è vantaggiosa per la sua semplicità ma
richiede circuiti complessi per l’esecuzione di somme algebriche.
Prima di eseguire una somma algebrica tra due operandi A e B e’
necessario determinare quale dei due e’ maggiore in valore assoluto.
 Se A e’ maggiore di B si esegue la differenza A-B e si assegna
al risultato il segno di A.
 Se A e’ minore di B si esegue la differenza B-A e si assegna al
risultato il segno di B
Osservazioni
Usando n bit (es. 8) per la codifica, il range di valori rappresentabili risulta:
[-2n-1-1..+2n-1-1]. Un bit (MSB) è usato per il segno.
(Con 8 bit sono rapresentabili valori nell’intervallo [-127 ..+127]).
Vi sono due configurazioni per lo zero (000000002 e 100000002 )
Poichè le operazioni vanno eseguite sulla sola parte di valore assoluto è
semplice la determinazione dell’overflow
Esempio di operazioni algebriche con rappresentazione S-VA
(23+ 16 )10
Stesso segno, si esegue la somma escludendo il bit più significativo. Entrambi gli operandi hanno lo
stesso segno ( bit 7 = 0 ), quindi il segno viene mantenuto ( bit 7 = 0 )
1
2310 +
1610 =
-----3910
00101112 +
00100002 =
-------------01001112
Risultato : +3910
001001112
( 22 - 17 )10
Il primo operando ha modulo maggiore del secondo ( |22| > |17| ) => si esegue la differenza tra
22 e 17. In questo caso il segno del risultato (5) è positivo e il bit 7 deve essere posto a 0.
1
2210 1710 =
-----510
00101102 00100012 =
-------------00001012
Risultato : +510
000001012
(8 - 16)10
Il secondo operando ha modulo maggiore ( |16| >|8| ) del primo.
Si esegue la differenza tra 16 e 8. Il segno e’ quello dell’operando di valore assoluto maggiore.
In questo caso il segno di 16 è negativo e il bit 7 deve essere posto a 1.
1
1610
810
-----810
00100002 00010002 =
-------------00010002
Risultato -810
100010002
(-112 - 39)10
Entrambi gli operandi di segno negativo => si sommano i valori assoluti.
11210
3910
-----15110
1
11100002 +
01001112 =
-------------100101112
Overflow. Sono necessari 8 bit per rappresentare 151 !
Usando la rappresentazione S-VA sono disponibili per il modulo solo 7 bit => (Overflow).
Rappresentazione in complemento a 2 (2’s C)
Dati n bit per la codifica del modulo e del segno:
la rappresentazione in complemento a 2 (2’s C) di un numero
si ottiene sommando (sottraendo nel caso di numeri negativi)
a 2n il numero codificato in valore assoluto ed eliminando
l’eventuale bit di riporto in posizione n;
- Con tale rappresentazione possono essere codificati i valori compresi
nell’intervallo [(2n-1-1), -2n-1].
- I numeri positivi restano inalterati
- I numeri negativi sono calcolabili partendo dal corrispondente valore
positivo, invertendo tutti i bit (complemento a 1, 1’s) e sommando 1
Esempio
Siano dati 3 bit (n=3) per la rappresentazione di numeri con segno
n=3
Con tale configurazione di bit potranno essere
codificati i numeri da +3 a -4, cioè [22-1,-22]
Bit 2
Bit 1
Bit 0
La rappresentazione in complemento a 2 (2’s C) si ottiene come segue:
si somma (o si sottrae) a 23 = 810 = 10002 la rappresentazione in valore
assoluto del numero che si vuole rappresentare in 2’s C,
Es +2: Per i numeri positivi si somma a 10002 il modulo del numero (|210|=0102).
Quindi +210 = 10002+0102 = x0102 in complemento a 2
Es -2: Per i numeri negativi si sottrae da 10002 il modulo del numero |210|=0102.
Quindi -210 = 10002-0102 = x1102 in complemento a 2
Rappresentazione in Segno e Valore Assoluto (S-VA) e Complemento a
2 (2’s C) di numeri con segno utilizzando 3 bit
Dec
S-VA
2's C
O
1
2
3
-4
-3
-2
-1
OOO
OO1
O1O
O11
???
111
11O
1O1
OOO
OO1
O1O
O11
1OO
1O1
11O
111
Interpretazione di un numero codificato in complemento a 2
La rappresentazione con segno e valore assoluto (S-VA) risulta più intuitiva ma meno potente
rispetto alla rappresentazione in complemento a 2 (2’s C).
Come interpretare un numero codificato in complemento a 2 ?
In una configurazione binaria di n bit codificata in complemento a 2, il bit più significativo (MSB in
posizione n-1) assume un peso negativo pari a -2n-1.
V10  2
n 1
n2
 d n 1   d i  2 i
i 0
I numeri positivi (dn-1=0) codificati in complemento a 2 rimangono inalterati.
Esempio: n=4
10112 in complemento a 2 equivale a:
10112 = -1·23 + 0·22 + 1·21 +1·20 = -8 + 0 + 2 +1 = -510
Mentre 01112 in complemento a 2 equivale a :
01112 = 0·23 + 1·22 + 1·21 +1·20 = 0 + 4 + 2 +1 = +710
di  0,1
Metodo opertivo per il calcolo del complemento a 2 di un numero
Nella rappresentazione in complemento a 2 i numeri positivi rimangono inalterati
mentre i numeri negativi possono essere ottenuti, dalla rappresentazione in
valore assoluto, invertendo tutti i bit (1’s C) e sommando 1.
Esempio n = 4
a) Rappresentare +510 in complemento a 2.
Soluzione
+ 510 = 01012
(rimane inalterato)
b) Rappresentare -510 in complemento a 2.
Soluzione
Si esprime il valore assoluto di –5 in binario. Si applica il complemento a 1 e si somma 1 a
risultato.
1’s
+1
510 = 0101 -> 10102 -> 10112 = -5
Propriètà
Applicando due volte
originale.
la regola del complemento a 2 si ottiene il numero
Esempio
n=4
-510 in complemento a 2 risulta 10112
Applicando nuovamente il complemento a 2 si ottiene il valore assoluto del
numero
1’s
+1
-5 -> 10112 -> 01002 -> 01012 = + 510
Propriètà
il complemento di una somma algebrica è uguale alla somma aritmetica dei
complementi
Vantaggi della rappresentazione in complemento a 2 rispetto alla
rapp. somma valore assoluto
- Vi è una sola rappresentazione per lo zero (00…000).
- Operativamente non vi e’ differenza nell’eseguire somme o sottrazioni
- Non e’ necessario individuare il maggiore, in valore assoluto, tra i due
operandi come nel caso della rappresentazione S-VA.
Per Esercizio
Utilizzando una rappresentazione a 4 bit calcolare
3
3
-1
3
+1
-1
-2
-7
= [0100]
= [0010]
= [1101]
= [1100]
Overflow
S-VA
Nel caso della rappresentazione con segno e valore assoluto (S-VA) la presenza di
eventuali situazioni overflow puo’ essere rilevata analizzando il bit di carry-out
relativo al bit più significativo del modulo.
2’s C
Nel caso di somme algebriche con numeri rappresentati in complemento a 2 la
rilevazione della condizione di overflow si ottiene controllando se il bit di carry-in e il
bit di carry_out relativi al bit più significativo (il bit n-1) della codifica sono diversi.
Questa operazione puo’ essere eseguita utilizzando l’operatore logico or-esclusivo.
Esempi: Con N=3 possono essere rappresentati i numeri tra [+3, -4] in 2’s C
3+3 = 6 (overflow)
2+1 = 3
-3-3 = -6 (overflow)
-3-1 = -4
-3+2 = -1
0 1 1
0 0 0
1 0 1
1 1 1
0 0 0
0 1 1+
0 1 0+
1 0 1+
1 0 1+
1 0 1+
0 1 1=
0 0 1=
1 0 1=
1 1 1=
0 1 0=
------------------
------------------
------------------
------------------
------------------
0 1 1 0
0 0 1 1
1 0 1 0
1 1 0 0
0 1 1 1
Progetto di un sommatore algebrico a 4 Bit
Problema: progettare in modo gerarchico una rete che esegua la somma
algebrica di due numeri di 4 bit codificati con segno e valore assoluto (S-VA).
La rete produce un risultato a 4 bit per cui è necessario segnalare eventuali
situazioni di overflow.
Level 0 - “Entity”
Segno X
X[0..2]
Segno Y
3
Somma
Algebrica
Overflow
3
3
Y[0..2]
S-VA
S-VA
Segno Z
Z[0..2]
Level 1
Lo schema logico dell’esercizio puo’ essere ulteriormente scomposto.In rosso sono
evidenziati i tipi di rappresentazione utilizzati per l’elaborazione delle informazioni
all’interno della rete.
Segno x
X[0..2]
C2’s
3
2
4
4
Segno y
4 Bit
Full Adder
Errore
4
C2’s
3
Overflow
Segno Z
C2’s
3
Y[0..2]
Z[0..2]
S-VA
2’s C
2’s C
S-VA
Level 2
La rete che calcola il complemento a 2 può essere ulteriormente decomposta
con due blocchi in cascata che, nel caso di numeri negativi, calcolano il
complemento a 1 e sommano 1.
La rete che somma 1 al numero in complemento a 1 puo’ essere ottenuta con
un FA a 4 bit nel quale uno degli operandi è 1 se il numero è negativo e 0 se il
numero è positivo.
Segno x
3
I[0..2]
C1’s
+1
4
S-VA
U[0..3]
4
2’s C
Level 3
Mentre la rete che calcola il complemento a 1 puo’ essere realizzata con
degli operatori di or-esclusivo.