Rappresentazione dell’Informazione Rappresentazione delle informazioni in codice binario Caratteri Naturali e Reali positivi Interi Razionali Rappresentazione del testo Una stringa di bit per ogni simbolo (caratteri maiuscoli, caratteri minuscoli, cifre, ...) ANSI (American National Standards Institute) ha adottato il codice ASCII (American Standard Code for Information Interchange): 7 bit per ogni simbolo + 0 come bit piu’ significativo =un byte Rappresentare numeri Il codice ASCII e’ inefficiente: per rappresentare numeri con n cifre servono n byte Meglio usare metodi che sfruttano la notazione binaria (base 2) Base 2: solo le cifre 0 e 1 invece che 0, 1, ..., 9 (base 10) Base 10 e base 2 Rappresentazione decimale Base 10 cifre da 0 a 9 Sequenza di cifre decimali d k-1 … d1 d0 numero intero ∑j=0…k-1 dj 10j dk-1 x 10 k-1 + … d1 x 10 + d0 Esempio: 102 in base 10 è 1x100 + 0x10 + 2x1 Rappresentazione binaria Base 2 cifre 0 e 1 Sequenza di cifre binarie d k-1 … d1 d0 numero intero (stesso procedimento ma su base 2) ∑j=0…k-1 dj 2j Esempio: 01011012 = 1·25 + 1·23 + 1·22 + 1·20 = 32 + 8 + 4 + 1 = 4510 Rappresentazione binaria Valore minimo di una sequenza di n cifre binarie: 000 … 0 (n volte) = 010 Valore massimo: 1111…111 (n volte) = 2n-1 + 2 n-2 + … + 22 + 21 + 20 = 2n –1 Esempio con n=3: 111 = 22 + 2 + 1 = 7 = 23 -1 Da 0 a 8: 0, 1, 10, 11, 100, 101, 110, 111, 1000 Una proprietà dei numeri binari 1001001= 73 100100 = 36 = 73/2 e questo è il resto Eliminare il bit più a destra corrisponde a dividere per 2 il valore, ed il bit eliminato è il resto Trasformazione di un numero in base 10 a numero binario 125 in binario è 125 125/2=62 62/2=31 31/2=15 15/2=7 7/2=3 3/2=1 1/2=0 resto 1 resto 0 resto 1 resto 1 resto 1 resto 1 resto 1 1111101 rappresenta 62 rappresenta 31 Etc. Esercizio 1 •Scrivere la rappresentazione binaria dei numeri decimali: •30 •36 •15 Esercizio 2 •Scrivere la rappresentazione decimale dei numeri binari: •1000 •1010 •01011 •10111 Correzione degli esercizi •Scrivere la rappresentazione binaria dei numeri decimali: •30 11110 •36 100100 •15 1111 Correzione degli esercizi •Scrivere la rappresentazione decimale dei numeri binari: •1000 8 •1010 10 •01011 11 •10111 23 Somma binaria Somma binaria Colonna per colonna, da destra a sinistra Riporto se la somma su una colonna supera la base Tre cifre binarie (prima riga, seconda riga, riporto), somma =1 se una o tre sono 1, riporto = 1 se almeno due sono 1 Riporto: 1 1 1 1 0 0 0111002 + 1001112 = ----------10000112 1 11 1010011 + 1100011 = ---------10110110 riporti Si vuole quindi costruire un circuito per sommare due numeri binari 10000110 1010011 + 1100011 = ---------10110110 riporti Iniziamo con un circuito che faccia la somma su una colonna Abbiamo tre cifre binarie X, Y, R in input mentre in output vogliamo ottenere la somma S ed il riporto R' Tabella di verità X 0 0 0 0 1 1 1 1 Y 0 0 1 1 0 0 1 1 R 0 1 0 1 0 1 0 1 S 0 1 1 0 1 0 0 1 R' 0 0 0 1 0 1 1 1 Supponiamo di avere i circuiti che calcolano somma e riporto X Y R X Y R S SOMMA R' RIPORTO Possiamo allora combinare i circuiti SOMMA e RIPORTO per ottenere il seguente circuito 1-ADD 1-ADD S X Y R SOMMA R' RIPORTO Il circuito RIPORTO puo` essere realizzato nel seguente modo RIPORTO X R' Y R Basta infatti verificare la corrispondente tabella di verita’ Il circuito SOMMA naturalmente puo' pure essere realizzato (vedi dispensa). A questo punto componendo K circuiti 1-ADD e` possibile realizzare un circuito K-ADD che somma due numeri binari di K cifre. Vediamo l'esempio della somma di due numeri binari di 4 cifre. Somma di numeri di 4 bit Y3 Y2 Y1 Y0 riporto R 3 finale inutile X3 X2 X1 X0 R2 1-add R1 1-add S3 S2 0 0 riporto R0 1-add S1 risultato 1-add S0 iniziale 0 1 0 1 0 1 1-add 1-add 0 1 1 1 1 1-add 1 1 0 1 0 Esempio 0 1-add 0111 + 0110 = -----1101 Attenzione Si e` trascurato il problema del cosiddetto overflow, cioe’ il risultato e’ troppo grande per essere contenuto nei bit disponibili. Per esempio: 0111 + 1110 = -----10101 Esercizi 11011+ 1100 --------- 11111+ 1 --------- Correzioni 1 11011+ 1100 --------100111 11111 11111+ 1 --------100000 Rappresentazione dei reali Reali in notazione binaria bk-1 bk-2 … b2 b1 b0 , b-1 b-2 … bk-1 x 2 k-1 + bk-2 x 2 k-2 +… + b2 x 22 + b1 x 2 + b0 x 20 + b-1 x 2-1 + b-2 x 2-2 +… Da decimale a binario: Per la parte intera, come sappiamo fare (metodo delle divisioni) REALE--> BINARIO cosa significa una parte frazionaria binaria: .1101001 2-1+ 2-2 + 2-4 + 2-7 .1101001 2-1 2-2... 1.101001 20 2-1....... moltiplicarlo per 2 significa spostare il punto di un posto a destra Se abbiamo un valore decimale in base 10: 0.99 come troviamo la sua rappresentazione in base 2? Ragioniamo come segue: Supponiamo che .99 = .b1b2b3...bk (binario) Allora 2 .99 = 1.98 = b1.b2b3...bk Quindi b1 è 1 e .98 è rappresentato da .b2b3...bk Per trovare la rappresentazione binaria di un decimale lo moltiplichiamo per 2 ed osserviamo se 1 appare nella parte intera: rappresentazione binaria di .592= 1.18 .182= 0.36 .362= 0.72 .59 .722= 1.44 .442= 0.88 .100101..... .882= 1.76 ....... dipende da quanti bit abbiamo Esempio 18.59 18 10010 (metodo della divisione per 2) .59 .100101...(metodo della moltiplic. per 2) 10010.100101.... Esercizi Convertire i seguenti numeri binari in formato decimale: 11,01 101,111 10,1 Esprimere i seguenti valori in notazione binaria: 4.5 2.75 Eseguire le seguenti somme binarie: 1010,001+1,101 111,11+0,01 Correzione degli esercizi Convertire i seguenti numeri binari in formato decimale: 11,01 3 +1/4 = 13/4 = 3.25 101,111 5 + 7/8 = 47/8 = 5.87 10,1 2.5 Esprimere i seguenti valori in notazione binaria: 4.5 100,1 2.75 10,11 Eseguire le seguenti somme binarie: 1010,001 + 1,101 1011,110 111,11 + 0,01 1000,00 Rappresentazione degli interi Notazione in complemento a 2 n bit per la notazione Nella realta’ n=32 Per comodita’ noi supponiamo n=4 Numeri positivi 0 si rappresenta con 4 zeri 0000 1 0001, 2 0010 e cosi’ come gia’ visto fino al massimo positivo rappresentabile 0111 7 Numeri negativi -1 si rappresenta con 4 uni 1111 -1 -2 -> 1110, -3 1101 fino al minimo negativo rappresentabile 1000 -8 Gli interi rappresentabili con n bit [-2n-1 , 2n-1 -1] Nell’esempio [-24-1,24-1-1]=[-8,7] Complemento a due su 3 e 4 bit Complemento a due Bit piu’ a sinistra: segno (0 per positivi, 1 per negativi) Confrontiamo k e –k: da destra a sinistra, uguali fino al primo 1 incluso, poi una il complemento dell’altra Esempio (4 bit): 2=0010, -2=1110 Complemento a due: decodifica Se bit di segno =0 positivo, altrimenti negativo Se positivo, basta leggere gli altri bit Se negativo, scrivere gli stessi bit da destra a sinistra fino al primo 1, poi complementare, e poi leggere Es.: 1010 e’ negativo, rappresenta 110 (6), quindi -6 Da k a -k Metodo alternativo: codifica e decodifica Intero positivo x complemento a due su n bit: se x 2n-1-1 scrivo (x)2 , altrimenti non e’ rappresentabile Intero negativo –x complemento a due su n bit: se –x -2n-1 calcolo 2n+(-x)=y e scrivo (y)2 Esempio: n=4, –x=-3 y=24-3=16-3=13 (13)2=1101 Compl. a due positivo (0 = bit + significativo) decimale: decodifica dal binario Esempio: n=4, x=5, (5)2=0101, x=8>23-1=7 Esempio: n=4, 0111=(7)2 Compl. a due negativo (1 = bit + significativo)decimale: decodifico dal binario a decimale, ottengo y e poi sottraggo y-2n Esempio 1010 = (10)2 10-16=-6 Somma in complemento a due Si utilizza il solito metodo Anche per sottrazione basta avere i circuiti per somma e complemento Es. (4 bit): 7-5 = 7 +(-5) = 0111 + 1011 = 0010 5 = 0101 -5 = 1011 L’eventuale n+1-simo bit generato a sinistra dal riporto deve essere troncato Esempio 0111+1011=10010 7 -5 2 Esempi di somme Overflow Si sommano due numeri positivi tali che il risultato e’ maggiore del massimo numero positivo rappresentabile con i bit fissati (lo stesso per somma di due negativi) Si ha un errore di overflow se: Sommando due positivi si ottiene un numero che inizia per 1: 0101+0100=1001, 5+4=-7 Sommando due negativi viene un numero che inizia per 0: 1011+1100= (1)0111, -5+(-4)= 7 Nei computer c’e’ overflow con valori superiori a 2.147.483.647= 231 Esercizi Da complemento a 2 a base 10: 00011, Da base 10 a complemento a 2 su 8 bit: 6, 01111, 11100, 11010, 00000, 10000 -6, 13, -1, 0 Numero piu’ grande e piu’ piccolo per la notazione in complemento a 2 su 4, 6, 8 bit Correzioni Da complemento a 2 a base 10: Da base 10 a complemento a 2 su 8 bit: 00011 3, 01111 15, 11100 -4, 11010 -6, 00000 0, 10000 -16 6, -6, 13, -1, 0 00000110, 11111010, 00001101, 11111111, 00000000 Numero piu’ grande e piu’ piccolo per la notazione in complemento a 2 su 4, 6, 8 bit Numero piu’ piccolo Numero piu’ grande -2n-1 (n=6 -25 = -32) 2n-1 -1 (n=6 25-1 = 31) Notazione in eccesso n bit 2n possibili configurazioni binarie ordinate da n zeri a n uni Supponiamo per comodita’ che n=4 0 e’ rappresentato da un 1 seguito da n-1 zeri: 01000 n zeri codifica -2n-1: - 2 4-1 = -8 0000 (0-8 = -8) n uni codifica 2n-1 – 1: 2 4-1-1= 7 1111 (15-8 = +7) n bit: notazione in eccesso 2n-1 rispetto al corrispondente binario Es.: 4 bit, notazione in eccesso 8 Notazione in eccesso 8 Esercizi Da eccesso 8 a decimale: 1110, Da decimale a eccesso 8 5, 0111, 1000,0010, 0000, 1001 -5, 3, 0, 7, -8 Numero piu’ grande e piu’ piccolo per la notazione in eccesso 8, 16, 32 Correzioni (1) Da eccesso 8 a decimale: 14-8=6 0111 7-8=-1 1000, 0010, 0000, 1001 0, -6, -8, 1 1110 Da decimale a eccesso 8 5+8 13 1101 -5 -5+8 3 0011 3, 0, 7, -8 1011, 1000, 1111, 0000 5 Correzioni (2) Numero piu’ grande e piu’ piccolo per la notazione in eccesso 8, 16, 32 8: 8=2n-1 n=4 numero piu’ piccolo: -8, numero piu’ grande 7 eccesso 16: 16=2n-1 n=5 numero piu’ piccolo: -16 numero piu’ grande 15 eccesso 32: 32=2n-1 n=6 numero piu’ piccolo: -32 numero piu’ grande 31 eccesso Rappresentazione dei numeri reali (floating point) Rappresentazione dei reali in un computer Bisogna rappresentare la posizione della virgola Notazione in virgola mobile (floating point): suddivisione in tre campi Esempio con 8 bit: da sinistra: primo bit segno (0 pos., 1 neg.) Tre bit per esponente Quattro bit per mantissa Partendo V = 0.mantissa * 2^{exp} Da floating point a decimale 01101011 1. 2. Segno: 0 positivo, 1 negativo Anteporre 0, alla mantissa 01101011 0,1011 3. Interpretare l’ esponente come un numero in eccesso su tre bit (eccesso 4) 1106, 4. 6-4 =2 Spostare la virgola della mantissa della quantita’ ottenuta dall’esponente a dx se il numero positivo a sx se e’ negativo 0,1011 10,11 5. Tradurre da binario a decimale mettendo il segno a seconda del bit piu’ significativo del foating point 10,11 2,75 6. Aggiungere il segno: +2,75 Altro esempio di decodifica 10111100 Segno: 1 negativo Mantissa: 1100 0,1100 Esponente: 011 -1 in notazione in eccesso 4 virgola a sinistra di 1 posto 0,01100 (3/8, infatti 2x2^(-2) + 2x2^(-3) ) Numero decimale: -3/8 = -0,375 Da decimale a floating point 1. Da decimale a binario: 0.375 (=3/8) 0,011 2. La mantissa si ottiene dall’1 piu’ a sinistra completando con zeri i quattro bit 1100 3. Contare di quante posizioni si deve spostare la virgola per passare da 0,mantissa a 0,011. Il numero e’ negativo se la virgola va a sinistra 1 bit a sinistra -1 4. Codificare il numero ottenuto in eccesso 4 -1 +4= 3 011 5. Mettere nel bit piu’ significativo il bit di segno 00111100 Errori di troncamento Codifichiamo 2 + 5/8= 2.625 in 8 bit Binario: 10,101 Mantissa: vorremmo scrivere 10101, ma abbiamo solo 4 bit 1010, tronco il bit meno significativo Esponente: 110 (2) Risultato: 01101010, che rappresenta 2.5 e non 2 + 5/8 Infatti: 0,1010 110 (2) 10,10 2+ ½ = 2.5 Esercizi Decodifica: 01001010, 01101101, 00111001 Codifica: 2.75, 5.25 Qual e’ il piu’ grande tra 01001001 e 00111101? Correzioni (1) Decodifica: 0 100 1010 5/8 = 0.625 Infatti: 0 100 1010 --> positivo 0,1010 100 --> 4-4=0 0.1010 1/2+1/8= 5/8 = 0.625 --> 0.625 Codifica: 2.75 --> 0 110 1011 Infatti: binario 10,11 1011 --> 2 posti a dx 2 --> 110 0 110 1011 Correzioni (2) Decodifica: 0 110 1101 3 + 1/4 = 13/4 = 3.25 0 011 1001 9/32 Codifica: 5.25 0 111 1010 Qual e’ il piu’ grande tra 01001001 e 00111101? Il primo e’ 0.56, il secondo e’ 0.40 il piu’ grande e’ il primo