rappresentazione in binario e algoritmi di conversione 20 ... · ai quali è progettato e...

Il linguaggio dei computer:rappresentazione in binario e algoritmi di

conversione

20 settembre 2018

Architettura degli Elaboratori

L’ Elaboratore (o calcolatore, o computer) è una macchina in grado di eseguire autonomamentesequenze di operazioni logiche-aritmetiche sui dati in ingresso (input) e restituire i risultati di tali operazioni in uscita (output)

L’ Architettura (informatica) è l’insieme dei criteri in base ai quali è progettato e realizzato un sistema informatico.

Modello di calcolo

Dal libro [P]

Achitettura Harward

La memoria è suddivisa in:Memoria dati eMemoria istruzioni

Studieremo il processore MIPS

• Un processore vero (vedi Appendice E)

• Sarà il nostro esempio di riferimento per studiare i principi di progettazione di un processore

Architettura Harward Modificata (Pipeline)

Studieremo UN processore particolare, ma per astrarreconcetti fondamentali della architettura degli elaboratori

Il nostro obiettivo finaleAlla fine del corso saprete come funziona una versione semplificata del processore MIPS

Dal libro [PH]

Il linguaggio dei computer

Linguaggio dei computer

I computer «parlano» in binario:

Spento, acceso (dei circuiti elettrici)

ON, OFF

1, 0 bit = binary digit

Rappresentazione in binario

Cosa possiamo rappresentare in binario?

Numeri (interi, col segno, con la virgola)

Parole (codificando le lettere)

Istruzioni

Programma

«Informazione»

Idea fondamentale su cui sono costruiti i calcolatori:

programmi e dati rappresentati da numeri


00 = 0

01 = 1

10 = 2

11 = 3

000 = 0

001 = 1

010 = 2

011

100

101

110

1110

1 0 = 2

1 = 3

0 = 0

1 = 1

0

01

1

00 = 4

01 = 5

10 = 6

11 = 7

0

0

0

01

1

1

1

000

001

010

011

100

101 = 13

110 = 14

111 = 15

0

0

0

0

0

0

0

01

1

1

1

1

1

1

1

Quali/ quanti interi posso rappresentare con una sequenza di n bit?

n = 1 n = 2 n = 3 n = 4

.

.

.

.

.

.

.

Osserva: Se con k bit posso

rappresentare p sequenze distinte, con

k+1 bit posso rappresentare 2p

sequenze distinte

Rappresentazione con n bit

Con n bit è possibile rappresentare tutti i 2n interi compresi fra 0 e 2n-1

Perché?

Sarà fondamentale in varie scelte della nostra architettura

ProvaSe con k bit posso rappresentare p sequenze distinte,

con k+1 bit posso rappresentare 2p sequenze distinte

1 bit 2= 21 sequenze distinte

2 bit 4 = 22 sequenze distinte



k bit 2k sequenze distinte

Si formalizza con una prova per induzione. Osservando che 2 2k = 2k+1

.

.

.

.

.

.


00 = 0

01 = 1

10 = 2

11 = 3

000 = 0

001 = 1

010 = 2

011

100

101

110

1110

1 0 = 2

1 = 3

0 = 0

1 = 1

0

01

1

00 = 4

01 = 5

10 = 6

11 = 7

0

0

0

01

1

1

1

000

001

010

011

100

101 = 13

110 = 14

111 = 15

0

0

0

0

0

0

0

01

1

1

1

1

1

1

1

Ma perché 101 in binario rappresenta 5 e 1101 = 13?

n = 1 n = 2 n = 3 n = 4

.

.

.

.

.

.

.

Notazione decimale

… o notazione araba:

7 5 2 = 7 102 + 5 101 + 2 100

Ogni cifra ha un peso diverso secondo la posizioneche occupa:

7 centinaia

5 decine

2 unità

E’ una notazione posizionale

Notazione binaria

1 0 1 = 1 22 + 0 21 + 1 20 = 5

1 1 0 1 = 1 23 +1 22 + 0 21 + 1 20 = 13

Ogni cifra ha un peso diverso secondo la posizione che occupa

E’ una notazione posizionale

Ambiguità

Per distinguere le due rappresentazioni:

(101)2 = (5) 10

(1101)2 = (13) 10

(1011)2 = (11) 10

Da binario a decimale

02457 22222N

141632128 181

N = (1 0 1 1 0 1 0 1)2

N = 1 27 + 0 26 + 1 25 + 1 24 + 0 23 + 1 22 + 0 21 + 1 20

7 6 5 4 3 2 1 0

Da decimale in binarioN = (181)10

Devo esprimere N come somma di potenze di 2. Cerco la più grande potenza di 2 contenuta in 181: 181 = 128 + 53 = 27 + 5353 = 32 + 21 = 25 + 2121 = 16 + 5 = 24 + 55 = 4+1 = 22+11 = 20

181 = 27+ 25+24 +22 + 20

181 = (10110101) 2

20=121=222=423=824=1625=3226=6427=12828=256

Nota: esiste un unico modo di esprimere un intero come somma di potenze distinte di 2

