LEZ01codifica - ICAR-CNR

La rappresentazione delle
informazioni
Che cosa è un’informazione?
"Per la teoria dell'informazione è abbastanza facile identificare alcune
delle ipotesi che la sorreggono e che riguardano il mondo degli eventi
fisici di cui essa fornisce un modello. […]
In questo mondo ciò che conta non sono gli oggetti, ma le differenze tra
gli oggetti e l'informazione sta nelle differenze che generano altre
differenze."
G. Longo, Teoria dell'informazione, Boringhieri, p. 18
Aspetti dell’informazione
Quando abbiamo a che fare con informazione
di qualunque tipo distinguiamo:
 contenuto (messaggio/significato)
 modalità espressiva (codifica/significante)

supporto materiale
Il numero dieci
10 (dieci nella numerazione araba)
X (dieci nella numerazione romana)
    
    
10
Analogico versus digitale
Omino perplesso
Analogico versus digitale: una
definizione

Analogico: basato sulla similitudine tra il
mezzo di rappresentazione e l'informazione
rappresentata

Digitale: basato su una rappresentazione
simbolica (discreta) dell'informazione
Esempi



Orologio a lancette/ orologio a cifre
il disco di vinile/ il CD
il telefono tradizionale/ la linea ISDN
Codifica di informazioni discrete
A = alfabeto = insieme finito di simboli = {a,b,c,…}
parola = sequenza finita di simboli di A = 1 … n
esempio: “aabcedc” è una parola di n = 7 simboli
informazioni
codifica
A* = insieme
di tutte le parole
finite su A
Esempio: codifica binaria A = {0,1}
La lampadina è
spenta
accesa
0
1
Siamo in
primavera
estate
autunno
inverno
00
01
10
11
Quante informazioni posso
rappresentare con n simboli di un
alfabeto di k simboli?
Quante sono le parole di lunghezza n se A ha k
simboli?
Data la parola s = x1 … xn-1 esistono k parole della
forma
x1 … xn-1 y con y A
perciò se le parole di lunghezza n-1 sono m, allora
quelle di lunghezza n
sono m  k.
Facendo variare m:
m
= 1 allora k;
m
= 2 allora k  k; …
in generale, se m = n
k  …  k (n volte) = kn
In conclusione: con un alfabeto di k simboli posso
rappresentare kn informazioni con parole di lunghezza n
Esercizio

L’alfabeto A contine i simboli a, b, c: quante
informazioni posso codificare con parole di
lunghezza 4?
34 = 81
Rappresentazione delle informazioni
all’interno degli elaboratori

L’entità minima di informazione all’interno di un elaboratore
prende il nome di bit (binary digit - cifra binaria). Mediante
un bit possiamo rappresentare due informazioni

Rappresentazione binaria (o digitale). Il linguaggio di base
mediante il quale ogni informazione deve essere codificata è
costituito da due soli simboli:
(0 e 1)
Le ragioni di questa scelta sono prevalentemente di tipo
tecnologico, infatti i due simboli corrispondono a:
due stati di polarizzazione di una sostanza
magnetizzabile;
 due stati di carica elettrica di una sostanza;al
passaggio/non passaggio di corrente attraverso un cavo
conduttore;
 al passaggio/non passaggio di luce attraverso un cavo
ottico

Unità di Misura: bit, Byte, …
1 bit
= parola su {0,1} di lunghezza unitaria
1 byte
= parola su {0,1} di lunghezza 8
1 Kbyte = 210 = 1024 byte
1 Mbyte = 1024 Kbyte (un milione di byte circa)
1 Gbyte = 1024 Mbyte (un miliardo di byte circa)
1 Tbyte = 1024 Gbyte (mille miliardi di byte circa)
Codifica binaria
Con 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

k
2
3
4
5
6
7
8
9
16
17
32
33
log2k
1
2
2
3
3
3
3
4
4
5
5
6
Esercizio

Quanti bit sono necessari per codificare i
giorni della settimana?

I giorni della settimana sono 7: ho bisogno di
3 bit
La codifica dei caratteri

L’obiettivo è quello di comunicare con il calcolatore usando il nostro
linguaggio. Dobbiamo rappresentare le lettere dell’alfabeto

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)
La codifica dei caratteri: Il codice ASCII
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
0001000
0001001
0001010
0001011
0001100
0001101
NUL
SOH
STX
ETX
EOT
ENQ
ACK
BEL
BS
HT
NL
VT
NP
CR
0001110
0001111
0010000
0010001
0010010
0010011
0010011
0010101
0010110
0010111
0011000
0011001
0011010
0011011
SO
SI
DLE
DC1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
0011100
0011101
0011110
0011111
0100000
0100001
0100010
0100011
0100100
0100101
0100110
0100111
0101000
0101001
FS
GS
RS
US
SP
!
"
#
$
%
&
'
(
)
La codifica dei caratteri: Il codice ASCII
0101010
0101011
0101100
0101101
0101110
0101111
0110000
0110001
0110010
0110011
0110100
0110101
0110110
0111000
*
+
,
.
/
0
1
2
3
4
5
6
8
0111001 9
0111010 :
0111011 ;
0111100 <
0111101 =
0111110 >
0111111 ?
1000000 @
1000001 A
1000010 B
1000011 C
1000100 D
1000101 E
1000110 F
1000111 G
1001000 H
1001001 I
1001010 J
1001011 K
1001100 L
1001101 M
1001110 N
1001111 O
1010000 P
1010001 Q
1010010 R
1010011 S
1010100 T
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 0
Codifica della parola cane
01100011 01100001 01101110 01100101
c
a
n
e
Problema inverso: decodifica
quale 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
01101001 01101100 00000000 01110000 01101111 00101110
01101001 01101100 00000000 01110000 01101111 00101110
i
l
P
o
.
Altri formati

