Discussione Shannon: la teoria dell'informazione, fondamenti e applicazioni

[haxo]

La teoria dell'informazione di Shannon studia e spiega il modo in cui l'informazione viene trasmessa, elaborata e compressa. Sviluppata dal grandissimissimo Claude Shannon, fornisce strumenti per quantificare l'informazione e ottimizzarla. Ha applicazioni in telecomunicazioni, crittografia e compressione dei dati.

Mi sono imbattuto nella teoria dell'informazione di Shannon per la prima volta quest'anno durante le scuole superiori. L'idea che ci sia una scienza che si occupa dell'informazione e delle sue fondamenti è stato veramente bello, dai anche divertente!.

Abbiamo fatto 3-4 lezioni su questa teoria, e fin dalla prima lezioni, si è accesa la lampadina. Shannon, con la sua teoria ha dimostrat concetti di bit, entropia e codifica e ha creato strumenti matematici per quantificare l'informazione e misurare la sua compressibilità.

Cercherò di scrivere solo le cose fondamentali, o almeno quello che ho scritto sul quaderno di sistemi e reti

1    Ma a che mi serve?

Ti serve.
Ti serve perchè viviamo nell'era delle informazione, dove se ti distrai, sei costretto a leggere per essere informato, sopratutto nell'informatica.
Quindi comunque si, ti serve

2    Ecco come funziona il processo comunicativo

Che sia per via etere, che sia via rete, il processo comunicativo, quindi di scambio di informazioni avviene attraverso questo schema:

Credo non abbia bisogno di spiegazioni, ma la faremo lo stesso:

Inizialmente, è presente la sorgente, cioè da dove parte il messaggio, continuando abbiamo bisogno di un trasmettitore che permette al messaggio di fluire nel canale comunicativo, per finire abbiamo un ricevitore che riceve il messaggio e lo passa al destinatario.

E' possibile notare che oltre a questi 4 elementi, ne è presente uno chiamato "Noise Source".
Il Noise Source sono tutti quei possibili disturbi che possono presentarsi nel canale comunicativo mettendo "a rischio" l'integrità del dato trasmesso

Pensiamo ad esempio un professore che durante è costretto a fermare momentaneamente la sua lezione a causa dei ragazzi all'ultimo banco che parlano.

3    Il concetto di codifica

3.1    Simboli e codici

Quando parliamo della teoria dell'informazione di Shannon, è necessario spiegare (per quanto sia banale) cosa siano simboli e codici

Per capire cosa sia un simbolo, possiamo prendere come riferimento l'alfabeto che rappresenta l'insieme di simboli distinti che possono essere utilizzati per creare messaggi (nel nostro caso).

Ma esistono altri tipi di simboli e codic, pensiamo ad esempio a come il computer comunica, semplicemente attraverso il numero 0, e il numero 1 (sistema binario )

Quindi, quando parliamo di simboli e codici ci riferiamo a elementi che utilizzati nel contesto appropriato, rappresentano l'informazione da codificare.

3.2    Codificazione del messaggio

