Rappresentazione dell’informazione

Informazione analogica e digitale

Rappresentazione dell’informazione

• Il primo tipo di informazione che si presta ad essere rappresentato rigorosamente è l’informazione numerica– n aste per rappresentare il numero n (numerazione unaria)

– ëlogk(n)û + 1 cifre per rappresentare il numero n in base k

Bit = binary digit

• Con un bit si possono rappresentare due informazioni diverse– 0/1, vero/falso, acceso/spento

• 1 byte = 8 bit• Informazioni più complesse richiedono un numero

variabile di bit– Con N bit si possono rappresentare 2N informazioni diverse• N = 2 -> 00, 01, 10, 11

Informazione non numerica

• Informazione testuale (caratteri)• Informazione grafica (forme geometriche)• Informazione musicale (digitalizzata o no)• Fotografie• Video

Testo

• ASCII (American Standard Code for Information Interchange)– 7 o 8 bit usati per rappresentare 128/256 caratteri

• A ogni lettera (le maiuscole da A a Z, le minuscole da a a z), cifra (da 0 a 9) separatore o simbolo viene assegnato un numero naturale rappresentabile in forma binaria – Ad esempio “A” viene codificata in ASCII come numero 65 e la sua

forma binaria è 01000001– Il separatore “;” viene codificato come 59 e la sua forma binaria

è 00111011

Immagini

• Quadradito = pixel• Ogni pixel può assumere n colori diversi– 2 colori (1 bit)– 1024 colori (10 bit)

Esempio

• RGB è un modello di colori– Specifiche descritte nel 1931

