Post on 01-May-2015
Luglio 2002 Algebra binaria 1
Algebra binaria
Luglio 2002
Luglio 2002 Algebra binaria 2
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 3
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 4
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 5
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 6
ESEMPI DI CONVERSIONE A BASE DECIMALENel 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 7
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 8
I PRIMI 16 NUMERI IN BASE 10,2,8,16
SISTEMA DI NUMERAZIONE decimale binario ottale esadecimale 0 0000 0 0 1 0001 1 1 2 0010 2 2 3 0011 3 3 4 0100 4 4 5 0101 5 5 6 0110 6 6 7 0111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F
Luglio 2002 Algebra binaria 9
I NUMERI NEGATIVI
Sign Magnitude One’s Complement Two’s Complement
000 = +0 000 = +0 000 = +0 001 = +1 001 = +1 001 = +1 010 = +2 010 = +2 010 = +2 011 = +3 011 = +3 011 = +3 100 = -0 100 = -3 100 = -4 101 = -1 101 = -2 101 = -3 110 = -2 110 = -1 110 = -2 111 = -3 111 = -0 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 10
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 11
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 12
OPERAZIONI ARITMETICHE SU NUMERI BINARI
0 1 0 1
0 0 1 addizione 0 0 0 moltiplicazione
1 1 10 1 0 1
1001,11+ 111,10 - 111,1 x 100011:101=111 1100,01= 10,01= 10,01= 10110110,00 101,01 1111 111
1111 101 10000,111 101
101 -
Le operazioni aritmetiche su numeri binari si eseguono con le usuali regole, tenendo presenti le seguenti tavole di addizione e di moltiplicazione:
Luglio 2002 Algebra binaria 13
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 dix2 y=f (x1,x2,…,xn)
commutazionexn
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 14
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 15
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 16
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 ANDassume il valore 1 se e solo se tutte le variabili valgono 1
Somma logica di A1… An è la funzione
X = A1+ Ax+ …. An ORassume il valore 0 se e solo se tutte le variabili valgono 0
Inversione della variabile booleana Y, la funzioneX = Y NOT
assume il valore 0 se Y vale 1, assume valore 1 se Y vale 0Di conseguenza X*X = 0 X+X=1
Non equivalenza la funzione f(x,y): assume valore 1 se le variabili sono diverse OR ESCLUSIVONOR = OR NAND = AND
Luglio 2002 Algebra binaria 17
SOMMA A 32 BITSNell’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) (riporti)
… 0 0 0 1 1 1
… 0 0 0 1 1 0
… (0)0 (0)0 (0)1 (1)1 (1)0 (0)1
Luglio 2002 Algebra binaria 18
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 19
A B C A AND NOT (B OR C) A OR (B AND (NOT C))
0 0 0 0 0
0 0 1 0 00 1 0 0 10 1 1 0 01 0 0 1 11 0 1 0 11 1 0 0 11 1 1 0 1
Luglio 2002 Algebra binaria 20
OPERATORI LOGICI (o porte logiche)
Reti logiche: circuiti che realizzano una funzione logica
Luglio 2002 Algebra binaria 21
Luglio 2002 Algebra binaria 22
c = AND (B1,B2)
R = OR (AND (NOT (B1), B2), AND (B1, NOT (B2)))