24/10/2002
Codifica dati e istruzioni
¾ Algoritmi
= istruzioni + dati.
scrivere un programma che descriva un
algoritmo è necessario rappresentare
istruzioni e dati utilizzando un formato che il
calcolatore sia in grado di:
¾ Per
Lezione 9
Codifica dell’informazione
• Memorizzare
• Elaborare
• Trasmettere
24/10/2002
Codifica dati e istruzioni
¾
Alfabeto dei simboli
¾
¾
• Esempio: 1.234,5 è la rappresentazione di un numero reale.
• Esempio: 1,23,45 non lo è.
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
¾
¾
¾
3
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
4
Codifica binaria dell’informazione
Il calcolatore utilizza un alfabeto binario: usiamo
dispositivi elettronici digitali in grado di assumere due
solo stati: acceso/spento, ON/OFF, 1/0, VERO/FALSO.
Un alfabeto binario non limita le funzionalità di un
calcolatore.
Il simbolo o cifra binaria si indica con bit (da Binary
digIT): quantità d’informazione che si ottiene
selezionando una configurazione da un insieme che ne
contiene due.
La risposta SI oppure NO a una domanda porta 1 bit
di informazione.
24/10/2002
Lo stesso alfabeto può essere utilizzato con codici
diversi:
• 123,456 = 1 x 102 + 2 x 101 + 3 x 100 + 4 x 10-1 + 5 x 10-2 + 5 x 10-3
(IT)
• 123,456 = 1 x 105 + 2 x 104 + 3 x 103 + 4 x 102 + 5 x 101 + 5 x 100
(UK)
Codifica binaria dell’informazione
¾
Codice (semantica): insieme di regole che ad ogni
configurazione ammissibile associa un’entità di
informazione
• 1.234,5 = 1 x 103 + 2 x 102 + 3 x 101 + 4 x 100 + 5 x 10-1
• 1,23,45 = ?
Regole di composizione (sintassi) che definiscono
le sequenze di cifre (parole) ammissibili:
24/10/2002
2
Codifica dati e istruzioni
• Esempio: cifre 0,1
• Esempio: cifre 0,1, 2, …, 9, separatore decimale (,),
separatore delle migliaia (.), segno positivo (+) e
negativo (-).
¾
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
¾ Il
calcolatore tratta diversi tipi di dati (numeri,
caratteri, ecc.) tutti rappresentati con la
codifica binaria.
¾ Problema: assegnare un codice univoco a tutti
gli oggetti compresi in un insieme predefinito.
¾ Esempio: associare un codice binario ai giorni
della settimana.
5
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
6
1
24/10/2002
Codifica binaria dell’informazione
Codifica binaria dell’informazione
¾ Quanti
oggetti diversi posso codificare con
parole binarie composte da k bit?
¾ Se
passiamo da una parola binaria di k bit ad
una parola di k+1 bit si raddoppia il numero di
oggetti che si possono rappresentare (2k+1).
• 1 bit: 21 = 2 stati (0, 1) ⇒ 2 oggetti
• 2 bit: 22 = 4 stati (00, 01, 10, 11) ⇒ 4 oggetti
• 3 bit: 23 = 8 stati (000, 001, 010, 011, 100, 101,
110, 111) ⇒ 8 oggetti
•…
• k bit: 2k stati ⇒ 2k oggetti
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
7
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Definire un codice
Codifica binaria dell’informazione
¾ Quanti
bit mi servono per codificare N oggetti:
¾Identificare due insiemi:
• Insieme delle configurazioni ammissibili;
• Insieme degli oggetti da rappresentare.
¾Associare gli elementi dei due insiemi
• N ≤ 2k ⇒ k ≥ log2 N ⇒ k = log2 N
¾ Ipotesi
implicita: le parole di un codice hanno
tutte la stessa lunghezza.
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
8
9
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Esempio
10
Esempio
¾ Associare
una codifica binaria ai giorni della
settimana.
¾ Quanti bit devono avere le parole binarie usate
per identificare i giorni della settimana
(7 oggetti diversi)?
111
110
101
Insieme delle configurazioni ammissibili
010
001
011
100
000
MAR
LUN
• k = log2 7 = 3
MER
VEN
GIO
SAB
DOM
Insieme degli oggetti da codificare
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
11
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
12
2
24/10/2002
Esempio
111
110
010
¾
001
011
101
Byte
100
Codice
¾
¾
000
¾
MAR
LUN
¾
MER
VEN
¾
GIO
SAB
24/10/2002
¾
DOM
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
13
24/10/2002
Codifica binaria dei caratteri
¾ Quanti
•
•
•
•
•
sono gli oggetti da rappresentare?
¾
¾
circa 120 oggetti complessivi
⇒ k = log2 120 = 7.
¾
15
Codifica binaria delle istruzioni
sono le istruzioni da codificare?
¾ Quanti bit devono avere le sequenze di bit
(parole binarie) usate per identificare le
istruzioni?
¾ Quale codifica (codice operativo) assegnare alle
sequenze di bit che rappresentano le istruzioni?
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Codice ASCII (American Standard Code for
Information Interchange) utilizza 7 bit
⇒ può rappresentare 27 = 128 caratteri detti caratteri
ASCII Standard.
Codice ASCII esteso utilizza 8 bit (1 Byte)
⇒ può rappresentare 28 = 256 caratteri detti caratteri
ASCII estesi.
Codice UNICODE utilizza 16 bit (2 Byte)
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
16
Codifica binaria delle istruzioni
¾ Quante
24/10/2002
14
• Tale codice comprende i caratteri ASCII standard e alcuni
caratteri semigrafici (cornici, lettere nazionali, simboli
matematici, ecc.)
¾ Totale
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Codifica binaria dei caratteri
26 lettere maiuscole
26 lettere minuscole
10 cifre
Circa 30 simboli d’interpunzione (, ; …)
Circa 30 caratteri di controllo (EOF, CR, …)
24/10/2002
bit rappresenta 2 stati: 0 oppure 1.
Byte rappresenta 8 bit ⇒ 28 = 256 stati
KiloByte [KB] = 210 Byte = 1024 Byte ≈ 103 Byte
MegaByte [MB] = 220 Byte = 1048576 Byte ≈ 106 Byte
GigaByte [GB] = 230 Byte ≈ 109 Byte
TeraByte [TB] = 240 Byte ≈ 1012 Byte
…
¾
Esempio: Insieme delle istruzioni composto da 11
istruzioni:
•
•
•
•
•
•
•
•
•
•
•
17
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
NOP
LOAD
STORE
ADD
SUB
MUL
DIV
BRANCH
JUMP
FUNC_CALL
RETURN
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
18
3
24/10/2002
Codifica binaria delle istruzioni
¾ Servono
k = log2 11 = 4 bit:
ISTRUZIONE
24/10/2002
Codifica binaria delle istruzioni
NOP
CODICE
OPERATIVO
0000
LOAD
STORE
ADD
SUB
MUL
DIV
BRANCH
JUMP
FUNC_CALL
RETURN
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
¾
Oltre al codice operativo è necessario fare riferimento
ai dati necessari per l’esecuzione dell’istruzione.
• Esempio ADD ha bisogno che sia specificato dove leggere i
due dati da sommare (operandi sorgente) e dove scrivere il
risultato (operando destinazione)
¾
Il numero dei dati da specificare è variabile, in
funzione delle istruzioni. Esempio:
• NOP
• JUMP R1
• ADD R1, R1, R2
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
19
24/10/2002
¾
REGISTRO
INDIRIZZO
REGISTRO
INDIRIZZO
¾
R0
0000
R8
1000
¾
R1
R2
R3
R4
0001
0010
0011
0100
R9
R10
R11
R12
1001
1010
1011
1100
R5
R6
R7
0101
0110
0111
R13
R14
R15
1101
1110
1111
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
21
NOP
JUMP R1
ADD R1, R1, R2
24/10/2002
Notazione posizionale
¾
¾
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Registro 1
Registro 2
Registro 3
20
0000
1000
0001
0011
0001
0001
0010
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
22
Notazione posizionale
Consideriamo i numeri interi assoluti (numeri naturali
più lo zero).
Notazione posizionale in base b:
Alfabeto: ci ∈ {0 … b-1}
ck ck-1 … c1 c0 rappresenta:
N = ck x bk + ck-1 x bk-1 + … + c0 x b0 =
Σ(i=0… k) ci x b i
c0 bit meno significativo
ck bit più significativo
24/10/2002
Registro 1
Codice operativo
Esempio
Esempio: Banco di registri (Register File) composto da
16 registri (R0, R1, …, R15)
⇒ servono k = log2 16 = 4 bit:
24/10/2002
Codice operativo
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Codifica binaria delle istruzioni
¾
Codice operativo
¾ Basi più frequentemente utilizzate:
base 2 : ci ∈ {0 , 1}
base 8: ci ∈ {0 , 1, 2, 3, 4, 5, 6, 7}
base 10: ci ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
base 16:
ci ∈ { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
23
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
24
4
24/10/2002
Conversione binario ⇒ decimale
Codifica binaria
¾ Numeri
binari: base b = 2
binario: cifre ci ∈ {0 , 1}
¾ (ck … c1 c0)2 rappresenta: N = Σ(i=0… k) ci x 2 i
¾ Alfabeto
¾ Dato
il numero N espresso in base 2, basta
riscriverlo secondo la notazione posizionale
utilizzando cifre e potenze della base 10.
¾ Esempi:
N = 11012
N = 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 1310
N = 1001012
N = 1 x 25 + 0 x 24 + 0 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 3710
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
25
Conversione decimale ⇒ binario
¾ Si
calcolano i resti della divisione per due finché
il risultato di una divisione diventa zero:
¾ Esempio: N = 2310
23 : 2 = 11
11 : 2 = 5
5:2=2
2:2=1
1:2=0
resto
resto
resto
resto
resto
R0
R1
R2
R3
R4
=
=
=
=
=
b0
b1
b2
b3
b4
=
=
=
=
=
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
26
Conversione decimale ⇒ binario
¾ Esempio:
N = 1810
18 : 2 = 9
9:2=4
4:2=2
2:2=1
1:2=0
1
1
1
0
1
resto
resto
resto
resto
resto
R0
R1
R2
R3
R4
=
=
=
=
=
b0
b1
b2
b3
b4
=
=
=
=
=
0
1
0
0
1
1810 = 100102
2310 = 101112
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
27
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
28
Conversione ottale ⇒ decimale
Codifica ottale
¾ Utile
per rappresentare sinteticamente i valori
binari.
¾ Numeri ottali: base b = 8
¾ Alfabeto ottale: cifre ci ∈ {0 , 1, 2, 3, 4, 5, 6, 7}
¾ (ck … c1 c0)8 rappresenta: N = Σ(i=0… k) ci x 8 i
¾
¾
Dato il numero N espresso in base 8, basta riscriverlo
secondo la notazione posizionale utilizzando cifre e
potenze della base 10.
Esempi:
N = 3548
N = 3 x 82 + 5 x 81 + 4 x 80 = 192 + 40 + 4 = 23610
N = 14618
N = 1 x 83 + 4 x 82 + 6 x 81 + 1 x 80 = 512 + 256 + 48 +1
= 81710
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
29
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
30
5
24/10/2002
Conversione decimale ⇒ ottale
Conversione ottale ⇒ binario
¾ Si
calcolano i resti della divisione per otto
finché il risultato di una divisione diventa zero:
¾ Esempio: N = 149210
1492 : 8 = 186
186 : 8 = 23
23 : 8 = 2
2:8=0
resto
resto
resto
resto
R0
R1
R2
R3
=
=
=
=
b0
b1
b2
b3
=
=
=
=
¾ Ogni
cifra ottale corrisponde a tre cifre binarie:
0 [000], 1 [001], 2 [010], 3 [011]
4 [100], 5 [101], 6 [110], 7 [111]
¾ E’ sufficiente ricordarsi (o derivare) la
rappresentazione binaria dei numeri da 0 a 7.
Esempio: N = 3548
[011] [101] [100] = 0111011002
4
2
7
2
149210 = 27248
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
31
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Conversione binario ⇒ ottale
32
Codifica esadecimale
¾ Suddividere
le cifre binarie (partendo da destra
verso sinistra) tenendo conto che tre cifre
binarie corrispondono a una cifra ottale
N = 0111011002
[011] [101] [100] = 3548
¾ Utile
per rappresentare sinteticamente i valori
binari.
¾ Numeri esadecimali: base b = 16
¾ Alfabeto esadecimale:
cifre ci ∈ { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}
¾ (ck
… c1 c0)16 rappresenta: N=Σ(i=0… k) ci x 16 i
N = 11001110012
[1] [100] [111][001]= 14718
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
33
Conversione esadecimale ⇒ decimale
¾
¾
24/10/2002
¾ Si
calcolano i resti della divisione per sedici
finché il risultato di una divisione diventa zero:
¾ Esempio: N = 149210
N = EC16
N = 14 x 161 + 12 x 160 = 224 + 12 = 23610
1492 : 16 = 93
93 : 16 = 5
5 : 16 = 0
N = 33116
N = 3 x 162 + 3 x 161 + 1 x 160 = 768 + 48 + 1 = 81710
149210 = 5D416
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
34
Conversione decimale ⇒ esadecimale
Dato il numero N espresso in base 16, basta
riscriverlo secondo la notazione posizionale utilizzando
cifre e potenze della base 10.
Esempi:
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
35
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
resto R0 = b0 = 4
resto R1 = b1 = 13 (D)
resto R2 = b2 = 5
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
36
6
24/10/2002
Conversione esadecimale ⇒ binario
¾
¾
Conversione binario ⇒ esadecimale
Ogni cifra esadecimale corrisponde a quattro cifre
binarie:
0 [0000], 1 [0001], 2 [0010], 3 [0011]
4 [0100], 5 [0101], 6 [0110], 7 [0111]
8 [1000], 9 [1001], A[1010], B [1011]
C [1100], D [1101], E [1110], F [1111]
E’ sufficiente ricordarsi (o derivare) la rappresentazione
binaria su 4 bit dei numeri da 0 a 15.
N = 35416
[0011] [0101] [0100] = 0011010101002
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
37
¾ Suddividere
le cifre binarie (partendo da destra
verso sinistra) tenendo conto che quattro cifre
binarie corrispondono a una cifra esadecimale.
N = 0011010101002
[0011] [0101] [0100] = 35416
N = 11001110012
[11] [0011] [1001]= 33916
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Rappresentazione dei numeri interi
assoluti da 0 a 15 per diverse basi
Codifica binaria su n bit
¾ Con
una sequenza di n bit si possono
rappresentare 2n numeri interi assoluti da 0 a
2n-1.
¾ Esempio: n = 4 bit ⇒ 24 = 16 numeri interi
assoluti da 0 a 15.
¾ La lunghezza delle sequenze di bit adottate
stabilisce il massimo numero che può essere
rappresentato.
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Nb
39
24/10/2002
Codifica binaria su n+1 bit
passiamo da una sequenza di lunghezza n
bit ad una sequenza di n+1 bit si raddoppiano
i numeri che si possono rappresentare (2n+1).
¾ Esempio:
¾
¾
Base 8
Base 10
Base 16
0000
0
0
0
0001
1
1
1
0010
2
2
2
0011
3
3
3
0100
4
4
4
0101
5
5
5
0110
6
6
6
0111
7
7
7
1000
10
8
1001
11
9
9
1010
12
10
A
1011
13
11
B
1100
14
12
C
1101
15
13
D
1110
16
14
E
1111
17
15
F
8
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
40
Se raddoppiamo la lunghezza di una sequenza da
n bit a 2n bit i numeri che si possono rappresentare
aumentano esponenzialmente (22n)
Esempio:
• n = 4 bit ⇒ 24 = 16 numeri da 0 a 15.
• n = 8 bit ⇒ 28 = 256 numeri da 0 a 255.
• n = 4 bit ⇒
= 16 numeri da 0 a 15.
• n = 5 bit ⇒ 25 = 32 numeri da 0 a 31.
24
¾
¾
¾
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Base 2
Codifica binaria su 2n bit
¾ Se
24/10/2002
38
41
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
Esempio:
Con 32 bit si possono rappresentare 232 numeri
naturali da 0 a 232-1= 4 294 967 295 ≈ 4 x 109.
Con 64 bit si possono rappresentare 264 numeri
naturali da 0 a 264-1= 16 x 1018 = 1,6 x 1019
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
42
7
24/10/2002
Addizione binaria
Addizione binaria su n bit
¾ Addizione
binaria tra due bit (a + b):
oltre al bit di somma S occorre memorizzare il
bit di riporto R (carry):
24/10/2002
a
b
S
R
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
¾ Addizione
binaria tra due numeri interi assoluti
di lunghezza n bit:
• si allineano i due numeri in colonne da destra verso
sinistra (cioè partendo dal bit meno significativo);
• si eseguono le somme bit a bit da destra verso
sinistra considerando per ogni colonna (successiva
alla colonna corrispondente al bit meno
significativo) il riporto generato dalla colonna alla
sua destra
43
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Addizione binaria tra due bit
ai e bi con riporto in ingresso Ri
Esempio
¾4
24/10/2002
ai
bi
Ri
Si
Ri+1
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
bit: a = 0101 b = 0011
R
A
B
A+B
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
44
45
24/10/2002
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
510
310
810
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
46
Rappresentazione dei numeri
interi relativi (o con segno)
Overflow
¾ Se
si considerano due numeri interi assoluti
rappresentati su n bit ⇒ si verifica la
condizione di overflow ogni volta che il
risultato supera 2n-1
¾ Esempio 4 bit: a = 0101 b = 1011
R
A
B
A+B
24/10/2002
1
1
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
¾ Codifica
modulo e segno
¾ Codifica
in complemento a due
510
1110
1610
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
47
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
48
8
24/10/2002
Codifica modulo e segno
¾
Codifica modulo e segno
Soluzione: indicare il segno seguito dal valore
assoluto.
¾
• 1 bit per indicare il segno
(convenzione: 0 positivo e 1 negativo)
• Restanti (n-1) bit per rappresentare il modulo (o valore
assoluto) del numero
¾
Indispensabile indicare il numero n di bit utilizzati
• Esempio: 4 bit
¾
¾
¾
+610 = 0110ms –610 = 1110ms
Problema: ci sono 2 rappresentazioni dello zero:
• Esempio: 4 bit
24/10/2002
+010 = 0000ms –010 = 1000ms
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
49
Diverse interpretazioni della
codifica binaria su 4 bit
Rappres. numeri interi
assoluti
Rappr. numeri interi
relativi (modulo e segno)
0000
0
0
0001
1
1
0010
2
2
0011
3
3
0100
24/10/2002
4
5
5
6
6
0111
7
7
1000
8
-0
1001
9
-1
1010
10
-2
1011
11
-3
1100
12
-4
1101
13
-5
1110
14
-6
1111
15
-7
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
¾
¾
¾
¾
51
Complemento a due:
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
52
¾ Primo
metodo pratico per calcolare la
rappresentazione di –X a partire da quella di X:
• Effettuare il complemento di ogni bit di X e
aggiungere 1.
¾ Esempio:
4 bit
• +610 = 0110C2
• Complemento di tutti i bit: 1001C2
• Aggiungere 1: (1001 + 0001) = 1010C2 = -610
Ciò impedisce il bilanciamento tra numeri positivi e
negativi:
• 4 bit: zero + 7 numeri positivi (fino a 7) + 8 numeri negativi
(fino a –8).
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Alfabeto binario:
Codifica in complemento a due
Con una sequenza di n bit si possono rappresentare
con la codifica in complemento a due 2n numeri
interi relativi compresi nell’intervallo
da – 2n-1 a 2n-1-1.
Esempio: 4 bit ⇒ 16 numeri interi relativi da –8 a 7
Notare: c’è una sola rappresentazione dello zero:
24/10/2002
50
• Date le sequenze di n bit, per rappresentare il
numero X si utilizza il valore binario corrispondente a
2n + x
• Esempio:
• 4 bit +610 ⇒ 24 + 6 = 22 ⇒ [1] 0110 ⇒ 0110C2
• 4 bit -610 ⇒ 24 - 6 = 10 ⇒ [0] 1010 ⇒ 1010C2
• 4 bit: +010 = 0000C2 (mentre 1000C2 = -810)
¾
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
• Anche il segno è rappresentato da 0 o 1
• Indispensabile indicare il numero n di bit utilizzati
Codifica in complemento a due
¾
24/10/2002
Codifica in complemento a due
4
0101
0110
Con una sequenza di n bit si possono rappresentare
2n numeri interi assoluti da 0 a 2n-1.
Con una sequenza di n bit si possono rappresentare
con la codifica modulo e segno 2n-1 numeri interi
relativi compresi nell’intervallo
da – (2n-1 –1) a 2n-1-1.
Esempio:
• 4 bit ⇒ 16 numeri interi assoluti da 0 a 15
• 4 bit ⇒ 15 numeri interi relativi da –7 a 7
53
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
54
9
24/10/2002
Codifica in complemento a due
Codifica in complemento a due
¾ Data
la rappresentazione di un numero su n
bit, la rappresentazione dello stesso numero su
n+1 bit si ottiene aggiungendo a sinistra un bit
uguale al bit più significativo (operazione di
estensione del segno).
¾ Esempio:
¾ Secondo
metodo pratico per calcolare la
rappresentazione di –X a partire da quella di X:
• Partendo da destra verso sinistra, lasciare invariati
tutti i bit fino al primo 1 compreso, e
complementare tutti gli altri bit.
¾ Esempio:
4 bit
• Rappresentazione di –6 su 4 bit = 1010C2
• Rappresentazione di –6 su 5 bit = 11010C2
• Rappresentazione di –6 su 8 bit = 11111010C2
• +610 = 0110C2
• Gli ultimi due bit rimangono invariati __10
• Complementare gli altri 2 bit: 1010C2 = -610
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
55
24/10/2002
Diverse interpretazioni della
codifica binaria su 4 bit
Rappres. numeri
interi assoluti
Rappr. numeri interi
relativi (modulo e segno)
Rappr. numeri interi
relativi (complemento a due)
0000
0
0
0
0001
1
1
1
0010
2
2
2
0011
3
3
3
0100
4
4
4
0101
5
5
5
0110
6
6
6
0111
7
7
7
1000
8
-0
-8
1001
9
-1
-7
1010
10
-2
-6
1011
11
-3
-5
1100
12
-4
-4
1101
13
-5
-3
1110
14
-6
-2
1111
15
-7
-1
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
¾ In
entrambe le rappresentazioni (MS e C2) i
numeri positivi iniziano con 0, quelli negativi
con 1 (è come se il primo bit rappresentasse il
segno del numero).
57
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
58
Somma algebrica
¾ Maggiore
vantaggio della notazione in
complemento a due:
la sottrazione tra due numeri (a – b) si effettua
come somma algebrica a + (-b)C2.
¾ Esempi:
¾ Si
consideri l’operazione di somma algebrica di
due numeri interi di n bit dotati di segno e
rappresentati in complemento a due
¾ Il risultato dell’addizione è corretto, a patto che
cada nel campo dei valori rappresentabili
(-2n-1 ≤ N ≤ 2n-1 –1), pur di trascurare
l’eventuale riporto in uscita dal bit più
significativo.
4 – 6 = 4 + (-6)C2 = 0100 + 1010 = 1110 = (-2)C2
7 – 3 = 7 + (-3)C2 = 0111 + 1101 = [1]0100 = +4
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
56
Osservazioni
Osservazioni
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
59
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
60
10
24/10/2002
Esempi
¾
¾
¾
¾
¾
Overflow/underflow
¾ Il
segnale di riporto in uscita non è sufficiente
per indicare un overflow/underflow di una
somma algebrica di numeri interi con segno.
¾ Si ha superamento di capacità se:
2 + 3 = 0010 + 0011 = 0101 = 5
-5 - 2 = (-5)+ (-2) = 1011 + 1110 = [1]1001 = -7
-3 – (-7) = (-3)+ 7 = 1101 + 0111 = [1]0100 = +4
-7 – 1 = (-7)+ (-1) = 1001 + 1111 = [1]1000 = -8
+2 – (-3) = 2 + 3 = 0010 + 0011 = 0101 = +5
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
• Sommando due numeri positivi si ottiene un
risultato negativo (generazione di overflow)
• Sommando due numeri negativi si ottiene un
risultato positivo (generazione di underflow)
61
24/10/2002
Esempi
+ 4 = 0111 + 0100 = 1011 = -5 NO!
OVERFLOW!
¾ -4 - 6 = (-4)+ (-6) = 1100 + 1010 = [1]0110 =
6 NO! UNDERFLOW!
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
62
Rappresentazione dei numeri reali
¾7
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
¾
¾
63
Problema: per una rappresentazione esatta di molti
numeri di questo tipo sarebbe richiesto un numero di
cifre illimitato (esempio: 1/3 = 0,3333333…. Oppure π
=3,14159265359…)
Per rappresentare tali numeri con una sequenza di bit
di lunghezza finita a uso di un calcolatore è
necessario approssimare tali numeri con numeri
razionali con un numero di cifre decimali ridotto e
prefissato, ma comunque sufficiente a garantire il
grado di precisione richiesto.
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
64
Rappresentazione binaria in
virgola fissa
Rappresentazione dei numeri razionali
¾ Esempi:
¾ Rappresentazione
in virgola fissa
¾ Rappresentazione
in virgola mobile
(floating point)
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
• 0,10112 = 1 x 2-1 + 0 x 2-2 + 1 x 2-3 + 1 x 2-4=
0,5 + 0,125 + 0,0625 =0,687510
• 11,1012 = 1 x 21 + 1 x20 + 1 x 2-1 + 0 x 2-2 +
1 x 2-3 = 2 + 1 + 0,5 + 0,125 = 3,62510
65
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
66
11
24/10/2002
Rappresentazione binaria in virgola
mobile
Rappresentazione in virgola mobile
¾ Usata
spesso (anche in decimale) per
rappresentare numeri molto grandi o molto
piccoli (esempio 0,135 x 1056).
¾ Rappresentazione in virgola mobile:
N = ± M x b±e
N = s x M x 2e
¾ Rappresentazione della mantissa M in modulo e
segno: 1 bit per il segno s e m bit per la
mantissa M
¾ Rappresentazione dell’esponente e polarizzato:
n bit per l’esponente
• Mantissa: parte frazionaria compresa tra 0 e 1
• Esponente: numero intero (positivo, negativo o
nullo)
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
s (1 bit)
67
24/10/2002
adottate:
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
¾ Rappresentazione
in virgola mobile su 16-bit
del numero decimale 5,5 supponendo n =7,
m= 8 e bias = 64
• Rappresentazione binaria: (101,1)2
• Rappresentazione normalizzata: (1,011)2 x (1010)2
• Esponente polarizzato: (2)10 +(64)10 =(66)10 cioè
(000 0010)2 + (100 0000)2 = (100 0010)2
0 (1 bit)
69
24/10/2002
Overflow/underflow
rappresentazione in virgola mobile può dar
luogo a overflow(underflow) dell’esponente
quando il valore dell’esponente supera il
massimo (minimo) previsto dalla convenzione
adottata per la rappresentazione del numero
¾ Esempio: n = 7 bit ⇒ l’esponente non
polarizzato del numero originario può variare
tra –64 e +63.
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
100 0010 (7-bit)
0110 0000 (8-bit)
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
70
Rappresentazione in virgola mobile
¾ La
24/10/2002
68
Esempio
• Rappresentazione normalizzata della mantissa
secondo lo standard IEEE (Institute of Electrical and
Electronic Engineers): numero binario la cui parte
intera è sempre pari a 1 (nel campo degli m bit
della mantissa compare solo la parte frazionaria).
• Esponente polarizzato su n bit ottenuto
sommando all’esponente originario una costante
(bias) che lo renda sempre positivo (eliminando
quindi il segno dell’esponente)
24/10/2002
M (m-bit)
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Rappresentazione binaria in virgola
mobile
¾ Convenzioni
e (n-bit)
¾
¾
Standard IEEE 754 –1985 per uniformare la
gestione della rappresentazione dei numeri in virgola
mobile.
Quattro formati per la rappresentazione dei numeri
in virgola mobile:
• Formati base
• Singola precisione (32 bit)
• Doppia precisione (64 bit)
• Formati estesi
• Singola precisione
• Doppia precisione
71
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
72
12
24/10/2002
Esercizio
¾ Eseguire
•
•
•
•
•
•
Esercizio
le seguenti conversioni di base:
¾ Dato
che (79)10 = (142)b determinare il valore
della base b.
(92)10 ⇒ base 3
(92)10 ⇒ base 5
(523,5)10 ⇒ base 2
(523,5)10 ⇒ base 8
(101,11)2 ⇒ base 8
(101,12)3 ⇒ base 10
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
73
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Esercizio
Esercizio
¾ Scrivere
una tabella che esprima la codifica
binaria su 3 bit e le corrispondenti
rappresentazioni:
¾ Dati
i seguenti numeri decimali:
23456, 89765, 67489, 111, 121331, 11101100
•
•
•
•
• dei numeri interi assoluti;
• dei numeri interi relativi in MS;
• dei numeri interi relativi in C2.
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
75
Si
Si
Si
Si
trasformino
trasformino
trasformino
trasformino
24/10/2002
Esercizio
l'interpretazione, fornendone il
corrispondente valore in base 10 completo di
segno, del numero binario 11110 nei seguenti
casi:
base
base
base
base
2;
3;
5;
7.
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
76
¾ Calcolare
il numero minimo di bit necessari per
codificare 48.000.000 informazioni utilizzando
un alfabeto binario.
• Numeri interi assoluti;
• Numeri interi relativi in MS;
• Numeri interi relativi in C2.
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
in
in
in
in
Esercizio
¾ Dare
24/10/2002
74
¾ Calcolare
il numero minimo di bit necessari per
codificare 13 623 235 informazioni utilizzando
un alfabeto binario.
77
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
78
13
24/10/2002
Esercizio
Esercizio
¾ Dato
il valore in modulo e segno -77, fornirne
la codifica binaria in complemento a 2
utilizzando il minor numero di bit e ipotizzando
che il valore fornito (il valore -77) sia espresso
nelle seguenti basi:
¾ Dati
i seguenti numeri:
• (23456)7, (12345)5, (2767)8, (1100)10, (C2CF)16
Convertire ciascuno in decimale e in binario.
• Base 8
• Base 10
• Base 16
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
79
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
Esercizio
¾
¾
Esercizio
¾ Svolgere
le operazioni A+B e A-B, in aritmetica
binaria utilizzando la rappresentazione in
complemento a due, dei seguenti valori
numerici (espressi in base 10), identificando la
presenza di un eventuale overflow:
Calcolare il risultato delle seguenti operazioni binarie
tra numeri interi con segno rappresentati in
complemento a due su 8 bit.
Scrivere l’equivalente rappresentazione dei numeri e
del risultato in decimale (verificando la correttezza del
risultato ottenuto).
•
•
•
•
00001101
00001100
00010100
11110100
24/10/2002
+
+
–
+
•
•
•
•
00111101
10110110
01101111
11101000
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
80
81
24/10/2002
A=(14)10 e B=(26)10
A=(12)10 e B=(74)10
A=(20)10 e B=(111)10
A=(-12)10 e B=(24)10
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
82
Esercizio
¾ Calcolare
il risultato dell’operazione binaria di
moltiplicazione tra i seguenti due numeri interi
assoluti a = 0101 b = 0011 rappresentati su 4
bit.
¾ Scrivere l’equivalente rappresentazione dei
numeri e del risultato in decimale (verificando
la correttezza del risultato ottenuto).
24/10/2002
Corso Informatica A - Allievi Gestionali - prof. C. Silvano
83
Corso Informatica A – Allievi Gestionali – prof. C. Silvano
14