da CIE (Commission internationale de l'éclairage)

– Si basa sui tre colori rosso(Red), verde (Green) e blu(Blue)

Codifica

• Numeri naturali

• 1716150413120110 = 128+64+32+8+4+1 = 237• Generalizzabile ad altre basi

– Da base due a base 8 (o 16) e viceversa è più facile. Perché?

237 : 2 = 118 resto 1

118 : 2 = 59 resto 0

59 : 2 = 29 resto 1

29 : 2 = 14 resto 1

14 : 2 = 7 resto 0

7 : 2 = 3 resto 1

3 : 2 = 1 resto 1

1 : 2 = 0 resto 1

Attenzione

• Rappresentazione del numero 32: 100000– Servono 6 bit– Implicitamente sono 33 elementi diversi: da 0 a 32

– ëlog2(32)û + 1 = 5+1

• 32 elementi diversi hanno rappresentazione da 0 a 31– Bastano quindi 5 bit -> ëlog2(31)û + 1 = 4+1

Primi esempi di rappresentazione

• Con un byte possiamo rappresentare i numeri naturali da 0 a 255– 0 ≤ k ≤ 2n-1 se n = 8: 0 ≤ k ≤ 255 – 010 = 000000002; 810 = 000010002; …; 25510 = 111111112

• Oppure i numeri interi compresi fra –127 e 127– -(2n-1 -1)≤ k ≤ 2n-1-1 se n = 8: -127 ≤ k ≤ +127 – Primo bit = 0: numero positivo, primo bit = 1: numero negativo– 1010 = 000010102 -1010 = 100010102

– 010 = 000000002 e -010 = 100000002

Operazioni elementari

• Inversione di un bit– 0 -> 1, 1 -> 0

• Somma di due bit– 0+0 = 0, 1+0 = 1, 0+1 = 1, 1+1 = 0 (1)– 0*0 = 0, 1*0 = 0, 0*1= 0, 1*1 = 1

• Se interpretiamo 0 come Falso e 1 come Vero, le operazioni di cui sopra diventano operatori logici– Inversione = negazione, (NOT, ¬)– Somma logica, (OR, Ú)– Prodotto logico, (AND, Ù)

Somma cifra per cifra

riporto 11100 00110000000100

8731 10001000011011

5698 01011001000010

risultato 14429 11100001011101

Modulo e segno

• Dato un numero intero N, codificato su n bit, il bit più significativo rappresenta il segno– 0 significa positivo e 1 negativo– I restanti n-1 bit rappresentano il valore assoluto del numero• N = 6 -> 3 bit + 1 per il segno -> 0110• N = -6 -> 1110

• Problemi con le operazioni aritmetiche elementari– Analisi del segno– Confronto dei valori assoluti

Somma tra due numeri

segno A = segno B

|A| > |B|

|RIS| = |B| - |A|

segno RIS = segno B segno RIS = segno A

|RIS| = |A| - |B|

SINO

NO

segno RIS = segno A

|RIS| = |A| + |B|

Complemento a 1

• Codifica diversa per semplificare l’algoritmo di calcolo• Non si distingue più il segno dal modulo• Dato un numero N, il suo opposto si calcola complementando ad

uno ad uno tutti i bit che compongono il numero– N = 01001 -> -N = 10110

• Somma e sottrazione richiedono solo sommatori e negatori (per il calcolo dell’opposto)

• Il risultato è corretto a meno di un 1 nel caso in cui si verifichi un riporto nella somma stessa– Quindi si usa sempre una seconda somma per sommare il riporto

generato (fosse zero la somma sarebbe inutile)

Esempio

• N = 011001 (+25) e M = 000011 (+3)• N + M = 011001 + 000011 = 011100 (+28)

• K = 111100 (-3)• N + K = 011001 + 111100 = (1)010101 – 010101 + 000001 = 010110 (+22)

• Numeri devono essere rappresentati con lo stesso numero di cifre• Sempre due somme– Non è la soluzione ottima, ma è la meno costosa

Complemento a 2

• Ulteriore miglioramento con rappresentazione più complicata• Somme algebriche con una sola addizione• Notazione non simmetrica (-2n-1 ≤ N ≤ 2n-1 -1)– Una sola codifica per il numero zero– Numeri positivi hanno sempre la stessa codifica– Numeri negativi

• -N è quel numero che sommato a N produce una configurazione di tutti zero e un bit di riporto che si trascura

• Operativamente– Complemento a 1 e poi si somma uno– Si scorre il numero da destra a sinistra, lasciando inalterate le cifre fino al primo uno

(compreso) e si complementano le altre

Esempio

• N = 011001 (+25)• -N = 100110 + 000001 = 100111 oppure• -N = 100111

– “Salvo” solo il primo uno e complemento tutto il resto

• N = 011001 (+25) e M = 000011 (+3)• K = 111101 (-3)• N + K = 011001 + 111101 = (1)010110 = 010110 (+22)

• M – N = 000011 + 100111 = 101010 (-22)– 010110 -> +22

• Attenzione a leggere i numeri negativi

ConfrontoCodifica Modulo e segno Complemento a 1 Complemento a 2

0000 +0 +0 +0

0001 +1 +1 +1

0010 +2 +2 +2

0011 +3 +3 +3

0100 +4 +4 +4

0101 +5 +5 +5

0110 +6 +6 +6

0111 +7 +7 +7

1000 -0 -7 -8

1001 -1 -6 -7

1010 -2 -5 -6

1011 -3 -4 -5

1100 -4 -3 -4

1101 -5 -2 -3

1110 -6 -1 -2

1111 -7 -0 -1

Numeri razionali

• Virgola fissa– Si codificano separatamente la parte intera e la parte

frazionaria– Ad esempio• primo byte: rappresentazione parte intera• secondo byte: rappresentazione parte frazionaria

• Virgola mobile– Mantissa e esponente (o caratteristica): r = m ´ bn

• Con b = 10: -331.6875 viene rappresentato m = -0.3316875 e n = 3

Conversione

23.47 = 2×101 + 3×100 + 4×10-1 + 7×10-2

10.012 = 1×21 + 0×20 + 0×2-1 + 1×2-2

= 1×2 + 0×1 + 0×½ + 1×¼= 2 + 0.25 = 2.25

0.58710

• 0.587 ´ 2 = 1.174: parte frazionaria 0.174 e parte intera 1• 0.174 ´ 2 = 0.348: parte frazionaria 0.348 e parte intera 0• 0.348 ´ 2 = 0.696: parte frazionaria 0.696 e parte intera 0• 0.696 ´ 2 = 1.392: parte frazionaria 0.392 e parte intera 1• 0.392 ´ 2 = 0.784: parte frazionaria 0.784 e parte intera 0• 0.784 ´ 2 = 1.568: parte frazionaria 0.568 e parte intera 1• 0.568 ´ 2 = …

• Precisione– 0.1001 (con quattro cifre binarie dopo la virgola) – 0.100101 (con sei cifre binarie dopo la virgola)

Virgola fissa (39.345)

Parte intera (39)

• 39:2 = 19 1• 19:2 = 9 1• 9:2 = 4 1• 4:2 = 2 0• 2:2 = 1 0• 1:2 = 0 1

• 00100111 = 39

Parte frazionaria (.345)

• .345 x 2 = .69 0• .69 x 2 = 1.38 1• .38 x 2 = .76 0• .76 x 2 = 1.52 1• .52 x 2 = 1.04 1• .04 x 2 = .08 0• .08 x 2 = .16 0

• 0.0101100 = 0.34375

Numero normalizzato (r = m ´ bn)

• Si impone che m sia sempre minore di 1 e la sua cifradecimale più significativa sia sempre diversa da 0– 0.45676 ´ 102 normalizzato– 0.0456 ´ 103 non normalizzato

• Un numero binario rappresentato in v.m. assume la forma normalizzata:1.d-1d-2d-3...d-(p-1)·2e

– si rappresenteranno esplicitamente:• i bit dopo la virgola• l'esponente• il segno del numero

IEEE 754

• È lo standard più diffuso per la rappresentazione deinumeri in virgola mobile

• Quattro formati per i numeri in virgola mobile:– a precisione singola (32 bit)

• Un numero in virgola mobile è rappresentato su parole di 32, 64 o 128 bit divisi in tre parti: un bit di segno (S), un campo esponente (E) e uno mantissa (M)– Precisione singola (32 bit): 1/8/23– Precisione doppia (64 bit): 1/11/52

(-1)S x 2E x M

• S (segno): 0 positivo e 1 negativo• E (esponente in forma intera)– Permette di rappresentare 256 valori

• I valori 0 e 255 vengono riservati per funzioni speciali• Gli altri permettono di rappresentare 254 valori per i numeri in forma

normale, compresi tra -126 e 127

– Il campo è rappresentato in eccesso k: E = e + k• Per i numeri a precisione singola, k è uguale a 127

– In questa rappresentazione, i valori dell'esponente compresi tra -126 e 127 assumono invece i valori compresi tra 1 e 254, eliminando la necessità di un bit riservato al segno

Mantissa

• Il campo M rappresenta la sequenza di cifre dopo la virgola– Tutte le mantisse sono normalizzate in modo che il numero

prima della virgola sia 1, per cui per un dato M il valorecorrispondente è m = 1.M

• La mantissa è costituita dal numero binario 1, seguitodalla virgola e dalla parte decimale del numerorappresentato, in forma binaria

Esempio: -118.5

• Numero negativo, quindi S = 1• Numero2: 1110110,1• Normalizzazione, spostiamo la virgola verso sinistra,

lasciando solo un 1 alla sua sinistra– La mantissa è riempita con zeri a destra fino a riempire i 23

bit: 11011010000000000000000

• L'esponente è pari a 6, ma E = 6 + 127 = 133– In forma binaria: 10000101

Numeri reali

• I numeri frazionari possono introdurre approssimazioni– Presenza di un numero limitato di cifre dopo la virgola

• Numeri reali approssimati dai razionali