Rappresentazione digitale e codifica informazione

Rappresentazione digitale e codifica dell'informazione

L'informazione

L'informazione è la riduzione di incertezza. L'incertezza crea la necessità di avere informazioni. Avere una scelta implica che esistono almeno due alternative che possono essere rappresentate attraverso due valori: 0 e 1, detti bit. Quindi il bit diventa l'unità fondamentale dell'informazione. Un bit rappresenta una scelta. Il bit serve a codificare la minima incertezza (data da sole due scelte, quindi si ha la minima quantità di informazione).

Dal singolo bit che può codificare la scelta tra due alternative, si ha la necessità di codificare la scelta tra più alternative. Le parole sono sequenze di n caratteri (=cifre) presi da un alfabeto finito. Una parola può essere costituita da più bit. Per esempio, una parola da 3 bit permette di codificare 8 alternative (2³ = 8 → 000, 001, 010, 100, ...). Con ogni cifra aggiunta alla parola posso raddoppiare il numero di alternative che sono in grado di codificare. Se ho un alfabeto di S simboli posso avere combinazioni di parole pari a Sⁿ. Le parole composte dall'alfabeto binario {0,1} sono dette parole binarie. Le parole binarie composte da 8 bit sono dette byte.

Codici e codifiche

Un codice è un elemento puramente sintattico che può essere descritto in due maniere equivalenti: (1) come insieme di parole che lo costituiscono; (2) come insieme delle regole che permettono di costruire tutte le sue parole a partire da un dato alfabeto di simboli.

Formalmente, definiamo un codice come un insieme di parole, cioè: C = {w₁, w₂, ..., w_n} in cui ogni parola è costituita da una sequenza di simboli, e l'insieme di tali simboli costituisce l'alfabeto del codice, cioè: Σ = {s₁, s₂, ..., s_k}.

Fissato un codice, si ha quindi a che fare con due insiemi ben distinti: le informazioni da rappresentare e le parole del codice. Ogni relazione che associa gli elementi dell'insieme delle informazioni alle parole del codice prende il nome di codifica.

Consideriamo come esempio il problema della codifica dei giorni della settimana. Si prende l'alfabeto finito Σ = {a, b, c} e un codice arbitrario di lunghezza 2, Γ = {aa, ab, ac, ba, bb, bc, ca, cb, cc}. Si noti che è possibile costruire 9 parole, ma solo 7 saranno quelle valide che devono rappresentare un'informazione. L'insieme delle informazioni da rappresentare è composto dai giorni della settimana, cioè: I = {lun, mar, mer, gio, ven, sab, dom}. Definire una codifica significa stabilire un'associazione tra questi due insiemi.

Una codifica infatti può essere vista come una regola o legge che associa un significato a una parola. Si definisce per esempio:

• Lunedì aa
• Martedì ab
• Mercoledì ac
• Giovedì ba
• Venerdì bb
• Sabato bc
• Domenica ca

Si noti che la relazione è biunivoca, cioè ad ogni elemento dell'insieme delle informazioni corrisponde una e una sola parola del codice. In generale, la relazione può anche non esserlo. Infatti, se una stessa informazione è associata a più parole del codice si dice che la codifica è non univoca, mentre se a una parola del codice sono associate più informazioni si dice che la codifica è ambigua.

Proprietà di codici e codifiche

• Non ridondanza: Per rappresentare un'informazione ho un'unica parola. Non implica che una parola del codice non possa rappresentare più informazioni.
• Lunghezza costante: Tutte le parole del codice hanno la stessa lunghezza, cioè lo stesso numero di caratteri/cifre.
• Esattezza: Una rappresentazione è esatta se riesco ad esprimere tutti i significati senza ambiguità. Quindi, un codice si dice esatto quando non ambiguo, cioè, quando ogni parola rappresenta una sola informazione e gli elementi dell'insieme delle informazioni sono tutti rappresentati. Non implica che un'informazione non possa essere rappresentata da più parole.

Esempio grafico delle proprietà descritte.

Notazione scientifica

In molti campi dell'ingegneria, della fisica e di altre scienze esatte si usa spesso la cosiddetta notazione scientifica in cui un valore numerico è espresso mediante mantissa ed esponente.

Codici posizionali e non posizionali

I codici e le codifiche possono essere classificati secondo diversi criteri. Una prima suddivisione si fa tra codici posizionali e non posizionali. I primi sono particolarmente adatti a rappresentare un insieme ampio di valori numerici. Un altro criterio riguarda la lunghezza delle parole: in alcuni casi essa è costante e prefissata, ed è il caso dei codici a lunghezza costante, in altri casi parole diverse possono avere lunghezze diverse, ed è il caso dei codici a lunghezza variabile che trovano diverse applicazioni nel campo della compressione dell'informazione.

