Codici e informazioni
Informazione è un qualunque insieme di segnali
che condizionano l’evoluzione di un sistema.
Nel mondo dell’informatica per informazione
intenderemo, in modo più restrittivo, tutto ciò che
può essere rappresentato tramite opportune
sequenze di simboli in un alfabeto prefissato.
La scelta della rappresentazione dei dati deve
consentire di gestire, elaborare e memorizzare le
informazioni in modo agile.
1
Codici e informazioni
Un codice C è un insieme di parole composte da
simboli di un alfabeto  (che chiameremo alfabeto
supporto di C).
La rappresentazione o codifica di un insieme di
informazioni I in un dato codice C è una funzione
f:IC, ossia è una legge che associa ad ogni
informazione che si intende rappresentare una
opportuna parola del codice C.
In modo analogo la decodifica è una funzione g
avente per dominio C e per codominio I.
2
Codici e informazioni
°Alfabeto 
°C: insieme di parole sull’alfabeto
°I: insieme di informazioni (parole di C)
°Funzioni di codifica e decodifica tra insiemi
diversi di informazioni
°Composizione di codifica e decodifica:
l’identità
°Codifica (o decodifica) non ambigua:
iniettività
3
Esempi
Codice in chiaro (codice in cui non vi è l’intenzione
di proteggere il contenuto del messaggio)
 = 26 lettere dell’alfabeto
