Codifica binaria

Rappresentazione di
dati: numerazione
binaria
Appunti per la cl. 3 Di
A cura del prof. Ing. Mario Catalano
Rappresentazione binaria
Tutta l’informazione interna ad un
computer è codificata con sequenze di
due soli simboli : 0 e 1
è facile realizzare dispositivi elettronici che
discriminano fra due stati, molto meno se
gli stati sono tanti
L’unità elementare di informazione si
chiama bit da‘binary digit’
Byte : sequenza di 8 bit
2
Sistema decimale posizionale (1)
 Un numero (es. 5) può essere rappresentato in
molti modi :
cinque, five, 5, V, XXXXX …..
 Rappresentazioni diverse hanno proprietà diverse
Es. moltiplicare due numeri in notazione romana è
molto più difficile che moltiplicare due numeri in
notazione decimale ….
 Noi siamo abituati a lavorare con numeri
rappresentati in notazione posizionale in base 10
3
Sistema decimale posizionale (2)
 La rappresentazione di un numero intero in base
10 è una sequenza di cifre scelte fra 0 1 2 3 4 5
6789
 Il valore di una rappresentazione è dato da
aN . 10N + aN-1 . 10N-1 ….+ a1 . 101 + a0 . 100 + a-1 . 101+
a-2 . 10-2 + a-3 . 10-3 + a-4 . 10-4 + ...
• b= 10 è la base
• 10i è il peso della cifra ai nel valore del
numero
• Sistema decimale posizionale
4
Sistema decimale posizionale (3)
 253 = 2 x 100 + 5 x 10 + 3 x 1
= 2 x 102 + 5 x 101 + 3 x 100
 23,47 = 2 x 10 + 3 x 1 + 4 x 0.1 + 7 x 0.01 = 2
x 10 + 3 x 1 + 4 x (1/10) + 7 x (1/100) =
2 x 101 + 3 x 100 + 4 x 10-1 + 7 x 10-2
Sistema posizionale
Sistema decimale
5
Notazione posizionale in base 2 (1)
La rappresentazione di un numero intero
in base 2 è una sequenza di cifre scelte
fra 0 1 :
es: 10, 110, 1
Il valore di una rappresentazione è dato da
aN . 2N + aN-1 . 2N-1 ….+ a1 . 21 + a0 . 20 + a-1 . 2-1 +
a-2 . 2-2 + a-3 . 2-3 + a-4 . 2-4 + ...
• b= 2 è la base
• 2i è il peso della cifra ai nel valore del numero
• Sistema binario posizionale
7
Notazione posizionale in base 2 (2)
Esempi :
• 10 = 1*21 + 0 *20 = 2
• 110 = 1*22 + 1*21 + 0 * 20 = 4 + 2 + 0 = 6
• 1 = 1 *20 = 1
10 si legge 1 0 e non dieci !!!
8
Conversione di interi
Base 10  Base 2
Successione di divisioni per 2 : termina
quando il resto è 0
Resti determinati in ordine inverso
es.:
13
6
3
1
0
Quozienti
1
0
1
1
Resti
1310 = 11012
9
Conversione di interi
Base 2  Base 10
Somma pesata delle cifre binarie:
es.: 11012 = 1 x 23 + 1 x 22 + 0 x 21 + 1 x
20
= 8 + 4 + 0 + 1
= 1310
10
Numeri binari interi: esempi
0
1
2
3
4
5
6
7
0
1
10
11
100
101
110
111
8
9
10
11
12
13
14
15
1000
1001
1010
1011
1100
1101
1110
1111
16 10000
17 10001
18 10010
…..
11
Numeri binari interi: esempi(2)
20
21
22
23
24
25
26
27
...
=
1
=
2
=
4
=
8
= 16
= 32
= 64
= 128
28
29
210
211
212
216
=
256
=
512
= 1024 (1 k)
= 2048
= 4096
...
= 65536 (64 k)
224  16 milioni
...
12
Esempio : convertire il numero
decimale 17
 17 2
16 8 2
1 8 4
0 4
0
2
2
2
0
2
1
13
Binario
Decimale
La somma dei prodotti della cifra binario
moltiplicata per la base (2) elevata la
posizione
100
2
1
(1* 2 ) + (0 * 2 ) + (0 * 2 )
 1*4 + 0
+ 0
0
=
=
4
14
Addizione in binario
 L’addizione in binario segue le stesse regole
