La codifica dell’informazione
Codifica dati e istruzioni

Algoritmo
• descrizione della soluzione di problema scritta in modo
da poter essere eseguita da un esecutore (eventualmente
diverso dall’autore dell’algoritmo)
• sequenza di istruzioni che operano su dati.
dati

Programma
• algoritmo scritto in modo da poter essere eseguito da un
calcolatore (esecutore automatico)

Per scrivere un programma è necessario
rappresentare istruzioni e dati in un formato tale
che l’esecutore automatico sia capace di
memorizzare e manipolare.
Codifica dati e istruzioni

Alfabeto dei simboli
• cifre “0”, “1”, …, “9”, separatore decimale (“,”), separatore delle
migliaia (“.”) e segni positivo (“+”) o negativo (“–”).

Regole di composizione (sintassi), che definiscono le
successioni “ben formate”
• “1.234,5” è la rappresentazione di un numero;
• “1,23,45” non lo è.

Codice (semantica: interpretazione posizionale)
• “1.234,5” = 1×103 + 2×102 + 3×101 + 4×100 + 5×10–1
• “1,23,45” = ??

Lo stesso alfabeto può essere utilizzato con codici diversi:
• “123,456” = 1×102 + 2×101 + 3×100 + 4×10–1 + 5×10–2 + 6×10–3, [IT]
• “123,456” = 1×105 + 2×104 + 3×103 + 4×102 + 5×101 + 6×100, [UK]
Codifica Binaria


Alfabeto binario: usiamo dispositivi con solo due stati (0,1)
Problema: assegnare un codice binario univoco a tutti gli oggetti
compresi in un insieme predefinito (e.g. studenti)

Quanti oggetti posso codificare con k bit:
•
•
•
•
•

1 bit  2 stati (0, 1)  2 oggetti (e.g. Vero/Falso)
2 bit  4 stati (00, 01, 10, 11)  4 oggetti
3 bit  8 stati (000, 001, …, 111)  8 oggetti
…
k bit  2k stati  2k oggetti
Quanti bit mi servono per codificare N oggetti:
• N ≤ 2k  k ≥ log2N  k = log2N (approssimato all’intero superiore)

Attenzione!
ipotesi implicita: i codici hanno tutti la stessa lunghezza
Esempio di codifica binaria

Problema: assegnare un codice binario univoco a
tutti i giorni della settimana

Giorni della settimana: N = 7  k ≥ log27  k = 3

Con 3 bit possiamo ottenere 8 diverse
configurazioni:
• Ne servono 7, quali utilizziamo?
• Quale configurazione associamo a quale giorno?

Attenzione: ipotesi che i codici abbiano tutti la
stessa lunghezza
I giorni della settimana in binario (1)
Lunedì
Martedì
Domenica
Lunedì
Giovedì
0
Martedì
Mercoledì
Lunedì
Martedì
Lunedì
00
Mercoledì
Giovedì
Mercoledì
01
Mercoledì
Domenica
Sabato
Giovedì
Sabato
Venerdì
Venerdì
1 bit
2 “gruppi”
10
Sabato
Venerdì
1
Domenica
Martedì
11
2 bit
4 “gruppi”
Giovedì
Venerdì
Sabato
Domenica
3 bit
8 “gruppi”
000
001
010
011
100
101
110
111
I giorni della settimana in binario (2)
Lunedì
Martedì
Domenica
Mercoledì
Sabato
Giovedì
Venerdì
Sabato
Giovedì
0
Martedì
Domenica
Lunedì
Mercoledì
Venerdì
1 bit
2 “gruppi”
1
Giovedì
00
Sabato
Martedì
Sabato
01
Mercoledì
Domenica
10
Lunedì
Giovedì
11
Martedì
Domenica
Mercoledì
Venerdì
Venerdì
Lunedì
2 bit
4 “gruppi”
3 bit
8 “gruppi”
000
001
010
011
100
101
110
111
Codifica binaria dei caratteri

Quanti sono gli oggetti compresi nell’insieme?
•
•
•
•
26 lettere maiuscole + 26 minuscole  52
10 cifre
Circa 30 segni d’interpunzione
Circa 30 caratteri di controllo (CANC,ESC,INVIO,CTRL,ALT …)
circa 120 oggetti complessivi  k = log2120 = 7

