Premessa
Elementi di Informatica e
Programmazione
Nella prima lezione è stato presentato il concetto astratto di
calcolatore: non com’è fatto o come funziona, ma che cos’è in sé
La Codifica dell’informazione
Concetto di problema (classe di domande omogenee, alle quali si
possa dare risposta con una procedura uniforme), istanza, soluzione
Concetto di algoritmo (specifica attraverso una sequenza di istruzioni
come produrre una soluzione per ogni istanza)
Il calcolatore come esecutore universale di algoritmi
(parte 1)
Corsi di Laurea in:
Ingegneria Civile
Ingegneria per l’Ambiente e il Territorio
Ora cominciamo a esaminare come “in pratica” i calcolatori attuali
sono costruiti, quali sono le loro componenti e le rispettive funzioni
Cominciamo da un sistema di elaborazione elementare
Università degli Studi di Brescia
Docente: Daniela Fogli
Daniela Fogli – Elementi di Informatica e Programmazione
2
Funzionamento dell’architettura di
Von Neumann
Architettura di Von Neumann
Si basa sui seguenti principi:
Dati e istruzioni del programma da eseguire sono
memorizzati nella memoria centrale
Il processore (CPU) legge e scrive in memoria per
acquisire le istruzioni da eseguire e i relativi dati e per
memorizzare i risultati delle istruzioni eseguite
Le istruzioni vengono acquisite ed eseguite dalla CPU in
modo sequenziale
CPU
ambiente
Dispositivi
di I/O
1. Reperimento dell’istruzione da eseguire
2. Interpretazione dell’istruzione
3. Esecuzione dell’istruzione
Memoria
NOTE: CPU = Central Processing
Unit (Unità centrale) detta oggi
Microprocessore o processore
Le singole operazioni necessarie per l’esecuzione delle
istruzioni sono scandite da un orologio di sistema (clock)
che definisce l’evolvere del tempo all’interno della macchina
Bus di sistema
Daniela Fogli – Elementi di Informatica e Programmazione
3
Daniela Fogli – Elementi di Informatica e Programmazione
4
Bus
Programma e dati in memoria
Indirizzo
In memoria
viene caricata la
forma binaria
del programma
0
1
…
0101011110011001
1101011110011111
0111000000011001
1101011100011101
0110011110011001
0101000111011000
1010011110011001
0101111110000000
0101010010011001
0111000000011001
0101000111011000
0101111110000000
Insieme di collegamenti (linee) che permettono di
trasferire dati da più sorgenti a più destinazioni
(componenti del calcolatore)
zona della
memoria che
contiene le
istruzioni
Il bus può essere suddiviso funzionalmente in:
Bus dati (trasferisce i dati scambiati tra componenti)
Bus indirizzi (trasferisce gli indirizzi della memoria o
delle interfacce di ingresso-uscita coinvolte nel trasferimento)
Bus comandi o “di controllo” (trasferisce segnali di controllo
che regolano le operazioni del sistema di elaborazione)
zona della
memoria che
contiene i dati
zona “libera”
MEMORIA
NB: non distinguibili in sé, è il
“programma” che ne stabilisce
il significato …
Daniela Fogli – Elementi di Informatica e Programmazione
5
… fine della premessa …
Daniela Fogli – Elementi di Informatica e Programmazione
6
Il concetto di informazione e supporto
Informazione: entità che può essere comunicata
Non può esistere informazione senza supporto fisico: mezzo
su cui l’informazione può essere memorizzata e attraverso
cui può essere trasmessa
...
Il CD in cui è memorizzato
Un brano musicale
Programmi, dati, risultati, indirizzi
sono informazioni …
Ora vediamo come si RAPPRESENTANO
nel calcolatore
Daniela Fogli – Elementi di Informatica e Programmazione
L’aria attraverso cui viene
trasmesso
…
7
Daniela Fogli – Elementi di Informatica e Programmazione
8
Proprietà di un supporto
Codice
Il supporto deve poter assumere configurazioni differenti
altrimenti non è in grado di portare informazione
Ad ogni configurazione viene associata una differente entità di
Successione di
simboli
informazione
Il caso più semplice: 2 configurazioni possibili
Esempi: interruttore acceso/spento, tensione sì/no, circuito
Entità di
informazione
E’ necessario un codice:
aperto/chiuso
un insieme di regole che
stabiliscono le associazioni
fra configurazioni e entità di
informazione
Elemento di informazione rappresentato dalla configurazione del
supporto (es. soccorso sanitario: )
Associazione simboli-significati: convenzione semantica
Es. di convenzione semantica alternativa: soccorso sanitario: Daniela Fogli – Elementi di Informatica e Programmazione
Attività di
interpretazione
Daniela Fogli – Elementi di Informatica e Programmazione
9
Esempio di codice
10
Codifica e Decodifica
Codifica = operazione con cui l’informazione viene
Attraverso il codice si attribuisce un significato
convenzionale a ciascuna configurazione che il supporto
può assumere
scritta (su un supporto fisico)
Decodifica = operazione con cui l’informazione viene
letta (da un supporto fisico)
ES., 2 dadi
•
•
•
•
⇒ lettera A
codifica
Il numero “dieci”
Informazione
⇒ lettera B
•
….
10
Daniela Fogli – Elementi di Informatica e Programmazione
11
decodifica
Daniela Fogli – Elementi di Informatica e Programmazione
Supporto
fisico
12
Codifica dei dati e delle istruzioni
Codifica binaria
Poiché il nostro esecutore utilizza componenti a 2
soli stati, è in grado di riconoscere solamente
sequenze di 0 e 1
Alfabeto binario = {0, 1} dove 0 e 1 sono dette cifre
binarie o BIT (Binary digIT)
Importanza tecnologica:
Programma = istruzioni che operano su dati
Istruzioni e dati devono essere rappresentate (codificate)
secondo il linguaggio noto all’esecutore
L’esecutore deve essere infatti in grado di memorizzare e
manipolare istruzioni e dati
Nel caso del calcolatore, istruzioni e dati vengono codificati
come sequenze di 0 e 1
Daniela Fogli – Elementi di Informatica e Programmazione
Dispositivi a due stati (livelli di tensione, magnetizzazione, …)
Semplicità di realizzazione – Affidabilità
“Tutti” i calcolatori elettronici e i dispositivi magnetici di
memorizzazione utilizzano tale corrispondenza
13
Bit, Byte, KiloByte, MegaByte,...
Daniela Fogli – Elementi di Informatica e Programmazione
14
Il problema della rappresentazione
Bit = ‘0’ oppure ‘1’
Byte = 8 bit = 23
Insieme di simboli
disponibili nel
calcolatore = {0, 1}
Insieme di “oggetti”
che vogliamo
rappresentare
KiloByte (KB) = 210 byte = 1.024 byte
MegaByte (MB) = 220 byte = 1.048.576 byte
GigaByte (GB) = 230 byte = 1.073.741.824 byte
TeraByte (TB) = 240 byte = …
PetaByte (PB) =
ExaByte (EB) =
250
260
Problema:
assegnare un codice univoco a tutti
gli oggetti compresi in un insieme
byte = …
byte = …
Ho n oggetti da codificare e 2 soli simboli, quanto è la lunghezza k
delle sequenze di simboli?
Oppure: dispongo di sequenze di lunghezza k di simboli 0 e 1, quanto è
il numero n di oggetti che posso codificare?
Daniela Fogli – Elementi di Informatica e Programmazione
15
Daniela Fogli – Elementi di Informatica e Programmazione
16
Codice binario a n bit
Codifica binaria
• Funzione:
- dominio (insieme di oggetti da rappresentare)
- codominio: insieme di tutte le possibili sequenze di n bit
Se k = 1
• Funzione biunivoca tra il dominio e la sua immagine,
detta insieme delle codifiche
Se k = 2
• Esempio di codice binario a 3 bit:
Se k = 3
Posso codificare n=4 oggetti: 00, 01, 10, 11
Posso codificare n=8 oggetti: 000, 001, 010, 011, 100, 101,
110, 111
110
100
O1
011
O3
Qual è la regola???? (Ipotesi implicita: i codici hanno
tutti la stessa lunghezza)
101
O2
111
Posso codificare due oggetti (n=2): al primo assegno il codice
‘0’ e al secondo assegno il codice ‘1’
insieme delle
codifiche
001
010
dominio
codominio
000
Daniela Fogli – Elementi di Informatica e Programmazione
n = 2k
Daniela Fogli – Elementi di Informatica e Programmazione
17
k = log2n
Esempio: i mesi dell’anno
Se ho a disposizione sequenze di k = 5 bit, quanti
elementi posso codificare?
1 bit 2 gruppi
n = 25 = 32 elementi
Gennaio Febbraio
Marzo Aprile
Maggio Giugno
Luglio Agosto
Settembre Ottobre
Novembre Dicembre
Se n = 128, di quanti bit ho bisogno (k) per codificarli
tutti?
k = log2128 = 7
…e se n = 129???
Allora ho bisogno di 1 bit in più! Ottengo uno spreco di
configurazioni, perché con 8 bit posso codificare fino a
256 elementi
Daniela Fogli – Elementi di Informatica e Programmazione
18
Gennaio
Marzo
Maggio
Luglio
Settembre Ottobre
Novembre Dicembre
Luglio
Settembre
Novembre
0
Agosto 1
Gennaio 000
Febbraio 010
Marzo 001
Maggio
Aprile 011
Giugno
Luglio 100
Agosto 110
Settembre 101
Novembre
Ottobre 111
Dicembre
3 bit 8 gruppi
19
2 bit 4 gruppi
Gennaio Febbraio
Marzo
Aprile
Maggio Giugno
00
10
Gennaio 0000
Febbraio
Aprile
Giugno
Agosto
Ottobre
Dicembre
01
11
Febbraio 0100
0010
Aprile
0110
Maggio
0011
Giugno
0111
Luglio
1000
Agosto
1100
Settembre 1010
Ottobre
1110
Novembre 1011
Dicembre 1111
Marzo
4 bit 16 gruppi… mancano 4
configurazioni!
Daniela Fogli – Elementi di Informatica e Programmazione
20
Esempio: codifica BCD
Cifra
Codifica binaria
decimale
b
rappresentata 3 b2 b1 b0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
2
0
0
1
1
3
0
1
0
0
4
0
1
0
1
5
0
1
1
0
6
0
1
1
1
7
1
0
0
0
8
1
0
0
1
9
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
Tipologie di codici
Nel seguito vedremo tipologie di rappresentazioni
diverse:
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
codifiche
non usate
Daniela Fogli – Elementi di Informatica e Programmazione
Codici di compressione (senza | con perdita)
21
Tipologie di codici
22
Sistema di numerazione posizionale
Ad ogni cifra del numero è attribuito un peso a seconda
della sua posizione all’interno del numero
Nel seguito vedremo tipologie di rappresentazioni
diverse:
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
Sistema di numerazione posizionale in base b:
Numero Nb = ckck-1ck-2…c0.c-1c-2…cc-h
Dove ck è la cifra più significativa mentre c0 è la cifra meno
significativa (prima della virgola) (c-1 è quella più significativa
della parte frazionaria, c-h quella meno significativa)
Nb è il numero ottenuto facendo:
ckxbk+ck-1xbk-1+ck-2xbk-2…+c0xb0 +c-1xb-1+…+c-hxb-h
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
Esempio: b=10, il numero 3256.234
dove c3 = 3, c2 = 2, c1 = 5, c0 = 6, c-1=2, c-2=3, c-3 =4 rappresenta
3x103 + 2x102 + 5x101 + 6x100 + 2x10-1 + 3x10-2 + 4x10-3 =
= 3000 + 200 + 50 + 6 + 0.2 + 0.03 + 0.004
Codici di compressione (senza | con perdita)
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
23
Daniela Fogli – Elementi di Informatica e Programmazione
24
Le basi più comuni
Notazione Binaria
Base = 2
Se la base è b, allora le cifre che possono essere
utilizzate per comporre un numero vanno
Cifre: 0, 1
Numeri espressi nella forma
(an an-1 … a1 a0 . a-1 a-2 …)due
da 0 a b-1
[ai ∈ {0,1}]
il cui “valore” è
(an*2n + an-1*2n-1 + … + a0*20 + a-1 * 2-1 + a-2 *2-2 …)
Esempio: b = 10, cifre possibili: [0,1,2,3,4,5,6,7,8,9]
Esempio: b = 2, cifre possibili: [0,1]
Esempio: b = 8, cifre possibili: [0,1,2,3,4,5,6,7]
Esempio: b = 16, cifre possibili: [0,1,2,3,4,5,6,7,8,9,A,
B,C,D,E,F]
ESEMPIO
N = 101011.1011due
N = 1 — 25 + 0 — 24 + 1 — 23 + 0 — 22 + 1 — 21 + 1 — 20
+ 1 — 2-1 + 0 — 2-2 + 1 — 2-3 + 1 — 2-4 =
= 43.6875dieci
Daniela Fogli – Elementi di Informatica e Programmazione
25
Conversione binario ⇒ decimale
26
Domande
Come visto, la conversione si ottiene direttamente dalla
definizione stessa di numero binario
Scriviamo i numeri denotando la base attraverso il pedice:
es. 1101.1due
E’ facile convertirlo in un numero decimale facendo:
Il numero binario 101001011due è pari o dispari?
A quale numero decimale corrisponde?
101001011due = (1x28 + 0x27 + 1x26 + 0x25 + 0x24 + 1x23 + 0x22 +
1x21 + 1x20)dieci = (256 + 64 + 8 + 2 + 1)dieci = 331dieci
1101.1due = 1x23 + 1x22 + 0x21 + 1x20 + 1x2-1 = 8dieci + 4dieci + 0dieci +
+ 1dieci + 0.5dieci = 13.5dieci
Altri esempi:
10101.01due = 1x24 + 0x23 + 1x22 + 0x21 + 1x20 + 0x2-1 + 1x2-2 = 16 +
+ 4 + 1 + 0.25 = 21.25dieci
110010.001due= 1x25 + 1x24 + 0x23 + 0x22 + 1x21 + 0x20 + …+ 1x2-3 =
= 32 + 16 + 2 + 0.125 = 50.125dieci
1000001due = 1x26 + 0x25 + 0x24 + 0x23 + 0x22 + 0x21 + 1x20 = 64 + 1
= 65dieci
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
27
Daniela Fogli – Elementi di Informatica e Programmazione
28
Conversione decimale ⇒ binario
Conversione decimale ⇒ binario
metodo pratico
Regola pratica per convertire la parte intera
Usare lo stesso metodo visto prima è complesso!
Si noti che:
10dieci 2dieci
Esempio: 3dieci
345dieci = 11x101010 + 100x101001 + 101x10100 = …
ckck-1ck-2…c0 si può scrivere anche come ckck-1ck-2c1xb+c0
Ad esempio:
3256 = 325x10 + 6
325 = 32x10 + 5
32 = 3x10 + 2
3=0x10 + 3
… e poi bisogna fare le moltiplicazioni e l’elevamento a
potenza in base 2 e sommarne i risultati in base 2
Useremo un “metodo pratico”
In pratica, per “isolare” le cifre del numero, basta fare una serie
di divisioni per la base e tenere il resto
Dato un numero decimale N, innanzitutto distinguiamo parte intera
e la parte frazionaria: N = I.F (ES: dato 56.5dieci, convertiamo
separatamente 56 e 0.5)
Daniela Fogli – Elementi di Informatica e Programmazione
(in base b = dieci)
Alla fine, quando il numero è diventato 0, si leggono i resti
dall’ultimo al primo e si ottiene di nuovo il numero
Daniela Fogli – Elementi di Informatica e Programmazione
29
Conversione decimale ⇒ binario
30
Esempio di conversione da decimale
a binario
metodo pratico
Allo stesso modo, per convertire un numero decimale in un
numero binario basta fare una sequenza di divisioni (operazione
div) per la base 2 e prendere il resto (operazione mod)
137dieci = ?due
137 div 2 = 68 & 137 mod 2 = 1
Esempio:
56 div 2 = 28 & 56 mod 2 = 0 (cifra meno significativa del numero bin)
28 div 2 = 14 & 28 mod 2 = 0
14 div 2 = 7 & 14 mod 2 = 0
7 div 2 = 3 & 7 mod 2 = 1
3 div 2 = 1 & 3 mod 2 = 1
1 div 2 = 0 & 1 mod 2 = 1 (cifra più significativa del numero bin)
Si ottiene 111000due = 32dieci + 16dieci + 8dieci + 0 + 0 + 0 = 56dieci
68 div 2 = 34 &
68 mod 2 = 0
34 div 2 = 17 &
34 mod 2 = 0
17 div 2 = 8
&
17 mod 2 = 1
8 div 2 = 4
&
8 mod 2 = 0
4 div 2 = 2
&
4 mod 2 = 0
2 div 2 = 1
&
2 mod 2 = 0
1 div 2 = 0
&
1 mod 2 = 1
Si legge dal
basso verso
l’alto !!!
Risultato = 10001001due
Esercizio: riconvertire il risultato in decimale
Daniela Fogli – Elementi di Informatica e Programmazione
31
Daniela Fogli – Elementi di Informatica e Programmazione
32
Errore Tipico (1)
81
40
20
10
5
2
1
0
1
0
0
0
1
0
1
Errore Tipico (2)
88
44
22
11
5
2
1
E’ un errore considerare la prima cifra
ottenuta come la più significativa
otterrei 1000101 che vale 69!
Daniela Fogli – Elementi di Informatica e Programmazione
NB: se si è colti dal dubbio, ricordare che la prima cifra
significativa in questo caso vale sempre 1
33
34
Basta fare una sequenza di moltiplicazioni per 2 e prendere la
parte intera di ciascun prodotto dalla cifra più significativa a quella
meno significativa
Esempio: 0.587dieci binario?
F = a-1*b-1 + a-2*b-2 + ....... + a-n*b-n (dove b è la base)
F * b = a-1 + a-2*b-1 + ....... + a-n*b-(n-1)
la parte intera è a-1
(F*b - a-1) * b = a-2 + ....... + a-n*b-(n-2)
la parte intera è a-2
...
.
0.587 x 2 = 1.174: p.f. 0.174, parte intera 1 (cifra più significativa)
0.174 x 2 = 0.348: p.f. 0.348, parte intera 0
0.348 x 2 = 0.696: p.f. 0.696, parte intera 0
0.696 x 2 = 1.392: p.f. 0.392, parte intera 1
0.392 x 2 = 0.784: p.f. 0.784, parte intera 0
0.784 x 2 = 1.568: p.f. 0.568, parte intera 1
….
Es. con b = 10, sia F=.53
Le 3 cifre che
costituiscono il
numero
Si ottiene 0.10010due con 5 cifre binarie dopo la virgola, oppure
0.100101due con 6 cifre binarie dopo la virgola, oppure…
In ogni caso c’è un’approssimazione
Ma a noi interessa che la base di arrivo sia la base 2 …
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
Conversione da decimale a binario
della parte frazionaria
Regola pratica per convertire la parte
frazionaria
la parte intera è 5
la parte intera è 3
la parte intera è 1
E’ un errore fermarsi quando si ottiene
1 come dividendo
otterrei 011000 (24) anziché 1011000 (64+24)
NB: se si è colti dal dubbio, ragionare: se continuassi il
procedimento di divisioni successive aggiungerei zeri; questi
“non pesano” solo se corrispondono alle posizioni più
significative ( 0…0xyz ) !
.531 x 10 = 5 + .31
.31 x 10 = 3 + .1
.1 x 10 = 1
0
0
0
1
1
0
35
Daniela Fogli – Elementi di Informatica e Programmazione
36
Esempio:
convertire 43.687dieci in binario
43
1
.687 x 2 p.i. 1
21
1
.374 x 2 p.i. 0
10
0
.748 x 2 p.i. 1
5
1
.496 x 2 p.i. 0
2
0
.992 x 2 p.i. 1
1
1
.984 …
Operazioni aritmetiche
Operazioni +, -, *, / su numeri in base 2
Valgono le stesse regole e proprietà delle
operazioni in base 10
0
43.687dieci = 101011.10101due
(fermandosi al quinto bit per la parte
frazionaria)
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
37
Aritmetica binaria: addizione
+
0
1
0
0
1
38
Aritmetica binaria: sottrazione
0
1
1
1
(1) 0
0
0
1
1
(1) 1
0
Riporto: 1 + 1 = 2dieci = 10due
Prestito (borrow): 102 – 12 (= 210 – 110) = 012
Esempio:
Esempio:
110+
10=
_________
6
1110 –
14
2
11 =
3
_________
1000
1011
Daniela Fogli – Elementi di Informatica e Programmazione
39
Daniela Fogli – Elementi di Informatica e Programmazione
11
40
Altri esempi di operazioni
aritmetiche in base 2
Aritmetica binaria: moltiplicazione
*
0
1
0
0
0
1
0
1
moltiplicazione
addizione
1011+
Esempio:
111010*
1011=
58
11
0111=
______
__________
111010
111010
000000
111010
10010
11000011=
__________
1001
_______________________________________
1001111110
sottrazione
638
1101×
1011=
_______
1101+
1101 +
0000
+
1101
+
_____________
10001111
Esercizio: controllare se i risultati sono corretti convertendo in decimale
Daniela Fogli – Elementi di Informatica e Programmazione
41
Numeri in base 8 (ottali)
Daniela Fogli – Elementi di Informatica e Programmazione
42
Numeri in base 16 (esadecimali)
Le cifre: [0, 1, 2, 3, 4, 5, 6, 7]
Le cifre: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]
17otto = ?dieci
1otto = 1dieci
17otto = (1 x
7otto = 7dieci
81
+7x
80)
dieci
7D2sedici = ?dieci
7sedici = 7dieci Dsedici = 13dieci 2sedici = 2dieci
7D2sedici = (7 x 162 + 13 x 161 + 2 x 160)dieci = (7 x 256 + 208 +
2)dieci = (1792 + 208 + 2)dieci = 2002dieci
= (8 + 7)dieci = 15dieci
372otto = ?dieci
372otto = (3 x 82 + 7 x 81 + 2 x 80)dieci = (3 x 64 + 56 + 2)dieci =
250dieci
Daniela Fogli – Elementi di Informatica e Programmazione
FAsedici = ?dieci
Fsedici = 15dieci Asedici = 10dieci
FAsedici = (15 x 161 + 10 x 160)dieci = (240 + 10)dieci = 250dieci
43
Daniela Fogli – Elementi di Informatica e Programmazione
44
Perché le basi 2, 8 e 16?
I primi 16 numeri in base 10, 2, 8, e 16
decimale
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sistema di numerazione
binario
ottale
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
10
1001
11
1010
12
1011
13
1100
14
1101
15
1110
16
1111
17
La rappresentazione binaria ha motivazioni di tipo
esadecimale
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
Daniela Fogli – Elementi di Informatica e Programmazione
tecnologico
Le rappresentazioni ottali ed esadecimali sono utili per
rappresentare sinteticamente i valori binari
E’ facile convertire un numero in base 2 in un numero
in base 8 o 16
Le cifre binarie si possono raggruppare a 3 a 3 e poi
codificare con numeri ottali
Le cifre binarie si possono raggruppare a 4 a 4 e poi
codificare con numeri esadecimali
Conversione binario ⇒ ottale
Tabella di conversione
0otto
000due
001due
1otto
010 due
2otto
011due
3otto
100due
4otto
101due
5otto
110due
6otto
111due
7otto
Daniela Fogli – Elementi di Informatica e Programmazione
45
46
Conversione binario ⇒ esadecimale
Tabella di conversione
11 110 110 100.001due = 3 6 6 4 .1otto
Separazione a gruppi di tre cifre binarie
a partire dalla meno significativa per la
parte intera, e dalla più significativa per
la parte frazionaria (dalla virgola!)
Nel gruppo “più significativo” della
parte intera si possono aggiungere degli
zeri a sinistra, nel “meno significativo”
della frazionaria zeri a destra
Daniela Fogli – Elementi di Informatica e Programmazione
47
0000due
0001due
0010due
0011due
0100due
0101due
0110due
0111due
1000due
1001due
1010due
1011due
1100due
1101due
1110due
1111due
0sedici
1sedici
2sedici
3sedici
4sedici
5sedici
6sedici
7sedici
8sedici
9sedici
Asedici
Bsedici
Csedici
Dsedici
Esedici
Fsedici
111 1011 0100due = 7 B 4sedici
Si procede nello stesso modo,
ma separando le cifre a gruppi
di 4 anziché di 3
Daniela Fogli – Elementi di Informatica e Programmazione
48
Errore Tipico
Esecuzione corretta
Convertire in notazione ottale il numero binario 10111010.11
L’esercizio quindi va risolto così:
10111010.11
5 6 2. 3
10111010.110
Invece 562.38 = 5*64 + 6*8 + 2 + 3/8 = 370.375 che sicuramente non può
essere rappresentato con una parte intera di soli 8 bit!!!
PARTIRE SEMPRE DAL PUNTO DI RADICE, EVENTUALMENTE
COMPLETANDO LE CIFRE CON DEGLI ZERI PER OTTENERE LE
TERNE:
2 7 2 . 68
infatti risulta 272.68 = 2*64 + 7*8 + 2 + 6/8 = 186.7510
e 10111010.112 = 128 + 32 + 16 + 8 + 2 + 0.5 + 0.25 = 186.7510
xxx xxx . yyy yyy …
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
49
50
Esempi di conversione
esadecimale-binario
Un altro esempio
Convertire in binario il numero in notazione ottale 135.18
1)
1 3 5.18
0111010 .1
3 A . 816
0 0 1 0 1 1 1 0 1 . 001
2)
E 3 . 716
11100011.0111
ERRORE TIPICO: CONVERTIRE IN
001 011 101 . 1
ATTENZIONE!!!
PARTIRE SEMPRE DAL PUNTO DI RADICE!!!
xxxx . xxxx xxxx
infatti 0.18 = 1/8 = 0.125 mentre 0.12 = 1/2 = 0.5
Daniela Fogli – Elementi di Informatica e Programmazione
51
Daniela Fogli – Elementi di Informatica e Programmazione
52
Esercizio (in aula)
Esercizio (in aula)
Dato il numero binario 001010110111due convertirlo in
un numero ottale e poi in un numero esadecimale
Se la base considerata è b = 4, quali sono le cifre
utilizzate per comporre i numeri?
[0,1,2,3]
Convertire il numero (1320)quattro nel corrispondente
numero in base 10
1320quattro = (1x43 + 3x42 + 2x41 + 0x40)dieci = (64 + 48 +
8)dieci = 120dieci
Qual è il numero massimo rappresentabile in base 3
con quattro cifre (espresso in base 3)?
2222tre
Convertire il numero ottale in numero decimale
Numero ottale: 001 010 110 111 1267otto
Numero esadecimale: 0010 1011 0111 2B716
Numero decimale: 1267otto = (1x83 + 2x82 + 6x81 +
7x80)dieci = (512 + 128 + 48 + 7)dieci = 695dieci
Daniela Fogli – Elementi di Informatica e Programmazione
53
Esercizi
1. Convertire in formato decimale i seguenti numeri binari:
11, 101011, 1100, 111111, 10101010
2. Convertire in decimale i seguenti numeri frazionari binari :
0.111, 0.0101, 0.00011
3. Convertire in formato decimale i seguenti numeri ottali:
12, 23, 345, 333.14, 560.271
4. Convertire in formato decimale i seguenti numeri esadecimali:
12.5, DAB, 15D, FFFF, 51A
5. Convertire in binario i seguenti numeri decimali (considerando 6 bit
per la parte frazionaria):
45.226, 234.349, 67.712, 83.8123
6. Convertire in ottale e in esadecimale i numeri binari ottenuti dalla
conversione dei numeri decimali di cui al punto precedente
Daniela Fogli – Elementi di Informatica e Programmazione
55
Daniela Fogli – Elementi di Informatica e Programmazione
54
Tipologie di codici
Elementi di Informatica e
Programmazione
Nel seguito vedremo tipologie di rappresentazioni
diverse:
La Codifica dell’informazione
(parte 2)
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
Corsi di Laurea in:
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
Ingegneria Civile
Ingegneria per l’Ambiente e il Territorio
Università degli Studi di Brescia
Codici di compressione (senza | con perdita)
Docente: Daniela Fogli
Daniela Fogli – Elementi di Informatica e Programmazione
Codifica dei numeri naturali
2
Nota
I numeri naturali si rappresentano normalmente, ma con n cifre
binarie possiamo rappresentare solo i numeri da 0 a Nmax
Con n cifre binarie si possono rappresentare i numeri da 0 a 2n-1
Esempio: con 8 cifre (n=8)
0
0
0
0
0
0
0
0
0
Esempio precedente
0
0
0
0
0
0
0
1
1
n=8
…
0
1
1
1
1
1
1
1
1
127
1
1
1
1
1
1
1
Nmax = 255
1
1
1
1
1
1
1
Nmax = 2n-1 = 256-1 =255
…
1
Daniela Fogli – Elementi di Informatica e Programmazione
3
Daniela Fogli – Elementi di Informatica e Programmazione
4
Viceversa
In generale …
Per poter rappresentare numeri naturali fino a N ≥ 0,
serve un numero di cifre n tali che:
Voglio rappresentare i numeri naturali da 0 a Nmax.
Di quante cifre binarie ho bisogno?
Nmax ≥ N ovvero (2n – 1) ≥ N
Esempio
Quindi deve essere
n ≥ log2(N + 1)
Voglio rappresentare numeri da 0 a 350
…
con n = 7 Nmax = 127
Esempio precedente
con n = 8 Nmax = 255
N = 350
con n = 9 Nmax = 511
n ≥ log2(351) = 8,….
quindi n ≥ 9
n=9
Daniela Fogli – Elementi di Informatica e Programmazione
5
Operazioni aritmetiche
14
0010=
2
Nel seguito vedremo tipologie di rappresentazioni
diverse:
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
_________
(1) 0 0 0 0
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
0?
Nel caso di sottrazione, un prestito dal bit più significativo indica
un risultato negativo (non rappresentabile)
1100–
12
1101=
13
__________
(1) 1 1 1 1
6
Tipologie di codici
Nel caso di addizione, ho traboccamento (overflow) quando ho un riporto
dal bit più significativo che non può essere rappresentato con le cifre a
disposizione
1110+
Daniela Fogli – Elementi di Informatica e Programmazione
Codici di compressione (senza | con perdita)
15?
Daniela Fogli – Elementi di Informatica e Programmazione
7
Daniela Fogli – Elementi di Informatica e Programmazione
8
Codifica in valore assoluto e segno
con 4 bit
Codifica in valore assoluto e segno
Il modo più semplice: indicare il segno seguito dal valore assoluto
0000
0001
0010
0011
0100
0101
0110
0111
Esempio: n = 8 (8 bit a disposizione)
Rappresentazione di -11
1
0
0
0
1
segno -
0
1
1
11
Daniela Fogli – Elementi di Informatica e Programmazione
Numeri negativi
Numeri positivi
Se i bit disponibili per la codifica sono n si utilizza il primo bit della
sequenza per indicare il segno (0 per positivo e 1 per negativo), e
i restanti bit rappresentano il valore assoluto del numero
-0
-1
-2
-3
-4
-5
-6
-7
Daniela Fogli – Elementi di Informatica e Programmazione
9
Due note importanti
1000
1001
1010
1011
1100
1101
1110
1111
+0
+1
+2
+3
+4
+5
+6
+7
10
Che problemi ha questa codifica?
Questa tecnica non viene usata nel calcolatore
Esistono due codifiche per il valore 0
Difficoltà nel fare le operazioni aritmetiche (es. la sottrazione)
0
0
0
0
0
0
0
0
0+
1
0
0
0
0
0
0
0
0-
Es. 1 (sottrazione di numeri entrambi positivi)
- (2n-1 - 1)
segno *
*
*
*
a
*
n-1 bit: da 0 a 2
*
n-1
0
0
0
1
1
0
1
1
b:
0
0
1
0
1
0
1
1
-
27
43
Dato che |b|>|a|, il segno del risultato è negativo, il valore assoluto è
I valori rappresentabili vanno:
da
a:
+ (2n-1 - 1)
0101011 0011011=
0010000
*
a-b:
-1
Daniela Fogli – Elementi di Informatica e Programmazione
11
1
0
0
1
|b|
|a|
0
0
0
0
Daniela Fogli – Elementi di Informatica e Programmazione
-16
12
Un altro esempio
In generale
Segno a
+
+
+
-
Es. 2: Sottrazione di numeri entrambi positivi ma con |a|>|b|
a:
0
0
1
1
1
0
1
1
b:
0
0
1
0
1
0
1
1
-
59
43
Dato che |a|>|b|, il segno del risultato è positivo, il valore assoluto
è
0111011- |a|
0101011= |b|
0010000
a-b:
0
0
0
1
0
0
0
0
|a| >|b|
|b|>|a|
|a| > |b|
|b| > |a|
segno(a-b)
+
+
+
|a-b|
a-b
b-a
|a| + b
a + |b|
|a| - |b|
|b| - |a|
Per il calcolatore le operazioni di somma e sottrazione sono complesse
Si vuole una rappresentazione per la quale esista
un unico semplice metodo per l’addizione e la sottrazione …
+16
Daniela Fogli – Elementi di Informatica e Programmazione
13
Codifica in complemento a 1
Daniela Fogli – Elementi di Informatica e Programmazione
14
Esempi
Si ottiene facendo il complemento di tutti i bit (ovvero
si sostituiscono gli 0 con 1 e gli 1 con 0)
Ad esempio:
n=8
+21dieci = 00010101due
–21dieci = 11101010due
Anche questa volta il numero 0dieci ha due
rappresentazioni: 00000000 e 11111111
Esercizio:
n=8
+36dieci = 00100100due
- 36dieci = ????????due
Es.: 5dieci = 0101due e –5dieci = 1010due
Il bit più significativo indica se positivo o negativo
I numeri positivi si rappresentano come nella
rappresentazione in valore assoluto e segno
I numeri negativi si rappresentano come
complemento a 1 del numero positivo corrispondente
Daniela Fogli – Elementi di Informatica e Programmazione
Segno b
+
+
+
-
15
Daniela Fogli – Elementi di Informatica e Programmazione
16
Operazioni aritmetiche
Codifica in complemento a 2
Sia n è il numero di bit utilizzati per la codifica
I numeri positivi sono rappresentati normalmente
(rappresentazione binaria dei numeri positivi) con il bit più
significativo pari a 0
I numeri negativi si ottengono come complemento a due del
numero positivo x corrispondente, ovvero come 2n – x, e il bit più
significativo è pari a 1
La somma si ottiene facendo la somma degli addendi e poi
sommando l’eventuale riporto
Esempi:
10011100 +
-99dieci
10011100 +
-99dieci
11100011 =
-28dieci
11001001 =
-54dieci
(1)01111111 +
(1)01100101 +
1=
1=
10000000
-127dieci
Risultato OK
01100110
Esempi (con n = 4):
+6dieci = 0110 (rappresentato normalmente)
- 6dieci ⇒ 24 - 6 = 10 ⇒ -6dieci = 1010c2
+3dieci ⇒ 0011 (rappresentato normalmente)
- 3dieci ⇒ 24 - 3 = 13 ⇒ -3dieci = 1101c2
+102dieci
Risultato ERRATO! (overflow)
E’ complicato?
Somma più semplice ma con il problema di sommare il riporto …
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
17
Due metodi pratici
Codifica in complemento a 2 con n=4 bit
Bit di
segno
Numeri positivi
0000
0001
0010
0011
0100
0101
0110
0111
0
1
2
3
4
5
6
7
Bit di
segno
18
Numeri negativi
1000
1001
1010
1011
1100
1101
1110
1111
Esistono due metodi pratici equivalenti per calcolare il
complemento a due di un numero x
-8
-7
-6
-5
-4
-3
-2
-1
Metodo 1:
1. Effettuare il complemento a 1 di x
2. Aggiungere 1
Metodo 2:
1. Partendo da destra e andando verso sinistra, lasciare
invariati tutti i bit fino al primo 1 compreso
2. Complementare (invertire) tutti i bit successivi al primo 1
Unica rappresentazione del numero zero
NB: il Metodo 1 è quello utilizzato nei dispositivi elettronici
NB: i numeri rappresentabili vanno da -2n-1 (-8) a +(2n-1 -1) (+7)
Daniela Fogli – Elementi di Informatica e Programmazione
19
Daniela Fogli – Elementi di Informatica e Programmazione
20
Esempio di uso del metodo 1
Esempio di uso dell’algoritmo 2
Dato +6dieci codificato su 4 bit ⇒ 0110
Dato +6dieci codificato su 4 bit ⇒ 0110
Facendo il complemento a 1 si ottiene 1001
1010
Sommando 1 al risultato si ottiene…
rimane invariato
rimane invariato
1001+
viene invertito
1=
Risultato
1010
viene invertito
1010
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
21
Altro esempio
22
Errore Tipico
ERRORE TIPICO: dimenticarsi che la rappresentazione in C.a 2 è relativa ad
un numero di bit fissati!!!
A partire dalla codifica binaria di 15dieci troviamo la
codifica binaria di –15dieci
15dieci = 01111 … nota 5 bit!
Usando il primo metodo:
01111 ⇒ complemento ⇒ 10000
Aggiungo 1 a 10000 ⇒ 10001
Es. Rappresentare in C. a 2 con 8 bit il numero decimale –3.
3dieci = 11due
Usando il secondo metodo:
quindi –3dieci = 01due
ma questo risulta un numero positivo!!!
Svolgimento corretto:
01111 ⇒ lascio invariato il primo 1 a destra e
complemento tutti gli altri ⇒ 10001
3dieci = 00000011due
-3dieci = 11111101
Daniela Fogli – Elementi di Informatica e Programmazione
23
Daniela Fogli – Elementi di Informatica e Programmazione
24
Una visione globale …
Intervalli di rappresentazione: esempio
Con n cifre si possono rappresentare 2n numeri.
Metà per i positivi e metà per i negativi, come in figura
Supponiamo di avere una codifica con n=16 bit
Rapp."normale“
Rappresentazione in valore assoluto e segno: numeri compresi
Numeri
positivi
fra –(215-1) e 215-1, ovvero fra –32767 e +32767… lo 0 ha due
rappresentazioni
00000010 +2
00000001 +1
00000000 0
+2n-1 -1 01111111
–2n-1 10000000
–(2n-1-1) 10000001
Rappresentazione in complemento a 1: numeri compresi fra –(2151) e 215-1, ovvero fra –32767 e +32767… lo 0 ha due
rappresentazioni
11111111 –1
11111110 –2
11111101 –3
Rappresentazione in complemento a 2: numeri compresi fra –215
e 215-1, ovvero fra –32768 e +32767… lo 0 ha una sola
rappresentazione (in pratica, però, tipicamente si utilizzano i valori fra
–32767 e +32767 per simmetria, così dato un qualsiasi numero
anche il suo opposto è rappresentabile)
Numeri
negativi
C. A 2: 2n - N
NB: i numeri rappresentabili vanno da -2n-1 a +(2n-1 -1)
Daniela Fogli – Elementi di Informatica e Programmazione
25
Conversione da numero binario in
complemento a 2 a numero decimale
Daniela Fogli – Elementi di Informatica e Programmazione
Altri esempi
Si può usare la simmetria dell’operazione in compl. a 2
10001 = -1x24 + 1x20 = -16 + 1 = -15dieci
Esempio:
1010 = -1x23 + 1x21 = -8 + 2 = -6dieci
1000001due è un numero negativo, pari a – 0111111 = -63dieci
10101010 = -1x27 + 1x25 + 1x23 + 1x21= -128 + 32 + 8
+ 2 = -86
Oppure si può usare la seguente regola:
il valore di un numero ckck-1…c1c0 rappresentato in complemento a
due è dato dalla seguente espressione
-ckx2k
+
ck-1x2k-1 +
…+
c1x21
+
26
Esercizio proposto:
ricavare il valore decimale col metodo della simmetria
c0x20
Esempio:
1 0 0 0 0 0 1due = (-1)x26 + 1x20 = - 64 +1 = - 63dieci
Daniela Fogli – Elementi di Informatica e Programmazione
27
Daniela Fogli – Elementi di Informatica e Programmazione
28
Perché il complemento a 2?
Estensione del segno
I calcolatori usano la rappresentazione in
complemento a 2
Estendiamo il segno per rappresentare
un numero su n=k + d bit anziché su
n=k bit
si semplificano i circuiti che svolgono le operazioni
aritmetiche
in particolare la somma si effettua semplicemente
come nel caso di numeri naturali, inoltre
somma e sottrazione possono essere realizzate
con un unico circuito: infatti: x - y = x + (-y)
Daniela Fogli – Elementi di Informatica e Programmazione
29
1 0 0 0
-8 su n = 4 bit
1 1 1 1 1 0 0 0
-8 su n = 8 bit
Daniela Fogli – Elementi di Informatica e Programmazione
Somma di numeri in complemento a 2
Esempio di addizione
L’addizione di due numeri rappresentati in
complemento a 2 dà un risultato corretto, trascurando
il riporto, a patto che il risultato sia compreso
Usando n = 6 bit, l’intervallo dei numeri rappresentabili
va da –25 a +25-1, ovvero da –32 a +31
30
Vogliamo calcolare 26 - 13
entro l’intervallo dei numeri rappresentabili
26 – 13 = 26 + (-13) = +13
n = 8 bit, posso rappresentare i numeri da –27 a +27 - 1
(+5)
00000101
(+5)
00000101
(+8)
00001000
(-8)
11111000
(+13) 00001101
(-3)
11111101
Daniela Fogli – Elementi di Informatica e Programmazione
011010+
26
110011=
-13
1001101
Il riporto viene trascurato
31
(13 = 0 0 1 1 0 1)
+13
È nell’intervallo dei
numeri rappresentabili
Daniela Fogli – Elementi di Informatica e Programmazione
32
Overflow
Esempio di overflow
Bit di segno
La somma di due numeri interi positivi o di due numeri
interi negativi può dar luogo ad un intero non rappresentabile
con i bit a disposizione
Questo dà luogo a ciò che si chiama “overflow”
(traboccamento)
In caso di overflow, il risultato di un’operazione non è valido
Esempio: supponiamo di avere a disposizione 8 bit per
rappresentare gli interi (1 bit per il segno e 7 bit per il valore)
Sommiamo a 01111111 (+127) il numero 00000001 (+1)
otteniamo un numero negativo (-128) invece di +128
Daniela Fogli – Elementi di Informatica e Programmazione
01111111 +
+127
00000001 =
+1
10000000
-128
Il risultato ha segno negativo nonostante
gli addendi siano entrambi positivi
33
Regola per la determinazione
dell’overflow
Daniela Fogli – Elementi di Informatica e Programmazione
34
Regola equivalente per l’overflow
Se gli addendi hanno segno discorde non si ha mai overflow:
Con una rappresentazione su n bit, si ha overflow se i
riporti generati nelle due posizioni più significative
(n-1 e n-2 in figura) sono diversi
MAX (+)
N1
Somma compresa tra N1 (positivo)
0
N2
ed N2 (negativo), quindi sicuramente
rappresentabile!
MIN (-)
Se gli addendi hanno segno concorde si ha overflow se il segno del
risultato è diverso dal segno dei due addendi:
+ e +:
deve risultare +, altrimenti overflow!
–e–:
deve risultare –, altrimenti overflow!
Daniela Fogli – Elementi di Informatica e Programmazione
n-1 n-2
1
0
(ovvero: se c’è riporto generato in una posizione ma non nell’altra)
35
Daniela Fogli – Elementi di Informatica e Programmazione
36
Esempio di overflow
Esempio di “non” overflow
Usando n = 6 bit, l’intervallo dei numeri rappresentabili va da –25 a
+25-1, ovvero da –32 a +31
25 - 13 = 25 + (-13) = 12 è compreso nell’intervallo
Vogliamo calcolare -25 - 13
-25 - 13 = -25 + (-13) = -38 non è compreso nell’intervallo
100111+
-25
(25 = 0 1 1 0 0 1)
110011=
-13
(13 = 0 0 1 1 0 1)
1011010
1
011001+
25
110011=
-13
1001100
1
+26
(13 = 0 0 1 1 0 1)
+12
1
Generato un riporto
in entrambe le
posizioni
più significative
0
Generato un riporto solo
nella posizione più
significativa
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
37
Esercizio d’esame (1)
38
Soluzione (cont.)
Somma algebrica:
Rappresentare i numeri –51 e –98 (in base 10) in notazione binaria in
complemento a due con 8 bit. Eseguire la somma algebrica dei numeri così
ottenuti e commentare il risultato. [3 punti]
11001101 +
10011110 =
1 01101011
Soluzione
Commento (= dire se c’è overflow e spiegare perché nel dettaglio):
- riporto generato in posizione 6: NO
- riporto generato in posizione 7: SI
Poiché i riporti generati nei bit di posizione 6 e 7 sono diversi ho un caso di
overflow
Conversione nella notazione binaria dei numeri (valori assoluti)
51 = 001100112
(32 + 16 + 2 + 1)
98 = 011000102
(64 + 32 + 2)
NB: la cosa è evidente anche dal fatto che dalla somma di due numeri negativi
ottengo un numero positivo. In effetti con 8 bit posso esprimere in
complemento a due i numeri da –128 a +127 [nella pratica da –127 a + 127],
mentre si ha –51 –98 = –149.
Rappresentazione in complemento a due:
-51 = 11001101
-98 = 10011110
ERRORE TIPICO:
Dire che c’è overflow perché “i bit del risultato di posiz. più significativa sono
diversi”. In questo caso è vero, ma non c’entra nulla con l’overflow!
Daniela Fogli – Elementi di Informatica e Programmazione
39
Daniela Fogli – Elementi di Informatica e Programmazione
40
Esercizio d’esame (2)
Soluzione (cont.)
Rappresentare i numeri –54 e –44 (in base 10) in notazione binaria in
complemento a due con 8 bit. Eseguire la somma algebrica dei numeri così
ottenuti e commentare il risultato. [3 punti]
Somma algebrica:
11001010 +
11010100 =
1 10011110
Soluzione
Conversione nella notazione binaria dei numeri (valori assoluti)
54 = 001101102
(32+16+4+2)
e quindi il risultato è 10011110.
44 = 001011002
(32+8+4)
Commento:
Non c’è overflow perché i riporti generati nelle posizioni 6 e 7 sono uguali (1 e
1). In effetti risulta un numero negativo pari a – 01100010due = – (64+32+2) =
–98dieci, che è proprio –54 – 44
Rappresentazione in complemento a due dei numeri (con 8 bit)
-54 = 11001010
-44 = 11010100
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
41
Un possibile errore
42
Esercizio d’esame (3)
Dimenticarsi del numero di bit (8):
54 = 1101102
44 = 1011002
Rappresentare i numeri 96 e 69 (in base 10) in notazione binaria in
complemento a due con 8 bit. Eseguire la somma algebrica dei numeri così
ottenuti e commentare il risultato. [3 punti]
-54 = 001010
-44 = 010100
Soluzione
e sommando:
Rappresentazione in complemento a due con 8 bit:
001010+
010100=
011110
96 =
01100000
69 =
01000101
Somma algebrica:
01100000+
01000101=
10100101
risultato che non ha alcun senso!!!
(NB: in questo caso l’esercizio è valutato 0 punti!)
Daniela Fogli – Elementi di Informatica e Programmazione
43
Daniela Fogli – Elementi di Informatica e Programmazione
44
Soluzione (cont.)
Esercizi
Commento:
Dati i seguenti numeri decimali interi positivi:
55, 121, 16, 42
Ho overflow perchè i riporti sono diversi (ho soltanto il riporto nel bit 7), cosa
deducibile anche dal fatto che il risultato ha il “bit di segno” pari a 1
(rappresenta un numero negativo ottenuto dalla somma di due positivi!).
Rappresentarli come numeri binari su 8 bit
Determinare i numeri negativi corrispondenti in binario
con le seguenti rappresentazioni:
Valore assoluto e segno
In complemento a 1
In complemento a 2
ERRORE TIPICO: complementare i due numeri che in realtà sono positivi
Daniela Fogli – Elementi di Informatica e Programmazione
45
Esercizi
Fare la somma dei numeri binari in complemento a 2
codificati su n = 8 bit che corrispondono ai numeri
16dieci e –42dieci
Fare la somma dei numeri binari in complemento a 2
codificati su n = 6 bit che corrispondono ai numeri
–5dieci e –28dieci
Daniela Fogli – Elementi di Informatica e Programmazione
47
Daniela Fogli – Elementi di Informatica e Programmazione
46
Tipologie di codici
Elementi di Informatica e
Programmazione
Nel seguito vedremo tipologie di rappresentazioni
diverse:
La Codifica dell’informazione
(parte 3)
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
Corsi di Laurea in:
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
Ingegneria Civile
Ingegneria per l’Ambiente e il Territorio
Università degli Studi di Brescia
Codici di compressione (senza | con perdita)
Docente: Daniela Fogli
Daniela Fogli – Elementi di Informatica e Programmazione
Formato
Rappresentazione dei numeri reali
Per rappresentare numeri come
In entrambi i casi, una rappresentazione è definita
mediante un formato
1/3 = 0.33333333333….
π = 3.141592653…
2 = 1.4142135…
Il numero n di bit a disposizione
I campi in cui sono suddivisi i bit
servirebbe un numero di cifre illimitato
Quanti
In che ordine
Quanti bit per ciascun campo
Cosa rappresenta ciascun campo
Nel calcolatore è possibile usare solo successioni di bit
di lunghezza finita
Necessaria approssimazione
2 modalità
Esempio di formato a 32 bit
Rappresentazione in virgola fissa
(non usata nei calcolatori)
Rappresentazione in virgola mobile
Daniela Fogli – Elementi di Informatica e Programmazione
2
3
S
E
M
1
8
23
Vedremo poi il significato…
Daniela Fogli – Elementi di Informatica e Programmazione
4
Rappresentazione in virgola fissa
Altro esempio
Abbiamo n bit a disposizione (e vogliamo rappresentare numeri reali):
- un campo del formato rappresenta la parte intera
- un campo del formato rappresenta la parte frazionaria
Esempio: n = 32 bit
31
Esempio: n = 24 bit (3 byte)
Parte intera
2 byte (16 bit)
Parte decimale
16 bit
Valore massimo rappresentabile in questo formato?
1111111111111111.1111111111111111
0 0 0 0 0 0 0 1 (2-8)
5
16 bit
16 bit
Daniela Fogli – Elementi di Informatica e Programmazione
6
Intervallo di rappresentazione:
in generale
Intervallo di rappresentazione: esempio
Nel formato precedente a 32 bit
Numero massimo rappresentabile NMAX
111……………………111 111……………………111
- Parte intera: 216 – 1 = 65535
- Parte frazionaria:
0.1111111111111111 +
0.0000000000000001 =
1.0000000000000000
16 bit
00000000000011010100000000000000
1 byte (8 bit)
Daniela Fogli – Elementi di Informatica e Programmazione
Parte frazionaria
Es. 13.25dieci sarebbe rappresentato così
Il numero più piccolo rappresentabile maggiore di 0 è:
0000000000000000
0
16 15
Parte intera
nI bit
2-16
Max parte intera: 2nI-1
Max parte frazionaria: 1 - 2-nF
se nF grande, 1 - 2-nF pari a circa 1
⇒ 1 - 2-16 = 0.9999847421 circa 1
NMAX = (2nI-1) + (1 - 2-nF)
se nF grande, NMAX pari a circa 2nI
NMAX = 65535.9999847421 circa 65536
Daniela Fogli – Elementi di Informatica e Programmazione
nF bit
7
Daniela Fogli – Elementi di Informatica e Programmazione
8
Granularità
Un inconveniente
Con la rappresentazione precedente, vogliamo rappresentare un
numero “grande”, ad esempio 60.000
Qual è la “precisione” della rappresentazione in virgola fissa?
Granularità: differenza tra un numero e il successivo
rappresentabile quanto più è piccola, tanto più precisa è la
rappresentazione!
1110101001100000
a cosa mi servono questi?
Dato un numero, rappresentato, qual è il successivo?
⇒ Molto meglio un campo più grande per la parte intera!
Es. 00000000000011010100000000000000
0.0000000000000001
00000000000011010100000000000001
In generale: la granularità è fissa e pari a
Vogliamo rappresentare un numero “piccolo”, ad esempio 2-15
0000000000000000
Daniela Fogli – Elementi di Informatica e Programmazione
a cosa mi servono questi?
⇒ Molto meglio un campo più grande per la parte frazionaria!
9
Daniela Fogli – Elementi di Informatica e Programmazione
10
Notazione scientifica
Alcuni esempi pratici
Massa dell’elettrone: 9 x 10-28 grammi
Per semplicità, vediamola prima in base 10
0000000000000000000000000000000000.0000000000000000000000000009
Massa del sole: 2 x
0000000000000010
2-nF
Per un qualsiasi numero rappresentabile I, il successivo è I + 2-nF
1033
0000000000000000
Un numero in base 10 viene rappresentato come
grammi
2000000000000000000000000000000000.0000000000000000000000000000
m x 10 exp
Potrei rappresentare tutti i numeri con 34 cifre a sinistra della
virgola e 28 cifre a destra, ma in questo modo spreco le cifre
disponibili!
base
mantissa esponente
Si vuole un sistema di rappresentazione in cui l’intervallo dei
numeri esprimibili sia indipendente dal numero di cifre
Esempio: 159 300 000 = +1.593 x 108 dove m=+1.593 ed e=8
significative
Esempio: -0.00001593 = -1.593 x 10-5 dove m= -1.593 ed e=-5
Ovvero un sistema in cui la granularità dipende dal numero
rappresentato: si estende così l’intervallo dei numeri
rappresentabili
Daniela Fogli – Elementi di Informatica e Programmazione
11
Daniela Fogli – Elementi di Informatica e Programmazione
12
Nel calcolatore:
Rappresentazione in virgola mobile
Notazione scientifica
per numeri binari
Virgola mobile o Floating point
Il numero 101010000due può essere rappresentato come
1.0101 x
28
Dato un numero da rappresentare N:
esponente
N = ±mant*2esp
mantissa
base
Altri esempi:
un numero molto grande come
101101011100000000000000000000000000000.000000
diventa
1011010111*229
FORMATO
Esempio di formato: sM
un numero molto piccolo come
0.00000000000000000000000000000000000011011011
diventa
0.11011011*2-36
Daniela Fogli – Elementi di Informatica e Programmazione
Si memorizzano
segno, mantissa ed esponente
|mant|
nM bit
esp
nE bit
Daniela Fogli – Elementi di Informatica e Programmazione
13
Problema
14
Standard IEEE 754
N = ±mant*2esp
Necessità di uniformare la precisione del calcolo (calcolatori di
produttori diversi con strutture differenti)
Lo standard IEEE* 754 stabilisce la lunghezza di mantissa ed
esponente
In questo modo la rappresentazione non è univoca:
32 bit per i numeri in precisione singola
0.1due = 1 * 2-1 mant = 1 esp = -1
1 bit segno, 8 bit esponente, 23 bit mantissa
= 10 * 2-2 mant = 10 esp = -2
1
= 0.1 * 20 mant = 0.1 esp = 0
8
23
64 bit per i numeri in precisione doppia
1 bit segno, 11 bit esponente, 52 bit
mantissa
⇒ si stabilisce la “forma normalizzata” della mantissa
1
*Institute
Daniela Fogli – Elementi di Informatica e Programmazione
15
11
52
of Electrical and Electronic Engineering
Daniela Fogli – Elementi di Informatica e Programmazione
16
Nota sulla rappresentazione
dell’esponente
IEEE 754 Singola Precisione
S
E
M
1
8
23
Segno S: 0 segno +
255
Esempio: num= -3.5
1 segno -
Numeri positivi
Segno: 1
Normalizzazione e mantissa
N = 1.xxxxxxxxx
127
+128
* 2esp
23 bit (M)
hidden bit
num = 11.1
= 1.11 * 21
M = 1100…0
+127
Numeri negativi
0
Rappresentazione dell’esponente
0
E = 1 +127 = 128
= 10000000
E = esp + 127
Rappresentazione in 8 bit a eccesso 127,
con le configurazioni 00000000 e 11111111
non ammesse (-126 ≤ esp ≤ 127)
11000000011000000000000000000000
Daniela Fogli – Elementi di Informatica e Programmazione
-127
Daniela Fogli – Elementi di Informatica e Programmazione
17
Esercizio d’esame (1)
Esercizio d’esame (2)
Se il campo esponente di una codifica contiene il numero 00111011
qual è il valore decimale dell’esponente?
[2 punti]
Ricavare il valore decimale del seguente numero in virgola mobile
rappresentato secondo lo standard IEEE 754 a 32 bit: [3 punti]
0 10000000 10000000000000000000000
Soluzione
Soluzione
E = esp + 127
Segno: +
valori rappresentabili da –127 a +128
(NB: gli estremi non sono utilizzati propriamente)
Esponente:
Nel caso specifico:
18
E = 59
quindi esp = 59-127 = -68
Mantissa:
E = 27 = 128
esp = 128-127 = 1
mant = 1.1
⇒ N = 1.1due * 21 = 11due = 3dieci
Daniela Fogli – Elementi di Informatica e Programmazione
19
Daniela Fogli – Elementi di Informatica e Programmazione
20
Esercizio d’esame (3)
Normalizzazione
PASSAGGIO IMPORTANTE: normalizzazione
Rappresentare il numero decimale –4.5 secondo lo standard in
virgola mobile IEEE 754 a 32 bit. [3 punti]
ESEMPIO 1
Soluzione
Rappresentazione binaria:
1001.01001 =
1.00101001 * 23
(forma normalizzata)
Segno: 1
Rapp. binaria:
4.5dieci = 100.1due
Forma normalizzata:
N = 1.001 * 22
ESEMPIO 2
Esponente:
esp = 2
⇒ IEEE754:
⇒
E = 2+127 = 129dieci =
10000001
Rappresentazione binaria:
0.001011 =
1.011 * 2-3
(forma normalizzata)
1 10000001 00100000000000000000000
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
21
22
Esempio:
IEEE 754 con singola precisione
L’insieme dei numeri in virgola mobile
non coincide con R
MinExp = -126
MaxExp = +127
[estremi per scopi speciali]
L’insieme dei numeri reali è denso e illimitato
L’insieme dei numeri in virgola mobile non è denso ed
è limitato tra un numero reale massimo ed uno
minimo esprimibili
Numero più grande normalizzato: ± 1.11…12 * 2127 ≈ 2*2127 = 2128
Numero più piccolo normalizzato: ± 1.00…02 * 2-126 = 2-126
⇒ L’aritmetica “reale” del calcolatore è diversa da
quella classica
OVERFLOW -
-∞
∞
-2128
NORMALIZZATI -
DENORM.-
-2-126
UNDERF. DENORM.+
-2-149 0 2-149
NORMALIZZATI +
2-126
OVERFLOW +
2128
+∞
∞
NB: nel caso della virgola fissa, l’intervallo dei valori rappresentabili
sarebbe molto più limitato. Es:
- anche se dedicassimo tutti i 32 bit alla parte intera, max 232
- anche se dedicassimo tutti i 32 bit alla parte fraz, min 2-32
Daniela Fogli – Elementi di Informatica e Programmazione
23
Daniela Fogli – Elementi di Informatica e Programmazione
24
I problemi che nascono dalla natura
digitale del calcolatore
E lo zero???
I numeri nelle regioni (-∞, -2128), (-2-126, 0), (0, 2-126),
(2128 , +∞) non possono essere rappresentati
In generale lo zero non si potrebbe rappresentare
perché la mantissa è sempre 1.M …
Determiniamo quanti numeri possono essere rappresentati
Si usa un valore speciale dell’esponente (E = 0) e si
pone la mantissa a 0000….000
questa rappresentazione significa “0”
la mantissa varia da m = 1.0..0 a 1.1..1 (223 numeri)
l’esponente varia da e = -126 a + 127 (254 ordini di grandezza)
in totale: 223 x 254 numeri positivi, 223 x 254 numeri negativi, e lo
zero 4.261.412.865 numeri
Altri casi particolari di E (E=0 oppure E=255) per
rappresentare ±∞, risultati di operazioni non valide,
numeri denormalizzati
I due intervalli di numeri positivi e negativi esprimibili non formano
insiemi continui: i numeri non sono cioè uniformemente
distribuiti (più radi per valori elevati dell’esponente e più fitti per
valori piccoli dell’esponente – si infittiscono nei pressi dello zero)
Daniela Fogli – Elementi di Informatica e Programmazione
Esempio
-∞
∞
NORMALIZZATI -
-2128
NORMALIZZATI +
-2-126
0
26
Operazioni sui numeri “reali”
Addizione e sottrazione:
La separazione fra 1.0..00 x 299 e 1.0..01 x 299 (ovvero, 2-23+99 = 276)
è molto maggiore di quella fra 1.0..00 x 20 e 1.0..01 x 20 (ovvero, 2-23)
OVERFLOW -
Daniela Fogli – Elementi di Informatica e Programmazione
25
2-126
OVERFLOW +
2128
+∞
∞
si trasformano (con eventuale perdita di precisione) gli addendi in
una rappresentazione con uguale esponente (il maggiore)
si sommano (sottraggono) le mantisse
si normalizza se necessario
Moltiplicazione:
si sommano gli esponenti
si moltiplicano le mantisse
si normalizza se necessario
1.0..00
Divisione:
si sottraggono gli esponenti
si dividono le mantisse
si normalizza se necessario
1.0..00 x 299
La precisione è “concentrata” dove ce n’è bisogno!
Daniela Fogli – Elementi di Informatica e Programmazione
27
Daniela Fogli – Elementi di Informatica e Programmazione
28
Esempio di addizione
Problemi con le operazioni
Somma tra i seguenti due numeri rappresentati IEEE 754:
0 01111011 000…111
e
Addizioni e sottrazioni possono dare luogo a errori
0 01111101 000…011
E = 123 (– 127 = -4)
Esempio: sottrazione fra due numeri quasi uguali
E = 125 (– 127 = -2)
Porto l’esponente del primo operando a -2:
1.000…111 x 2-4 = 0.010…001 x 2-2
Sommo le mantisse:
può dar luogo al fenomeno della cancellazione
(risultato = 0)
Nota: perdo le 2
cifre meno
significative della
mantissa
Divisione per numeri molto piccoli
0.010…001 + [ x 2-2]
1.000…011 = [ x 2-2]
[ x 2-2] NB: risultato già normalizzato!
1.010…100
Risulta quindi
il risultato può cadere nell’intervallo di overflow
(+ o -)
0 01111101 010…100
NB: le cose sono leggermente più complicate, ma l’idea è questa …
Daniela Fogli – Elementi di Informatica e Programmazione
29
Fenomeno della cancellazione:
esempio
Daniela Fogli – Elementi di Informatica e Programmazione
30
Esercizi
Se ho la sottrazione
Esprimere i numeri decimali 45.25, -234.875, 67.75, -83.8125 in
codifica binaria secondo lo standard IEEE 754 (in singola
precisione a 32 bit)
1.11100…0 x 2-126 1.11000…0 x 2-126 =
0.00100…0 x 2-126
Ricavare il valore decimale dei seguenti numeri in virgola mobile
rappresentati secondo lo standard IEEE 754 a 32 bit:
che normalizzato diventerebbe 1.0…0 x 2-129 che
viene dunque approssimato con 0, perché il minimo
esponente esprimibile è -126
0 10000100 00010001000000000000000
1 10000001 01010110000000000000000
NB: in realtà, è possibile esprimere numeri “denormalizzati”
prossimi allo 0, fino a 2-149, ma noi non ce ne occupiamo
(vedere libro per gli interessati)
Daniela Fogli – Elementi di Informatica e Programmazione
31
Daniela Fogli – Elementi di Informatica e Programmazione
32
Tipologie di codici
Codifica binaria di valori logici
Nel seguito vedremo tipologie di rappresentazioni
diverse:
Valore logico: esprime il “valore di verità” di un determinato fatto
Esempi
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
- Il voto del mio compito di informatica A è sufficiente (F1)
- Una squadra di pallavolo in campo è costituita da 6 giocatori (F2)
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
Il fatto F1 è vero oppure falso, non entrambi (lo stesso per F2)
Codici di compressione (senza | con perdita)
Daniela Fogli – Elementi di Informatica e Programmazione
33
Algebra di Boole
Daniela Fogli – Elementi di Informatica e Programmazione
34
Variabili booleane
E’ un particolare tipo di algebra che include:
Una variabile booleana è una variabile binaria che
può assumere uno dei due valori logici denotati con 0 e
1 (oppure Falso e Vero)
un insieme di supporto A (l’insieme {0,1} o {V,F} nel ns caso)
degli operatori binari: AND (—) e OR (+)
un operatore complemento: NOT (‾)
Usiamo ad esempio i simboli x, y, z, … per indicare
variabili booleane
Gli operatori soddisfano certe proprietà che si deducono da un
insieme di assiomi
Può essere x = 1 oppure x = 0
E’ lo strumento matematico su cui si fonda il funzionamento dei
circuiti digitali
Daniela Fogli – Elementi di Informatica e Programmazione
35
Daniela Fogli – Elementi di Informatica e Programmazione
36
Assiomi dell’Algebra di Boole
Operatori booleani e Tabelle di Verità
Operatori booleani (o logici) fondamentali:
NOT
AND
OR
not(x), x, ~x
x and y, x • y, xy
x or y, x + y
Negazione Logica
Prodotto Logico
Somma Logica
x1
x0
x1 • x0
x1
x0
x1 + x0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
1
AND
x
x
0
1
1
0
Forma AND
Forma OR
Commutatività
AB = BA
A+B = B+A
Distributività
A+BC=(A+B)(A+C)
A(B+C)=AB+AC
Identità
1A = A
0+A = A
Inverso
AĀ = 0
A+Ā = 1
NOT
OR
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
37
Formule (espressioni)
booleane (logiche)
Proprietà dell’Algebra di Boole
Forma AND
38
Forma OR
Elemento nullo
0A = 0
1+A = 1
Idempotenza
AA = A
A+A = A
Assorbimento
A(A+B) = A
A+AB=A
Associatività
(AB)C=A(BC)
(A+B)+C=A+(B+C)
De Morgan
AB = A+B
A+B = A B
Altre proprietà della negazione logica:
1.
Le costanti 0 e 1 e le variabili (simboli a cui possono essere
associati i valori 0 e 1) sono formule booleane
2.
Se E, E1 ed E2 sono formule booleane lo sono anche (E1+E2),
(E1—E2) e (E)
3.
Non esistono altre formule oltre a quelle che possono essere
generate da un numero finito di applicazioni delle regole 1 e 2
1=1
0=0
Daniela Fogli – Elementi di Informatica e Programmazione
39
Daniela Fogli – Elementi di Informatica e Programmazione
40
Equivalenza fra formule booleane
Esempi
Esempi di formule booleane
((x+y)—z)
x1x2 + x1x2x3 = x1 (x2+x2x3)
((x1—x2)+(x3—(x4+x5)))
x1 + x2 + x2x3 + x2x3 = x1 + x2 + x3(x2+x2) = x1 + x2 +
x3
Valgono le regole classiche di semplificazione delle parentesi e di
priorità degli operatori:
x1x2 + x1x2x3 + x1x2 = x1x2 + x1x2x3 = x1x2 (1 +x3) = x1x2
((x1—x2)+(x3—(x4+x5))) ⇒ x1—x2+x3—(x4+x5)
… e il simbolo “—” di solito si omette
Equivalenza di formule booleane:
per ogni combinazione di valori delle variabili le formule
restituiscono lo stesso valore
Daniela Fogli – Elementi di Informatica e Programmazione
Equivalenza fra formule booleane
Verifica tramite tabella
x2
0
0
1
1
0
0
1
1
x1
0
1
0
1
0
1
0
1
x2
1
1
0
0
1
1
0
0
Assorbimento:
x2x3 x2x3 x1+x2+x2x3+x2x3 x1+x2+x3
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
0
1
1
1
0
1
1
Daniela Fogli – Elementi di Informatica e Programmazione
42
Tabelle di verità e proprietà dell’Algebra
di Boole: Esempio
x1 + x2 + x2x3 + x2x3 = x1 + x2 + x3
x3
0
0
0
0
1
1
1
1
Daniela Fogli – Elementi di Informatica e Programmazione
41
x
0
0
1
1
43
y
0
1
0
1
x(x+y) = x
x+y x(x+y)
0
0
1
0
1
1
1
1
Daniela Fogli – Elementi di Informatica e Programmazione
44
Tabelle di verità e proprietà dell’Algebra
di Boole: Esempio (2)
Tabelle di verità e proprietà dell’Algebra
di Boole: Esempio (3)
NB: si può usare anche una diversa simbologia per i valori …
Assorbimento:
x
F
F
V
V
y
F
V
F
V
x(x +y) = x
Assorbimento:
x
F
F
V
V
x+y x(x+y)
F
F
V
F
V
V
V
V
Daniela Fogli – Elementi di Informatica e Programmazione
45
Tabelle di verità e proprietà dell’Algebra
di Boole: Esempio
Proprietà di De Morgan:
x
0
0
1
1
y
0
1
0
1
xy
0
0
0
1
xy
1
1
1
0
x
1
1
0
0
Daniela Fogli – Elementi di Informatica e Programmazione
y
F
V
F
V
x AND (x OR y) = x
x OR y
F
V
V
V
x AND (x OR y)
F
F
V
V
Daniela Fogli – Elementi di Informatica e Programmazione
46
Esercizi
Costruire le tabelle di verità delle seguenti formule booleane:
1. (x + y) + (xy) che è equivalente a scrivere
(x OR y) OR NOT(x AND y)
2. ((x + z) + y) + (xz) che è equivalente a scrivere
NOT ((x OR z) OR y) OR (x AND z)
xy= x+y
y
1
0
1
0
… o per gli operatori …
x+y
1
1
1
0
Usando gli assiomi e le proprietà dell’algebra di Boole
dimostrare le seguenti equivalenze di formule booleane:
1. xyz + xyz + xyz + x = x
2. x y + x y + x y = x + y
47
Daniela Fogli – Elementi di Informatica e Programmazione
48
Tipologie di codici
Codifica binaria dei caratteri
Quanti oggetti?
10 cifre
26 lettere minuscole + 26 lettere maiuscole = 52
~30 segni di interpunzione
~30 caratteri di controllo (LF, CR, EOF, …)
~120 oggetti ⇒ k = log2120 = 7 (sufficienti 7 bit)
Nel seguito vedremo tipologie di rappresentazioni
diverse:
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
Il codice ASCII utilizza 7 bit e quindi può rappresentare al
massimo n = 27 = 128 caratteri
Codice ASCII esteso: utilizza 8 bit e quindi codifica 256
caratteri
Codice UNICODE: utilizza 16 bit e quindi codifica 65536
caratteri (anche quelli delle lingue orientali… non tutti! Sono
circa 200 000! …e aumentano!) ⇒ Estensione a 21 bit del
codice UNICODE
Codici di compressione (senza | con perdita)
Daniela Fogli – Elementi di Informatica e Programmazione
49
Daniela Fogli – Elementi di Informatica e Programmazione
50
ASCII Table
Dec Hx Oct Char
Dec Hx Oct Char
Dec Hx Oct Char
Dec Hx Oct Char
---------------
---------------
---------------
---------------
0
0 000 NUL (null)
32 20 040 SPACE
64 40 100 @
96 60 140 `
1
1 001 SOH (start of heading)
33 21 041 !
65 41 101 A
97 61 141 a
2
2 002 STX (start of text)
34 22 042 "
66 42 102 B
98 62 142 b
3
3 003 ETX (end of text)
35 23 043 #
67 43 103 C
99 63 143 c
4
4 004 EOT (end of transmission)
36 24 044 $
68 44 104 D
100 64 144 d
5
5 005 ENQ (enquiry)
37 25 045 %
69 45 105 E
101 65 145 e
6
6 006 ACK (acknowledge)
38 26 046 &
70 46 106 F
102 66 146 f
7
7 007 BEL (bell)
39 27 047 '
71 47 107 G
103 67 147 g
8
8 010 BS
40 28 050 (
72 48 110 H
104 68 150 h
9
(backspace)
41 29 051 )
73 49 111 I
10
A 012 LF
9 011 TAB (horizontal tab)
(NL line feed, new line) 42 2A 052 *
74 4A 112 J
106 6A 152 j
11
B 013 VT
(vertical tab)
75 4B 113 K
107 6B 153 k
12
C 014 FF
(NP form feed, new page) 44 2C 054 ,
76 4C 114 L
108 6C 154 l
13
D 015 CR
(carriage return)
45 2D 055 -
77 4D 115 M
109 6D 155 m
14
E 016 SO
(shift out)
46 2E 056 .
78 4E 116 N
110 6E 156 n
15
F 017 SI
(shift in)
47 2F 057 /
79 4F 117 O
111 6F 157 o
16 10 020 DLE (data link escape)
48 30 060 0
80 50 120 P
112 70 160 p
17 11 021 DC1 (device control 1)
49 31 061 1
81 51 121 Q
113 71 161 q
18 12 022 DC2 (device control 2)
50 32 062 2
82 52 122 R
114 72 162 r
19 13 023 DC3 (device control 3)
51 33 063 3
83 53 123 S
115 73 163 s
52 34 064 4
84 54 124 T
116 74 164 t
20 14 024 DC4 (device control 4)
43 2B 053 +
53 35 065 5
85 55 125 U
117 75 165 u
22 16 026 SYN (synchronous idle)
54 36 066 6
86 56 126 V
118 76 166 v
23 17 027 ETB (end of trans. block)
55 37 067 7
87 57 127 W
119 77 167 w
24 18 030 CAN (cancel)
56 38 070 8
88 58 130 X
120 78 170 x
57 39 071 9
89 59 131 Y
(end of medium)
In generale interessa rappresentare non solo i caratteri che
compongono un testo ma anche altre caratteristiche di
formattazione quali:
lo stile di scrittura (grassetto, corsivo, sottolineato,…)
la dimensione del carattere
il tipo o “font” (times new roman, arial, courier,…)
l’ampiezza dei margini della pagina
…
105 69 151 i
21 15 025 NAK (negative acknowledge)
25 19 031 EM
Codifica binaria di testi
Esistono diversi codici, detti formati che consentono di
rappresentare un insieme più o meno ampio di caratteristiche:
testo semplice (text o txt): corrisponde a una sequenza di caratteri
ASCII senza caratteristiche di formattazione
testo arricchito (rich text format o rtf): in grado di rappresentare
un ristretto insieme di formattazioni (stile, dimensione, colori)
testo Word (document o doc): in grado di rappresentare un insieme
ampio di formattazioni
121 79 171 y
26 1A 032 SUB (substitute)
58 3A 072 :
90 5A 132 Z
122 7A 172 z
27 1B 033 ESC (escape)
59 3B 073 ;
91 5B 133 [
123 7B 173 {
28 1C 034 FS
(file separator)
60 3C 074 <
92 5C 134 \
124 7C 174 |
29 1D 035 GS
(group separator)
61 3D 075 =
93 5D 135 ]
125 7D 175 }
30 1E 036 RS
(record separator)
62 3E 076 >
94 5E 136 ^
126 7E 176 ~
31 1F 037 US
(unit separator)
63 3F 077 ?
95 5F 137 _
127 7F 177 DEL
Daniela Fogli – Elementi di Informatica e Programmazione
51
Daniela Fogli – Elementi di Informatica e Programmazione
52
Formati dei documenti
per stampa e visualizzazione
Formati standardizzati che sono orientati alla
produzione di documenti destinati a stampa e
visualizzazione:
Documenti in formato PDF (Portable Document Format,
formato di documento portabile)
Documenti in formato PS (Postcript) - l’applicazione GSview
(Ghostview) legge il formato postcript
Non limitati alla rappresentazione di testo ma possono
includere anche immagini e disegni
Daniela Fogli – Elementi di Informatica e Programmazione
53
Tipologie di codici
Elementi di Informatica e
Programmazione
Nel seguito vedremo tipologie di rappresentazioni
diverse:
La Codifica dell’informazione
(parte 4)
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
Corsi di Laurea in:
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rilevazione e correzione di errori
Ingegneria Civile
Ingegneria per l’Ambiente e il Territorio
Università degli Studi di Brescia
Codici di compressione (senza | con perdita)
Docente: Daniela Fogli
Daniela Fogli – Elementi di Informatica e Programmazione
Rappresentazione di informazioni
multimediali
2
La digitalizzazione
Con appositi metodi e codifiche si possono rappresentare
informazioni complesse con sequenze di bit:
Immagini
Filmati
Suoni
rappresentazione anche
approssimata tramite
sequenze di bit
• Voce
I problemi collegati alla gestione della rappresentazione,
memorizzazione e elaborazione di queste informazioni sono:
la richiesta di elevate capacità di elaborazione (es: calcoli
necessari per riprodurre un video codificato in divx)
occupazione elevata di memoria: per questo si utilizzano
tecniche di compressione dei dati che consentono di ridurre la
richiesta di memoria
• Suoni
0010010100
0010010100
• Immagini
Nel calcolatore
• Filmati
Informazione
“continua”
Daniela Fogli – Elementi di Informatica e Programmazione
3
Daniela Fogli – Elementi di Informatica e Programmazione
4
In cosa consiste la digitalizzazione?
Codifica di un suono…
Problema: codificare tramite una sequenza di bit una
… in una sequenza di bit attraverso
campionamento (nel tempo) e
quantizzazione (in ampiezza)
grandezza fisica (es. volume di un suono) i cui valori si
assumono variabili in un intervallo continuo
Soluzione: processo di digitalizzazione (o
conversione analogica-digitale)
Comprende 2 attività:
Frequenza di campionamento:
numero di campioni acquisiti nell’unità
di tempo (es. numero di campioni al
secondo, misurato in Hertz) - Es.
frequenza di 5 Hz significa acquisizione
di 5 campioni al secondo
Quantizzazione: discretizzazione dei valori attraverso
approssimazione con uno dei valori compresi fra quelli previsti
nella codifica
Campionamento: se la grandezza inoltre varia anche nel
tempo (es. un suono) o nello spazio (es. colore di
un’immagine) occorre selezionare un insieme finito di valori, ad
intervalli (nel tempo o nello spazio) costanti
Daniela Fogli – Elementi di Informatica e Programmazione
Il numero di bit necessari per
codificare ogni valore è il parametro
che qualifica la quantizzazione - Es. con
8 bit posso codificare 256 valori diversi
La quantizzazione è su 4 livelli, quindi il risultato
del campionamento è A2A2A0A1A3A3A1
La successione (codifica digitale) potrebbe essere
10 10 00 01 11 11 01
Daniela Fogli – Elementi di Informatica e Programmazione
5
Rappresentazione dei suoni
nei CD audio
Per ciascun intervallo di tempo viene scelto
l’istante di campionamento ti in cui viene rilevato
il valore della grandezza
6
Dal mondo reale al calcolatore
(e viceversa)
Segnali audio:
Dal mondo reale al calcolatore
onde analogiche campionamento + quantizzazione valori digitali
DIGITALIZZAZIONE
(campionam. & quantizz.)
Frequenza di campionamento:
fc = 44.1 kHz (44.100 campioni) per i 2 canali
NB: HW per
acquisizione sonora
(es. microfono)
Quantizzazione:
16 (2 byte) bit/campione = 65536 valori diversi per campione (numero
di livelli di quantizzazione)
memorizzazione,
eventuali elaborazioni…
Dal calcolatore al mondo reale
Il numero di bit memorizzati è dunque:
Nbit = F(durata, fc, bit/campione)
0010010100
0010010100
Nel calcolatore
Nello standard CDDA (CD Digital Audio) 70 minuti registrazione
richiedono 70 x 60 x 44.100 x 2 x 2 byte ≈ 750 MByte
Daniela Fogli – Elementi di Informatica e Programmazione
…
7
CONVERSIONE
DIGITALE-ANALOGICA
NB: scheda audio riceve i valori
digitali e ricostruisce il segnale
analogico + diffusori
Daniela Fogli – Elementi di Informatica e Programmazione
8
Codifica delle immagini
Alcuni formati audio
Campionamento:
WAVE: .wav, occupano molto spazio (corrisponde a quanto visto
nei lucidi precedenti: ~1MB per minuto)
Nel caso delle immagini è una discretizzazione nello spazio: si
divide l’immagine in quadrati, per ognuno dei quali si dovrà prelevare
un campione che si considera rappresentativo di tutto il quadrato
Questi quadrati sono trattati come elementi di base dell’immagine
digitale: sono chiamati pixel
Quanti più pixel vengono considerati per unità di superficie tanto più
precisa sarà la riproduzione dell’immagine (risoluzione)
MP3 (MPEG-1 Layer 3): grande diffusione su Internet. Utilizza
tecniche di compressione per ridurre le dimensioni (vedi poi).
MPEG nasce da un gruppo di lavoro di standardizzazione
MIDI (Musical Instrument Digital Interface): .mid, i file
memorizzano non suoni ma comandi (es. le note musicali di un
particolare strumento) che vengono inviati ai dispositivi MIDI per
riprodurre i suoni, occupano molto meno spazio dei .wav.
Quantizzazione: codifica del colore associato a ogni pixel
Immagini in bianco e nero: 1 bit per pixel (b/n)
Immagine a scala di grigi: es. un byte per pixel (256 livelli di grigio)
Immagine a colori: es. con modello RGB (colore ottenuto per
sovrapposizione di Rosso Verde e Blu) 3 byte per pixel, uno per ogni
colore primario
Es: tastiera musicale + calcolatore permettono di suonare un brano su
tastiera che viene automaticamente trascritto in notazione musicale in
un file midi che può poi essere anche modificato
Daniela Fogli – Elementi di Informatica e Programmazione
9
Campionamento e quantizzazione: esempio
Daniela Fogli – Elementi di Informatica e Programmazione
10
Daniela Fogli – Elementi di Informatica e Programmazione
12
Campionamento
Maggie Cheung dal film “Hero” di Zhang Yimou (2002)
Daniela Fogli – Elementi di Informatica e Programmazione
11
Quantizzazione
Codifica bitmap (raster) di immagini
Immagine bitmap (o raster):
matrice di pixel
• L’immagine è rappresentata direttamente come matrice di pixel
• Risoluzione: num. di pixel orizzontali X num. di pixel verticali
• Ad ogni pixel è riservato un certo numero di bit:
Per ogni pixel un certo numero di byte
es. 3 byte (colori) o 1 byte (b/n)
Daniela Fogli – Elementi di Informatica e Programmazione
13
Immagini bitmap RGB
•
•
1 bit (per pixel)
2 informazioni diverse (b/n)
4 bit (per pixel)
16 colori o livelli di grigio
8 bit (per pixel)
256 colori o livelli di grigio
16 bit (per pixel)
64K colori (216 = 210 x 26)
24 bit (per pixel)
16M = 224 colori
(più di 16 milioni di colori)
Daniela Fogli – Elementi di Informatica e Programmazione
14
Problemi con immagini bitmap
L’informazione sul colore di ogni pixel occupa 3 byte, uno per ogni
colore primario (rosso, verde, blu)
Ogni ingrandimento fa perdere qualità (l’immagine si
“sgrana”) – vedi prossimo lucido
per evitare questo problema si può usare la codifica
vettoriale
La quantità di colore primario è data da un valore tra 0 e 255 (o
equivalentemente è rappresentato da una sequenza di bit a partire
da 00000000 fino a 11111111)
R=25, G=72, B=78
Occupano molta memoria. Possibili soluzioni:
uso di tavolozze (palette)
formati compressi
codifica vettoriale
R=90, G=85, B=12
R=255, G=255, B=255
R=0, G=0, B=0
Daniela Fogli – Elementi di Informatica e Programmazione
15
Daniela Fogli – Elementi di Informatica e Programmazione
16
Immagini bitmap: esempio
Uso di tavolozze (palette)
Un’immagine RGB occupa:
3 byte x risoluzione verticale x risoluzione
orizzontale
Spesso un’immagine utilizza un numero limitato di colori (scelti
comunque tra l’insieme ampio di tutti i colori rappresentabili)
Esempio: un’immagine RGB con risoluzione 1024x768
pixel necessita di più di 2 MB
Esempio banale: immagine RGB che usa due soli colori (qualsiasi)
Dimensioni senza palette: numero pixel * 3 byte
Idea: il formato memorizza i colori usati in un’area specifica
(palette) e per ogni pixel si indica quale dei due colori usato
… e se la
ingrandisco si
sgrana…
0
1
Insieme dei
16 M colori
Tavolozza
(2*3 byte)
0
1
1
…
1
1
0
Matrice (1 bit per pixel)
IMMAGINE CODIFICATA
Daniela Fogli – Elementi di Informatica e Programmazione
17
Daniela Fogli – Elementi di Informatica e Programmazione
Esercizio
Esercizio
Un’immagine di risoluzione 1024*768 utilizza 256 colori RGB.
Quali dimensioni occupa la sua codifica se si utilizza una palette?
E se non la si utilizza?
Un’immagine di risoluzione 1024*768 utilizza 256 colori RGB.
Quali dimensioni occupa la sua codifica se si utilizza una palette?
E se non la si utilizza?
18
Senza utilizzare palette:
1024 * 768 * 3 byte = 210 * 3 * 28 * 3 byte
= 2.359.296 byte
Con utilizzo di palette:
- 256 * 3 byte = 768 byte (per codificare la tavolozza)
- a cui si sommano 1024 * 768 * 1 byte (per la matrice)
⇒ TOTALE = 768 + 786.432 = 787.200 byte
Daniela Fogli – Elementi di Informatica e Programmazione
19
Daniela Fogli – Elementi di Informatica e Programmazione
20
I formati di file bitmap
Codifica vettoriale di immagini
Le immagini sono rappresentate tramite un insieme di elementi
grafici (linee, rettangoli, ellissi, archi e curve)
Memorizzazione come coordinate numeriche o formule
matematiche che specificano forma e posizione: occupa poca
memoria (es. un cerchio solo centro e raggio, una retta le
coordinate degli estremi)
Necessaria un’operazione di rendering (rasterizzazione)
che, a partire dalla descrizione matematica, produca l’immagine
raster
Programmi di tipo draw (programmi di grafica vettoriale):
es. Corel Draw, programmi di CAD, programmi di grafica
tridimensionale
Vantaggi:
BMP: formato standard non compresso per MS Windows, 24 bit
per pixel, .bmp. Gestisce palette a 2, 16, 256 colori + true color
TIFF (Tagged Image File Format): alta qualità (32 bit per pixel),
16 milioni di colori (24 bit) + ulteriori proprietà, dimensioni file
molto grandi, .tif, adottato da scanner e macchine fotografiche
FORMATI COMPRESSI:
GIF (Graphic Interchange Format): formato compresso, 8 bit per
pixel (256 colori), .gif
JPEG (Joint Picture Experts Group): 16 milioni di colori, formato
compresso (più del gif), .jpg
Controllo accurato di linee e colori
Ingrandimento, riduzione, rotazione senza perdita
Possibilità inserimento testo attorno agli oggetti
JPEG 2000: formato ancor più compresso, .j2k o .jp2
Alcuni formati: DXF, DWG, CDR, AI, WMF
Daniela Fogli – Elementi di Informatica e Programmazione
21
Daniela Fogli – Elementi di Informatica e Programmazione
22
Codifica di sequenze video
Immagini vettoriali: esempio
In teoria, una sequenza video è semplicemente una
sequenza di fotogrammi (immagini):
campionamento nel tempo (successione di fotogrammi)
ciascun fotogramma rappresentato normalmente
(campionamento nello spazio e quantizzazione)
In pratica, le dimensioni risulterebbero troppo elevate.
Facendo un conto “a spanne”, se un’immagine occupa
1 MB con 25 fotogrammi al secondo:
25 MB al secondo
25 x 60 MB al minuto = circa 1,5 GB al minuto!
Tecniche di compressione specifiche per le sequenze video
Daniela Fogli – Elementi di Informatica e Programmazione
23
Daniela Fogli – Elementi di Informatica e Programmazione
24
Mondo analogico e mondo digitale
Rappresentazione analogica e digitale
Come è rappresentato un brano musicale su un vecchio disco di vinile?
Rappresentazione analogica: le configurazioni assunte dal supporto
possono variare in modo continuo e riflettono secondo una
analogia diretta la struttura dell’informazione
Limite: applicabile solo se esiste un supporto in grado di ricreare
tra le sue configurazioni una struttura corrispondente a quella
presente sull’insieme degli elementi di informazione
rappresentazione analogica (la forma del
solco descrive per analogia il suono da
produrre)
Come è rappresentato un brano musicale su un CD?
Rappresentazione digitale: l’insieme delle configurazioni è finito (e
fissato a priori) e la struttura dell’informazione si può dedurre dalle
configurazioni solo attraverso una specifica regola di codifica.
Limite: si può rappresentare un insieme di elementi di
informazione finito e predefinito (se emerge l’esigenza di codificare
un nuovo elemento, necessario rivedere o estendere la codifica)
0101 0011 0011
rappresentazione
digitale (il supporto dà
una informazione cha va
decodificata)
Daniela Fogli – Elementi di Informatica e Programmazione
25
Daniela Fogli – Elementi di Informatica e Programmazione
26
Perché la rappresentazione digitale?
E perché proprio quella binaria?
Esempio
(a) Corrispondenza fra l’orario e la posizione dell’ago sulla scala
Una qualunque grandezza fisica può essere convertita
in forma digitale (conversione analogico-digitale o
digitalizzazione)
(b) Configurazioni convenzionali: combinazioni di segmenti illuminati
La conversione conduce a perdita di informazione (il
segnale originario non può essere ricostruito in modo
esatto a partire dal segnale digitale). Tuttavia:
Campionamento: è (almeno in linea teorica) reversibile (no perdita di
informazione) se la frequenza di campionamento è sufficientemente alta
Quantizzazione: perdita di informazione arbitrariamente piccola all’aumentare
del numero di livelli di quantizzazione
Inoltre i valori dei segnali analogici in realtà non sono tutti distinguibili (rumore,
imprecisione strumento di misura, ecc.)
Daniela Fogli – Elementi di Informatica e Programmazione
27
Daniela Fogli – Elementi di Informatica e Programmazione
28
Altre ragioni del
“predominio del digitale”
Immunità al rumore (affidabilità)
Volt
Volt
4
4
1
3
3
2
2
2.5
0
0
(a)
In realtà:
Uniformità nella rappresentazione: una varietà ristretta di
dispositivi può realizzare svariate funzioni
3.5 V
1.5 V
1
1
Molte informazioni sono di natura “prettamente simbolica”
+5 V Valore 1
5
5
0
0V
Tecniche di codifica e trasmissione uniformi su tipologie di
informazioni diverse
Valore 0
0
Elaborazione simbolica (numerica) delle informazioni digitali
(mediante operazioni matematiche) in tempi brevi
(b)
Elaborazione digitale per modificare le caratteristiche di un segnale
analogico (es. restauro di incisioni audio o di pellicole
cinematografiche)
• Con (a) sono tollerati disturbi fino a 0.5 V, con (b) fino a 1.25 V
• L’immunità al rumore risulta essere una delle ragioni fondamentali
che hanno determinato il predominio della rappresentazione digitale su
quella analogica
• In particolare la codifica binaria è quella migliore
Daniela Fogli – Elementi di Informatica e Programmazione
29
Daniela Fogli – Elementi di Informatica e Programmazione
30
Tipologie di codici
Elementi di Informatica e
Programmazione
Nel seguito vedremo tipologie di rappresentazioni
diverse:
La Codifica dell’informazione
(parte 5)
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
Corsi di Laurea in:
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rivelazione e correzione di errori
Ingegneria Civile
Ingegneria per l’Ambiente e il Territorio
Università degli Studi di Brescia
Codici di compressione (senza | con perdita)
Docente: Daniela Fogli
Daniela Fogli – Elementi di Informatica e Programmazione
Un esempio: memorizzazione di
informazioni
2
Un esempio: memorizzazione di
informazioni
Informazioni da memorizzare
(ad esempio: in un CD)
Informazioni da memorizzare
(ad esempio: in un CD)
0011010100
0011010100
0011010100
0011010100
1110010100
1110010100
1110010100
1110010100
.
.
.
.
.
.
0010010100
0010010100
0010010100
0010010100
???
Daniela Fogli – Elementi di Informatica e Programmazione
3
Daniela Fogli – Elementi di Informatica e Programmazione
4
Un esempio: trasmissione di
informazioni
0011010100
0011010100
Errore
1011010100
1011010100
1110010100
1110010100
1111010000
1111010000
.
Errore: modifica di un bit (0 diventa 1 oppure 1 diventa 0)
Posso avere uno o più errori
.
.
LA SOLUZIONE
.
.
.
0010010100
0010010100
Su una sequenza di bit, usare dei codici particolari che permettono:
1010010100
1010010100
• Di rivelare la presenza di errori:
CODICI RIVELATORI
???
• Di correggere gli errori, ricostruendo la sequenza originaria:
CODICI CORRETTORI
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
5
Come?
O8
Codice ridondante
L’insieme delle codifiche è un sottoinsieme proprio del codominio
⇒ l’insieme delle non codifiche è non nullo
110
O7
100
O1
011
O3
6
codominio
101
Esempio:
codice
ridondante
a due bit
01
O2
O1
111
dominio
O6
O4
001
O5
010
00
insieme delle
codifiche
O2
000
11
insieme delle
codifiche
10
8 oggetti, 3 bit: il codice è non ridondante
dominio
insieme delle
non-codifiche
codominio
Non è possibile rivelare né correggere errori
Per esempio:
Per rivelare o correggere errori dobbiamo
introdurre della ridondanza
Daniela Fogli – Elementi di Informatica e Programmazione
se codifico O1 e ho un errore (ad esempio sul primo bit)
ottengo 10 ⇒ rivelazione dell’errore
7
Daniela Fogli – Elementi di Informatica e Programmazione
8
Quanto?
Rivelazione: l’idea
Voglio un codice che, per qualunque codifica sia in grado di
rilevare/correggere k errori comunque siano distribuiti
d=5
Esempio: un semplice codice per due entità, 5 bit
Atalanta
Brescia
00000
11111
00000
11111
Distanza tra le
codifiche: d = 5
Fino
a 4 errori
• Si può dimostrare che si possono rivelare fino a k = 4 errori
(d ≥ k+1)
Data una codifica (es. 00000) un’alterazione di un numero di bit
minore o uguale a k = 4 non può generare l’altra codifica (11111)
poiché la distanza è 5 (k + 1)
• Si può dimostrare che si possono correggere fino a k = 2 errori
(d ≥ 2k+1)
Daniela Fogli – Elementi di Informatica e Programmazione
9
Correzione: l’idea
Daniela Fogli – Elementi di Informatica e Programmazione
10
In generale
d = 5 ≥ 2k+1
k
Distanza fra due sequenze di bit: numero di bit di pari posto che
hanno diverso valore nelle due sequenze (es. la distanza fra 00010111
e 10010000 è 4)
k
≥1
00000
11111
Distanza di un codice: minimo valore delle distanze tra ogni coppia
di elementi appartenenti all’insieme delle codifiche
≥ k+1
Rivelazione e correzione di errori
Data una codifica (es. 00000) un’alterazione di un numero di bit minore o
uguale a k = 2 può generare una non-codifica che può essere corretta
associando ad essa la codifica avente distanza minima
• Per rivelare k errori, un codice deve avere distanza d con
d ≥ k+1
• Per correggere k errori, un codice deve avere distanza d con
d ≥ 2k+1
Es. sia 00000 la codifica di partenza e 10100 una non-codifica con k = 2
errori, la codifica associata con distanza minima è proprio 00000, invece
avendo la non-codifica 11100 (codifica 00000 con 3 errori) non posso risalire
alla codifica perché correggendo troverei 11111
Daniela Fogli – Elementi di Informatica e Programmazione
11
Daniela Fogli – Elementi di Informatica e Programmazione
12
Codice di parità
Esercizio
Esempio di codice rilevatore: il codice di parità
Per codificare i tre simboli D, F, I si utilizza il seguente codice a 5 bit:
Dato un codice: si aggiunge un bit in modo che il numero
di 1 sia pari (parità pari) [o dispari (parità dispari)]
Esempio
1
Codice ASCII a 7 bit
0011100
D
00000
F
11100
I
10011
Errori di trasmissione possono dar luogo alla modifica di uno o più bit.
a) Quanti errori è in grado di rivelare il codice in generale?
Bit di parità (codice a parità pari)
b) E quanti errori è in grado di correggere?
d = 2 (a partire da una codifica con un numero pari di 1 è
necessario modificare almeno 2 bit per ottenere una sequenza che
a sua volta abbia un numero pari di 1, ovvero che sia una codifica)
⇒ può rivelare un errore, correggerne nessuno
Daniela Fogli – Elementi di Informatica e Programmazione
13
Soluzione
Daniela Fogli – Elementi di Informatica e Programmazione
14
Esercizio
d12 = 3
Si consideri il codice a tre valori originari
d23 = 4
‘1’ codificato con 000000
d13 = 3
‘2’ codificato con 000001
la distanza del codice è pari a 3
‘3’ codificato con 111111
a) Trovare quanti errori può correggere e rivelare in generale.
a) Errori rilevati:
b) Si supponga di ricevere la sequenza 001111.
Assumendo che possano essere stati compiuti al più 2 errori, è
possibile decodificare correttamente la sequenza?
Come si giustifica la risposta in relazione al risultato
trovato nel punto a)?
d ≥ k+1 quindi kmax = 2 (possono essere rivelati 2 errori)
b) Errori corretti:
d ≥ 2k+1 quindi kmax = (3-1)/2=1
(può essere corretto 1 errore)
Daniela Fogli – Elementi di Informatica e Programmazione
15
Daniela Fogli – Elementi di Informatica e Programmazione
16
Soluzione (a)
Soluzione (b)
b) Ricevo 001111, mentre avevo:
a) Risulta:
d12 = 1
d23 = 5
‘1’ d13 = 6
‘2’ 000001
dist2 = 3
001111
⇒ il codice non può (in generale) rivelare né tanto meno
correggere alcun errore [errori rilevati: d ≥ k+1, quindi
con k=1 serve d ≥ 2]
‘3’ 111111
dist3 = 2
001111
In questo caso posso decodificare 001111 con il valore “3”.
Se sono stati commessi al più due errori, sono sicuro che la
decodifica è corretta, perché:
[000000 non può essere modificato in 001111]
dist1 = 4 > 2
dist2 = 3 > 2
17
Perchè?
[000001 non può essere modificato in 001111]
Daniela Fogli – Elementi di Informatica e Programmazione
18
Tipologie di codici
Come mai posso correggere due errori anche se
(cfr. punto a) il codice ha distanza 1?
Nel seguito vedremo tipologie di rappresentazioni
diverse:
La distanza del codice si riferisce al “caso peggiore”
(distanza minima) ⇒ le relative formule garantiscono le
proprietà del codice di rivelazione e correzione di errori
in ogni caso, ovvero per qualunque simbolo
rappresentato e per qualunque posizione degli errori
Senza assumere limitazioni sul numero di bit a disposizione:
per numeri [notazione binaria, ovvero posizionale con base 2]
Disponendo di un numero di bit limitato:
numeri naturali
interi relativi [valore assoluto e segno, compl. a 1, compl. a 2]
“reali” [virgola fissa e virgola mobile]
valori logici, caratteri alfabetici, testi
suoni, immagini e sequenze video
codici per la rivelazione e correzione di errori
Per esempio, nel caso venga trasmesso ‘1’ (codificato
con 000000), è sufficiente un errore sull’ultimo bit per
ottenere 000001, che è pari alla codifica di ‘2’: in tal
caso l’errore non verrebbe neppure rivelato!
Daniela Fogli – Elementi di Informatica e Programmazione
dist1 = 4
001111
quindi la distanza del codice è 1
Daniela Fogli – Elementi di Informatica e Programmazione
000000
Codici di compressione (senza | con perdita)
19
Daniela Fogli – Elementi di Informatica e Programmazione
20
La compressione dei dati
Concetti fondamentali
Cambiando modalità di codifica è possibile ridurre il numero dei
bit richiesti
Vantaggi per memorizzazione e trasmissione
Per qualunque tecnica di compressione: data una
sequenza di bit S
Denotiamo con |S| il numero dei bit della sequenza
funzione di compressione Fc t.c. |Fc(S)| < |S|
rapporto di compressione |S|/|Fc(S)| (NB: > 1)
funzione di decompressione Fd per ricostruire la successione
originaria: Fd(Fc(S))
Esempio:
rappresentare una sequenza di 1 milione di caratteri, ognuno
appartenente all’insieme {A, C, G, T}
se uso 4 configurazioni a 2 bit ho bisogno di 2 milioni di bit
ma se so che la frequenza dei caratteri all’interno della sequenza varia
(es. 50% A, 25% C, 12.5% G e T) allora posso usare una codifica
diversa: A = 0, C = 10, G = 110 e T = 111
Num. bit complessivi = (1x50%+2x25%+3x12.5%+3x12.5%) x 1
milione = 1.75 milioni
Ho ridotto il numero di bit senza perdere informazione
Daniela Fogli – Elementi di Informatica e Programmazione
Due tipi di compressione dei dati:
senza perdita (lossless)
è garantito che Fd(Fc(S)) = S, ovvero Fd=Fc-1
con perdita (lossy)
(perdita di informazione)
in generale Fd(Fc(S)) ≠ S
21
22
Algoritmi di compressione dati con perdita
Algoritmi di compressione dati senza perdita
Si adottano quando non si può perdere informazione, es. programmi
in formato eseguibile, file doc
Svantaggio: ridotto rapporto di compressione
Principio fondamentale: sottosequenze di bit frequenti sostituite con
codici opportuni
Esempi:
Si applicano a dati che hanno origine nel mondo analogico (suoni,
immagini, sequenze video, ecc.)
Si adottano quando si è disposti a perdere una parte
dell’informazione durante la compressione: compromesso
qualità/rapporto di compressione
Tecniche dipendenti dalla natura del segnale considerato:
formati ZIP e RAR (con un apposito programma di utilità - es. winzip si può creare un archivio in cui i file vengono memorizzati in formato
compresso)
formato GIF (per le immagini raster): utilizzo di un “dizionario” con le
configurazioni di valori che si ripetono
Daniela Fogli – Elementi di Informatica e Programmazione
Daniela Fogli – Elementi di Informatica e Programmazione
per i suoni, variazioni di volume e frequenza al di sotto di una certa
soglia non sono percepite dall’orecchio umano; inoltre i suoni a basso
volume sovrapposti a suoni di volume maggiore sono poco udibili
(formato compresso MP3)
per le immagini, lievi cambiamenti di colore in punti contigui non sono
percepiti dall’occhio umano (formato JPEG)
nelle animazioni video, immagini successive hanno spesso molte parti
uguali e si possono codificare solo le differenze (formato MPEG)
23
Daniela Fogli – Elementi di Informatica e Programmazione
24