I = insieme degli animali domestici
C=insieme delle parole del vocabolario che
corrispondono ai vari animali domestici.
Codice non in chiaro-Cifrario di Cesare
Funzione di codifica: f:ii+3(mod 26), i=0,1,…,25
dove al numero 0 corrisponde la lettera a, al numero
1 la lettera b..
In base a tale cifrario, è facile verificare che “babbo”
è codificato come “edeer”.
4
Alfabeto, sintassi, semantica
• Alfabeto dei simboli
• Regole di composizione (sintassi) che
definiscono la sequenza di configurazioni
ammissibili( vanno a creare I)
• Codice (semantica): insieme di regole che ad
ogni configurazione ammissibile associa un’entità
di informazione
• Lo stesso alfabeto può essere usato con codici
diversi.
5
Numeri naturali
Consideriamo
un
particolare
tipo
di
informazione, quella che specifica il valore di
un numero naturale:
0,1,2,3,4…..
Attenzione: analogamente agli altri tipi di
informazione va fatta una distinzione tra il
concetto o significato di numero (numero) e la
sua rappresentazione o codifica in un qualche
codice (numerale).
6
Numeri e numerali
• Numero: entità astratta
• Numerale: stringa di caratteri che rappresenta
un numero in un dato sistema di numerazione
• Lo stesso numero è rappresentato da
numerali diversi in diversi sistemi.
• Il numero di caratteri del numerale determina
l’intervallo dei numeri rappresentabili.
• Un numerale rappresenta un numero solo se
si specifica un sistema di numerazione
• Lo stesso numerale rappresenta diversi
numeri in diversi sistemi.
7
Rappresentazioni dei numeri
• posizionali: ogni cifra ha un peso
• le più usate: decimale, binaria,
esadecimale, ottale
• non posizionale: romana, italiano…
8
Posizionale in Base 10
°Alfabeto decimale:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
°esempio:
3271 =
(3x103) + (2x102) + (7x101) + (1x100)
Ad ogni simbolo è associato un peso
diverso a seconda della posizione che
occupa.
9
Numeri: la notazione posizionale
°Base B (è un numero) => ho B simboli:
• Base 10 (Decimale): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Base 2 (Binaria): 0, 1
°Rappresentazione di numeri:
• Un numero naturale può essere espresso con una
sequenza di m cifre ci in base b dove le cifre
denotano un insieme di b simboli che
corrispondono ai primi b numeri naturali.
m 1
i
• Vale la relazione N=  ci b
i 0
Esempio
1011010 = 1x26 + 0x25 + 1x24 + 1x23 + 0x22 +
1x2 + 0x1 = 64 + 16 + 8 + 2 = 90
10
Conversione da una rappresentazione a
un’altra
Dato un numero rappresentato in base a, come
è possibile ottenere la sua rappresentaziuone
in base b?
L’algoritmo per effettuare il cambiamento di base
dalla base a alla base b consiste
semplicemente nel dividere il numero N
espresso in base a per b finchè il quoziente
non risulti uguale a 0. I resti ottenuti
(ovviamente compresi tra 0 e b-1) costituiscono
le cifre del numero N codificato in base b.
Attenzione: rappresentazione e numero sono
due cose diverse….
11
Il principio di funzionamento di un computer si basa
sulla logica binaria.
Per comprenderne l'idea di base, possiamo
pensare a un interruttore, che può essere aperto o
chiuso, o ad una scheda che può essere forata o
meno in un punto, o ad un suono che può essere
presente o no, o ancora ad una riflessione ottica
che può verificarsi o meno.
12
Bit
Ciò che accomuna tutti questi fenomeni è la
caratteristica di poter assumere solamente due
stati:
0 = aperto
1 = chiuso
Questa variabile che assume solo due stati (0 e
1) si chiama bit ("binary digit", cifra binaria) ed è
l'unità minima di informazione e la base
dell'algebra binaria.
13
Byte
Un
computer
"ragiona"
unicamente
interpretando gruppi di bit, cioè comandi
rappresentati da sequenze di "uno" e di "zero"
(per esempio, 00101100).
Convenzionalmente, 8 bit costituiscono 1 byte.
14
Numerazione binaria
Affiancando un sufficiente numero di bit è possibile
rappresentare qualunque numero.
Ogni posizione rappresenta una potenza crescente
di 2:
27 26 25 24 23 22 21 20
1
0
0
1
0
1
1
0
= 128*1 + 64*0 + 32*0 + 16*1 + 8*0 + 4*1 + 2*1 + 1*0 =
150 decimale
Questo procedimento consente di convertire un
numero binario in decimale
15
Numerazione binaria
Il procedimento inverso (da decimale a binario), si
ottiene dividendo i resti per le potenze di 2:
150/128=1
r:22/64=0
r:22/32=0
r:22/16=1
r:6/8=0
r:6/4=1
Gli stessi principi valgono per
qualunque BASE di
numerazione.
r:2/2=1
r:0
16
Ancora conversione
In modo più semplice, è sufficiente dividere il
numero di partenza per la base di destinazione,
tante volte finché il quoziente si annulla.
Il resto delle divisioni letto in senso inverso è il
numero nella base di destinazione.
Ad es:
810
(?)2
810=10002
17
Numerazione ottale
In ambito informatico rivestono
particolare rilevanza altre due
numerazioni: quella ottale, che utilizza
solo 8 cifre (da 0 a 7),
84
83
82
81
80
3
7
0
4
5
che in decimale è =
4096*3+512*7+64*0+8*4+5 = 15909
18
…ed esadecimale
E la numerazione esadecimale, che utilizza 16
cifre (da 0 a 9 e le lettere da A a F) che
corrispondono ai valori da 0 a 15 decimali.
163
2
162
5
161
E
160
F
che in decimale è = 4096*2+256*5+16*14+15 =
9711
Per la conversione inversa da decimale a
ottale (o esadecimale) si utilizza lo stesso
metodo di divisione dei resti visto per la
numerazione binaria.
19
Confronti
20
CONVERSIONE TRA BASI
Essendo le basi 8 e 16 potenze di 2, esiste un
meccanismo semplice di conversione tra
esse e la base 2:
Per i numeri ottali è sufficiente suddividere il
numero binario in gruppi di 3 bit (a partire da
destra) e convertire ogni singolo gruppo nel
corrispondente ottale:
1 0 1 1 1 0 1 0 0 = 5 6 4 ottale
Per i numeri esadecimali è sufficiente
suddividere il numero binario in gruppi di 4
bit (a partire da destra) e convertire ogni
gruppo nel corrispondente esadecimale:
1 0 1 0 0 0 1 1
= A 3 esadecimale
21
Quali codici esistono per i computer?
°Binario….
bit
°ASCII
caratteri
°Esadecimale
byte...
I codici che usiamo sono a lunghezza
fissa: numero fisso di “posizioni”
Tutte le posizioni vengono usate
Perché? Discutiamone
22
Codifica binaria dell’informazione
• Con parole binarie composte da k bit è
possibile codificare 2K oggetti diversi.
• Passando da una parola binaria a k bit ad una
a k+1 bit si raddoppia il numero di oggetti
rappresentabili (2K+1).
•Raddoppiando il numero di bit (da k a 2k) il
numero di oggetti rappresentabili aumenta
esponenzialmente (22k).
•Per codificare N oggetti servono circa log2N bit.
23
Che cosa facciamo con i numeri?
° Le solite cose!
•
•
•
•
•
Addizioni
Sottrazione
Moltiplcazioni
Divisioni
Confronti
° Esempio:
10 + 7 = 17
+
1 1
1 0
1
0
0
1
1
1
------------------------1
0
0
0
1
• Se ho numeri binari…. circuito
24
Che base usare?
°Decimale? Va bene per noi
°Esadecimale? Rappresentazione
compatta di numeri binari
• Terribile da usare sulla carta
°Binaria: quella che usano i computer
impareremo come un computer fa +,-,*,/
• Per un computer, i numeri sono sempre
binari
• Comunque siano scritti:
3210 == 0x20 == 1000002
• usiamo “ten”, “hex”, “two” se ci sono
confusioni
25
Ci sono dei limiti?
°I bit possono rappresentare tutto!
°Caratteri?
• 26 lettere => 5 bits
• minuscole/maiuscole + punteggiatura
=> 7 bits (in 8) (“ascii”)
• Unicode: codice standard che copre tutte le
lingue del mondo (i simboli) => 16 bits
°Valori logici? 0 -> Falso, 1 => Vero
°Ma: N bits => si possono rappresentare
solo 2N cose
26
Come rappresento I numeri negativi?
°Fino ad ora, numeri senza segno
°Soluzione ovvia: il bit più a sinistra
rappresenta il segno!
• 0 => +, 1 => • Gli altri: il valore assoluto
°MIPS usa interi a 32-bit. +1ten sarebbe:
0000 0000 0000 0000 0000 0000 0000 0001
°E - 1ten invece:
1000 0000 0000 0000 0000 0000 0000 0001
27
Problemi…
°Per sommare (e fare altre operazioni) ho dei
circuiti….
• A seconda del segno devo fare cose particolari…
°Poi, due zero
• 0x00000000 = +0ten
• 0x80000000 = -0ten
• utile? Cosa potrebbe significare?
°Forse non è la rappresentazione più
conveniente….
28
Rappresentazione degli interi
°Devo rappresentare positivi e negativi
°Ho il problema del segno:
°Soluzione semplice: aggiungo un bit
per il segno
• Problematiche le operazioni… complicate
°Soluzioni alternative:
• Complemento a 1
• Complemento a 2
• Le altre le vedremo in seguito…
29
riassunto delle domande a cui bisogna
saper rispondere
°conversione tra basi
• perchè funziona in quel modo?
°problema della rappresentazione dei
numeri interi relativi:
• complemento a 1
- Come funziona e perchè
• complemento a 2
- Come funziona e perchè
30