SCIENZE E TECNOLOGIE INFORMATICHE

[:it]Lo schema di un canale trasmissivo può essere visto come segue:

La codifica di sorgente ha il compito di trasformare un messaggio scritto ad esempio in una tastiera in una sequenza di bit.

Tale trasformazione può essere a lunghezza fissa (codice ASCII) o a lunghezza variabile (ad esempio codifica di Huffmann)

Ci sono i pregi e i difetti per entrambi i tipi di decodifica.

Codice ASCII.

Esso permette la codifica dei caratteri in 8 bit. Utilizzando la definizione di distribuzione a ripetizione avendo un alfabeto di 2 cifre per 8 bit in tutto si ha combinazioni diverse.

Codice Huffmann

Il codice di Huffman costruisce una tabella di codifica-decodifica utilizzando un numero di bit differente a seconda della probabilità che si ha di trovare uno specifico valore.

Utilizzando meno bit per i codici più probabili, e più bit per quelli meno diffusi, si può risparmiare memoria.

E’ il codice migliore per ottimizzare l’entropia, è il metodo più efficiente per la compressine dei dati. (pkzip, jpeg, mp3).

Per creare la giusta codifica si usa uno schema ad albero

Ecco la spiegazione dell’algoritmo:

• si ordinano i simboli in ordine decrescente di probabilità
• i due valori più piccoli creano le prime due foglie (leaf node) e si sommano creando il primo nodo. A ramo di sinistra si associa sempre il valore 0 ed al ramo di destra il valore 1.
• si ordinano nuovamente i valori.
• i due valori più piccoli si sommano creando ancora un nodo, Al ramo di sinistra si associa il valore 1, al ramo di destra il valore 0.
• il processo continua finchè non vi sono più simboli o probabilità associati al relativo simbolo.

Esempio

Sia dato un file formato da 120 caratteri con la seguente frequenza di caratteri (attenzione parlare di frequenza o probabilità di un carattere è uguale)

Se si usasse un codice a lunghezza fissa si dovrebbe usare una stringa di bit lunga 3 in quanto essa è l’unica che possa contenere la codifica di 6 caratteri, infatti

Siccome vi sono 120 caratteri da trasmettere bit

Utilizzando invece la codifica a lunghezza variabile si ha:

Bastano bit

Spiegazione di come si crea il codice variabile.

• ordino i valori dal meno frequente al più frequente:

• sommo gli ultimi due
• creo due foglie con il ramo 0 a sinistra 0 ed il ramo 1 a destra
• ordino la sequenza:

• sommo gli ultimi due
• creo due foglie con il ramo 0 a sinistra e il ramo 1 a destra
• ordino la sequenza
• sommo gli ultimi due
• creo un nuovo nodo
• ordino la sequenza

• sommo gli ultimi due
• creo un nuovo nodo
• ordino la sequenza

• sommo gli ultimi 2
• creo l’ultimo nodo

Adesso come si legge il codice?

• o partendo dal basso e poi invertendo i bit: ad esempio f: 0011 lo inverto 1100
• o partendo dall’alto (root) ed arrivando a tutte le radici

Come avviene la decodifica?

Siccome nessuna parola codice è prefisso di un’altra, la prima parola codice del file codificato risulta univocamente determinata.

Ad esempio trasmetto 0101100, comincio a leggere da sinistra verso destra. Prendo i primi 4 caratteri, non corrisponde a nessuna cifra, prendo i primi tre ancora nessuna, prendo il primo e corrisponde ad a, elimino lo 0 rimane

101100

1011 non corrisponde a nessun carattere,

101 corrisponde alla b

rimane 100 che corrisponde alla c

per cui il messaggio è abc.[:]

[:it]

Franz Marc

La sorgente aleatoria numerica viene anche definita una sorgente aleatoria discreta, essere senza memoria significa che i simboli sono indipendenti ed identicamente distribuiti estratti da un alfabeto A di dimensione finita L.

Quindi ogni simbolo ha una certa probabilità di essere emesso.

In inglese esso è definito come:

Discrete Memoryless source, DMS[:]

[:it]

Charles S. Raleigh

Tutti questi esercizi possono essere risolti mediante l’applicazione delle relazioni definite nei posti precedenti sulla definizione di informazione, entropia, lunghezza di un messaggio, ridondanza.