dell’addizione tra numeri decimali:
 i due numeri sono incolonnati uno sopra l’altro;
 si effettua la somma delle cifre di pari peso.
15
Addizione
 1010 + (10)
111 = ( 7)
10001
(17)
16
Addizione: esempio
1
carry o riporto
1
1
1
1
1
1
0
1
1
1
0
0
0
1
0
0
1
0
+
17
Sottrazione in binario
 Anche la sottrazione in binario segue le stesse regole
della sottrazione tra numeri decimali:
 i due numeri sono incolonnati uno sopra l’altro;
 si effettua la sottrazione delle cifre di pari peso.
18
Sottrazione
11011 10101 =
00110
110
19
Sottrazione: esempio
1
carry o riporto
1
0
0
1
1
1
1
0
0
1
0
1
-
20
Esercizi
• (34)10 + (77)10
0
1
0
0
0
1
0
+
1
0
0
1
1
0
1
=
1
1
0
1
1
1
1
• (84)10 - (37)10
1
1
1
1
1
1
0
0
1
1
0
0
0
1
1
0
0
0
1
0
1
0
1
1
1
1
=
21
Moltiplicazione
1 per 1
0 per 1
=1
=0
1101 *
101=
1
11011
000011011000001
22
divisione
1101 11
11
100
0001
RISULTATO 100
RESTO 1
23
Sistema esadecimale
Base 16
Simboli : 0…9+le sei lettere maiuscole
A,B,C,D,E,F
Assume importanza perché la base 16 è
una potenza di 2, base del sistema di
numerazione binario.
4
16 = 2
24
Da esadecimale a decimale
 numero esadecimale 2BC1
3
2
1
0
2*(16) + 11 *(16) + 12*(16) + 1*(16)
2*4096+11*256+12*16+1*1 =11201
25
Decimale
11201 : 16 =
 700 : 16 =

43 : 16 =

2
in esadecimale
resto 1
resto 12 C
resto 11 B
26
Esempio: trasformazione del numero esadecimale
3 AF2 in numero decimale:
163  3  162 10  161 15  160  2  15090
Trasformazione del numero decimale 16034 in
numero esadecimale:
Quozienti resti
16034
1002
62
3
0
2
A
E
3
1603410  3EA216
27
Nelle operazione di conversione dei numeri da un sistema
all’altro, è conveniente ricordare le seguenti tabelle:
Binario
Ottale
000
001
010
011
100
101
110
111
0
1
2
3
4
5
6
7
Binario
Esadecimale
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
28
Da binario a esadecimale
Si raggruppano le cifre del numero binario a
gruppi di quattro a partire da destra e si
trasformano le cifre di ciascun gruppo nel
corrispondente numero esadecimale secondo
la tabella di conversione
Es.: il numero binario 1011110111
Si può scrivere come
10
2
1111
F
0111
7
Quindi: 1011110111 2 = 2F716
29
Da esadecimale a binario
Si fa corrispondere a ciascuna delle cifre
esadecimale che compongono il numero un
gruppo di quattro bit secondo la tabella di
conversione.
Es.: dato il numero esadecimale C3B
Quindi:
C
3
B
1100
0011
1011
C3B16  1100001110 112
30
La rappresentazione dei numeri
all’interno di un computer (1)
 Usa la notazione binaria
 Ogni numero viene rappresentato con un
numero finito di cifre binarie (bit)
 Numeri di ‘tipo’ diverso hanno rappresentazioni
diverse
es. interi positivi, interi (pos. e neg.), razionali, reali,
complessi
31
La rappresentazione dei numeri
all’interno di un computer (2)
 Alcuni termini utili:
byte : una sequenza di 8 bit
word (parola) : 2 o 4 byte (dipende dalla macchina)
unità minima che può essere fisicamente letta o
scritta nella memoria
 Tipicamente gli interi positivi si rappresentano
usando 2 o 4 byte
00110010
 Notazione
MLS (Most Significant Bit)
LSB (Least Significant Bit)
32
La rappresentazione dei numeri
all’interno di un computer (3)
Interi positivi e negativi :
ci sono diverse convenzioni di
rappresentazione
modulo e segno in cui il primo bit viene riservato al
segno (1 negativo, 0 positivo) e gli altri 31 al
modulo
Complemento a due
Complemento a uno (la trascuriamo)
rimane comunque il problema dell’overflow
33
Rappresentazione modulo e segno
Dati N bit, il bit più significativo indica il
segno, ed i restanti N-1 bit indicano il
valore assoluto del numero in binario puro.
S
Modulo
Il segno è codificato nel seguente modo:
0 : segno +
1 : segno 34
La rappresentazione dei numeri in
modulo e segno
Numeri relativi
 Modulo e segno (es con 3 bit)
