LL’’algebra algebra BooleanaBooleana

(1)

L L ’ ’ alg eb ra alg eb ra Bo ole an a Bo ole an a Alg eb ra Alg eb ra Bo ole an a Bo ole an a

Contempla due costanti

00e tio dgerico contatto nei uircuito a piùcontatn c ertivere lo stato di apsuura o chiura di un descrnossoPo o a i cCorrispondondue stathe si escludono a vicenda vefalso11rovee ofalsro)(

Si definiscono delle operazioni fra i valori booleani:ANDAND,

ORORNOTori i talendamfonoperat, gli nosoTNO 01

(2)

LL ’ op era zio ne di OR ’ op era zio ne di OR

Si definisce l’operazionedi somma logicasomma logica(OR):il valore della somma logica èil simbolo 1 se il valore di almeno uno degli operandièil simbolo 1

0

0 0

10+00+1 0+0 = 00+1 = 1

1+0 = 1

1+1 = 1 1

1 1

01+01+1

L L ’ ’ op era zio ne di AN D op era zio ne di AN D

Si definisce l’operazionedi prodottologicoprodottologico(AND):il valore del prodotto logico èil simbolo 1 se il valore di tutti gli operandièil simbolo 1

0××××0 = 0

0××××1 = 0

1××××0 = 0

1××××1 = 111

1××××1 01

1××××0 10

0××××1 00

0××××0

(3)

La ne ga zio ne N OT La ne ga zio ne N OT

Si definisce l’operatoredi negazionenegazione(NOT):l’operatore inverte il valore della costante su cui opera

0 = 1

1 = 0dalla definizione…

0 = 0

1 = 1

Va ria bili bin arie Va ria bili bin arie

Una variabile binaria indipendente può assumere unodei due valori

0

e

1

Date nvariabili binarie indipendenti, la loro somma logica (OR) è x 01 x1+x2+…+xn= 1se almeno una xivale 1

0sex1 = x2 = …= xn =0

(4)

AN D e N OT co n va ria bili bin arie AN D e N OT co n va ria bili bin arie

x1×x2×…×xn= 0se almeno una xivale 0

1sex1 = x2 = …= xn =1 Date nvariabili binarie indipendenti, il loro prodottologico (AND) è

La negazione di una variabile xè

x=0sex=1x=1sex=0

Alc un e id en tit Alc un e id en tit à à

x+1=1x+0=xx+x=x x ××××1= xx××××0= 0x××××x= x

x ××××1=x

1××××1=10××××1=0 x =0x =1

OK!OK! Si verificano le uguaglianze

Ad esempio…

(5)

Per gli operatori AND e OR valgono le seguenti proprietà:

Per l’operatore NOT si provano le seguenti identità:

Alt re pro prie t Alt re pro prie t à à

com mu tativ a com mu tativ a

x1 +x2 =x2 +x1 x1 ×x2 =x2 ×x1

ass ocia tiva ass ocia tiva

x1 +x2 +x3 =x1 +(x2 +x3 )x1 ×x2 ×x3 =x1 ×(x2 ×x3

dist ribu tiva de l dist ribu tiva de l pro dott o ris pett o a lla s om ma pro dott o ris pett o a lla s om ma

x1 ×x2 +x1 ×x3 =x1 ×(x2 +

x+x=1x××××x=0x=x

Daten variabili binarie indipendenti x1 , x2 ,…, xn , questepossono assumere 2 n configurazioni distinte

Una configurazione specifica èindividuata univocamente da un AND (a valore 1) di tutte le variabili, dove quellecorrispondenti ai valori 0 compaiono negate

Co nfig ura zio ni d elle va ria bili Co nfig ura zio ni d elle va ria bili

Ad esempio per n=3 si hanno 8 configurazioni

x1 x2 x3 000001010011100101110111

x1 x2 x3 010

(6)

Una variabiley èuna funzionedellen variabili indipendenti x1 , x2 ,…, xn ,se esiste un criterio che facorrispondere in modo univoco ad ognuna delle 2 nconfigurazioni delle xi un valore di y

Una rappresentazione esplicita di una funzione èla tabella di verittabella di verit

y 12n re xxdi ni ioazbinmcodi valo, x, ,con associato il, … ààili elessibin cui si ncano tutte le po, ^y^F⁼_(x

gic he i lo ion nz Fu Fu nz ion i lo gic he

1 ,x2 ,…,xn )

x1x2y

0 0 0

0 1 1

1 0 1

1 1 1 y = x1 +x2

Un a t ab ella di ve rit Un a t ab ella di ve rit à à

Date tre variabili booleane(A,B,C), si scriva la funzione Fche vale 1 quando solo due di esse hannovalore 1ABCF

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0 Si può scrivere la funzionecome somma logicadelle configurazioni corrispondentiagli 1

F(A,B,C) = ABC + ABC + ABCForma canonica: somma di prodotti (OR di AND)Forma canonica: somma di prodotti (OR di AND)−tutte le funzioni logiche si possono scrivere in questa forma

(7)

Un es em pio : lo X OR Un es em pio : lo X OR

La funzioneXOR verifica la disuguaglianza di due variabili

L’espressione come somma di prodotti èquindi... x1 x2 XOR

0 0 0

0 1 1

1 0 1

1 1 0

XOR= x1x2 +x1x2

Un cir cu ito co n d ue in ter ru tto ri Un cir cu ito co n d ue in ter ru tto ri

I due interruttori corrispondono a due variabili (A,B) a valori booleani−le variabili assumono i due valori 0 e 1 che corrispondono alle due posizioni dell’interruttore

AB

00

01

10

11

L = A××××B+AB AB011 0

A=1B=0 L

AB AB011 0

A=1B=1 L AB AB011 0A=0B=1 L

AB AB011 0

A=0B=0 L

(8)

Un es erc izio Un es erc izio

Progettare un circuito per accendere e spegnere una lampada da uno qualsiasi di tre interruttori indipendenti

ABC 111 000

ABC 11 0

1 00 000

001 Cambia lostato di uninterruttorequalsiasi L = 0L = 1

An alis i d elle co m bin azio ni An alis i d elle co m bin azio ni

Si c ons ide ra c osa acc ade a p artir e d alla co nfig ura zion e d i pa rten za, cam bia ndo lo s tato di u n in terr utto re p er v olta

ABC

000 L=0 L=1

ABC

010

ABC

001 L=1

ABC

100 L=1L=0

ABC

101 ABC

111 011 ABC L=0

110 ABC L=0

(9)

Sc ritt ura de lla fu nz ion e lo gic a Sc ritt ura de lla fu nz ion e lo gic a

Dalle otto combinazioni si ottiene latabella di verittabella di verit

funzione logica ààdella

Si può scrivere la funzioneLcome somma logica di somma logica di prodotti logiciprodotti logici A B C L

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 1

L = A××××B××××C + A××××B××××C + A××××B××××C + A××××B××××C

Co m e c olle ga re gli int err utt ori Co m e c olle ga re gli int err utt ori

Si può manipolare l’espressione di Lusando la proprietàdistributiva dell’AND rispetto all’OR

L = A××××(B××××C + B××××C)+ A××××(B××××C + B××××C) L = A××××B××××C + A××××B××××C + A××××B××××C + A××××B××××C

A A

B B

C CC CBBA A

B B

C CC CBB

1 0 01 0 1

(10)

Sis tem i d i n um era zio ne Sis tem i d i n um era zio ne Sis tem i d i n um era zio ne Sis tem i d i n um era zio ne

Sistemi di numerazioneposizionaliposizionali:La basebasedel sistema di numerazioneLecifrecifredel sistema di numerazioneIl numero èscritto specificando le cifre in ordine ed ilsuo valore dipende dalla posizione relativaposizione relativadelle cifreEsempioEsempio: Il sistema decimale (Base 10)

Cifre : 0 1 2 3 4 5 6 7 8 9

5641 = 510 3+ 610 2+ 410 1+ 110 0

Posizione: 3 2 1 0

(11)

Sis tem i in ba se B Sis tem i in ba se B

La base definisce il numero di cifre diverse nel sistema di numerazioneLa cifra di minor valore èsempre lo 0; le altre sono, nell’ordine, 1,2,…,B−1; se B>10 occorre introdurre B−10simboli in aggiunta alle cifre decimali

N = cn Bn+cn−1 Bn−1+...+c2 B2+c1 B1+c0 B0

Un num ero fraz ion ario fraz ion ario N’s i ra ppr ese nta co me (0, c

1

c

2

…c

n

)

B

Un num ero inte ro inte ro N s i ra ppr ese nta co n la scr ittu ra ( c

n

c

n−1

…c

2

c

1

c

0

)

B

N’= c1 B−1+c2 B−2+...+cn B−n

nn

cc cifra pi ùù èla cifra pi

sign ifica tiva sign ifica tiva ,

00

cc me no s ign ifica tiva la me no s ign ifica tiva

Nu m eri int eri se nz a s eg no Nu m eri int eri se nz a s eg no

Con n cifre in base B si rappresentano tutti i numeri interi positivi da 0 a B n−1 (B nnumeri distinti)EsempioEsempio: base 10

2 cifre: da 0 a 102−1 = 99 000102….9899EsempioEsempio: base 2

2 cifre: da 0 a 22−1 = 3 00011011 102= 100 valori

22= 4 valori

(12)

Il s iste m a b ina rio (B = 2) Il s iste m a b ina rio (B = 2)

La base 2La base 2

èèn sneioerazla nudi a mistemr ula copicùpipeisteioerazmnudi a mla n sr upecopicla piùne Cifre: 0 1 −bitbit(binarybinarydigitdigit)EsempiEsempi:(101101)2 = 1×25+ 0×24+1×23+1×22+0×21+1×20 =32 + 0 + 8 + 4 + 0 + 1 = (45)10(0,0101)2 = 0⋅2 −1+ 1⋅2 −2+ 0⋅2 −3+ 1⋅2 −4=0 + 0,25 + 0 +0,0625 = (0,3125)10(11,101)2 = 1⋅2 1+ 1⋅2 0+ 1⋅2 −1+ 0⋅2 −2+ 1⋅2 −3=2 + 1 +0,5 + 0 + 0,125 = (3,625)10

FormaForma

polinomiapolinomia

Unbytebyteèun insieme di 8 bit (un numero binario a 8 cifre

Con un by te s i ra ppr ese nta no i nu me ri in teri fra 0 e 2

8−

1 = 25 5

Èl’e lem ento ba se c on c ui s i ra ppr ese nta no i da ti n ei c alco lato ri

Si u tiliz zan o q uas i se mp re d im ens ion i m ultip le ( di p ote nze de l 2) del byte : 2 byte (16 bit) , 4 b yte (32 bit) , 8 b yte (64 bit) … Da l b it a l b yt e Da l b it a l b yt e

^b⁷^b⁶^b₅

b4b3b2b1b0

00000000000000010000001000000011…………….1111111011111111 28= 256 valori distinti

(13)

Da l b yt e a l ki lob yt e Da l b yt e a l ki lob yt e

Potenze del 2 Cosa sono KB (Kilobyte), MB (Megabyte), GB (Gigabyte), TB (Terabyte)? 24= 1628= 256216= 65536210= 1.024 (K=Kilo)≈migliaia220= 1.048.576 (M=Mega)≈milioni230= 1.073.741.824 (G=Giga)≈miliardi240 = 1.099.511.627.776 (T=Tera)≈migliaia di miliardi 1 KB = 2 10byte = 1.024 byte1 MB = 2 20byte = 1.048.576 byte1 GB = 2 30byte = 1.073.741.824 byte1 TB = 240byte = 1.099.511.627.776 byte (Terabyte)

Da de cim ale a bin ario Da de cim ale a bin ario − − 1 1 Si d ivid e ri petu tam ente il num ero inte ro inte ro dec im ale per 2 fin o a d otte nere un qu ozie nte nu llo; le c ifre de l nu me ro b ina rio s ono i re sti delle div isio ni; l a cif ra p iù sign ifica tiva è l’ult im o re sto

EsempioEsempio: convertire in binario (43)10 43 : 2 = 21 + 121 : 2 = 10 + 110 : 2 = 5 + 05 : 2 = 2 + 12 : 2 = 1 + 01 : 2 = 0 + 1 resti

bit piùsignificativo

(43)10 = (101011)2

(14)

Si m oltip lica rip etu tam ente il num ero fraz ion ario fraz ion ario dec im ale per 2, fino ad ott ene re u na p arte de cim ale nulla o, dato ch e la co ndiz ion e potr ebb e n on veri fica rsi m ai, per un num ero pre fiss ato di volt e; le cifre de l nu me ro b ina rio s ono le p arti inte re d ei p rod otti suc ces sivi; la c ifra più sign ifica tiva è il ris ulta to d ella prim a m oltip lica zion e Da de cim ale a bin ario Da de cim ale a bin ario − − 2 2

EsempioEsempio: convertire in binario (0,21875)10 e (0,45)100,45 ×2 = 0,90,90 ×2 = 1,80,80 ×2 = 1,60,60 ×2 = 1,20,20 ×2 = 0,4 etc.

(0.45)10≈(0.01110)2 0,21875 ×2 = 0,43750,4375 ×2 = 0,8750,875 ×2 = 1,750,75 ×2 = 1,50,5 ×2 =1,0

(0.21875)10 = (0.00111)2

Da bin ario a de cim ale Da bin ario a de cim ale

Oltr e a ll’es pan sion e e splic ita i n p ote nze de l 2

−

form a form a polin om ia polin om ia…

…si può o pera re nel mo do seg uen te: si rad dop pia il bit più sign ifica tivo e s i ag giu nge al sec ond o b it; s i ra ddo ppia la som ma e si a ggiu nge al t erzo bit… si c onti nua fin o a l bit m eno sig nific ativ o

EsempioEsempio: convertire in decimale (101011)2

bit piùsignificativo (101011)2 = 1×25+ 0×24+ 1×23+ 0×22+ 1×21+ 1×20 = (43)10

1 x 2 = 2 + 02 x 2 = 4 + 15 x 2 = 10 + 010 x 2 = 20 + 121 x 2 = 42 + 1 = 43

(101011)2 = (43)10

(15)

Sis tem a Sis tem a esa de cim ale esa de cim ale

La base 16 La base 16

èèpomatmfor inico cama sato uoltinpoatmfor insat camina o uoltmico

Cifre: 0 1 2 3 4 5 6 7 8 9 A B C D E F

EsempioEsempio:

(3A2F)16 = 3×163+ 10×162+ 2×161+ 15×160=3×4096 + 10×256 +2×16 + 15 = (14895)10 La corrispondenza in decimale delle cifre oltre il 9 è

A = (10)10 D =(13)10B = (11)10E = (14)10C = (12)10F = (15)10

Da bin ario a Da bin ario a esa de cim ale esa de cim ale

Una cifra esadecimalecorrisponde a 4 bit

Si p oss ono rap pre sen tare nu me ri b ina ri lu ngh i co n p och e cif re ( 1/4 ) La con vers ion e da bin ario ad esa dec im ale è im me dia ta, rag gru ppa ndo le cif re bin arie in g rup pi di 4 (da d estr a) e sos titu end ole co n le cifr e e sad ecim ali sec ond o la tab ella pre ced ente

0000 0 1000 80001 1 1001 90010 2 1010 A0011 3 1011 B0100 4 1100 C0101 5 1101 D0110 6 1110 E0111 7 1111 FF corrisponde a 4 bit a 1 0 corrisponde a 4 bit a 0

(16)

Da i b it a ll Da i b it a ll ’ ’ he x he x

Un numero binario di 4n bit corrisponde a un numeroesadecimaledi n cifreEsempioEsempio: 32 bit corrispondono a 8 cifre esadecimali

1101 1001 0001 1011 0100 0011 0111 1111D 9 1 B 4 3 7 F(D91B437F)16EsempioEsempio: 16 bit corrispondono a 4 cifre esadecimali

0000 0000 1111 11110 0 F F

(00FF)16

Da Da esa de cim ale esa de cim ale a b ina rio a b ina rio

La conversione da esadecimalea binario si ottieneespandendo ciascuna cifra con i 4 bit corrispondentiEsempioEsempio:

con vert ire i n b ina rio i l nu me ro e sad ecim ale

aliecimsaderi enum grataresenprerapper ne aziommpro i gi duaglingolti mta inusane azioNot

0x0x 0c8 f

0 c 8 f0000 1100 1000 1111

Il numero binario ha 4x4 =16 bit

(17)

Es em pi Es em pi − − 1 1 In qua lsia si bas e, l’es sere il siste ma di num era zion e

posizionaleposizionale

im pon e che co mb ina zion i d iver se di cifre ug uali rap pre sen tino num eri d iver si; a d e sem pio :

(319)10≠(193)10(152)6≠(512)6, infatti... (152)6=1×6 2+5×6 1+2×6 0=36+30+2=(68)10(512)6=5×6 2+1×6 1+2×6 0=180+6+2=(188)10

Num eri che h ann o ide ntic a rap pre sen tazio ne, in bas i d iver se, han no v alo ri d iver si:

(234)10≠(234)8 , infatti...(234)8= 2×8 2+ 3×8 1+ 4×8 0= 2×64 + 3×8 + 4 = 128+24+4 = (156)10

Oss erv azio ne Oss erv azio ne : p iù picc ola è la b ase , m ino re è il v alo re d el n um ero rap pre sen tato da lla s tess a se que nza di c ifre

Es em pi Es em pi − − 2 2 La nota zion e p osiz ion ale si a pplic a a nch e p er il ca lcolo de l va lore dei num eri f razio nari , in fatt i...

(0,872)10= 8×10−1+ 7×10−2+ 2×10−3= 8/10 + 7/100 + 2/1000 = 0,8 + 0,07 + 0,002

Qua nte cifr e o cco rrer ann o p er r app rese nta re il nu me ro d ecim ale 36 in b ase 2? Sap pia mo ch e co n n cifr e si rap pre sen tan o i n um eri d a0 a 2

n−

1, q uin di...

per n=1 (con una cifra) si rappresentano 0...21−1⇒0,1per n=2: 0...22−1⇒0...3per n=3: 0...2 3−1⇒0...7per n=4: 0...2 4−1⇒0...15per n=5: 0...25−1⇒0...31per n=6: 0...26−1⇒0...63 Effettivamente possiamo verificare che (100100)2=(36)10, infatti...100100=1×25+0×24+0×23+1×22+0×21+0×20

= 32 + 4 = 36con

del numero in base 2 66cifre necessarie per la codifica

(18)

Es em pi Es em pi − − 3 3

QuesitoQuesito : Per quale base B risulteràvera l’uguaglianza17 + 41 + 22 = 102 ?Se i numeri sono rappresentati in base B, sappiamo che:(17)B = 1×B1+7×B0= B+7(41)B = 4×B1+1×B0= 4B+1(22)B= 2×B1+2×B0= 2B+2(102)B= 1×B 2+0×B 1+2×B 0= B 2+2da cui...B+7+4B+1+2B+2 = 7B+10 = B 2+2⇒Si ottiene un’equazione di 2°grado:B2−7B−8 = 0Risolvendo: ∆= 49+32 = 81

B = (7 ±√∆)/2 =(7−9)/2 = −1 (7+9)/2 = 8

ÈÈla la soluzionesoluzione

!!

Non può essereuna base

La ra pp res en taz ion e d ei d ati La ra pp res en taz ion e d ei d ati e l e l ’ ’ arit m etic a d eg li e lab ora tor i arit m etic a d eg li e lab ora tor i

(19)

Nu m eri int eri po siti vi Nu m eri int eri po siti vi

I numeri interi positivi sono rappresentati all’internodell’elaboratoreutilizzandounmultiplodel byte (generalmente 2/4 byte)Sel’intero si rappresenta con unnumerodi cifre minore, vengono aggiunti zeri nellecifre piùsignificativeEsempioEsempio: 12 viene rappresentato in un byte come…00001100

Nu m eri co n s eg no Nu m eri co n s eg no

Per rappresentare numeri con segno, occorre utilizzare un bit per definire il segno del numeroSi possono usare 2 tecniche di codifica

Modulo e segnoComplemento a 2

(20)

M od ulo e se gn o M od ulo e se gn o

Il b it p iù sign ifica tivo ra ppr ese nta il seg no: 0 p er i n um eri pos itivi, 1 p er q uelli ne gati vi

Esis te u no z ero po sitiv o (0 0… 0) e un o ze ro n ega tivo (10 …0 )

Se si u tiliz zan o n bit si rap pre sen tan o tu tti i num eri com pre si fra

−

(2

n−1−

1) e +2

n−1−

1

EsempioEsempio: con 4 bit si rappresentano i numeri fra −7 (−(23−1)) e +7 (23−1) 0000 +00001 +10010 +20011 +30100 +40101 +50110 +60111 +7 1000 −01001 −11010 −21011 −31100 −41101 −51110 −61111 −7positivinegativi

Co m ple m en to a 2 Co m ple m en to a 2

Il c om ple me nto a 2 di u n n um ero bin ario (N )

2

a n cifr e è il n um ero

Tale nu me ro s i ott ien e…

Effettuando il complemento di ogni cifra del numero di partenza(complemento a 1): si trasforma ogni 0 in 1 e ogni 1 in 0Aggiungendo 1 al numero ottenuto

Opp ure : a part ire d a d estr a, la scia ndo inv aria te t utte le c ifre fin o a l prim o 1 co mp reso , qu ind i in vert end o il valo re d elle rim ane nti

010101111010100010101001 complemento cifre+ 1 100000000+ 011111111−010101111010100010101001 2 82 8−1N2 8−1−N2 8−1−N+1 2n−(N)2 = 10……0−(N)2

n {

(21)

In ter i in co m ple m en to a 2 In ter i in co m ple m en to a 2 I num eri p osit ivi num eri p osit ivi son o ra ppr ese nta ti co me in m odu lo e se gno I num eri n ega tivi num eri n ega tivi han no u n 1 ne lla p osiz ion e p iù sign ifica tiva e s ono rap pre sen tati in c om ple me nto a 2 Lo zero è rap pre sen tato co me nu me ro p osit ivo (co n u na seq uen za di n zer i) Il c am po d ei n um eri r app rese nta bili èd a

−

2

n−1

a + 2

n−1−

1

EsempioEsempio

: nu me ri a 4 c ifre

0000 +00001 +10010 +20011 +30100 +40101 +50110 +60111 +7 1000 −81001 −71010 −61011 −51100 −41101 −31110 −21111 −1 Nota: 0111 +71000 −8

In ter i a 16 bit In ter i a 16 bit Num eri i nte ri ra ppr ese nta ti su 16 bit in c om ple me nto a 2 :

Il piùgrande numero intero positivo è215−1=(32767)100111 1111 1111 11110x 7 F F FIl piùpiccolo numero intero negativo è−2 15=(−32768)101000 0000 0000 00000x 8 0 0 0 0111 1111 1111 1111 +1 1000 0000 0000 0000Il numero intero –1 èrappresentato come 1111 1111 1111 11110x F F F F 0000 0000 0000 0000 +1 0000 0000 0000 0001

(22)

Ad diz ion e b ina ria Ad diz ion e b ina ria

Le regole per l’addizione di due bit sono

L’ultima regola è…(1)2 +(1)2 = (10)2 …(1+1=2)10 !! 0 + 0 = 00 + 1 = 11 + 0 = 11 + 1 = 0 con riporto di 1

EsempioEsempio1 11 101011011+0101101010110101 riporti

181 91+90

So ttra zio ne bin aria So ttra zio ne bin aria − − 1 1

Le regole per la sottrazione di due bit sono

La sottrazione può divenire complicata: quando si ha una richiesta sulla cifra precedente a sinistra, che èuno 0, l’operazione si propaga a sinistra fino alla prima cifra ad 1 del sottraendo 0 −0 = 01 −0 = 11 −1= 010 −1 = 1 con prestito di 1 dalla cifra precedente a sinistraEsempioEsempio0 21 1 0 0 1−1 0 11 010 0 20 25 −5

(23)

So ttra zio ne bin aria So ttra zio ne bin aria

–– 22

Utilizzando la rappresentazione in complemento a 2, addizione e sottrazione sono trattate come un’unica operazioneN1−N2 = N1+(2 n−N2)−2 ncomplemento a 2 di N2 : (−N2 ) si trascura il bit n+1

Si c alco la il com ple me nto a 2 di N

2

Si s om ma N

1

con il c om ple me nto a 2 di N

2

Si tr asc ura il b it p iù sign ifica tivo de l ris ulta to

EsempioEsempio: (010001)2−(000101)2= (17)10−(5)10

010001 +1110111001100(12)10

{

Ove rflo w Ove rflo w

L’overflowoverflowsi ha quando il risultato di un’operazione non èrappresentabile correttamente con n bit Per evitare l’overflowoccorre aumentare il numero di bit utilizzati per rappresentare gli operandiC’èoverflowsec’èriporto al di fuori del bit di segno e non sul bit di segno, o se c’èriporto sul bit di segno, ma non al di fuori EsempioEsempio: 5 bit →[−16,+15]01110 +0101011000 14 +1024 11000 +10110101110 −8 +−10−18−8+14

Punteggio nei vecchi videogame…0111 1111 1111 1111 + 1 = 1000 0000 0000 000032767 + 1 = −32768

(24)

M olti plic azio ne bin aria M olti plic azio ne bin aria

Le regole per la moltiplicazione di due bit sono

Moltiplicare per 2 ncorrisponde ad aggiungere n zeri incoda al moltiplicando 0 ×0 = 00 ×1 = 01 ×0 = 01 ×1 = 1EsempioEsempio1100111 x 1011100111000000011001111000000011

110011 x 10000 = 11001100000000×16 = 24

La divisione binaria di A per B viene calcolata in modo analogo alla divisione decimale, cosìda ottenere un quoziente Q ed un resto R, tali che A = B×Q + R

La divisione binaria si compone di una serie di sottrazioni

Dividere per 2 nequivale a scorrere il numero a destra di n posizioni; le cifre scartate costituiscono il resto

Divi sio ne bin aria Divi sio ne bin aria

1 1 0 1 1 0 1 0 11 0 1 1 0 1 01 1 11 0 11 0 0

(

^^^

51:16 = 3con resto 3110011 :10000 = 11 con resto 11 54 = 5×10 + 4

(25)

Es erc izi Es erc izi

Esercizio 1Esercizio 1

Ass um end o c he un elab ora tore ra ppr ese nti i n um eri inte ri c on seg no su qua ttro bit in com ple me nto a 2, s i ca lcoli no entr am bi i me mb ri d ella seg uen te id enti tà:

(A(A

−−

C)+ B = (A +B ) C)+ B = (A +B ) 2) (84 2) (84 e ch tale se b

a)

Si d ete rm ini, se e siste ba , la di siste ma di num era zion e un

2Esercizio 2Esercizio

ella . osta risp ni d otiv m re le cute Dis bri? em m due azio A= 5 7 C= 7 B= B= 5, 7, A= 7. S C= ste i ot tien e lo sso con ulta to d al c alco lo d ei ris C

−−

C,

bb

= (1 202 ) = (1 202 )

1010 b)

Si dete rm ini, se esis te, la bas e b

≤

16 di un siste ma d i num era zion e ta le c he (72 5) (72 5)

bb−−

(62 6) (62 6)

bb

= (2 24) = (2 24)

1010

Co nfr on to de lle ra pp res en taz ion i Co nfr on to de lle ra pp res en taz ion i

InteriInteripositivipositivi0000000100100011010001010110011110001001101010111100110111101111 0123456789101112131415 +0+1+2+3+4+5+6+7-0-1-2-3-4-5-6-7 +0+1+2+3+4+5+6+7-8-7-6-5-4-3-2-1 Segno eSegno emodulomodulo

Complemento Complemento a 2a 2

+0+1+2+3+4+5+6+7-7-6-5-4-3-2-1-0

Complemento Complemento

a 1a 1

(26)

Nu m eri in vi rg ola m ob ile Nu m eri in vi rg ola m ob ile

La rappresentazione dei numeri in virgola mobile èinrelazione con la notazione scientificanotazione scientifica(es. 1.2×10 2=120)

La IEEE ha previsto uno standard per la rappresentazionein virgola mobilesingola precisionesingola precisione(32 bit = 4 byte)doppia precisionedoppia precisione(64 bit = 8 byte)quadrupla precisionequadrupla precisione(128 bit =16 byte)Singola precisione031222323 bit8 bitMantissa(o Caratteristica) Segno Se E≠0 e E≠255, il valore è(−1)S1.M×2E−127 Esponente

EccessoEccesso: vale 2t−1−1, se t èil numero di cifre riservate alla caratteristica →rappresentazione“interna”dell’esponente sempre positiva

Nu m eri in vi rg ola m ob ile : c asi sp ecia li Nu m eri in vi rg ola m ob ile : c asi sp ecia li

se E=255e M≠0NaN(nota number)0 11111111 10101000111000101001100se E=255, M=0, S=1-Infinity1 11111111 00000000000000000000000se E=255, M=0, S=0+Infinity0 11111111 00000000000000000000000se E=0, M=0, S=0+00 00000000 00000000000000000000000se E=0, M=0, S=1-0

0 00000000 00000100000110001100000 1 00000000 000000000000000000000000se E=0, M ≠0(−1)S0.M×2-126 Si dice valoredenormalzzato Ad esempio dividendo un numero per 0 puoottenere un NaN

(27)

Sin go la p rec isio ne Sin go la p rec isio ne Il n um ero più gra nde rap pre sen tab ile è 2

127×

(2

−

2

−23

)

≈

2

128≈

3.4 02

×

10 Il p iù picc olo nu me ro p osit ivo è2

−126×

2

−23

=2

−149≈

1.4 013

×

10

−45

In tota le si r app rese nta no 2

32

num eri dist inti, m età pos itivi, m età neg ativ i Circ a m età dei num eri s ono co mp resi fra

−

1 e 1 ( E

−

127 <0)

0 11111110 111111111111111111111112254−1271.111111111111111111111111

0 00000000 000000000000000000000012−1260.00000000000000000000001 0.50124 223valori2 23valori223valori223valori

Metodo per il calcolo dell’addizione1.

Se le c ara tter istic he dei num eri son o d iver se, si c ons ide ra il num ero co n ca ratt eris tica m ino re e …

1.1

Si tr asla la m anti ssa di u n p osto a d estr a

1.2

Si in cre me nta la c ara tter istic a d i 1 Si r ipe te 1 .1 e 1.2 fin o a qu and o le due ca ratt eris tich e so no ugu ali.

2.

La ma ntis sa del risu ltato è otte nuta da lla som ma de lle due ma ntis se

3.

La cara tter istic a d el r isult ato è iniz ialm ente qu ella de finit a a l pun to 1 . S e l’a ddiz ion e c om port a u n rip orto olt re la cifr a p iù sign ifica tiva , si tras la la m anti ssa de l ris ulta to a de stra di un pos to e si in cre me nta la c ara tter istic a d i 1. L L ’ ’ arit m etic a arit m etic a flo atin g flo atin g − − po in t po in t : a dd izio ne : a dd izio ne

(28)

Supponiamo che per la rappresentazione floating–pointvengano utilizzati otto bit, di cui uno per il segno, tre per la caratteristica (rappresetantain eccesso a 3) e quattro per la mantissa

La caratteristica del secondo operando èpiùpiccola di una unità, quindi lamantissa deve scorrere di una posizione a destra

La caratteristica del risultato è110, la mantissa è

Un es em pio di Un es em pio di ad diz ion e ad diz ion e

1.1001 ×22 ⇒0.1100 1×23 1.1001×22= 1.1101 ×23 =01100011 00111110N = (−1) s1.M×2 E−3

se non esistono sufficiense non esistono sufficienbit, ci bit, ci puopuo 100.110 0100.1 1 +101.1 i trontomencare derrontomencai trore derro ess unere’’ unereess

La caratteristica deve essere aumentata di 1 e la mantissa del risultato traslata a destra di una posizione:

Il risultato codifica il numero 1.0100 ×2 4=20 ma il risultato corretto è20.75: errore di troncamento. errore di troncamento.

Errori di approssimazioneErrori di approssimazionesono inevitabilisono inevitabilicon i numeri reali in ambito con i numeri reali in ambito scientifico! Occorre stimare il scientifico! Occorre stimare il massimo erroremassimo erroreche si che si puopuo’’commettere.commettere.

Un es em pio di Un es em pio di ad diz ion e ad diz ion e

E=110, M=10.1001

010110101

(29)

Metodo per il calcolo della moltiplicazione1.

Si m oltip lica no l e d ue m anti sse

2.

Si a ddiz ion ano le d ue c ara tter istic he

3.

Si tras la a s inis tra il p rod otto de lle due m anti sse fin o a d otte nere un 1 com e c ifra più sign ifica tiva ; s i a um enta la cara tter istic a d i 1 p er o gni tras lazio ne a de stra ese guit a

4.

Si tron ca la ma ntis sa al num ero d i bit utiliz zati nella rap pre sen tazio ne; la m anti ssa de l pr odo tto è il ris ulta to d el tron cam ento

5.

Si sott rae l’ec ces so alla som ma delle cara tter istic he, otte nen do l a ca ratt eris tica de l pro dott o L L ’ ’ arit m etic a arit m etic a flo atin g flo atin g −−

po in t po in t : m olt ip lic azio ne : m olt ip lic azio ne

Supponiamo che per la rappresentazione floating–pointvengano utilizzati otto bit, di cui uno per il segno, tre per la caratteristica e quattro per la mantissa

Moltiplicando le mantisse e sommando le caratteristiche si ottiene:

La mantissa del risultato deve essere traslata di un posto a destra, e la somma delle caratteristiche deve essere incrementata di 1;

Un es em pio di Un es em pio di m olti plic azio ne m olti plic azio ne

M=1.1101X 1.1001=10.11010101 E=010+101=111 011000111.1001×22=6.25 1.1101×2 -1= 000110110 = (−1)s1.M×2E−3

M=10.11010101⇒M=1.011010101E=111 ⇒E=1000

(30)

infine la mantissa deve essere troncata alle 4 cifre significative e l’eccesso (011) sottratto alla caratteristica:

Un es em pio di Un es em pio di m olti plic azio ne m olti plic azio ne

01011001

Codifica il numero 5.5, ma il risultato corretto è5.6640625: errore di troncamentoerrore di troncamento 1 0 0 0-0 1 1 M=1.011010101E=1000

L’aritmetica “interna”degli elaboratori differisce notevolmente dall’aritmetica classica

Sebbene le stesse operazioni possano essere realizzate secondo modalitàdiversesuelaboratori diversi,si riscontrano alcune caratteristiche comuni:

Rap pre sen tazio ne b ina ria d ei n um eri Rap pre sen tazio ne b ina ria d ei n um eri Ran go f inito de i nu me ri ra ppr ese nta bili Ran go f inito de i nu me ri ra ppr ese nta bili Pre cisio ne f inita de i nu me ri Pre cisio ne f inita de i nu me ri Op era zion i es pre sse in t erm ini d i op era zion i pi Op era zion i es pre sse in t erm ini d i op era zion i pi ùù sem plic i sem plic i L L ’ ’ arit m etic a d eg li e lab ora tor i arit m etic a d eg li e lab ora tor i − − 1 1

(31)

Rango finito dei numeri rappresentabiliRango finito dei numeri rappresentabili

Qu alu nqu e sia la c odif ica utiliz zata , es isto no s em pre il p iù gra nde ed il p iù picc olo nu me ro r app rese nta bile

I lim iti in ferio re e su peri ore de l ra ngo di r app rese nta zion e dip end ono sia da l tip o d i co dific a, s ia d al n um ero di bit utiliz zati

Se il ris ulta to di u n’o pera zion e n on app artie ne al r ang o dei num eri rap pre sen tab ili, si d ice che si è veri fica to u n ove rflo w (un und erflo w und erflo w , più pre cisa me nte , se il ri sult ato è più picc olo de l più picc olo nu me ro r app rese nta bile ) L L ’ ’ arit m etic a d eg li e lab ora tor i arit m etic a d eg li e lab ora tor i − − 2 2

Precisione finita dei numeriPrecisione finita dei numeri

La pre cisio ne pre cisio ne della ra ppr ese nta zion e di un num ero fraz ion ario è una m isur a d i q uan to ess a c orris pon da al num ero ch e d eve ess ere rap pre sen tato

Neg li e lab ora tori, i n um eri fraz ion ari son o ra ppr ese nta ti in virg ola mo bile ( floa ting floa ting

o d finit i bit –– poin t poin t), utiliz zan do un num ero

È pla usib ile che u n num ero re ale non am me tta una rap pre sen tazio ne finit a, q uin di d ovrà ess ere co dific ato in ma nie ra a ppr oss im ata

Neg li elab ora tori si rap pre sen tan o solt anto num eri razio nali (fin o a d u na d ata pre cisio ne) L L ’ ’ arit m etic a d eg li e lab ora tor i arit m etic a d eg li e lab ora tor i − − 3 3

(32)

Operazioni espresse in termini di operazioni piOperazioni espresse in termini di operazioni pi

firm e war nte me nte perm ane (in firm war e) zati, app am ente re aliz osit e g ene ralm ente m zati em oriz ope razio ni più sem plic i, s otto il con troll o d i p rog ram mi nte son o r ealiz zate m edia suc l’e uzio ne di i ces sion i d sec e hard war app osit i cir cuit i (in hard i più war sse com ple zion pera le o e); plic ope

razio ni p iù sem e d i so no ese guit am ente da Le irett

sottrazioni izze La divisione si real successione a di shiftper unamezzo di ioni edizad dishiftshift(traslazioni) La moltiplicazione si realizza per successidi one meunadi zzo ioneun’addiz izzLa sottrazione si realmezzo a per e didi entazione complemuna

irett do d i es egu ire d gra am tut te le op era zion i: ente egli

La m agg ior part e d po elab ora tori non ssie de circ in uiti

ùùseiplicmplicmsei

eg 4 − i tor ora li e lab a d m arit L ’ etic ora − L i tor eg lab li e a d etic m arit ’ 4

Co dific a d ei ca rat ter i a lfa be tic i Co dific a d ei ca rat ter i a lfa be tic i

Oltre ai numeri molte applicazioni informatiche elaborano caratteri(simboli)

Gli elaboratori elettronici trattano numeri

Si codificano i caratteri e i simboli con dei numeri

Per poter scambiare dati (testi) in modo corretto occorre definire uno standard di codificaA01000001300110011$00100100

Quando si scambiano dati deve essere noto il tipo di codifica utilizzato

In genere un sistema informatico deve supportare piùstandard di codifica

La codifica deve prevedere le lettere dell’alfabeto, le cifre numeriche, i simboli, la punteggiatura, i caratteri speciali per certe lingue(æ, ã, ë, è, …)