1. Una sorgente discreta emette i simboli aventi probabilità rispettivamente . Determinare l’informazione associata a ciascun simbolo e l’entropia della sorgente
2.  Calcola la ridondanza di una sorgente binaria discreta le cui probabilità di emissione sono
3. Una sorgente discreta emette 5 simboli con probabilità . a) Calcola la ridondanza della sorgente b) La lunghezza del codice necessaria ad effettuare una corretta codifica della sorgente.
4. Si ha una sorgente di 6 simboli discreti con ridondanza ; calcola: a) L’entropia b) la lunghezza del codice c) l’efficienza della codifica
5. Una sorgente ha alfabeto di n=4 simboli con le seguenti probabilità di emissione: simbolo probabilità 0.38 0,25 0,22 0,15 a) Calcola l’entropia della sorgente b)Calcola il contenuto informativo dei due seguenti messaggi: e
6. Una sorgente ha un alfabeto di n=7 simboli con le seguenti probabilità di emissione: simbolo probabilità codice 0,32 00 0,23 01 0,13 100 0,1 101 0,09 110 0,08 1110 0,05 1111 Calcola la lunghezza media del codice
7. Una sorgente discreta emette 3 simboli statisticamente indipendenti; sapendo che , calcolare la ridondanza .
8. Un alfabeto è costituito da 2 simboli equiprobabili. IL tempo impiegato per trasmettere il primo simbolo è mentre , calcolare: a) l’entropia della sorgente b) il tempo medio per trasmettere un simbolo c) la velocità di trasmissione

 [:]

[:it]Anno2015

Anno2017[:]

[:it]

Vladimir Kush

La lunghezza media di un codice è data da quanti simboli in media sono necessari per mandare un messaggio con tali simboli ossia:

dove con è il numero di simboli.

oppure se si conosce la lunghezza del codice:

Per efficienza si intende:

Per ridondanza si intende quindi

ossia quanto più una sorgente ha una grande entropia (ossia fornisce molte informazioni) con un alfabeto molto basso, minore è la ridondanza ossia la necessità di trasmettere segnali simili nel canale trasmissivo.[:]

[:it]

Vladimir Kush

Che cos’è l’entropia di una sorgente?

E’ il massimo grado di informazione che può darci un opportuno codice.

In fisica l’entropia fornisce il grado di disordine di un particolare sistema, nella teoria dell’informazione quanto più un codice ha un’elevata entropia quanta più informazione esso potrà portare.

Nella teoria della probabilità, quando due eventi sono statisticamente indipendenti la probabilità che uno accada in seguito all’altro è dato dal prodotto delle loro probabilità ossia: (principio delle probabilità composte)

L’unica funzione matematica che dal prodotto permette di passare alla somma è ancora il logaritmo per cui esso compare ancora nella definizione di entropia:

L’unità di misura dell’entropia è il bit/carattere.

La velocità di trasmissione viene definita non come la frequenza con cui si trasmette ma come il prodotto tra l’entropia e la frequenza dei simboli emessi.[:]

[:it]

Vladimir Kush

L’informazione, nell’ambito delle telecomunicazioni,  viene definita come la riduzione di incertezza che si poteva avere a priori sul simbolo trasmesso.

Sembra un panegirico ma, in realtà, il concetto è che se io trasmetto sempre un solo segnale sempre uguale, la probabilità di riceverlo è sempre 1. Ma tale fatto significa anche che l’informazione trasmessa è nulla.

Per trasmettere un’informazione vi è bisogno che si modifichi uno stato da luce a buio o viceversa; si pensi ai solo caratteri morse: per comunicare un messaggio, ossia un’informazione, si alternano i punti con le linee in un’opportuna combinazione.

Per dare una definizione che possa essere misurabile si utilizza la funzione logaritmo perché è l’unica che quando il suo argomento vale 1, il suo valore va a zero ed inoltre lo si caperà ancora di più quando si definisce l’entropia.

dove con si intende la probabilità con cui quel simbolo possa presentarsi.

Se la base del logaritmo è:

• 2 l’informazione si misura in bit
• 10 l’informazione si misura in hartley
• e (numero di Eulero) l’informazione si misura in nat

