Algebra binaria
Luglio 2002
Luglio 2002
Algebra binaria
1
RAPPRESENTAZIONE DEI NUMERI NEI SISTEMI
DI ELABORAZIONE
Nel calcolo manuale le grandezze numeriche vengono rappresentate
con simboli grafici per la rappresentazione delle varie cifre.
Nel calcolo automatico esse saranno costituite da “enti” riconoscibili e
riproducibili dalle apparecchiature impegnate (esempio le diverse
tensioni in un circuito, presenza di diverse configurazioni di fori in
aree preassegnate in una certa zona di una superficie di carta)
Luglio 2002
Algebra binaria
2
RAPPRESENTAZIONE DEI NUMERI NEI SISTEMI
DI ELABORAZIONE (Cont.1)
Nei sistemi fisici utilizzati per la rappresentazione convenzionale di numeri, si
impiegano dispositivi che possono trovarsi solo in 2 diverse configurazioni (per
motivi di semplicità e sicurezza).
Dobbiamo quindi definire un sistema di numerazione binario e un’algebra binaria.
Luglio 2002
Algebra binaria
3
I NUMERI NATURALI
Sequenze delle 10 cifre (0,1…9)
Indo - Arabici (furono introdotti in Europa dagli Arabi nel Medio Evo)
In base 10
Posizionali (non addittivi)
Luglio 2002
Algebra binaria
4
NUMERI NATURALI (Cont.1)
1728 = 8 * 100 + 2 * 101 + 7 * 102 + 1 * 103
In generale un numero naturale XD di m+1 cifre può essere rappresentato dalla
sequenza
Xm Xm-1 ……… X1 X0
Ed è dato dalla seguente formula
m
Xd=x0 * 100 + x1 * 101 + ……+ xm-1 * 10 m-1 + xm * 10m =  x i * 10i
i =o
Luglio 2002
Algebra binaria
5
ESEMPI DI CONVERSIONE A BASE DECIMALE
Nel sistema binario le cifre sono 0 e 1
(La numerazione binaria, già nota agli antichi cinesi, è stata oggetto di studi di Nepero
[“Aritmetica Locale”] di F. Bacone e specialmente di Leibniz, che introdusse le notazioni
tuttora in uso)
1011012 = 1*20 + 0*21 + 1*22 + 1*23 + 0*24 + 1*25 =
= 1 + 4 + 8 + 32 = 4510
Nel sistema ottale le cifre sono 01234567
2578 = 7*80 + 5*81 + 2*82 = 7 + 40 + 128 = 17510
Nel sistema esadecimale (base 16) le cifre sono
0123456789ABCDEF
A4F16 = 15*160 + 4*161 + 10*162 = 15 + 64 + 2560 = 263910
Luglio 2002
Algebra binaria
6
Conversione da decimale a base diversa
169 : 2= 84 con resto di 1
84 : 2= 42 con resto di 0
42 : 2= 21 con resto di 0
21 : 2= 10 con resto di 1
10 : 2= 5 con resto di 0
5 : 2= 2 con resto di 1
2 : 2= 1 con resto di 0
1 : 2= 0 con resto di 1
16910 = 101010012
Verifica: 1*20 + 1*23 + 1*25 + 1*27 = 1+8+32+128 = 169
Conversione da binario a ottale ed esadecimale
10101001
2
= 010101001 2
Corrisponde a
A916
2518
Luglio 2002
Algebra binaria
7
I PRIMI 16 NUMERI IN BASE 10,2,8,16
decimale
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Luglio 2002
SISTEMA DI NUMERAZIONE
binario
ottale
0000
0
0001
1
0010
2
0011
3
0100
4
0101
5
0110
6
0111
7
1000
10
1001
11
1010
12
1011
13
1100
14
1101
15
1110
16
1111
17
Algebra binaria
esadecimale
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
8
I NUMERI NEGATIVI
Sign Magnitude
One’s Complement
Two’s Complement
000 = +0
001 = +1
010 = +2
011 = +3
100 = -0
101 = -1
110 = -2
111 = -3
000 = +0
001 = +1
010 = +2
011 = +3
100 = -3
101 = -2
110 = -1
111 = -0
000 = +0
001 = +1
010 = +2
011 = +3
100 = -4
101 = -3
110 = -2
111 = -1
da – (2m – 1 – 1) a (2m - 1 – 1)
da – (2m - 1) a (2m-1 –1)
in base 2 con numeri di m cifre
Luglio 2002
Algebra binaria
9
Con 32 bits:
0000 0000 0000 0000 0000 0000 0000 00002 = 010
0000 0000 0000 0000 0000 0000 0000 00012 = + 110
0000 0000 0000 0000 0000 0000 0000 00102 = +210
…
0111 1111 1111 1111 1111 1111 1111 11102 = +2.147.483.64610
0111 1111 1111 1111 1111 1111 1111 11112 = +2.147.483.64710
1000 0000 0000 0000 0000 0000 0000 00002 = -2.147.483.64810
1000 0000 0000 0000 0000 0000 0000 00012 = -2.147.483.64710
1000 0000 0000 0000 0000 0000 0000 00102 = -2.147.483.64610
…
1111 1111 1111 1111 1111 1111 1111 11012 = -310
1111 1111 1111 1111 1111 1111 1111 11102 = -210
1111 1111 1111 1111 1111 1111 1111 11112 = -110
Luglio 2002
Algebra binaria
10
CAMBIAMENTO DEL SEGNO
-Fare il complemento a uno (cioè cambiare gli 1 in 0 e viceversa)
-Sommare 1 nella posizione meno significativa
Esempio:
opposto di 410 cioè 0000…….0000 0100
1111…….1111 1011
1
1111……1111 1100  -410
ora verifichiamo calcolando nuovamente l’opposto
0000……0000 0011
1
0000……0000 0100  410
Luglio 2002
Algebra binaria
11
OPERAZIONI ARITMETICHE SU
NUMERI BINARI
Le operazioni aritmetiche su numeri binari si eseguono con le usuali
regole, tenendo presenti le seguenti tavole di addizione e di
moltiplicazione:
0
1
0 1
0 1
1 10
1001,11+
1100,01=
10110,00 101,01
addizione
0
0
0
0
1
111,10 10,01=
moltiplicazione
111,1 x
10,01=
1111
100011:101=111
101
111
1111
10000,111
Luglio 2002
1
0
1
Algebra binaria
101
101
101
12
CIRCUITI DI COMMUTAZIONE
Le informazioni sulle quali il calcolatore è chiamato ad operare sono
contenute in organi elementari che possono assumere soltanto due stati.
x1
Circuito di
x2
y=f (x1,x2,…,xn)
commutazione
xn
Il progetto di un calcolatore e la descrizione del suo funzionamento
sarebbero compiti ardui, se si facesse costante riferimento alla
costituzione fisica dei circuiti.
Significativi vantaggi si possono ottenere dai diagrammi a blocchi.
Luglio 2002
Algebra binaria
13
L’ALGEBRA E I CIRCUITI DI COMMUTAZIONE
L’applicazione dell’algebra della logica alla schematizzazione di
circuiti elettrici di commutazione operanti su segnali binari fu proposta
per la prima volta da Shannon in un suo articolo del 1938.
I circuiti sono allora schematizzabili per mezzo di formule o per mezzo
di diagrammi “logici”.
Se un dato circuito fisico adempiente date funzioni è realizzato in modo
che i segnali in entrata ed in uscita soddisfano alle condizioni di
variazioni discrete fra due soli valori, si potranno fare considerazioni
sul comportamento del circuito stesso riferendosi solo al suo modello
logico (algebrico e grafico) e prescindendo dalla realizzazione fisica
effettiva.
Luglio 2002
Algebra binaria
14
L’ALGEBRA DI BOOLE PER LO STUDIO DEI
CIRCUITI DI COMMUTAZIONE
Per la schematizzazione dei circuiti di commutazione e per
l’algebrizzazione delle dipendenze fra i segnali relativi si adopera la
formulazione dell’algebra della logica, proposta da G. Boole nella sua
opera del 1854: “An investigation of the laws of thought on which are
founded the mathematical theories of logic and probabilities”
Caratteristiche:
-Semplicità
-Identità con l’algebra usuale
-Tutte e sole le operazioni definite da Boole sono applicabili alla
schematizzazione dei circuiti di commutazione
Luglio 2002
Algebra binaria
15
DEFINIZIONI FONDAMENTALI
DELL’ALGEBRA DI BOOLE
Costante booleana: grandezza capace di possedere e conservare il suo valore
(0 o 1); es. tubazione in flusso continuo o interrotto
Variabile booleana: grandezza capace di assumere solo due valori (0 o 1); es.
interruttore
Prodotto logico di n variabili booleani A1… An è la funzione
X = A1 * Ax * …. An
AND
assume il valore 1 se e solo se tutte le variabili valgono 1
Somma logica di A1… An è la funzione
X = A1+ Ax+ …. An
OR
assume il valore 0 se e solo se tutte le variabili valgono 0
Inversione della variabile booleana Y, la funzione
X=Y
NOT
assume il valore 0 se Y vale 1, assume valore 1 se Y vale 0
Di conseguenza
X*X = 0
X+X=1
Non equivalenza la funzione f(x,y): assume valore 1 se le variabili sono
diverse
OR ESCLUSIVO
NOR = OR
NAND = AND
Luglio 2002
Algebra binaria
16
SOMMA A 32 BITS
Nell’Unità Aritmetica la somma viene eseguita bit per bit
prelevandoli dai registri. Ad ogni bit corrisponde una circuiteria “ad
hoc”
Si procede da destra a sinistra prestando grande attenzione ai riporti:
0000 0000 0000 0000 0000 0000 0000 01112 = 710
+ 0000 0000 0000 0000 0000 0000 0000 01102 = 610
= 0000 0000 0000 0000 0000 0000 0000 11012 = 1310
…
(0)
(0)
(1)
(1)
(0)
…
0
0
0
1
1
1
…
0
0
0
1
1
0
… (0)0
Luglio 2002
(riporti)
(0)0 (0)1 (1)1 (1)0 (0)1
Algebra binaria
17
Teoricamente la sottrazione si potrebbe ottenere con appositi circuiti
che operano pure bit per bit.
con il “prestito”
0000 0000 0000 0000 0000 0000 0000 01112 = 710
- 0000 0000 0000 0000 0000 0000 0000 01102 = 610
= 0000 0000 0000 0000 0000 0000 0000 00012 =
110
In pratica si somma al minuendo l’opposto del sottraendo
0000 0000 0000 0000 0000 0000 0000 01112 = 710
- 1111 1111 1111 1111 1111 1111 1111 10102 = - 610
= 0000 0000 0000 0000 0000 0000 0000 00012 =
110
Il risultato può essere troppo grande rispetto ai 32 bit
0111 1111 1111 1111 1111 1111 1111 11112 = 214748364710
+ 0000 0000 0000 0000 0000 0000 0000 00102 = 210
= 1000 0000 0000 0000 0000 0000 0000 00012 =-21474836710
Ci vorrebbero 33 bits!
Luglio 2002
Algebra binaria
18
ABC
A AND NOT (B OR C)
A OR (B AND (NOT C))
000
001
010
011
100
101
110
111
0
0
0
0
1
0
0
0
0
0
1
0
1
1
1
1
Luglio 2002
Algebra binaria
19
OPERATORI LOGICI (o porte logiche)
Reti logiche: circuiti che realizzano una funzione logica
Luglio 2002
Algebra binaria
20
Luglio 2002
Algebra binaria
21
c = AND (B1,B2)
R = OR (AND (NOT (B1), B2), AND (B1, NOT (B2)))
Luglio 2002
Algebra binaria
22