Codifica dei Dati Idea: vogliamo rappresentare dati eterogenei

utilizzando un linguaggio che l’elaboratore puo’ facilmente manipolare

Essenzialmente vogliamo costruire una codifica tra linguaggi

Utilizzamo codifica binaria per le seguenti ragioni un alfabeto con due soli simboli corrisponde al

linguaggio di una macchina basata su circuiti elettronici riduce l’errore nella rappresentazione dell’informazione Il numero di simboli per rappresentare numeri cresce in

modo logaritmico con il numero: per rappresentare N occorrono in fatti simboli

N2log~

Vari tipi di codifiche La rappresentazione usuale dei numeri

e’ quella posizionale decimale dove si utilizzano 10 caratteri Alfabeto: 0…9 Si ragiona in base 10.

Es. 19= 1*10+9*(10**0) Operazioni aritmetiche:

Le tabelline delle elementari…(riporto ecc)

Altre possibili rappresentazioni: Unaria: una barretta per unita’

Ad es: IIIIIIIIIIIIII rappresenta 15!!!

Numeri Romani con multipli di 5: Alfabeto: I V X L C D (500) M (1000) Si minimizza numero di simboli ad es:

I II III IV V …. XL (40) …. MCCLXXI (1271)…. Problema con numeri > 4000:

Ad es. MMMMMMMMMMMM… Operazioni? Abaco!!

Codifica in base N La generalizzazione della codifica

decimale consiste nell’utilizzare un alfabeto con N cifre e ragionare quindi su base N Binaria: 2 cifre, potenze di 2 Ottale: 8 cifre, potenze di 8 Esadecimale: 16 cifre, potenze di 16 Base N: N cifre, potenze di N Numero di cifre per rappresentare un numero

)1(log mN

Da numero a codifica Dato M la sua codifica posizionale

in base N si estrae utilizzando la divisione con resto come segue M = A1*N +B1 A1= A2*N + B2 …. Ak-1=Ak*N + Bk Cod(M,N) = Ak Bk … B1

Esempio Base 2:

Cod(13,2) = 1 1 0 1 = 1*8+1*4+1 13 : 2 = 6 con resto 1 6 : 2 = 3 con resto 0 3 : 2 = 1 con resto 1

Base 8: Cod(13,8) = 1 5 = 1*8 + 5*1 13 : 8 = 1 con resto 5

Esempio di cambio di base Per passare dalla base 2 alla base 8:

raggruppo gruppi di 3 bit! Per passare dalla base 8 alla base 2:

Espando cifre in gruppi di tre bit Esempio:

001 101 (binario) 1 5 (ottale)

Codifica degli interi La codifica in binario dei numeri naturali permette di

utilizzare operazioni bit-a-bit per implementare operazioni aritmetiche quali la somma e la moltiplicazione

0 1 1 0 1 + 0 1 0 0 1 = 1 0 1 1 0

Vorremmo ottenere la stessa cosa nel caso di numeri interi!

Bit di segno Complemento a 1 e complemento a 2

Bit di segno Bit di segno: fissiamo il numero di cifre il primo

bit a sinistra identifica il segno Su un byte (8 bit):

00000001 = 1 10000001 = -1

Algoritmo per la somma? Occorre una analisi dei possibili casi a seconda del

segno degli operandi non si riduce in modo semplice ad operazioni bit-a-

bit, peccato!

Complemento a 1 Su K bit

il primo a sinistra identifica il segno il valore assoluto viene rappresentato invertito dopo

aver negato i singoli bit Es. 00000010 = 2 mentre 11111101 = -2

Somma bit a bit? Funziona quasi sempre

Se operandi hanno segno negativo si ottiene il risultato decrementato di 1! (Es. –12 invece di –11)

Nota: zero ha due rappresentazioni: 00000000 e 11111111!

00110+ (+6)10101= (-5)11011 (-4)

11001+ (-6)11010= (-5)10011 (-12)

Complemento a 2 Su K bit

il primo a sinistra identifica il segno il valore assoluto viene rappresentato invertito dopo

aver negato i singoli bit Infine si somma la costante 1 al modulo 00000010 = 2 11111110 = 11111101+1= -2

Operazioni per rapp. in complemento a 2

Somma bit a bit? Funziona sempre

Nota: zero ha una sola rappresentazione: 00000000

11010+ (-6) dove 6=0110 1001 + 1 = 1010

11011= (-5) dove 5=0101 1010 + 1 = 1011

10101 (-11) dove11=1011 0100+1 = 0101

Rappresentazione per eccesso a 2**(N-1)

Un’altra possibile rappresentazione di numeri interi consiste nel suddividere il range di valori rappresentabili su N bit in numeri positivi e numeri negativi: (**=elevamento a potenza)

Le codifiche da 0 a (2**N-1)-1 rappresentano i numeri negativi da –(2**(N-1)) a –1

2**(N-1) rappresenta lo zero

Le rimanenti codifiche rappresentano:i numeri positivi da +1 a +(2**(N-1))-1

Codifica e decodifica Codifica di M:

Cod(M+2**(N-1),2)

Decodifica M: M=Cod(N,2) Dec(M)=N-2**(N-1)

Esempio Per N=3 il range di valori –4…0…3

000 rappresenta –4 001 rappresenta –3 …. 010 rappresenta 0 … 111 rappresenta 3

Codifica/decodifica -3 = Cod(-3+4,2)=Cod(1,2)=001 3 = Cod(3+4,2)=Cod(7,2)=111 111=Cod(7,2) e quindi Dec(111)=7-4=3

Numeri Razionali Utilizzando opportune convenzioni

possiamo pensare di rappresentare non solo interi ma anche razionali Virgola fissa: si fissa il numero di cifre della

parte decimale Virgola mobile: si rappresentano esponente

e mantissa (Virgola= notazione all’inglese!)

Virgola fissa Fissiamo quante cifre intere e quante decimali

vogliamo rappresentare ed utilizziamo potenze di 2 sia positive che negative!

Ad esempio: se la cifra piu’ a destra rappresenta ½ (=2**-1):

10001 rappresenta 8.5 = 8 + ½ cioe’ va letto come: 1000.1 !!

Si rappresentano solo valori divisibili per potenze negative di 2 (occorre approssimare gli altri valori)

Virgola Mobile Se vogliamo rappresentare sia numeri molto

piccoli che numeri molto grandi occorre utilizzare una rappresentazione in cui la virgola decimale varia a seconda del numero

Si usa una rappresentazione del tipo: Valore= 2**(+/- Esponente)+Mantissa La mantissa viene normalizzata per ottenere una

rappresentazione unica (varia tra 1 e ½). Cioe’ dobbiamo memorizzare su K bit le

informazioni su: Segno Esponente Mantissa

Standard IEEE Precisione singola su 32 bit

1 bit di segno 8 di esponente (da -126 a +127) 23 di mantissa Si possono rappresentare valori fino a 2**(-150)

Precisione doppia su 64 bit 1 bit di segno 11 di esponente (da -1022 a +1023) 52 di mantissa Si possono rappresentare valori fino a 2**(-1075)