Codiﬁca binaria dell informazione - Intranet...

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE

Codifica binaria dell’informazione

Marco D. Santambrogio – [email protected] Ver. aggiornata al 29 O0obre 2013


Info di servizio

•  Doodle su demo 1mo compitino http://tinyurl.com/infob1314-demo1mo

•  Correzione demo http://tinyurl.com/infob1314-cdemo1mo

2


Un obiettivo per domarli tutti…

3


Uno dei problemi…

4


Obiettivi

•  Rappresentazione dell’informazione •  Da decimale a binario

§ Contiamo con i numeri binari •  Limiti della rappresentazione •  Complemento a due

5


Codifica binaria

6

Claude Shannon nel 1948 nel paper: “A Mathematical Theory of Communication”

Chi ha “inventato” il bit?


Codifica binaria

•  Alfabeto binario: usiamo dispositivi con solo due stati •  Problema: assegnare un codice univoco a tutti gli oggetti

compresi in un insieme predefinito (e.g. studenti)

•  Quanti oggetti posso codificare con k bit: §  1 bit ⇒ 2 stati (0, 1) ⇒ 2 oggetti (e.g. Vero/Falso) §  2 bit ⇒ 4 stati (00, 01, 10, 11) ⇒ 4 oggetti §  3 bit ⇒ 8 stati (000, 001, …, 111) ⇒ 8 oggetti §  … §  k bit ⇒ 2k stati ⇒ 2k oggetti

•  Quanti bit mi servono per codificare N oggetti: §  N ≤ 2k ⇒ k ≥ log2N ⇒ k = ⎡log2N⎤ (intero superiore)

•  Attenzione: ipotesi implicita che i codici abbiano tutti la stessa lunghezza

7


Esempio di codifica binaria

•  Problema: assegnare un codice binario univoco a tutti i giorni della settimana

•  Giorni della settimana: §  N = 7 ⇒ k ≥ log27 ⇒ k = 3

•  Con 3 bit possiamo ottenere 8 diverse configurazioni: §  Ne servono 7, quali utilizziamo? §  Quale configurazione associamo a quale

giorno?

•  Attenzione: ipotesi che i codici abbiano tutti la stessa lunghezza

8


I giorni della settimana in binario (1)

3 bit 8 “gruppi”


Lunedì

Martedì

Mercoledì

Giovedì

Venerdì

Sabato

Domenica

Lunedì Martedì

Mercoledì Giovedì

Venerdì Sabato

Domenica


Lunedì

Martedì Mercoledì Giovedì

Venerdì

Sabato Domenica

Lunedì Martedì

Mercoledì

Giovedì

Venerdì

Sabato Domenica

9


I giorni della settimana in binario (2)



Lunedì

Martedì

Mercoledì

Giovedì

Venerdì

Sabato

Domenica

Lunedì

Martedì

Mercoledì

Giovedì

Venerdì

Sabato

Domenica


Lunedì

Martedì

Mercoledì

Giovedì

Venerdì

Sabato

Domenica

Lunedì Martedì

Mercoledì

Giovedì

Venerdì

Sabato Domenica

10


Stampa dei caratteri

11


Quale è il codice ASCII di ‘a’?

12

Siamo sicuri?

Ma quindi, quanto vale ‘a’? 97, 353, 609 97, 353=97+256, 609=353+256=97+256+256

97 = 97 + 256*0 353 = 97+256*1 609 = 97+256*2


97+256*i… quindi…

•  Quanti caratteri ci sono? §  256

•  Con quanti bit rappresento 256 numeri? §  log2256 = log228 = 8

13


Codifica binaria dei caratteri

•  Quanti sono gli oggetti compresi nell’insieme? §  26 lettere maiuscole + 26 minuscole ⇒ 52 §  10 cifre §  Circa 30 segni d’interpunzione §  Circa 30 caratteri di controllo (EOF, CR, LF, …) circa 120 oggetti complessivi ⇒ k = ⎡log2120⎤ = 7

