Codifica binaria dell`informazione - SisInf Lab

4. Codifica binaria dell’informazione
Ing. Simona Colucci
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Codifica binaria dell’informazione
• Tutte le informazioni vanno tradotte in bit(organizzati poi
in byte o parole):
–
–
–
–
–
–
Numeri naturali
Numeri interi(con segno)
Numeri frazionari
Numeri reali
Caratteri
Immagini
• Nell’interazione con il calcolatore la codifica in binario e
la decodifica in formato leggibile sono trasparenti
all’utente
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Numeri naturali:
Sistemi di numerazione
• Un sistema di numerazione è composto da:
– Insieme finito di simboli o cifre
– Regole che permettono di rappresentare i numeri naturali
• Classificazione
– Sistemi additivi (Es. sistema romano parzialmente):
• Ogni cifra assume un valore prefissato
• Il numero si ottiene addizionando le cifre che lo compongono
• Impossibilità di rappresentare numeri molto grandi e difficoltà di esecuzione
delle operazioni matematiche
– Sistemi posizionali (Es. sistema decimale):
• Le cifre acquistano un peso diverso a seconda della posizione che occupano
• Un numero generico di m cifre è rappresentato in base p dalla sequenza:
an, an-1, an-2,..., a0
an : cifra più significativa
a0 : cifra meno significativa
n = m-1
ai  {0, 1, ..., p-1}
• Compattezza di rappresentazione anche per numeri molto grandi e facilità di
esecuzione delle operazioni
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi posizionali:
Rappresentazione in base p
Sistemi Informativi
DEE - Politecnico di Bari
Numero naturale N, composto da m cifre, in base p:
• Rappresentazione
n
N p  an  p n  an 1  p n 1  ...  a1  p1  a0  p 0   ai  p i
i 0
•
Spazio di Rappresentazione:
numeri nell’intervallo discreto [0 , pm - 1]
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Il sistema decimale:
rappresentazione in base 10
• Sistema posizionale
– Esempio: 123 = 100 +20 +3
• Base: p = 10
• Insieme di simboli: ai  {0,1,2,3,4,5,6,7,8,9}
• Numero naturale N di m cifre:
– Rappresentazione:
• N10 = an·10n+an- 1·10n-1+…+a0·100
• Esempio, con m=3:
58710 = 5·102+8·101+7·100
n=m-1
– Spazio di rappresentazione: intervallo discreto [0, 10m-1]
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Sistema binario:
Rappresentazione in base due
• Sistema posizionale
• Base binaria: p=2
• Insieme di simboli: ai  {0, 1}
– Simboli chiamati bit (binary digit)
– Otto bit chiamati byte
• Numero naturale N di m cifre:
– Rappresentazione:
• N2 = an·2n+ an-1·2n-1+…+a0·20
n=m-1
• Esempio, con m=5:
110112 = (1·24+1·23+0·22+1·21+1·20)10 = 2710
– Spazio di rappresentazione:
• intervallo discreto [0 , 2m -1]
• Esempio con m=8: [000000002 , 111111112],
ovvero: [010 , 25510]
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
•
•
•
•
Il sistema binario: unità di misura
kilobyte(Kb) = 210 byte = 1024 byte
megabyte(Mb) = 220 byte = 1048576 byte
gigabyte(Gb) = 230 byte = 1073741824 byte
terabyte(Tb) = 240 byte = 1099511627776 byte
Le approssimazioni a potenze di 10:
• sono accettabili solo per i kilobyte: 1024 ~1000
• sono inaccettabili per 104 ,105 ,106
• le lettere maiuscole nel simbolo indicano che non si tratta
delle potenze di 10 del sistema internazionale
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Basi ottale ed esadecimale
DEE - Politecnico di Bari
•
Rappresentazione in base 8:
– Base ottale: p=8;
– Insieme di simboli ai  {0, 1, 2, 3, 4, 5, 6, 7}
– Numero N di m cifre:
• Rappresentazione: N8 = (an·8n+an-1·8n-1+…+ a0·80)10
Es. 2348 = (2·82+3·81+4·80)10 = 15610
• Spazio di rappresentazione: [0, 8m-1]
•
n=m-1
Rappresentazione in base 16:
– Base esadecimale: p=16;
– Insieme di simboli ai  {0, 1, 2, …, 9, A, B, C, D, E, F}
• Notare: “11” al posto di “B” e “15” al posto di “F”, i loro equivalenti in base
dieci
– Numero N di m cifre:
• Rappresentazione: N16 = (an·16n+an-1·16n-1+…+ a0·160)10
Esempio: B7F16 = (11·162+7·161+15·160)10 = 294310
• Spazio di rappresentazione: [0, 16m-1]
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
n=m-1
Sistemi Informativi
Conversioni di base
DEE - Politecnico di Bari
• Per convertire da base p a base 10:
N p  an  p  an 1  p
n
n 1
n
 ...  a1  p  a0  p   ai  p i
1
0
i 0
Esempio: 110112 = (1·24+1·23+0·22+1·21+1·20)10 = 2710
• Per convertire da base dieci a base due:
– Metodo delle divisioni successive: esempio
331:2
165:2
82:2
41:2
20:2
10:2
5:2
2:2
1:2
= 165
= 82
= 41
= 20
= 10
= 5
= 2
= 1
= 0
con resto di 1
con resto di 1
con resto di 0
con resto di 1
con resto di 0
con resto di 0
con resto di 1
con resto di 0
con resto di 1
(331)10=(101001011)2
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Conversioni di base
• Le basi ottale ed esadecimale sono di interesse
informatico per la facilità di conversione, con il
metodo”per parti”:
– Da base 2 a base 8: si converte a gruppi di tre bit, traducendo
ciascuna tripla nella corrispondente cifra ottale
(001010110111)2=(1267)8
– Da base 2 a base 16: si converte a gruppi di quattro bit,
traducendo ciascuna quadrupla nella corrispondente cifra
esadecimale
(001010110111)2=(2B7)16
• La base ottale ed esadecimale consentono una grande
sintesi di rappresentazione
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Somma
DEE - Politecnico di Bari
•
Le cifre sono 0 e 1 ed il riporto può essere solo 1
Riporto
precedente
Somma
Risultato
Riporto
0
0+0
0
0
0
0+1
1+0
1
0
0
1+1
0
1
1
0+0
1
0
1
0+1
1+0
0
1
1
1+1
1
1
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
•
Esempio di somma e carry
Esempio:
1  riporto
0101 +
(510)
1001 =
(910)
-----1110
(1410)
111
 riporti
1111 +
1010 =
------carry  11001
(1510)
(1010)
(2510 se uso 5 bit;
910 se considero 4 bit: errato)
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Numeri interi
• Includono anche i numeri negativi
• Rappresentati tramite il segno ed il valore del numero
• Codifica binaria secondo uno delle due modalità
seguenti:
– Rappresentazione in modulo e segno
– Rappresentazione in complemento a due
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Modulo e segno
DEE - Politecnico di Bari
•
In un numero di m bit il primo bit è utilizzato per memorizzare il segno:
– “1” numero negativo
– “0” numero positivo
•
•
Spazio di rappresentazione: tra -(2m-1-1) e (2m-1-1)
Fenomeno dello zero positivo e negativo
Esempio m=3
Num. intero, base 10
Num. intero, base due, modulo e segno
–3
111
–2
110
–1
101
–0
100
+0
000
+1
001
+2
010
+3
011
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Complemento a due (CPL2)
DEE - Politecnico di Bari
• Usando m bit: (-N)CPL2 = (2m - N10)2
• Spazio di rappresentazione: intervallo discreto [-2m-1 , 2m-1 - 1]
– Asimmetria tra negativi e positivi
– Esempio (m=8): [-128, +127], perché -27 = -128 e 27 - 1 = +127
• Tutti i numeri negativi cominciano con il bit più significativo posto a
“1”, mentre tutti i positivi e lo zero iniziano con uno “0”
Esempio m=3
(-N)CPL2 =(23-N10)2
Num. intero base 10
Trasformazione
Num. intero, base 2, CPL2,
-4
8-4=4
410 = 100
-3
8-3=5
510 = 101
-2
8-2=6
610 = 110
-1
8-1=7
710 = 111
0
nessuna
010 = 000
1
nessuna
110 = 001
2
nessuna
210 = 010
3
nessuna
310 = 011
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
m=3
Sistemi Informativi
Complemento a due (CPL2)
DEE - Politecnico di Bari
• Metodo alternativo per ottenere (-N)CPL2
– Complementare i bit della rappresentazione binaria del modulo
N(cambiare gli 1 in 0 e viceversa)
– Sommare 1 al risultato ottenuto
Esempio:
-N= -3
N=(3)10=(011)2
complemento ad 1
complemento a 2
100
101
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
•
•
•
Somma e sottrazione in CPL2
Somma: come per i naturali
Sottrazione: N1 - N2 = N1 + (-N2)CPL2
Carry:
– Il carry finale non viene considerato!
•
Overflow:
– Se, sommando due interi di m bit dotati di segno concorde, ottengo un
risultato di segno discorde (sempre considerando m bit), allora si ha un
overflow (il risultato non è codificabile su m bit) e l’operazione è errata
– L’overflow non può verificarsi se gli operandi sono di segno discorde
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Somma e sottrazione in CPL2
DEE - Politecnico di Bari
Esempi: m=7 spazio di rappresentazione [-64, +63]
+5
00101
+5
00101
-5
11011
-63
1000001
+8
01000
-8
11000
+8
01000
-8
1111000
+13
01101
-3
11101
+3
(1)00011
RIPORTO
-71
[1](1)0111001
OVERFLOW
RIPORTO
•Perché ignorare il riporto finale in CPL2 ad m bit?
Esempio: base=10
10180-9878=302=
= 10180 -9878 +10000-10000=
= 10180+(10000-9878)-10000=
(10000-9878)- è il complemento a 10 del sottraendo: (9878)CPL10
= 10180+122-10000=
si addiziona al minuendo il complemento a 10 del sottraendo
= 10302-10000=
questa sottrazione equivale a trascurare la cifra piu significativa
= 302
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
•
•
•
Caratteri
Codifica numerica tramite 1 byte
ASCII (American Standard Code for Information Interchange) utilizza 7
bit (estesa talvolta a 8 bit per rappresentare altri 128 caratteri)
L’ASCII codifica:
– I caratteri alfanumerici (lettere maiuscole e minuscole e numeri), compreso
lo spazio
– I simboli (punteggiatura, @, #, …)
– Alcuni caratteri di controllo che non rappresentano simboli visualizzabili
(TAB, LINEFEED, RETURN, BELL, ecc)
– Non codifica per esempio le lettere accentate o greche
•
L’ ottavo bit o un nono possono essere usati come bit di parità: rende
pari il numero di 1 in modo che se esso risulta dispari ci si accorge di
errori di immagazzinamento o trasmissione dati.
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Tabella ASCII (parziale)
DEE - Politecnico di Bari
DEC
48
CAR
0
DEC
65
CAR
A
DEC
75
CAR
K
DEC
97
CAR
a
DEC
107
CAR
k
49
1
66
B
76
L
98
b
108
l
50
2
67
C
77
M
99
c
109
m
51
3
68
D
78
N
100
d
110
n
52
4
69
E
79
O
101
e
111
o
53
5
70
F
80
P
102
f
112
p
54
6
71
G
81
Q
103
g
113
q
55
7
72
H
82
R
104
h
114
r
56
8
73
I
83
S
105
i
115
s
57
9
74
J
84
T
106
j
116
t
85
U
117
u
86
V
118
v
87
W
119
w
88
X
120
x
89
Y
121
y
90
Z
122
z
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Codifica delle immagini
DEE - Politecnico di Bari
L’immagine digitale
•
•
•
•
Le immagini sono codificate come sequenze di bit
Digitalizzazione: passaggio dall’immagine alla sequenza binaria
L’immagine è suddivisa in una griglia di punti (detti pixel)
Ogni pixel è descritto da un numero (su 8, 16, 24, o 32 bit) che ne
rappresenta il colore(un particolare tono di grigi nelle immagini bianco
e nero)
– Es. con 8 bit  28 = 256 combinazioni di colore
• Per decodificare la sequenza binaria che codifica l’immagine bisogna
conoscere:
– le dimensioni dell’immagine : larghezza e altezza in pollici del rettangolo in
cui è contenuta
– la risoluzione dell’immagine :numero di pixel per pollice (dpi - dot per inch)
– il numero di colori o toni di grigio disponibili per ogni pixel
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
L’immagine digitale
DEE - Politecnico di Bari
• Standard di codifica:
– TIFF (Tagged Image File Format)
– PNG (Portable Network Graphics)
– JPEG
• Tecniche di compressione
– utilità:
• ridurre lo spazio necessario a rappresentare i punti dell’immagine
• ridurre la quantità di memoria necessaria a memorizzare l’immagine
• ridurre il tempo necessario a trasmettere l’immagine tra i dispositivi
– classificazione:
• compressione lossless : comprime l’immagine senza deteriorarla (TIFF)
– adatte solo per immagini con ampie aree monocromatiche. in cui sequenze di
punti con la stessa tonalità vengono codificate in forma compatta
• compressione lossy: comprimono (molto di più), ma deteriorano l’immagine
(JPEG , PNG)
– adatte ad immagini con molti colori, memorizzano le differenze cromatiche tra
gruppi di pixel
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
DEE - Politecnico di Bari
Operazioni con le informazioni
• Aritmetiche
– Es. Somma e differenza viste prima
• Logiche
– Utilizzano l’algebra di Boole
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Algebra di Boole
DEE - Politecnico di Bari
•
Formalismo basato su tre operazioni logiche (dette anche operazioni
booleane):
– AND operatore binario
– OR operatore binario
– NOT operatore unario
•
•
•
•
Le operazioni booleane si applicano ad operandi che possono assumere solo
due valori: vero o falso
Ogni formula scritta in algebra di Boole può assumere solo due valori: vero
o falso
Rappresentando vero con “1” e falso con “0” un bit può rappresentare un
operando o il valore di una formula in algebra di Boole
Tavole di verità: rappresentano il valore di una espressione
logica(ottenuta a partire dai tre operatori logici) in funzione del valore
degli operandi
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Operatori booleani
DEE - Politecnico di Bari
•
Tavole di verità:
A
B
A AND B
A
B
A OR B
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
1
A
NOT A
0
1
1
0
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Operatori booleani: proprietà
DEE - Politecnico di Bari
•
Commutativa:
– A OR B = B OR A
– A AND B = B AND A
•
Distributiva di uno verso l’altro:
– A OR (B AND C) = (A OR B) AND (A OR C)
– A AND (B OR C) = (A AND B) OR (A AND C)
•
Leggi di De Morgan:
– A AND B = NOT ((NOT A) OR (NOT B))
– A OR B = NOT ((NOT A) AND (NOT B))
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Espressioni booleane
DEE - Politecnico di Bari
•
Regole di precedenza:
– NOT ha la massima precedenza
– poi segue AND
– infine OR
•
•
•
Se voglio alterare queste precedenze devo usare le parentesi (a volte
usate solo per maggior chiarezza)
Per valutare un espressione booleana si usa la tabella della verità
Due espressioni booleane sono equivalenti se e solo se le tabelle della
verità sono identiche
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Dalla formula alla tabella
DEE - Politecnico di Bari
•
Vediamo un esempio, per l’espressione:
D = A AND NOT (B OR C)
A
B
C
D = A AND NOT (B OR C)
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011
Sistemi Informativi
Dalla tabella alla formula
DEE - Politecnico di Bari
•
Se conosco la tabella della verità, posso ricostruire la formula logica.
Partiamo dalla tabella:
NOT A AND B
A AND NOT B
A AND B
A
B
C1
0
0
0
0
1
1
1
0
1
1
1
1
C1 = (NOT A AND B) OR (A AND NOT B) OR (A AND B)
Fondamenti di Informatica
CDL in Ingegneria Gestionale (B) - A.A. 2010-2011