ECBDIC formato alternativo a 8 bit

UNICODE nuovo standard a 16 bit contiene
simboli per la maggiorparte degli alfabeti
esistenti (compreso arabo, giapponese,
etc…)
Esercizio

Un testo di 400 caratteri occupa 1600 bit,
quanti caratteri ha l’alfabeto?

Ogni carattere occupa 1600/400 = 4 bit
con 4 bit posso codificare 24 = 16 caratteri

Rappresentazione dei numeri

La numerazione decimale utilizza una notazione
posizionale basata sul numero 10. La sequenza “234”
rappresenta il numero
4 x 100 + 3 x 101 + 2 x 102

La notazione posizionale può essere utilizzata in qualunque
altro sistema di numerazione (con base diversa da 10)
Sistemi di numerazione
Fissata una base B > 1
cn cn-1 … c1 c0
dove ciascun ci < B, rappresenta il numero
r = c0  B0 + c1  B1 +… + cn-1  Bn-1 + cn  Bn
Basi usate comunemente

Base decimale B = 10:
valori 0,1,2,3,4,5,6,7,8,9

Base binaria B=2:
valori 0,1

Base ottale B=8:
valori 0,1,2,3,4,5,6,7

Base esadecimale B=16:
valori 0,1,…,9,A,B,C,D,E,F
Sistema di numerazione binaria
Nel caso binario la sequenza
cn cn-1 cn-2... c1 c0
(ogni “ci” è la cifra “0” o la cifra “1”) rappresenterà il
numero
c0 x 20 + c1 x 21 + ... cn-1 x 2n-1 + cn x 2n
La sequenza “1011” in base 2 denota il numero
1 x 20 + 1 x 21 + 0 x 22 + 1 x 23 = 11
(in base 10)
Per evitare ambiguità si usa la notazione
10112 = 1110
Metodo di conversione da base 10 a base 2
Dato k = c0 x 20 + c1 x 21 + ... cn-1 x 2n-1 + cn x 2n
siano m il quoziente di k diviso 2 e r il resto,
hai che
m = c1 x 20 + ... cn-1 x 2n-2 + cn x 2n-1
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 diventa 0
Esempio
2210
22 = 2  11 + 0
11 = 2  5 + 1
5=22 +1
101102
2=21 +0
1=20 +1
101102 = 1  24 + 0  23 + 1  22 + 1  21 + 0  20 = 2210
Rappresentazione di un numero intero
Consideriamo la base dieci: con tre cifre decimali si possono
rappresentare i numeri compresi tra 0 e 999, il numero
successivo (1000) richiede una quarta cifra di cui non
disponiamo
In questo caso si dice che 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-1
Consideriamo 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
Esempio: numero
rappresentazione
0
1
2
3
4
5
6
7
000
001
010
011
100
101
110
111
Aritmetica binaria
0 + 0 = 0 con riporto 0
0 + 1 = 1 con riporto 0
1 + 0 = 1 con riporto 0
1 + 1 = 0 con riporto 1
1101
111
101 +
11 =
1000
11=
1101
1101
100111
Overflow nelle operazioni
2+
3=
___
5
010 +
011 =
______
101
5+
4=
___
9
101 +
100 =
______
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
Rappresentazione dei numeri

Lo stesso numero può essere codificato in modi diversi:
ASCII: 37 00110011 00110111
3
7
BINARIA: 37 00100101 (1 byte)

Il primo modo è usato per le comunicazioni con l'esterno
(input/output: ingresso/uscita)

Il secondo modo è usato all'interno (per fare i calcoli)
non è possibile usare direttamente le codifiche ASCII:
Esempio: Numero
ASCII
3+
00110011
2=
00110010
---------------e
01100101
 Esistono dei programmi di conversione che
trasformano i numeri da una codifica all'altra
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
Rappresentazione di numeri grandi
Esempio: supponiamo di avere a disposizione solo 2 byte di
dover memorizzare 23.077.130
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)
1° BYTE
2° BYTE
0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1
ESPONENTE
MANTISSA
Codifica standard a 32 bit
1 bit per il segno dell’esponente
 1 bit per il segno della mantissa
 10 bit per il valore assoluto dell’esponente
 20 bit per il valore assoluto della mantissa

Uso di hardware specializzato per operazioni con floating
point: coprocessore matematico