•  Codice ASCII: utilizza 7 bit e quindi può rappresentare al massimo 27=128 caratteri §  Con 8 bit (= byte) rappresento 256 caratteri (ASCII esteso) §  Si stanno diffondendo codici più estesi (e.g. UNICODE) per

rappresentare anche i caratteri delle lingue orientali

14


ASCII su 7 bit 0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

010 sp ! " # $ % & ' ( ) * + , -‐ . / 011 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 100 @ A B C D E F G H I J K L M N O 101 P Q R S T U V W X Y Z [ \ ] _ 110 ̀ a b c d e f g h I j k l m n o 111 p q r s t u v w x Y z { | } ~ canc

15


bit, Byte, KiloByte, MegaByte, …

bit = solo due sta9, “0” oppure “1”. Byte = 8 bit, quindi 28 = 256 sta9 KiloByte [KB] = 210 Byte = 1024 Byte ~ 103 Byte MegaByte [MB] = 220 Byte = 1'048'576 Byte ~ 106 Byte GigaByte [GB] = 230 Byte ~ 109 Byte TeraByte [TB] = 240 Byte ~ 1012 Byte PetaByte [PB] = 250 Byte ~ 1015 Byte ExaByte [EB] = 260 Byte ~ 1018 Byte

16


Da Hobbit a Hobbyte

17


Da base 10 a base 2

•  Dato un numero K rappresentato in base dieci, la sua rappresentazione in base due sarà del tipo bn bn-1bn-2 … b1b0 §  bi: cifra binaria

•  Per convertire un numero in base dieci nel corrispondente in base due si devono trovare i resti delle divisioni successive del numero K per due

18


Da base 10 a base 2

•  Esempio: il numero 610:

6/2 = 3 resto 0 3/2 = 1 resto 1 1/2 = 0 resto 1

•  Leggendo i resti dal basso verso l’alto, si

ha che la rappresentazione binaria del numero 610 è 1102

•  Per una corretta verifica basta riconvertire il risultato alla base 10 §  Cioè, calcolare 1 x 22 + 1 x 21 + 0 x 20

19


Da base 10 a base 2

•  Perché 1102 = 610 ?

6/2 = 3 resto 0 0 x 20 + 3/2 = 1 resto 1 1 x 21 + 1/2 = 0 resto 1 1 x 22

= 6 1 x 22 + 1 x 21 + 0 x 20 = 1 x 21 + 1 x 20 con resto 0 2 1 x 21 + 1 x 20 = 1 x 20 con resto 1 2 1 x 20 = 0 con resto 1 2

20


Da base 10 a base 2

•  Esempio: il numero 34510:

345/2 = 172 resto 1 172/2 = 86 resto 0 86/2 = 43 resto 0 43/2 = 21 resto 1 21/2 = 10 resto 1 10/2 = 5 resto 0 5/2 = 2 resto 1 2/2 = 1 resto 0 1/2 = 0 resto 1

•  Leggendo i resti dal basso verso l’alto

§  Larappresentazione binaria del numero 34510 è 1010110012

21


Altre basi: ottale, esadecimale

•  Sistema ottale §  Utilizza una notazione posizionale basata su

otto cifre (0,1,…,7) e sulle potenze di 8 §  Esempio: 1038 = 1 x 82 + 0 x 81 + 3 x 80 = 67

•  Sistema esadecimale §  Utilizza una notazione posizionale basata su

sedici cifre (0,1,…,9,A,B,C,D,E,F) e sulle potenze di 16

§  Esempio: 10316 = 1 x 162 + 0 x 161 + 3 x 160 = 259 §  Esempio: AC416 = 10 x 162 + 12 x 161 + 4 x 160 = 2756

22


Operazioni su numeri binari

•  Vediamo solo il caso della addizione nella codifica binaria: §  Si mettono in colonna i numeri da sommare §  Si calcola il riporto ogni volta che la somma

parziale supera il valore 1

•  Addizione: 0 + 0 = 0 con riporto 0 0 + 1 = 1 con riporto 0 1 + 0 = 1 con riporto 0 1 + 1 = 0 con riporto 1

23


Operazioni su numeri binari