0 segno+
1 segno -
- codifica semplice
- operazioni aritmetiche più complesse
es.: +2  010 e -2  110
001 +
1+
110 =
-2 =
Errato!
111
-3
Occorre differenziare tra i bit del numero e quelli di segno
Bisogna codificare in modo diverso le operazioni
35
aritmetiche.
Rappresentazione dei numeri in
complemento a 2
Complemento a due (es con 4 bit)
es: +5 = 0101
-5 ??
• Partendo da +5 = 0101 si invertono gli 1 con gli
0 : 1010
• Si aggiunge 1: 1010 + 1 = 1011 = -5
- 1 x 23 +0 x 22 + 1 x 21 + 1 x 20
= - 8 +0 + 2 + 1 = -5
Il primo bit non rappresenta solo il segno!
36
Non occorre più pertanto differenziare i bit.
Rappresentazione in complemento a 2:
esempio
 -5 con quattro bit
il bit di segno è 1
 Conversione:
 Inversione:
 Somma di 1:
 Verifica: + 5
–5
=0
510 = 01012
0101  1010
1010 + 1 = 1011
 0101
 1011
= (1)0000
37
Rappresentazione dello 0
Il numero 0 può avere, in modulo e segno,
le seguenti due rappresentazioni:
0
0…………….0
1
0…………….0
Intervallo di valori rappresentabili:
- 2 (N-1) + 1  + 2 (N-1) -1
38
Conversione da complemento a 2 in decimale con
segno
 se prima cifra 0  numero positivo  conversione solita
(es. 0100  +4)
 se prima cifra 1  numero negativo 
 inversione dei bit (tranne il primo)
 conversione da binario a decimale
 somma di 1
39
Conversione da complemento a 2 in decimale con
segno: esempio
 1101
tolgo il bit di segno  101
Inversione  010
Conversione in decimale  0102 = 210
Somma  2 + 1 = 3
Segno  -3
40
Esempio di conversione da
decimale a complemento a 2
Rappresentare in complemento a 2 su 6 bit i
seguenti numeri: + 3, - 6.
 +3 è positivo: la rappresentazione è uguale
a quella in modulo e segno: (000011);
 - 6 è negativo:
 il numero corrispondente positivo (+6) vale
000110;
 complemento bit a bit e ottengo 111001;
 sommo 1 ed ottengo 111010.
41
Addizione in complemento a due
Con 3 bit avremo:
000
+0
001
+1
010
+2
011
+3
100
-4
101
-3
110
-2
111
-1
Esempi di addizione:
0010+
1011=
1101
(+2)
(-5)
(-3)
0111+
1011=
0010
(+7)
(-5)
(+2)
Nel secondo esempio,
l’overflow è ignorato
42
Limiti delle rappresentazioni
Fissato un numero N di bit disponibili, i
limiti delle rappresentazioni finora trattate
sono:
 Binario puro
0….. +(2N-1);
Complemento a 2 -(2N-1)… 0…+(2N-1-1);
43
Limiti delle rappresentazioni
Fissato un numero di 5 bit disponibili
avremo:
 Binario puro
0….. 31;
 Modulo e segno -15… -0+0…+15;
 Complemento a 2
-16… 0…+15;
44
La rappresentazione dei numeri
razionali
 Razionali
