3. TEORIA DELL`INFORMAZIONE - Università degli Studi di Trento
by user
Comments
Transcript
3. TEORIA DELL`INFORMAZIONE - Università degli Studi di Trento
Trasmissione Numerica
Università di Trento
3. TEORIA DELL’INFORMAZIONE
INTRODUZIONE
MISURA DI INFORMAZIONE
SORGENTE DISCRETA SENZA MEMORIA
ENTROPIA DI UNA SORGENTE NUMERICA
CODIFICA DI SORGENTE
1° TEOREMA DI SHANNON
CODICI UNIVOCAMENTE DECIFRABILI
Trasmissione Numerica
Università di Trento
3. TEORIA DELL’INFORMAZIONE
DISUGUAGLIANZA DI KRAFT
CODICE DI SHANNON-FANO
CODICE DI HUFFMAN
MISURA DI INFORMAZIONE MUTUA
CANALE BINARIO SIMMETRICO
CAPACITA’ DI UN CANALE DISCRETO
CODIFICA DI CANALE
Trasmissione Numerica
Università di Trento
3. TEORIA DELL’INFORMAZIONE
2° TEOREMA DI SHANNON
CANALI CONTINUI
CAPACITA’ DI UN CANALE CONTINUO
SISTEMA DI TELECOMUNICAZIONE IDEALE
LEGGE DI HARTLEY-SHANNON
CONFRONTI DELLE PRESTAZIONI DI SISTEMI REALI
Trasmissione Numerica
Università di Trento
INTRODUZIONE
Sino ad ora abbiamo considerato i sistemi di TLC dal punto
di vista dei messaggi emessi da una sorgente e dei segnali
ad essi associati.
Obiettivo di un sistema di TLC: trasferire informazione da
una sorgente ad una destinazione mediante un canale di
trasmissione.
E’ importante studiare i sistemi di TLC sulla base
dell’informazione associata ad un messaggio.
Trasmissione Numerica
Università di Trento
INTRODUZIONE
Teoria dell’Informazione: un sistema di TLC viene studiato
dal punto di vista del processo di trasferimento
dell’informazione contenuta nei messaggi emessi dalla
sorgente, indipendentemente dal segnale con cui questa
informazione viene rappresentata.
Cenni storici: la Teoria dell’Informazione è stata formulata
da Shannon (1948).
Trasmissione Numerica
Università di Trento
INTRODUZIONE
OBIETTIVO DELLA TEORIA DELL’INFORMAZIONE
Dato un messaggio prodotto da una sorgente, l’obiettivo della
teoria dell’informazione è capire come si deve rappresentare
tale messaggio per ottenere una trasmissione efficiente
dell’informazione in esso contenuta su di un canale di
comunicazione reale (con inevitabili limitazioni fisiche).
X={x1 , x2 , …, xM}
Sorgente
?
Canale
?
Destinazione
Trasmissione Numerica
Università di Trento
INTRODUZIONE
La teoria dell’informazione utilizza 3 concetti base:
misura di informazione di una sorgente;
capacità di informazione di un canale;
codifica: mezzo per utilizzare la capacità di canale
per trasferire informazione.
Trasmissione Numerica
Università di Trento
INTRODUZIONE
Codifica ottima: “adatta” sorgente e canale in modo da
avere
la
massima
“efficienza”
nel
trasferimento
dell’informazione.
Nella teoria dell’informazione, il processo di codifica viene
separato in 2 fasi distinte:
codifica di sorgente;
codifica di canale.
Trasmissione Numerica
Università di Trento
INTRODUZIONE
CODIFICA DI SORGENTE
La
codifica
di
sorgente
adatta
la
sorgente
alla
trasmissione su di un opportuno canale equivalente privo
di rumore.
La codifica di sorgente è governata dal 1° Teorema di
Shannon.
Trasmissione Numerica
Università di Trento
INTRODUZIONE
CODIFICA DI CANALE
La codifica di canale permette di trasmettere l’informazione
emessa dalla sorgente (opportunamente trattata mediante la
codifica di sorgente) in maniera affidabile su un canale reale
caratterizzato da limitazioni fisiche (es. rumore).
La codifica di canale è governata dal 2° Teorema di Shannon
Trasmissione Numerica
Università di Trento
INTRODUZIONE
Sorgente
Codifica di
sorgente
Canale equivalente
privo di rumore
Decodifica di
sorgente
Codifica di
canale
Canale reale
(rumoroso)
Decodifica di
canale
Destinazione
Trasmissione Numerica
Università di Trento
INTRODUZIONE
Nel seguito, dapprima analizzeremo il caso di informazione
legata ad una sorgente discreta.
Successivamente i risultati ottenuti nel caso discreto
verranno generalizzati al caso continuo.
Il
primo
passo
da
fare
nello
studio
della
teoria
dell’informazione è definire in maniera formale una sorgente
discreta e la quantità di informazione da essa emessa.
Trasmissione Numerica
Università di Trento
SORGENTE DISCRETA: DEFINIZIONE
Sorgente discreta: esperimento con diversi valori di uscita
caratterizzati da una conoscenza probabilistica del tasso
di emissione.
x1, x2, … , xM
VALORE DI USCITA
P1,P2, … , PM
PROBABILITA’
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE
La misura
di
informazione è legata all’incertezza
associata all’emissione di ciascun simbolo
xi (ovvero è
legata all’incertezza sul fatto che il valore di uscita
dell’esperimento sia proprio xi)
Forte incertezza
grande contenuto informativo
Messaggi “poco probabili”
grande contenuto informativo
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE
Quindi l’informazione associata ad un messaggio è legata
alla sua probabilità
le probabilità degli eventi
definiscono la funzione informazione (o la funzione
incertezza).
Shannon definì misura di informazione la quantità:
def
1
I i = − log b Pi = log b
Pi
I
L
b
autoinformazione del messaggio xi
base del logaritmo
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE:
PROPRIETA’
Ii ≥0
per
b)
Ii →0
per
Pi → 1
c)
Ii > Ij
per
Pi < Pj
a)
0≤ Pi ≤1
HYHQWR PROWR
SUREDELOH
SRFD
LQIRUPD]LRQH
i q PHQR SUREDELOH GL
j
i FRQWLHQH SL
LQIRUPD]LRQH GL j
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE:
PROPRIETA’
d) Consideriamo due messaggi indipendenti xi, xj :
P (xi , xj) = Pi ·Pj
(
)
I ij = − log b P xi , x j = − log b Pi Pj = − log b Pi − log b Pj = I i + I j
L’informazione
totale
è
uguale
alla
somma
dell’informazione associata ai singoli messaggi.
N.B.: La misura di informazione definita da Shannon è l’unica
funzione che soddisfa le 4 proprietà viste.
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE
Solitamente si lavora nel caso binario (b=2):
I i = log 2
Per una sorgente binaria con simboli equiprobabili:
P(x1 ) = P(x2 ) =
1
[bit ]
Pi
1
2
I 1 = I 2 = log 2 2 = 1 [bit ]
Questo significa che 1 bit è l’informazione necessaria per
distinguere tra 2 messaggi equiprobabili.
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE:
NOTAZIONE
E’ necessario distinguere tra:
bit intesi come misura di informazione;
bit intesi come vere e proprie cifre di un codice binario.
Nel seguito si userà il termine binit per indicare le cifre
binarie quali elementi fisici di un messaggio o di un
codice.
Il termine bit verrà associato alla misura di informazione.
Trasmissione Numerica
Università di Trento
SORGENTE DISCRETA SENZA
MEMORIA: DEFINIZIONE
Definiamo sorgente discreta senza memoria una sorgente
caratterizzata delle seguenti proprietà:
sorgente che può emettere un insieme di M simboli X={x1, x2,
… , xM} ciascuno caratterizzato da probabilità Pi e
autoinformazione Ii ;
Pi costanti nel tempo (sorgente stazionaria);
simboli emessi in istanti differenti statisticamente indipendenti.
Indichiamo con r [simboli/sec] la symbol rate (velocità di
simbolo) media di emissione della sorgente.
Trasmissione Numerica
Università di Trento
ENTROPIA DI UNA SORGENTE
DISCRETA SENZA MEMORIA
L’informazione media per simbolo è data dalla media
statistica delle autoinformazioni dei simboli della sorgente
(I1 , I2 ,… , IM ):
def M
H (X ) =
M
∑ Pi I i = ∑ Pi log 2
i =1
i =1
1
[bit / simbolo]
Pi
Tale quantità è definita entropia della sorgente.
Trasmissione Numerica
Università di Trento
ENTROPIA DI UNA SORGENTE
BINARIA
Nel caso di sorgente binaria (M=2), l’entropia della sorgente
può assumere i seguenti valori:
0 ≤ H (X ) ≤ log2 M = 1
In particolare, note le probabilità di emissione dei simboli
(P1 =p e P2 =1-p), l’entropia di una sorgente binaria è data
da:
H (X ) = Ω ( p ) = p log 2
1
1
+ (1 − p )log 2
p
1− p
Trasmissione Numerica
Università di Trento
ENTROPIA DI UNA SORGENTE
BINARIA
Ω (p)
IL MASSIMO DELL’ENTROPIA SI
VERIFICA NELLE CONDIZIONI DI
EQUIPROBABILITA’ (p=0.5) E VALE
log22=1 [bit/simbolo]
p
Trasmissione Numerica
Università di Trento
ENTROPIA DI UNA
SORGENTE M-ARIA
Nel caso di sorgente M-aria, l’entropia H(X) dipende dalla
probabilità Pi dei simboli emessi dalla sorgente e dalla
dimensione M dell’alfabeto (M=numero di simboli).
Si può dimostrare che:
0 ≤ H (X ) ≤ log2 M
NESSUNA INCERTEZZA SUL
SIMBOLO EMESSO DALLA
SORGNTE (Pi =1, Pj =0 ∀j ≠i )
MASSIMA INCERTEZZA SUL
SIMBOLO EMESSO DALLA
SORGENTE (Pi =1/M, ∀i )
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
Se la sorgente emette una sequenza di n simboli (con
n>>1), l’informazione totale da trasferire è pari a circa
nH(X) bit.
Si definisce velocità di informazione della sorgente
(“information rate”) R la seguente quantità:
R=
DURATA DELLA
SEQUENZA NEL TEMPO
nH (X )
= rH (X ) [bit / sec]
nr
SONO BIT DI
INFORMAZIONE
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
Shannon: l’informazione proveniente da una sorgente
discreta senza memoria può essere codificata con cifre
binarie e trasmessa su di un canale senza rumore con
una bit rate rb che deve soddisfare il seguente vincolo:
rb ≥ R [binit / sec]
SONO CIFRE DI UN
CODICE BINARIO
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
NOTAZIONE
r è la symbol rate misurata in [simboli/sec];
R è la information rate misurata in [bit/sec];
rb è la signalling rate (o bit rate) misurata in [binit/sec].
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
Consideriamo una sorgente discreta senza memoria
caratterizzata dalla possibilità di emettere M simboli
differenti:
se i simboli sono equiprobabili
se i simboli non sono equiprobabili
R = r log 2 M
R = rH (X ) < r log 2 M
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
OSSERVAZIONI
Nel caso di simboli equiprobabili, l’informazione può essere
efficacemente trasmessa per mezzo di simboli M-ari con
symbol rate r.
Nel caso di simboli non equiprobabili, conviene usare una
un processo di codifica che tenga conto dell’informazione
variabile associata ai simboli e che consenta di trasmettere
ad una velocità prossima a R.
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
Consideriamo il caso di codifica binaria dei simboli di
sorgente.
Il codificatore produce un’uscita uguale a quella che
avrebbe una sorgente binaria con entropia
Ω(p) e
information rate rbΩ(p) (con p opportuno).
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
Poiché il codificatore non aggiunge né distrugge informazione,
allora l’information rate di ingresso deve essere uguale a quella
di uscita:
Information rate in
ingresso al codificatore
R = rH (X ) = rb( p ) ≤ rb
Bit rate in uscita dal
codificatore
Information rate in uscita
dal codificatore
Sorgente discreta
senza memoria
rb ≥ R
Codificatore
binario
R = rH (X )
R = rbΩ ( p )
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE
Si definisce lunghezza media di un codice la quantità:
rb
N=
r
Si può scrivere:
M
N = ∑ Pi N i
LUNGHEZZA DELLA
PAROLA DI CODICE
RELATIVA AL SIMBOLO
i-ESIMO
i =1
Parola di codice (caso binario): sequenza di “1” e “0” con
cui viene codificato un determinato simbolo.
Trasmissione Numerica
Università di Trento
1° TEOREMA DI SHANNON
Siano H (X ) l’entropia di una sorgente discreta senza
memoria e N il valore medio delle lunghezze delle parole
di codice che rappresentano i simboli emessi dalla
sorgente. Si può dimostrare che vale la seguente
condizione:
N ≥ H (X )
Il limite inferiore di N è quindi dato da
N = H (X ) .
Trasmissione Numerica
Università di Trento
EFFICIENZA DI UN CODICE
Un codice per cui vale
N = H (X )
si dice assolutamente
ottimo.
Un codice per cui si ottiene il valore minimo possibile di
N per una determinata sorgente si dice ottimo (anche se
N > H (X ) ).
Un codice con valore di N superiore a quello di un codice
ottimo si dice sub-ottimo.
Trasmissione Numerica
Università di Trento
EFFICIENZA DI UN CODICE
Il rapporto tra entropia e lunghezza media del codice:
R H (X )
=
≤1
rb
N
rappresenta una buona misura dell’efficienza di un codice
ottimo o sub-ottimo. Pertanto, si può definire l’efficienza
come:
efficienza % =
H (X )
⋅ 100
N
Trasmissione Numerica
Università di Trento
CODICE UNIVOCAMENTE
DECIFRABILE
Proprietà fondamentale di un codice: la sequenza di
simboli codificati non deve dare luogo ad ambiguità in
sede di decodifica.
Un codice che rispetta la suddetta proprietà è detto
unicamente decifrabile (ud).
Esempio: codice non ud
A→0, B→1, C→10, D→11
10011 può essere decodificato come
BAABB
CAD
CABB
Trasmissione Numerica
Università di Trento
CODICE UNIVOCAMENTE
DECIFRABILE ISTANTANEO
Definizione: Codice ud istantaneo (o codice a prefisso)
Si dice codice ud istantaneo un codice in cui ogni parola è
identificabile non appena finita la sequenza binaria che la
rappresenta.
Per costruire un codice ud istantaneo, ogni parola di
codice deve essere scelta in modo tale che non risulti
prefisso di altre parole di codice.
Esempio di codice ud istantaneo:
A → 0, B → 10, C → 110, D → 111
Trasmissione Numerica
Università di Trento
DISUGUAGLIANZA DI
KRAFT-MCMILLAN
Data una sorgente discreta senza memoria che può emettere
uno tra M simboli, un codice binario ud che rappresenta tale
sorgente è sempre costituito da parole di codice aventi
lunghezze
che
soddisfano
la
seguente
Ni
disuguaglianza di Kraft-McMillan:
M
K = ∑ 2 − Ni ≤ 1
i =1
Viceversa, se si scelgono per le parole di codice che
rappresentano la sorgente lunghezze che soddisfano la
condizione di Kraft-McMillan, allora è sempre possibile
costruire un codice ud.
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE: ESEMPIO
Consideriamo una sorgente che emette 4 simboli non
equiprobabili:
P1 =
1
2
P2 =
1
4
P3 =
1
8
P4 =
1
8
L’entropia H(X) di questa sorgente è data da:
4
H (X ) = ∑ Pi log 2
i =1
1
1
1
1 1
= log 2 2 + log 2 4 + log 2 8 + log 2 8 = 1.75 [ bit / simbolo ]
8
Pi 2
4
8
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE: ESEMPIO
xi
Pi
&RG
&RG
&RG
&RG
$
%
&
'
N
.
Trasmissione Numerica
Università di Trento
CODIFICA DI SORGENTE: ESEMPIO
Codice 1 (codice a lunghezza fissa)
N =2
=1 → ud, efficienza 88%
N
Codice 2
Codice 3 (codice a virgola)
N = 1.25 < H (X ) , N>1 → non è ud!
N = 1.875 ,
<1 → ud, efficienza 93%
N
Codice 4 (codice ad albero)
N = 1.75 = H (X )
=1 → ud, efficienza 100% →
codice assolutamente ottimo
.
Trasmissione Numerica
Università di Trento
CODICE ASSOLUTAMENTE OTTIMO:
CONDIZIONE NECESSARIA
Un codice binario può essere assolutamente ottimo (cioè
N = H (X ) ) se e solo se k=1 e le probabilità dei simboli
sono tali per cui:
Pi =
1
2 Ni
i=1,2,…,M
Ni=LUNGHEZZA PAROLA i-ESIMA
Pertanto, il codice assolutamente ottimo dovrà avere:
Ni = − log2 Pi = Ii
Trasmissione Numerica
Università di Trento
CODICE ASSOLUTAMENTE
OTTIMO
ESEMPIO
1
1
P2 =
8
16
N1 = 3 N 2 = 4
P1 =
1
1
... PM =
2
64
N 3 = 1 ... N M = 6
P3 =
CONCLUSIONE
La strategia da adottare per effettuare la codifica di sorgente
prevede di assegnare ai simboli che hanno probabilità più
alta parole di codice più corte rispetto a quelle dei simboli
con probabilità più bassa.
Trasmissione Numerica
Università di Trento
CODICE DI SHANNON-FANO
Si tratta di un codice sub-ottimo univocamente decifrabile
semplice ed efficiente.
STRATEGIA DI CODIFICA
1.
I
simboli
vengono
ordinati
in
colonna
con
probabilità
decrescente.
2.
I simboli vengono divisi in due gruppi, tramite una riga
orizzontale, in modo che le probabilità cumulative dei due gruppi
siano le più simili possibili.
Trasmissione Numerica
Università di Trento
CODICE DI SHANNON-FANO
3.
Si aggiunge una cifra 0 a destra delle parole di codice del I°
gruppo e una cifra 1 a destra di quelle del II° gruppo.
4.
Per ognuno dei due gruppi si ripetono i passi dal 2 in poi.
5.
Quando tutti i gruppi sono stati ridotti ad un simbolo ⇒ il codice
è completo.
Trasmissione Numerica
Università di Trento
CODICE DI SHANNON-FANO:
ESEMPIO
Trasmissione Numerica
Università di Trento
CODICE DI SHANNON-FANO:
ESEMPIO
Se la symbol rate fosse r = 1000 [simboli/ sec] , la information
Il codice di Shannon-Fano avente
rate sarebbe pari a R = rH (X ) = 2150 [bit / sec] .
N = 2.18
richiede
una
bit rate rb = N ⋅ r = 2180 [binit/ sec] (si noti che, come atteso,
per i codici sub-ottimi rb > R ).
L’efficienza di tale codice vale:
efficienza % =
H (X )
2.15
⋅ 100 =
⋅ 100 = 98.6%
N
2.18
Trasmissione Numerica
Università di Trento
CODICE DI SHANNON-FANO:
ESEMPIO
Per confronto, vediamo quale efficienza e quale bit rate rb
avrebbe un codice a lunghezza di parola fissa.
Utilizzando il codice a lunghezza fissa con N = N i = log 2 8 = 3
si ottiene:
rb = N ⋅ r = 3 ⋅ 1000 = 3000 [binit / sec ]
efficienza % =
H (X )
2.15
⋅ 100 =
⋅ 100 = 71.6%
N
3
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN
Il codice di Huffman è un codice ottimo (ovvero permette di
ottenere il minimo N
possibile per una determinata
sorgente), ma non necessariamente assolutamente ottimo.
Pertanto si tratta di un codice che permette di avvicinarsi il
più possibile al limite del 1° teorema di Shannon ( N = H (X ) ).
Trasmissione Numerica
Università di Trento
CONDIZIONI DI OTTIMALITÀ
DI UN CODICE
Si può dimostrare che affinché un codice ud istantaneo sia
ottimo devono essere verificate le seguenti condizioni:
1. Si devono assegnare parole di codice più lunghe ai simboli meno
probabili:
Pi > Pj
Ni < Nj
2. Le due parole di codice meno probabili (che sono anche le più
lunghe) devono avere la stessa lunghezza:
NM-1=NM
3. Tra le parole di codice che hanno la stessa lunghezza, almeno 2
devono coincidere in tutti i bit tranne l’ultimo.
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN
Sulla base delle condizioni precedenti, Huffman ha sviluppato la
seguente strategia di codifica dimostrando che conduce ad un
codice ottimo (ovvero il più vicino possibile al limite di Shannon):
Supponiamo di dover codificare i simboli xi emessi da una
sorgente S con M uscite caratterizzate dalle probabilità P1 ,…,PM.
Analogamente a quanto fatto per il codice di Shannon-Fano, gli M
simboli da codificare vengono ordinati secondo le loro probabilità.
Supponiamo di essere nella seguente situazione :
P1 ≥ P2 ≥ ... ≥ PM
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN
Consideriamo una sorgente S’ con M-1 uscite yi caratterizzate
dalle seguenti probabilità di emissione:
P’1 = P1
N’1
P’2 = P2
N’2
P’M-1 = PM-1 + PM
Lunghezza delle
parole di un codice
ottimo per S’
N’M-1= N’M-2
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN
Se conosciamo un codice ottimo per la sorgente S’, il codice ottimo
per la sorgente S può essere ottenuto nel modo seguente:
Le prime M-2 parole di codice della sorgente S sono uguali a
quelle della sorgente S’. Pertanto:
Ni=N’i
i=1,…,M-2
Le ultime 2 parole di codice della sorgente S vengono
generate aggiungendo alla parola yM-1 di S’ rispettivamente
un bit “0” e un bit “1”. Quindi, si ottiene:
NM = NM-1 = N’M-1+1
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN
CODICE OTTIMO PER LA
SORGENTE S’
Le prime M-2 parole di
codice non cambiano
CODICE OTTIMO PER LA
SORGENTE S
N1
N’1
Parola di codice
relativa al simbolo
xM-1
N’M-2= N’M-1
NM-2= N’M-2
0
Parola di codice relativa al
simbolo yM-1
1
Parola di codice
relativa al simbolo
xM
NM-1= NM = N’M-1 +1
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN
Tale strategia può essere iterata all’indietro fino a risalire ad una
sorgente binaria equivalente. Arrivati alla sorgente binaria
possiamo attribuire facilmente un codice ai due simboli emessi:
y1
y2
Simboli della sorgente binaria
0
1
Migliore codice possibile
(assolutamente ottimo solo se i simboli y1 e y2
sono equiprobabili)
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN: ESEMPIO
Consideriamo una sorgente discreta senza memoria
X={A,B,C,D,E} che può emettere uno tra 5 simboli
caratterizzati dalle seguenti probabilità:
P(A) = P1 = 0.4
P(B ) = P2 = 0.2 P(C ) = P3 = 0.2 P(D ) = P4 = 0.1 P(E ) = P5 = 0.1
L’entropia H(X) di questa sorgente è data da:
H (X ) =
5
∑ Pi log 2
i =1
1 2
5 1
= log 2 + log 2 5 +
Pi 5
2 5
1
1
1
+ log 2 5 + log 2 10 + log 2 10 ≅ 2.12 [bit / simbolo]
5
10
10
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN: ESEMPIO
Vediamo ora di costruire il codice di Huffman per tale sorgente
Simbolo
Probabilità di emissione
A
0.4
A
0.4
A
0.4
B+C+D+E
0.6
B
0.2
B
0.2
C+D+E
0.4
A
0.4
C
0.2
C
0.2
B
0.2
D
0.1
D+E
0.2
E
0.1
Raggruppiamo iterativamente i simboli meno probabili sino ad avere una sorgente binaria
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN: ESEMPIO
A questo punto possiamo costruire un codice ottimo per la
sorgente binaria ottenuta e derivare un codice ottimo per la
sorgente originaria
B+C+D+E (0.6)
A (0.4)
0
A (0.4)
1
A (0.4)
1
A (0.4)
1
1
C+D+E (0.4)
00
B (0.2)
01
B (0.2)
01
B (0.2)
01
C (0.2)
000
C (0.2)
000
D+E (0.2)
001
D (0.1)
0010
E (0.1)
0011
Migliore codice possibile per questa
sorgente binaria
(non è assolutamente ottimo)
Codice ottimo per la sorgente
considerata
Trasmissione Numerica
Università di Trento
CODICE DI HUFFMAN: ESEMPIO
Calcoliamo ora la lunghezza media del codice ottenuto:
N=
5
∑ Pi N i = 0.4 ⋅ 1 + 0.2 ⋅ 2 + 0.2 ⋅ 3 + 0.1 ⋅ 4 + 0.1 ⋅ 4 = 2.2 [binit / simbolo]
i =1
Il codice ottenuto è ottimo (la codifica di Huffman è sempre
ottima), ma non assolutamente ottimo. Infatti:
N ≠ H (X ) = 2.12 [bit / simbolo]
Trasmissione Numerica
Università di Trento
EFFICIENZA DI UN CODICE
UD ISTANTANEO
Si può dimostrare che per un codice ud istantaneo valgono le
seguenti relazioni:
log 2
1
1
≤ N i < log 2 + 1
Pi
Pi
H ( X ) ≤ N < H (X ) + 1
Trasmissione Numerica
Università di Trento
EFFICIENZA DI UN CODICE
UD ISTANTANEO
Sulla base delle precedenti relazioni, si può dire che un codice
ud istantaneo ha buona efficienza se
tutti i simboli si ha
N i ≈ log 2
1
Pi
H (X ) >> 1
oppure se per
.
Se nessuna di queste condizioni è verificata, al fine di migliorare
le caratteristiche del codice, è possibile ricorrere ad un artificio
noto come “estensione della sorgente”.
Trasmissione Numerica
Università di Trento
ESTENSIONE DELLA SORGENTE
Si dice che una sorgente S’ è un’estensione di ordine n di una
sorgente S, se i suoi simboli sono ottenuti raggruppando in
sequenze di lunghezza n i simboli emessi dalla sorgente S.
E’ possibile codificare i simboli della sorgente estesa S’ anziché
i simboli della sorgente originale S senza perdere informazione.
Si può dimostrare che codificando i simboli della sorgente
estesa di ordine n con un codice ud istantaneo si ottiene un
codice che soddisfa la seguente condizione:
H ( X ) ≤ N < H (X ) +
1
n
Trasmissione Numerica
Università di Trento
ESTENSIONE DELLA SORGENTE
Per quanto visto, si può concludere che il meccanismo di
estensione della sorgente permette di avvicinarsi quanto si
vuole al limite di Shannon agendo sul valore di n. In particolare,
quando n → ∞ allora N → H (X ) .
OSSERVAZIONE
N
Nella pratica aumentare n (ovvero avvicinare
a H (X ) )
significa incrementare significativamente la complessità del
decodificatore ed introdurre un ritardo di trasmissione.
Trasmissione Numerica
Università di Trento
SORGENTE DISCRETA
CON MEMORIA
Sino ad ora abbiamo considerato sorgenti in cui i simboli
emessi sono statisticamente indipendenti.
Molte sorgenti informative reali hanno una memoria: la
probabilità
di
emissione
di
un
simbolo
all’istante
considerato dipende dai simboli emessi precedentemente.
Trasmissione Numerica
Università di Trento
SORGENTE DISCRETA CON
MEMORIA: DEFINIZIONE
Definiamo sorgente discreta con memoria, una sorgente con
le seguenti proprietà:
sorgente che può emettere un insieme di M simboli X={x1, x2,
… , xM} ciascuno caratterizzato da probabilità Pi e
autoinformazione Ii ;
Pi costanti nel tempo (sorgente stazionaria);
simboli emessi dalla sorgente in istanti differenti correlati:
( ) ( )
P xi x ≠ P xi
La probabilità che venga emesso il simbolo xi dipende dalla sequenza di simboli x
emessa precedentemente dalla sorgente
Trasmissione Numerica
Università di Trento
ORDINE DELLA MEMORIA
Definiamo ordine della memoria della sorgente il numero
di simboli precedentemente emessi che influenzano la
probabilità di emissione del simbolo corrente.
Nel seguito considereremo il caso di una sorgente con
memoria di primo ordine (la probabilità del simbolo
emesso dipende solo dal simbolo precedente):
( ) (
P xi x = P xi x j
)
dove xj è il simbolo emesso prima di xi .
Trasmissione Numerica
Università di Trento
ENTROPIA DI UNA SORGENTE
DISCRETA CON MEMORIA
Data una sorgente X con memoria di primo ordine, si
può definire la sua entropia condizionata al simbolo xj
come:
(
)
H X xj =
∑ P(xi
def M
i =1
)
x j log 2
(
1
P xi x j
)
Mediando su tutti i possibili simboli xj , si ottiene:
M
( ) (
H ( X )= ∑ P x j H X x j
j =1
)
Valido solo per il caso di
memoria di primo ordine
Trasmissione Numerica
Università di Trento
ENTROPIA DI UNA SORGENTE
DISCRETA CON MEMORIA
Le probabilità condizionate hanno l’effetto di ridurre il
valore dell’entropia (la memoria introduce una certa
prevedibilità
riducendo
la
quantità
di
informazione
associata ai simboli).
Come si deve trattare una sorgente con memoria dal punto
di vista della codifica di sorgente?
Trasmissione Numerica
Università di Trento
CODIFICA PREDITTIVA
Un modo di sfruttare la memoria della sorgente è quello di
utilizzare un meccanismo di codifica predittivo.
Consideriamo il seguente schema:
Predizione del bit i-esimo
Sorgente M-aria
con memoria
~
x (i )
Predittore
Conversione da
simboli M-ari
a binari
x(i)
bit i-esimo della
sequenza binaria
ε(i)
sommatore modulo 2
Codificatore
errore di predizione
(vale o “0” o “1”)
Trasmissione Numerica
Università di Trento
CODIFICA PREDITTIVA
L’ingresso ε(i) al codificatore è costituito da una sequenza di
bit.
Se usiamo un “buon predittore” sbagliamo poco
nella
sequenza ε(i) compaiono molti “0” e pochi “1”.
Essendo molto sbilanciate le probabilità degli “0” e degli “1”, la
sequenza ha un’entropia molto bassa.
Trasmissione Numerica
Università di Trento
CODIFICA PREDITTIVA
P{ε (i ) = 0} = p con
p >>
1
2
Essendo l’entropia della sequenza “errore” molto bassa, in uscita
dal codificatore è possibile ottenere una sequenza codificata con
una bit rate “bassa”.
Trasmissione Numerica
Università di Trento
CODIFICA RUN-LENGTH
Abbiamo detto che la sequenza ε(i) è costituita da lunghe
stringhe di bit “0” intervallate da qualche bit “1”.
Definizione: si dice run di lunghezza n una sequenza di n bit “0”
seguiti da 1 bit “1”.
ESEMPIO
«
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
«
run di lunghezza 11 (n=11)
Trasmissione Numerica
Università di Trento
CODIFICA RUN-LENGTH
La codifica run-length sfrutta la presenza dei run
precedentemente definiti.
Invece di trasmettere l’intera stringa, si trasmette il
valore n che caratterizza la sua lunghezza.
Usando parole di codice composte da k bit, è possibile
rappresentare stringhe con lunghezza massima pari a
n=2k-1.
Trasmissione Numerica
Università di Trento
CODIFICA RUN-LENGTH
Esprime la lunghezza del run
ESEMPIO: k=3.
n
Parola di
codice
0
000
1
001
…
…
2k-2=6
110
2k-1=7
111
Rappresenta una situazione con un run
con n ≥ 7. In questa evenienza, il
codificatore deve attendere la parola di
codice successiva per ricostruire il run.
N.B.: Se si verifica troppo spesso la stringa “111” si deve
aumentare il valore di k.
Trasmissione Numerica
Università di Trento
CODIFICA RUN-LENGTH:
EFFICIENZA
La codifica risulta efficiente se in media le parole di
codice hanno meno bit dei run che rappresentano.
Indichiamo con E la media dei bit presenti in un run e
con N il numero medio dei bit delle di parole di codice
necessarie per codificare il run.
La bit rate rb sarà data da:
N
rb =
E
r
Il rapporto N E dice quanto è efficiente la codifica. Più
piccolo è il rapporto, migliore è la codifica.
Trasmissione Numerica
Università di Trento
INTRODUZIONE ALLA CODIFICA
DI CANALE
Sorgente
Codifica di
sorgente
Canale equivalente
privo di rumore
Decodifica di
sorgente
Codifica di
canale
Canale reale
rumoroso
Decodifica di
canale
Destinazione
Trasmissione Numerica
Università di Trento
INTRODUZIONE ALLA CODIFICA
DI CANALE
Quanto visto per la codifica di sorgente ha senso solo nell’ipotesi
che il canale non introduca errori (Pbe=0). Infatti, per i codici visti,
un errore in ricezione distruggerebbe l’intero messaggio!
La codifica di canale affronta il problema di trasmettere in
maniera affidabile su un canale non-affidabile.
In pratica si realizza un processo di codifica a controllo d’errore
per ridurre gli effetti del rumore presente sul canale.
La codifica di canale è governata dal 2° Teorema di Shannon.
Trasmissione Numerica
Università di Trento
INTRODUZIONE ALLA CODIFICA
DI CANALE
Per semplicità, nel seguito assumeremo che sia la sorgente
sia il canale di trasmissione siano discreti (l’assunzione di
canale discreto è poco realistica).
In queste ipotesi, verranno definite la quantità di informazione
trasferita e la capacità di un canale.
Trasmissione Numerica
Università di Trento
CANALE DISCRETO: DEFINIZIONE
L’ingresso è costituito da un insieme
L’uscita è costituita da un insieme
finito X di simboli xi.
finito Y di simboli yj.
X = {x1 ,...,xM }
CANALE
Y = {y1 ,...,yK }
Il rumore e altre possibili distorsioni del canale alterano i simboli trasmessi, producendo
un alfabeto a destinazione Y che può essere diverso da quello di
ingresso X (K può essere diverso da M).
Trasmissione Numerica
Università di Trento
CANALE DISCRETO: NOTAZIONE
P(xi) probabilità che la sorgente emetta il simbolo xi;
P(yj) probabilità che a destinazione venga ricevuto il simbolo yj;
P(xi,yj) probabilità congiunta che sia stato trasmesso il simbolo xi
e venga ricevuto il simbolo yj;
P(xi / yj) probabilità condizionata che sia stato trasmesso il simbolo
xi dato che è stato ricevuto il simbolo yj;
P(yj / xi) probabilità condizionata che sia stato ricevuto il simbolo yj
dato che è stato trasmesso il simbolo xi.
Trasmissione Numerica
Università di Trento
CANALE DISCRETO SENZA MEMORIA
TEMPO-INVARIANTE: DEFINIZIONE
Si definisce canale discreto senza memoria tempo-invariante un
canale discreto:
in cui l’uscita in un determinato istante dipende solo dal
simbolo in ingresso al canale in quell’istante e non dai simboli
precedentemente trasmessi.
le cui proprietà non variano nel tempo;
Un canale discreto senza memoria tempo-invariante è univocamente
definito dall’alfabeto di ingresso X, da quello di uscita Y e dalle
probabilità condizionate di transizione in avanti P(yj / xi).
Trasmissione Numerica
Università di Trento
CANALE DISCRETO SENZA MEMORIA
TEMPO-INVARIANTE: ESEMPIO
P(y1 / x1)
y1
x1
y2
P(y1 / x2)
P(y2 / x1)
P(y2 / x2)
x2
y3
P(y3 / x1)
P(y3 / x2)
PROBABILITÀ DI TRANSIZIONE IN AVANTI PER UN CANALE DISCRETO CON DUE SIMBOLI IN
INGRESSO (M=2) E TRE SIMBOLI IN USCITA (K=3)
Trasmissione Numerica
Università di Trento
CANALE DISCRETO SENZA
MEMORIA TEMPO-INVARIANTE
Talvolta può essere utile scrivere le probabilità di transizione
di un canale in forma matriciale:
Matrice delle
probabilità di
transizione
P(y1 x1 ) P(y2 x1 )
P(y x )
1 2
P=
P( y1 xM )
P(yK x1 )
P(yK xM )
Nota: per semplicità di notazione, da qui in poi assumeremo
implicita la tempo-invarianza ed indicheremo un canale discreto
senza memoria tempo-invariante semplicemente con la dicitura
canale discreto senza memoria.
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA
Obiettivo: misurare l’informazione trasferita da un canale
(ipotesi: canale discreto senza memoria).
Vediamo innanzitutto di introdurre l’entropia condizionata
alla ricezione di un particolare simbolo H(X/yj):
1
H X y j = ∑ P xi y j log2
P xi y j
xi∈X
(
)
(
)
(
)
Questa quantità esprime quanto vale l’incertezza sul
simbolo trasmesso (ovvero il simbolo emesso dalla
sorgente) una volta che è stato ricevuto il simbolo yj.
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA
Il valore medio di H(X/yj) (ovvero la media calcolata su tutte
le possibili uscite) è chiamato entropia condizionata H(X/Y)
e rappresenta l’incertezza che rimane in media sul simbolo
trasmesso dopo l’osservazione del simbolo ricevuto:
1
H (X Y ) = ∑ H X y j P y j = ∑ ∑ P xi , y j log2
P xi y j
y j∈Y
y j∈Y xi∈X
(
)( )
(
)
(
)
H(X/Y) è anche chiamata equivocazione e può essere vista
come l’informazione perduta nel canale rumoroso.
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA
L’entropia della sorgente H(X) rappresenta l’incertezza sul
simbolo inviato sul canale prima dell’osservazione dell’uscita.
Sulla base di quanto visto fin qui, possiamo definire
l’informazione mutua media I(X;Y) di un canale come:
def
I (X ;Y ) = H (X ) − H (X Y )
L’informazione mutua media I(X;Y) dice di quanto si sia ridotta
in media l’incertezza sul simbolo emesso dalla sorgente una
volta osservato il simbolo ricevuto.
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA
L’informazione mutua media I(X;Y) può essere calcolata
anche come:
∑ P(xi , y j )I (xi ; y j ) [bit simbolo]
I (X ;Y ) = ∑
xi∈X y j∈Y
dove I(xi;yi) è l’informazione mutua associata alla trasmissione
del simbolo xi ed alla ricezione del simbolo yi (ovvero la
quantità di informazione trasferita sul canale quando viene
trasmesso xi e viene ricevuto yi). I(xi;yi) è definita come:
(
)
(
P xi y j
I xi ; y j = log2
P(xi )
def
) [bit]
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE
MUTUA: PROPRIETÀ
1. L’informazione mutua media di un canale è simmetrica,
ovvero:
I (X ;Y ) = I (Y ; X )
2. L’informazione mutua media è sempre una quantità nonnegativa:
I (X ;Y ) ≥ 0
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE
MUTUA: PROPRIETÀ
3. L’informazione mutua media di un canale può essere espressa
come:
I (X ;Y ) = H (Y ) − H (Y X )
dove H(Y) è l’entropia a destinazione e H(Y/X) è chiamata
entropia di rumore. H(Y) e H(Y/X) sono date rispettivamente da:
( )
H (Y ) = ∑ P y j log2
y j∈Y
H (Y X ) = ∑
(
1
P yj
( )
)
∑ P xi , y j log 2
xi∈X y j ∈Y
(
1
P y j xi
)
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE
MUTUA: PROPRIETÀ
4. L’ informazione mutua media di un canale è legata all’entropia
congiunta di ingresso e uscita H(X,Y) secondo la seguente
relazione:
I (X ;Y ) = H (X ) + H (Y ) − H (X ,Y )
dove H(X,Y) è definita come:
H (X ,Y ) =
∑ ∑
xi∈X y j ∈Y
(
)
P xi , y j log 2
1
P xi , y j
(
)
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA
Abbiamo già detto che descrivere un canale discreto senza
memoria significa stabilire gli alfabeti X, Y e le probabilità di
transizione in avanti P(yj/xi).
Per calcolare I(X;Y) sono necessarie:
le probabilità congiunte P(xi,yj) , le probabilità condizionate
P(xi / yj) e le probabilità di emissione dei simboli P(xi);
oppure:
le probabilità congiunte P(xi,yj) , le probabilità condizionate
P(yi / xj) e le probabilità P(yi).
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA
In realtà, fissate le probabilità di emissione dei simboli di
sorgente P(xi) e note le probabilità di transizione P(yj|xi), si
hanno tutti i dati per il calcolo dell’informazione mutua.
Infatti, utilizzando il Teorema di Bayes, si può scrivere:
(
) (
)
P xi , y j = P y j xi P(xi )
I (X ;Y ) = ∑
∑ P(xi , y j )log2
xi∈X y j∈Y
( )=
P y j xi
( )
xi∈X y j∈Y
( )
(
P yj
( )
∑ ∑ P y j xi P(xi )log2
( )
∑ P(y j xi )P(xi )
P y j xi
xi∈X
)
(
)
P y j = ∑ P xi , y j = ∑ P y j xi P(xi )
xi∈X
xi∈X
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA:
CASI PARTICOLARI
CANALE SENZA RUMORE (IDEALE)
Esempio: M=K=3
Ogni simbolo yj identifica solo un determinato xi:
(
)
P xi y j = 1
1
I xi , y j = log2
= Ii
(
)
P
x
i
(
)
x1
x2
y1
y2
x3
y3
L’informazione trasferita è identica all’autoinformazione del
simbolo xi . Ragionando in media si ha:
I (X ;Y ) = H (X )
Trasmissione Numerica
Università di Trento
MISURA DI INFORMAZIONE MUTUA:
CASI PARTICOLARI
RUMORE INFINITO (CANALE “INUTILE”)
L’osservazione di yj non riduce l’incertezza sul simbolo xi
trasmesso:
(
)
P xi y j = P(xi )
(
)
I xi , y j = log2 1 = 0
L’informazione trasferita è nulla. Ragionando in media si ha:
I (X ;Y ) = 0
Trasmissione Numerica
Università di Trento
CANALE BINARIO SIMMETRICO:
DEFINIZIONE
Si definisce canale binario simmetrico un canale discreto con le
seguenti caratteristiche:
l’alfabeto di sorgente è composto da due simboli x1 e x2
caratterizzati da probabilità P(x1)=p e P(x2)=1-p;
l’alfabeto di destinazione è composto da due simboli y1 e y2;
le probabilità di transizione valgono:
P( y1 x2 ) = P( y2 x1 ) = α
P( y1 x1 ) = P( y2 x2 ) = 1 − α
Trasmissione Numerica
Università di Trento
ESEMPIO: CANALE BINARIO
SIMMETRICO
P(x1 ) = P1 = p
P(x2 ) = P2 = 1 − p
P( y1
P=
P( y1
1-α
x1
x2
x1 ) P( y2
x2 ) P( y2
α
y1
α
y2
1- α
x1 ) 1 − α α
=
x2 ) α 1 − α
Trasmissione Numerica
Università di Trento
ESEMPIO: CANALE BINARIO
SIMMETRICO
È possibile verificare che per un canale binario simmetrico
valgono le seguenti relazioni:
H (Y ) = Ω [P(y1 )] = Ω (α + p − 2αp)
H (Y X ) = Ω (α )
dove Ω(p) è l’entropia di una sorgente binaria definita come:
Ω ( p ) = p log 2
1
1
+ (1 − p )log 2
p
1− p
Trasmissione Numerica
Università di Trento
ESEMPIO: CANALE BINARIO
SIMMETRICO
Nel caso di canale binario simmetrico, l’informazione mutua
è quindi data da:
I (X ;Y ) = H (Y ) − H (Y X ) = Ω (α + p − 2αp) − Ω (α )
I(X;Y)
α=0
1
0<α<1/2
0.5
p
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN CANALE DISCRETO
L’informazione mutua di un canale I (X ;Y ) dipende dalle
probabilità di transizione in avanti P(yj|xi) e dalle probabilità
di emissione dei simboli della sorgente P(xi). Pertanto,
I ( X ;Y ) non dipende solo dal tipo di canale considerato, ma
anche dall’uso che viene fatto del canale.
Al fine di caratterizzare un canale discreto senza memoria
indipendentemente dalla sorgente in ingresso, si definisce
capacità del canale il valore massimo dell’informazione
mutua rispetto a tutte le possibili distribuzioni delle
probabilità dei simboli di ingresso:
CS = max {I (X ;Y )} [bit / simbolo]
{P(xi )}
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN CANALE DISCRETO
La capacità di canale rappresenta il massimo trasferimento
di informazione possibile per simbolo di un canale, ottenuto
in presenza di una particolare statistica di sorgente.
La capacità di canale può essere anche misurata in termini
di velocità nel trasferimento dell’informazione (information
rate).
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN CANALE DISCRETO
Se s [simboli/sec] indica la massima velocità dei simboli
(symbol rate) permessa dal canale, allora la capacità del
canale per unità di tempo è data da:
C = s ⋅ CS [bit / sec]
La capacità di canale per unità di tempo C rappresenta la
massima velocità di trasferimento dell’informazione permessa
dal canale.
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN CANALE
DISCRETO SIMMETRICO
La capacità di canale è una caratteristica propria del canale
(non dipende dall’ingresso considerato) ed è legata alla
matrice di transizione.
In generale non è semplice calcolare la capacità di un
canale.
In ipotesi di canale è simmetrico, il calcolo della capacità di
canale si semplifica.
Trasmissione Numerica
Università di Trento
CANALE DISCRETO SIMMETRICO
Definizione: canale discreto simmetrico
Un canale discreto simmetrico è un canale in cui le
probabilità di transizione sono tali per cui la probabilità di
transire risulta uguale per tutti i simboli (la matrice di
transizione è formata da righe e colonne caratterizzate dagli
stessi valori di probabilità).
In un canale discreto simmetrico l’entropia condizionata
H (Y xi ) è indipendente dal simbolo xi (non dipende dalla
riga della matrice di transizione su cui si fa il calcolo).
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN CANALE
DISCRETO SIMMETRICO
Vediamo quanto vale la capacità di canale CS nel caso di
canale discreto simmetrico:
CS = max{H (Y ) − H (Y X )}= maxH (Y ) − ∑ P(xi )H (Y xi ) =
{P( x )}
{P( x )}
i
i
xi ∈X
= max H (Y ) − H (Y xi ) ∑ P(xi ) = max {H (Y ) − H (Y xi )}
{P(xi )}
{P(xi )}
xi∈X
È indipendente da xi
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN CANALE
DISCRETO SIMMETRICO
Pertanto l’informazione mutua I(X;Y) è massima quando
H(Y) è massima. Ciò è verificato quando i simboli yj sono
equiprobabili.
Vediamo quale condizione deve essere verificata sui
simboli di ingresso xi al fine di ottenere simboli in uscita yj
equiprobabili:
( ) ∑ P(y j , xi ) = ∑ P(y j xi )P(xi ) = M1 ∑ P(y j xi )
x ∈X
x ∈X
x ∈X
P yj =
i
i
sono equiprobabili
i
Se gli M ingressi sono equiprobabili
Non dipende da j
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN CANALE
DISCRETO SIMMETRICO
Quindi, nel caso di canale discreto simmetrico, i simboli in
uscita sono equiprobabili quando anche i simboli in
ingresso sono equiprobabili.
La capacità del canale può quindi essere determinata
assumendo equiprobabili i simboli di ingresso.
Trasmissione Numerica
Università di Trento
ESEMPIO: CAPACITÀ DI UN
CANALE BINARIO SIMMETRICO
Nel caso di canale binario simmetrico, abbiamo già visto
che la media dell’informazione mutua vale:
I (X ;Y ) = H (Y ) − H (Y X ) = Ω (α + p − 2αp) − Ω (α )
I(X;Y)
α=0
1
0<α<1/2
0.5
p
Per ogni α la curva che
descrive
l’informazione
mutua ha un massimo per
p=0.5, ovvero per simboli
equiprobabili.
Trasmissione Numerica
Università di Trento
ESEMPIO: CAPACITÀ DI UN
CANALE BINARIO SIMMETRICO
Pertanto, ponendo p =0.5 si ottiene:
Cs = Ω (α + p − 2αp) − Ω (α ) = 1 − Ω (α )
CS
1
0.5
1
α
Trasmissione Numerica
Università di Trento
ESEMPIO: CAPACITÀ DI UN
CANALE BINARIO SIMMETRICO
Quindi la capacità di canale CS dipende dalla probabilità di
transizione α.
Osservazioni (sorgente binaria)
Canale ideale (senza rumore):
α=0
CS=1 [bit/simbolo]
Canale molto rumoroso:
α→1/2
CS→0 [bit/simbolo]
Trasmissione Numerica
Università di Trento
CODIFICA DI CANALE
A questo punto diventa importante studiare come sia
possibile utilizzare la capacità di un canale per trasferire
l’informazione emessa da una sorgente.
Dato un canale reale (ovvero “rumoroso”) caratterizzato da
una capacità di informazione data, è possibile utilizzare una
strategia che permetta di ottenere dal punto di vista del
trasferimento dell’informazione un canale equivalente senza
rumore?
Trasmissione Numerica
Università di Trento
CODIFICA DI CANALE
In un sistema di trasmissione numerica, la presenza di un
canale “rumoroso” causa delle discrepanze (errori) tra la
sequenza di dati in ingresso al sistema e quella in uscita.
Per canali “relativamente” rumorosi la probabilità di errore sul bit
è dell’ordine di 10-2.
Per applicazioni reali, tipicamente è necessario ottenere una
probabilità di errore sul bit di informazione dell’ordine di 10-6.
Tali valori di probabilità d’errore si possono raggiungere
effettuando una codifica della sequenza da trasmettere (codifica
di canale).
Trasmissione Numerica
Università di Trento
CODIFICA DI CANALE
L’obiettivo della codifica di canale consiste nell’aumentare
la resistenza di un sistema di telecomunicazione al rumore
presente sul canale.
La codifica di canale “trasforma” la sequenza di dati in
ingresso al canale in una nuova sequenza intrinsecamente
più robusta agli effetti del rumore.
La decodifica di canale effettua l’operazione inversa in
uscita dal canale al fine di ricostruire le sequenza orginale
(che rappresenta l’informazione della sorgente).
Trasmissione Numerica
Università di Trento
CODIFICA DI CANALE
L’approccio adottato nella codifica di canale solitamente consiste
nell’introdurre ridondanza.
Sfruttando tale ridondanza, il decodificatore può ricostruire il
messaggio originale anche in presenza di bit errati.
OSSERVAZIONE
L’obiettivo della codifica di sorgente è quello di ridurre la
ridondanza per incrementare l’efficienza del sistema di
trasmissione.
L’obiettivo della codifica di canale è quello di introdurre ridondanza
per incrementare l’affidabilità del sistema di trasmissione.
Trasmissione Numerica
Università di Trento
ESEMPIO: CODICI A BLOCCHI
I codici a blocchi costituiscono un semplice approccio alla
codifica di canale.
La sequenza da trasmettere viene divisa in blocchi di k bit di
informazione. Ogni blocco viene codificato con n bit (n>k).
k
n-k
Il numero di bit ridondanti è quindi pari a n-k. Tali bit
vengono scelti in modo da ottenere una protezione
dell’informazione dal rumore (vedi parte 4 del corso).
Trasmissione Numerica
Università di Trento
ESEMPIO: CODICI A BLOCCHI
Se una sorgente emette M simboli equiprobabili, ogni
simbolo della nuova parola di codice ha associata
un’informazione pari a log2 M n .
Si definisce code rate la quantità Rc = k n .
Aumentando n aumenta la ridondanza introdotta e quindi la
resistenza del codice al rumore, ma aumenta il tempo
necessario alla trasmissione della sequenza (a parità di
altre condizioni).
Trasmissione Numerica
Università di Trento
CODIFICA DI CANALE
A questo punto ci si può porre la seguente domanda:
Esiste uno schema di codifica (eventualmente anche molto
complicato) tale da rendere la probabilità di errore di un
canale reale rumoroso arbitrariamente piccola?
Il 2° Teorema di Shannon fornisce una risposta precisa alla
domanda precedente.
Trasmissione Numerica
Università di Trento
2° TEOREMA DI SHANNON: IPOTESI
Supponiamo di avere una sorgente discreta senza memoria
con alfabeto X, entropia H(X) e symbol rate r.
Per quanto visto precedentemente, l’information rate della
sorgente vale R=rH(X).
Supponiamo di disporre di un canale discreto senza
memoria con capacità per unità di tempo pari a C [bit/sec].
Trasmissione Numerica
Università di Trento
2° TEOREMA DI SHANNON
Nelle ipotesi precedenti, il 2° Teorema di Shannon afferma che:
Se R≤C allora esiste un sistema di codifica tale da
permettere la trasmissione dell’informazione emessa dalla
sorgente sul canale con una probabilità di errore
arbitrariamente piccola.
Se invece R>C non è possibile trasmettere l’informazione
senza errori.
Trasmissione Numerica
Università di Trento
2° TEOREMA DI SHANNON:
OSSERVAZIONI
Il 2° Teorema di Shannon non fornisce dettagli sul sistema
di codifica necessario per ottenere probabilità d’errore
arbitrariamente piccola, ma afferma solo che, se R≤C, esso
esiste.
Nella pratica, si può verificare che per ridurre la probabilità
d’errore si deve incrementare il numero di bit di ridondanza
(n-k).
Per (n-k) → ∞ il tempo necessario per la trasmissione del
messaggio codificato tende però all’infinito.
Trasmissione Numerica
Università di Trento
SORGENTI E CANALI CONTINUI
Fino ad ora è stato considerato il caso in cui sia la sorgente che il
canale sono discreti.
Nel seguito si generalizzerà la trattazione al caso più realistico di
sorgente che emette un segnale continuo e di canale anch’esso
continuo.
La capacità del canale sarà espressa in termini di larghezza di
banda e di rapporto segnale-rumore (legge di Hartley-Shannon).
Si arriverà alla definizione di un sistema di telecomunicazione
ideale che serve come riferimento per il confronto con i sistemi
reali.
Trasmissione Numerica
Università di Trento
SORGENTI CONTINUE
Nel caso continuo, la sorgente può produrre un insieme di
possibili segnali nel tempo x(t) che può essere visto come
un processo aleatorio che si assume essere ergodico.
Si effettua inoltre l’ipotesi che il processo abbia larghezza di
banda limitata, in modo da poterlo campionare senza
perdita
di
informazione
(vedi
Teorema
del
Campionamento).
Trasmissione Numerica
Università di Trento
SORGENTI CONTINUE
Ad ogni istante di campionamento, l’insieme dei possibili
valori assunti dal campione costituisce una variabile
aleatoria continua x descritta dalla sua funzione di densità
di probabilità pX(x).
La quantità di informazione media per campione è misurata
tramite la funzione entropia così definita:
H (X ) =
+∞
∫
−∞
p X (x )⋅ log 2
1
dx
p X (x )
Trasmissione Numerica
Università di Trento
SORGENTI CONTINUE
OSSERVAZIONE
In realtà l’entropia assoluta associata ad una sorgente
continua è sempre ∞. Ciò è facilmente verificabile
applicando il concetto di limite alla definizione di entropia
per una sorgente discreta:
1
H ass (X ) = lim ∑ p X (xi )∆x log 2
=
∆x →0 i
p X (xi )∆x
=
+∞
∫
−∞
p X (x )log 2
1
p X (x )
dx − lim log 2 ∆x
Questa è la H(x) definita precedentemente e
rappresenta una misura di entropia relativa
(o differenziale)
∆ x →0
Questo termine vale sempre
-∞
non è informativo
Trasmissione Numerica
Università di Trento
CANALI CONTINUI
La sorgente emette il segnale x(t) che, dopo essere stato
corrotto dal rumore presente sul canale, arriva a destinazione
come segnale y(t). In analogia al caso discreto, la media
dell’informazione mutua trasferita dal canale può essere
calcolata come:
I ( X ;Y ) =
+∞ +∞
∫ ∫
−∞ −∞
p XY (x , y )log 2
p X (x y )
p X (x )
dx dy
dove pX(x) è la densità di probabilità della sorgente, pXY(x,y) è la
densità di probabilità congiunta e pX (x|y) è la densità di
probabilità di transizione all’indietro.
Trasmissione Numerica
Università di Trento
CANALI CONTINUI
Tipicamente, si conosce la densità di probabilità di transizione
in avanti pY(y/x) del canale; pertanto, conviene calcolare
l’informazione mutua mediante la seguente espressione:
I (X ;Y ) = H (Y ) − H (Y X )
Si noti che, come nel caso discreto, l’informazione mutua è
una quantità simmetrica per cui può anche essere calcolata
come:
I (X ; Y ) = H ( X ) − H (X Y )
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN
CANALE CONTINUO
La capacità di un canale continuo è data da:
C S = max {I (X ; Y )}
p X (x )
[bit / campione]
Se il canale ha larghezza di banda fissata B, allora y(t) è
anch’esso a banda limitata. Campionando al limite di Nyquist
( fc=2B ) si ottengono 2B campioni (o simboli) al secondo.
Trasmissione Numerica
Università di Trento
CAPACITÀ DI UN
CANALE CONTINUO
Pertanto, la massima velocità di trasferimento dell’informazione è
data da:
C = 2BCS
[bit / sec]
C definisce la capacità per unità di tempo di un canale continuo a
banda limitata.
Per calcolare la capacità di un canale continuo, dobbiamo quindi
determinare Cs. Vediamo come si può fare nell’ipotesi di canale
che introduca un rumore additivo gaussiano bianco (AWGN).
Trasmissione Numerica
Università di Trento
CANALE CONTINUO CON
RUMORE AWGN
Consideriamo un canale con le seguenti caratteristiche:
il canale non provoca distorsioni all’interno della banda B e ogni
attenuazione è compensata da opportune amplificazioni;
il canale vincola il segnale in ingresso x(t) ad essere un segnale a
banda limitata con potenza media fissata S = x 2 ;
il segnale y(t) a destinazione è contaminato da rumore n(t) additivo
gaussiano bianco a media nulla e potenza media N= σ2 =ηB;
il segnale e il rumore sono indipendenti:
y(t)=x(t)+n(t)
y2 = S + N
Potenza media
di y(t)
Trasmissione Numerica
Università di Trento
LEGGE DI HARTLEY-SHANNON
Shannon ha dimostrato che la capacità di una canale continuo
AWGN con le caratteristiche descritte in precedenza può essere
calcolata come:
S
C = B log2 1 +
N
[bit / sec]
LEGGE DI
HARTLEY-SHANNON
dove B è la banda del canale espressa in [Hz] e
il rapporto segnale-rumore a destinazione.
S
N
è
Come atteso, C aumenta se aumenta la banda B o se aumenta
S
.
N
Trasmissione Numerica
Università di Trento
LEGGE DI HARTLEY-SHANNON:
DIMOSTRAZIONE
Abbiamo visto prima che la capacità di canale è data da:
C = 2BCS = 2B max{I (X ;Y )} = 2B max{H (Y ) − H (Y X )}
p X (x )
p X (x )
In analogia al caso discreto, l’entropia di rumore H(Y/X) si
può scrivere come:
H (Y X ) =
+∞ +∞
∫ ∫
−∞ − ∞
p X (x ) pY (y x )log 2
1
dxdy
PY (y x )
Trasmissione Numerica
Università di Trento
LEGGE DI HARTLEY-SHANNON:
DIMOSTRAZIONE
Nell’ipotesi di rumore additivo indipendente si può scrivere:
pY ( y x ) = pY (x + n ) = pn ( y − x )
Quindi, l’entropia di rumore H(Y/X) si può scrivere come:
H (Y X ) =
+∞
∫
pn (n )log 2
−∞
1
p n (n )
dn =
1
log 2 2πeN
2
L’entropia di rumore non
dipende da pX(x)
Pertanto la capacità Cs sarà data da:
[
]
1
Cs = max H (Y ) − H (Y X ) = max{H (Y )}− log2 2π eN
p X (x )
p X (x )
2
Trasmissione Numerica
Università di Trento
LEGGE DI HARTLEY-SHANNON:
DIMOSTRAZIONE
La potenza media del segnale in ricezione è data da:
y(t ) = x(t ) + n(t ) ⇒ y 2 = S + N
1
H (Y ) ≤ log2 2π e(S + N )
2
Si può dimostrare che H(Y) è uguale al suo massimo quando
pX(x) è gaussiana a media nulla. In tali condizioni si ha:
1
1
1
S+N
Cs = log2 2π e (S + N ) − log2 2π e N = log2
2
N
2
2
S
C = B log2 1 +
N
C.V.D.
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
Al fine di ottenere una probabilità d’errore circa nulla, deve essere
verificata la condizione R ≤ C .
Si definisce sistema di telecomunicazione ideale un sistema che
ha un tasso d’errore quasi nullo (Perr≅0) con un’information rate
pari a:
S
R = B log 2 1 +
N
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
La legge di Hartley-Shannon dice qual’è l’ottimo
compromesso sullo scambio tra banda e potenza. In
particolare, essendo N=ηB, con B banda del canale e
η
densità spettrale di potenza del rumore AWGN, si può
2
scrivere:
S
C = B log 2 1 +
ηB
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
Assumendo che η e R abbiano valori fissati, si ricava una
espressione utile che identifica le condizioni affinché la
trasmissione dell’informazione avvenga ad una rate R≤C:
R
S
B B
≥ 2 − 1
ηR R
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
comunicazioni reali
R<C
R=C
B
<1
R
R>C
impossibile per comunicazioni reali
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE: OSSERVAZIONI
Nella regione corrispondente a R>C è impossibile ottenere
un trasmissione affidabile.
B
< 1 (compressione di banda) occorre aumentare
R
Se
notevolmente la potenza del segnale al fine di trasmettere
in maniera affidabile.
B
>1
R
Se
(espansione di banda) si può effettuare una
trasmissione affidabile anche con basse potenze del
B
S
≈ 1.6 [dB] ).
→∞ ,
segnale (per
ηR
R
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
Un canale ideale con larghezza di banda infinita ha
capacità C∞ finita data da:
S ln(1 + λ )
S
S
S
= lim
C∞ = lim B log 2 1 +
1
.
44
=
≅
B →∞
B →∞ η λ
B
ln
2
η
η
η ln 2
λ=
S
→ 0
η B B →∞
ln(1 + λ )
→ 1
λ
λ →0
In pratica se:
B
> 10
R
C ≅ C∞
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
I risultati ottenuti sulla base della legge di Hartley- Shannon
si riferiscono ad un sistema di telecomunicazione ideale
(pertanto non realizzabile nella pratica).
Tuttavia, tali risultati sono molto utili nella progettazione di
un sistema di telecomunicazioni reale, in quanto
definiscono il limite superiore delle prestazioni ottenibili da
un sistema modellabile con un canale corrotto da rumore
AWGN.
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
ESEMPIO
Sia dato un canale AWGN con B = 1 [KHz ]
e
η = 1 [µW / Hz ] .
Trovare il minimo valore della potenza S (espressa in
[mW]) per avere un collegamento affidabile a R =100
[bit/sec] , R =1000 [bit/sec], R = 10000 [bit/sec].
Trasmissione Numerica
Università di Trento
SISTEMA DI TELECOMUNICAZIONE
IDEALE
SOLUZIONE
Usando la relazione:
R
S
B B
≥ 2 − 1
ηR R
si ricava:
R
B B
S ≥ η R 2 − 1
R
−3
Poiché η B = 10 allora:
R
− 3 1000
−1
S ≥ 10 ⋅ 2
R = 100 → S ≥ 0.072 [mW ]
R = 1000 → S ≥ 1 [mW ]
R = 10000 → S ≥ 1023 [mW ]
Trasmissione Numerica
Università di Trento
CONFRONTO CON I SISTEMI DI
TELECOMUNICAZIONE ANALOGICI
I parametri essenziali per effettuare un confronto tra un
sistema ideale e i sistemi di comunicazione analogici sono:
il rapporto segnale-rumore;
l’occupazione di banda.
Consideriamo un sistema analogico generico in cui il
segnale a destinazione abbia banda W e rapporto segnalerumore (S/N)D.
Consideriamo un canale AWGN con banda BT e rapporto
SR
segnale-rumore dato da
(dove SR è la potenza del
η BT
segnale in ricezione).
Trasmissione Numerica
Università di Trento
CONFRONTO CON I SISTEMI DI
TELECOMUNICAZIONE ANALOGICI
S
R = W log 2 1 +
N D
MODULATORE
CANALE AWGN
S
C = BT log 2 1 +
η BT
SORGENTE
ANALOGICA
DEMOD.
DESTINAZIONE
La massima information rate ottenibile in uscita è data da:
S
R = W log 2 1 +
N D
In ogni caso, l’information rate non può superare la capacità
del canale:
SR
R ≤ C = BT log 2 1 +
η BT
Trasmissione Numerica
Università di Trento
CONFRONTO CON I SISTEMI DI
TELECOMUNICAZIONE ANALOGICI
Ponendo R≤C e risolvendo rispetto a (S/N)D si ottiene:
SR
S
≤ 1 +
N D η BT
BT
W
γ
− 1 = 1 + − 1
b
b
dove:
b=
BT
S
, γ = R
W
ηW
Trasmissione Numerica
Università di Trento
CONFRONTO CON I SISTEMI DI
TELECOMUNICAZIONE ANALOGICI
La relazione trovata fornisce un termine di confronto per
tutti i sistemi di comunicazione analogici (è sufficiente
fornire a b e a γ i valori che caratterizzano il sistema in
esame).
Solitamente, si usa confrontare grafici che rappresentano
(S/N)D in funzione di γ (avendo fissato b) oppure che
rappresentano γ in funzione di b (avendo fissato (S/N)D).
Trasmissione Numerica
Università di Trento
CONFRONTO CON I SISTEMI DI
TELECOMUNICAZIONE ANALOGICI