Luglio 2002Algebra binaria1 Luglio 2002. Algebra binaria2 RAPPRESENTAZIONE DEI NUMERI NEI SISTEMI DI...

Luglio 2002 Algebra binaria 1

Algebra binaria

Luglio 2002


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)


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.


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)


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


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


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


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


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


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


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


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:


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.


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.


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


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


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


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!


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


OPERATORI LOGICI (o porte logiche)

Reti logiche: circuiti che realizzano una funzione logica


c = AND (B1,B2)

R = OR (AND (NOT (B1), B2), AND (B1, NOT (B2)))

Luglio 2002Algebra binaria1 Luglio 2002. Algebra binaria2 RAPPRESENTAZIONE DEI NUMERI NEI SISTEMI DI...

Documents

Transcript of Luglio 2002Algebra binaria1 Luglio 2002. Algebra binaria2 RAPPRESENTAZIONE DEI NUMERI NEI SISTEMI DI...