La codifica si riferisce al processo di rappresentazione di un messaggio utilizzando un sistema di simboli (ad esempio l'alfabeto) o codici. L'obiettivo della codifica è ridurre la quantità di informazione necessaria per rappresentare il messaggio, in modo da rendendolo più compatto ed efficiente.

4    Applicazioni della teoria dell'informazione

La teoria dell'informazione di Shannon ha molte applicazioni in diversi campi. Uno dei settori principali in cui viene utilizzata è quello delle telecomunicazioni, infatti viene utilizzata per progettare sistemi di comunicazione efficienti. Ad esempio, quando parli al telefono o invii un messaggio su Internet, l'informazione viene convertita in segnali e trasmessa attraverso un canale di comunicazione.

La teoria vale anche per il settore della crittografia, in quanto utilizzando concetti di codifica e compressione dei dati, la teoria fornisce gli strumenti per proteggere le informazioni sensibili da accessi non autorizzato

 

[St3ve]

Fa piacere leggere qualche argomento un po' più teorico anche su questo forum. Ne approfitto per dare un piccolo contributo alla discussione visto che hai presentato lo schema generale, ma non hai introdotto nemmeno uno risultato teorico.

Supponiamo che stiamo comunicando in un noisy channel come quello che hai presentato tu. Per semplificarci la vita, diciamo che stiamo scrivendo una sequenza di bit su un hard disk e, come ogni cosa in natura, non abbiamo la certezza assoluta che i bit che stiamo scrivendo noi (source) siano uguali a quelli che saranno effettivamente memorizzati nell'hard disk (destination); per esempio, potrebbe esserci uno sbalzo di tensione o un malfunzionamento della testina di scrittura che a un certo punto mi porta a scrivere uno invece che zero, o vice versa. Facciamo finta che il nostro hard disk è particolarmente economico e abbiamo il 10% di probabilità che un bit si corrompa durante la scrittura. Abbiamo tra le mani un hard disk veramente terribile.

I dati corrotti su un hard disk sono un problema abbastanza serio. Una soluzione classica per mitigare questo problema è di aggiungere ridondanza pura, ovvero compriamo un po' di hard disk e scriviamo la stessa cosa su tutti quanti. Questa cosa di attaccare un po' di hard disk assieme e scrivere gli stessi dati su tutti quanti si chiama raid 1. Nel momento in cui andiamo a leggere un bit, lo leggiamo da tutti gli hard disk che abbiamo e procediamo per voto di maggioranza: se 7 hard disk dicono che un certo bit è uno e 2 hard disk dicono che è zero, io mi fido della maggioranza. Il concetto è molto semplice, se abbiamo scritto la stessa cosa su tanti hard disk è probabile che, nel momento in cui andiamo a leggere un bit, quasi tutti gli hard disk mi dicano la stessa cosa. Non voglio perdere troppo tempo dietro ai calcoli, anche perché sarò molto superficiale quando annuncerò il risultato di Shannon, ma per farla breve questo approccio di "voto di maggioranza" con $$\(n$$\) hard disk con probabilità di errore per bit $$\(p$$\) riduce la probabilità di errore a
$$\[\sum_{k=(n+1)/2}^{n} \binom{n}{k}p^k (1-p)^{n-k} \text{ per bit}$$\]che, per chi sa di cosa sto parlando, è la distribuzione binomiale (i.e., probabilità di avere $$\(k$$\) successi in $$\(n$$\) esperimenti bernulliani indipendenti) sommata per tutti i $$\(k$$\) che passano il voto di maggioranza.

Abbiamo detto che i nostri hard disk hanno il 10% di probabilità di corrompere un bit. Noi questi hard disk vorremmo usarli sul serio, quindi vorremmo ridurre questa probabilità di errore a zero, perché su un hard disk ci scriviamo cose importanti e se si iniziano a corrompere i dati è una bella rottura di palle. Chiaramente non possiamo eliminare completamente la probabilità di errore, ma un po' più ragionevolmente possiamo chiedere che su 1.25 terabyte (numero sparato a caso) di dati scritti vogliamo essere sicuri al 99.9% che nemmeno un bit sia sbagliato. Per quello che ho detto fin ora, potremmo comprarci una sfilza di hard disk da almeno 1.25TB l'uno e collegarli in raid 1 (i.e., scrivere la stessa cosa su ognuno di questi). Conti alla mano 1.25TB sono $$\(10^{13}$$\) bits e se vogliamo una probabilità di errore complessiva pari allo 0.1% vuol dire che la probabilità di errore per bit dev'essere $$\(10^{-16}$$\). Per raggiungere questa probabilità abbiamo bisogno di fare raid 1 con circa 65 hard disk, perché inserendo n=65 nella formula precedente otteniamo circa $$\(10^{-16}$$\). Meglio ancora se usiamo ancora più hard disk, ma già 65 è un numerone che nella pratica non vorrai usare mai. Sarebbe bello ottenere risultati simili in modo più efficiente.

Fin qui, matematica a parte, penso di non aver detto niente di strano. Se abbiamo un hard disk mezzo guasto che ha il 10% di probabilità di sbagliarsi a leggere/scrivere un bit possiamo usarlo comunque, in modo affidabile, aggiungendo ridondanza sui dati. Intuitivamente, se vogliamo essere sicuri al 99.9% che il nostro terabyte di dati non venga corrotto abbiamo bisogno di tanta ridondanza. In particolare, facendo i calcoli, abbiamo scoperto che abbiamo bisogno di fare raid 1 con ben 65 hard disk. Shannon però se n'è uscito con un risultato secondo me molto sorprendente: non è vero che abbiamo bisogno di tanta ridondanza, con solo solo 2 di questi hard disk (10% probabilità di errore), usando la codifica opportuna, possiamo essere sicuri al 99.9999999% (grande a piacere) che il nostro terabyte di dati sia scritto/letto senza nessun errore (noisy-channel coding theorem). Questo almeno in teoria, perché in pratica scrivere un encoder/decoder che raggiunge il limite promesso da Shannon è fuori questione; però, ovviamente, ci sono un sacco di codici usati in pratica che ottengono risultati significativamente migliori rispetto al raid 1 di cui vi ho parlato. Applicazioni pratiche a parte, secondo me questo corollario del noisy-channel coding theorem è interessantissimo.