Codifica dell’Informazione
1
Programmazione - Michele Colajanni, 2003/2004
Esempi di segnali binari
levetta:
alta/bassa
tensione elettrica:
High/Low
contatto:
aperto/chiuso
cristallo liquido:
trasparente/opaco
Programmazione - Michele Colajanni, 2003/2004
lampadina:
accesa/spenta
corrente elettrica:
presente/assente
2
1
Variabili binarie
BIT (BInary digiT) - Variabile x tale che:
x ∈ B{0,1}
Un bit può rappresentare un segnale binario.
Bisogna però decidere quale valore “fisico” è rappresentato dal
simbolo “matematico” 1. Esistono infatti due diverse possibilità
usualmente denominate logica positiva e negativa
I Interruttore I
0
alto
1
1
basso
0
C
0
1
Contatto
aperto
chiuso
C
1
0
L
0
1
Lampada
accesa
spenta
L
1
0
logica negativa logica positiva
Programmazione - Michele Colajanni, 2003/2004
3
Configurazioni binarie
Configurazione binaria di n bit - E’
n bit
una stringa di n caratteri 0 e 1.
Con una configurazione di n bit si
Bn-1
B2 b1 b0
possono codificare 2n informazioni
• n bit hanno 2n configurazioni binarie diverse.
• Una configurazione di n bit può rappresentare
i valori di n segnali binari ad un certo istante.
Es: n=3
•
Una configurazione di n bit può rappresentare
cba
i valori di un segnale binario in n istanti.
000
100
010
c
0
001
x
110
1
0 0
b
0
101
ta tb tc
011
a
0
111
4
Programmazione - Michele Colajanni, 2003/2004
2
Codice binario
Codice binario - Funzione dall’insieme delle 2n configurazioni
di n bit ad un insieme di M informazioni (simboli alfanumerici,
colori, eventi, stati interni, ecc.).
Condizione necessaria per la codifica: 2n ≥ M
2n
config.
0 0 0 ……..0
1 0 0 ……..0
0 1 0 ……..0
1 1 0 ……..0
0 0 1 ……..0
0 0 1 ……..1
z
non utilizzato
1
5
a
M
informazioni
?
m
0 1 1 ……..1
1 1 1 ……..1
Programmazione - Michele Colajanni, 2003/2004
5
Proprietà di un codice
Il codice è una rappresentazione convenzionale dell’informazione
La scelta di un codice è condivisa da sorgente e destinazione
ed ha due gradi di libertà:
• il numero di bit (qualsiasi, a patto che sia 2n ≥ M )
• l’associazione tra configurazioni e informazioni;
a parità di n e di M le associazioni possibili sono:
2n ! / (2n -M)!
Codice standard - Codice fissato da norme internazionali (de iure)
o dal primo costruttore che risulta utile per tutti gli altri (de facto).
• L’uso di codici standard nelle unità di I/O consente di collegare
macchine realizzate da costruttori diversi
Programmazione - Michele Colajanni, 2003/2004
6
3
0
1
più
meno
segno
Esempi
1
0
Cifre decimali
Altri
29
miliardi
di
codici
a
4 bit
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
BCD
zero
uno
due
tre
quattro
cinque
sei
sette
otto
nove
Programmazione - Michele Colajanni, 2003/2004
1111110
0110000
1101101
1111001
0110011
1011011
0011111
1110000
1111111
1110011
7 segmenti
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
0000000001
uno su dieci
(1= acceso)
7
Codice BCD (Binary Coded Decimal)
Ad ogni cifra decimale sono associati 4 bit, secondo la
tabella seguente:
Cifra Decimale
0
1
2
3
4
5
6
7
8
9
Cifra BCD
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Dalla tabella è possibile osservare che esistono delle
configurazioni non usate dal codice BCD: [1010...1111] (in
quanto necessita di 10 delle 16 configurazioni possibili).
Programmazione - Michele Colajanni, 2003/2004
8
4
Codice BCD (cont.)
Utilizzando il codice BCD si ha una corrispondenza
biunivoca fra il numero di cifre decimali e binarie
Questo codice consente di avere dei circuiti
visualizzazione dei numeri decimali più semplici
di
Esempio
Codifica del numero decimale 27 con il codice BCD:
27
0010 0111
9
Programmazione - Michele Colajanni, 2003/2004
Codice 1 su N
E’ un codice che associa ad ognuna delle n possibili
configurazioni una stringa di n bit avente un solo bit ad 1
Esempi
Calcolatori tascabili: utilizzato per immettere dati attraverso la tastiera
numerica
Negli ascensori: è utilizzato per visualizzare la posizione dei piani
raggiunti e per selezionare il piano da raggiungere:
Pulsanti ascensore
Codifica 1 su N
3
1000
2
0100
1
0010
T
0001
Programmazione - Michele Colajanni, 2003/2004
10
5
Codice a sette segmenti
Codice utilizzato nei display per consentire la
rappresentazone grafica di cifre decimali.
Impiega 7 bit (a,b,c,d,e,f,g) per codificare i 10 simboli
decimali
a
a
f
1
g
b
c
e
f
abcdefg
0110000
g
b
c
e
d
a
d
9
f
abcdefg
1111011
g
b
c
e
d
Programmazione - Michele Colajanni, 2003/2004
11
Codice a matrice di punti
Impiega MxN bit per consentire la rappresentazione di
simboli grafici su una matrice di punti di M righe e N
colonne .
Utilizzato per la visualizzazione dei caratteri nei monitor, nei
display dei telefonini, nei display delle calcolatrici,...
0000000
N
0000000
0011000
0100100
0100100
M
0111100
………..
0000000
Programmazione - Michele Colajanni, 2003/2004
12
6
Classi di informazione da codificare
all’interno del calcolatore
• Informazione alfanumerica
– Codice ASCII (necessario 1 byte)
• Indirizzi di memoria
– Rappresentazione posizionale
• Sono numeri interi positivi (necessari più byte)
• Numeri
– Rappresentazione decimale codificata
– Rappresentazione posizionale
• Numeri interi positivi e negativi
• Numeri frazionari
13
Programmazione - Michele Colajanni, 2003/2004
Codice ASCII
Il codice ASCII è non ridondante, perché i simboli codificati sono in
numero pari alle configurazioni ottenibili con 7 cifre binarie.
Ampiamente utilizzato in computer, stampanti, trasmissione dati,…
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
000
NUL
SOH
STX
ETX
EOT
ENQ
ACK
BEL
BS
HT
LF
VT
FF
CR
SO
SI
001
DLE
DC1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US
010
!
“
#
$
%
&
‘
(
)
*
+
,
.
/
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
{
|
}
~
DEL
Sono numeri interi positivi (necessario un byte)
Programmazione - Michele Colajanni, 2003/2004
14
7
Indirizzi
•
•
•
•
Necessari per memorizzare informazioni complesse
Indicano (puntano a) una locazione di memoria
Sono numeri interi positivi (su più byte)
Esiste un legame tra la dimensione della word e la
dimensione massima della memoria (il numero di bit di un
indirizzo binario denota l’indirizzo massimo
rappresentabile)
CPU
8080
8086
80286
80486
Pentium
Bit per indirizzo
16 bit
20 bit
24 bit
46 bit
46 bit
Memoria massima
64 Kbyte (KB)
1 Megabyte (MB)
16 Megabyte
64 Terabyte (TB)
64 Terabyte
15
Programmazione - Michele Colajanni, 2003/2004
Unità di misura
• Unità di misura standard
Byte (insieme di 8 bit) e suoi multipli
• Multipli
1 KiloByte=
x1024
=
x1024
=
x1024
=
x1024
=
1.024 byte
1 MegaByte
1 GigaByte
1 TeraByte
1 PetaByte
• Abbreviazioni
Kb = Kilobit
Mb = Megabit
Gb = Gigabit
Programmazione - Michele Colajanni, 2003/2004
=
=
=
=
1.048.576 byte
1.073.741.824 byte
1.099.511.627.776 byte
….. byte
KB = KiloByte
MB = MegaByte
GB = GigaByte
16
8
Rappresentazione
dei numeri
17
Programmazione - Michele Colajanni, 2003/2004
Sommario
• Introduzione
• Rappresentazione dei numeri interi positivi
• Rappresentazione dei numeri interi
• Operazioni aritmetiche
• Rappresentazione dei numeri frazionari
– Numeri in virgola fissa
Nel Corso di
“Architetture
dei
Calcolatori”
– Numeri in virgola mobile
Programmazione - Michele Colajanni, 2003/2004
18
9
Sommario
• Introduzione
– Numeri
– Numerali
– Basi
• Rappresentazione dei numeri interi
positivi
• Rappresentazione dei numeri interi
• Operazioni aritmetiche
Programmazione - Michele Colajanni, 2003/2004
19
Numeri e numerali
Numero: entità astratta
Numerale: stringa di caratteri che rappresenta un
numero in un dato sistema di numerazione
Lo stesso numero è rappresentato da numerali diversi
in sistemi diversi. Es.,
– 156
– CLVI
nel sistema decimale
in numeri romani
Il numero di caratteri nel numerale determina l’intervallo
di numeri rappresentabili. Es.,
– interi a 3 cifre con segno in notazione decimale: [-999,+999]
Programmazione - Michele Colajanni, 2003/2004
20
10
Numerali: regole fondamentali
• Un numerale è solo una stringa di cifre
• Un numerale rappresenta un numero solo se si
specifica un sistema di numerazione
• Lo stesso numerale rappresenta diversi numeri in
diverse notazioni
Esempio
La stringa 110100 rappresenta:
–
–
–
–
–
–
Centodiecimilacento in base 10
(+52)10 in binario naturale
(-11)10 in complemento a 1
(-12)10 in complemento a 2
(+20)10 in eccesso 16
Un numero dell’ordine di vari milioni in esadecimale
21
Programmazione - Michele Colajanni, 2003/2004
Numeri a precisione finita
Nel momento in cui si utilizzano numerali con un numero finito
di cifre:
• Si perdono alcune proprietà dei numeri, quali:
– chiusura operatori ( + , −, × )
– proprietà associativa, distributiva, …
Esempio: numerali decimali con due sole cifre frazionarie
• ovvero 2 cifre decimali e segno [-99,+99]
• 78+36=114 (no Chiusura)
• 60+(50-40) ≠ (60+50)-40 (no Associatività)
• Vi sono errori di arrotondamento
• Vi sono buchi nella rappresentazione dei reali
Esempio
– usando numerali decimali con due sole cifre frazionarie:
?
0
0.01
Programmazione - Michele Colajanni, 2003/2004
0.02
22
11
Sistemi di numerazione
Posizionali
Il valore di un simbolo dipende dalla posizione che esso
occupa all’interno della configurazione, seguendo una
legge nota. I vari sistemi di numerazione posizionale
differiscono per la scelta della base B. La base B indica
il numero di simboli usati (0, …, B-1)
Es: decimale, binario , ottale, esadecimale
Non posizionali
Il valore di un simbolo non dipende dalla posizione che
esso occupa all’interno della configurazione.
Es: Numeri romani
23
Programmazione - Michele Colajanni, 2003/2004
Interpretazione dei simboli in un
sistema posizionale
Nei sistemi posizionali, i simboli di una configurazione
possono essere interpretati come i coefficienti del
seguente polinomio:
n−1
n −1
V=∑ d i ⋅ Bi
V= ∑ di ⋅ Bi
i =0
Numero intero
i= − m
Numero frazionario
B = base
di = i-esima cifra ∈ [0,…,B-1]
n = numero di cifre della parte intera
m = numero di cifre della parte frazionaria
(La virgola è posta tra le cifre di posizione 0 e –1)
Programmazione - Michele Colajanni, 2003/2004
24
12
Esempio 1: Sistema decimale
Il numero 135.2 decimale può essere rappresentato come
segue :
B = 10
n=3
m=1
base
numero cifre parte intera
numero cifre parte frazionaria
cifra
1
3
5
2
posizione
2
1
0
-1
10 2
10 1
10 0
10 -1
peso
1 • 10 2 + 3 • 101 + 5 •100 + 2 •10-1 = 135.2
Programmazione - Michele Colajanni, 2003/2004
25
Sommario
• Numeri, numerali e basi
• Rappresentazione dei numeri interi positivi
–
–
–
–
Base binaria
Conversioni
Altre basi potenze di 2
Problemi nelle conversioni di base
• Rappresentazione dei numeri interi
• Operazioni aritmetiche
• Rappresentazione dei numeri frazionari
– Numeri in virgola fissa
– Numeri in virgola mobile
Programmazione - Michele Colajanni, 2003/2004
26
13
Rappresentazione dei numeri binari
• La rappresentazione dei numeri usata nei calcolatori è
quella binaria.
• Le cifre binarie prendono il nome di bit (Binary digIT).
• Un numero binario intero è costituito da un vettore di bit.
B = bn-1…b1b0
• Il valore di B è dato da:
bi = {0, 1}
V(B) = bn-1×2n-1 + … + b 1×21 + b0×20
• Un vettore di n bit consente di rappresentare i numeri
naturali nell’intervallo da 0 a 2 n-1.
• Per rappresentare i numeri positivi e negativi si
usano diversi sistemi
27
Programmazione - Michele Colajanni, 2003/2004
Esempio 2: Sistema binario
Valore decimale corrispondente al numero binario 11012 ?
cifra2
1
1
0
1
peso
23
22
21
20
valore
1•8
1•4
0•2
1•1
11012 = 1 • 23 + 1 • 22 + 0 • 21 + 1 • 20 = 1310
Programmazione - Michele Colajanni, 2003/2004
28
14
Da base Decimale a Binaria: Numeri interi
Per ottenere il valore binario di un numero intero codificato nel sistema
decimale si procede utilizzando un metodo iterativo di successive
divisioni per 2.
Il resto delle divisioni fornisce le cifre del numerale binario (a partire dalla
meno significativa)
2610
26
Cifra a destra
(meno significativa) 0
2
13
1
2
6 2
0
26)10 = 11010)2
3 2
1
1
Cifra a sinistra
(più significativa)
29
Programmazione - Michele Colajanni, 2003/2004
Da base Decimale a Binaria: Numeri frazionari
Si separa la parte intera da quella frazionaria, La parte intera si calcola
come nel caso precedente La parte frazionaria si ottiene come segue:
1. Si moltiplica la parte frazionaria per 2
2. Se il numero ottenuto è maggiore di 1, si sottrae 1 e si considera come
prima cifra dopo la virgola un ‘1’.
3. Se invece il numero è nella forma 0,….. ---> la cifra da inserire è uno ‘0’.
4. Si ripete dal passo 1 fino a che il numero di partenza non è zero.
Esempio:
0.625 10 =0.101 2
0.625 * 2 = 1.25 1
=
0.25 * 2 = 0.5 0 =
0.5 * 2 = 1 1=
0
0, 1 0 1
Programmazione - Michele Colajanni, 2003/2004
30
15
Sistemi di numerazione Ottale ed
Esadecimale
Quando per la rappresentazione di un numero si utilizzano molte
cifre binarie può convenire usare altri sistemi di numerazione.
I sistemi ottale ed esadecimale sono utilizzati principalmente per
rappresentare in modo più compatto i numeri binari.
I simboli del sistema Ottale sono 8:
{ 0, 1, 2, 3, 4, 5, 6, 7}
I simboli del sistema Esadecimale sono 16:
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }
Si scelgono basi “potenza di 2” perché le regole di
conversione da/a numero binario sono molto semplici ed
efficienti
Programmazione - Michele Colajanni, 2003/2004
31
Conversioni di base
Binario -> Ottale
Per passare dalla codifica Binaria a quella Ottale, si raggruppano le cifre
binarie a gruppi di 3 (a partire da destra) e le si sostituiscono con una
cifra del sistema ottale.
Esempio : 111 001 0102 = 7128
Ottale -> Binario
Per passare dalla codifica Ottale a quella Binaria, si sostituisce ad ogni
cifra ottale la corrispondente codifica binaria (composta da 3 cifre).
Esempio : 3028 = 011 000 0102
Programmazione - Michele Colajanni, 2003/2004
32
16
Conversioni di base (cont.)
Binario -> Esadecimale
Per passare dal codice Binario a quello Esadecimale, si raggruppano le
cifre a gruppi di 4 (a partire da destra) e le si sostituiscono con una cifra
del sistema esadecimale.
Esempio : 1001 0001 11112 = 91F16
Esadecimale -> Binario
Per passare dal codice Esadecimale a quello Binario, si sostituisce ad
ogni cifra esadecimale la corrispondente configurazione binaria
(composta da 4 cifre).
Esempio : A7F16 =1010 0111 11112
33
Programmazione - Michele Colajanni, 2003/2004
Esempio 1
Codifica del numero 12510 = 11111012
In codice Ottale:
1 111 101
In codice Esadecimale:
1101
111
7D
175
Esempio 2
Decimale
5
12
78
149
Binario
101
1100
1001110
10010101
Programmazione - Michele Colajanni, 2003/2004
Ottale
5
14
116
225
Esadecimale
5
C
4E
95
34
17
Codifica dei primi 16 numeri in quattro
sistemi di numerazione
Decimale
Binario
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
dcba
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Ottale
Esadecimale
00
01
02
03
04
05
06
07
10
11
12
13
14
15
16
17
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
35
Programmazione - Michele Colajanni, 2003/2004
Problemi nelle conversioni di base
• Non sempre si può rappresentare un numero in
due basi diverse con un numero finito di cifre.
Esempio: Il numero 0.357 in base 10 non si può rappresentare
finitamente in base 2:
0,357 * 2 = 0,714 (<1) e
0,714 * 2 = 1,428 (>1) e
0,428 * 2 = 0,856 (<1) e
0,856 * 2 = 1,712 (>1) e
0,712 * 2 = 1,424 (>1) e
0,424 * 2 = 0,848 (<1) e
0,848 * 2 = 1,796 (>1) e
0,796 * 2 = 1,592 (>1) e
0,592 * 2 = 1,184 (>1) e
0,184 * 2 = 0,368 (<1) e
….
quindi 0
quindi 1
quindi 0
quindi 1
quindi 1
quindi 0
quindi 1
quindi 1
quindi 1
quindi 0
0.35710 finito ---> 0.0101101110…2
Programmazione - Michele Colajanni, 2003/2004
36
18
Problemi nelle conversioni (cont.)
Esempio 2: Il numero 0.15 in base 10 risulta un
numero periodico in base 2:
0.15 * 2 = 0.30
(<1) e quindi 0
0.30 * 2 = 0.60
(<1) e quindi 0
0.60 * 2 = 1.20
(>1) e quindi 1
0.20 * 2 = 0.40
0.40 * 2 = 0.80
(<1) e quindi 0
(<1) e quindi 0
0.80 * 2 = 1.60
(>1) e quindi 1
0.60 * 2 = 1,20
(>1) e quindi 1
….
0.1510 finito ---> 0.00(1001)2
Programmazione - Michele Colajanni, 2003/2004
37
Problemi nelle conversioni (cont.)
Esercizio 3 (per chi ha coraggio): Il numero 0.14 in
base 10 risulta un numero periodico in base 2.
Determinare la sua rappresentazione binaria.
Programmazione - Michele Colajanni, 2003/2004
38
19
Sommario
• Numeri, numerali e basi
• Rappresentazione dei numeri interi
positivi
• Rappresentazione dei numeri interi
– Modulo e segno
– Complemento a 1
– Complemento a 2
– Eccesso
• Operazioni aritmetiche
Programmazione - Michele Colajanni, 2003/2004
39
Regola per numeri negativi
• Nella rappresentazione binaria di numeri dotati
di segno viene tipicamente usato un bit per
discriminare tra valori positivi e valori
negativi.
• Quindi, per rappresentare gli interi relativi, a
parità di cifre si dimezza l’intervallo dei valori
assoluti rappresentabili
• Def. (MSB): Most significant bit. Dati n bit per la
rappresentazione, MSB è il bit in posizione n-1
(ricordarsi che si conta da 0)
Programmazione - Michele Colajanni, 2003/2004
40
20
Rappresentazione dei numeri interi
• Modulo e segno
– Un numero negativo si ottiene fissando ad 1 il bit più significativo.
– E’ molto simile alla rappresentazione dei numeri decimali.
• Complemento a 1
– Un numero negativo si ottiene invertendo bit a bit il corrispondente
numero positivo.
– E’ semplice ottenere la rappresentazione di un numero negativo.
• Complemento a 2
– Un numero negativo si ottiene invertendo bit a bit il corrispondente
numero positivo, quindi sommando il valore 1.
– Ha un’unica rappresentazione per il valore 0.
– Consente di realizzare circuiti più semplici.
• Eccesso 2 n-1
– I numeri vengono rappresentati come somma fra il numero dato e
una potenza di 2, in modo che risultino positivi.
41
Programmazione - Michele Colajanni, 2003/2004
Modulo e Segno
• In questo rappresentazione al valore assoluto
del numero viene prefisso un bit per indicarne
il segno.
• Il valore 0 di questo bit codifica il segno più e
il valore 1 il segno meno.
Esempio con n=8 cifre:
+5710 = 001110012
segno
-5710 = 101110012
modulo
Programmazione - Michele Colajanni, 2003/2004
42
21
Modulo e Segno (cont.)
• Usando n bit (es. 8) per la codifica, il range di valori
rappresentabili risulta essere : [-2n-1+1, …, +2n-1 -1].
• Con 8 bit [-127, …, +127], perché un bit è usato per il
segno.
• Vi sono due configurazioni per lo zero (non bello!)
00000000
10000000
• Poichè le operazioni vanno eseguite sulla sola parte
di valore assoluto (modulo) la determinazione
dell’overflow è semplice (si vedrà in seguito…)
Programmazione - Michele Colajanni, 2003/2004
43
Modulo e Segno (cont.)
• La rappresentazione è vantaggiosa per la sua semplicità
• L’intervallo dei numeri rappresentati (positivi e negativi) è
simmetrico
• Tuttavia, richiede circuiti complessi per l’esecuzione di
somme algebriche
• Prima di eseguire una somma algebrica tra due operandi
A e B è sempre necessario determinare quale dei due è
maggiore in valore assoluto. P.es., nelle sottrazioni:
– Se A è maggiore di B si esegue la differenza A-B e si assegna al
risultato il segno di A
– Se A è minore di B si esegue la differenza B-A e si assegna al
risultato il segno di B
Programmazione - Michele Colajanni, 2003/2004
44
22
Complemento a 1
• I numerali positivi iniziano per 0, i negativi per 1
• Per cambiare di segno si complementa il numerale
bit a bit (àComplementare = cambiare segno)
• Es., 3 à 0011
-3 à 1011
• Con n bit: [-2n-1+1,…, +2n-1-1]
Es. n=8 à [-127, …, +127],
• È una notazione semi-posizionale perché il MSB non
ha peso 2 n-1, ma ha peso (2n-1+1)
Pesi: (-2n-1+1) 2 n-2 ... 2 1 20
Anche in questo caso vi è una doppia rappresentazione dello 0
Programmazione - Michele Colajanni, 2003/2004
45
Complemento a 1 (cont.)
• Complemento a uno: negazione mediante il
complemento bit a bit del numero in valore assoluto a cui
si aggiunge uno zero.
• Rappresentazione poco utilizzata in pratica
Programmazione - Michele Colajanni, 2003/2004
46
23
Complemento a 1 (cont.)
Esempio
Dati n=4 bit, l’intervallo dei numeri rappresentabili è
[-2n-1+1, +2n-1-1] = [-7, +7].
I numeri positivi si rappresentano come al solito:
510 = 01012
I numeri negativi si rappresentano:
– prendendo il valore assoluto e rappresentandolo come al solito
– aggiungendo un bit 0 a sinistra
– complementando a 1 il numero ottenuto (ovvero sostituendo 0
con 1 e 1 con 0)
-510 à 1012 à 01012 à 10102
(equivalente a -7+2)
Programmazione - Michele Colajanni, 2003/2004
47
Rappresentazione in complemento a 2
Dati n bit per la codifica del numero con segno, la
rappresentazione in complemento a 2 di un numero si
ottiene sommando (sottraendo nel caso di numeri negativi)
a 2n il numero codificato in valore assoluto ed eliminando
l’eventuale bit di posizione n.
- Con tale rappresentazione possono essere codificati i valori compresi
nell’intervallo [-2n-1, 2n-1-1]
- I numeri positivi restano inalterati
-I numeri negativi negativi risultano ottenuti sommando qualche valore
positivo al massimo negativo
METODO OPERATIVO: i numeri negativi sono calcolabili partendo
dal corrispondente valore positivo, invertendo tutti i bit e sommando 1
Programmazione - Michele Colajanni, 2003/2004
48
24
Da complemento a 2 a decimale
Il complemento a 2 è una rappresentazione semi-posizionale
perché in una configurazione binaria di n bit, il bit più
significativo (MSB, in posizione n-1) assume un peso negativo
pari a -2n-1
n−2
n −1
i
d i ∈ [0,1]
V10 =− 2 ⋅ d n−1 + ∑ d i ⋅ 2
i =0
Di conseguenza, i numeri positivi (avendo dn-1=0) codificati in complemento a 2
rimangono inalterati, mentre i numeri negativi risultano ottenuti sommando
qualche valore positivo al massimo negativo (-2n-1)
• 10112 in complemento a 2 equivale a:
10112 = 1·(-23) + 0·22 + 1·21 +1·20 = -8 + 0 + 2 +1 = -510
• 01112 in complemento a 2 equivale a :
01112 = 0·(-23) + 1·22 + 1·21 +1·20 = 0 + 4 + 2 +1 = +710
Programmazione - Michele Colajanni, 2003/2004
49
Complemento a 2
• Complemento a due: negazione mediante
complemento a 1, e somma di 1.
• Notazione non completamente posizionale
Programmazione - Michele Colajanni, 2003/2004
50
25
Complemento a 2 (cont.)
Esempio (Metodo operativo)
Dati n=4 bit, l’intervallo dei numeri rappresentabili è
[-2n-1, +2n-1-1] = [-8, +7].
I numeri positivi si rappresentano come al solito:
510 = 01012
I numeri negativi si rappresentano:
– prendendo il valore assoluto e rappresentandolo come al solito
– aggiungendo tanti bit 0 a sinistra fino a raggiungere n bit
– complementando a 1 il numero ottenuto
– sommando 1
-510 à 1012 à 01012 à 10102 à 10112
Programmazione - Michele Colajanni, 2003/2004
51
Motivazione del metodo operativo
• Il numero –X in complemento a 2 ha la stessa sequenza di
bit del numero 2n-X rappresentato in binario puro:
-74 à 10110110 (complemento a 2)
256-74=182 à 10110110 (binario puro)
• Il metodo operativo rappresenta, invece di –X, proprio 2n-X
• Perché calcolare 2 n-X è più efficiente?
2n-X = (2n -1-X)+1
Questa è una sottrazione molto efficiente
da calcolare perché 2 n-1 è una sequenza
di tutti 1 e quindi (2n-1-X) si ottiene invertendo
tutti i bit della rappresentazione di X (ovvero
complementando a 1 la rappresentazione di X)
A questo punto, per ottenere la rappresentazione
cercata, basta aggiungere il +1 fuori parentesi
Programmazione - Michele Colajanni, 2003/2004
52
26
Proprietà del complemento a 2
• Vi è una sola rappresentazione per lo zero
• Il complemento di una somma algebrica è uguale alla
somma aritmetica dei complementi.
• Operativamente non vi è differenza nell’eseguire somme o
sottrazioni. Quindi, non è necessario individuare il
maggiore (in valore assoluto tra i due operandi) come nel
caso della rappresentazione Modulo-Segno.
• Applicando due volte la regola del complemento a 2 si
ottiene il numero originale:
-510 in complemento a 2 risulta 10112
Applicando nuovamente il complemento a 2 si ottiene il valore
positivo del numero e viceversa
-510 à 10112 à 01002 à 01012 = + 510
Programmazione - Michele Colajanni, 2003/2004
53
Rappresentazione in Eccesso k
• È possibile definire rappresentazioni in eccesso k, dove k
è un numero qualsiasi
• L’eccesso “potenza di 2” è solo un caso particolare, anche
se molto interessante
• Rappresentando un intero m in eccesso k con n bit, si
rappresenta in realtà il numero positivo k+m
• Deve comunque valere: k ≤ 2n
• L’intervallo dei numeri rappresentabili dipende sia da k che
da n:
[-k , 2 n-k-1]
Esempi
n=8, k=127
n=8, k=100
n=8, k=50
[-127,+128]
[-100,+155]
[-50,+205]
Programmazione - Michele Colajanni, 2003/2004
54
27
Rappresentazione in Eccesso 2n-1
• I numeri vengono rappresentati come somma fra il
numero dato e una potenza di 2.
• Con n bit si rappresenta l’eccesso 2 n-1
• Intervallo come complemento a 2: [-2n-1 , +2n-1-1]
• Metodo operativo:
I numerali si ottengono da quelli in complemento a
2 complementando il bit più significativo
Esempio
n=4 bit: eccesso 8, intervallo [-8,+7]
- 310
- 3+8 = 5 : 01012
+410
+4+8 = 12 : 11002
• Intervallo asimmetrico
• Rappresentazione unica dello 0
55
Programmazione - Michele Colajanni, 2003/2004
Rappresentazione in Eccesso 2n-1 (cont.)
• Dato un numero m determinare il numero minimo di cifre
nmin necessarie
• Determinare la prima potenza di 2 superiore al modulo di m
e confrontarla con gli estremi dell’intervallo
Esempio
Convertire (-347)10 in eccesso 2 n-1
• 28 = 256 < 347 < 512 = 2 9
• Intervallo con n bit: [-2n-1 ,+2n-1-1] e pertanto nmin=10
• 512 - 347 = 165
• 165 = 128+32+4+1
9
• (-347)10 in eccesso 2 è:
Programmazione - Michele Colajanni, 2003/2004
512
256
0
0
128
64
32
16
1 0 1
0
8
4
2
1
0 1 0 1
56
28
Confronto tra rappresentazioni
B
b2b1b0
000
001
010
011
100
101
110
111
Modulo e segno
+0
+1
+2
+3
-0
-1
-2
-3
V(B)
Complemento a 1
+0
+1
+2
+3
-3
-2
-1
-0
Complemento a 2
+0
+1
+2
+3
-4
-3
-2
-1
57
Programmazione - Michele Colajanni, 2003/2004
Confronto tra rappresentazioni (cont.)
Decimale
+7
+6
+5
+4
+3
+2
+1
+0
-0
-1
-2
-3
-4
-5
-6
-7
-8
M-S
CP1
CP2
Ecc 8
0111
0110
0101
0100
0011
0010
0001
0000
1000
1001
1010
1011
1100
1101
1110
1111
----
0111
0110
0101
0100
0011
0010
0001
0000
1111
1110
1101
1100
1011
1010
1001
1000
----
0111
0110
0101
0100
0011
0010
0001
0000
----1111
1110
1101
1100
1011
1010
1001
1000
1111
1110
1101
1100
1011
1010
1001
1000
----0111
0110
0101
0100
0011
0010
0001
0000
Programmazione - Michele Colajanni, 2003/2004
58
29