1

Aspetti dell’informazione

Quando abbiamo a che fare con informazionedi qualunque tipo distinguiamo:

contenuto (messaggio/significato) rappresentazione (codifica/significante)supporto materiale

Il numero dieci

10 (dieci nella numerazione araba)

X (dieci nella numerazione romana)

10

2

Significato e significante

Pane Cane

Analogico/digitale: una definizione

Analogico: basato sulla similitudine tra la rappresentazione e l'informazione rappresentata

Digitale: basato su una rappresentazione simbolica di informazioni discrete

3

Esempi

Orologio a lancette/ orologio a cifreil disco di vinile/ il CDLa fotocamera tradizionale/quella digitaleil telefono tradizionale/ la linea ISDN

Codifica di informazioni (discrete)A = alfabeto = insieme finito di simboli = {a,b,c,…}

stringa = sequenza finita di simboli di A

esempio: “aabcedc” è una stringa di n = 7 simboli

codifica: funzione che associa in modo 1-1 (iniettivo)una stringa su A ad ogni informazione

informazioniA* = insieme

di tutte le stringhesu A

codifica

4

Esempio: codifica binaria A = {0,1}

spenta

accesa01

La lampadina è

primaveraestate

autunnoinverno

00011011

Siamo in

Quante informazioni posso rappresentare con stringhe di lunghezza n su un alfabeto di k simboli? Esempio A = { }Quante sono le stringhe di lunghezza n se A ha ksimboli?

Data la stringa s = x1 … xn-1 esistono k stringhe dellaforma

x1 … xn-1 y con y ∈A

5

perciò se le stringhe di lunghezza n-1 sono m, allora quelle di lunghezza n

sono m × k.

Facendo variare n:

n = 1 allora k

n = 2 allora k × k …

n = 3 allora k × k × k

in generale le stringhe di lunghezza n saranno:

k × … × k (n volte) = kn

In conclusione: con un alfabeto di k simboli posso rappresentare kn informazioni con stringhe di lunghezza n

Esercizio

L’alfabeto A = { } : quante informazioni posso codificare con stringhe di lunghezza 5?

45 = 1024

6

Rappresentazione delle informazioni all’interno dei computer

I computer usano una codifica binaria. L’alfabeto e’ costituito da soli due simboli, indicati convenzionalmente con 0 e 1L’entità minima di informazione (0 e 1) prende il nome di bit(binary digit - cifra binaria). Mediante un bit possiamo rappresentare due informazioni

Le ragioni di questa scelta sono prevalentemente di tipo tecnologico, infatti i due simboli corrispondono a:

due stati di polarizzazione di una sostanza magnetizzabile;

i due stati di carica elettrica di una sostanzaal passaggio/non passaggio di corrente attraverso un

cavo conduttore;al passaggio/non passaggio di luce attraverso un cavo

otticoetc.…..

7

Unità di Misura: bit, Byte, …

1 bit = stringa su {0,1} di lunghezza unitaria

1 byte = stringa su {0,1} di lunghezza 8

1 KB = 210 = 1024 byte

1 MB = 220 =1024 Kbyte (un milione di byte circa)

1 GB = 230 =1024 Mbyte (un miliardo di byte circa)

1 TB = 240 =1024 Gbyte (mille miliardi di byte circa)

Codifica binariaCon una sequenza di n bit possiamo rappresentare

2n informazioni

Viceversa: se devo rappresentare k> 1 informazioni diverse, quanti bit sono necessari?

Ho bisogno di un numero di bit n tale che 2n ≥ k

Questo numero è log2k

8

k log2k2 13 24 25 36 37 38 39 416 417 532 533 6

Esercizio

Quanti bit sono necessari per codificare i giorni della settimana? E i giorni del mese?

9

Soluzione

I giorni della settimana sono 7: ho bisogno di 3 bitI giorni del mese sono al massimo 31: hobisogno di 5 bit

La codifica dei caratteri

Dobbiamo rappresentare le lettere dell’alfabeto{a,b,c, …A,B,C, %, &, (, ),…0,1,2,3,.,; ?+,-*,...}

L’insieme di simboli comunemente usati nell’alfabeto anglosassone, incluse le cifre numeriche, lettere maiuscole e minuscole, simboli di punteggiatura, parentesi e operatori aritmetici, può essere codificato usando 7 bit (27 = 128)Il metodo di codifica più diffuso tra i produttori di hardware e di software prende il nome di codice ASCII (American Standard Code for Information Interchange)

10

La codifica dei caratteri: Il codice ASCII

0000000 NUL 0001110 SO 0011100 FS0000001 SOH 0001111 SI 0011101 GS0000010 STX 0010000 DLE 0011110 RS 0000011 ETX 0010001 DC1 0011111 US0000100 EOT 0010010 DC2 0100000 SP0000101 ENQ 0010011 DC3 0100001 !0000110 ACK 0010100 DC4 0100010 "0000111 BEL 0010101 NAK 0100011 #0001000 BS 0010110 SYN 0100100 $0001001 HT 0010111 ETB 0100101 %0001010 NL 0011000 CAN 0100110 &0001011 VT 0011001 EM 0100111 '0001100 NP 0011010 SUB 0101000 (0001101 CR 0011011 ESC 0101001 )

