ARCHITETTURA DEI SISTEMI
ELETTRONICI
LEZIONE N° 3
•
•
•
•
•
Sistema numerico
Base 2, 3, 4, 5, 8, 10, 12, 16
Aritmetica binaria
Conversione da base “N” a base 10
Conversione da base 10 a base “N”
A.S.E.
3.1
Richiami
•
•
•
•
Segnali analogici
Segnali numerici
Segnali digitali
Conversione da segnale analogico a segnale
numerico
• Conversione da segnale numerico a segnale
analogico
• Codifica
A.S.E.
3.2
Riepilogo (1)
• Segnale Analogico
– Un segnale analogico ha un’ampiezza che varia in
maniera continua nel tempo
• Segnale campionato
– Viene “congelato” il valore che il segnale analogico
assume a intervalli regolari di tempo
• Segnale numerico 1
– Viene assegnato al segnale campionato il valore
numerico relativo all’intervallo di appartenenza
A.S.E.
3.3
Riepilogo (2)
• Segnale numerico 2
– Al segnale quantizzato si può associare il valore
numerico “codificato”
• Segnale digitale (binario)
– Particolare segnale numerico che può assumere
solo due valori “0” e “1”
• Al valore “0” si associa, per esempio, 0 V
• Al valore “1” si associa, per esempio, 5 V
A.S.E.
3.4
Codifica (1/4)
• Un valore numerico può essere codificato per
mezzo di un numero n di simboli (cifre) binari
– il numero di cifre binarie necessario per la codifica è
n = log2N, dove N è il numero di livelli da codificare;
• se vale n = log2N, allora N = 2n e tutte le possibili sequenze di
n cifre binarie sono utilizzate nella codifica;
• se invece n > log2N, allora la codifica utilizza un sottoinsieme
N < 2n delle possibili sequenze di n cifre binarie;
– è possibile utilizzare diverse leggi di codifica, e il
loro numero C è una funzione di N, n:
• se N = 2n , allora C è dato dal numero di permutazioni di N
oggetti:
C N  PN  N !  N  N  1  N  2...  2 1
A.S.E.
3.5
Codifica (2/4)
• se invece N < 2n , allora C può essere determinato
considerando che:
– bisogna individuare N simboli di codifica fra i 2n possibili
simboli rappresentabili con n cifre binarie; il loro numero è pari
alle combinazioni C(2n,N) di N oggetti estratti da un insieme di
2n elementi:

 

 2n 
2n !
2 n  2 n  1  ...  2 n  N  1
C (2 , N )    

n
N   N  1  ...  2 1
 N  N ! 2  N !

n

– per ciascuna combinazione, possono essere definite P(N) = N!
permutazioni diverse;
– complessivamente, il numero
di codifiche è quindi dato da:
n


C N  C 2 n , N  PN  

 

2 !
n
n
n

N
!

2

2

1

...

2
 N 1
n
N ! 2  N !


– nota: se N = 2n , sfruttando la proprietà 0!=1, l’espressione di CN
coincide proprio col risultato ottenuto in precedenza, CN = N!
A.S.E.
3.6
Codifica (3/4)
• Esempio: N = 7
• n = 3, CN = 8! = 40320
Valore
A
B
C
0
1
0
1
1
1
1
0
2
1
1
1
3
1
1
0
4
0
1
1
5
0
1
0
6
0
0
1
A
B
C
0
0
0
1
1
0
1
0
2
0
1
1
3
1
1
0
4
1
1
1
Valore
A
B
C
5
1
1
0
0
1
0
0
6
1
0
1
1
1
1
1
2
0
1
0
3
1
0
1
4
0
0
1
5
1
1
0
6
0
1
1
…..
Valore
A.S.E.
3.7
Codifica (4/4)
• Fra tutte le codifiche, due sono più significative:
• codifica naturale;
• codifica Gray;
• Esempio: N = 8 (n = 3, CN = 8! = 40320)
Valore
A
B
C
Valore
A
B
C
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
1
2
0
1
0
2
0
1
1
3
0
1
1
3
0
1
0
4
1
0
0
4
1
1
0
5
1
0
1
5
1
1
1
6
1
1
0
6
1
0
1
7
1
1
1
7
1
0
0
CODIFICA NATURALE
A.S.E.
CODIFICA GRAY
3.8
Notazione Posizionale
• Per rappresentare una quantità maggiore di quella
associata a ciascun simbolo (cifra, digit) si usano più
digit per formare un numero
• La posizione relativa di ciascun digit all’interno del
numero è associata ad un peso, dato dalla base di
rappresentazione b
• Notazione posizionale
N  d n1d n2      d1d 0 .d 1      d m
• Rappresenta il polinomio
N  d n 1  b n 1  d n  2  b n  2     d1  b1  d 0  b 0 .d 1  b 1     d  m  b  m
A.S.E.
3.9
Sistema Decimale
• Il sistema decimale è il sistema posizionale
comunemente utilizzato nella nostra vita quotidiana
• Ad esempio il numero decimale 872.64, significa:
872.64  8 100  7 10  2 1  6  0.1  4  0.01
 8 10 2  7 101  2 100  6 10 1  4 10 2
