ELEMENTI DI PROBABILITÀ - docente.unicas.it · Consideriamo un esperimento aleatorio con spazio di...
Transcript of ELEMENTI DI PROBABILITÀ - docente.unicas.it · Consideriamo un esperimento aleatorio con spazio di...
ELEMENTI DI PROBABILITÀ
Grossi/Venturino 1Corso di Telecomunicazioni - AA 2011/2012
Premessa
QUESITO 1: Marco viaggia in auto alla velocità costante di 60 Km/h. Quanti Km avrà percorso dopo 45 minuti?
QUESITO 2: Marco lancia dal balcone di casa una biglia di metallo ed un foglio di carta. Quale dei due impiega meno tempo per arrivare a terra?
QUESITO 3: Mariella lancia un dado. Quale numero esce?
QUESITO 4: Mariella estrae una carta da un mazzo di carte napoletane. Quale carta esce?
Corso di Telecomunicazioni - AA 2011/2012 2Grossi/Venturino
Premessa
Un esperimento si dice DETERMINISTICO se siamo in grado di prevederne in maniera certa il risultato.
Un esperimento si dice ALEATORIO (o STOCASTICO) se non siamo in grado di prevederne con certezza il risultato.
Corso di Telecomunicazioni - AA 2011/2012 3Grossi/Venturino
Premessa
Corso di Telecomunicazioni - AA 2011/2012 4
Nel 1654 un giocatore d'azzardo chiese consiglio ad un matematico francese, Blaise Pascal (1601-1665),
sul modo di ripartire le sue puntate in denaro in un gioco di dadi. Pascal discusse il problema con un altro
eminente matematico, di nome Pierre de Fermat (1623-1662), e la soluzione di questo problema diede origine alla
teoria della probabilità.
Blaise Pascal
Pierre de Fermat
Grossi/Venturino
Teoria della probabilità
Si occupa dello studio degli esperimenti aleatori.
Consente di fare delle previsioni sul risultato di un esperimento aleatorio.
Corso di Telecomunicazioni - AA 2011/2012 5Grossi/Venturino
Esempio: lancio di una moneta
Il risultato dell’esperimento può essere TESTA o CROCE.
Ogni risultato dell’esperimento viene detto “evento elementare”.
Se la moneta non è truccata non abbiamo motivo per preferire un evento elementare ad un altro diciamo che gli eventi elementari sono egualmente probabili.
Se la faccia “TESTA” è più pesante, siamo portati a preferire il risultato CROCE al risultato TESTA diciamo che l’evento elementare CROCE è più probabile dell’evento elementare TESTA.
Corso di Telecomunicazioni - AA 2011/2012 6Grossi/Venturino
Esempio: lancio di una moneta
Supponiamo di lanciare N volte una moneta. Ogni lancio viene detto “prova”. Possiamo definire le seguenti grandezze:
Frequenza assoluta del risultato “testa”: è il numero di volte che si verifica il risultato “testa” su N prove è un numero intero compreso tra 0 e N.
Frequenza relativa del risultato “testa”: è il rapporto tra la frequenza assoluta del risultato “testa” e il numero di prove eseguite N è un numero decimale compreso tra 0 e 1.
In modo analogo possiamo definire la frequenza relativa per l’evento elementare “croce”.
Corso di Telecomunicazioni - AA 2011/2012 7Grossi/Venturino
Esempio: lancio di una moneta
Corso di Telecomunicazioni - AA 2011/2012 8
Al crescere del numero di prove la frequenza relativa di un evento elementare converge ad un valore costante tale
valore prende il nome di probabilità dell’evento elementare.
Grossi/Venturino
Esempio: lancio di una moneta
Corso di Telecomunicazioni - AA 2011/2012 9
Pr{TESTA} = 0.5Pr{CROCE} = 0.5
Pr{TESTA} = 0.8Pr{CROCE} = 0.2
Grossi/Venturino
Come esprimere la probabilità
La probabilità di un evento si può esprimere:a) come frazione, ad esempio 1/2b) come numero decimale, ad esempio 1/2 = 0.5c) come percentuale, ad esempio 0.5 = 50%
Nota. Per trasformare una frazione in una percentuale si divide il numeratore per il denominatore e si moltiplica il risultato per 100.
Corso di Telecomunicazioni - AA 2011/2012 10Grossi/Venturino
Esempio: lancio di un dado
Il risultato dell’esperimento può essere 1, 2, 3, 4, 5 o 6.
Lanciamo N volte il dado. Possiamo definire le seguenti grandezze: Frequenza assoluta del risultato “1”: è il numero di
volte che si verifica il risultato “1” su N prove è un numero decimale compreso tra 0 e N.
Frequenza relativa del risultato “1”: è il rapporto tra la frequenza assoluta del risultato “1” e il numero di prove eseguite N è un numero decimale compreso tra 0 e 1.
In maniera analoga possiamo definire la frequenza relativa per gli altri eventi elementari.
Corso di Telecomunicazioni - AA 2011/2012 11Grossi/Venturino
Esempio: lancio di un dado
Corso di Telecomunicazioni - AA 2011/2012 12Grossi/Venturino
Esempio: lancio di un dado
Corso di Telecomunicazioni - AA 2011/2012 13
Al crescere del numero di prove la frequenza relativa di ogni evento elementare converge al medesimo valore possiamo
concludere che il dado non è truccato e che Pr{1} = Pr{2} = … = Pr{6} = 1/6 ≈ 0.1667 = 16.67 %
Grossi/Venturino
Spazio campione
Consideriamo un generico esperimento aleatorio che può avere M possibili risultati, indicati con s1,…,sM.
Si definisce spazio dei campioni l’insieme di tutti i possibili risultati si indica con la lettera S
M prende il nome di cardinalità dello spazio dei campioni
Corso di Telecomunicazioni - AA 2011/2012 14
s2
s5
s1
s4
s7
s3
s6
SPAZIO CAMPIONE (S)CON CARDINALITA’ M=7
Grossi/Venturino
Eventi
Si chiama evento un sott’insieme dello spazio dei campioni.
Classificazione:
Evento elementare, se è un insieme con un solo elemento
Evento composto (o semplicemente evento), se è un insieme con almeno due elementi
Evento certo, se coincide con lo spazio dei campioni S (ovvero se contiene tutti gli eventi elementari)
Evento impossibile, se non contiene alcun elemento (insieme vuoto) viene indicato con il simbolo ∅
Grossi/Venturino 15Corso di Telecomunicazioni - AA 2011/2012
Eventi
Corso di Telecomunicazioni - AA 2011/2012 16
s2
s5
s1
s4
s7
s3
s6
SPAZIO CAMPIONE EVENTO CERTO
EVENTO ELEMENTARE
A = ∅ EVENTO IMPOSSIBILE
B = {s4,s6,s7} EVENTO COMPOSTO
Grossi/Venturino
Esempio: lancio di un dado
Spazio dei campioni S = {1,2,3,4,5,6} A = {esce un numero pari} = {2,4,6} B = {esce un numero dispari} = {1,3,5} C = {esce un numero maggiore di 4} = {5,6} E = {esce un numero maggiore di 7}= ∅
Corso di Telecomunicazioni - AA 2011/2012 17
3
41
2
5 6
A
B
C
S
Grossi/Venturino
Operazione fra eventi: unione
L’unione (o somma) di due eventi A e B si indica con A⋃B ed è l'insieme formato da tutti gli elementi di A e B presi una sola volta.
Corso di Telecomunicazioni - AA 2011/2012 18
AB
SPAZIO DEI CAMPIONI (S)
A⋃B
Grossi/Venturino
Operazione fra eventi: intersezione
L’intersezione (o prodotto) fra due eventi A e B si indica con A∩B ed è l'insieme formato da tutti gli elementi che appartengono sia ad A che a B.
Corso di Telecomunicazioni - AA 2011/2012 19
SPAZIO DEI CAMPIONI (S)A⋂B
AB
Grossi/Venturino
Operazione fra eventi: differenza
La differenza fra due eventi A e B si indica con A \ B ed è l’insieme formato da tutti gli elementi che si trovano in A ma non in B.
Corso di Telecomunicazioni - AA 2011/2012 20
AB
SPAZIO DEI CAMPIONI (S)A \ B
Grossi/Venturino
Operazione fra eventi: complementazione Si definisce evento complementare (o negato o
opposto) di A l’insieme Ac costituito dagli eventi elementari che non appartengono ad A.
Corso di Telecomunicazioni - AA 2011/2012 21
SPAZIO DEI CAMPIONI (S)
AcA
Grossi/Venturino
Eventi mutuamente esclusivi
Due eventi A e B si dicono mutuamente esclusivi (o incompatibili) se non hanno elementi in comune (ovvero se A⋂B=∅)
Corso di Telecomunicazioni - AA 2011/2012 22
BA
SPAZIO DEI CAMPIONI (S)
Grossi/Venturino
Esempio di operazioni fra eventi
Osserviamo la sequenza di teste (T) e croci (C) che si presentano lanciando tre volte una moneta.
S = {TTT,TTC,TCT,TCC,CTT,CTC,CCT,CCC}
A = “si hanno più di due teste consecutive” = {TTT,TTC,CTT}
B = “tutti lanci danno lo stesso risultato” = {TTT,CCC}
A⋂B = {TTT}
A⋃B = {TTT,TTC,CTT,CCC}
A \ B = {TTC,CTT}, B \ A = {CCC}
Ac = {TCT,TCC, CTC,CCT,CCC}
Corso di Telecomunicazioni - AA 2011/2012 23Grossi/Venturino
Probabilità di un evento
Consideriamo un esperimento aleatorio con spazio di probabilità S = {s1,…,sM}
Ad ogni evento A⊆S possiamo associare una probabilità che indichiamo con Pr{A}.
Intuitivamente, Pr{A} indica la frazione di volte che l’evento A si verifica in un numero molto grande di esecuzioni (prove) indipendenti dell’esperimento aleatorio.
Corso di Telecomunicazioni - AA 2011/2012 24Grossi/Venturino
Assiomi della probabilità (assiomi di Kolmogorv) La probabilità di ogni evento è non negativa, cioè
Pr(A) ≥ 0, per ogni A
L’evento certo ha probabilità 1, cioè Pr(S) = 1
Se gli eventi A e B sono mutuamente esclusivi risultaPr(A⋃B) = Pr(A) + Pr(B)
La probabilità è una funzione non negativa, normalizzata (cioè che assume valore al
più pari da uno) e additiva
Corso di Telecomunicazioni - AA 2011/2012 25Grossi/Venturino
Conseguenze degli assiomi della probabilità Chiamiamo pi≥0 la probabilità che si verifica
l’i-esimo evento elementare si
Poiché S = {s1,…,sM} = {s1} ⋃ …⋃ {sM} e gli eventi elementari sono mutuamente esclusivi risulta:
1 = Pr{S} = p1 + … + pM
Se gli eventi elementari sono equiprobabili risulta risulta p1 = … = pM = 1/M
Corso di Telecomunicazioni - AA 2011/2012 26Grossi/Venturino
Conseguenze degli assiomi della probabilità Si consideri l’evento A = {s1,s2,s3} = {s1} ⋃ {s2}
⋃ {s3} contente tre eventi elementari. Si ha:
Se gli eventi elementari sono egualmente probabili risulta:
Corso di Telecomunicazioni - AA 2011/2012 27
M3
possibili casi numerofavorevoli casi numeroPr{A} ==
1 ppp }Pr{s}Pr{s} Pr{s Pr{A} 0
321
321
≤++=++=≤
Grossi/Venturino
Esempio: lancio di un dado regolare
Spazio dei campioni S = {1,2,3,4,5,6} A = {esce un numero pari} = {2,4,6} B = {esce un numero dispari} = {1,3,5} C = {esce un numero maggiore di 4} = {5,6}
Corso di Telecomunicazioni - AA 2011/2012 28
3
41
2
5 6
A
B
C
S
Pr{1} = … = Pr{6} = 1/6
Pr{A} = 3/6
Pr{B} = 3/6
Pr{C} = 2/6
Grossi/Venturino
Conseguenze degli assiomi della probabilità Se A e B non sono mutuamente esclusivi
risulta:Pr{A⋃B} = Pr{A} + Pr{B} – Pr{A⋂B}
Corso di Telecomunicazioni - AA 2011/2012 29
SPAZIO DEI CAMPIONI (S)
A⋂BA
B
Grossi/Venturino
Esempio: lancio di un dado regolare
Spazio dei campioni S = {1,2,3,4,5,6} B = {esce un numero dispari} = {1,3,5} C = {esce un numero maggiore di 4} = {5,6} B⋃C = {1,3,5,6} B⋂C = {5}
Corso di Telecomunicazioni - AA 2011/2012 30
Pr{B} = 3/6, Pr{C} = 2/6
Pr{B⋂C} = 1/6
Pr{B⋃C} = 4/6
Grossi/Venturino
3
41
2
5 6
B
C
S
Conseguenze degli assiomi della probabilità Sia A un generico evento. Si ha S = Ac⋃A.
Poiché Ac ed A sono mutuamente esclusivi risulta:1 = Pr{S} = Pr{Ac} + Pr{A}
Pr{Ac} = 1 - Pr{A}
L’evento impossibile si verifica con probabilità nulla. Infatti:
S=∅ ⋃ S Pr{S} = Pr{∅} + Pr{S} Pr{∅} = 0
Corso di Telecomunicazioni - AA 2011/2012 31Grossi/Venturino
Esempio: lancio di un dado regolare
Spazio dei campioni S = {1,2,3,4,5,6} A = {esce un numero pari} = {2,4,6} B = {esce un numero dispari} = {1,3,5} = Ac
E = {esce un numero maggiore di 7}= ∅
Corso di Telecomunicazioni - AA 2011/2012 32
3
41
2
5 6
A
B
S
Pr{A} = 3/6, Pr{B} = 3/6
Pr{B} = 1 - Pr{A}
Pr{E} =0
Grossi/Venturino
Esempio: lancio coppia di dadi
Supponiamo di lanciare una coppia di dadi non truccati, uno di colore rosso e l’altro di colore blu.
Lo spazio dei campioni ha cardinalità M=36 La probabilità di ogni risultato è 1/36
Corso di Telecomunicazioni - AA 2011/2012 33
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Grossi/Venturino
Esempio: lancio coppia di dadi
A = {il punteggio dei due dadi è uguale} Numero casi favorevoli = 6 Pr{A} = 6/36 = 1/6
Corso di Telecomunicazioni - AA 2011/2012 34
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole ad A
Grossi/Venturino
Esempio: lancio coppia di dadi
A = {il punteggio dei due dadi è uguale} B = {il punteggio dei due dadi è diverso} Pr{B} = Pr{Ac} = 1-Pr{A} = 1-1/6 = 5/6
Corso di Telecomunicazioni - AA 2011/2012 35
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole ad A
Favorevole a B
Grossi/Venturino
Esempio: lancio coppia di dadi
C = {il punteggio del dado rosso è minore di 3} Numero casi favorevoli = 12 Pr{A} = 12/36 = 1/3
Corso di Telecomunicazioni - AA 2011/2012 36
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole a C
Grossi/Venturino
Esempio: lancio coppia di dadi
A = {il punteggio dei due dadi è uguale} C = {il punteggio del dado rosso è minore di 3} Pr{A⋂C} = 2/36 = 1/18
Corso di Telecomunicazioni - AA 2011/2012 37
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole ad A
Favorevole a C
Favorevole ad A e C
Grossi/Venturino
Esempio: lancio coppia di dadi
Calcoliamo i possibili valori che possiamo ottenere sommando i punteggi dei dadi
Corso di Telecomunicazioni - AA 2011/2012 38
x punteggio Combinazioni possibili Pr{x}2 (1,1) 1/363 (1,2) (2,1) 2/364 (2,2) (3,1) (1,3) 3/365 (2,3) (3,2) (4,1) (1,4) 4/366 (3,3) (4,2) (2,4) (5,1) (1,5) 5/367 (3,4) (4,3) (5,2) (2,5) (6,1) (1,6) 6/368 (4,4) (5,3) (3,5) (6,2) (2,6) 5/369 (6,3) (3,6) (5,4) (4,5) 4/36
10 (5,5) (6,4) (4,6) 3/3611 (5,6) (6,5) 2/3612 (6,6) 1/36
Grossi/Venturino
Probabilità condizionata
Il verificarsi di un evento B può in generale influenzare il verificarsi di un altro evento A.
Si chiama probabilità condizionata dell’evento A rispetto all’evento B la probabilità che un evento A si realizzi nell’ipotesi che un altro evento B si sia già realizzato.
La probabilità condizionata dell’evento A rispetto all’evento B indica con il simbolo
Pr(A|B)
Corso di Telecomunicazioni - AA 2011/2012 39Grossi/Venturino
Esempio: lancio coppia di dadi
Calcolare la probabilità di ottenere il punteggio 8 (evento A), se si è sicuri che il risultato del lancio da un punteggio pari (evento B)
Corso di Telecomunicazioni - AA 2011/2012 40
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole ad B
Favorevole ad A e B
Grossi/Venturino
Esempio: lancio coppia di dadi
Pr{A} = 5/36 Pr{B} = 18/36 Pr{A|B} = 5/18
Corso di Telecomunicazioni - AA 2011/2012 41
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole ad B
Favorevole ad A e B
Grossi/Venturino
Esempio: lancio coppia di dadi
Calcolare la probabilità di ottenere il punteggio 11 (evento A), se si è sicuri che il risultato del lancio da un punteggio pari (evento B)
Corso di Telecomunicazioni - AA 2011/2012 42
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole ad B
Favorevole a A
Grossi/Venturino
Esempio: lancio coppia di dadi
Pr{A} = 2/36 Pr{B} = 18/36 Pr{A|B} = 0 (A e B sono incompatibili)
Corso di Telecomunicazioni - AA 2011/2012 43
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Favorevole ad B
Favorevole a A
Grossi/Venturino
Eventi indipendenti
L’evento A si dice indipendente dall’evento B se risulta:
Pr(A|B)=Pr(A)
Se A è indipendente da B, allora anche B è indipendente da A
Pr(B|A)=Pr(B)
Due eventi sono fra loro indipendenti se il verificarsi di uno non influenza in alcun
modo il verificarsi dell’altro.Corso di Telecomunicazioni - AA 2011/2012 44Grossi/Venturino
Esempio: lancio coppia di dadi
A = {il punteggio del dado blu è pari} B = {il punteggio del dado rosso è maggiore di 4}
Corso di Telecomunicazioni - AA 2011/2012 45
Favorevole ad A
Favorevole a B
Favorevole ad A e B
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Grossi/Venturino
Esempio: lancio coppia di dadi
Pr{A} = 18/36 = 1/2 Pr{B} = 12/36 = 1/3 Pr{A|B} = 6/12 =1/2 (A e B sono indipendenti)
Corso di Telecomunicazioni - AA 2011/2012 46
Favorevole ad A
Favorevole a B
Favorevole ad A e B
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Grossi/Venturino
Legge del prodotto
La probabilità dell’intersezione di due eventi A e B è uguale al prodotto della probabilità di uno degli eventi per la probabilità condizionata dell’altro:
Pr{A⋂B} = Pr{A|B} Pr{B} = Pr{B|A} Pr{A}
Se gli eventi sono indipendenti, la probabilità dell’intersezione è uguale al prodotto delle probabilità
Pr{A⋂B} = Pr{A} Pr{B}
Corso di Telecomunicazioni - AA 2011/2012 47Grossi/Venturino
Esempio: estrazione senza reinserimento
Si estraggono successivamente 2 palline da un’urna contenente 10 palline bianche (B) e 5 palline nere (N). Quale è la probabilità che esse siano entrambe nere? (NOTA: dopo la prima estrazione non viene rimessa nell’urna)
Le palline sono indistinguibili, se non per il colore bianco o nero.
Definiamo i seguenti eventi: A = {la prima pallina estratta è nera} B = {la seconda pallina estratta è nera} A⋂B={entrambe le palline estratte sono nere}
Corso di Telecomunicazioni - AA 2011/2012 48Grossi/Venturino
Esempio: estrazione senza reinserimento
Corso di Telecomunicazioni - AA 2011/2012 49
Pr{A} =numero casi favorevolinumero casi possibili
=5
15
Pr{B | A} =numero casi favorevolinumero casi possibili
=4
14
Pr{A ∩ B} = Pr{B | A}Pr{A} =4
145
15=
221
Grossi/Venturino
Esempio: tiro al bersaglio
Tre tiratori tirano al bersaglio. Le proprietà di centrare il bersaglio sono rispettivamente 0.75, 0.80, 0.90. Vogliamo calcolare: La probabilità che tutti e tre i tiratori facciamo
centro La probabilità che nessun tiratore faccia
centro La probabilità che almeno un tiratore faccia
centro
Corso di Telecomunicazioni - AA 2011/2012 50Grossi/Venturino
Esempio: tiro al bersaglio
A = {il primo tiratore fa centro} Pr{A} = 0.75 B = {il secondo tiratore fa centro} Pr{B} = 0.80 C = {il terzo tiratore fa centro} Pr{C} = 0.90
Ac = {il primo tiratore non fa centro} Pr{A} = 0.25 Bc = {il secondo tiratore non fa centro} Pr{B} = 0.20 Cc = {il terzo tiratore non fa centro} Pr{C} = 0.10
Corso di Telecomunicazioni - AA 2011/2012 51
E’ lecito assumere che un tiratore non è influenzato dalla bravura degli avversari A, B, C sono eventi indipendenti
Grossi/Venturino
Esempio: tiro al bersaglio
D = {tutti i tiratori fanno centro} = A ⋂ B ⋂ C
Pr{D} = Pr{A} Pr{B} Pr{C}=0.54
E = {nessun tiratore fa centro} = Ac ⋂ Bc ⋂ Cc
Pr{E} = Pr{Ac} Pr{Bc} Pr{Cc} = 0.005
F = {almeno un tiratore fa centro} = Ec
Pr{E} = 1 - Pr{Ec} = 0.995
Corso di Telecomunicazioni - AA 2011/2012 52Grossi/Venturino
Legge della probabilità totale
Supponiamo di dividere lo spazio dei campioni S in più insiemi mutuamente esclusivi:
S = H1 ⋃ H2 ⋃ H3
H1, H2 e H3 formano una partizione di S
Corso di Telecomunicazioni - AA 2011/2012 53
H1
H2
H3
SPAZIO DEI CAMPIONI (S)
Grossi/Venturino
Legge della probabilità totale
Per un generico evento A risulta: A = (A⋂H1) ⋃ (A⋂H2) ⋃ (A⋂H3) (A⋂H1), (A⋂H2) e (A⋂H3) sono mutuamente
esclusivi
Corso di Telecomunicazioni - AA 2011/2012 54
H1
H2
H3
SPAZIO DEI CAMPIONI (S)
A⋂H1
A⋂H2
A⋂H3
A
Grossi/Venturino
Legge della probabilità totale
Per un generico evento A risulta: A = (A⋂H1) ⋃ (A⋂H2) ⋃ (A⋂H3) (A⋂H1), (A⋂H2) e (A⋂H3) sono mutuamente
esclusivi
Vale la seguente legge della probabilità totale:
Pr{A} = Pr{A⋂H1} + Pr{A⋂H2} + Pr{A⋂H3} =
Pr{A|H1}Pr{H1} + Pr{A|H2}Pr{H2} + Pr{A|H3}Pr{H3}Corso di Telecomunicazioni - AA 2011/2012 55Grossi/Venturino
Esempio: estrazione da più urne
Consideriamo 5 urne Due urne contenenti ciascuna due palline rosse e una
nera (ipotesi H1) Un urna contenente dieci palline nere (ipotesi H2) Due urne contenenti ciascuna tre palline rosse e una
nera (ipotesi H3) Si scegli un urna a caso, e da essa si estrae una
pallina a caso
Corso di Telecomunicazioni - AA 2011/2012 56
Urna 1 Urna 2 Urna 3 Urna 4 Urna 5
H1H2
H3
Grossi/Venturino
Esempio: estrazione da più urne
Le urne sono indistinguibili dall’esterno, e dunque hanno la medesima probabilità di essere scelte Pr{H1} = 2/5 Pr{H2} = 1/5 Pr{H3} = 2/5
Corso di Telecomunicazioni - AA 2011/2012 57
H1
H2
H3
SPAZIO DEI CAMPIONI (S)
Grossi/Venturino
Esempio: estrazione da più urne
A = {la pallina scelta è rossa}
Pr{A|H1} = 2/3, Pr{A|H2} = 0, Pr{A|H3} = 3/4
Pr{A} = Pr{A|H1}Pr{H1}+Pr{A|H2}Pr{H3}+Pr{A|H3}Pr{H3} = 17/30
Corso di Telecomunicazioni - AA 2011/2012 58
H1
H2
H3
SPAZIO DEI CAMPIONI (S)
A⋂H1
A⋂H2
A⋂H3
AGrossi/Venturino
Esempio: collaudo apparecchi
Si devono collaudare 12 apparecchi telefonici di cui sono fabbricati nello stabilimento di Roma, 4 in quello di Milano, e 5 in quello di Firenze. Gli apparecchi costruiti a Roma passano il
collaudo con probabilità 0.9. Gli apparecchi costruiti a Milano passano il
collaudo con probabilità 0.8. Gli apparecchi costruiti a Firenze passano il
collaudo con probabilità 0.75. Trovare la probabilità che un apparecchio scelto
a caso passi il collaudo.Corso di Telecomunicazioni - AA 2011/2012 59Grossi/Venturino
Esempio: collaudo apparecchi
Definiamo i seguenti eventi H1 = {l’apparecchio proviene da Roma} H2 = {l’apparecchio proviene da Milano} H3 = {l’apparecchio proviene da Firenze} A = {l’apparecchio passa il collaudo}
Pr{H1} = 3/12, Pr{H2} = 4/12, Pr{H3} = 5/12
Pr{A|H1} = 0.9, Pr{A|H2} = 0.8, Pr{A|H1} = 0.75
Usando la legge della probabilità totale si ha:
Corso di Telecomunicazioni - AA 2011/2012 60
804.075.01258.0
1249.0
123
} Pr{H}H| Pr{A } Pr{H}H| Pr{A } Pr{H}H| Pr{APr{A} 332211
=++
=++=
Grossi/Venturino
Esempio: Superenalotto
Nel superenalotto vengono estratti 6 numeri (senza reinserimento) da un’urna che ne contiene 90
Corso di Telecomunicazioni - AA 2011/2012 61
Primo numero estratto
Quinto numero estratto
Quarto numero estratto
Terzo numero estratto
Secondo numero estratto
Sesto numero estratto
90 scelte 89 scelte 88 scelte 87 scelte 86 scelte 85 scelte
Possibili sestine = 90 x 89 x 88 x 87 x 86 x 85 = 448 282 533 600
Numeri da 1 a 90
Grossi/Venturino
Esempio: Superenalotto
Per vincere non è importante l’ordine con cui vengono estratti i numeri
Ad esempio, le sestine 1 2 3 4 5 6 e 2 1 3 4 5 6 sono equivalenti.
Quante sono le sestine che contengono i numeri 1, 2, 3, 4, 5, 6 in qualunque ordine?
Corso di Telecomunicazioni - AA 2011/2012 62Grossi/Venturino
Superenalotto
Corso di Telecomunicazioni - AA 2011/2012 63
Posizione 1
Posizione 5
Posizione 4
Posizione 3
Posizione 2
Posizione 6
6 scelte 5 scelte 4 scelte 3 scelte 2 scelte 1 scelte
Possibili sestine = 6 x 5 x 4 x 3 x 2 x 1 = 720
1 6234
5
Grossi/Venturino
Superenalotto
Concludiamo che la probabilità di vincere giocando i numeri 1, 2, 3, 4, 5, 6 è
Verificare che ogni altro gruppo di sei numeri (ad esempio: 4, 8, 80, 17, 11, 89) ha la stessa probabilità di essere estratto.
Corso di Telecomunicazioni - AA 2011/2012 64
630 614 6221
600 533 282 448720
possibili casi numerofavorevoli casi numero
==
Grossi/Venturino
CENNI ALLA TEORIA DEI GIOCHI
65Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Guadagno medio
Consideriamo un generico esperimento aleatorio che può avere M possibili risultati.
Assumiamo che il risultato si si verifica con probabilità pi.
Consideriamo un gioco dove il giocatore guadagna una somma xi se esce il risultato si: xi>0 il giocatore ha una vincita xi<0 il giocatore ha una perdita
Corso di Telecomunicazioni - AA 2011/2012 66
Risultato esperimento s1 s2 s3 … sM
Probabilità p1 p2 p3 … pM
Guadagno x1 x2 x3 … xM
Grossi/Venturino
Guadagno medio
Si definisce guadagno medio del gioco la seguente quantità
G = x1p1+ x2p2+ x3p3+…+ xMpM
G>0 il gioco è favorevole al giocatore G=0 il gioco è equo G<0 il gioco è sfavorevole al giocatore
Corso di Telecomunicazioni - AA 2011/2012 67
Risultato esperimento s1 s2 s3 … sM
Probabilità p1 p2 p3 … pM
Guadagno x1 x2 x3 … xM
Grossi/Venturino
Esempio: estrazione da un urna
Un urna contiene 28 palline 10 palline bianche 7 nere 5 rosse 6 blu
Il giocatore paga un prezzo di 30 euro per partecipare al gioco (posta).
Si estraggono a caso due palline. Se entrambe le palline sono rosse il giocatore
guadagna 100 euro (evento s1) Se solo una pallina è rossa il giocatore guadagna 50
euro (evento s2) Altrimenti il giocatore perde la somma scommessa
(evento s3)
Corso di Telecomunicazioni - AA 2011/2012 68Grossi/Venturino
Esempio: estrazione da un urna
Probabilità di guadagnare 100
Probabilità di guadagnare 50
Probabilità di perdere la posta
Corso di Telecomunicazioni - AA 2011/2012 69
1895
274
285
1 ==p
378115
275
2823
2741
285
2 =+
−=p
( )3782531 213 =+−= ppp
Grossi/Venturino
Esempio: estrazione da un urna
Il gioco è sfavorevole al giocatore:
Calcoliamo quanto deve valere la posta scommessa per avere un gioco equo:
Corso di Telecomunicazioni - AA 2011/2012 70
G =1005
189+ 50
115378
− 30253378
≅ −2.22
68.26
0378253
37811550
1895100
≅⇓
=−+=
y
yG
Grossi/Venturino
Esempio: gioco delle tre carte
Abbiamo tre carte: un re, un fante, ed un asso Un giocatore paga una posta di X EURO per
partecipare al gioco Se indovina la posizione dell’asso guadagna 90
euro, altrimenti perde la posta. Calcolare quanto deve valere la posta X affinché
il gioco sia equo per il giocatore.
Corso di Telecomunicazioni - AA 2011/2012 71Grossi/Venturino
Esempio: gioco delle tre carte
Probabilità di trovare l’asso (vincere)
Probabilità di non trovare l’asso (perdere)
Guadagno medio:
Corso di Telecomunicazioni - AA 2011/2012 72
31
1 =p
32
2 =p
Grossi/Venturino
G = 9013
− X23
< 0, se X > 45 (sfavorevole)= 0, se X = 45 (equo) > 0, se X < 45 (favorevole)
ATTENZIONE
Quando il gioco è equo, su un numero molto grande di partire, in media, né si vince né si perde tuttavia questa previsione è realistica solo se il giocatore ha una disponibilità di soldi illimitata.
Se infatti il giocatore ha un tetto massimo di spesa, potrebbe accadere di perdere più partire consecutivamente e non essere più in grado di continuare il gioco si parla in questo caso di rovina del giocatore.
Corso di Telecomunicazioni - AA 2011/2012 73Grossi/Venturino
Esempio: gioco delle tre carte
Corso di Telecomunicazioni - AA 2011/2012 74
Assumiamo che Il giocatore ha in tasca 90 euro e che il gioco sia equo.
Calcoliamo la probabilità che il giocatore si rovini entro cinque partite.
90
45
0 135
90
45
0 135
180
135 270
225
180
135 270
315
270 405
180
135
90
45
0 135
180
135 270
225
180
135 270
315
270 405
270
225
270
225 360
315
270 405
360
315
270 405
450
405 540
Grossi/Venturino
Esempio: gioco delle tre carte
Corso di Telecomunicazioni - AA 2011/2012 75
Possibilità di rovina in cinque partite A={Perdo la prima e la seconda} B= {Perdo la prima, vinco la seconda, perdo la terza,
perdo la quarta e perdo la quinta} C={Vinco la prima, perdo la seconda, perdo la terza,
perdo la quarta e perdo la quinta}
90
45
0 135
90
45
0 135
180
135 270
225
180
135 270
315
270 405
180
135
90
45
0 135
180
135 270
225
180
135 270
315
270 405
270
225
270
225 360
315
270 405
360
315
270 405
450
405 540
Grossi/Venturino
Esempio: gioco delle tre carte
Corso di Telecomunicazioni - AA 2011/2012 76
Possibilità di rovina in cinque partite A={Perdo la prima e la seconda} B= {Perdo la prima, vinco la seconda, perdo la terza,
perdo la quarta e perdo la quinta} C={Vinco la prima, perdo la seconda, perdo la terza,
perdo la quarta e perdo la quinta}
57.032
32
32
32
31
32
32
32
31
32
32
32
}CPr{}BPr{}APr{}rovinaPr{
≅
++=
++=
Grossi/Venturino
Esempio: lancio di dadi
Due giocatori A e B giocano con il lancio di due dadi regolari. Se escono 2 numeri pari A paga a B 10 euro
(evento E1) Se escono 2 numeri dispari B paga ad A 5
euro (evento E2) Se escono un numero pari ed uno dispari B
paga ad A 2 euro (evento E3)
Stabilire se il gioco è favorevole ad A o a BCorso di Telecomunicazioni - AA 2011/2012 77Grossi/Venturino
Esempio: lancio di dadi
Pr{E1} = 9/36 = 1/4
Corso di Telecomunicazioni - AA 2011/2012 78
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Grossi/Venturino
Esempio: lancio di dadi
Pr{E2} = 9/36 = 1/4
Corso di Telecomunicazioni - AA 2011/2012 79
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Grossi/Venturino
Esempio: lancio di dadi
Pr{E3} = 18/36 = 1/2
Corso di Telecomunicazioni - AA 2011/2012 80
POSSIBILI RISULTATI ESPERIMENTO1 2 3 4 5 6
1 (1,1) (1,2) (1,3) (1,4) (1,5) (1,6)2 (2,1) (2,2) (2,3) (2,4) (2,5) (2,6)3 (3,1) (3,2) (3,3) (3,4) (3,5) (3,6)4 (4,1) (4,2) (4,3) (4,4) (4,5) (4,6)5 (5,1) (5,2) (5,3) (5,4) (5,5) (5,6)6 (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Grossi/Venturino
Esempio: lancio di dadi
Corso di Telecomunicazioni - AA 2011/2012 81
G(A) = 514
+ 212
−1014
= −0.25 → guadagno medio A
G(B) =10 14
− 5 14
− 2 12
= 0.25 → guadagno medio B
Il gioco è favorevole al giocatore B
Grossi/Venturino
Esempio: quiz televisivo
Partecipate ad una trasmissione televisiva assieme ad altri concorrenti. Alla fine del gioco siete rimasti in tre, ognuno con una busta chiusa in mano. Due buste sono vuote, mentre l’altra contiene un assegno di €10000. Avete due possibilità: aprire la vostra busta Scambiarla con quella di un altro concorrente
Cosa fate?
Corso di Telecomunicazioni - AA 2011/2012 82Grossi/Venturino
Esempio: quiz televisivo
Opzione 1: apro la busta Vinco 10000 con probabilità 1/3 Non vinco nulla con probabilità 2/3 Guadagno medio = 10000/3
Opzione 2: cambio busta Con probabilità 1/3 cambio la busta vincente con una vuota Con probabilità 2/3 ho una busta vuota
Con probabilità 1/2 la cambio con un’altra busta vuota Con probabilità 1/2 la cambio con la busta vincente
Guadagno medio = 10000/3
Corso di Telecomunicazioni - AA 2011/2012 83
Le due scelte sono equivalenti Grossi/Venturino
VARIABILI ALEATORIE
84Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Variabili aleatorie
Una variabile aleatoria (v.a.) X è una funzione del risultato di un esperimento aleatorio
Esempi:
Esperimento: lancio di una moneta.
Esperimento: lancio di una coppia di dadi. X = somma delle 2facce
Esperimento: gioco delle 3 carte. X = guadagno a fronte di una puntata di 10 €
Corso di Telecomunicazioni - AA 2011/2012 85Grossi/Venturino
X =1, se esce testa 0, se esce croce
Variabili aleatorie: valor medio
X v.a. {x1, x2,…, xM} = valori assunti da X {p1, p2,…, pM} = probabilità; pi = Pr{X = xi}
Il valor medio di X è:
Esempio: lancio di una moneta
v.a.
Valor medio:
Corso di Telecomunicazioni - AA 2011/2012 86Grossi/Venturino
MM xpxpxpX +++= 2211][E
X =1, se esce testa 0, se esce croce
E[X] =12
⋅ 1+12
⋅ 0 =12
valori x1 =1 x2 = 0probabilità p1 =1/2 p2 =1/2
Variabili aleatorie: valor medio
Esempio: lancio di una coppia di dadi
v.a. X = somma delle 2 facce
Valor medio:
Corso di Telecomunicazioni - AA 2011/2012 87Grossi/Venturino
E[X] =136
⋅ 2 +236
⋅ 3+3
36⋅ 4 +
436
⋅ 5 +536
⋅ 6 +636
⋅ 7 +
+536
⋅ 8 +436
⋅ 9 +3
36⋅ 10 +
236
⋅ 11+136
⋅ 12 =
= 7
valori 2 3 4 5 6 7 8 9 10 11 12probabilità
136
236
336
436
536
636
536
436
336
236
136
Variabili aleatorie: valor medio
Esempio: gioco delle 3 carte (se indovino, vinco 3 volte la posta, altrimenti perdo la posta)
v.a. X = guadagno con una posta di 10 €
Valor medio:
Corso di Telecomunicazioni - AA 2011/2012 88Grossi/Venturino
E[X] =13
⋅ 20 +23
⋅ (−10) = 0
valori 20 € −10 €probabilità 1/3 2 /3
MISURA DELL’INFORMAZIONE
89Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Considerazioni preliminari
Un sistema di telecomunicazione digitale è un insieme di apparati atti a trasferire l’informazione da una sorgente numerica ad una destinazione “lontana”.
Corso di Telecomunicazioni - AA 2011/2012 90
Sorgente numerica canale destinatario
Grossi/Venturino
Domande
Cosa è l’informazione?
Si può misurare l'informazione racchiusa in un messaggio?
Fino a che punto si può “sintetizzare” o “comprimere” un messaggio senza che si perda l'informazione in esso contenuta?
Quanto deve essere “buono” o “veloce” un canale di comunicazione per potervi trasmettere un messaggio senza che si perda l'informazione in esso contenuta?
Corso di Telecomunicazioni - AA 2011/2012 91Grossi/Venturino
La teoria dell’informazione
Claude E. Shannon ha sviluppato nel 1948 una raffinata teoria matematica che ci permette di rispondere a queste domande e che è alla base di tutti i moderni sistemi di comunicazione digitali.
Corso di Telecomunicazioni - AA 2011/2012 92Grossi/Venturino
Variabili aleatorie e Informazione
Esempio: messaggio = “domani sorge il sole” il messaggio è deterministico il destinatario non acquisisce alcuna
informazione: sa già che domani il sole sorgerà Se il messaggio è deterministico non porta
informazione Il messaggio ha natura aleatoria
Corso di Telecomunicazioni - AA 2011/2012 93Grossi/Venturino
mittente destinatariomessaggio
Il messaggio è rappresentabilecome una variabile aleatoria
Esempio:
È una variabile aleatoriaCorso di Telecomunicazioni - AA 2011/2012 94Grossi/Venturino
[ ]
messaggio
messaggio del carattere ultimo
messaggio del carattere 2
messaggio del carattere 1domani" vediamoci" = Messaggio
1721
17
o2
o1
=⇒
==
=
=
Y
XXXYX
XX
Entropia di una variabile aleatoria
X v.a.
H(X) = entropia di X, è definita da
H(X) si misura in bitCorso di Telecomunicazioni - AA 2011/2012 95Grossi/Venturino
valori x1 x2 … xM
probabilità p1 p2 … pM
1log ++1log 1log )H( 22
221
21M
M pp
pp
ppX +=
Esempio
X v.a.
Corso di Telecomunicazioni - AA 2011/2012 96Grossi/Venturino
valori x1 x2 x3 x4
probabilità 1/2 1/4 1/8 1/8
H(X) = 12
log21
1/2+
14
log21
1/4+
18
log21
1/8 + 1
8 log2
11/8
=12
log2 2 +14
log2 4 +18
log2 8 +18
log2 8
=12
+14
2 +18
3 + 18
3 =74
=1.75 [bit]
Entropia e incertezza
H(X) è una misura dell’incertezza di X:
più è grande, più la variabile aleatoria è incerta
Corso di Telecomunicazioni - AA 2011/2012 97Grossi/Venturino
Entropia e incertezza: esempio
Gioco: Giulia pensa una lettera tra {a, b, c, d} e Marco tenta di indovinarla col minor numero di domande a risposta si/no
Marco sa che nel 50% dei casi, Giulia pensa ad “a”, nel 25% dei casi a “b”, e nel rimanente 25% dei casi a “c” o “d” indifferentemente
Marco deve sfruttare questa informazione. Se la lettera “a” è la più probabile, la prima domanda sarà: si tratta della lettera “a”?
Corso di Telecomunicazioni - AA 2011/2012 98Grossi/Venturino
Entropia e incertezza: esempio
Migliore sequenza di domande da fare:
Corso di Telecomunicazioni - AA 2011/2012 99Grossi/Venturino
La lettera è “a”?
La lettera è “b”?
La lettera è “c”?
SI NO
SI NO
NOSI
indovinata in1 domanda
indovinata in3 domande
indovinata in2 domanda
Entropia e incertezza: esempio
Q = numero di domande fatte. È una v.a. Q = 1, se Giulia aveva pensato alla “a”, cosa
che accade con probabilità ½ Q = 2, se Giulia aveva pensato alla “b”, cosa
che accade con probabilità ¼ Q = 3, se Giulia aveva pensato alla “c” o alla
“d”, cosa che accade con probabilità ¼
Corso di Telecomunicazioni - AA 2011/2012 100Grossi/Venturino
Il numero medio che di domande che Marco fa è:
E[Q] =12
⋅ 1+14
⋅ 2 +14
⋅ 3 =74
=1.75
Entropia e incertezza: esempio
X = lettera pensata da Giulia. È una v.a.
H(X) = 1.75 bit (calcolata nell’esempio precedente)
H(X) = E[Q]
Corso di Telecomunicazioni - AA 2011/2012 101Grossi/Venturino
valori a b c d
probabilità 1/2 1/4 1/8 1/8
Entropia e incertezza: esempio
In generale, l’entropia di una v.a. è approssimativamente uguale al numero medio di domande binarie (= a risposta si/no, ecco perché si misura in bit) necessarie per indovinarla
Quindi: H(X) grande servono in media molte
domande per indovinarla X è molto incerta H(X) piccola servono in media poche
domande per indovinarla X è poco incerta
H(X) = incertezza di XCorso di Telecomunicazioni - AA 2011/2012 102Grossi/Venturino
Entropia e informazione
H(X) è una misura dell’informazione che porta X:
più è grande, più la variabile aleatoria porta informazione
Corso di Telecomunicazioni - AA 2011/2012 103Grossi/Venturino
Entropia e informazione: esempio
Si deve deve immagazzinare sulla memoria di un sensore meteorologico la situazione meteo giornaliera sull’Aspromonte, in Calabria
Si è interessati alle sole condizioni: sereno, nuvoloso, pioggia, grandine
Da osservazioni passate si è visto che è sereno nel 50% dei casi, nuvoloso nel 25% dei casi e indifferentemente pioggia o grandine nel rimanente 25% dei casi
Si vogliono utilizzare, in media, il minor numero possibile di bit per immagazzinare questa informazione
Corso di Telecomunicazioni - AA 2011/2012 104Grossi/Venturino
Entropia e informazione: esempio
Migliore codifica binaria:
Corso di Telecomunicazioni - AA 2011/2012 105Grossi/Venturino
valore codificasereno 0
nuvoloso 10pioggia 110
grandine 111
Entropia e informazione: esempio
L = numero di bit utilizzati. È una v.a. L = 1, se è sereno, cosa che accade con
probabilità ½ L = 2, se nuvoloso, cosa che accade con
probabilità ¼ L = 3, se c’è pioggia o grandine, cosa che
accade con probabilità ¼
Corso di Telecomunicazioni - AA 2011/2012 106Grossi/Venturino
Il numero medio di bit utilizzati per immagazzinare l’informazione meteo è:
E[L] =12
⋅ 1+14
⋅ 2 +14
⋅ 3 =74
=1.75
Entropia e informazione: esempio
X = situazione meteo del giorno. È una v.a.
H(X) = 1.75 bit (calcolata nell’esempio precedente)
H(X) = E[L]
Corso di Telecomunicazioni - AA 2011/2012 107Grossi/Venturino
valori sereno nuvoloso pioggia grandine
probabilità 1/2 1/4 1/8 1/8
Entropia e informazione: esempio
In generale, l’entropia di una v.a. è approssimativamente uguale al numero medio di bit (ecco perché si misura in bit) necessari in per descriverla/rappresentarla
Quindi: H(X) grande servono in media molti bit
per descriverla X porta molta informazione H(X) piccola servono in media pochi bit
per descriverla X porta poca informazione
H(X) = informazione portata da X
Corso di Telecomunicazioni - AA 2011/2012 108Grossi/Venturino
Entropia/incertezza/informazione
Corso di Telecomunicazioni - AA 2011/2012 109Grossi/Venturino
H(X) misura l’incertezza di X e dunque l’informazione portata da X
H(X) grande X molto incerta X porta molta informazione
H(X) piccola X poco incerta X porta poca informazione
Entropia: proprietà 1
X v.a.H(X) = 1.75 bit
Y v.a.
H(Y) = 2 bit
Y ha un’entropia maggiore è più incerta e porta più informaizone
L’entropia è massima se i valori sono equiprobabili Corso di Telecomunicazioni - AA 2011/2012 110Grossi/Venturino
valori x1 x2 X3 x4
probabilità 1/2 1/4 1/8 1/8
valori y1 y2 y3 y4
probabilità 1/4 1/4 1/4 1/4
Entropia: proprietà 2
Y v.a.
H(Y) = 2 bit Z v.a.
H(Z) = 3 bit
Z ha un’entropia maggiore è più incerta e porta più informaizone
L’entropia cresce all’aumentare del numero di valoriCorso di Telecomunicazioni - AA 2011/2012 111Grossi/Venturino
valori y1 y2 y3 y4
probabilità 1/4 1/4 1/4 1/4
valori z1 z2 z3 z4 z5 z6 z7 z8
probabilità 1/8 1/8 1/8 1/8 1/8 1/8 1/8 1/8
Misura dell’informazione
L’informazione si misura in bit (binary unit).
Un bit è la quantità di informazione che porta una v.a. con 2 valori equiprobabili
Una v.a. con M simboli equiprobabili genera log2(M) bit di informazione.
Corso di Telecomunicazioni - AA 2011/2012 112Grossi/Venturino
ATTENZIONE
La parola bit ha due significati diversi, a seconda del contesto in cui la si usa: un bit è l'unità di misura dell'informazione
(dall'inglese "binary unit"), definita come la quantità minima di informazione che serve a discernere tra due alternative equiprobabili.
un bit è una cifra binaria, (in inglese "binarydigit") ovvero uno dei due simboli del sistema numerico binario, classicamente chiamati zero(0) e uno (1).
Corso di Telecomunicazioni - AA 2011/2012 113Grossi/Venturino
ATTENZIONE Un registro contiene 2 celle, ognuna
delle quali può trovarsi in 2 stati (1 e 0) In informatica sono 2 bit di memoria In teoria dell’informazione dipende da cosa c’è
scritto dentro Se le 2 celle si trovano nello stato allora
portano 0 bit di informazione Se nelle 2 celle è immagazzinato il risultato del
lancio di 2 monete bilanciate allora portano 2bit di informazione
In generale l’informazione è compresa tra 0 e 2Corso di Telecomunicazioni - AA 2011/2012 114Grossi/Venturino
11
Entropia di una sorgente stazionaria senza memoria
Consideriamo una sorgente discreta stazionaria senza memoria con alfabeto A = {a1,…,aM}.
Un messaggio emesso dalla sorgente è una concatenazione di simboli dell'alfabeto.
L’emissione di uno dei simboli dell’alfabeto genera un’informazione.
Corso di Telecomunicazioni - AA 2011/2012 115Grossi/Venturino
Entropia di una sorgente stazionaria senza memoria
X(n) simboli emesso al tempo “n”
X(n) ∈ AX = {a1,…,aM}
AX = {a1,…,aM} alfabeto discreto
Pr{X(n) = ai} = pi (stazionaria = non dipende da n)
Simboli successivi sono emessi in maniera indipendente (senza memoria)
Corso di Telecomunicazioni - AA 2011/2012 116
Sorgente digitale,stazionaria e senza memoria
… X(-1), X(0), X(1), X(2), …
ImmaginiTestoAudioVideo….
Qual è l’informazione media emessa dalla sorgente?
Grossi/Venturino
Entropia di una sorgente stazionaria senza memoria
Corso di Telecomunicazioni - AA 2011/2012 117
Simboli a1 a2 … aM
Probabilità p1 p2 … pM
Entropiadella
sorgente
H = p1 log2(1/p1) + p2 log2(1/p2) +… + pM log2(1/pM)
[bit/simbolo]
L’entropia di una sorgente è l’informazione media associata all’emissione di un simbolo
Grossi/Venturino
Esercizio
Consideriamo una sorgente senza memoria che emette a caso un numero intero fra uno e sei (ottenuto ad esempio lanciando un dado equilibrato)
Corso di Telecomunicazioni - AA 2011/2012 118
Simboli 1 2 3 4 5 6Probabilità p1=1/6 p2=1/6 p3=1/6 p4=1/6 p5=1/6 p6=1/6
Informazione log2(6) log2(6) log2(6) log2(6) log2(6) log2(6)
Entropia della sorgente
H = (1/6) log2(6) + … + (1/6) log2(6)
= log2(6) = 2.585 [bit/simbolo]
Grossi/Venturino
Esercizio
Calcolare il contenuto informativo medio di sorgente con 4 simboli, aventi probabilità pari a 0.125, 0.25, 0.125 e 0.5.
Se la sorgente emette simboli con una frequenza Rspari a 1200 simboli/s (simboli al secondo) calcolare la frequenza (tasso) di informazione Rb.
Corso di Telecomunicazioni - AA 2011/2012 119
Simboli a1 a2 a3 a4
Probabilità p1=0.125 p2=0.25 p3=0.125 p4=0.5
Entropia della sorgente
Tasso di informazione
Rb=HxRs=1200 simboli/s x 1.75 bit/simbolo= 2100 bit/s
H = 0.125 log21
0.125
+ 0.25 log2
10.25
+ 0.125 log2
10.125
+ 0.5 log2
10.5
= 0.375 + 0.5 + 0.375 + 0.5( ) = 1.75 bit/simbolo
Grossi/Venturino
Trasferimento dell’informazione
Una sorgente che emetta un messaggio genera “informazione” e pone il destinatario in una situazione di “incertezza a priori”.
Durante la trasmissione il canale potrebbe distruggere parte dell’informazione emessa dalla sorgente.
Leggendo il messaggio all’uscita del canale, il destinatario rimuove parte o tutta l’incertezza a priori sul messaggio della sorgente. L’incertezza rimossa è pari all’informazione acquisita leggendo il messaggio
120Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Trasferimento dell’informazione
Entropia = Incertezza a priori
Flusso Informativo = Incertezza a priori –Incertezza a posteriori
121Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Canale di comunicazione
Un canale di comunicazione è un meccanismo che associa ad ogni simbolo (messaggio) emesso dalla sorgente un nuovo simbolo (messaggio), non necessariamente uguale a quello originariamente emesso, disponibile alla destinazione.
X Y
X: Messaggio emesso dalla sorgente
Y: Messaggio disponibile al destinatario
Sorgente numerica
Canalediscreto destinatario
122Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Relazione tra incertezze e flusso informativo
H(X) Incertezza a priori su X (o Entropia)
H(X|Y) Incertezza a posteriori su X (una volta osservato Y)
I(X;Y) = H(X)-H(X|Y) Incertezza rimossa su X dopo l’osservazione di Y (ovvero, flusso informativo attraverso il canale)
123Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Relazione tra incertezze e flusso informativo
Un canale è inutile seIncertezza a priori = Incertezza a posteriori
I(X;Y) = H(X) – H(X|Y) = 0cioè tutta l’informazione portata da X va persa nel canale
Un canale è ideale seIncertezza a posteriori = 0
I(X;Y) = H(X) – H(X|Y) = H(X)cioè tutta l’informazione portata da X arriva al destinatario
124Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Relazione tra incertezze e flusso informativo
Un canale reale è in genere tale che0 < Incertezza a posteriori < Incertezza a priori
0 < H(X) – H(X|Y) = I(X;Y) < H(X)Cioè una parte dell’informazione portata da X va persa nel canale e la restante parte arriva al destinatario.
125Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Esempio: invio lettera alfabeto
Una sorgente emette a caso una lettera da un alfabeto di 26 lettere.
La lettera emessa “viaggia” in un ambiente rumoroso fino ad una destinazione.
La destinazione riesce solo a capire che la lettera emessa è una vocale, ma non riesce a ricostruire quale.
DOMANDA: Quale è il flusso informativo attraverso il canale?
126Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Esempio: invio lettera alfabeto
H(X)= log2(26) ≈ 4.67 bit Incertezza a priori su quale delle 26 lettere dell’alfabeto è stata emessa.
H(X|Y)= log2(5) ≈ 2.3 bit Incertezza a posteriori su quale delle 5 vocali è stata emessa.
I(X;Y)=H(X)-H(X|Y)= log2(26)- log2(5) ≈ 2.37 bit flusso informativo sul canale.
127Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Esempio: invio carta
Una sorgente estrae una carta da un mazzo di carte napoletane.
La carta emessa “viaggia” in un ambiente rumoroso fino ad una destinazione
La destinazione riesce solo a capire che la lettera emessa è una carta di “coppe”, ma non riesce a ricostruire quale.
Problema: Quale è il flusso informativo attraverso il canale?
128Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Esempio: invio carta
H(X) = log2(40) ≈ 5.3 bit Incertezza a priori su quale delle 40 carte del mazzo è stata emessa.
H(X|Y) = log2(10) ≈ 3.3 bit Incertezza a posteriori su quale delle 10 carte di coppe è stata emessa.
I(X;Y) = H(X) - H(X|Y) = log2(40)-log2(10) ≈ 2 bit.
129Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
CODIFICA DI SORGENTE
130Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Indovinello
Proviamo a completare il seguente testo:
Corso di Telecomunicazioni - AA 2011/2012 131
D I T U # T E L E C O S E # I C U R E L A P I U’# E R T A E’ I L # U B B I O ( B R E C H T )
Grossi/Venturino
Indovinello
Proviamo a completare il seguente testo:
Corso di Telecomunicazioni - AA 2011/2012 132
D I T U # T E L E C O S E # I C U R E L A P I U’# E R T A E’ I L # U B B I O ( B R E C H T )
Grossi/Venturino
DI TUTTE LE COSE SICURE LA PIU’CERTA E’ IL DUBBIO (BRECHT)
Compressione senza perdite
Il messaggio emesso da una sorgente spesso è ridondante, cioè contiene un numero di simboli (caratteri) maggiore di quelli effettivamente necessari per descriverne il contenuto informativo.
Comprimere senza perdite un messaggio significa trovare una rappresentazione alternativa che riduca il numero di simboli (caratteri) utilizzati senza però alterare il contenuto informativo.
Corso di Telecomunicazioni - AA 2011/2012 133Grossi/Venturino
Compressione senza perdite
Consente di risparmiare tempo nella spedizione.
Corso di Telecomunicazioni - AA 2011/2012 134
messaggio originale
messaggio originale
messaggio compresso
compressione
decompressione
IDENTICI !
Grossi/Venturino
Schema di comunicazione di Shannon
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 135
sorgentenumerica
codifica di sorgente
codifica di canale
modulatoredemodulatore
destinatariodecodifica di sorgente
decodifica di canale
canale
Compressione senza perdite
Sfrutta la memoria e le proprietà di ricorrenza statistiche della sorgente.
Una sorgente con memoria emette simboli successivi seguendo alcune regole predeterminate (ad esempio le regole della grammatica e della sintassi della lingua italiana nel caso di un messaggio di testo).
Simboli successivi emessi da una sorgente con memoria non sono fra loro indipendenti alcuni simboli si possono estrapolare da altri.
Alcuni simboli sono emessi più frequentemente (cioè con probabilità maggiore).
Corso di Telecomunicazioni - AA 2011/2012 136Grossi/Venturino
Compressione del testo
La parola quadro potrebbe essere scritta nella forma qadro, visto che dopo una q iniziale viene sempre una u (tranne che nella parola soqquadro), per cui la stessa informazione viene data trasmettendo 5 lettere invece di 6.
Il numero 3.8888888884 contiene la cifra 8 che si ripete 9 volte. Una rappresentazione più efficiente potrebbe essere 3.8[9]4 che utilizza 7 caratteri invece che 12.
Corso di Telecomunicazioni - AA 2011/2012 137Grossi/Venturino
Compressione del testo
Una doppia consonante è sempre seguita da una vocale. Spesso la vocale può essere facilmente estrapolata dal contesto e dunque essere omessa nella trasmissione. successo succsso alligatore allgatore un pappagallo un pappgall una giraffa una giraff
Corso di Telecomunicazioni - AA 2011/2012 138Grossi/Venturino
Compressione di un’immagine
In un’immagine, pixel vicini hanno spesso lo stesso colore (omogeneità spaziale)
Non è necessario trasmettere tutti i pixel dell’immagine
Corso di Telecomunicazioni - AA 2011/2012 139Grossi/Venturino
Compressione di un’immagine
Supponiamo di avere una semplice immagine composta da sedici pixel
Invece di trasmettere la sequenza rosso-rosso-rosso-rosso-rosso-rosso-rosso-rosso-rosso-rosso-verde-verde-blu-blu-blu-rosso, possiamo trasmettere la sequenza 10 rossi -> 2 verdi -> 3 blu -> 1 rosso.
È facile capire come immagini con vaste aree di colore uniforme vengano molto compresse.
Corso di Telecomunicazioni - AA 2011/2012 140Grossi/Venturino
Compressione di un video
In un video, due o più frame successivi hanno solo pochi pixel diversi (omogeneità temporale)
Possiamo trasmettere solamente il colore e la posizione dei pixel che sono cambiati rispetto al frame precedente.
Corso di Telecomunicazioni - AA 2011/2012 141Grossi/Venturino
Codifica binaria dei simboli
Supponiamo di voler trovare un codice per convertire in binario la seguente frase:
SHE-SELLS-SEA-SHELLS
La frase contiene 20 caratteri.
Ogni carattere può assumere 6 possibili valori: “A”, “H”, “-”, “E”, “L”, “S”.
Corso di Telecomunicazioni - AA 2011/2012 142Grossi/Venturino
Codice a lunghezza fissa
Un possibile codice binario a lunghezza fissa è il seguente:
La trasmissione del messaggio richiede complessivamente 60 bit (3 bit per carattere).
Corso di Telecomunicazioni - AA 2011/2012 143
simbolo codice binario 1
0 A 000
1 H 001
2 - 010
3 E 011
4 L 100
5 S 101
Grossi/Venturino
Codice a lunghezza fissa
Vantaggi univocamente decifrabile ogni lettera può essere decifrata senza decifrare
le precedenti o le successive (accesso casuale)
Corso di Telecomunicazioni - AA 2011/2012 144
SLLEHS
AES
SLLES
EHS
101100100011001101
010000011101
010101100100011101
010011001101
−
−
−
simbolo codice binario 1
A 000
H 001
- 010
E 011
L 100
S 101
Grossi/Venturino
Codice a lunghezza variabile
I simboli dell’alfabeto non hanno tutti la stessa importanza alcuni simboli sono più frequenti nel messaggio.
Proviamo ad utilizzare un codice che assegna stringhe più corte a simboli più frequenti.
La trasmissione del messaggio richiede ora 49 bit (cioè 2.45 bit per carattere).
Corso di Telecomunicazioni - AA 2011/2012 145
simbolo frequenza codice binario 2
A 1 0000
H 2 0001
- 3 001
E 4 10
L 4 01
S 6 11
Grossi/Venturino
Codice a lunghezza variabile
Vantaggi univocamente decifrabile più efficiente del codice a lunghezza fissa
Svantaggi per decifrare una lettera è necessario aver decifrato le precedenti
Corso di Telecomunicazioni - AA 2011/2012 146
SLLEHS
AES
SLLES
EHS
11010110000111
00100001011
0011101011011
00110000111
−
−
−
Grossi/Venturino
simbolo frequenza codice binario 2
A 1 0000
H 2 0001
- 3 001
E 4 10
L 4 01
S 6 11
Codice a lunghezza variabile
Consideriamo un altro codice a lunghezza variabile:
La trasmissione del messaggio richiederebbe solo 30 bit (cioè 1.5 bit per carattere).
Perché non usiamo questo codice?
Corso di Telecomunicazioni - AA 2011/2012 147
simbolo frequenza codice binario 3
A 1 10
H 2 01
- 3 11
E 4 00
L 4 1
S 6 0
Grossi/Venturino
Codice a lunghezza variabile
La sequenza di bit codificata è:001001100011011000101101000110
Proviamo a decodificarla:
Corso di Telecomunicazioni - AA 2011/2012 148
simbolo codice binario 3
A 10
H 01
- 11
E 00
L 1
S 0“SSLSS” (0 0 1 0 0)
00100
“EAS” (00 10 0)
“SSLE” ( 0 0 1 00 )
“SHE” (0 01 00)
Grossi/Venturino
Codici binari a prefisso
Corso di Telecomunicazioni - AA 2011/2012 149
simbolo codice binario 1 codice binario 2 codice binario 3A 000 0000 10
H 001 0001 01
- 010 001 11
E 011 10 00
L 100 01 1
S 101 11 0
CODICE A PREFISSO CODICE AMBIGUO
Condizione sufficiente affinché un codice sia univocamente decifrabile è che nessuna parola codice sia prefisso di un’altra
parola codice ( CODICE A PREFISSO o ISTANTANEO).
I codici a prefisso permettono di effettuare una decodifica istantanea del messaggio e sono da preferire.
Grossi/Venturino
Albero binario
Un albero binario è una struttura dati formata da nodi collegati tra loro da rami.
Ogni nodo (padre) può avere due figli (destro e sinistro).
Corso di Telecomunicazioni - AA 2011/2012 150
Radice dell’albero
foglia
Profondità
0
1
2
3
Grossi/Venturino
Rappresentazione grafica del codice
CODICE NON A PREFISSO Le parole codice non sono nodi terminali I nodi “codice” si trovano a profondità differenti
Corso di Telecomunicazioni - AA 2011/2012 151
0 1
00 01 10 11
simbolo codice binario 3
A 10
H 01
- 11
E 00
L 1
S 0
Grossi/Venturino
Rappresentazione grafica del codice
CODICE A LUNGHEZZA FISSA Le parole codice sono nodi terminali Tutti nodi “codice” si trovano alla stessa profondità
Corso di Telecomunicazioni - AA 2011/2012 152
0 1
000 001 010 011 100 101
simbolo codice binario 1
A 000
H 001
- 010
E 011
L 100
S 101
Grossi/Venturino
Rappresentazione grafica del codice
CODICE A LUNGHEZZA VARIBILE A PREFISSO Le parole codice sono nodi terminali I nodi “codice” si trovano a profondità differenti
Corso di Telecomunicazioni - AA 2011/2012 153
simbolo codice binario 2
A 0000
H 0001
- 001
E 10
L 01
S 11
0 1
11
001
10
0000 0001
01
Grossi/Venturino
Decodifica di un codice a prefisso
Corso di Telecomunicazioni - AA 2011/2012 154
simbolo codice binario 2
A 0000
H 0001
- 001
E 10
L 01
S 11
0 1
11
001
10
0000 0001
01
SLLEHSAES
SLLESEHS
1101011000011100100001011
001110101101100110000111
−
−−
Grossi/Venturino
Cosa suggeriscono gli esempi?
Un buon codice di sorgente deve assegnare parole codice differenti a simboli
differenti, soddisfare la condizione del prefisso per
garantire una decodifica istantanea e non ambigua,
avere una lunghezza quanto più piccola possibile.
Codici a lunghezza variabile possono essere più efficienti dei codici a lunghezza fissa.
Corso di Telecomunicazioni - AA 2011/2012 155Grossi/Venturino
Domande
Quale è la minima lunghezza ammissibile per un codice a prefisso? TEOREMA SULLA CODIFICA DI SORGENTE
Come costruire in forma sistematica dei buoni codici a prefisso? ALGORITMO DI HUFFMAN
Corso di Telecomunicazioni - AA 2011/2012 156Grossi/Venturino
Lunghezza del codice ed entropia
La lunghezza media del codice è
L’entropia della sorgente è
Corso di Telecomunicazioni - AA 2011/2012 157Grossi/Venturino
simbolo frequenza codice binario 2 probabilità lunghezza della parola [in bit]
A 1 0000 1/20 4
H 2 0001 2/20 4
- 3 001 3/20 3
E 4 10 4/20 2
L 4 01 4/20 2
S 6 11 6/20 2
L = 43
20+ 3
320
+ 21420
=4920
= 2.45
H(X) =120
log21
1/20+
220
log21
2/20+L +
620
log21
6/20≈ 2.41≤ L
Teorema sulla codifica di sorgente
Consideriamo una sorgente stazionaria senza memoria con alfabeto A = {a1,…,aM}.
Supponiamo di assegnare ad ogni simbolo aiuna stringa di bit c(ai) lunga ni bit
c(ai) è detta parola codice binaria (o semplicemente parola codice) assegnata al simbolo ai.
L’insieme di tutte le parole codice C = {c(a1),…, c(aM)} prende il nome di codice sorgente.
Corso di Telecomunicazioni - AA 2011/2012 158Grossi/Venturino
Teorema sulla codifica di sorgente
Corso di Telecomunicazioni - AA 2011/2012 159
Simboli a1 a2 … aM
Probabilità p1 p2 … pM
Informazione log2(1/p1) log2(1/p2) … log2(1/pM)ENTROPIA H = p1log2(1/p1) + … + pMlog2(1/pM) [bit per simbolo]
Parola codice c(a1) c(a2) … c(aM)Probabilità p1 p2 … pM
Lunghezza n1 n2 … nM
LUNGHEZZAMEDIA DEL
CODICEL = p1 n1 + … + pM nM [bit per simbolo]
Grossi/Venturino
Teorema sulla codifica di sorgente
La lunghezza di un qualunque codice a prefisso maggiore o uguale all’entropia della sorgente
H ≤ L Un codice a prefisso si dice “ottimo” se
minimizza la lunghezza media L. In generale, il codice ottimo non è unico
Un codice a prefisso ottimo soddisfa la seguente disuguaglianza:
H ≤ L < H+1Corso di Telecomunicazioni - AA 2011/2012 160Grossi/Venturino
Conseguenze teorema
Confrontando H ed L intuiamo che un buon codice di sorgente deve assegnare parole
codice più corte a simboli più frequenti
Corso di Telecomunicazioni - AA 2011/2012 161
ENTROPIA ALFABETO H = p1 log2(1/p1) + … + pM log2(1/pM) [bit per simbolo]
LUNGHEZZAMEDIA DEL
CODICEL = p1n1 + … + pM nM [bit per simbolo]
Grossi/Venturino
Conseguenze teorema (continua)
Esiste un codice a prefisso con L = H solo se log2(1/p1), …, log2(1/pM) sono interi
In tal caso, il codice ottimo ha ni = log2(1/pi), i=1,…,M.
Corso di Telecomunicazioni - AA 2011/2012 162
ENTROPIA ALFABETO H = p1 log2(1/p1) + … + pM log2(1/pM) [bit per simbolo]
LUNGHEZZAMEDIA DEL
CODICEL = p1n1 + … + pM nM [bit per simbolo]
Grossi/Venturino
Esempio
Corso di Telecomunicazioni - AA 2011/2012 163
Simboli a1 a2 a3 a4 a5
Probabilità p1=1/2 p2=1/4 p3=1/8 p4=1/16 p5=1/16
Informazione log2(1/p1)=1 log2(1/p2)=2 log2(1/p3)=3 log2(1/p4)=4 log2(1/p5)=4
ENTROPIA ALFABETO H = p1 log2(1/p1) + … + pM log2(1/pM) = 15/8 [bit per simbolo]
Parola codice c(a1)=1 c(a2)=00 c(a3)=010 c(a4)=0110 c(a5)=0111
Probabilità p1=1/2 p2=1/4 p3=1/8 p4=1/16 p5=1/16
Lunghezza n1=1 n2=2 n3=3 n4=4 n5=4
LUNGHEZZAMEDIA DEL
CODICEL = p1 n1+ … + pM nM = 15/8 [bit per simbolo]
Grossi/Venturino
Conseguenze teorema (continua)
Fra tutti i codici a lunghezza fissa che soddisfano la condizione del prefisso, quello che minimizza la lunghezza media del codice assegna parole codice di lunghezza log2M ad ogni simbolo.
Corso di Telecomunicazioni - AA 2011/2012 164Grossi/Venturino
Esempio
Simboli Codice 1 Codice 2 Codice 3 Codice 4 Codice 5x1 00 000 000 0000 000001x2 01 001 001 0010 000010x3 10 010 010 0100 000100x4 11 011 011 1000 001000x5 00 100 101 1110 010000x6 11 111 110 0111 100000
Corso di Telecomunicazioni - AA 2011/2012 165
CODICE AMBIGUO
CODICI A PREFISSO
L= log2(M) L> log2(M)
Grossi/Venturino
EsempioSimboli Codice 1 Codice 2 Codice 3 Codice 4 Codice 5
x1 000 0000 1000 11000 110000x2 001 0001 1001 11001 110010x3 010 0010 1010 11010 110100x4 011 0011 1011 11011 110110x5 100 0100 1100 11100 111000x6 101 0101 1101 11101 111010x7 110 0110 1110 11110 111100x8 111 0111 1111 11111 111110x9 011 1001 0001 10001 100010
Corso di Telecomunicazioni - AA 2011/2012 166
CODICE AMBIGUO CODICI A PREFISSO
L= log2(M) L> log2(M)Grossi/Venturino
Conseguenze teorema (continua)
Esiste un codice ottimo a lunghezza fissa solo se risultano verificate due condizioni: p1 =… = pM = 1/M M = 2n
In tal caso, ogni simbolo è codificato con log2M=n bitCorso di Telecomunicazioni - AA 2011/2012 167
ENTROPIA H = p1 log2(1/p1) + … + pM log2(1/pM) [bit per simbolo]
LUNGHEZZAMEDIA DEL
CODICEL = p1 n1 + … + pM nM [bit per simbolo]
Grossi/Venturino
Esempio
Corso di Telecomunicazioni - AA 2011/2012 168
Simboli a1 a2 a3 a4
Probabilità p1=1/4 p2=1/4 p3=1/4 p4=1/4
Informazione log2(1/p1)=2 log2(1/p2)=2 log2(1/p3)=2 log2(1/p4)=2
ENTROPIAH = p1 log2(1/p1) + … + pM log2(1/pM) = 2 [bit per simbolo]
Parola codice c(a1)=00 c(a2)=01 c(a3)=10 c(a4)=11
Probabilità p1=1/4 p2=1/4 p3=1/4 p4=1/4
Lunghezza n1=2 n2=2 n3=2 n4=2
LUNGHEZZAMEDIA DEL
CODICEL = p1 n1 + … + pM nM = 2 [bit per simbolo]
Grossi/Venturino
Costruzione del codice ottimo
Corso di Telecomunicazioni - AA 2011/2012 169
Albero generato seguendo l’algoritmo di Huffman per una sorgente di sei simboli
simbolo codicea1 1a2 011a3 010a4 001a5 0001a6 0000
Grossi/Venturino
Costruzione del codice ottimo
ALGORITMO DI HUFFMAN
1. Gli M simboli dell’alfabeto di sorgente vengono ordinati in
accordo a valori non crescenti delle loro probabilità pi
2. Si raggruppano gli ultimi due simboli aM e aM-1 in un “simbolo
equivalente” di probabilità (pM-1+pM)3. Si ripetono i passi 1 e 2 finché non rimane un solo simbolo
4. Per ogni simbolo, la parola di codice corrispondente si trova esplorando a ritroso l’albero generato con i passi 1 ÷ 3, dalla radice finale verso quel simbolo
Corso di Telecomunicazioni - AA 2011/2012 170Grossi/Venturino
Costruzione del codice ottimo
Per l’esempio precedente risulta:
Corso di Telecomunicazioni - AA 2011/2012 171
H = 2 0.05 log21
0.05
+ 0.15log2
10.15
+ 0.1 log21
0.1
+ 0.5 log2
10.5
= 2.086 [bit per simbolo]
L = 0.05 × 4 + 0.05 × 4 + 0.1 × 3+ 0.15 × 3+ 0.15 × 3+ 0.5 ×1= 2.81 [bit per simbolo]
Non esiste nessun altro codice a prefisso con lunghezza media più piccola
Grossi/Venturino
Decodifica del codice ottimo
Proviamo a decodificare la sequenza 0011010011001….
Corso di Telecomunicazioni - AA 2011/2012 172
Muovendosi dalla radice dell’albero, si seguono i rami ad ogni nodo intermedio in accordo alle cifre binarie della sequenza finché si raggiunge un nodo terminale (cioè un simbolo).Poi si ricomincia la procedura.
Grossi/Venturino
Esempio
Codificare la frase: SHE-SELLS-SEA-SHELLS
Corso di Telecomunicazioni - AA 2011/2012 173
simbolo frequenza probabilità codice binario 1
codice binario 2
A 1 1/20 000 0000
H 2 2/20 001 0001
- 3 3/20 010 001
E 4 4/20 011 10
L 4 4/20 100 01
S 6 6/20 101 11
Facciamo vedere che il codice 2 è un codice ottimo (codice di Huffman)
Grossi/Venturino
Esempio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 174
simbolo codice binario 2
A 0000
H 0001
- 001
E 10
L 01
S 11
Grossi/Venturino
Esempio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 175
simbolo codice binario
2
codice binario
3A 0000 1111
H 0001 1101
- 001 110
E 10 01
L 01 00
S 11 10
Il codice di Huffman non è unico: ad esempio, scambiando i valori ‘0’ e ‘1’ ottengo un altro codice di Huffman
Grossi/Venturino
Esempio (continua)
Codificare la frase: SHE-SELLS-SEA-SHELLS
Entropia alfabeto (H): 2.41 bit per simbolo Lunghezza media codice 1 (L): 3 bit per simbolo Lunghezza media codice 2 (L): 2.45 bit per simbolo (ottimo)
Corso di Telecomunicazioni - AA 2011/2012 176
simbolo frequenza probabilità codice binario 1
codice binario 2
A 1 1/20 000 0000
H 2 2/20 001 0001
- 3 3/20 010 001
E 4 4/20 011 10
L 4 4/20 100 01
S 6 6/20 101 11
Grossi/Venturino
Esercizio
Una sorgente stazionaria discreta senza memoria ha un alfabeto di 8 simboli con probabilità 0.25, 0.20, 0.15, 0.12, 0.10, 0.08, 0.05 e 0.05.
Determinare: L’entropia della sorgente; un codice a lunghezza fissa per la sorgente; un codice di Huffman per la sorgente; la lunghezza media di simbolo per i due codici.
Corso di Telecomunicazioni - AA 2011/2012 177Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 178
simboli probabilità informazionea1 p1=0.25 log2(1/p1)
a2 p2=0.20 log2(1/p2)
a3 p3=0.15 log2(1/p3)
a4 p4=0.12 log2(1/p4)
a5 p5=0.10 log2(1/p5)
a6 p6=0.08 log2(1/p6)
a7 p7=0.05 log2(1/p7)
a8 p8=0.05 log2(1/p8)
H = 0.25 log21
0.25
+ 0.20 log2
10.20
+ 0.15 log2
10.15
+ 0.12 log2
10.12
+0.10 log21
0.10
+ 0.08 log2
10.08
+ 0.05 log2
10.05
+ 0.05 log2
10.05
= 2.80 [bit per simbolo]
Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 179
simboli probabilità Codice 1(a lunghezza fissa)
LunghezzaParola codice
a1 p1=0.25 000 3
a2 p2=0.20 001 3
a3 p3=0.15 010 3
a4 p4=0.12 011 3
a5 p5=0.10 100 3
a6 p6=0.08 101 3
a7 p7=0.05 110 3
a8 p8=0.05 111 3
LUGHEZZA MEDIA CODICE 1 (L1) = 3 [BIT PER SIMBOLO]
LUGHEZZA MEDIA CODICE 1 > ENTROPIA
Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 180Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 181
simboli probabilità
Codice 2 (Huffman)
LunghezzaParola codice
a1 p1=0.25 01 2a2 p2=0.20 11 2a3 p3=0.15 001 3a4 p4=0.12 101 3a5 p5=0.10 100 3a6 p6=0.08 0001 4a7 p7=0.05 00001 5a8 p8=0.05 00000 5
LUGHEZZA MEDIA CODICE 2 (L2) = 2.83 [BIT PER SIMBOLO]
L1>L2>H
Grossi/Venturino
Esercizio
Una sorgente stazionaria senza memoria emette un nuovo simbolo ogni millisecondo (0.001 secondi).
L’alfabeto di sorgente contiene tre simboli che sono emessi con probabilità p1=0.6, p2=0.3, e p3=0.1.
Determinare: l’entropia della sorgente; un codice a lunghezza fissa per la sorgente. un codice di Huffman per la sorgente e calcolare il
bit-rate medio; un codice di Huffman che codifichi coppie di
simboli e determinare il bit-rate medio.
Corso di Telecomunicazioni - AA 2011/2012 182Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 183
simboli probabilità informazionea1 p1=0.6 log2(1/p1)a2 p2=0.3 log2(1/p2)a3 p3=0.1 log2(1/p3)
H = 0.6 log21
0.6
+ 0.3 log2
10.3
+ 0.1 log2
10.1
≅1.30 [bit per simbolo]
Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 184
simboli probabilità Codice 1(a lunghezza fissa)
Codice 2 (Huffman)
a1 p1=0.6 00 1a2 p2=0.3 01 01a3 p3=0.2 10 00
L2 = 1.4 bit per simbolo
L1 = 2 bit per simbolo
Grossi/Venturino
Esercizio (continuo)
Coppie di simboli Probabilitàa1 a1 Pr{a1 a1} = Pr{a1} Pr{a1} = 0.36a1 a2 Pr{a1 a2} = Pr{a1} Pr{a2} = 0.18a1 a3 Pr{a1 a3} = Pr{a1} Pr{a3} = 0.06a2 a1 Pr{a2 a1} = Pr{a2} Pr{a1} = 0.18a2 a2 Pr{a2 a2} = Pr{a2} Pr{a2} = 0.09a2 a3 Pr{a2 a3} = Pr{a2} Pr{a3} = 0.03a3 a1 Pr{a3 a1} = Pr{a3} Pr{a1} = 0.06a3 a2 Pr{a3 a2} = Pr{a3} Pr{a2} = 0.03a3 a3 Pr{a3 a2} = Pr{a3} Pr{a3} = 0.01
Corso di Telecomunicazioni - AA 2011/2012 185Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 186Grossi/Venturino
Esercizio (continuo)
Corso di Telecomunicazioni - AA 2011/2012 187
Coppie di simboli
Probabilità Codice 3 (Huffman)
Lunghezza parole codice
a1 a1 0.36 1 1
a1 a2 0.18 011 3
a1 a3 0.06 0011 4
a2 a1 0.18 010 3
a2 a2 0.09 0001 4
a2 a3 0.03 00001 5
a3 a1 0.06 0010 4
a3 a2 0.03 000001 6
a3 a3 0.01 000000 6
Grossi/Venturino
L =1⋅ 0.36 + 2⋅ 0.36 + 4⋅ 0.21+ 5⋅ 0.03 + 6⋅ 0.04 == 2.670 [bit per coppia di simboli] ==1.335 [bit per simbolo]
Esercizio (continuo)
Frequenza simboli = 1 nuovo simbolo ogni 0.001 secondi = 1000 simboli al secondo
Lunghezza codici Codice 1 2 bit per simbolo Codice 2 1.4 bit per simbolo Codice 3 1.335 bit per simbolo
Bit rate (frequenza di bit) Codice 1 2000 bit al secondo Codice 2 1400 bit al secondo Codice 3 1335 bit al secondo
Corso di Telecomunicazioni - AA 2011/2012 188Grossi/Venturino
Osservazione
La lunghezza media del codice può essere ridotta codificando coppie (o più in generale gruppi di simboli), al costo di una maggiore complessità delle operazioni di codifica e decodifica.
In riferimento all’esempio precedente, supponiamo di voler trasmettere un messaggio lungo 10000 caratteri Codice ha lunghezza fissa si trasmettono 10000 x
2=20000 cifre binarie Codice di Huffman (simbolo a simbolo) si trasmettono
10000 x 1.4 = 14000 cifre binarie Codice di Huffman (coppia di simboli) si trasmettono
10000 x 1.335 = 13350 cifre binarie Codificando gruppi di simboli più grandi possiamo in teoria
raggiungere il limite entropico di 10000 x 1.3 = 13000 cifre binarie.
Corso di Telecomunicazioni - AA 2011/2012 189Grossi/Venturino
Riassumendo
La compressione senza perdite riduce il numero di simboli (cifre binarie) da trasmettere a parità di contenuto informativo del messaggio
La compressione senza perdite sfrutta la memoria e le proprietà statistiche della sorgente: alcuni simboli del messaggio possono essere
estrapolati da altri; simboli più frequenti possono essere codificati con
stringhe binarie più corte.
Corso di Telecomunicazioni - AA 2011/2012 190Grossi/Venturino
Standard di compressione ZIP
Lo ZIP è un formato di compressione dei dati molto diffuso nei personal computer.
Usa un algoritmo di compressione senza perdite.
Ogni file viene compresso separatamente, il che permette di estrarre rapidamente i singoli file.
Viene utilizzato per inviare o archiviare programmi o file che non possono essere modificati dal processo di compressione.
Corso di Telecomunicazioni - AA 2011/2012 191Grossi/Venturino
Cenni alla compressione con perdite
La compressione senza pedite permette di ottenere limitati fattori di compressione (tipicamente 4:1)
Talvolta nel processo di compressione si accetta di perdere parte del contenuto informativo del messaggio al fine aumentare la velocità di trasmissione.
Nella codifica con perdite si effettua una riduzione dei simboli dell’alfabeto di sorgente.
Corso di Telecomunicazioni - AA 2011/2012 192Grossi/Venturino
Esempio di compressione con perdita
193Corso di Telecomunicazioni - AA 2011/2012
16777216 livelli (24-bit) 256 livelli (8-bit)
16 livelli (4-bit)2 livelli (1-bit)
Grossi/Venturino
Esempio di compressione con perdita
Corso di Telecomunicazioni - AA 2011/2012 194Grossi/Venturino
Standard di compressione JPEG
Sviluppato dal Joint Photographic ExpertsGroup e standardizzato nel 1992
E’ lo standard di compressione delle immagini fotografiche più utilizzato.
Estensioni: .jpeg, .jpg, .JPG, .JPE
Corso di Telecomunicazioni - AA 2011/2012 195Grossi/Venturino
Standard di compressione JPEG
Usa un algoritmo di compressione con perdite. E’ possibile specificare il fattore di qualità desiderato (1≤Q≤100)
Si può ottenere un fattore di compressione 15:1 senza alterare visibilmente la qualità dell'immagine. Sono possibili fattori di compressione fino a 100:1.
La maggior parte delle fotocamere digitali in commercio salva le immagini sulla memoria interna utilizzando lo standard jpeg
Molte immagini presenti sul web sono in formato JPEG
Corso di Telecomunicazioni - AA 2011/2012 196Grossi/Venturino
Esempio di compressione JPEG
Consideriamo un immagine sorgente con 73242 pixel, ogni pixel rappresentato con una risoluzione di 24 bit (ovvero, 224 possibili livelli di colore).
La trasmissione di questa immagine richiede l’invio di 73242x24 = 1.8 Mb.
Proviamo a comprimere l’immagine secondo lo standard jpeg.
Corso di Telecomunicazioni - AA 2011/2012 197Grossi/Venturino
Esempio di compressione JPEG
198Corso di Telecomunicazioni - AA 2011/2012
ORIGINALE Q=50 compressione 15:1
Q=25 compressione 23:1 Q=10 compressione 46:1
Grossi/Venturino
Standard di compressione M-JPEG
Motion JPEG (M-JPEG) è il formato comunemente usato dai sistemi videosorveglianza di rete.
Le telecamere acquisiscono le singole immagini e le comprimono nel formato JPEG.
Una telecamera di rete è in grado di acquisire e comprimere fino a 30 immagini singole al secondo.
Se la velocità di trasmissione è pari o superiore a 16 fotogrammi al secondo, le immagini vengono percepite come video “full motion”.
Poiché ogni fotogramma rappresenta un’immagine JPEG, tutti i fotogrammi hanno la stessa qualità che varia a seconda del livello di compressione scelto per la telecamera di rete o il server video.
Corso di Telecomunicazioni - AA 2011/2012 199Grossi/Venturino
Standard di compressione MPEG
MPEG è l’acronimo di Moving Picture Experts Group, un comitato tecnico internazionale incaricato di definire standard per la rappresentazione in forma digitale di audio, video e altre tipologie di contenuti multimediali in modo da soddisfare un'ampia varietà di applicazioni.
Gli standard definiti dall'MPEG comprendono una famiglia di formati di compressione video digitale con perdita.
Gli standard definiti dall'MPEG sono tra i più universalmente utilizzati.
Corso di Telecomunicazioni - AA 2011/2012 200Grossi/Venturino
Standard di compressione MPEG
Nome Descrizione ApplicazioniMPEG-1 Codifica di immagini in movimento, e associato
audio, per supporto di archiviazione digitale fino a circa 1,5 Mbit/s
Video CD (qualità simile al VHS)
MPEG-2 Codifica generica di immagini in movimento e informazione audio associata
DVD, Televisione digitale
MPEG-4 Estensione dell'MPEG-1 in grado di gestire flussi audio/video eterogenei, contenuti 3D, e diritti digitali. Per la codifica video supporta il formato MPEG-2 oppure un nuovo codec molto efficiente chiamato MPEG-4 AVC (H.264).
Televisione digitale ad alta definizione HDTV, DVD, Blu-ray Disc, telefoni cellulari 3G
Corso di Telecomunicazioni - AA 2011/2012 201Grossi/Venturino
Standard di compressione MPEG
Il principio base del formato MPEG consiste nel confronto di due immagini da trasmettere in rete.
La prima immagine è usata come fotogramma di riferimento per le immagini successive sono trasmesse solo le informazioni relative ai pixel differenti.
I terminali utilizzati per la visualizzazione ricostruiscono le immagini originali utilizzando l’immagine di riferimento e i dati degli elementi diversi.
Nonostante l’apparente complessità, il formato MPEG offre il vantaggio di ridurre in modo significativo il volume di dati trasmesso in rete rispetto al formato Motion JPEG.
Corso di Telecomunicazioni - AA 2011/2012 202Grossi/Venturino
Esempio di compressione MPEG
Sequenza di tre immagini da comprimere
Sequenza di immagini che vengono trasmesse dopo la compressione
Corso di Telecomunicazioni - AA 2011/2012 203Grossi/Venturino
Standard di compressione DivX
Il DivX® è una tecnologia multimediale proprietaria, attualmente basata su una variante dell’MPEG-4.
Di questa tecnologia fa parte tra l'altro un celebre compressore video sviluppato da DivX Inc. ed utilizzato da moltissime persone nel mondo.
La particolarità del software di compressione DivX sta nella sua capacità nel produrre file di dimensioni ridotte a partire da filmati di lunga durata, lasciando pressoché inalterata la qualità dell'immagine.
In pratica, è possibile convertire un film DVD di 6-8 GB in un file DivX di 700 MB (la dimensione di un CD-ROM) con una qualità video e audio più che discrete. Per questo motivo è al centro di controversie per il suo utilizzo nella duplicazione non autorizzata di DVD protetti.
Corso di Telecomunicazioni - AA 2011/2012 204Grossi/Venturino
Standard di compressione MP3
MP3 sta per Motion Picture Expert Group-1/2 Audio Layer 3 (e anche noto come MPEG-1 Audio Layer 3)
E’ un algoritmo di compressione audio con perdita in grado di ridurre drasticamente la quantità di dati richiesti per memorizzare un suono, mantenendo comunque una qualità accentabile del suono.
Corso di Telecomunicazioni - AA 2011/2012 205Grossi/Venturino
Standard di compressione MP3
Il segnale audio non compresso memorizzato nei CD-AUDIO ha un bit rate di 1411.2 kb/s
Alcuni rate di codifica disponibili nello standard MP3:
Corso di Telecomunicazioni - AA 2011/2012 206
Bit-rate MP3(kb/s)
Fattore di compressione(rispetto al CD-AUDIO)
32 44 : 164 22 : 196 14.7 : 1
128 11 : 1160 9 : 1192 7 : 1256 5.5 : 1320 4.4 : 1
Grossi/Venturino
Standard di compressione MP3
128 kb/s è il formato di compressione attualmente più diffuso in quanto offre una buona qualità del suono con un buon fattore di compressione.
Con il crescere della capacità dei supporti di memorizzazione e l’introduzione delle connessioni a banda larga anche i formati di compressione a 160 kb/s a 192 kb/s si stano diffondendo.
Molti sono in grado di distinguere un formato MP3 a 128 kb/s da un CD originale.
Test di ascolto hanno mostrato che che per avere una qualità del suono indistinguibile da quella dei CD-AUDIO è necessario usare un formato di compressione non inferiore a 256 kb/s.
Corso di Telecomunicazioni - AA 2011/2012 207Grossi/Venturino
CODIFICA DI CANALE
208Corso di Telecomunicazioni - AA 2011/2012Grossi/Venturino
Premessa
Nel progettare un sistema di comunicazione si hanno due esigenze contrastanti:1. “ridurre all’osso” le dimensioni del messaggio
da trasmettere senza perdere alcuna informazione così da aumentare la velocità di trasferimento (CODIFICA DI SORGENTE);
2. proteggersi dagli errori introdotti dal canale (CODIFICA DI CANALE).
Corso di Telecomunicazioni - AA 2011/2012 209Grossi/Venturino
Schema di comunicazione di Shannon
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 210
sorgentenumerica
codifica di sorgente
codifica di canale
modulatoredemodulatore
destinatariodecodifica di sorgente
decodifica di canale
canale
Svantaggi delle compressione
La rimozione di ridondanza aumenta la probabilità d’errore.
ESEMPIO: se il canale trasforma la “q” in una “l”, la parola “quadro” diviene “luadro”, facilmente correggibile, mentre la parola “qadro” diventa “ladro”, generando un errore.
Corso di Telecomunicazioni - AA 2011/2012 211Grossi/Venturino
Compressione vs affidabilità
L’esigenza di comprimere la sorgente è in contraddizione con quella di ottenere trasmissioni affidabili.
Paradossalmente, nello schema di Shannondapprima si rimuove ridondanza dalla sorgente attraverso la codifica di sorgente, per poi introdurla nuovamente attraverso il codificatore di canale per proteggersi dagli errori.
Corso di Telecomunicazioni - AA 2011/2012 212Grossi/Venturino
sorgentenumerica
codifica di sorgente
codifica di canale
Compressione vs affidabilità
Il codificatore di sorgente rimuove la ridondanza “disordinata” della sorgente.
Il codificatore di canale introduce una ridondanza “ordinata” che possa essere sfruttata per rivelare eventuali errori e, in alcuni casi, correggerli.
Corso di Telecomunicazioni - AA 2011/2012 213Grossi/Venturino
Codici di canale
Le prestazioni di un codice vengono misurate in termini di: capacità di rivelazione: numero massimo di errori
che esso riesce a rivelare in una parola di codice; capacità di correzione: numero massimo di errori
che esso riesce a correggere in una parola codice (minore a quella di rivelazione);
code rate (R): è il rapporto fra la lunghezza (k) del messaggio da trasmettere e la lunghezza (n) della parola codice generala R=k/n.
Corso di Telecomunicazioni - AA 2011/2012 214Grossi/Venturino
Codice a ripetizione a lunghezza 2
Supponiamo di voler trasmettere il messaggio 1 0 1 0 0 (5 bit)
Possiamo ripetere la trasmissione di ogni bit due volte; il messaggio codificato è:
11 00 11 00 00 (10 bit) Supponiamo che il segnale ricevuto sia
11 10 11 00 11 (10 bit)
Corso di Telecomunicazioni - AA 2011/2012 215
ERRORERILEVATO
COPPIA DI ERRORINON RILEVATA
Grossi/Venturino
Codice a ripetizione a lunghezza 3
Proviamo a ripetere la trasmissione di ogni bit tre volte; il messaggio codificato è:
111 000 111 000 000 (15 bit) Supponiamo che il segnale ricevuto sia
111 100 111 000 110 (15 bit)
Corso di Telecomunicazioni - AA 2011/2012 216
ERRORERIVELATO E CORRETTO
COPPIA DI ERRORIRIVELATA
Grossi/Venturino
Codice a ripetizione a lunghezza 4
Proviamo a ripetere la trasmissione di ogni bit quattro volte; il messaggio codificato è:
1111 0000 1111 0000 0000 (20 bit) Supponiamo che il segnale ricevuto sia
1111 1000 1111 0000 1100 (20 bit)
Corso di Telecomunicazioni - AA 2011/2012 217
ERRORERIVELATO E CORRETTO
COPPIA DI ERRORIRIVELATA
Grossi/Venturino
Codice a ripetizione a lunghezza n
Aumenta il numero il numero di cifre da trasmettere di n-volte (rate 1/n).
Permette di rilevare n/2 errori del canale.
Permette di rilevare e correggere n/2 -1.
NOTA: x = parte intera inferiore del numero x Esempi: 1.7 = 1; -1.2 = -2; 5 = 5
Corso di Telecomunicazioni - AA 2011/2012 218Grossi/Venturino
Codice a controllo di parità
Supponiamo di voler trasmettere il messaggio0100011 1011000 1100011 (21 bit)
Possiamo organizzare le cifre binarie in una tabella con 3 righe come segue
Corso di Telecomunicazioni - AA 2011/2012 219
0 1 0 0 0 1 11 0 1 1 0 0 01 1 0 0 0 1 1
Grossi/Venturino
Codice a controllo di parità
Per ogni riga contiamo il numero di 1: se sono in numero dispari, si aggiunge un bit di parità 1, se invece sono pari, si aggiunge un bit di parità 0.
Corso di Telecomunicazioni - AA 2011/2012 220
0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 0 0 1 1 0
BIT DI PARITA’
Grossi/Venturino
Codice a controllo di parità
Supponiamo che durante la trasmissione si abbiano degli errori sulla seconda riga:
Corso di Telecomunicazioni - AA 2011/2012 221
0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 0 0 1 1 0
0 1 0 0 0 1 1 11 0 1 1 1 0 0 11 1 0 0 0 1 1 0
0 1 0 0 0 1 1 11 0 1 0 1 0 0 11 1 0 0 0 1 1 0
0 1 0 0 0 1 1 11 0 1 0 1 1 0 11 1 0 0 0 1 1 0
ERRORE RIVELATO
ERRORENON
RIVELATO
ERRORE RIVELATO
MESSAGGIO TRASMESSO
canale
Grossi/Venturino
Codice a controllo di parità
Aggiunge un bit di ridondanza per ogni k bit di informazione rate = k/(k+1).
Può rilevare (ma non correggere) un numero dispari di errori.
Per rilevare e correggere un errore dobbiamo necessariamente aumentare il numero di bit controllo usati (vedi esempio seguente).
Corso di Telecomunicazioni - AA 2011/2012 222Grossi/Venturino
Codice a doppio controllo di parità
Supponiamo di voler trasmettere il messaggio0100011 1011000 1100011 (21 bit)
Possiamo organizzare le cifre binarie in una tabella con 3 righe e 7 colonne:
Corso di Telecomunicazioni - AA 2011/2012 223
0 1 0 0 0 1 11 0 1 1 0 0 01 1 0 0 0 1 1
Grossi/Venturino
Codice a doppio controllo di parità
Per ogni riga contiamo il numero di 1: se sono in numero dispari, si aggiunge un bit di parità 1, se invece sono pari, si aggiunge un bit di parità 0.
Per ogni colonna contiamo il numero di 1: se sono in numero dispari, si aggiunge un bit di parità 1, se invece sono pari, si aggiunge un bit di parità 0.
Corso di Telecomunicazioni - AA 2011/2012 224
0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 0 0 1 1 00 0 1 1 0 0 0
BIT DI PARITA’ DI RIGA
BIT DI PARITA’ DI COLONNA
Grossi/Venturino
Codice a doppio controllo di parità
Il rate del codice è 21 / 31 ≈ 0.6
Corso di Telecomunicazioni - AA 2011/2012 225
0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 0 0 1 1 00 0 1 1 0 0 0
10 bit di ridondanza
21 bit di informazione
Grossi/Venturino
Codice a doppio controllo di parità
Corso di Telecomunicazioni - AA 2011/2012 226
ERRORE CORRETTO
DUE ERRORI RIVELATI
MESSAGGIO TRASMESSO
canale0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 0 0 1 1 00 0 1 1 0 0 0
0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 1 1 0 1 00 0 1 1 0 0 0
0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 0 1 0 1 00 0 1 1 0 0 0
0 1 0 0 0 1 1 11 0 1 1 0 0 0 11 1 0 0 1 1 1 00 0 1 1 0 0 0
TRE ERRORI RIVELATI
Grossi/Venturino
ARQ (Automatic Repeat-reQuest)
Quando viene rilevato un errore all’interno di un pacchetto è possibile richiedere la ritrasmissione dell’intero pacchetto.
L’uso di protocolli di ritrasmissione richiede la presenza di un canale di feedback per notificare l’errore al trasmettitore.
Esistono protocolli di ARQ: Stop-and-wait Go-back-N Selective-repeat
Corso di Telecomunicazioni - AA 2011/2012 227Grossi/Venturino
ARQ stop-and-wait
Il mittente invia un messaggio e attende dal destinatario una conferma positiva (ACK), negativa (NAK).
Se scade il tempo di attesa, il mittente provvede a rispedire il pacchetto.
Nel caso in cui si verificasse un errore nella trasmissione del segnale di conferma (ACK), il mittente provvede a rinviare il pacchetto.
Tutti i pacchetti trasmessi sono numerati per risolvere la ricezione di copie multiple di uno stesso pacchetto.
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 228
ARQ stop-and-wait
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 229
La presenza del timer è necessaria per segnalare eventi di errore al trasmettitore
ARQ go-back-N
Il mittente dispone di un buffer dove immagazzina N pacchetti da spedire.
Man mano che riceve la conferma ACK svuota il buffer e lo riempie con nuovi pacchetti.
Nell'eventualità di un pacchetto perso o danneggiato avviene il rinvio di tale pacchetto e di tutti i successivi.
I pacchetti ricevuti dal destinatario dopo quello scartato vengono eliminati.
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 230
ARQ go-back-N
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 231
Anche se i pacchetti sono ricevuti correttamente, se non in sequenza vengono perduti (in ricezione
è presente un solo buffer)
ARQ selective-repeat
Nel protocollo go-back-N il ricevitore accetta solo pacchetti in sequenza: inefficiente se il tasso di errore è elevato.
Accettare pacchetti ricevuti correttamente anche se fuori sequenza permette un miglioramento delle prestazioni.
Il protocollo selective-repeat richiede la ritrasmissione dei soli pacchetti errati, e provvede al ricevitore a rimettere i pacchetti corretti nella giusta sequenza.
Maggiore complessità del selective-repeat rispetto al go-back-N : il ricevitore del go-back-N possiede un buffer singolo ed
accetta solo pacchetti in sequenza; il ricevitore del selective-repeat possiede un N-buffer e
gestisce arrivi fuori sequenza.
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 232
Riassumendo
Rimuovere “ridondanza disordinata” con il codificatore di sorgente aumenta la velocità di trasferimento ma rende il messaggio più vulnerabile agli errori.
Introdurre “ridondanza strutturata” con il codificatore di canale diminuisce la velocità di trasferimento dell’informazione, ma produce un aumento della sua affidabilità.
Progettare un buon sistema per il trasferimento dell’informazione richiede di trovare un
giusto compromesso tra affidabilità e velocitàCorso di Telecomunicazioni - AA 2011/2012 233Grossi/Venturino
Digitale vs analogico
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 234
sorgentenumerica
codifica di sorgente
codifica di canale
modulatore numerico
modulatore AM/FM
Sorgente analogica
trasduttore
modulatore AM/FM
trasmettitore trasmettitore
Conversione A/D
canale
Digitale vs analogico
Grossi/Venturino Corso di Telecomunicazioni - AA 2011/2012 235
destinatario
decodifica di sorgente
decodifica di canale
demodulatore numerico
demodulatore AM/FM
destinatario
trasduttore
demodulatore AM/FM
Conversione D/A
canale
ricevitore ricevitore