Rappresentazione dell'informazione: concetti e codifica dei dati

Corso di Informatica

Corso di Laurea Triennale in Matematica Rappresentazione dell'Informazione Rev. 2009 by Mario AlvianoDispensa del corso di Informatica - CdL in Matematica A.A. 2009/2010 Pag. 2 di 15

Sommario

Rappresentazione dell'informazione. 3 Concetti introduttivi: informatica, algoritmo, programma 3 Introduzione alla rappresentazione dell'informazione 4 Cenni sulla conversione di base 5 Codifica dei numeri interi 8 Codifica dei numeri non interi 9 Codifica dei caratteri 12 Codifica di dati multimediali. 13 Liberamente distribuibile secondo i termini della licenza GNU Free DocumentRappresentazione dell'informazione

L'informatica è la scienza che studia i modi in cui l'informazione può essere rappresentata e manipolata in un sistema informatico (un computer). Per manipolazione intendiamo elaborazione: lo scopo dell'informatica è elaborare dati, automaticamente, per raggiungere un determinato obiettivo. Per meglio chiarire questo concetto consideriamo un programma che determini l'area di un quadrato data la lunghezza del lato. In questo caso, il programma elaborerà l'informazione "lunghezza del lato" al fine di determinare l'area del quadrato, ad esempio applicando la nota formula "lato x lato".

L'informazione può essere elaborata solo se rappresentata in modo opportuno. Ad esempio, è possibile leggere un libro solo se scritto in un linguaggio noto, ovvero se i "concetti" (le informazioni) che contiene sono rappresentate in modo comprensibile al lettore. Allo stesso modo, affinché un computer possa elaborare delle informazioni, queste devono essere rappresentate secondo determinate regole. L'insieme delle regole che definiscono come un'informazione debba essere rappresentata prende il nome di codifica. Nel seguito approfondiremo questi concetti e discuteremo brevemente le codifiche delle informazioni fondamentali, concentrandoci in particolare sulla rappresentazione dei numeri (interi e non).

Concetti introduttivi: informatica, algoritmo, programma

Per informazione intendiamo una notizia o un dato che consente di avere conoscenza di fatti o situazioni. Ad esempio, un'informazione può essere la lunghezza del lato di un quadrato.

L'informatica, come già detto, è la scienza che studia la rappresentazione e l'elaborazione dell'informazione. L'elaborazione è volta alla risoluzione di un problema di interesse, che definisce le informazioni in input e le informazioni che dovranno essere fornite come risposta (l'output). Ad esempio, per il problema del calcolo dell'area del quadrato descritto sopra, l'input è costituito dalla lunghezza del lato del quadrato, e l'output che ci aspettiamo è l'area del quadrato.

L'elaborazione delle informazioni consiste in una sequenza determinata di operazioni eseguite sui dati di partenza (l'input). L'insieme di queste operazioni viene detto algoritmo. Più formalmente, un algoritmo è una sequenza di operazioni che risolvono un problema. In generale, un problema può essere risolto da diversi algoritmi. Ad esempio, il problema del calcolo dell'area di un quadrato può essere risolto dai seguenti algoritmi:

1. Sia L la lunghezza del lato del quadrato fornito in input; restituisci L×L.
2. Sia L la lunghezza del lato del quadrato fornito in input; restituisci L2.

Come ogni altra informazione, un algoritmo può essere compreso (o meglio eseguito) dal computer solo se rappresentato in modo opportuno per mezzo di un programma. Per questo motivo si dice che un programma implementa un algoritmo, ad evidenziare il fatto che un programma non è altro che una rappresentazione di un algoritmo che un computer può eseguire. Come un problema può essere risolto da diversi algoritmi, un algoritmo può essere implementato da diversi programmi. Liberamente distribuibile secondo i termini della licenza GNU Free DocumentIntroduzione alla rappresentazione dell'informazione