Vedremo altri «algoritmi» per i passaggi da decimale in binario e viceversa

Da decimale in binarioN = (181)10

Devo esprimere N come somma di potenze di 2. Cerco la più grande potenza di 2 contenuta in 181: 181 = 128 + 53 = 27 + 5353 = 32 + 21 = 25 + 2121 = 16 + 5 = 24 + 55 = 4+1 = 22+11 = 20

181 = 27+ 25+24 +22 + 20

181 = (10110101) 2

20=121=222=423=824=1625=3226=6427=12828=256

Nota: Poiché 181 = 27+ 25+24 +22 + 20, per rappresentare 181 in binario sono necessari almeno 8 bit. Però:181 = 0 210 + 0 29 + 0 28 + 1 27 + 0 26 + 1 25 + 1 24 + 0 23

+ 1 22 + 0 21 + 1 20

Quindi 181 = (00010110101) 2 con 10 bit

La notazione posizionale è definita solo per 2 e 10?

Potremmo definirla per 8?

Notazione posizionale (in base b generica)

(1 0 1) 10 = 1 102 + 0 101 + 1 100

(1 0 1) 2 = 1 22 + 0 21 + 1 20 = (5) 10

(1 0 1) 8 = 1 82 + 0 81 + 1 80 = ( 65 ) 10

(1 1 0 1) 10 = 1 103 + 1 102 + 0 101 + 1 100

(1 1 0 1) 2 = 1 23 +1 22 + 0 21 + 1 20 = (13) 10

(1 1 0 1) 8 = 1 83 +1 82 + 0 81 + 1 80 = ( 577 ) 10

SequenzeCome indicare una generica sequenza (o stringa) di lunghezza n?

Come indicare una generica sequenza di lunghezza 8?

a7 a6 a5 a4 a3 a2 a1a0

Dove a7, a6 , … , a1, a0 sono gli elementi della sequenza, in ordine;

il relativo indice indica (appunto) la posizione all’interno della sequenza.

Gli indici sono i = 0, 1, …, 6, 7. Gli elementi sono ai.

Esempio: 35082847

a7 =3, a6 =5, a5 =0, a4 =8, a3 =2, a2 =8, a1 =4, a0 =7

Una sequenza di lunghezza n la indicheremo così:

an-1 an-2 …a1 a0

Notazione binaria per numeri naturaliIn base 2.

I simboli ammessi sono 0,1.

Una sequenza / stringa di 0 e 1, di lunghezza n

an-1 an-2 …a1 a0

con ai {0, 1} per i = 0, 1, …, n-1

rappresenta l’intero N:

N = (an-1 an-2 … a1 a0 )2 =

= an-1 2n-1 + an-2 2n-2 + … + a1 21 + a0 20

In notazione compatta:

1

0

2n

i

ii

aN

Notazione posizionale (in base b generica)

In base b.

I simboli ammessi sono 0,1, … , b-1.

Una sequenza / stringa di 0, 1, … , b-1, di lunghezza n

an-1 an-2 …a1 a0

con ai {0, 1, … , b-1} per i = 0, 1, …, n-1

rappresenta l’intero N:

N = (an-1 an-2 … a1 a0 )b =

= an-1 bn-1 + an-2 bn-2 + … + a1 b1 + a0 b0

In notazione compatta:

1

0

n

i

iibaN

Esempi

(234)10

(234)8

(234)16

(101)10

(101)8

(101)2

10

2 2344103102

10

2 15648382

10

2 5644163162

10

2 1011100101

10

2 6518081

10

2 512021

Esercizi

• Da cosa sono caratterizzati i numeri pari in binario?(11010)2 è pari?

Dimostrare nel modo più formale, preciso e convincente la vostra affermazione.

• Da cosa sono caratterizzati i numeri multipli di 4 in binario?(11010)2 è pari?

Dimostrare nel modo più formale, preciso e convincente la vostra affermazione.

Algoritmi di conversione binario decimale

• Da binario a decimale: moltiplico ogni cifra per l’opportuna potenza di 2 e poi sommo

• Da decimale a binario: esprimo il numero come somma di potenze di 2, partendo dalla più grande potenza di 2 minore o uguale del numero

Esistono altri «algoritmi» per convertire un numero dalla rappresentazione binaria alla decimale e viceversa.Bisogna conoscere più metodi di soluzione! Per scegliere il più adatto, veloce, …. Mai accontentarsi!

Algoritmi di conversioneProblema della conversione da binario a decimale

Dati: n bit an-1, an-2, … , a1, a0

Risultato: l’intero N tale che N = (an-1 an-2…a1a0)2

Algoritmo = procedimento di calcolo che risolve il problema con una sequenza finita di passi elementari

Problema della conversione da decimale a binario Dati: un intero N

Risultato: n bit an-1, an-2 , … , a1, a0 tali che N = (an-1 an-2…a1a0)2

Verso un algoritmo di conversione da b=10b = 10

N = (3752) 10

n = 4

(3 7 5 2) 10 = 3 103 + 7 102 + 5 101 + 2 100

