Presentazione 1.2
Basi
Architettura dell'informazione | Prof. Luca A. Ludovico
Definizione di base
• E' possibile scegliere il numero di cifre (o simboli)
differenti utilizzabili in una notazione posizionale.
Tale numero prende il nome di base.
•
Nel sistema decimale si usano le cifre {0,1,2,3,4,5,6,7,8,9}
Il valore posizionale è legato alle potenze di 10.
•
Nel sistema binario si usano le cifre {0,1}
Il valore posizionale è legato alle potenze di 2.
La base 2 è la più piccola possibile per un sistema di numerazione.
•
Nel sistema esadecimale si usano le cifre
{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
Il valore posizionale è legato alle potenze di 16.
Architettura dell'informazione
Prof. Luca A. Ludovico
Confronto tra base 2, 10 e 16
Base 2
Base 10
Base 16
0000
00
0
0001
01
1
0010
02
2
0011
03
3
0100
04
4
0101
05
5
0110
06
6
0111
07
7
1000
08
8
1001
09
9
1010
10
A
1011
11
B
1100
12
C
1101
13
D
1110
14
E
1111
15
F
…
…
…
Architettura dell'informazione
Prof. Luca A. Ludovico
Esercizio: conversione da base m a base n
• Convertire da base 16 a base 2
– 4021
– 003
0100 0000 0010 0001
0000 0000 0011
– A
– 9ED7
1010
1001 1110 1101 0111
= 11 (gli zeri in posiz. più
significativa non contano)
• Convertire da base 2 a base 16
–
–
–
–
0110
11100101
11010
00002010
Architettura dell'informazione
Prof. Luca A. Ludovico
attenzione alla partizione: è 0001 1010
il simbolo 2 non esiste!
Esercizio
• Si scrivano «intuitivamente» i primi 15 numeri interi non negativi,
cioè da 0 a 14, utilizzando la notazione posizionale e la base 3.
• Approccio: comincio a scrivere i numeri costituiti da cifre
differenti, provando con una cifra. Se le combinazioni non
bastano, aggiungo una seconda cifra, ecc.
• Risultato:
0 1 2 >> 3 combinazioni: non sufficiente!
00 01 02 10 11 12 20 21 22 >> 9 combinazioni: non sufficiente!
000 001 002 010 011 012 020 021 022 100 101 102 110 111 112 …
• Verifica: 1123 = 1410?
Sì: 2 · 30 + 1 · 31 + 1 · 32 = 2 + 3 + 9 = 1410
Architettura dell'informazione
Prof. Luca A. Ludovico
Alcune osservazioni sulle basi
• La rappresentazione dei numeri in una data base
piuttosto che in un’altra ne cambia la scrittura (ad
es. 1510 = 11112 = F16), ma non il significato
semantico. Pertanto anche le operazioni matematiche
danno lo stesso risultato e godono delle stesse
proprietà in ogni base.
• Si osservi che in una generica base n, i simboli
utilizzati ricadono convenzionalmente nell’intervallo
[0..n–1].
– Ad esempio, i simboli usati come cifre in base 10 sono [0..9]
– Ne consegue che ad es. il numero 1041 non possa esistere in
alcuna base n≤4.
Architettura dell'informazione
Prof. Luca A. Ludovico
Alcune osservazioni sulle basi
• Data una base n e un numero composto da m cifre,
quante differenti combinazioni si possono ottenere?
nm
• Questo perché ogni cifra rappresenta una casella che
è possibile valorizzare con un simbolo scelto tra gli n
simboli della base n. Con 2 caselle, si hanno n · n
combinazioni di simboli, e via dicendo…
– Esempio: con 2 cifre in base 10, si ottengono 102 diverse
combinazioni: [00..99]
– Esempio: con 4 cifre in base 2, si ottengono 24 diverse
combinazioni: [0000..1111]
Architettura dell'informazione
Prof. Luca A. Ludovico
Problema del distributore automatico
• Si consideri un distributore
automatico, il cui display
contiene una lettera e due
cifre.
• Esempi:
• Sulla base di questa scelta,
qual è il numero massimo di
scomparti diversi da cui un
cliente può attingere prodotti?
Architettura dell'informazione
Prof. Luca A. Ludovico
Numeri che richiedono più cifre
• Esempio in base 16
– 0 1 2 3 4 5 6 7 8 9 A B C D E F sono sufficienti per i numeri
0..15; ma poi?
– 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F è la
rappresentazione su due cifre dei numeri sopra
– La cifra più significativa ora diventa il secondo simbolo
dell’alfabeto: 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
– Esaurita la sequenza, la cifra più significativa diventa il terzo
simbolo dell’alfabeto: 20 21 ...
– Quando si esauriscono i simboli dell’alfabeto, si aggiunge
un’ulteriore cifra nella posizione più significativa (cioè a
sinistra).
Architettura dell'informazione
Prof. Luca A. Ludovico
Conversione da base n a base 10
• Per una numerazione in base n, con n numero naturale > 1, la
base supporta n cifre distinte.
Sia A un numero rappresentato come una sequenza di k+1 cifre
ak…a0.
Esso si può esprimere in base 10 secondo la formula
k
j
[
a
]

b
 j
j 0
ove b è la rappresentazione in base 10 di n.
• Ad esempio, se n = 2 il numero
a = 1012 = 1 · 22 + 0 · 21 + 1 · 20 = 4 + 1 = 510
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Conversione da base 10 a base n (num. interi)
• Metodo delle divisioni successive: consiste nel
prendere il numero da convertire e dividerlo per la
base considerata; prenderne il quoziente e dividerlo
ancora per la base, e così via, fino a che non si
ottiene come risultato un quoziente zero.
• In questa sequenza di divisioni occorre ricordare i
resti che man mano si ottengono, perché sono questi
che, letti in senso inverso dall'ultimo al primo,
costituiscono proprio la conversione cercata.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Algoritmo
Sia a il numero da convertire.
1. Si divide a per la nuova base n; sia q il quoziente ed r
il resto.
2. Si converte r nella corrispondente cifra della nuova
base n.
3. Si aggiunge la cifra così ottenuta a sinistra delle cifre
ottenute in precedenza.
4. Se q = 0, fine; altrimenti poni a = q e torna al
passo 1.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Esempio: da base 10 a base 2
a = 3510 2
17 1
8 1
4 0
2 0
1 0
0 1
a = 3510 = 1000112
a = 3210 2
16 0
8 0
4 0
2 0
1 0
0 1
a = 3210 = 1000002
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Esempio: da base 10 a base 5 e viceversa
a = 3210 5
6 2
1 1
0 1
a = 3210 = 1125
a = 1125 = 1 · 52 + 1 · 51 + 2 · 50 = 25 + 5 + 2 = 3210
Osservazione: questo tipo di verifica può sempre
essere fatto per controllare la correttezza del
risultato
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Come fare esercizio di conversione tra basi
• Tramite i metodi illustrati, è possibile convertire i
numeri da base 10 a una qualsiasi base n (metodo
delle divisioni successive) e da una qualsiasi base n a
base 10 (somma di prodotti).
• Ad esempio, la Calcolatrice di Windows in modalità
scientifica (Visualizza > Scientifica) presenta una
scelta di rappresentazione dei numeri che contempla
le basi Bin (2), Oct (8), Dec (10) e Hex (16).
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Conversione tra basi generiche
• E’ sempre possibile convertire un numero da una base
m a una base n con m ed n generici.
• Un metodo consiste nell’utilizzare la base 10 come
passaggio intermedio.
– Il numero x viene prima convertito da base m a base 10, per
poi essere nuovamente convertito da base 10 a base n.
• In alcuni casi si può procedere a una conversione
diretta.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Conversione diretta tra basi
• Se le basi di origine m e di destinazione n sono l’una potenza
dell’altra, è applicabile un metodo di conversione diretta.
Questa può essere svolta per sostituzione di gruppi di cifre
invece che con algoritmi di divisione.
• Se n = mk, allora k cifre del numero nella base originaria m
vengono sostituite con singole cifre nella nuova base n.
– E’ il caso di m = 2 ed n = 16, ad esempio.
• Viceversa, se m = nk, allora ogni singola cifra del numero nella
base originaria m viene espansa in k cifre nella nuova base n.
– E’ il caso di m = 9 ed n = 3, ad esempio.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 4.1
Presentazione 1.2
Operazioni aritmetiche in base 2
Architettura dell'informazione | Prof. Luca A. Ludovico
Operazioni aritmetiche basilari
• Le regole da imparare nel caso di una base b sono
relative alle b2 possibili combinazioni delle cifre da 0
ab–1
• Ad esempio, considerando la somma in base 10, si
tratta di 100 regole:
0+0=?
9+7=?
0+1=?
...
9+8=?
0+2=?
9+9=?
• Tali regole si riducono a 4 soltanto nella base 2
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Un vantaggio della base 2
• Semplificazione portata dalla base 2: a parità di
significato (valore) un numero scritto in base 2 è
molto più lungo dell'equivalente scritto in base 10,
ma le regole per poi eseguire le operazioni sono di
gran lunga più semplici.
• Nel caso dell'elaboratore questo è essenziale; infatti,
la velocità permette di non preoccuparsi
eccessivamente della lunghezza dei numeri, mentre
le regole relative alle operazioni su coppie di cifre
sono legate alla circuiteria elettronica che le deve
eseguire.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Addizione binaria
• L’algoritmo dell’operazione di addizione o somma non
cambia qualunque sia la base considerata.
• Le proprietà della somma (associativa, commutativa,
distributiva, …) si mantengono.
• Le 4 regole di somma in base 2:
0+0=0
0+1=1
1+0=1
1 + 1 = 0 con riporto 1
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Esempi di addizione binaria
• Esempio:
o
o
o
o
a = 112 = 310
b = 10002 = 810
a + b = 112 + 10002 = 10112
Verifica in base 10: con divisioni successive 10112 = 1110
• Esempio:
o
o
o
o
a = 110112 = 2710
b = 001102 = 610
a + b = 110112 + 001102 = 1000012
Verifica in base 10: con divisioni successive 1000012 = 3310
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Overflow
• In ogni calcolatore viene utilizzato un numero fissato di bit per
rappresentare i numeri sia interi che reali.
• E' possibile, effettuando operazioni con numeri rappresentati da
n bit, ottenere un numero non rappresentabile con n bit.
• Se il numero è troppo grande si parla di overflow (o trabocco).
La condizione di overflow si ha quando il risultato di un calcolo
intero è un numero che in binario occupa più bit di quelli a
disposizione, di conseguenza ne viene troncata la parte più
significativa generando un risultato errato.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Esempio di overflow
• 7110 e 6010 sono due interi in base 10 entrambi
rappresentabili su 7 bit in forma binaria.
–
trascuriamo al momento il bit di segno
• La somma (71 + 60)10 = 13110 però non è
rappresentabile con lo stesso numero di bit.
Infatti troncando il risultato a 7 bit, si ottiene
[1]00000112 = 310
• La stessa operazione, eseguita su 8 bit, non avrebbe
provocato overflow.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Sottrazione binaria
• L’algoritmo dell’operazione di sottrazione o
differenza non cambia qualunque sia la base
considerata.
• Le proprietà della sottrazione in base 10 si
mantengono.
• Le 4 regole di sottrazione in base 2:
0-0=0
1-1=0
1-0=1
0 - 1 = 1 con prestito di 1
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Esempio di sottrazione binaria
• Ipotesi: risultato della sottrazione non negativo
–
Ancora non sappiamo rappresentare valori negativi
• Esempio:
o
o
o
o
a = 11012=1310
b = 1012=510
a - b = 11012 – 1012 = 10002
Verifica in base 10: con divisioni successive 10002 = 810
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Moltiplicazione binaria
• L’algoritmo dell’operazione di moltiplicazione o
prodotto non cambia qualunque sia la base
considerata.
• Le 4 regole di moltiplicazione in base 2:
0·0=
1·0=
0·1=
1·1=
0
0
0
1
• In altri termini: il prodotto per zero dà sempre come
risultato zero; il prodotto per 1 dà sempre come
risultato il numero stesso.
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
Esempio di moltiplicazione binaria
•
•
•
a = 10112 = 1110
b = 11012 = 1310
a x b = 10112 · 11012 = 100011112 = 14310
1011 ·
1101 =
1011 +
00000 +
101100 +
1011000 =
10001111
Informatica Generale (Prof. Luca A. Ludovico)
Presentazione 5.1
In questo caso, non si
verifica mai l’operazione in
colonna:
1+1+1+1=?
Si può ovviare all’eventuale
problema scomponendo la
somma (a + b + c + d) in più
operazioni di somma a due
addendi ((a + b) + c) + d
Esercitazione sulla codifica binaria
• Si escogiti un sistema per scambiare informazioni
binarie tra un mittente e un destinatario posti agli
estremi di quest’aula, sfruttando solo il materiale
attualmente a disposizione.
• Il sistema verrà testato tramite l’invio di un messaggio
di prova.
Architettura dell'informazione
Prof. Luca A. Ludovico