Per rappresentare in modo non ambiguo (quindi codici che godono delle proprietà precedenti) un numero di informazioni (cioè la cardinalità dell'insieme delle informazioni) utilizzando un codice basato su un alfabeto di S simboli, la lunghezza minima delle parole deve essere pari a: ℓ = ⌈log_S(n)⌉, in cui la simbologia ⌈ ⌉ significa che il risultato della funzione log verrà arrotondato all'intero successivo.

Per esempio, per rappresentare 100 informazioni con un alfabeto di 3 simboli sono necessarie parole di lunghezza pari almeno a ⌈log₃(100)⌉ = 5, mentre con un alfabeto di 9 simboli la lunghezza richiesta delle parole scende a ⌈log₉(100)⌉ = 3. In entrambi i casi, il numero di informazioni rappresentabili è maggiore di quello richiesto (100); nel primo caso, con 3 simboli e parole di lunghezza 5 si possono costruire 3⁵ = 243 sequenze distinte.

Quando la lunghezza delle parole di codice e la cardinalità dell'alfabeto consentono di costruire un numero di parole di codice pari alla cardinalità dell'insieme delle informazioni, cioè si parla di codice a lunghezza minima.

Per esempio, la seguente tabella mostra quanti caratteri servono per rappresentare significati:

Il logaritmo e gli esponenziali godono delle seguenti proprietà:

• log_b(xy) = log_b(x) + log_b(y)
• log_b(x/y) = log_b(x) - log_b(y)
• (x^y) = y * log_b(x)
• log₂(2^x) = x
• log_b(x) = log(x) / log(b)

Si usano i logaritmi perché sono funzioni estremamente efficienti, perché ogni volta che aggiungo un carattere all'insieme dell'alfabeto raddoppio il potere espressivo del codice, cioè posso rappresentare il doppio delle informazioni. Il grafico mostra proprio come, grazie alla funzione logaritmica, l'informazione raddoppia in modo esponenziale all'aumentare di un simbolo nell'insieme dell'alfabeto.

Limitazione e discretizzazione

Un insieme illimitato contiene un numero infinito di elementi, oppure esso è infinitamente denso (o continuo). Questi insiemi non possono essere rappresentati digitalmente perché per essere rappresentato precisamente avremo bisogno di un numero illimitato di simboli. Questa proposizione viene dal fatto che la funzione logaritmica ha come limite l'infinito. Per rappresentare un insieme infinito o infinitamente denso devo limitarlo, cioè renderlo finito. Si sceglie di rappresentare solo alcuni significati/informazioni. Questa tecnica si dice limitazione.

Quindi, per esempio, l'insieme dei numeri naturali ℕ per essere rappresentato digitalmente deve essere limitato, cioè posso scegliere di ridurre ad un sottoinsieme che va da 0 a 999. Questo sottoinsieme ora può essere codificato e rappresentato correttamente.

Si definisce un insieme illimitato come un insieme all'interno del quale preso un elemento ne esisterà sempre uno più grande o più piccolo. Un insieme infinitamente denso si definisce invece come un insieme in cui per ogni coppia di elementi presi esisterà sempre un elemento nel mezzo. In quest'ultimo caso, infatti, non è possibile applicare solo la limitazione. In questo caso, l'applicazione che si utilizza per arrivare ad avere una rappresentazione digitale esatta si chiama discretizzazione. La discretizzazione è un'operazione che partiziona un definito insieme limitato.

Ogni partizione ha le seguenti caratteristiche:

• Gli intervalli non sono sovrapposti, quindi un qualunque elemento appartiene ad un unico intervallo.
• L'insieme delle partizioni copre tutto l'insieme finito, quindi ogni elemento appartiene ad una partizione.

La discretizzazione si applica ad un qualunque insieme infinitamente denso. Una partizione, per essere rappresentabile deve essere un sottoinsieme finito. Quello che viene rappresentato però non sono gli elementi della partizione, ma la partizione stessa. La rappresentazione fatta è approssimativa per l'insieme ed esatta solo per la rappresentazione di una singola partizione.

Quindi, per esempio, l'insieme dei numeri razionali ℚ per essere rappresentato digitalmente deve essere prima limitato in un intervallo, cioè posso scegliere di ridurlo ad un sottoinsieme che va da 0 a 1. Questo sottoinsieme ora può essere partizionato, cioè diviso in sotto intervalli. Ora posso codificare e rappresentare tali partizioni in modo esatto, ma la rappresentazione dei numeri in ℚ è approssimata.

Le operazioni di limitazione e discretizzazione sono due tecniche che vengono utilizzate per ridurre un insieme con infiniti elementi ad un insieme discreto (o finito/limitato).

Rappresentazione degli insiemi numerici

Per rappresentare le informazioni di tipo numerico i codici posizionali sono particolarmente utili in quanto la codifica è esprimibile in forma algebrica. Per la rappresentazione posizionale, cioè il significato della parola si basa sulla posizione che occupa un simbolo. La posizione, infatti, determina il "peso" che il simbolo assume all'interno di quella parola. Nel contesto dei codici posizionali la cardinalità dell'alfabeto che si utilizza viene detta base. Detto {s₁, s₂, ..., s_k} l'alfabeto, una parola di un codice posizionale in base b è una sequenza di lunghezza n del tipo: W = s_n-1 s_n-2 ... s₁ s₀.

I simboli da s₀ a s_n-1 rappresentano la parte intera mentre i simboli da s_-1 a s_-m rappresentano la parte frazionaria. L'associazione tra la parola di codice e l'informazione corrispondente, ovvero il valore numerico che si vuole rappresentare, è data dalla relazione:

f(W) = s_n-1 \* b^n-1 + s_n-2 \* b^n-2 + ... + s₁ \* b¹ + s₀ \* b⁰ + s_-1 \* b^-1 + ... + s_-m \* b^-m.

Questa relazione fissa una codifica. La notazione posizionale, infatti, indica che il peso di un dato simbolo non è fisso ma dipende dalla posizione che il simbolo occupa nella parola di codice.

Considerando come esempio la notazione decimale, cioè con la base 10, si ha un alfabeto composto dalle cifre da 0 a 9 e il peso di ogni cifra nella parola di codice è determinato da potenze di 10, secondo la posizione occupata dal simbolo. Prendiamo come esempio la parola di codice [3 8 4 6] che corrisponde al valore numerico:

3 \* 10³ + 8 \* 10² + 4 \* 10¹ + 6 \* 10⁰ = 3000 + 800 + 40 + 6 = 3846.

Chiamo con 0 la prima posizione, cioè quella delle unità ed ha peso 10⁰. Analogamente, il peso delle decine la chiamo 1 ed è pari a 10¹.

In base 2, cioè in notazione binaria, prendiamo come esempio la parola di codice [1 0 1] che corrisponde al valore numerico:

1 \* 2² + 0 \* 2¹ + 1 \* 2⁰ = 4 + 0 + 1 = 5.

Il modo in cui il peso viene assegnato ad ogni cifra è analogo indifferentemente dalla base. Da base a base cambia solo appunto la base delle potenze.

Quindi nella notazione posizionale un numero è rappresentato da una sequenza di cifre che in realtà rappresentano i coefficienti per i quali verranno moltiplicate le potenze di b. Come scritto in precedenza, il coefficiente moltiplicherà la potenza b⁰, moltiplicherà la potenza b¹ e così via.

La tabella seguente riassume gli alfabeti di uso comune relativi alle basi 2, 8, 10, 16:

La base minima è 2 perché con meno di 2 simboli non posso costruire un alfabeto.

Rappresentazione numeri naturali

La codifica naturale è adatta alla rappresentazione dei numeri interi. Mediante parole di bit su un alfabeto di s simboli (cioè un codice in base s) posso rappresentare tutti i numeri interi compresi nell'intervallo chiuso [0; sⁿ-1]. Una parola di codice assume la forma:

f(W) = s_n-1 \* s^n-1 + s_n-2 \* s^n-2 + ... + s₁ \* s¹ + s₀ \* s⁰.

In pratica, si toglie la parte frazionaria.

Conversione di base dei numeri naturali

Le regole di conversione si deducono direttamente dalla definizione stessa di notazione posizionale. Si distinguono due metodi per effettuare una conversione tra basi differenti: per somma di prodotti oppure per divisioni ripetute. Entrambi i metodi di codifica si basano sulla relazione:

s_n-1 \* b^n-1 + s_n-2 \* b^n-2 + ... + s₁ \* b¹ + s₀ \* b⁰.

Dove c_i è il coefficiente numerico, b è la base e l'esponente è il peso assunto da c_i. Partendo da tale formula possiamo raccogliere a fattor comune la base...