oppure lo possiamo ottenere così, leggendo la stringa da sinistra verso destra (immaginate di non sapere quante cifre saranno):

3 3 7 5 2

3 10 + 7 = 37 3 7 52

37 10 + 5 = 375 3 7 5 2

375 10 + 2 = 3752 3 7 5 2

S3 = 3

S2 = 37

S1 = 375

S0 = 3752 = N

Idea:

3 7 5 2 = 3 103 + 7 102 + 5 10 + 2 =

= (3 102 + 7 10 + 5 ) 10 + 2 =

= ( (3 10 + 7) 10 + 5 ) 10 + 2 =

= ( ( (3) 10 + 7) 10 + 5 ) 10 + 2

Verso un algoritmo di conversione da b=2b = 2

N = (1101) 2

n = 4

(1 1 0 1) 2 = 1 23 + 1 22 + 0 21 + 1 20

oppure lo possiamo ottenere così:

1 1 1 0 1

1 2 + 1 = 3 1 1 0 1

3 2 + 0 = 6 1 1 0 1

6 2 + 1 = 13 1 1 0 1

S3 = 1

S2 = 3

S1 = 6

S0 = 13 = N

Idea:

1 1 0 1 = 1 23 + 1 22 + 0 2 + 1 =

= (1 22 + 1 2+ 0 ) 2 + 1 =

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

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

S0 = S1 2 + a0

Sn-2 = Sn-1 2 + an-2

S1 = S2 2 + a1

S2 = S3 2 + a2

…..

Sn-1 = an-1

N = an-12n-1+ an-22

n-2+ …+ a12+ a0

= (an-12n-2+ an-22

n-3+ …+ a22 + a1) 2 + a0

= ( (an-12n-3+ an-12

n-4+ …+ a2) 2 + a1) 2 + a0

…..

= ((… (an-12+ an-2) 2 + … + a2) 2 + a1)2 + a0

Verso un algoritmo di conversione da b=2

N = (an-1 an-2…a1a0)2

= ((… ( (an-1) 2+ an-2) 2 + … + a2) 2 + a1)2 + a0

…..

Sn-2 = an-2 + 2Sn-1

Sn-3 = an-3 + 2Sn-2

Si = ai + 2Si+1

…..

…..

Sn-1 = an-1

Algoritmo di conversione: binario in decimale

N = (an-1 an-2…a1a0)2

S0 =N

N = ((… ( ( an-1) 2+ an-2) 2 + … + a2) 2 + a1)2 + a0

S0 = a0+2S1

N= S0 = S1 2 + a0

Sn-2 = Sn-1 2 + an-2

S1 = S2 2 + a1

S2 = S3 2 + a2

…..

Sn-1 = an-1

Dal bassoverso l’alto:da an-1

a a0 ;da MSD a LSD

LSD=cifra meno significativaMSD=cifra più significativa

Esempio 1

(1 0 1 1 0 1 0 1)2

n=8

S7 = a7 = 1

S6 = a6+2S7 = 0 + 2 = 2

S5 = a5+2S6 = 1 + 4 = 5

S4 = a4+2S5 = 1 + 10 = 11

S3 = a3+2S4 = 0 + 22 = 22

S2 = a2+2S3 = 1 + 44 = 45

S1 = a1+2S2 = 0 + 90 = 90

S0 = a0+2S1 = 1 + 180 = 181

N = (a7 a6 a5 a4 a3 a2 a1a0)2

Sn-1 = an-1

Sn-2 = an-2+2Sn-1

Sn-3 = an-3+2Sn-2

Si = ai+2Si+1

…..

…..

S0 =N

(11101001)2

n=8 S7 = a7 = 1

S6 = a6+2S7 = 1 + 2 = 3

S5 = a5+2S6 = 1 + 6 = 7

S4 = a4+2S5 = 0 + 14 = 14

S3 = a3+2S4 = 1 + 28 = 29

S2 = a2+2S3 = 0 + 58 = 58

S1 = a1+2S2 = 0 + 116 = 116

S0 = a0+2S1 = 1 + 232 = 233

Esempio 2

(11111111)2

n=8 S7 = a7 = 1

S6 = a6+2S7 = 1 + 2 = 3

S5 = a5+2S6 = 1 + 6 = 7

S4 = a4+2S5 = 1 + 14 = 15

S3 = a3+2S4 = 1 + 30 = 31

S2 = a2+2S3 = 1 + 62 = 63

S1 = a1+2S2 = 1 + 126 = 127

S0 = a0+2S1 = 1 + 254 = 255

Esempio 3

Esercizi (continua)

• Quanti bit sono necessari per rappresentare 18?

• Quanti bit sono necessari per rappresentare un intero n?

Riepilogo

• Rappresentazione binaria con n bit

• Algoritmi di conversione bin->dec e dec->bin [P] parr. 1.1, 1.2, 1.3.1

rappresentazione in binario e algoritmi di conversione 20 ... · ai quali è progettato e...

Documents

Transcript of rappresentazione in binario e algoritmi di conversione 20 ... · ai quali è progettato e...