CODIFICA DELL’INFORMAZIONE
Esaminiamo i metodi più comuni di codifica di caratteri di testo e di dati
numerici.
Invece non prenderemo in esame nè la codifica di immagini (GIF, JPEG,
TIFF), nè quella dei suoni (MP3) o dei video (MPEG)
RAPPRESENTAZIONE DEL TESTO
CODICE ASCII
(American Standard Code for Information Interchange)
standard (a 7 bit) o esteso (a 8 o piu bit)
I caratteri sono divisi in gruppi:
0-31
32-127
di controllo per i devices (alcuni semplici, altri assai oscuri)
caratteri comuni stampabili (tranne il 127)
e, se si tratta di un codice esteso,
128-255 caratteri speciali aggiunti (con l'ottavo bit)
Ad es. la parola “Hello.” nel codice ASCII standard ha la seguente codifica:
1001000 1100101 1101100 1101100 1101111 0101110
Le applicazioni non window-based usano per lo più questo codice.
CODICE ANSI
(American National Standards Institute)
8 bits
dove i caratteri 0-31 sono poco usati, quelli 32-127 sono come in
standard ASCII, i rimanenti sono usati in applicazioni internazionali.
Nonostante il codice ASCII sia stato dominante per molti anni oggi si
diffondono codici in grado di rappresentare un maggior numero di
caratteri.
Le applicazioni window-based usano per lo più questo codice.
CODICE UNICODE 16 bit con 65536 caratteri
Oss.
Un file di testo è un file costitutito da una sequenza di caratteri codificati
in ASCII o Unicode o....
Un text editor (detto anche semplicemente editor) è un programma che
manipola un file di testo.
Un word processor manipola un file che contiene non solo codifiche di
caratteri ma anche codici proprietari che rappresentano informazioni
sull'allineamento, sui fonts, ecc.
STANDARD ASCII (da Wikipidia)
Da Wikipedia, l'enciclopedia libera.
Il termine ASCII esteso (in inglese extended ASCII o high ASCII) designa una
codifica a 8 bit o più, in grado di rappresentare molti caratteri oltre ai tradizionali 128
dell'ASCII a 7 bit. L'utilizzo di questo termine è stato spesso criticato in quanto
potrebbe lasciar intendere (erroneamente) che l'ASCII originario sia stato aggiornato
o che si tratti della stessa codifica.
Ragioni per l'espansione
Poiché il numero dei simboli usati nelle lingue naturali è molto più grande dei
caratteri codificabili col vecchio ASCII è stato necessario espanderne il set.
Poiché la codifica ASCII utilizza 7 bit molti dei set di estensione usavano i 128
caratteri aggiuntivi codificabili usando l'ottavo bit disponibile in ogni byte.
Estensioni proprietarie
Varie estensioni proprietarie nacquero sui mini-computer, specialmente nelle
università. L'IBM introdusse una codifica a 8 bit sui suoi IBM PC con varianti per i
diversi paesi. L'IBM produsse codifiche ASCII-compatibili, poiché i primi 128
caratteri del set mantenevano il valore originario (US-ASCII).
ISO 8859 e adattamenti proprietari
In seguito al proliferare di codifiche proprietarie, l'ISO (International Organization
for Standardization) rilasciò uno standard denominato ISO 8859 contenente
un'estensione a 8 bit del set ASCII.
Il più importante fu l'ISO 8859-1, detto anche Latin1, contenente i caratteri per i
linguaggi dell'Europa Occidentale. Furono standardizzate codifiche per gli altri
linguaggi: ISO 8859-2 per i linguaggi dell'Europa Orientale, ISO 8859-5 per i
caratteri cirillici e molti altri.
Una particolarità dell'ISO 8859 rispetto agli altri caratteri estesi è che i caratteri dal
128 al 159, i cui 7 bit più bassi corrispondono ai caratteri di controllo ASCII, non
sono usati per non creare problemi di compatibilità. Microsoft successivamente creò
la code page 1252, un set compatibile con l'ISO 8859-1 che riempie anche questi 32
caratteri, che divenne lo standard per le versioni europee di Windows.
Unicode
Una nuova codifica chiamata Unicode fu sviluppata nel 1991 per poter codificare più
caratteri in modo standard e permettere di utilizzare più set di caratteri estesi (es.
greco e cirillico) in un unico documento; questo set di caratteri è oggi largamente
diffuso. Inizialmente prevedeva 65.536 caratteri (code points) ed è stato in seguito
esteso a 1.114.112 (= 220 + 216) e finora ne sono stati assegnati circa 101.000. I primi
256 code point ricalcano esattamente quelli dell'ISO 8859-1. La maggior parte dei
codici sono usati per codificare lingue come il cinese, il giapponese ed il coreano.
RAPPRESENTAZIONE DEI NUMERI
Premesse
– Rappresentazione in base intera b ≥ 2 di un numero reale.
– Conversioni speciali fra rappresentazioni in basi che sono una una
potenza dell'altra, cioè passaggio da una rappresentazione in base b
ad una in base bk ( k ≥ 2) e viceversa.
– Algoritmo di conversione in base b ≥ 2 di un numero intero
positivo.
– Algoritmo di conversione in base b ≥ 2 di un numero frazionario
positivo minore di 1.
– Aritmetica in base b ≥ 2: somma e sottrazione di numeri
rappresentati in base b.
Nei calcolatori i numeri vengono rappresentati in una “forma di
notazione binaria”.
Si usano forme differenti. alcune adatte per rappresentare numeri interi,
altre per rappresentare anche numeri frazionari.
Noi presenteremo quelle chiamate:
- Rappresentazione in complemento a due (per gli interi)
- Rappresentazione in virgola mobile (anche per i frazionari).
Altre rappresentazioni sono:
- Modulo e segno
- Eccesso M
- Complemento alla base (a due, a dieci)
- Complemento alla base diminuita (a uno, a nove)
- Codice BCD (4 bit per ogni cifra decimale; nei tascabili)
RAPPRESENTAZIONE IN COMPLEMENTO A DUE
(di interi )
I 4 bit b3 b2 b1 b0 rappresentano in C2 i numeri
0000C2
0001C2
0010C2
0011C2
0100C2
0101C2
0110C2
0111C2
= - 0 x 23 + 0 x 22 +0 x 21 +0 x 20
= - 0 x 23 + 0 x 22 +0 x 21 +1 x 20
= - 0 x 23 + 0 x 22 +1 x 21 +0 x 20
= - 0 x 23 + 0 x 22 +1 x 21 +1 x 20
= - 0 x 23 + 1 x 22 +0 x 21 +0 x 20
= - 0 x 23 + 1 x 22 +0 x 21 +1 x 20
= - 0 x 23 + 1 x 22 +1 x 21 +0 x 20
= - 0 x 23 + 1 x 22 +1 x 21 +1 x 20
= 0dec
= 1dec
= 2dec
= 3dec
= 4dec
= 5dec
= 6dec
= 7dec
1000C2
1001C2
1010C2
1011C2
1100C2
1101C2
1110C2
1111C2
= - 1 x 23 + 0 x 22 +0 x 21 +0 x 20
= - 1 x 23 + 0 x 22 +0 x 21 +1 x 20
= - 1 x 23 + 0 x 22 +1 x 21 +0 x 20
= - 1 x 23 + 0 x 22 +1 x 21 +1 x 20
= - 1 x 23 + 1 x 22 +0 x 21 +0 x 20
= - 1 x 23 + 1 x 22 +0 x 21 +1 x 20
= - 1 x 23 + 1 x 22 +1 x 21 +0 x 20
= - 1 x 23 + 1 x 22 +1 x 21 +1 x 20
= -8dec
= -7dec
= -6dec
= -5dec
= -4dec
= -3dec
= -2dec
= -1dec
Def. La sequenza bn bn-1 ....b0
di m = n+1 bits rappresenta in
complemento a due il numero intero N = ∑i=0,...,n-1 bi2i - bn2n .
Oss.
bn = 0 ⇔ 0 ≤ N ≤ 2n -1 e
bn = 1 ⇔ -2n ≤ N < 0
e
∑i=0,...,n-1 bi2i = N
( ∑i=0,...,n bi2i = N )
∑i=0,...,n-1 bi2i = 2n - |N |
( ∑i=0,...,n bi2i = 2m - |N | )
Oss. con n+1 bits si rappresentano gli interi nell'intervallo: [-2n , 2n -1].
m=8
m = 16
m = 32
[-27 , 27 -1]
[-215 , 215 -1]
[-231 , 231 -1]
= [- 128 , 127]
= [- 32768 , 32767]
= [- 2147483648 , 2147483647]
Provate sulla vostra macchina:
P e r t r o v a r e l a rappresentazione dell'opposto di u n n um er o
rappresentato in complemento a due basta copiare da destra tutti gli zeri
della rappresentazione fino al primo 1 incluso e poi scambiare i rimanenti
bit fino a quello del segno compreso (oppure invertire tutti i bit della
rappresentazione e poi sommare 1). Verificare che 0 e -2n sono
autocomplementanti.
P e r sommare due numeri rappresentati in complemento a due basta
applicare l'algoritmo che esegue la somma binaria di tutte le cifre
comprese quelle del segno.
Si può dimostrare che se il riporto uscente dall'ultimo bit è uguale al
precedente non si ha overflow altrimenti sì.
RAPPRESENTAZIONE IN COMPLEMENTO A DUE
(di frazionari)
Def. La sequenza b0 b-1 ....b-n
di m = n+1 m bits rappresenta in
complemento a due il numero frazionario M = ∑i=1,...,n b-i2-i - b0 20.
Oss.
bn = 0 ⇔ M ≥ 0
e
b0 =1 ⇔ M < 0 e
∑i=1,...,n b-i2-i = M
∑i=1,...,n b-i2-i = 1 - | M|
(∑i=0,...,n b-i2-i = M).
(∑i=0,...,n b-i2-i = 2 - |M|).
Oss. con n+1 bit si rappresentano numeri frazionari nell'intervallo:
[-1, 1 -1/2n]
distanziati di 1/2n.
Oss. M ∈ [1/2,1) ⇔ la rappresentazione di M inizia con 01......
M ∈ [-1,-1/2) ⇔ la rappresentazione di M inizia con 10......
RAPPRESENTAZIONE IN ECCESSO 8
-8
è rappresentato da
0000
-7
è rappresentato da
…...
è rappresentato da
è rappresentato da
…....
è rappresentato da
è rappresentato da
0001
0
1
6
7
1000
1001
1110
1111
Da notare che la differenza tra un sistema in eccesso e un sistema in
complemento a due sta nel bit del segno che è invertito.
RAPPRESENTAZIONE IN VIRGOLA MOBILE
(di reali)
Sia b = 2 , R un numero reale che si vuole rappresentare in virgola
mobile.
Si sceglie una coppia di numeri (M, E) in modo tale che R = M 2E .
I numeri si chiamano mantissa M ed esponente E.
Se R > 0 si sceglie M ∈ [1/2, 1)
Se R < 0 si sceglie M ∈ [-1, -1/2)
Se R = 0 si sceglie M = 0
Si rappresenta R usando la coppia (M, E).
Es . R = + 392,5 = (+110001000,1)2 = (+ 0,1100010001)2 (29) = M 2E
Una rappresentazione in virgola mobile di R può rappresentare sia M
(frazionario) che E (intero) in complemento a due, ottenendo, con 32 bit:
00001001 0 1100010 00100000 00000000
Es . R = - 5 = (- 101)2 = (- 0,101) (23) = M 2E
00000011 1 0110000 00000000 00000000
Es . R = + 1 = (+ 1)2 = (+ 0,1) 2 (21) = M 2E =
00000001 0 1000000 00000000 00000000
Es . R = - 1 = (- 1)2 = (- 0,1) 2 (21) = M 2E =
00000001 1 1000000 00000000 00000000
la mantissa non è normale; normalizziamola moltiplicandola per 2;
occorre poi calare l'esponente di uno.
00000000 1 0000000 00000000 00000000
L' intervallo di rappresentazione è circa:
[10-38 , 1038]
[10-3xx , 1030x]
single
double
equivalente a:
6-7
cifre decimali significative
14-15 cifre decimali significative
in precisione singola, e
in precisione doppia
Operazioni di somma o sottrazione:
1) L’esponente più piccolo viene reso uguale al più grande spostando la
mantissa verso destra del numero di cifre pari alla differenza tra gli
esponenti (shift per ottenere un corretto incolonnamento)
2) Le mantisse vengono sommate o sottratte
3) Se necessario, la mantissa viene rinormalizzata e l’esponente corretto
Operazioni di moltiplicazione e divisione:
1) Le mantisse vengono moltiplicate o divise
2) Gli esponenti vengo sommati o sottratti
3) Se necessario, la mantissa viene rinormalizzata e l’esponente corretto
Es. Eseguire le seguenti somme:
0010 011011 +
0100 100011 =
0100 101001
1001 100111 +
1011 101111 =
1011 101000
0100 010000 +
0001 101000 =
0011 011010
0111 010100 +
0000 011011 =
0111 010100
Oss. L’aritmetica in virgola fissa è esatta, quella in virgola mobile non lo
è sia perchè la rappresentazione dei reali può essere approssimata (ad
esempio ͔π , 1/10 =1/16+1/32+1/256+1/512+ 1/4096+1/8192+.....) sia
perchè le operazioni stesse introducono eventuali troncamenti e/o
approssimazioni.
Provate a sommare 2.5+1/4+1/4 associando a sinistra e poi a destra (con
4 bit per la mantissa).
Precisione Macchina: è il più piccolo numero macchina a > 0 tale 1+a è
il numero macchina successivo ad 1.
Con parole di 32 bit è 2-23
Con parole di 64 bit è 2-52
#include <stdio.h>
#include <math.h>
#include <limits.h>
main()
{
puts("\nPrecisione macchina:");
// precisione macchina
if(1+pow(2,-52) >1)
puts("O.K. 52");
if(1+pow(2,-53) >1)
puts("O.K. 53");
puts("\nMassimo reale positivo:");
// massimo reale positivo
printf("2^1023 = %f\n", pow(2,1023));
printf("2^1023 = %e\n", pow(2,1023));
printf("2^1023 = %.14e\n", pow(2,1023));
puts("");
printf("2^1024 = %e\n", pow(2,1024));
printf("2^1024 = %.14e\n\n", pow(2,1024));
puts("\nMinimo reale positivo:");
// minimo reale positivo
printf("2^-1074= %e\n", pow(2,-1074));
printf("2^-1075 = %.14e\n", pow(2,-1075));
puts("\nMinimo e massimo intero :");
}
printf("%d %d\n", INT_MIN, INT_MAX);
// Sulla mia macchina questo programma stampa:
Precisione macchina:
O.K. 52
Massimo reale positivo:
2^1023 =898846567431157953864652595394512366808988489471153286367150405788663379027
5048156635423866120376801056005693993569667882939488440720831124642371531973706218
8394671243274263815110980062304705972654147604250288441907534117123144073695655524
13618581675255342293149119973622969239858152417678164812112068608.000000
2^1023 = 8.988466e+307
2^1023 = 8.98846567431158e+307
2^1024 = inf
2^1024 = inf
Minimo reale positivo:
2^-1074= 4.940656e-324
2^-1075 = 0.00000000000000e+00
Minimo e massimo intero :
-2147483648 2147483647
IEEE 754 floating point standard:
s eeeeeeee
s eeeeeeeeeee
m..................m
(1+8+23 bits)
m ......................... m (1+11+52 bits)
single
double
Il numero viene scritto in binario come ∓1.b1b2b3.... 2E
Il primo 1 non viene rappresentato.
L'esponente viene aumentato di 127 in single (di 1023 in double) e poi
rappresentato senza segno.
In eccesso 127:
0 viene rappresentato con la sequenza
1 viene rappresentato con la sequenza
01111111
10000000
Esempi di rappresentazione in virgola mobile :
Numero decimale -1 = -1.0 20:
1 01111111 0000000 00000000 00000000
Numero decimale 2 = 1.0 21:
0 10000000 0000000 00000000 00000000
Numero decimale -3 = -1.1 21:
1 10000000 1000000 00000000 00000000
Numero decimale 0.5 = 1.0 2-1:
0 01111110 0000000 00000000 00000000
Numero decimale 0.085 = 1.01011100001010001111
0 01111011 0101110 00010100 01111010
Numero decimale -0,75 = -1.1 2-1:
1 01111110 1000000 00000000 00000000
Numero decimale -5 = -1.01 22:
1 10000001 1100000 00000000 00000000
2-4