Rappresentazione dell'informazione Informatica@Matematicamartini/MATH/Info-Mat-3.pdf · Somma in...
-
Upload
phungthien -
Category
Documents
-
view
218 -
download
0
Transcript of Rappresentazione dell'informazione Informatica@Matematicamartini/MATH/Info-Mat-3.pdf · Somma in...
Omnia in. . . numero
Unico tipo disponibile alla macchina fisica: parole di bit
Una parola e lunga 1, 2, 4, 8 byte
Rappresentazione esatta di grandezze discrete
Rappresentazione approssimata di grandezze discrete,mediante campionamento
3 / 21
Rappresentazione posizionale
In base b su k cifre
Per n 2 N, l’unica successione di k cifre definita da
n = ck�1bk�1 + · · ·+ c0b
0, ci 2 [0, b � 1].
Su k cifre sono rappresentabili i naturali nell’intervallo [0, 2k � 1].
(n)kb = ck�1 · · · c0
b = 2, 8, 16
Per b = 16, le cifre dopo 9 sono A,B ,C ,D,E ,F .(A17)16 = 1010 0001 0111 in binario.
4 / 21
Rappresentazione in modulo e segno
Per n 2 Z:
MS(n)k2 =
⇢(n)k2 se 0 n < 2k�1
(2k�1 + |n|)k2 se �2k�1 < n 0
L’intervallo di rappresentazione e [�2k�1 � 1, 2k�1 � 1].
Piu diretto: rappresenta |n| su k � 1 cifre;aggiungi la k-esima cifra (la piu significativa) come bit di segno:1 se n e negativo; 0 se n e positivo.
5 / 21
Rappresentazione in modulo e segno, 2
Svantaggi:
Due rappresentazioni per zero: 00000000 e 10000000 (su 8 bit)
Somma e sottrazione devono testare il bit di segno prima dell’operazione
6 / 21
Rappresentazione in complemento a 2
Per n 2 Z:
CD(n)k =
⇢(n)k�1
2 se 0 n < 2k�1
(2k + n)k2 se �2k�1 n < 0
L’intervallo di rappresentazione e [�2k�1, 2k�1 � 1].
Il bit piu significativo e ancora un bit di segno, ma il modulo di un numeronegativo e complementato: su 4 bit, 1010 rappresenta �6 (i bit 010rappresentano 2, cioe quello che manca a 6 per ottenere 23).
Su quattro bit, ora 1000 rappresenta �8, il minimo intero rappresentabile.
7 / 21
Somma in complemento a 2
Due interi (relativi) si sommano come due numeri senza segno
Gli ultimi due riporti (quelli di significativita 2k�1 e 2k) indicano se ilrisultato e corretto:
se sono diversi, e avvenuto overflow.
Esempi:
Interi su 8 bit; 27 = 128;intervallo di rappresentativita: [�128, 127].
Senza overflow:
11111 1110 (rip)
0000 1111 (15)
+ 1111 1011 (-5)
-----------
0000 1010 (10)
Con overflow:
01111 0000 (rip)
0111 1000 (120)
+ 0000 1010 ( 10)
-----------
1000 0010 (-126)
(e non 130)
8 / 21
Rappresentazione in virgola fissa
Per n 2 Q:
Su k bit, f bit riservati alla parte frazionaria;
Rappresentazione in complemento a 2
Intervallo di rappresentazione: [�2k�1/2f , (2k�1 � 1)/2f ]
Minimo modulo rappresentabile: 2�f .
Non necessita di hardware apposito
Spreco di bit per zeri non significativi
Scarsa precisione
9 / 21
Rappresentazione in virgola mobile
Per n 2 Q:
Rappresentato con una tripla (b, e, s)
la base b;
un numero intero e con segno, detto esponente.
un numero frazionario s con segno, detto significante
(o mantissa);
Rappresenta il numeros ⇥ b
e .
b = 2, sottinteso.
10 / 21
Numeri normalizzati
Rappresentazione non unica:I (+010,+1.1010) = (1 + 2�1 + 2�3)⇥ 22 = 6.5I (+011,+0.1101) = (0 + 2�1 + 2�2 + 2�4)⇥ 23 = 6.5
s e normalizzato sse e 1.b1b2 · · · bkla rappresentazione e unica per normalizzati,
ma abbiamo perso lo zero. . .
11 / 21
IEEE 754
Precisione semplice (32 bit):
Una specifica rappresentazione:
1 1 bit per il segno del significante (0 indica +);
2 8 bit per l’esponente, e, in eccesso 127;
3 23 bit per il significante normalizzato s
(solo parte frazionaria: bit nascosto).
Esponente e 2 [�126,+127], rappresentato come e + 127.Campo esponente 00000000 (e s = 0): zero.Campo esponente 11111111: NaN.
12 / 21
IEEE 754: Un esempio
1 10000001 10110000000000000000000
1 numero negativo;
2e = (27 + 1)� 127 = 2;
3 �(1.10110000000000000000000)2, ovveros = 1 + 2�1 + 2�3 + 2�4 = 1.6875;
4 �1.6875⇥ 22 = �6.75
13 / 21
IEEE 754
Precisione doppia (64 bit)
Standard per float di Python:
1 1 bit per il segno del significante (0 indica +);
2 11 bit per l’esponente, e, in eccesso 1023;
3 52 bit per il significante normalizzato s
(solo parte frazionaria: bit nascosto).
14 / 21
ASCII
American Standard Code for Information Interchange, 1961Codifica caratteri su 7 bit: solo 128 caratteri!
Ottavo bit: codice di parita(oggi: bit piu significativo e 0)
Codici (decimali) da 0 a 31 e 127: non stampabili (codici di controllo);
32: spazio (blank)
da 65 (101 oct) a 90 (132 oct): maiuscole da A a Z
da 97 (141 oct) a 122 (172 oct): minuscole da a a z
15 / 21
ASCII
Forse su�ciente negli anni ’60. . .
Assolutamente inadeguato oggi:I caratteri con segni diacritici: e, e, o, n, œ, a, c, a, z, oI segni di interpunzione: ¡, ¿, -, –, —I simboli: 8, 9, ⌦, 2, ?, ⇡, ⇠=I caratteri di altri alfabeti: ↵, �, H. ,I legature: ’∫J⌦ ´ –CÇÀ@
Necessita di codifiche estese e modulari
17 / 21
Unicode
Una codifica (in divenire) di tutti i caratteri usatiI da tutte le lingue viveI da alcune lingue morte
Piu di 110 000 caratteri
Piu di 100 script (“modi di scrivere”, p.e. “latin”,“armenian”, “arabic”, ecc.)
Comprende:I grafici per la resa visualeI metodi per la codifica (encoding methods)I info aggiuntive (normalizzazione, rendering, resa bidirezionale
etc.)
18 / 21
Unicode
Unicode non codifica direttamente “caratteri” con stringhebinarie.
Distinguiamo:
- Repertorio di carattericon serie di decisioni: “u” e uno o due caratteri?
- I codici (“code points”) di quei caratteri: un insieme di naturali“Coded Character Set” (CCS)
- Un Character Encoding Form, CEF:codifica dei code points con uno o piu bytes
- Come questi bytes sono ordinati (big-endian vs little-endian)
Numeri in gioco:
- Repertorio caratteri: 2 milionilog2 2M 21: 21 bit (3 byte)
- CEF piu “semplice” mappa ogni code point su tre bytes.Assurdo spreco!
19 / 21
Character Encoding: UTF
Universal Transformation Format
Ogni codice e rimappato su codifiche basate su 1, 2 o 4 byte:UTF-8, UTF-16, UTF-32
UTF-8 codifica i caratteri ASCII con 1 byte,e gli altri con due, o tre, o quattro byte.E il piu di↵uso; dovrebbe essere il defaultUn byte ASCII e un byte UTF-8 corretto.
UTF-16 codifica i caratteri piu comuni con 2 byte,e gli altri con 4 byte.
20 / 21