Che materia stai cercando?

Basi di dati - il sistema di numerazione e l'algebra booleana Appunti scolastici Premium

Appunti di Basi di dati per l'esame della professoressa Farinetti sul sistema di numerazione e sull'algebra booleana. Gli argomenti trattati sono i seguenti: l'algebra booleana ed i sistemi di numerazione (posizionale, binario, ottale, esadecimale e decimale).

Esame di Basi di dati docente Prof. L. Farinetti

Anteprima

ESTRATTO DOCUMENTO

Rappresentazione in complemento a due

Un modo alternativo per calcolare il \complemento

a due" di un numero binario negativo e il seguente:

Considerando il numero da destra a sinistra eseguo

le seguenti operazioni:

copio tutti gli zeri no a trovare il primo uno

copio l'uno

complemento i restanti bit

Esempio: : : : : : : :::

01 01 01 1 0 0

:::

0 0

:::

1 0 0

: : : : : : :::

10 10 10 1 0 0

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.20

Esempi - complemento a due

Rappresentare in complemento a due su 5 bit il nu-

mero (+8) 10

codi co il modulo in binario (+8) = (1000)

10 2

il numero e positivo, quindi il bit di segno e 0

(+8) = (01000) CA

10 2

Rappresentare in complemento a due su 5 bit il nu-

;

mero ( 11) 10

codi co il modulo in binario (+11) = (01011)

10 2

complementando i bit si ha (10100) 2

sommando +1 (cioe 00001), si ha:

;

( 11) = (10101) CA

10 2

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.21

Conversione da complemento a due a

decimale

se il numero e positivo (MSB=0), si converte co-

me un numero binario puro

se il numero e negativo (MSB=1):

