Post on 11-Oct-2018
09/03/2012 2
Sommario
• Rappresentazione dei numeri naturali (N)
• Rappresentazione dei numeri interi (Z)
– Modulo e segno
– In complemento a 2
• Operazioni aritmetiche
• Esercizi
3
Codifica delle informazioni
• Qualunque informazione (dato associato a un significato)
sia essa un numero, una data, una immagine, un suono,
prima di essere elaborata (memorizzata, trasformata,
comunicata) da un computer necessita di essere
rappresentata in forma digitale.
• Questo in quanto i computer si basano sul sistema binario
che comprende solo i numeri 0 e 1.
• Queste cifre sono chiamate bit (binary digit) .
Registro
I computer per rappresentare le informazioni utilizzano dei dispositivi
fisici detti registri che hanno numero fisso di cifre binarie.
Si è passati rapidamente da 8 a 16 a 32 a 64 bit…. ma il limite rimane!
• Un registro è un dispositivo elettronico per memorizzare le
informazioni
• Dal punto di vista tecnologico un registro è un insieme di n elementi
fisici bistabili, detti bit.
Registro
I computer per rappresentare le informazioni utilizzano dei dispositivi
fisici detti registri che hanno numero fisso di cifre binarie.
Si è passati rapidamente da 8 a 16 a 32 a 64 bit…. ma il limite rimane!
• Un registro è un dispositivo elettronico per memorizzare le
informazioni
• Dal punto di vista tecnologico un registro è un insieme di n elementi
fisici bistabili, detti bit.
Se si usa un numero prestabilito di cifre binarie (dovuto al fatto che i registri del computer hanno una dimensione prestabilita - n bit), si pone un limite al numero massimo di informazioni rappresentabili
Registro n=4 24= 16 configurazioni
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
000
001
010
011
100
101
110
111
Registro
Un registro formato da n bit è in grado di assumere 2n
configurazioni di stato diverse.
5 4 3 2 1 0 n=6 26= 64 configurazioni
Ciascun bit ha due configurazioni stabili possibili,
a cui per convenzione vengono associati i simboli 0 e 1
11
Per la rappresentazione si utilizza la conversione del numero
naturale in binario0
0
1
1
3
3
2
2
1
1 22.....222 xdxdxdxdxd N
N
N
N
N
N
I NUMERI NATURALI sono i numeri interi positivi:
0, 1, 2, 3, 4, 5, 6, …..
Rappresentazione dei numeri naturali
12
Il più piccolo numero codificabile è:
02020.....202020 01321 xxxxx NNN
Il più grande numero codificabile è:
01321 2121.....212121 xxxxx NNN
Se N=8, 0-255 ossia da 0 a (2N-1)
Se N=16, 0-65535 ossia da 0 a (2N-1)
Se N=32, 0-4.294.967.295 ossia da 0 a (2N-1)
Rappresentazione dei numeri naturali
13
La codifica esadecimale viene a
volte usata al posto della binaria
per ridurre spazio
Il numero binario viene
suddiviso in blocchi di 4 bits a
partire dal meno significativo
Ad ogni gruppo viene sostituito
il simbolo esadecimale
corrispondete
Decimale Binario Esadecimale
0 0000 0
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 5
6 0110 6
7 0111 7
8 1000 8
9 1001 9
10 1010 A
11 1011 B
12 1100 C
13 1101 D
14 1110 E
15 1111 F
Rappresentazione dei numeri naturali
14
Rappresentazione dei numeri naturali
• Esempi:
– codifica dei numeri da 0 a 7:
• bastano3 bit
• una possibile codifica che usa 4 bit
000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7
15
• Esempi:
– codifica dei numeri da 0 a 8:
• 3 bit non bastano
• una possibile codifica che usa 4 bit
0000 0
0001 1
0010 2
0011 3
0100 4
0101 5
0110 6
0111 7
1000 8
Rappresentazione dei numeri naturali
16
Per la codifica dei numeri da 0 a M
– Se M=2n-1
Servono n bit ove n= log 2 M
– Per M qualsiasi il più piccolo n
tale che 2n M
Esempio: M=1000
Se scelgo n=9 riesco a rappresentare 512
informazioni:, quindi non basta. n=10
(1024 informazioni) va bene
00000000 0
00000001 1
00000010 2
00000011 3
00000100 4
00000101 5
00000110 6
00000111 7
….. ….
11111111 127
Rappresentazione di M numeri naturali
18
I numeri interi o relativi sono rappresentati in modo analogo
a quanto fatto per i numeri senza segno, riservando 1 bit per
rappresentare il segno
Si sceglie il bit più significativo per il segno
Se il bit vale 1 allora il segno rappresentato è il –
Se il bit vale 0 allora il segno è il +
Il numero di bit utili per rappresentare il valore assoluto del
numero intero relativo è: N-1
Rappresentazione dei Numeri
Interi Modulo e Segno
19
Esempio: si voglia rappresentare il numero -5 con 8 bit
Il primo bit (quello più significativo) viene posto a 1 perchè il numero è negativo
gli altri 7 bit si calcolano con il metodo visto prima applicato al numero 5, ottenendo
0000101.
Dunque il numero binario che rappresenta -5 è: 10000101
Si rappresenta un intero mediante la rappresentazione separata del modulo e del
segno;
•qualunque sia il numero dei bit usati, quello più significativo rappresenta il segno
(0 +;1 -) (tale bit simbolico, non ha peso);
•I restanti (n-1) bit (che hanno un peso in funzione della posizione) rappresentano la
codifica binaria del modulo
Rappresentazione dei Numeri
Interi Modulo e Segno
20
Dunque se dispongo di N bit, è possibile rappresentare numeri
interi relativi il cui intervallo sarà:
-(2N-1-1…….+(2N-1-1)
Se N=8 ---> -127,….,0,….,+127.
Se N=16 ---> -32.767,….,0,….,+32.767.
Se N=32 ---> -2.147.483.647,….,0,….,+2.147.483.647.
NOTA: ci sono due
rappresentazioni
dello 0
Rappresentazione dei Numeri
Interi Modulo e Segno
Rappresentazione dei numeri
negativi in modulo e segno
• Con 3 bit avremo:
000 +0
001 +1
010 +2
011 +3
100 -0
101 -1
110 -2
111 -3
Problemi:
Il numero 0 ha due
rappresentazioni
Per l’operazione di
somma si deve tener
conto dei segni degli
addendi
0 0 1 0 + (+2)
1 0 1 1 = (-3)
1 1 0 1 (-5 ERRATO)
22
Dati due numeri binari in rappresentazione modulo e segno, le operazioni
di somma o di sottrazione dipendono dai segni
Se i segni sono gli stessi:
Si considerano tutti i bit meno quello del segno
Si sommano tali sequenze
Il numero binario risultante sarà ottenuto aggiungendo il bit di
segno ai bit ottenuti dalla somma.
Se i segni dei due numeri sono diversi:
Si considerano tutti i bit meno quello del segno
Si sottrae il numero più piccolo in valore assoluto dal numero più
grande
Il numero binario risultante sarà ottenuto aggiungendo ai bit ottenuti
dalla sottrazione il bit di segno del numero in valore assoluto più
grande.
Somme e Sottrazioni in Modulo
e Segno
Il principale problema della rappresentazione in Modulo e
segno è che le somme algebriche vanno eseguite in modo
diverso in dipendenza dal segno concorde o discorde dei due
operandi
Questo complica notevolmente la realizzazione delle operazioni
di somma e sottrazione a livello hardware.
Somme e Sottrazioni in Modulo
e Segno
24
Cosa è il complemento a 2 di un numero binario ?
Dato un numero binario X di N bit, si definisce
complemento a 2 di tale numero il numero Y che si ottiene
effettuando l’operazione 2N-X
Un modo semplice per calcolarlo si ottiene tramite il
seguente algoritmo: si invertono tutti i bit del numero (0 diviene 1, e viceversa)
si somma 1
Il Complemento a 2
25
Esempio: si determini il complemento a 2 del numero 10100.
Dalla definizione si ottiene: 100000-10100 =01100
Applicando il metodo si ha:
01011 +1
01100
Esempio: si determini il complemento a 2 del numero 01101001.
Dalla definizione si ottiene: 100000000- 01101001 =10010111
Applicando il metodo si ha:
10010110 +1
10010111
Il Complemento a 2
26
La rappresentazione in complemento a 2 di un numero intero su N bit, si effettua
nella seguente maniera:
i numeri interi positivi (incluso lo zero) sono rappresentati in modulo e segno
utilizzando gli N bit:
1 bit di segno (il MSB, pari a 0) e N-1 bit per la codifica
i numeri interi negativi sono rappresentati realizzando il complemento a 2 della
codifica binaria su N bit del valore assoluto del numero che si vuole
rappresentare
Rappresentazione dei Numeri
Interi in Complemento a 2
27
La rappresentazione in complemento a 2 di un numero intero su N bit, si effettua
nella seguente maniera:
i numeri interi positivi (incluso lo zero) sono rappresentati in modulo e segno
utilizzando gli N bit:
1 bit di segno (il MSB, pari a 0) e N-1 bit per la codifica
i numeri interi negativi sono rappresentati realizzando il complemento a 2 della
codifica binaria su N bit del valore assoluto del numero che si vuole
rappresentare
Rappresentazione dei Numeri
Interi in Complemento a 2
1. Si rappresenta in binario usando tutti i bit il valore assoluto del
numero negativo da codificare
2. Si effettua il complemento a due del numero binario ottenuto
• Si invertono tutti i bit in tale rappresentazione (0 1,1 0)
• Si somma uno al risultato ottenuto al passo precedente
28
Rappresentazione dei Numeri
Interi in Complemento a 2
Esempio: si voglia rappresentare il numero 1 con 8 bit
Essendo il numero positivo:
•Segno 0
•Codifica binaria su 7 bit di 1: 0000001
Codifica ottenuta: 00000001
Esempio: si voglia rappresentare il numero -1 con 8 bit
Essendo il numero negativo:
Codifica binaria del valore assoluto (1) su 8 bit 00000001
complemento a 2:
•11111110+1
• 11111111.
29
Esempio: si voglia rappresentare il numero 1 con 8 bit
Essendo il numero positivo:
•Segno 0
•Codifica binaria su 7 bit di 1: 0000001
Codifica ottenuta: 00000001
Esempio: si voglia rappresentare il numero -1 con 8 bit
Essendo il numero negativo:
Codifica binaria del valore assoluto (1) su 8 bit 00000001
complemento a 2:
•11111110+1
• 11111111.
Rappresentazione dei Numeri
Interi in Complemento a 2
30
Esempio Codifica in Complemento a 2 su 4 bit
Rappresentazione dei Numeri
Interi in Complemento a 2
31
Secondo questa rappresentazione non (completamente) posizionale le 2n
combinazioni di n bit vengono usate per denotare metà valori positivi (da 0 a
2n-1-1) e metà valori negativi (da -1 a -2n-1).
Si noti che in questa rappresentazione il bit più significativo ha peso -2n-1
anziché, come accade usualmente in binario puro, 2n-1.
Così, ad esempio, nella sequenza di bit 11110001 il bit più significativo ha
peso -128 anziché +128.
In questo modo:
quando il bit più significativo vale 0, la stringa di bit denota valori positivi, e
in particolare denota gli stessi valori che denoterebbe in binario puro, perché
il differente peso del MSB non ha influenza;
quando invece tale bit vale 1, la stringa denota valori negativi, e in particolare
il valore rappresentato si ottiene sommando il contributo negativo dell’MSB
con i contributi positivi degli altri bit.
Rappresentazione dei Numeri
Interi in Complemento a 2
32
Dato un numero in complemento a 2, la sua conversione in
decimale avviene tramite la formula:
Da questa formula si vede che il numero più piccolo che può
essere rappresentato con N bit è:
mentre il numero più grande è:
00
11
3N3N
2N2N
1N1N 2d2d....2d2d2d
1N2
1222....22 1N013N2N
Rappresentazione dei Numeri
Interi in Complemento a 2
33
Dunque se dispongo di N bit, è possibile rappresentare numeri
interi relativi il cui intervallo sarà:
-(2N-1)…….+(2N-1-1)
Se N=8 ---> -128,….,0,….,+127.
Se N=16 ---> -32.768,….,0,….,+32.767.
Se N=32 ---> -2.147.483.648,….,0,….,+2.147.483.647.
Codifica Numeri Interi
Complemento a 2
34
Esempio: si voglia convertire il numero binario in complemento a 2
00000001
Applicando la formula precedente , si ottiene che il numero decimale è 1.
Esempio: si voglia convertire il numero binario in complemento a 2
11111111
Applicando la formula
si ottiene che il numero decimale è dato dalla somma:
-1*27+1*26+1*25+1*24+1*23+1*22+1*21+1*20=
-128+64+32+16+8+4+2+1 =
-128+127=-1
00
11
55
66
77 2d2d....2d2d2d
00
11
55
66
77 2d2d....2d2d2d
Codifica Numeri Interi
Complemento a 2
35
Perchè la Rappresentazione in Complemento a 2 è più Conveniente ?
Il motivo più rilevante è relativo ai vantaggi ottenibili nell'esecuzione di
operazioni elementari come la somma e la sottrazione.
Queste due operazioni sono quelle che vengono più frequentemente
realizzate in un computer, e, dunque, un risparmio nel tempo necessario
alla loro esecuzione comporta un indiscusso aumento delle prestazioni di
un computer.
La codifica in complemento a 2 permette un notevole risparmio di tempo
nell'esecuzione di somme
Con la rappresentazione in complemento a 2 l’operazione di sottrazione
viene ricondotta alla somma previa complementazione dell’operando.
Confronto tra le Codifiche
Numeri Interi
36
Addizione…..già studiata
Le regole per realizzare l'addizione tra numeri binari:
0+0=0
0+1=1
1+0=1
1+1=0 con riporto di 1
Esempio: Sommare i numeri 0001 (1) e 1010(10).
0001+
1010=
_______
1011 (11)
Esempio: Sommare i numeri 0011 (3) e 1010(10).
0011+
1010=
_______
1101 (13)
37
Somme e Sottrazioni in
Complemento a 2
Dati due numeri binari in complemento a due, per la somma si
applicano le regole dell'addizione a tutti i bit compreso il bit
di segno.
Esempio: Si sommino i numeri a 4 bit 0010 (+2) e 1010 (-6).
0010+
1010=
______
1100 (-4)
Il numero binario risultante è già il risultato con il segno
giusto.
38
Somme e Sottrazioni in
Complemento a 2
Esempio: Si sommino i numeri in complemento a 2 001100
(+12) e 100000 (-32).
001100+
100000=
_______
101100 (-20)
Il numero binario risultante è già il risultato con il segno
giusto.
39
E’evidente la semplificazione nel calcolo della somma e
della sottrazione dei numeri rappresentati in complemento
a due.
Confronto tra le Codifiche
Numeri Interi
40
Primo caso
Si supponga di lavorare con codifica complemento a 2 su 4 bit (-8,…,+7)
si consideri la seguente operazione di somma in complemento a due:
1001 (-7) e 1111 (-1).
La somma in base 10 è -8 e rappresenta il limite inferiore codificabile con 4 bit
Eseguendo la somma tra le rappresentazioni dei numeri si ottiene:
1001+
1111=
_________
1 1000
l'operazione effettuata ha prodotto un risultato non contenibile nello spazio
predisposto in quanto è necessario un altro bit (l’1 a sinistra, ottenuto come riporto,
viene memorizzato nel CARRY FLAG per superamento della capacità del registro),
comunque il risultato ottenuto (1000 in complemento a 2 corrisponde a –8) è da
considerare corretto.
Riconoscimento Automatico di
un Risultato Corretto
41
Secondo Caso
Si supponga sempre di lavorare con codifica in complemento a 2 su 4 bit (-8,…,+7)Si consideri la seguente operazione di somma in complemento a due:
1001 (-7) e 1110 (-2).
In questo caso la somma -9 non è codificabile con 4 bit.
Eseguendo la somma si ottiene:
1001+
1110=
________
1 0111
l'operazione effettuata ha prodotto un risultato non contenibile nello spazio predisposto in
quanto è necessario un altro bit (l’1 a sinistra, ottenuto come riporto, viene memorizzato
nel CARRY FLAG per superamento della capacità del registro ), ma il risultato ottenuto
(0111 - in complemento a 2 corrisponde a +7) ) è da considerare errato!
Si ha Overflow.
Riconoscimento Automatico di
un Risultato Corretto
Quando la somma di due interi
produce come risultato un valore
esterno all’insieme dei valori
rappresentabili si dice che si è
verificato un “Overflow” e il risultato
ottenuto non è corretto;
Il Calcolatore non e in grado di
prevenire un errore di Overflow, in
quanto questo viene individuato solo
dopo aver effettuato l’operazione.
42
Terzo Caso
Si supponga di lavorare ad 8 bit (-128,….,+127)
Si consideri la seguente operazione di somma in complemento a due:
01111110 (126) e 00000011 (3).
In questo caso la somma (129) è superiore al numero massimo positivo codificabile in
complemento a due. con 8 bit
Eseguendo la somma, si ottiene:
01111110 +
00000011 =
____________
10000001
l'operazione effettuata ha prodotto un valore contenibile nello spazio predisposto ma il
risultato ottenuto (10000001 - in complemento a 2 corrisponde a -127) ) è da considerare
errato!
Si ha Overflow.
Riconoscimento Automatico di
un Risultato Corretto
Quando la somma di due interi
produce come risultato un valore
esterno all’insieme dei valori
rappresentabili si dice che si è
verificato un “Overflow” e il risultato
ottenuto non è corretto;
Il Calcolatore non e in grado di
prevenire un errore di Overflow, in
quanto questo viene individuato solo
dopo aver effettuato l’operazione.
43
Per capire se il risultato che è stato ottenuto sia valido o meno, osservando i casi
precedenti basta controllare i bit più significativi dei numeri da sommare ( X e Y ) e
della somma ( S ) ottenuta.
Se i bit più significativi dei numeri da sommare ( X e Y ) sono diversi non potrà
verificarsi mai l’overflow e il risultato sarà sempre da considerarsi corretto.
Se i bit più significativi dei numeri da sommare ( X e Y ) sono uguali e il bit più
significativo della somma ( S ) è diverso da essi allora ci sarà overflow e il risultato
dovrà essere considerato errato.
Nella CPU esiste un registro (detto registro di stato - PSW) dove ciascuno dei bit che lo compongono ha un
significato autonomo che indica (flag) se nel corso dell'ultima operazione eseguita si è verificato un determinato
evento.CF=1: Carry Flag o flag del riporto. Indica se l'operazione effettuata ha generato un riporto.
OF=1: Overflow Flag. Indica se nell'operazione effettuata si è verificato un errore di overflow (risultato non rappresentabile
nello spazio predisposto).
PF = 1 se il risultato di un’operazione ha un numero pari di bit ad uno;
ZF = 1 quando il risultato di un’operazione è pari a zero;
SF = 1 indica il segno associato al risultato, in questo caso negativo;
……………
In caso di risultato errato viene impostato a 1 il flag di overflow (OF)
Riconoscimento Automatico di
un Risultato Corretto
44
Esempio: Siano dati i numeri a 4 bit 0010 (+2) e 1010 (-6).
0010+
1010=
_______
1100 (-4)
OF=0, ossia il risultato S è valido, perché i bit più
significativi di X e Y sono diversi.
Riconoscimento Automatico di
un Risultato Corretto
45
Esempio: Siano dati i numeri a 8 bit 01111110 (+126) e
00000011 (+3)
01111110+
00000011=
___________
10000001
OF=1, ossia il risultato S NON è valido, perché i bit più significativi di X
e Y sono uguali e il bit più significativo di S NON è uguale a loro.
Riconoscimento Automatico di
un Risultato Corretto
46
Esempio: si consideri la seguente operazione di somma in
complemento a due:
1001 (-7) e 1111 (-1).
Eseguendo la somma, il calcolatore ottiene:
1001+
1111=
_________
1 1000 (-8)
OF=0, ossia il risultato S è valido, perché i bit più
significativi di X e Y sono uguali e il risultato ha il bit più
significativo uguale ad essi.
Riconoscimento Automatico di
un Risultato Corretto
47
Esercizi
1. Data una rappresentazione in complemento a due con 16 bit
quanti numeri interi positivi e negativi si possono
rappresentare?
2. Effettuare la sottrazione tra il numero decimale 22 e il
numero decimale 33 rappresentati prima in binario con
modulo e segno e poi rappresentati in binario in
complemento a 2.
3. Determinare la rappresentazione in complemento a 2 del
numero decimale -10 con 5 e 12 bit.
48
Esercizi
• Fare la somma dei numeri binari in complemento a 2
codificati su n = 8 bit che corrispondono ai numeri decimali 16
e – 42
• Fare la somma dei numeri binari in complemento a 2
codificati su n = 6 bit che corrispondono ai numeri decimali -5
e –28
49
Esercizi
Si ordinino in modo decrescente i seguenti numeri:
• N1= - 113 in base 10
• N2 = 0100 0111 in base 2
• N3 = 43 in base 16
Quanti bit occorrono per rappresentare N3 ed N1 in
complemento a 2?
Eseguire in complemento a 2 (mostrando i passaggi, indicando
esplicitamente se si verifica overflow e motivando la risposta) le
operazioni:
• N1 + N2
• N1 - N3.