•  Addizione: 0 + 0 = 0 con riporto 0 0 + 1 = 1 con riporto 0 1 + 0 = 1 con riporto 0 1 + 1 = 0 con riporto 1

•  Esempi:

1 + 1 = 1 0

1 0 1 + 1 1 = 1 0 0 0

1 0 1 1 0 1 0 1 + 1 0 0 0 1 1 0 = 1 1 1 1 1 0 1 1

1 1 1 + 1 1 = 1 0 1 0

24


Codici a lunghezza fissa

•  Se si usa un numero prestabilito di cifre si ha un codice a lunghezza fissa

•  In questo modo si pone anche un limite al numero massimo rappresentabile

•  Esempio: qual è il numero più grande rappresentabile con 4 cifre? §  In base 10: 9999 §  In base 2: 1111 (=1510) §  In base 16: FFFF (=6553510) §  In base 8: 7777 (=409510)

25


Il fattoriale

•  Dato n, intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei primi n numeri interi positivi minori o uguali di quel numero. In formule

•  Nota: §  0! = 1 §  1! = 1 §  2! = 2, 3! = 6,…

26


Il fattoriale: codice

27


Proviamo ad eseguirlo…

28

WAT



•  Numeri maggiori di quello massimo rappresentabile causano problemi di overflow §  Ovvero per essere rappresentati richiedono più

cifre di quelle a disposizione

•  Esempio: 4 cifre §  In base 10: 9999 + 1 = 1000010 §  In base 2: 1111 + 1 = 100002 (=1610) §  In base 16: FFFF + 1 = 1000016 (=6553610) §  In base 8: 7777 + 1 = 100008 (=409610)

29



•  In generale, con N cifre a disposizione e base b il più grande numero (intero positivo) rappresentabile si può esprimere come

bN – 1 •  Esempio: N=4

§  In base 10: 9999 = 104 - 1 §  In base 2: 1111 = 24 - 1 §  In base 16: FFFF = 164 - 1 §  In base 8: 7777 = 84 - 1

30



•  Esempio di overflow nel sistema binario dovuto a operazioni aritmetiche: §  5 + 4 = 9 (in sistema decimale) §  abbiamo usato solo una cifra decimale per il

risultato

•  Ricordiamo: 510 = 1012, 410 = 1002

1 0 1 + 1 0 0 = 1 0 0 1

(in sistema binario)

Errore: overflow (non può essere codificato 910 = 10012 con tre bit)

31


Rappresentazione dei numeri

•  Possiamo rappresentare i numeri usando un numero variabile di cifre (che dipende dal valore che si vuole rappresentare) §  Come? Introduciamo un simbolo speciale che indica

dove termina la rappresentazione di un numero e inizia quella del numero successivo

§  Esempio: 1001#11#1 (codice a lunghezza variabile, # separatore)

•  Esistono anche “codici di espansione”, che permettono di definire dei codici a lunghezza variabile senza far uso del carattere di separazione

32


Rappresentazione dei numeri

•  In realtà, una semplice codifica binaria come quella discussa fino ad ora non è sufficiente, per due motivi: §  Numeri negativi §  Numeri con la virgola

•  Per questi numeri vengono utilizzate delle rappresentazioni differenti §  Per esempio “complemento a due” per

rappresentare i numeri negativi

33


Numeri negativi

•  Si può pensare di usare un bit per il segno §  “0” identifica “+” §  “1” identifica “-”

•  Gli altri bit vengono usati per codificare il valore assoluto (modulo) del numero

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

[-22+1, 22-1] [0, 23-1]

34


Numeri negativi - problemi

•  Con 3 bit avremo:

000 +0 001 +1 010 +2 011 +3 100 -0 101 -1 110 -2 111 -3

" Problemi: n  Il numero 0 ha due

rappresentazioni n  Per l’operazione di

somma si deve tener conto dei segni degli addendi

0 0 1 0 + (+2) 1 0 1 1 = (-3) 1 1 0 1 (-5 ERRATO)

35


Il fattoriale: codice

36



37

