Rappresentazione dell’Informazione

Fondamenti dell’Informatica

Michele Ceccarelli

Università del Sannioceccarelli@unisannio.it

Angelo Ciaramella

DMI-Università degli Studi di Salernociaram@unisa.it

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)