• Ciascuna cifra della rappresentazione è un simbolo
dell’alfabeto decimale (0, 1, 2, …, 9)
• La posizione di una cifra all’interno del numero,
relativa alla virgola decimale, indica il suo peso,
ossia l’esponente ad essa associata nel suo sviluppo
polinomiale
A.S.E.
3.10
Sistema numerico non posizionale
• I numeri romani non danno luogo a un sistema
numerico posizionale
• Come in un sistema posizionale, uno stesso simbolo in
posizioni diverse assume valori diversi
– a differenza di un sistema posizionale, il peso di una cifra non è
esprimibile come una potenza della base di rappresentazione
– non è definita una base di numerazione per i numeri romani
• lo sviluppo polinomiale non è possibile
– Esempio
• I; II; IV; VI; etc…
A.S.E.
3.11
Sistema Numerico
• Base (radice)
• Numero di simboli diversi di un sistema numerico
• Digit (Cifra)
• ciascun simbolo = DIGIT denota una quantità
Base
Sistema
Digit
2 binario
0, 1
3 ternario
0, 1, 2
4 quaternario
0, 1, 2, 3
5 quinario
0, 1, 2, 3, 4
8 ottale
0, 1, 2, 3, 4, 5, 6, 7
10 decimale
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
12 duodecimale
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B
16 esadecimale
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
A.S.E.
3.12
Rappresentazione completa
• Uno stesso numero rappresenta quantità diverse in
funzione della base utilizzata
– Si deve quindi indicare la base utilizzata. Ad esempio:
287  28710
• Altri esempi:
28710 , 3458 , 45AD16 , 234 , 10010112
28712  28710
• Nel caso rappresentazione binaria, una “binary digit”
si indica come bit (letteralmente “pezzetto”)
A.S.E.
3.13
Tabella
Decimale
Binario
Ternario
Ottale
Esadecimale
0
0
0
0
0
1
1
1
1
1
2
10
2
2
2
3
11
10
3
3
4
100
11
4
4
5
101
12
5
5
6
110
20
6
6
7
111
21
7
7
8
1000
22
10
8
9
1001
100
11
9
10
1010
101
12
A
11
1011
102
13
B
12
1100
110
14
C
13
1101
111
15
D
14
1110
112
16
E
15
1111
120
17
F
16
10000
121
20
10
A.S.E.
3.14
Operazioni aritmetiche di base
• Le quattro operazioni aritmetiche di base sono:
–
–
–
–
Addizione
Sottrazione
Moltiplicazione
Divisione
• Tali operazioni sono note in base decimale
• Si possono eseguire con le stesse modalità in
qualunque base diversa da 10
• Si considera ora il sistema binario e quello
ternario
– quello binario è di gran lunga il più importante
A.S.E.
3.15
Addizione
• Addizione di due digit
– Può essere espressa i modo tabellare
• Sistema binario
b
a+b
a
Sistema ternario
a
a+b
0
1
0
0
1
1
0
1 C=1
0
0
0
b 1
1
2
2
A.S.E.
1
2
1
2
0
2
C=1
0
1
C=1 C=1
3.16
Addizione binaria 1
• Somma di due bit
• x+y
• s = Somma
• c = Carry (RIPORTO)
x
0
0
1
• Esempio
carry (c) 1
addendo
addendo
somma
1
1
1
1
1
1
0
1
0
1
1
0
1
0
1
0
1
1
1
0
0
1
A.S.E.
y
0
1
0
s
0
1
1
c
0
0
0
1 1 0 1
1
1
0
89 + 117 = 206
3.17
Addizione binaria 2
• In caso di numeri frazionari si deve allineare il
punto binario
• Esempio
1011.011+110.1011 =10010.0001
1
1
1
1
0
1
0
1
0
1
1
1
1
1
1.
0.
0.
1
0
1
0
1
1
0
0
A.S.E.
1
1
0
1
1
11.375 +
06.6875 =
18.0625
3.18
Addizione ternaria 1
x
0
0
0
1
1
1
2
2
2
• Somma di due digit
• x+y
• d = Somma
• c = Carry (RIPORTO)
• Esempio:
riporto (c)
addendo
addendo
somma 1
1
2
1
1
1
0
2
0
1
2
2
2
1
1
1
0
2
1
0
A.S.E.
0
2
2
1
1
2
y
0
1
2
0
1
2
0
1
2
s
0
1
2
1
2
0
2
0
1
c
0
0
0
0
0
1
0
1
1
1666 +
1420 =
3086
3.19
Addizione ternaria 2
• In caso di numeri frazionari si deve allineare il
punto ternario
• Esempio
2012.012+120.1022 =2202.1212
2
2
1
0
1
2
1
2
0
2. 0
0. 1
2. 1
1
1
0
2
A.S.E.
2
2
1
2
2
59.1851 +
15.4320 =
73.6171
3.20
Sottrazione
• Sottrazione di due digit
– Può essere espressa i modo tabellare
• Sistema binario
b
a-b
0
a
Sistema ternario
b
a-b
0
1
0
0
1
B=1
1
1
0
0
0
a 1
1
2
2
A.S.E.
1
2
2
1
B=1 B=1
2
0
B=1
1
0
3.21
Sottrazione binaria 1
• Sottrazione di due bit
• x-y
• D = Differenza
• B = Borrow (PRESTITO)
x
0
0
1
• Esempio
prestito (b) 1
minuendo 1
sottraendo
differenza
y
0
1
0
D
0
1
1
B
0
1
0
1 1 0 0
1
1
1
1
1
0
1
0
0
1
1
1
0
1
1
1
0
A.S.E.
1
1
0
0
0
1
1
206 –
117 =
89
3.22
Sottrazione binaria 2
• In caso di numeri frazionari si deve allineare il
punto binario
• Esempio
10010.0001- 1011.011 =110.1011
1
1
1
0
1
1
0
0
1
1
1
1 1
0. 0
1. 0
1
0
1
0
1
1
0
1
1
0. 1
0
1
1
A.S.E.
18.0625 11.375 =
06.6875
3.23
Sottrazione ternaria 1
x
0
0
0
1
1
1
2
2
2
• Sottrazione di due digit
• x-y
• D = Differenza
• B = Borrow (PRESTITO)
• Esempio
prestito (b) 1 1
minuendo
1 1
1
0
sottraendo
1
2
2
0
differenza
1
2
1
0
0
2
2
2
2
1
1
1
2
2
0
1
1
A.S.E.
y
0
1
2
0
1
2
0
1
2
D
0
2
1
1
0
2
2
1
0
B
0
1
1
0
0
1
0
0
0
3086 –
1420 =
1666
3.24
Sottrazione ternaria 2
• In caso di numeri frazionari si deve allineare il
punto ternario
• Esempio:
prestito (b)
minuendo
sottraendo
differenza
2
2
1
1
2 0 2. 1 2 1 2
0 1 2. 0 1 2
1 2 0. 1 0 2 2
73.6171 59.1851 =
15.4320
• Esempio 2:
– 2012.012 - 120.1022 = 2202.1212
A.S.E.
3.25
Moltiplicazione
• Moltiplicazione di due digit
– Può essere espressa i modo tabellare
• Sistema binario
axb
0
0 0
a
1 0
b
Sistema ternario
axb
b
1
2
0
0
0 0
0
0
1
a 1 0
1
1
2 0
A.S.E.
2
1
2
C=1
3.26
Moltiplicazione binaria
x y P
0 0 0
0 1 0
• Prodotto di due bit
• X*Y
• P = Prodotto
• Esempio
moltiplicando
moltiplicatore
Prodotti parziali
prodotto
1 0. 1 1
1 0 1
1 0. 1 1
0 0 0. 0
1 0 1 1
1 0 0
1 1 1
2.75 *
5=
13.75
1 1 0 1. 1 1
A.S.E.
3.27
Moltiplicazione ternaria
x y P C
0 0 0 0
0 1 0 0
• Prodotto di due digit
• XxY
• P = Prodotto
• C = Carry
0
1
1
1
• Esempio
moltiplicando
moltiplicatore
Prodotti parziali
prodotto
2 1 0 2
1 0 2
1 1 2 1 1
0 0 0 0
2 1 0 2
65 *
11 =
715
2
0
1
2
0
0
1
2
0
0
0
0
2 0 0 0
2 1 2 0
2 2 1 1
2 2 2 1 1 1
A.S.E.
3.28
Divisione binaria
• Operazione divisione si effettua con
moltiplicazioni e sottrazioni multiple
• Divisione binaria:
dividendo
1 0 1
- 1 1
1 0
- 1
0
-
0 0. 1 1 1
1 1 0. 1
0
1
1 0
0 0
1 0 1
- 1 1
resto
1 0
A.S.E.
divisore
quoziente
3.29
Divisione Ternaria
• Esempio
dividendo
2 0
-1 2
1
0
1
1
1 0 1 2
1 0 2
1
0
1 0
0 1
2 resto
A.S.E.
divisore
quoziente
3.30
Conversione di base
• Un numero è un insieme di simboli o cifre che
rappresentano una certa quantità
– la rappresentazione di un numero è relativa alla base di
rappresentazione utilizzata
• Una numero può essere espresso in qualunque base di
rappresentazione
– esistono diverse rappresentazioni di uno stesso valore (numero)
• Un intero espresso in base a è un intero anche in base b
• Un numero frazionario espresso in base a è un numero
frazionario anche in base b
• Esistono due tecniche di conversione da una base ad
un’altra (a  b:
– metodo polinomiale (le operazioni si fanno nella base d’arrivo)
– metodo iterativo (le operazioni si fanno nella base di partenza)
A.S.E.
3.31
Metodo polinomiale
• Il numero “N” espresso in base “a” ha la forma:
N (a )  d n1(a ) d n2(a )    d1(a ) d 0(a ) , d 1(a )    d m(a )
 d n1(a )  a (na)1     d 0(a )  a (0a ) .d 1(a )  a (a1)     d m(a )  a (am)
• In base a = 10 si ha:
N(a )  d n1(a ) 10(na1)    d0(a ) 100(a ).d 1(a ) 10(a1)    d m(a ) 10(am)
• In base “b” il numero “N” risulta espresso da:
N( b )  d n1( b )  a (nb)1    d0( b )  a (0b ) .d 1( b )  a (b1)    d m( b )  a (bm)
• Calcolando il risultato di questo polinomio in
aritmetica in base b, i può completare la
conversione:
N (a )  N ( b )
A.S.E.
3.32
Esempio 1
• Convertire 1101 in base 2 nell’equivalente in
base 10
1101( 2 )  1( 2 ) 103( 2)  1( 2) 10(22 )  0( 2 ) 101( 2 )  1( 2) 100( 2 )




 1(10)  23(10)  1(10)  2(210)  0(10)  21(10)  1(10)  20(10)
 8  4  0 1
 13(10)
A.S.E.
3.33
Esempio 2
• Convertire il numero binario 101.011
nell’equivalente in base 10
101.011( 2 )  1( 2 ) 10(22 )  0( 2 ) 101( 2 )  1( 2 ) 100( 2 )  0( 2 ) 10(21)  1( 2 ) 10(22)  1( 2 ) 10(23)
 1(10)  2(210)  0(10)  21(10)  1(10)  20(10)  0(10)  2(101 )  1(10)  2(102 )  1(10)  2(103 )
 4  0  1  0.25  0.125  5.375(10)
• Convertire il numero ternario 201.1
nell’equivalente in base 10
201.1(3)  2 (3) 10(23)  0( 3) 101(3)  1(3) 100( 3)  1( 3) 10 (31)
 2(10)  3(210)  0(10)  31(10)  1(10)  30(10)  1(10)  3(101 )
 18  0  1  0.3333....  19.333...(10)
A.S.E.
3.34
Esempio 3
• Convertire il numero esadecimale D3F
nell’equivalente in base 10
D3F(16)  D (16) 10 (216)  3(16) 101(16)  F(16) 10 0(16)
 13(10) 16 (210)  3(10)  161(10)  15(10)  16 0(10)
 13  256  3 16  15  3391(10)
• Osservazione: il metodo polinomiale è
conveniente per la conversione da una generica
base a alla base 10
A.S.E.
3.35
Esempio 4
(numeri frazionari)
• Conversione da base a a base 10
• Rappresentazione polinomiale del numero in base a:
N  dn1a n1    d0a 0 .  d1a 1    dma m
• Esempio : convertire il numero binario 1101.101 in base 10:
1101.101  1 23  1 2 2  0  21  1 20.  1 2 1  0  2 2  1 2 3 
 1 8  1 4  0  2  11.  1 0.5  0  0.25  1 0.125 
 8  4  1  0.5  0.125  13.625
A.S.E.
3.36
Metodo iterativo
(numeri interi)
• Tecnica delle divisioni successive
– Si basa sul teorema della divisione con resto;
• Dividendo un numero per la sua base, il resto della
divisione intera è l’ultima cifra della sua rappresentazione
in tale base
N  d n 1a n 1  d n  2a n 2     d1a 1  d 0a 0
N1 
N
a
 d n 1a n 2  d n 1a n 3     d1a 0
N
resto di    d 0
a 
N  N1a  d 0
A.S.E.
3.37
Esempio 1
• Convertire il numero 52 in base 10
nell’equivalente in base 2
52 2
0
26 2
0
13 2
1
6 2
0
3 2
• Quindi:
1
1
5210  1101002
A.S.E.
3.38
Esempio 2
• Convertire il numero 58506 in base 10
nell’equivalente in base 16
58506 16
10 3656 16
(A)
• Quindi
8
(8)
228 16
4 14
(4) (E)
5850610  E48A16
A.S.E.
3.39
Esempio 3
• Convertire il numero 58506 in base 10
nell’equivalente in base 8
58506 8
2 7313 8
1
914 8
2
114 8
2
• Quindi
14 8
6
1
5850610  1622128
A.S.E.
3.40
Osservazione
• Il metodo iterativo utilizza l’aritmetica della
base di partenza
– è particolarmente conveniente per la conversione
da base 10 ad una generica base b diversa da 10
A.S.E.
3.41
Metodo iterativo
(numeri frazionari)
• Conversione da base 10 a base b
• La parte intera procedimento prima visto
• Per la parte frazionaria in base b si ha
N F  d 1b 1  d 2 b 2    d m b m
• Moltiplicando per la base si ha
b  N F  d1  d2 b 1    dm b m1  d1  N F'
b  N F'  d2  d3b 1    dm b m2  d2  N F''
b  N F''  
• La conversione può non avere fine, si arresta una volta
raggiunta la precisione desiderata (con un certo numero di
cifre decimali)
A.S.E.
3.42
Esempio
• Conversione da base 10 a base 16
N F  0.843510
16  0.8435
16  0.496
16  0.936
16  0.976
 13.496
 7.936
 14.976
 15.616
d 1  D
d 2  7
d 3  E
d 4  F
N F  0.D 7 EF16
A.S.E.
3.43
Errore di Conversione
• Avendo arrestato la conversione al quarto passaggio si
commette un errore di conversione
• L’entità dell’errore si può valutare convertendo di
nuovo il risultato ottenuto in base 10 e valutando la
differenza rispetto al numero di partenza (in aritmetica
decimale)
N F  0.8435
N 1F 16  0.D7 EF16
N 1F 10  D 16 1  7 16 2  E 16 3  F 16 4  0.8434906006
 ass  N F  N 1F 10  0.8435  0.8434906006  0.0000093994
A.S.E.
3.44
Osservazione
• È vera la seguente uguaglianza:
a ma 
N N m
a b 
• Quindi, per convertire dalla base a alla base b un
numero frazionario lo si può moltiplicare per a (ma )  10(ma ) ,
il cui risultato è un numero intero, convertibile con il
metodo delle divisioni successive, e quindi si deve
dividere (in base b) il risultato ottenuto per a (mb )
• Dualmente, si può anche considerare: N  N  b ma' b mb'

– OSS1: m’ potrebbe anche essere diverso da m;

– OSS2: la divisione in base b diventa adesso uno spostamento
m'
0 (b )
della posizione della virgola, dato che b ( b )  10

m'
A.S.E.
3.45
Esempio 1
• Convertire il numero 61.25 da base 10 a base 8
– m = 2, si moltiplica per 102 =100 e si eseguono le
divisioni successive in base 10:
6125 8
5 765 8
5 95 8
7 11 8
3
1
– Il risultato si divide per 102(10) = 144(8), quindi risulta:
• N = 13755 / 144 = 75.2
– N.B.: la divisione è eseguita in base 8!
A.S.E.
3.46
Esempio 2
• Convertire il numero 61.25 da base 10 a base 8
– si moltiplica per 82 = 64 in base 10, e si eseguono le
divisioni successive per 8 in base 10 (8(10))
3920 8
0
490 8
2
61 8
5
7
– il risultato si divide per 82(10) = 100(8), quindi risulta
• N(8) = 7520 / 100 = 75.2
– N.B.: la divisione è fatta in base 8 (ma ora ha
complessità nulla!)
A.S.E.
3.47
Conclusioni
• Aritmetica binaria
• Conversione da base “N” a base 10
• Conversione da base 10 a base “N”
A.S.E.
3.48