L'idea fondamentale alla base della rappresentazione dell'informazione è il BIT (Binary digiT, ovvero cifra digitale). Il BIT costituisce l'unità minimale di rappresentazione in quanto può rappresentare uno di due valori: 0 oppure 1. La semplicità del BIT ne consente una facile e naturale rappresentazione in un calcolatore elettronico. Potendo assumere solo due valori, infatti, un BIT può essere associato alla presenza/assenza di corrente elettrica. D'altro canto, potendo assumere solo i valori 0 e 1, le uniche informazioni rappresentabili da un BIT sono quelle a due valori. Ad esempio, con un BIT possiamo rappresentare lo stato di un interruttore, ON oppure OFF, associando 1 al primo stato e 0 al secondo. Lo stato di un interruttore ha infatti un dominio di soli due valori, ON e OFF appunto. In modo simile possiamo distinguere fra giorno e notte. Non potremmo invece rappresentare la stagione in cui ci troviamo. Questo tipo d'informazione ha infatti un dominio di quattro elementi: primavera, estate, autunno e inverno. In questi casi possiamo combinare più BIT allo scopo di rappresentare informazioni più complesse. Ad esempio, per rappresentare una stagione sono sufficienti 2 BIT:

Rappresentazione della Stagione con BIT

1º BIT 2º BIT Stagione 0 0 Primavera 0 1 Estate 1 0 Autunno 1 1 Inverno Quindi, seguendo questa rappresentazione, per indicare che ci troviamo in autunno useremo la coppia di BIT (1,0).

Rappresentazione del Giorno della Settimana con BIT

Per rappresentare un giorno della settimana 2 BIT non bastano, ma 3 sono sufficienti. Un possibile schema di rappresentazione è il seguente:

1º BIT 2º BIT 3º BIT Giorno della settimana 0 0 0 Lunedì Martedì 0 0 1 0 1 0 Mercoledì 0 1 1 Giovedì 1 0 0 Venerdì 1 0 1 Sabato 1 0 Domenica 1 1 1 1 NON USATO Seguendo questo schema, la tripla (0,1,0) è usata per indicare il giorno Mercoledì. Visto che i BIT possono assumere due soli valori, 0 oppure 1, una coppia, una tripla e più in generale una n-pla sono generalmente rappresentate come successioni di zeri e di uno, omettendo le virgole e le parentesi. Quindi, per indicare Liberamente distribuibile secondo i termini della licenza GNU Free DocumentSabato useremo 101, mentre con 011 indicheremo Giovedì. Come è possibile osservare dallo schema, una delle 8 combinazioni (111) dei 3 BIT è di troppo. I giorni della settimana sono infatti 7. In questi casi le combinazioni in eccesso non saranno utilizzate in quanto non significative.

Combinazioni di BIT e Dominio di Valori

In generale, N BIT possono assumere 2^ combinazioni diverse, ognuna delle quali può essere associata a un valore che una specifica informazione può assumere. Ne consegue che con N BIT possiamo rappresentare informazioni con un dominio di al più 2^ valori. Viceversa, per rappresentare un'informazione con un dominio di M valori avremo bisogno di almeno minNEN2 2 M BIT. Ad esempio, per rappresentare un'informazione che può assumere uno di 57 valori diversi avremo bisogno di almeno 6 BIT. Infatti, 26 = 64 > 57, mentre 25 = 32 < 57.

BYTE e i suoi Multipli

Particolarmente importanti sono le sequenze di 8 BIT, comunemente chiamate BYTE. Con un BYTE possiamo rappresentare informazioni con dominio di al più 28 = 256 elementi. Generalmente, informazioni più complesse (ovvero con dominio di più di 256 elementi) vengono rappresentate con successioni di BYTE. Quindi, in informatica difficilmente si troveranno informazioni codificate in 10 BIT, preferendo in questi casi l'uso di 2 BYTE (ovvero 16 BIT).

Come per ogni altra unità di misura, i multipli del BYTE prendono nomi specifici. Generalmente i multipli delle unità di misura seguono le potenze di 10, che è la base che comunemente adottiamo. In informatica la base più comune è invece la 2 (come le combinazioni esprimibili da un BIT), e pertanto anche i multipli seguiranno questa base. Per non stravolgere il nostro modo di pensare, le potenze di 2 scelte per i multipli del BYTE sono quelle che più si avvicinano alle potenze di 10. In particolare, i primi multipli del BYTE sono KiloByte (KB), MegaByte (MB), GigaByte (GB), TeraByte (TB). Il loro valore è il seguente:

• 1 KB = 210 × 1 BYTE = 1024 × 1 BYTE ~ 1000 ×1 BYTE = 103 BYTE
• 1 MB = 210 × 1 KB = 1024 ×1 KB ~1000 ×1KB ~ 10° BYTE
• 1 GB =210x1 MB = 1024 × 1 MB ~ 1000 ×1MB ~ 109 BYTE
• 1 TB = 210 x 1 GB = 1024 × 1 GB ~ 1000 ×1GB ~ 1012 BYTE

Cenni sulla conversione di base

Molte informazioni sono costituite da un numerale associato a un nome; in questi casi, il numerale indica in modo preciso la quantità numerica di qualcosa, costituendo quindi un'importante parte dell'informazione. Ad esempio, nell'informazione "tre mele", il numerale tre indica la quantità di mele. Per ovvie ragioni siamo abituati a pensare ai numeri in base 10, quella che quotidianamente utilizziamo per esprimerci e far di conto. Tuttavia, sebbene per ragionare con i numeri abbiamo bisogno di rappresentarli in qualche base, il concetto di numero è indipendente dalla base di rappresentazione. Inoltre, quando scriviamo un numero, non posizioniamo le cifre a caso, ma diamo un peso a ogni cifra a seconda della sua posizione. Questo tipo di rappresentazione prende il nome di notazione posizionale (e anche questa non dipende dalla base adottata). Nella notazione posizionale la posizione di una cifra in un numero indica il suo peso in potenze della base. Ad esempio, 123 in base 10 indica un numero composto da

• 3 unità, ovvero 3 × 10°,
• 2 decine, ovvero 2 × 101,
• 1 centinaia, ovvero 1 × 102.

Quindi, 123 in base 10 indica il numero 3 × 10° + 2 × 101 + 1 × 102 + = 123. Similmente, 110010 in base 2, indicato anche come [110010]2, è una rappresentazione del numero [110010]2 = 0x2° +1x21 +0x22 +0x23 +1x24 +1x25 =0+2+0+0+16+32=50.

Conversione da Base 2 a Base 10

L'ultimo esempio dovrebbe chiarire come convertire un numero da base 2 a base 10: si moltiplica ogni cifra per il suo peso e quindi si somma il tutto. In modo simile, è possibile convertire in base 10 un numero espresso in una base qualsiasi B. Il peso della cifre si ottiene nel modo seguente:

• La cifra meno significativa ha peso Bº (e quindi sarà 1 per tutte le basi).
• La prima cifra a sinistra della cifra meno significativa ha peso B1.
• La seconda cifra a sinistra della cifra meno significativa ha peso B2. .
• …
• La n-esima prima cifra a sinistra della cifra meno significativa ha peso B".
• …

Conversione da Base 10 a Base B

La conversione inversa, ovvero da base 10 a una base qualsiasi B, si ottiene dividendo ripetutamente il numero per B. I resti rappresentano cifre via via più significative. Chiaramente, il processo può essere terminato quando il quoziente della divisone è 0, in quanto continuare significherebbe aggiungere zeri a sinistra del numero (ottenendo quindi lo stesso numero). Ad esempio, le divisioni da eseguire per convertire 123 in base 2 sono le seguenti:

123 7 3 1 . /2= /2= /2= 0 /2= 61 /2= 30 . con resto con resto 1 1 61 30 /2= 15 con resto 0 . · 15 /2= 7 con resto 1 3 con resto 1 · 1 con resto 1 con resto 1 Come detto, continuare a dividere il quoziente produrrebbe un ulteriore 0 con resto 0, e pertanto ci fermiamo. La rappresentazione in base due di 123 è quindi [1111011]2. Per verificare la correttezza della conversione possiamo convertire [1111011]2 in base 10: Liberamente distribuibile secondo i termini della licenza GNU Free Document