La codifica dei caratteri: Il codice ASCII

0101010 * 0111001 9 1000111 G0101011 + 0111010 : 1001000 H0101100 , 0111011 ; 1001001 I0101101 - 0111100 < 1001010 J0101110 . 0111101 = 1001011 K0101111 / 0111110 > 1001100 L0110000 0 0111111 ? 1001101 M0110001 1 1000000 @ 1001110 N0110010 2 1000001 A 1001111 O0110011 3 1000010 B 1010000 P0110100 4 1000011 C 1010001 Q0110101 5 1000100 D 1010010 R0110110 6 1000101 E 1010011 S0110111 7 1000110 F 1010100 T0111000 8

11

La codifica dei caratteri: Il codice ASCII

1010101 U 1100011 c 1110001 q

1010110 V 1100100 d 1110010 r

1010111 W 1100101 e 1110011 s

1011000 X 1100110 f 1110100 t

1011001 Y 1100111 g 1110101 u

1011010 Z 1101000 h 1110110 v

1011011 [ 1101001 i 1110111 w

1011100 \ 1101010 j 1111000 x

1011101 ] 1101011 k 1111001 y

1011110 ^ 1101100 l 1111010 z

1011111 _ 1101101 m 1111011 {

1100000 ` 1101110 n 1111100 ¦

1100001 a 1101111 o 1111101 }

1100010 b 1110000 p 1111110 ~

1111111 DEL

Il codice ASCII

Sebbene 7 bit siano sufficienti per codificare l’insieme di caratteri di uso comune, il codice ASCII standard utilizza 8 bit, il primo dei quali è sempre 0Codici ASCII con 1 iniziale sono utilizzati per codificare caratteri speciali, ma la codifica non è standard.

Codifica della parola cane

01100011 01100001 01101110 01100101c a n e

12

Problema inverso: decodificaquale testo è codificato da una data sequenza?

– si divide la sequenza in gruppi di otto bit (un byte); – si determina il carattere corrispondente ad ogni byte

011010010110110000000000011100000110111100101110011010010110110000000000011100000110111100101110

i l P o .

Osserva che:

La decodifica è possibile (e facile) perchè i caratteri sono codificati con stringhe binarie dilunghezza costante

13

Altri formati

ECBDIC formato alternativo a 8 bitUNICODE nuovo standard a 16 bit contiene simboli per la maggiorparte degli alfabeti esistenti (compreso arabo, giapponese, etc…)

MSWINDOWS codifica proprietaria della Microsoft simile a UNICODE

Esercizio

Un testo di 400 caratteri occupa 1600 bit, quanti caratteri puo’ avere al massimo l’alfabeto?

14

Soluzione

Ogni carattere occupa 1600/400 = 4 bit, quindicon 4 bit posso codificare sino a 24 = 16 caratteri

Codifica di un documento

Un documento può essere formattato: – i caratteri hanno una dimensione, uno stile,

un font– il testo può essere giustificato, avere margini,

tabulazioni, centrature, incolonnato etc.Tutte queste caratteristiche possono venire codificate e memorizzate insieme al testoformato solo-testo (text-only) rimuove tutte le informazioni di formattazione aggiuntive

15

Il codide ASCII codifica anche le cifre decimalila codifica ASCII è troppo costosa in spazio:

24 = 00110010 00110100non è possibile usare direttamente le codifiche ASCII

per le operazioni aritmetiche:Esempio: Numero ASCII

3 + 001100112 = 00110010---- -------------e 01100101

Rappresentazione dei numeri

Rappresentazione dei numeri

La numerazione decimale utilizza una notazione posizionale basata sul numero 10. La sequenza “234” rappresenta il numero

2 x 102 + 3 x 101 + 4 x 100

La notazione posizionale può essere utilizzata in qualunque altro sistema di numerazione (con base diversa da 10)

16

Sistemi di numerazione

Ogni numero può essere rappresentato in qualunque base B > 1

Fissata una base B > 1

cn cn-1 … c1 c0

dove ciascun ci < B, rappresenta il numero

r = cn × Bn + cn-1 × Bn-1 +… + c1 × B1 + c0 × B0

Basi usate comunementeBase decimale B = 10:

cifre 0,1,2,3,4,5,6,7,8,9

Base binaria B=2:

cifre 0,1

Base ottale B=8:cifre 0,1,2,3,4,5,6,7

Base esadecimale B=16:cifre 0,1,…,9,A,B,C,D,E,F

17

Sistema di numerazione binariaNel caso binario la sequenza

cn cn-1 cn-2... c1 c0

(ogni “ci” è la cifra “0” o la cifra “1”) rappresenterà il numero

cn x 2n + cn-1 x 2n-1 + ... c1 x 21 + c0 x 20

La sequenza “1011” in base 2 denota il numero 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 = 11

(in base 10)Per evitare ambiguità si usa la notazione 10112 = 1110

Esempio: numero rappresentazione binaria0 0001 0012 0103 0114 1005 1016 1107 111

18

Metodo di conversione da base 10 a base 2

Dato k = cn x 2n + cn-1 x 2n-1 + ... c1 x 21 + c0 x 20

siano m il quoziente di k diviso 2 e r il resto, hai che

m = cn x 2n-1 + cn-1 x 2n-2 + …+ c1 x 20

r = c0

k = 2m + c0

c0 ∈ {0,1} è l’ultimo bit (il meno significativo)ripeti il procedimento su m determinando in questo modo gli altri bit, fino a che m non e’ piu’ divisibile.

Esempio2210 22 = 11 × 2 + 0

101102

101102 = 1 × 24 + 0 × 23 + 1 × 22 + 1 × 21 + 0 × 20 = 2210

2 = 1 × 2 + 0

1 = 0 × 2 + 1

5 = 2 × 2 + 1

11 = 5 × 2 + 1

19

Esercizio

Esercizio: convertire in binario il numero 37

soluzione:3710 = 1001012

3710 = 1 × 25 + 0 × 24 + 0 × 23 + 1 × 22+ 0 × 21 + 1 × 20

Aritmetica binaria

0 + 0 = 0 con riporto 00 + 1 = 1 con riporto 01 + 0 = 1 con riporto 01 + 1 = 0 con riporto 1

1 0 1 +

1 1 =

1 0 0 0

1 1 0 1 ×

1 1 =

1 1 0 1

1 1 0 1

1 0 0 1 1 1

20

Esercizio

Calcola 10011+1101

Soluzione

risultato = 100000 = 32

21

Limiti della rappresentazione di numeri

Consideriamo la base dieci: con 3 cifre decimali si possono rappresentare i numeri compresi tra 0 e 999, il numero successivo (1000) richiede una quarta cifra

Se si vuole rappresentare 1000 con 3 cifre decimali si ha un problema di overflow, ossia si esce dal numero di cifre destinato alla rappresentazione, e si genera un errore perché il numero non può essere rappresentato

Poiché il numero 999 può essere scritto come 103-1 (ossia 1000-1), possiamo enunciare la seguente regola:con N cifre decimali si possono rappresentare i numeri da 0 a 10N-1Consideriamo la base due: con tre cifre binarie si possono rappresentare i numeri compresi tra 0 e 23-1 (ossia 8-1), possiamo enunciare la seguente regola:con N cifre binarie si possono rappresentare i numeri da 0 a 2N-1

22

Overflow nelle operazioni

2 + 010 +3 = 011 =___ ______5 101

5 + 101 +4 = 100 =___ ______9 1001

*** ERRORE: OVERFLOW ***(non può essere codificato con tre bit)

Questo problema può essere osservato anche con la rappresentazione decimale

5 +6 =_____11 *** ERRORE:

non basta una sola cifra

Standard per numeri interi

Numeri piccoli: 1byte <= 255Interi: 2-4byte <= 232

Interi lunghi: 4-8byte <= 264

23

Rappresentazione di numeri razionali in virgola mobile (floating point)

Rappresentazione di numeri razionali, esempio 12,5

Abbiamo che 12,5 = 125/10 = 125 * 10-1

= 1250/100 = 1250 * 10-2

possiamo quindi rappresentare 12,5 con la coppia(125, -1)

Si adotta una rappresentazione dei numeri razionali(con segno) del tipo

segno × mantissa × baseesponente

24

Rappresentazione di numeri grandi

Esempio: supponiamo di avere a disposizione solo 2 byte di dover memorizzare 23.077.130(non si può: 216 ~ 65.000)

O si usano più byte o si sacrifica la precisione, adottando una rappresentazione in virgola mobile

23.077.130 = (2.307 x 10.000) + 7.130 == (2.307 x 104) + 7.130

Se siamo disposti a trascurare l'ultimo addendo (7.130), possiamo memorizzare il numero dedicando i primi 4 bit all'esponente (il 4 di 104) e i restanti 12 bit al moltiplicatore 2.307 (mantissa)

0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

ESPONENTE MANTISSA

1° BYTE 2° BYTE

25

Codifica standard a 32 bit1 bit per il segno dell’esponente1 bit per il segno della mantissa8 bit per il valore assoluto dell’esponente22 bit per il valore assoluto della mantissa

Uso di hardware specializzato per operazioni con floating point: coprocessore matematico

Esempio: rappresentazione dei razionali (con base 10)

0

-1x10-255 1x10-255 222 –1x10255-222x10255

Numeri Negativi rappresentabili

Numeri Positivi rappresentabili

26

EsercizioSupponi di avere – 1 bit per segno mantissa– 1 bit per segno esponente– 2 bit per esponente e– 8 bit per mantissa m

e i numeri siano scritti in base 10 come m* 10e

quali sono il minimo e il massimo numero positivo e negativo rappresentabili?osservare le lacune: alcuni numeri non sono rappresentabili

Fissando il numero complessivodi bit si hanno due scelte:

Meno bit per l’esponente, più bit per la mantissa: – maggiore precisione – intervallo piccolo dei numeri rappresentabili

(numeri densi)Più bit per l’esponente, meno per la mantissa:– minore precisione, – intervallo grande dei numeri rappresentabili

(numeri sparsi)