numero finito di cifre periodiche dopo la virgola (ad
esempio 3.12 oppure 3.453
rappresentazione solitamente su 4/8 byte
rappresentazione in virgola fissa : riservo X bit per la
parte frazionaria
es : con 3 bit per la parte intera e 2 per quella
frazionaria 011.11, 101.01
Parte intera
Parte frazionaria
45
Come si converte in base 10 una
rappresentazione in virgola fissa
es :
101.01 = 1* 22 + 0 * 21 + 1 * 20 + 0 * 2-1 + 1 * 2-2
= 4 + 1+ 0.25 = 5.25
10101.1101 = 1*24 + 1*22 + 1*20 + 1*2-1 + 1*2-2
+ 1*2-4 = 21.8125
dove 2-1 = 1/2 = 0.5, 2-2 = 1/22 = 0.25
e in generale 2-n = 1/2n
46
REALE--> BINARIO
cosa significa una parte decimale
binaria:
.1101001
2-1+ 2-2 + 2-4 + 2-7
47
per trovare la rappresentazione binaria di
un decimale lo moltiplichiamo per 2 ed
osserviamo se 1 appare nella parte intera:
rappresentazione binaria di
.592= 1.18
.182= 0.36
.362= 0.72
.59
.722= 1.44
.442= 0.88
.100101.....
.882= 1.76
....... dipende da quanti bit
abbiamo
48
esempio
18.59
18  10010
.59  .100101...
10010.100101....
49
Problemi della rappresentazione in
virgola fissa
overflow
underflow quando si scende al di sotto del
minimo numero rappresentabile
es. vediamo in base 10, con 2 cifre riservate alla
parte frazionaria 0.01 / 2 = 0.005 non
rappresentabile usando solo due cifre
50
 Problemi della rappresentazione in virgola fissa
(cont.)
spreco di bit per memorizzare molti ‘0’ quando lavoro
con numeri molto piccoli o molto grandi
 es. vediamo in base 10, con 5 cifre per la parte intera e 2
cifre riservate alla parte frazionaria
10000.00 oppure 00000.02
i bit vengono usati più efficientemente con la
notazione esponenziale o floating point (virgola
mobile)
51
Conversione di numeri con la virgola: da
binario a decimale
 La conversione di questi numeri in base 10 è immediata.
Basta fare l’analogia con i numeri in base 10. ad
esempio, nel numero
 112,18
 la cifra 1 dopo la virgola ha peso 10-1, la cifra 8 ha peso
1/100 cioè 10-2.
 In maniera analoga
 00101011,01101 =
0*27 + 0*26 + 1*25 + 0*24 +1*23 + 0*22 + 1*21 + 1*20 +
+0*2-1 + +1*2-2 + 1*2-3 + 0*2-4 + 1*2-5 =
32 + 8 + 2 + 1 + 1/4 + 1/8 + 1/32 =
42 + 0.25 + 0.125 + 0.03125 = 43.40625
52
Conversione di numeri con la virgola: da
decimale a binario
43.40625 =
0*27+ 0*26 + 1*25 + 0*24 +1*23 + 0*22 + 1*21+
1*20 +0*2-1+1*2-2 + 1*2-3 + 0*2-4 + 1*2-5 =
00101011,01101 quindi N = 43 e 0,M =
0.40625
53
Rappresentazione in virgola mobile
idea : quando lavoro con numeri molto piccoli uso
tutti i bit disponibili per rappresentare le cifre dopo la
virgola e quando lavoro con numeri molto grandi le
uso tutte per rappresentare le cifre in posizioni
elevate
questo permette di rappresentare numeri piccoli con
intervalli minori fra loro rispetto ai numeri grandi
questo riduce gli errori nel calcolo a parità di bit
utilizzati
54
Rappresentazione in virgola mobile
La notazione in virgola mobile è basata
sulla rappresentazione dei numeri in
notazione scientifica.
Nella notazione scientifica un numero N
viene espresso nella seguente forma:

N = ± mantissa * base esponente
55
Esempio
 Il numero decimale 213.0465 si può scrivere (almeno)
nelle seguenti notazioni scientifiche:
 2.130465 * 102
 0. 2130465 * 103




Il binario 1011.011 si può scrivere (almeno) come:
1.011011 * 23
0.1011011 * 24
1011011 * 2-3
56
Standard IEEE 754
Per evitare ambiguità di rappresentazione di
uno stesso numero si usa una forma
normalizzata (standard IEEE 754) su 32 bit
suddivisi nel seguente modo:
S
Esponente
Mantissa (modulo)

 Singola precisione (SP)
 Doppia precisione (DP)
8 bit
11 bit
23 bit
52 bit
57
Standard IEEE 754
 Precisione singola su 32 bit
 1 bit di segno
 8 di esponente (da -126 a +127)
 23 di mantissa
 Si possono rappresentare valori fino a 2 elevato a (-150)
 Precisione doppia su 64 bit
 1 bit di segno
 11 di esponente (da -1022 a +1023)
 52 di mantissa
 Si possono rappresentare valori fino a 2 elevato a (-1075)
58
Standard IEEE 754
S
Esponente
Mantissa (modulo)
E’ sempre normalizzata nella forma
1.XXXXX; l’1 viene sottinteso
E’ rappresentato come numero senza
segno su 8 bit in eccesso 127, cioè i valori
da -126 a 127 sono messi in corrispondenza
con i valori da 1 a 254, per non dover gestire
Il segno dell’esponente.
0 = positivo
1 = negativo
59
Standard IEEE 754
La rappresentazione floating point IEEE
754 e’ quindi nella forma:
Numero(binario) = ± 1.XXXX * 2 (YYYY)
0/1
Esponente
Mantissa (modulo)
60
Intervallo di rappresentazione
 MantissaMIN = 1
MantissaMAX < 2
 EsponenteMIN = -126
EsponenteMAX = +127
 Valori rappresentabili:
 zero;
 [2 (-126) … 2(+127)]; equivalente a [10 (-38) …10(+38)];
 [-2(+127) …-2(-126 )]; equivalente a [-10(+38) …-10(-38)];
61
Ulteriore sistema di codifica dei numeri
BCD (Binary-Coded Decimal)
 Si codificano in binario (4 bit) le singole cifre
decimali.
 es.: 254
2
5
4
0010 0101 . 0100
 nessun errore di conversione
 precisione dei calcoli decimali
 spreco di cifre
 usato nelle calcolatrici tascabili
62
Rappresentazione di un insieme
finito di oggetti
Vogliamo rappresentare i giorni della
settimana :
{Lu, Ma, Me, Gio, Ve, Sa, Do}
usando sequenze 0 e 1
Questo significa costruire un ‘codice’,
cioè una tabella di corrispondenza che
ad ogni giorno associa una opportuna
sequenza
In principio possiamo scegliere in modo
del tutto arbitrario….
63
Rappresentazione di un insieme
finito di oggetti (2)
 Per rappresentare 7 oggetti diversi servono
almeno 3 bit (minima potenza di due che
supera 7 è 8= 23) quindi :
000
001
010
011
100
101
Lunedì
Martedì
Mercoledì
Giovedì
Venerdì
Sabato
110 Domenica
111 non ammesso
64
Rappresentazione di caratteri e
stringhe
 Tipologia di caratteri:
alfabeto e interpunzioni: A, B, .., Z, a, b, .., z, ;, :, “, ..
cifre e simboli matematici: 0, 1, ..., 9, +, -, >, ..
caratteri speciali: £, $, %, ...
caratteri di controllo: CR, DEL, ....
 Le stringhe sono sequenze di caratteri terminate in modo
particolare.
 I caratteri sono un insieme finito di oggetti e seguono la
strategia vista per i giorni della settimana
65
Rappresentazione di caratteri e
stringhe (2)
 ASCII (American Standard Code for
Information Interchange): Codice a 7 bit
(standard)
 ASCII esteso a 8 bit (non standard)
 es.:
A
01000001
(
00101000
 UNICODE: su 16 bit (65536 diverse
configurazioni): più recente, permette di
rappresentare anche alfabeti diversi e simboli
per la scrittura di lingua orientali.
66
Rappresentazione di caratteri e stringhe (3)
 ASCII a 7 bit
I 7 bit sono suddivisi logicamente in 7 campi
rispettivamente di 3 e 4 bit.
I primi tre bit rappresentano categorie di caratteri,
mentre gli ultimi quattro servono a rispettare l’
ordinamento dei caratteri all’ interno di ogni
categoria.
67
Rappresentazione di caratteri e stringhe (4)
1°bit
2°bit 3°bit Caratteri rappresentati
0
1
0
0
1
1
simboli di punteggiatura, simboli
speciali e di operazione
simbolo di =
0
1
1
numerali
1
0
0
maiuscole (A - O)
1
0
1
maiuscole (P - Z)
1
1
0
minuscole (a - o)
1
1
1
minuscole (p - z)
68
Rappresentazione di caratteri e
stringhe (5)
 4°, 5°, 6°, 7° bit
 Nei numerali sono costituiti dalla codifica in
binario su 4 bit delle cifre decimali (codice BCD).
 Per i caratteri dell’alfabeto la codifica è tale da
rispettare l’ordinamento alfabetico
 Esempi
b (2ª lettera) : 1100010
B: 1000010
69
FINE
70