Codice ASCII: utilizza 7 bit e quindi può rappresentare
al massimo 27=128 caratteri
• Con 8 bit (= byte) rappresento 256=28 caratteri (ASCII ext.)
• Oggi si usano codici più estesi: UNICODE 216 = 65535
per rappresentare anche i caratteri delle lingue orientali
ASCII su 7 bit
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
010
sp
!
"
#
$
%
&
'
(
)
*
+
,
-
.
/
011
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
100
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
101
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
110
`
a
b
c
d
e
f
g
h
I
j
k
l
m
n
o
111
p
q
r
s
t
u
v
w
x
Y
z
{
|
}
~
canc
Bit, Byte, KiloByte, MegaByte, …
Bit = solo due stati, “0” oppure “1”.
Byte = 8 bit, quindi 28 = 256 stati
KiloByte [KB] = 210 Byte = 1024 Byte ~ 103 Byte (diff.2%)
MegaByte [MB] = 220 Byte = 1'048'576 Byte ~ 106 Byte
GigaByte [GB] = 230 Byte ~ 109 Byte
TeraByte [TB] = 240 Byte ~ 1012 Byte (differenza 10%)
PetaByte [PB] = 250 Byte ~ 1015 Byte
ExaByte [EB]
= 260 Byte ~ 1018 Byte
Lo standard IEC per i prefissi binari
Grandezza
Nome Simbolo
Dimensione
SI
Diff. %
103
2.40%
Kilo binario
Kibi
Ki
210
Mega binario
Mebi
Mi
(210)2
1'048'576 (103)2
4.86%
Giga binario
Gibi
Gi
(210)3
1'073'741'824 (103)3
7.37%
Tera binario
Tebi
Ti
(210)4
1'099'511'627'776 (103)4
9.95%
Peta binario
Pebi
Pi
(210)5
1'125'899'906'842'624 (103)5 12.59%
Exa binario
Exbi
Ei
(210)6
1'152'921'504'606'846'976 (103)6 15.29%
Zetta binario
Zebi
Zi
(210)7
1'180'591'620'717'411'303'424 (103)7 18.06%
Yotta binario
Yobi
Yi
(210)8 1'208'925'819'614'629'174'706'176 (103)8 20.89%
1'024
• Usando questi prefissi si può risolvere l’ambiguità
• capacità di un disco fisso: 120 GB = 111.76 GiB,
• capacità di un floppy: 1.406 MiB = 1.475 MB
La codifica delle istruzioni

Si segue lo schema presentato per i caratteri
alfanumerici:
• quali e quante sono le istruzioni da codificare?
• qual è la lunghezza delle successioni di bit da utilizzare ?
• qual è la corrispondenza tra istruzioni e successioni di bit ?
Istruzioni
aritmetico-logiche
Codice Istruzione
0111 1100
ADD
0111 1101
SUB
0111 1110
AND
……… ………
Istruzioni per il
trasferimento dati
Codice Istruzione
1110 1000 LOAD
1111 1000 STORE
……… ………
……… ………
Istruzioni di
controllo
Codice Istruzione
0100 1001 IF_EQ
0100 1000 GOTO
0100 1100 RETURN
……… ………
Oltre al codice operativo

… è necessario far riferimento ai dati necessari per
completare l’esecuzione dell’istruzione,
• e.g. addizione: è necessario che sia specificato (anche implicitamente)
dove leggere i due operandi da sommare e dove scrivere il risultato;

il numero dei dati da specificare è variabile, in funzione
delle istruzioni.
Rappresentazione dei numeri
naturali
La rappresentazione dei numeri naturali (0,1,2,…) usata dai latini o dai
greci (I,II,III,…) era del tutto convenzionale, mentre quella da noi usata
(trasmessa dagli arabi) in base dieci (o decimale) si basa su un teorema
fondamentale dell’aritmetica.
Ciascun numero naturale (0,1,2,…) può essere rappresentato da una ed
una sola successione finita di bit, detta rappresentazione binaria o in
base due.
Questa possibilità è conseguenza di un importante Teorema
dell’Aritmetica, lo stesso che consente l’usuale rappresentazione
decimale dei numeri naturali, detta anche rappresentazione in base 10.
Questo Teorema è alla base anche della rappresentazioni dei naturali in
base due (binaria) così come di altre basi (ottale, esadecimale, ecc.)
Per capire questo importante Teorema della rappresentazione dei numeri
naturali, occorre distinguere tra:
i numeri naturali, i loro nomi-concetti e le loro rappresentazioni:
queste ultime possono cambiare a seconda del supporto (base) scelto
Teorema: Rappresentazione dei numeri
naturali
Scelto un numero naturale N (detto base) maggiore o uguale a
2, ogni numero naturale M diverso da 0 può essere
rappresentato in una sola maniera come somma finita di
potenze decrescenti (k, k-1, …) di N moltiplicate per
coefficienti (Ck, Ck-1,… C0) minori di M.
Ossia: scelta una base N≥2, per ogni numero naturale M≠0,
esiste un solo k ed una sola k-pla di numeri (coefficienti) Ck,
Ck-1,…C0 minori di N e con Ck≠0, tale che:
M = (Ck x Nk) + (Ck-1 x Nk-1) + … + (C0 x N0)
Esempi:
se la base N= 10, ventitrè => (2 x 101 ) + (3 x 100) => 23
se la base N= 2, ventitrè => (1 x 24 ) + (0 x 23) + (1 x 22) +
+ (1 x 21) + (1 x 20) => 10111
Esempio 1: Rappresentazione dei numeri naturali
Assumiamo: base N=10 ed M = “duemilacentootto”
- La più grande potenza di 10 presente in N è la terza potenza di
10, cioè 103 ; questa compare ben 2 volte; otteniamo quindi il
primo termine 103 x 2 (= 2000).
- Togliendo (103 x 2) da N, in quel che rimane (centootto), la
seconda potenza di 10, ossia 102 compare 1 volta, quindi
otteniamo il secondo termine 102 x 1 (=100)
- Togliendo (103 x 2)+(102 x 1) da N, in quel che rimane (otto), la
potenza prima di 10, ossia 101,compare 0 volte, quindi
otteniamo il terzo termine 101 x 0 (=0)
- Togliendo infine (103 x 2)+(102 x 1)+(101 x 0) da N, in quel che
rimane (otto), la potenza nulla di 10, ossia 100 (=1) compare 8
volte, quindi otteniamo il quarto ed ultimo termine 100 x 8 (=8)
Pertanto, duemilacentootto in base 10 è rappresentato da:
(103 x 2)+(102 x 1)+(101 x 0)+(100 x8) = 2108dieci
Esempio 2: Rappresentazione dei numeri naturali
Assumiamo: base N=2 ed M = “ventitrè”
- La più grande potenza di 2 presente in N è la quarta potenza di 2, cioè 24;
questa compare 1 sola volta; otteniamo quindi il primo termine 24 x 1 (=16).
- Togliendo (24 x 1) da N, in quel che rimane (sette), la terza potenza di 2,
ossia 23 compare 0 volte, quindi otteniamo il secondo termine 23 x 0 (=0)
- Togliendo (24 x 1)+(23 x 0) da N, in quel che rimane (sette), la seconda
potenza di 2, ossia 22,compare 1 volta, quindi otteniamo il terzo termine
22 x 1 (=4)
- Togliendo (24 x 1)+(23 x 0)+(22 x 0) da N, in quel che rimane (tre), la prima
potenza di 2, ossia 21 (=2) compare 1 volte, quindi otteniamo il quarto
termine 21 x 1(=2)
- Infine, togliendo (24 x 1)+(23 x 0)+(22 x 0)+(21 x 1) da N, in quel che rimane
(uno), la potenza nulla di 2, ossia 20 (=1) compare 1 volta, quindi otteniamo
il quinto ed ultimo termine 20 x 1(=1)
Pertanto, ventitrè in base 2 è rappresentato da:
(24 x 1)+(23 x 0)+(22 x 1)+(21 x 1)+(20 x1) = 10111due
Numeri naturali
Fissata la base, il Teorema assicura l’univocità della “lettura” (o
“interpretazione” o “de-codifica”) della sequenza di simboli
(cifre) di cui si compone il numero dato
 Sistema
di numerazione posizionale in base b
• N = ckck–1…c0 rappresenta ck×bk + ck–1×bk–1 + … + c0×b0
• b=10  1101dieci indica 1×103 + 1×102 + 0×10 + 1×100
• b=2 =>1101due indica 1×1011 + 1×1010 + 0×101 + 1×100
 Conversione
binario  decimale
• basta scrivere il numero secondo la notazione posizionale utilizzando già
il sistema decimale
• b=2  1101due indica 1×23 + 1×22 + 0×2 + 1×20 = 13dieci
Conversione binario  decimale
5
101100due = 1dieci×2dieci
+ 0dieci×24dieci+ 1dieci×23dieci+ 1dieci×22dieci+ 0dieci×21dieci+
+ 0dieci×20dieci =
= 1dieci×32dieci + 0dieci×16dieci + 1dieci×8dieci + 1dieci×4dieci+ 0dieci×2dieci
+ 0dieci×1dieci =
= 32dieci + 8dieci + 4dieci =
= 44dieci
101110101due = 1dieci×28dieci+ 0dieci×27dieci+ 1dieci×26dieci+ 1dieci×25dieci+ 1dieci×24dieci+
0dieci×23dieci+ 1dieci×22dieci+ 0dieci×21dieci+ 1dieci×20dieci =
= 1dieci×256dieci+ 0dieci×128dieci+ 1dieci×64dieci+ 1dieci×32dieci+
1dieci×16dieci+ 0dieci×8dieci+ 1dieci×4dieci+ 0dieci×2dieci+ 1dieci×1dieci =
= 256dieci+ 64dieci+ 32dieci+ 16dieci+ 4dieci+ 1dieci =
= 373dieci