{ si sottrae 1

{ si complementano tutti i bit

{ si converte il numero cos ottenuto conside-

randolo come un numero binario puro

I primi due punti possono essere attuati anche

applicando l'operazione di complemento a 2 al

numero, infatti (( ) ) =

numero numero

CA CA

2 2

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.22

Conversione da complemento a due a

decimale - esempio

Scrivere il numero decimale corrispondente al nume-

ro 100101 in complemento a due su 6 cifre

Il numero (100101) e negativo, percio

CA

2

prima sottraggo 1, ottenendo (100100) 2

complementando i bit ottengo (011011)

2

converto considerando il numero in binario puro:

(011011) = 1 2 + 1 2 + 1 2 + 1 2 = (27)

4 3 1 0

2 10

;

Quindi il numero decimale corripsondente e 27.

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.23

Limiti delle rappresentazioni

Fissato il numero N di bit disponibili, e possibile

rappresentare i seguenti numeri:

binario puro ;

N

0 (2 1)

: : :

modulo e segno ; ; ; ;

; ;

N N

1 1

(2 1) 0+0 + (2 1)

::: :::

complemento a due ; ;

; ;

N N

1 1

(2 ) 0 + (2 1)

::: :::

Ad esempio, su 5 bit e possibile rappresentare i se-

guenti numeri:

in binario puro : da 0 a 31

;

in modulo e segno : da 15 a +15

;

in complemento a due: da 16 a +15

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.24

Rappresentazione di oggetti

Per rappresentare N oggetti con numeri binari oc-

corrono almeno K bit: d e

K N

= log ( )

2

d e

X

dove per si intende il numero intero immediata-

mente superiore od uguale ad X (funzione ).

ceiling

Ad esempio, per rappresentare 77 oggetti, sono ne-

cessari almeno 7 bit (2 = 128), dato che con 6 bit

7

posso arrivare solo no a 2 = 64.

6

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.25

Esercizi sulle rappresentazioni

Rappresentare in MS e in CA2 su 8 bit i seguenti

numeri decimali:

+12 [R. 0 0001100]

; 35 [R. 1 0100011]

[R. 1 1011101]

+40 [R. 0 0101000]

; 1 [R. 1 0000001]

[R. 1 1111111]

; 128 [R. Impossibile]

[R. 1 0000000]

+271 [R. Impossibile]

+127 [R. 0 1111111]

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.26

Somma in complemento a due

X Y

Dati due numeri e in complemento a due su N

X Y

bit, la somma + si calcola sommando aritmeti-

camente tutti i bit degli addendi, compreso quello di

.

segno

L'eventuale carry oltre il bit di segno viene tralascia-

to. ;

Esempio: calcolare ( 7) + (10) in complemento

10 10

a due su 5 bit ;

( 7) = 11001

10

(10) = 01010

10

1 1 0 0 1 +

0 1 0 1 0

1 0 0 0 1 1

Il carry nella posizione oltre il bit di segno non viene

considerato ed il risultato e 00011, ossia (3)

10

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.27

Di erenza in complemento a due

Ci si riconduce al caso della somma trasformando la

di erenza nella somma del primo numero con l'in-

verso del secondo. ; ;

Esempio: calcolare ( 7) (4) in complemento a

10 10

due su 5 bit. ; ;

Si opera come se l'operazione fosse ( 7) + ( 4) :

10 10

;

( 7) = 11001

10

;

( 4) = 11100

10

1 1 0 0 1 +

1 1 1 0 0

1 1 0 1 0 1

Tralasciando il carry oltre il bit di segno il risultato

;

e 10101, ossia ( 11) 10

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.28

Over ow in complemento a due

Si puo veri care se contemporaneamente:

i due addendi hanno segno concorde

il segno del risultato e diverso dal segno dei due

addendi s1

s1

s2 over ow 6

se e solo se s2 = s1

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.29

Esempio - over ow

; ;

Calcolare ( 12) + ( 6) in complemento a due su

10 10

5 bit: ;

( 12) = 10100

10

;

( 6) = 11010

10

1 0 1 0 0 +

1 1 0 1 0

1 0 1 1 1 0

Si ha carry oltre il bit di segno, che viene ignorato. Il

bit di segno e diverso da quello degli addendi, cioe il

risultato della somma di due numeri negativi sarebbe

positivo, il che e impossibile (over ow).

;

Veri ca: il risultato sarebbe ( 18) , non rappresen-

10

tabile in complemento a due su 5 bit.

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.30

Esercizi - somma e sottrazione in

complemento a due

Eseguire le seguenti operazioni in complemento a due

su 9 bit:

;

(131) (193)

10 10 ;

[R. ( 62) = 111000010]

10

;

(255) (256)

10 10 ;

[R. ( 1) = 111111111]

10

; ;

( 127) + ( 130)

10 10 ;

[R. ( 257) over ow]

10

;

(255) + (2) + ( 127)

10 10 10

[R. (130) = 010000010]

10

;

( 256) + (2)

10 10 ;

[R. ( 254) = 100000010]

10

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.31

Numeri frazionari

Conversione da decimale a binario:

si convertono separatamente parte intera e parte

frazionaria

per la parte intera si segue la procedura di con-

versione gia vista

per la parte frazionaria si e ettuano moltiplica-

zioni successive per 2 separando la parte intera

(0 o 1) da quella frazionaria cos ottenuta, nche:

{ : : : :

il risultato della moltiplicazione e 1 000

{ oppure si raggiunge la precisione richiesta

:

Esempio: convertire in binario (6 25) 10

(6) = (110)

10 2

0.25 0.5 0.0 parte frazionaria

0 1 parte intera

: :

6 25 = 110 01

10 2

.

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.32

Approssimazione dei numeri frazionari

Si noti che in generale ad un numero frazionario deci-

male con un numero limitato di cifre puo corrispon-

dere un numero frazionario binario con un numero

in nito di cifre. In tal caso ci si ferma quando si

raggiunge la precisione desiderata.

:

Esempio: convertire in binario (0 3) con la preci-

10

sione di almeno 1

100

0.6 0.2 0.4 0.8 0.6 0.2

0.3

0 1 0 0 1 1 0

" " " " " " "

1 1 1 1 1 1 1

1 2 3 4 5 6 7

2 2 2 2 2 2 2

: : : : :

(0 3) = 0 0100110

10 <

perche = .

L'errore e minore di 1 1 1

1 7

100 128 100

2

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.33

Esercizi - numeri frazionari

Convertire in binario i seguenti numeri

:

(0 625) 10 :

[R. 0 101 ]

2

:

(0 03125) 10 :

[R. 0 00001 ]

2

:

(0 828125) 10 :

[R. 0 110101 ]

2

Calcolare a quale numero decimale corrispondono i

seguenti numeri binari frazionari:

:

0 1101001 2 :

[R. (0 8203125) ]

10

:

1011 0101

2 :

[R. (11 3125) ]

10

:

11 10011 2 :

[R. (3 59375) ]

10

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.34

Rappresentazione in oating-point

Utilizzata per rappresentare numeri frazionari nella

notazione esponenziale: esponente

numero mantissa

= ( ) 2

Il formato piu utilizzato e quello IEEE P754, rap-

presentato su 32 bit nel seguente modo:

8 bit 23 bit

esponente mantissa (modulo)

S esponente

L' e rappresentato come numero senza se-

gno su 8 bit in , cioe i valori da -126 a

eccesso 127

+127 sono messi in corrispondenza con i valori da 0

a 255, per non dovere gestire anche il segno dell'e-

sponente.

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.35

Floating-point: mantissa

mantissa

La e codi cata su 24

in modulo e segno

bit,

la mantissa e sempre normalizzata nella forma

:XXXXX

1

si rappresenta solo la parte frazionaria nei 23 bit

meno signi cativi

;

il peso del MSB del modulo e 2 1

il segno e dato dal MSB dei 32 bit

La rappresentazione di un numero e quindi nella for-

ma Y Y Y Y

numero :XXXXX

= 1 2 2

( )

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.36

Conversione decimale IEEE P754

!

Per trasformare un numero decimale N nella sua rap-

presentazione in oating-point, si deve

trasformarlo in binario

trasformarlo nella forma normalizzata

:XXXXX Y Y Y Y

1 2 2

( )

il segno e 0 per i numeri positivi, 1 per i negativi

n n

l'esponente e pari a 127+ , dove e il numero di

posizioni di cui e stato spostato il punto decimale

dalla forma binaria a quella normalizzata

la parte frazionaria della mantissa normalizzata

XXXXX

( ) si memorizza nei 23 bit meno signi-

cativi

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.37

Esempio - oating-point

Convertire in formato oating-point IEEE P754 il

:

numero 13 25 10

il numero e positivo, per cui il segno e 0

il numero convertito in binario puro e :

:

1101 01 2

spostando il punto decimale di 3 posizioni, il nu-

mero si normalizza in

:

1 10101 2 3

2

l'esponente in eccesso 127 vale:

127 + 3 = 130 = 10000010

2

La rappresentazione richiesta e:

0 10000010 10101000000000000000000

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.38

Conversione IEEE P754 decimale

!

L'interpretazione di un numero e piuttosto compli-

s e m

cata: chiamando il segno, l'esponente, ed la

mantissa, si possono avere i seguenti casi:

e m

;

s

=0, =0: il valore e ( 1) (0), cioe +0 o -0

e m

6

=0, =0: il numero e nella forma non norma-

lizata

e

< <

0 255: il numero e nella forma

;

;

s e :m

( 1) 2 (1 )

( 127)

e m

; 1

s

=255, =0: il valore e ( 1) , cioe un numero

1 ;1

in nitamente grande o piccolo (+ o )

e m

6

=255, =0: non e un numero valido (detto

NAN, ); puo essere usato per co-

Not A Number

di care informazioni di errore

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.39

Esercizi - codi ca IEEE P754

Rappresentare in formato IEEE P754 i seguenti nu-

meri

:

5 0 10 : : :

[R. 0 10000001 0100 0]

; :

9 25 10 : : :

[R. 1 10000010 0010100 0]

:

12 8125 10 : : :

[R. 0 10000010 100110100 0]

Dati i seguenti numeri in formato IEEE P754, dire

a quale numero decimale corrispondono:

: : :

0 10000001 010010 0 [R. 5.125]

: : :

1 10001101 01110 0 [R. 23552.0]

: : :

0 01111101 01010 0 [R. 0.328125]

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.40

Codici BCD

E' una codi ca per rappresentare numeri decimali in

binario ( ).

Binary Coded Decimal

Il numero decimale viene suddiviso nelle cifre deci-

mali che lo compongono, e ciascuna di queste con-

vertita in binario puro secondo la corripondenza:

cifra codice

0 0000

1 0001

2 0010

3 0011

4 0100

5 0101

6 0110

7 0111

8 1000

9 1001

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.41

Esempi - codici BCD

Esempio: convertire il numero 1592 in codice BCD.

1 5 9 2

# # # #

0001 0101 1001 0010

Quindi 1592 = 0001010110010010 .

BCD

10

Esempio: ricavare il numero decimale corrispondente

al numero 01011000000001000111 BCD

0101 1000 0000 0100 0111

# # # # #

5 8 0 4 7

Quindi 01011000000001000111 = 58047 .

BCD 10

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.42

Esercizi - conversione binaro BCD

$

Convertire i seguenti numeri binari in BCD:

1000 1001 0011 0111 [R. 8937]

100 1000 0010 1001 [R. 4829]

1 0010 0011 0010 1001 0001 [R. 123291]

10 1001 0101 0110 0101 [R. 29565]

Convertire i seguenti numeri BCD in binario:

4171 [R. 100 0001 0111 0001]

6153 [R. 110 0001 0101 0011]

4261 [R. 100 0010 0110 0001]

10478 [R. 1 0000 0100 0111 1000]

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.43

Codi ca dell'informazione non numerica

I calcolatori possono intrinsecamente trattare solo

informazioni binarie. Per trattare numeri relativi

e frazionari abbiamo adottato particolari codi che

(modulo e segno, complemento a due, oating-point).

Piu in generale con i numeri binari posso rappresen-

tare insiemi di oggetti, stabilendo una

enumerabili

corrispondenza biunivoca tra oggetti e numeri (

codi-

).

ca

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.44

Codi ca dell'informazione non numerica

Per rappresentare i caratteri alfabetici esistono alcu-

ne codi che standard: ad esempio il codice ASCII (il

piu di uso) codi ca su 7 cifre binarie tutti i caratteri

alfabetici piu alcuni speciali.

Codice ASCII (ottale)

000 nul 001 soh 002 stx 003 etx 004 eot 005 enq 006 ack 007 bel

010 bs 011 ht 012 nl 013 vt 014 np 015 cr 016 so 017 si

020 dle 021 dc1 022 dc2 023 dc3 024 dc4 025 nak 026 syn 027 etb

030 can 031 em 032 sub 033 esc 034 fs 035 gs 036 rs 037 us

040 sp 041 ! 042 " 043 # 044 $ 045 % 046 & 047 '

050 ( 051 ) 052 * 053 + 054 , 055 - 056 . 057 /

060 0 061 1 062 2 063 3 064 4 065 5 066 6 067 7

< >

070 8 071 9 072 : 073 ; 074 075 = 076 077 ?

100 @ 101 A 102 B 103 C 104 D 105 E 106 F 107 G

110 H 111 I 112 J 113 K 114 L 115 M 116 N 117 O

120 P 121 Q 122 R 123 S 124 T 125 U 126 V 127 W

130 X 131 Y 132 Z 133 [ 134 135 ] 136 137

\ ^

140 ` 141 a 142 b 143 c 144 d 145 e 146 f 147 g

150 h 151 i 152 j 153 k 154 l 155 m 156 n 157 o

160 p 161 q 162 r 163 s 164 t 165 u 166 v 167 w

f g

170 x 171 y 172 z 173 174 & 175 176 177 del

~

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.45

Codi che

Un codice deve permettere di risalire dalla codi ca

al simbolo rappresentato: per questo motivo, una

stringa binaria su un certo numero di bit ha piu in-

terpretazioni, a seconda della codi ca che si conside-

ra.

Ad esempio, la stringa binaria 1101010 rappresenta:

il numero 106 in binario puro

il numero -42 in modulo e segno

il numero -22 in complemento a due

il carattere 'j' nella codi ca ASCII

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.46

Algebra Booleana

Opera su variabili che possono assumere soltanto i

due valori 0 e 1 (variabili Booleane).

Operazioni base:

AND OR

A B A B A B A B

+

0 0 0 0 0 0

0 1 0 1

0 1

1 0 0 1 0 1

1 1

1 1 1 1

NOT

A A

0 1

1 0

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.47

Algebra Booleana

Operazioni estese:

NAND NOR

A B A B A B

A B +

0 0 1 0 0 1

0 1 0 1

1 0

1 0

1 0 1 0

0 0

1 1 1 1

EXOR EXNOR

A B A B

A B A B

0 0 0 0 0 1

0 1 1 0 1 0

1 0 1 1 0 0

0 1

1 1 1 1

N.B. E possibile rappresentare qualunque espressio-

ne utilizzando esclusivamente l'operazione NAND op-

pure l'operazione NOR.

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.48

Funzioni booleane

Funzioni di variabili booleane che assumono soltanto

i valori 0 e 1.

De nite tramite , nelle quali si indi-

tabelle di verita

ca il valore assunto dalla funzione per ogni possibile

combinazione delle variabili.

F x ; x

Esempio: ( ) de nita da

1 2 x x F

1 2

0 0 0

1

0 1

1 0 0

1 1 1

Normalmente rappresentate nella forma di espressio-

, in cui le variabili booleane sono combi-

ni booleane

nate tramite i quattro operatori fondamentali

Esempio:

F x ; x x x x

( ) = +

1 2 1

1 2

c 1992 - 96 - L.Farinetti, C.Fornaro, A.Lioy, M.Poncino (POLITO - DAI) SN-AB.49


PAGINE

67

PESO

255.00 KB

PUBBLICATO

+1 anno fa


DETTAGLI
Esame: Basi di dati
Corso di laurea: Corso di laurea in ingegneria civile
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher cecilialll di informazioni apprese con la frequenza delle lezioni di Basi di dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Torino - Polito o del prof Farinetti Laura.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria civile

Riassunto di scienza e tecnologia dei materiali
Appunto
Scienze dei materiali
Appunto