[:en]trasmesso e viene definita come la riduzione di incertezza che si poteva avere a priori sul simbolo trasmesso.
Sembra un panegirico ma, in realtà, il concetto è che se io trasmetto sempre un solo segnale sempre uguale, la probabilità di riceverlo è sempre 1. Ma tale fatto significa anche che l’informazione trasmessa è nulla.
Per trasmettere un’informazione vi è bisogno che si modifichi uno stato da luce a buio o viceversa; si pensi ai solo caratteri morse: per comunicare un messaggio, ossia un’informazione, si alternano i punti con le linee in un’opportuna combinazione.
Per dare una definizione che possa essere misurabile si utilizza la funzione logaritmo perché è l’unica che quando il suo argomento vale 1, il suo valore va a zero ed inoltre lo si caperà ancora di più quando si definisce l’entropia.

dove con si intende la probabilità con cui quel simbolo possa presentarsi.
Se la base del logaritmo è:
2 l’informazione si misura in bit
10 l’informazione si misura in hartley
e (numero di Eulero) l’informazione si misura in nat[:de]trasmesso e viene definita come la riduzione di incertezza che si poteva avere a priori sul simbolo trasmesso.
Sembra un panegirico ma, in realtà, il concetto è che se io trasmetto sempre un solo segnale sempre uguale, la probabilità di riceverlo è sempre 1. Ma tale fatto significa anche che l’informazione trasmessa è nulla.
Per trasmettere un’informazione vi è bisogno che si modifichi uno stato da luce a buio o viceversa; si pensi ai solo caratteri morse: per comunicare un messaggio, ossia un’informazione, si alternano i punti con le linee in un’opportuna combinazione.
Per dare una definizione che possa essere misurabile si utilizza la funzione logaritmo perché è l’unica che quando il suo argomento vale 1, il suo valore va a zero ed inoltre lo si caperà ancora di più quando si definisce l’entropia.

dove con si intende la probabilità con cui quel simbolo possa presentarsi.
Se la base del logaritmo è:
2 l’informazione si misura in bit
10 l’informazione si misura in hartley
e (numero di Eulero) l’informazione si misura in nat[:]

[:it]

1. Lanciando due monete qual è la probabilità di ottenere due teste?
2. Si lanciano due dadi. Trova la probabilità che escano due 3; che escano un 3 e un 4; che escano due numeri pari.
3. Calcola la probabilità che lanciando una moneta esca testa
4. Calcola la probabilità che lanciando 1 dado esca il numero 1.
5. Calcola la probabilità che lanciando 1 dado esca un numero divisibile per 2
6. Determina la probabilità che, lanciando 3 volte di seguito 1 moneta, si verifichi l’evento “esca almeno una croce”, sapendo che il primo lancio ha dato testa.
7. Da un’urna contenente 9 palline nere e 7 bianche si estraggono successivamente 3 palline, rimettendo ogni volta nell’urna la pallina estratta. Qual è la probabilità che siano tutte e tre nere? Che siano tutte e 3 bianche? Che siano le prime 2 bianche e la terza nera? Che siano  bianche e 1 nera?	;;;

 [:]

[:it]

Samy Charnine

Dal post sulle probabilità condizionate si è affermato che:

che è uguale a scrivere:

ma nel caso in cui si abbiano eventi indipendenti

per cui si ha il principio delle probabilità composte ossia

Questa relazione è alla base della definizione di Entropia nell’ambito delle telecomunicazioni.

Esempio di applicabilità

Si vuole sapere qual è la probabilità che esca testa, nel lancio di una moneta due volte, sapendo che prima è uscita testa.

In questo caso si è in presenza di eventi indipendenti per cui la probabilità che esca testa al primo lancio è , la probabilità che esca nuovamente testa è , per cui la probabilità che in due lanci mi esca due volte testa vale .[:]

[:it]

Samy Charnine

Due eventi sono indipendenti se il verificarsi dell’uno non influisce sul calcolo della probabilità del verificarsi dell’altro

Due eventi sono dipendenti se il verificarsi dell’uno influisce sul calcolo della probabilità del verificarsi dell’altro.

Sono molto importanti queste due definizioni perché influiscono moltissimo nel caso in cui dovessi prevedere la trasmissione di un messaggio e quindi la necessità di trasmetterlo solo una volta o ritrasmetterlo.

Il primo esempio di eventi indipendenti potrebbe essere quello dell’estrazione di una pallina bianca da un’urna contente palline bianche e nere. In questo caso se dopo l’estrazione rimetto all’interno la pallina bianca estratta avrò eventi INDIPENDENTI ossia calcolare la probabilità di estrarre un’altra pallina bianca non dipende dall’estrazione precedente.

Se invece la pallina bianca non viene reintrodotta dall’urna allora tale fatto ha reso dipendente l’estrazione successiva da quella precedente.[:]