int sono interi con segno


Il fattoriale: unsigned int

38



39


Numeri negativi: Complemento a due

•  Il bit più significativo rappresenta il segno del numero: 0 per i numeri positivi e 1 per i numeri negativi

•  La rappresentazione di un numero positivo si ottiene codificando il valore assoluto del numero con i bit restanti

•  La rappresentazione di un numero negativo si ottiene in tre passi: §  Si rappresenta in complemento a due il numeri positivo

con lo stesso valore assoluto del numero negativo da codificare

§  Si invertono tutti i bit in tale rappresentazione (0→1,1→0)

§  Si somma uno al risultato ottenuto al passo precedente

40


Complemento a due

•  Esempio (con 4 bit a disposizione): §  La codifica di +5 è 0101 §  La codifica del numero –5 avviene in tre passi:

•  La rappresentazione in complemento a due di +5 è 0101

•  Invertendo tutti i bit si ottiene 1010 •  Sommando 1 si ottiene 1011, la rappresentazione

in complemento a due di -5

41


Complemento a due

•  Per ottenere un numero con segno data la sua rappresentazione in complemento a due: §  Se il primo bit è 0 il numero è positivo: per

calcolarne il valore assoluto si esegue la conversione da binario a decimale

§  Se il primo bit è 1 il numero è negativo: •  Si ignora il primo bit •  Si invertono i restanti bit •  Si converte il numero da binario a decimale •  Si somma uno al numero ottenuto per ottenere il

valore assoluto del numero negativo

42


Complemento a due

•  Esempio: 1011 §  Si esclude il primo bit §  Invertendo 011 si ottiene 100 che è codifica di 4 §  Va aggiunto 1 per ottenere il valore assoluto 5 §  Il risultato è quindi -5

43


Complemento a due

•  Con 3 bit avremo:

000 +0 001 +1 010 +2 011 +3 100 -4 101 -3 110 -2 111 -1

" Esempi di addizione: 0 0 1 0 + (+2) 1 0 1 1 = (-5) 1 1 0 1 (-3) 0 1 1 1 + (+7) 1 0 1 1 = (-5) 0 0 1 0 (+2) Nel secondo esempio, l’overflow è ignorato

44


Exe 1: Codifica dell’informazione

•  Quanti bit si devono utilizzare per rappresentare 300 informazioni distinte?

•  Quanti byte occupa la parola “psicologia” se la si codifica utilizzando il codice ASCII?

•  Dati 12 bit per la codifica, quante informazioni distinte si possono rappresentare?

45


Exe 2: Codifica dei suoni

•  Quanto spazio occupa un suono della durata di 30 secondi campionato a 100 Hz (100 campioni al secondo), in cui ogni campione occupa 4 byte?

46


Exe 3: Codifica dei numeri

•  Codificare il numero 17510 nella corrispondente rappresentazione binaria

•  Ordinare in modo crescente i seguente numeri: 10510 , 128 , 1001100002 , 1001110

•  Codificare il numero negativo –1510 nella rappresentazione in complemento a due

47


Exe 4: Codifica delle immagini

•  Quanti bit occupa un’immagine di 100 x 100 pixel in bianco e nero?

•  Quanti byte occupa un’immagine di 100 x 100 pixel a 256 colori?

•  Se un’immagine a 16777216 di colori occupa 2400 byte, da quanti pixel sarà composta?

48


Fonti per lo studio + Credits

•  Fonti per lo studio §  Informatica arte e mestiere, S. Ceri, D. Mandrioli, L.

Sbattella, McGrawHill •  Capitolo 11

§  Introduzione ai sistemi informatici, D. Sciuto, G. Buonanno, L. Mari, 4a Ed, McGrawHill •  Capitolo 2

§  The Art & Craft of Computing, S. Ceri, D. Mandrioli, L. Sbattella, Addison-Wesley •  Capitolo 13

•  Credits §  P. Spoletini §  J. Sproston

49

Codiﬁca binaria dell informazione - Intranet...

Documents

Transcript of Codiﬁca binaria dell informazione - Intranet...