Rappresentazione dell’Informazione
Fondamenti dell’Informatica
Michele Ceccarelli
Università del [email protected]
Angelo Ciaramella
DMI-Università degli Studi di [email protected]
Argomenti della Lezione n. 2
• Premessa
• Sistemi di numerazione posizionali
• Numeri frazionari
• Sistemi decimale, binario, ottale, esadecimale
• Conversione binario � decimale
• Rappresentazione di interi in complemento a 2
• Rappresentazione di reali in floating point
• Caratteri: codici ASCII e UNICODE
Codifica dati e istruzioni
• Algoritmi=istruzioniistruzioni che operano su datidati
• Per scrivere in programma è necessario rappresentare istruzioni e dati in maniera che l’esecutore automatico possa – Memorizzare dati e istruzioni
– Manipolare dati e istruzioni
Codifica dati e istruzioni
• Alfabeto dei simboli– Cifre “0”, “1”,…,”9”, separatore delle migliaia (.), separatore
decimale (“,”)e segni “+” e “-”
• Regole di composizione (sintassi) che definiscono le successioni “ben formate”– “1.234,5” è la rappresentazione di un numero– “12,23,4” non lo è
• Codice (semantica)– “1.234,5”=1x103+2x102+3x101+4x100+5x10-1
– “12,23,4” = ??
• Lo stesso alfabeto può essere utilizzato per codici diversi– “123,456” = 1x102+2x103+3x100+4x10-1+5x10-2+6x10-3 [IT]– “123,456” = 1x105+2x104+3x103+4x102+5x101+6x100 [UK]
Codifica binaria
•• Alfabeto binarioAlfabeto binario: dispositivi con due soli stati
• Problema: assegnare un codice univoco a tutti gli elementi di un insieme
• Quanti oggettioggetti possiamo rappresentare con k bitk bit (cifre binarie)– 1 bit � 2 stati (0,1) � 2 oggetti
– 2 bit � 4 stati (00 01 10 11) � 4 oggetti
– 3 bit � 8 stati (000 001 010 011 … 111) � 8 oggetti
– …
–– k bit k bit �� 22kk stati stati �� 22kk oggettioggetti
• Quanti bit servono per rappresentare N oggetti?–– N N ≤≤ 22k k �� k k ≥≥loglog22N N �� k=k=loglog22NN
Codifica binaria
• Quanti bit per rappresentare i giorni della settimana?– 3 bit
• Quanti bit per i mesi dell’anno– 4 bit
• Tutti i caratteri?– 26 miniscole+26 maiuscole+10 cifre+circa 30 caratteri di interpunzione+circa 30 caratteri di controllo ≈ 120 caratteri � k=k=loglog22120120=7=7
Alcune unità di misura
• bit – cifra binaria, solo due stati
• Byte – 8 bit
• KiloByte = 210 byte = 1024 byte≈ 103 byte
• MegaByte = 210 KiloByte ≈ 106 byte
• GigaByte = 210 MegaByte ≈ 109 byte
• TeraByte = 210 GigaByte ≈ 1012 byte
• PetaByte = …
• ExaByte = …
Codifica di Interi
Sistemi di numerazione posizionali
• Cosa intendiamo quando scriviamo (p.es.)??
1346712
• Questo si ottiene come:– Due + dieci + settecento+ seimila+… + unmilione
• Ogni cifra è moltiplicata per un peso. – A partire da destra i pesi sono 1, 10, 100, 1000, ….100000, ovvero 100,
101, 102, 103,…., 106
• Il totale si ottiene sommando il valore di ciascuna cifra moltiplicata per il peso corrispondente alla sua posizione
• In un sistema di numerazione posizionale:– ogni cifra della rappresentazione di un numero assume un peso in base
alla posizione che essa occupa nella rappresentazione, tale peso è una potenza della base
Sistemi di numerazione posizionali
• Elementi di un sistema di numerazione posizionale– La base b, un numero naturale (p.es. 10)– L’insieme dei numeri di cifre D=(0,1,…, b-1)– Le regole di codifica per integrare stringhe di cifre – Le operazioni (+, -, *,/)
• Un numero intero rappresentato in base b con n cifre è una sequenza ordinata di cifre:
(Cn-1, Cn-2…. C1, C0) b• A ciascuna cifra è associata un peso. Da destra a sinistra i pesi sono b0, b1, b2,…., bn-1
Forma polinomiale
(Cn-1 Cn-2…. C1, C0) b=C0xb0+C1xb1+C2xb2+…+Cn-1xbn-1
• In modo analogo possiamo scrivere numeri frazionari:
(C-1 C-2…. C-m)b =C-mxb-m+…+C-2xb-2+ C-1xb-1
Ad esempio: .532 = 2x 10-3+ 3x 10-2+ 5x 10-1
• Infine abbiamo numeri misti con una parte intera e una parte frazionaria:
(Cn-1…. C0.C-1 …. C-m)b =C-mxb-m+…+C0+C-1xb-1+ C0xb0 + C1xb1+…+Cn-1xbn-1
Base 2
• In questo caso D={0,1}
• Bit: binary digit (cifra binaria)
• Esempi di conversione binario => decimale:
(10100)2 =1x24+0x23+1x22+0x21+0x20= (20)10(1011)2 =1x23+0x22+1x21+1x20= (11)10(11000101)2=27+26+22+20+
= 128+64+4+1+=(197)10
Conversione decimale => binario
• Problema formulabile come segue: dato un intero decimale d, determinare la sequenza di bit Cn-1 Cn-2 …C1C0 tale che
d= C0x20+C1x21+C2x22+…+Cn-1x2n-1
• Mettiamo in evidenza il 2:– d = 2(C1x20+C2x21+…+Cn-1x2n-2)+ C0
• Applichiamo il teorema fondamentale dei numeri naturali (unicitàdel quoziente e del resto)– Esistono e sono unici q ed r tali che
d=2q+r ed r<2, dove q=[d/2] (quoziente), r= d mod 2 resto
• Da cui: C0 = resto della divisione di d per 2 cioè C0=d mod 2q = C1x2
0+C2x21+C3x2
2+…+Cn-1x2n-2 cioè: q = [d/2]
Conversione decimale => binario
• Se q ≠0 (ovvero d>1) possiamo ripetere la procedura:q=2q’+r’
q = C1x20+C2x21+C3x22+…+Cn-1x 2n-2= C1+2(C2x20+…+Cn-1x2n-3)
• Da cui:– C1 = r’ = q mod 2
– q’ = C2x20+…+Cn-1x2n-3=[q/2]
• Se q’ ≠ 0 si ripete ancora:q’=2q’’+r’’
da cui C2=q’ mod 2 q’’=[q’/2]
Esempio
• Convertire in binario il numero decimale (54)10
54 mod 2 = 0 = C0 (least significant bit), 54/2 = 2727 mod 2 = 1 = C1 27/2 = 1313 mod 2 = 1 = C2 13/2 = 66 mod 2 = 0 = C3 6/2 = 33 mod 2 = 1 = C4 3/2 = 11 mod 2 = 1 = C5 (most significant bit), 1/2 = 0
Quindi (54)10= (110110)2
Esercizio
• Calcolare la rappresentazione in base due dei numeri: 18, 137, 75
Sistema ottale
• D =[0, 1, 2, 3 4, 5,6, 7]• (453)8 = 4 x 82 + 5 x 81 +3 x 80 = (299)10• Decimale-ottale: Divisione successive
• Esempio: (678)10
678 mod 8 = 6 (q=84) C0=684 mod 8 = 4 (q=10) C1=410 mod 8 = 2 (q=1) C2=21 mod 8 = 1 (q=0) C3=1
Quindi (678)10=(1246)8
Conversione binario �ottale
• Ciascuna cifra ottale corrisponde ad una tripletta di bit:– 000=>0 001=>1 010=>2 011=>3
100=>4 101=>5 110=>6 111=>7
La conversione è quindi immediata
Esempio: (25)8 = (010101)2Esempio: (11100101011)2 = (3453)8
Sistema esadecimale
• D=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]– Nota:
(A)16=(10)10(B)16=(11)10(C)16=(12)10(D)16=(13)10(E)16=(14)10(F)16=(15)10
• Le conversioni si effettuano allo stesso modo (forma polinomiale per passare a decimale, divisioni successive per passare a esadeciamle)
Sistema esadecimale
• In questo caso ciascuna cifra esadecimale può essere rappresentata da 4 bits0000 =>0 0001 =>1 0010=>2 0011=>3
0100 =>4 0101 =>5 0110=>6 0111=>7
1000 =>8 1001 =>9 1010=>a 1011=>B
1100 =>C 1101 =>D 1110=>E 1111=>F
Come per l’ottale, le conversioni esadecimale �
binario sono banali:
(1011011001)2 = (2D9)16(3FA4)16 = (11111110100100)2
Forma complemento
• Dato un intero N in base b e k cifre, il complemento a b di N, scritto Cb(N) è il numero in base b tale che– N+Cb(N) = bk
• Per b=2, C2(N)=2k-N
Esempi:
– b=10, k=4, N=2553, C10(2553)=104-2553 = 7447
– b=10, k=3, N=945, C10(945)=103-945 = 55
– b=2, k=5, N=(10100)2, C2(10100)=(100000)2-(10110)2 = (10100)2– b=2, k=5, N=(01101)2, C2(01101)=(100000)2-(01101)2 = (10011)2
– b=2, k=6, N=(101100) 2, C2(101100)=(010100)2
Regola pratica per il caso b=2
• C2(N) = (2k-1) – N+1
• Nel caso binario 2k-1=111..1 (k volte)
• Sottrarre (2k-1) – N significa negare (invertire 0->1 ed 1->0) tutti i bit di N quindi si somma 1
• Esempio: (01101)2
Primo passo: si negano i bit, ottenendo 10010
Secondo passo: si somma 1, ottenendo 10011
Sottrazione con la forma complemento
• Vogliamo calcolare N-M:
• Si rappresenta N e M con lo stesso numero k di cifre (eventualmente aggiungendo zeri in sinistra)
• Si calcola il complemento C2(M)
• Si somma N+C2(M), questo è uguale a N+2k-M
• Si scarta la cifra più significativa del risultato (cioè2k)– Esempio : (11001100)2 – (11000010)2 (204)10-(194)10C2(11000010)=(00111101)2+(1)2=(00111110)2(11001100)2+(00111110)2=(100001010)2Risultato = (00001010)2
00111101+1=
00111110
11001100+00111110=
100001010
Rappresentazione di interi
• Senza segno: si usano k bit per la sequenza di k cifre – il range di valori rappresentabili è [0, 2k-1]
• Come possiamo rappresentare numeri negativi?• Modulo e segno: si destina un bit al segno (p.es. il
MSB)– Esempio con 8 bit:– (+54)10=(00110110)2– (-54)10=(10110110)2– Posso rappresentare i numeri fra -2k-1-1 e 2k-1-1
• Problema: dato lo zero avrebbe due rappresentazioni diverse: (0000000)2 e (10000000)2
• Inoltre non si trarrebbe vantaggio dalla possibilità di sottrarre e sommare con lo stesso circuito
K=5
10000 � 16 11100 � 28
10001 � 17 11101 � 29
10010 � 18 11110 � 30
10011 � 19 11111 � 31
10100 � 20
10101� 21
10110 � 22
10111 � 23
11000 -> 24
11001 � 25
11010 � 26
11011 � 27
Rappresentazione di interi
• Soluzione: si usano k bit e si rappresentano i numeri negativi in complemento a 2 (in questo modo il bit più significativo rappresenta il segno)
• Il range è [-2k-1, 2k-1-1]
• Esempio (8bit):33 00100001-21 11101011-128 10000000127 01111111
Soluzione: si usano k bit e si rappresentano i numeri negativi in complemento a 2
• K=5-1� 11111-2� 11110-3 �11101-4 �11100-5 �
…-15 �10001-16 �1000010000� nego i bit � 01111
110000
Diverse codifiche/interpretazioni
7770111
6660110
5550101
4440100
3330011
2220010
1110001
0000000
C2MSNatCodice
-1-7151111
-2-6141110
-3-5131101
-4-4121100
-5-3111011
-6-2101010
-7-191001
-8-081000
C2MSNatCodice
Overflow
• Esempio: 71 e 60 sono due interi entrambi rappresentabili su 8 bit in complemento a 2
• La somma 71+60=131 non è rappresentabile
• Se calcoliamo la somma binaria otteniamo:
0 1 0 0 10 1 1 +
0 0 1 1 01 1 0 =
1 0 0 0 10 0 1
(10000011)2=(-128+3)10=-125
Rappresentazione numeri reali
• Virgola fissa: si stabilisce un numero di bit K1
da assegnare alla parte intera ed un numero di bit K2 da assegnare alla parte frazionaria
• Per esempio si destinano 32 bit:16 alla parte intera e 16 alla parte frazionaria
• Adatta solo a casi particolari in cui l’intervallo di valori da rappresentare è noto a priori
• Inadatta nella maggior parte delle applicazioni scientifiche o finanziarie
Rappresentazione floating point
• Si parte dalla rappresentazione scientifica in cui un numero è il prodotto di 2 parti: una parte frazionaria ed un fattore di scala
• Esempio: il numero 4123.14 può essere rappresentato equivalentemente come:– 412.314x101
– 41.2314x102
– 4.12314x103
– 0.412314x104
– etc…
•• rappresentazione normalizzatarappresentazione normalizzata: la cifra più a sinistra e immediatamente preceduta dal punto decimale deve essere diversa da zero
Rappresentazione in floating point
• Nel caso mantissa ed esponente sono rappresentabili in binario
• Esempi:
Numero Rappres. Mantissa Esponente
normalizzata
(0.000110)2 0.11x2-11 0.1100000 -11
(101000.0)2 0.101x2110 0.1010000 +110
(11.01010)2 0.110101x210 0.110101 +010
Codifica floating point
• La caratteristica (o esponente) corrisponde al fattore di scala della rappresentazione scientifica
• La mantissa corrisponde alla parte frazionaria
• Il segno viene rappresentato con un bit a parte
• Standard IEEE:– Short float: 8 bit di esponente, 23 di mantissa (32bit)
– Long float: 16 bit di esponente, 47 di mantissa (64 bit)
Codifica dei caratteri
• Repertorio. Insieme dei caratteri considerati, definito mediante i nomi dei caratteri e magari una loro rappresentazione visiva
• Numero di codice: tabella in cui ciascun carattere del repertorio è messo in corrispondenza 1-a-1 con un insieme di numeri naturali
• Codifica: un metodo per associare a ciascun numero di codice una sequenza di ottetti (gruppi da otto bits) che poi sono utilizzabili per la trasmissione o la memorizzazione elettronica
• Nel caso più semplice ogni carattere ha un numero tra 0 e 127 e la codifica è semplicemente la codifica binaria del numero in 7 bit
Codifica ASCII
• American Standard Code for Information Interchange
• Serve per rappresentare caratteri (sia visibili che alcuni caratteri di controllo)
• 7 bits per carattere, dunque si possono rappresentare 27 = 128 caratteri diversi
• I codici da 0 a 1F sono usati per i caratteri di controllo
• I codici da 20 a 7E sono usati per caratteri stampabili (e segni di interpunzione)
• Ordine alfabetico: cifre 0-9 prima dei caratteri alfabetici, maiuscole prima delle minuscole (si rifletterà nell’ordinamento delle stringhe)
Tabella de codici ASCII
Alcuni caratteri di controllo
• 04 (Crtl-D): End-of-terminal
• 07 (Crtl-G): Bell
• 08 (Crtl-H): Backspace
• 0A (Crtl-J): New line
• 0C (Crtl-L): New page
• 0D (Crtl-M): Carriage return
• 1B tasto Espace
Vantaggi e limitazione del codice ASCII
• ASCII è un codice standard e (ad eccezione di alcune variati nazionali pressoché in disuso) molto sicuro; purtroppo:– I caratteri internazionali di numerose lingue europee non sono contemplati
– Per non parlare delle lingue asiatiche per le quali il numero di simboli è elevatissimo
• La standardizzazione è importante: nella trasmissione e memorizzazione elettronica i caratteri sono rappresentati da ottetti di bit ed è importante che il “trasmettitore” e il “ricevitore” adottino le stesse convenzioni !
UNICODE
• La versione 3.0 di UNICODE (Febbraio 2000) definisce 49,194 caratteri
• Il vantaggio di UNICODE è di definire un insieme di caratteri adatti a trattare tutti i linguaggi
• Mentre con altri standard lo stesso carattere può avere codifiche diverse (a seconda dell’alfabeto usato), in Unicode ogni carattere ha una codifica unica
• Ha grande diffusione industriale (Apple, HP, IBM, Microsoft, Oracle, Sun, Sybase, etc…)
• Supportato da vari SO e internet browsers più recenti
UNICODE
• Il codice usa 16 bit (fino a 64K caratteri)