CODIFICA CANALE

CODIFICA CANALE
Sorgente
Cofificatore
Canale
Decodificatore
Ricevitore
Rumore
Comunicazione con successo: ricevitore ottiene output
sorgente
– p. 1/39
CODIFICA CANALE
Sorgente
Cofificatore
Canale
Decodificatore
Ricevitore
Rumore
Comunicazione con successo: ricevitore ottiene output
sorgente
Es. effetto rumore. Input possibili al canale sequenze
101 e 111,
input 101, rumore: secondo bit modificato, output: 111;
input: 111, rumore: nessuno, output: 111;
⇒ diverse sequenze in input producono lo stesso
output (input confondibili).
– p. 1/39
CODIFICA CANALE
Sorgente
Cofificatore
Canale
Decodificatore
Ricevitore
Rumore
Comunicazione con successo: ricevitore ottiene output
sorgente
Es. effetto rumore. Input possibili al canale sequenze
101 e 111,
input 101, rumore: secondo bit modificato, output: 111;
input: 111, rumore: nessuno, output: 111;
⇒ diverse sequenze in input producono lo stesso
output (input confondibili).
Obiettivo: proteggere l’informazione da eventuali errori
di trasmissione legati al rumore
– p. 1/39
Codifica Canale
Obiettivo: Input NON Confondibili ≡ correzione errori
trasmissione
– p. 2/39
Codifica Canale
Obiettivo: Input NON Confondibili ≡ correzione errori
trasmissione
Metodo: Aggiungere ridondanza
– p. 2/39
Codifica Canale
Obiettivo: Input NON Confondibili ≡ correzione errori
trasmissione
Metodo: Aggiungere ridondanza
Nota: impossibile eliminare effetto rumore
vogliamo input non confondibili con alta robabilità
– p. 2/39
Canali
Canale discreto (alfabeti I/O discreti): (X , ⋄, Y)
X= alfabeto input al canale
Y= alfabeto output al canale
Π = [p(y/x)]= matrice delle probabilità di transizione
– p. 3/39
Canali
Canale discreto (alfabeti I/O discreti): (X , ⋄, Y)
X= alfabeto input al canale
Y= alfabeto output al canale
Π = [p(y/x)]= matrice delle probabilità di transizione
Canale discreto senza memoria (DMC) (X, Π, Y):
distribuzione probabilità output dipende solo da input
corrispondente
NON da precedenti input o output.
– p. 3/39
Capacitá Canale
Capacità del canale senza memoria:
C = max I(X, Y )
p(x)
– p. 4/39
Capacitá Canale
Capacità del canale senza memoria:
C = max I(X, Y )
p(x)
Dimostreremo:
capacità = massimo numero di bit per uso del canale.
– p. 4/39
Canale senza rumore
0
0
1
1
Trasmette un bit per uso senza errore ⇒
C=1
– p. 5/39
Canale senza rumore
0
0
1
1
Trasmette un bit per uso senza errore ⇒
C=1
Infatti
C = max I(X, Y ) = max H(X)−H(X/Y ) = max H(X) = 1
p(x)
p(x)
p(x)
per p(x) = (1/2, 1/2)
– p. 5/39
Canale binario simmetrico
1−p
0
p
p
0
"
p
1−p
Π=
1−p
p
1
1
#
1−p
I(X; Y ) = H(Y ) − H(Y /X) = H(Y ) −
X
p(x)H(Y /X = x)
x
= H(Y ) −
X
p(x)h(p) = H(Y ) − h(p)
x
– p. 6/39
Canale binario simmetrico
C = maxp(x) I(X, Y ) = maxp(x) H(Y ) − h(p) ≤ 1 − h(p)
p(x) = (1/2, 1/2) ⇒ p(y = 1) = 21 (1 − p) + 21 p =
1
2
⇒ H(Y ) = 1
1
Quindi C = 1 − h(p)bits
1/2
1
– p. 7/39
Canali Simmetrici
Canale simmetrico: Ogni riga (risp. colonna) é
permutazione
di ogni altra
riga (risp. colonna)


0.3 0.2 0.5


Es. Π = 0.5 0.3 0.2
0.2 0.5 0.3
– p. 8/39
Canali Simmetrici
Canale simmetrico: Ogni riga (risp. colonna) é
permutazione
di ogni altra
riga (risp. colonna)


0.3 0.2 0.5


Es. Π = 0.5 0.3 0.2
0.2 0.5 0.3
Canale debolmente simmetrico: Ogni riga é
permutazione di ogni altra riga; la somma su ogni
colonna "
é costante
#
1/3 1/6 1/2
Es. Π =
1/3 1/2 1/6
– p. 8/39
Canali Simmetrici
Canale simmetrico: Ogni riga (risp. colonna) é
permutazione
di ogni altra
riga (risp. colonna)


0.3 0.2 0.5


Es. Π = 0.5 0.3 0.2
0.2 0.5 0.3
Canale debolmente simmetrico: Ogni riga é
permutazione di ogni altra riga; la somma su ogni
colonna "
é costante
#
1/3 1/6 1/2
Es. Π =
1/3 1/2 1/6
Canale simmetrico ⇒ Canale debolmente simmetrico
– p. 8/39
Canali (Debolmente) Simmetrici
r=riga di Π
I(X; Y ) = H(Y )−H(Y /X) = H(Y )−H(r) ≤ log |Y |−H(r)
– p. 9/39
Canali (Debolmente) Simmetrici
r=riga di Π
I(X; Y ) = H(Y )−H(Y /X) = H(Y )−H(r) ≤ log |Y |−H(r)
Ponendo p(x) = 1/|X| per ogni x ∈ X risulta
p(y) =
X
x
1
somma colonna
=
p(x)p(y/x) =
|X|
|Y |
– p. 9/39
Canali (Debolmente) Simmetrici
r=riga di Π
I(X; Y ) = H(Y )−H(Y /X) = H(Y )−H(r) ≤ log |Y |−H(r)
Ponendo p(x) = 1/|X| per ogni x ∈ X risulta
p(y) =
X
x
1
somma colonna
=
p(x)p(y/x) =
|X|
|Y |
Quindi C = log |Y | − H(r)
– p. 9/39
Codifica Canale DMC
Codice canale (M, n) per (X, Π, Y):
Insieme di indici {1, . . . , M }
– p. 10/39
Codifica Canale DMC
Codice canale (M, n) per (X, Π, Y):
Insieme di indici {1, . . . , M }
Funzione codifica X n : {1, . . . , M } → X n
– p. 10/39
Codifica Canale DMC
Codice canale (M, n) per (X, Π, Y):
Insieme di indici {1, . . . , M }
Funzione codifica X n : {1, . . . , M } → X n
Funzione decodifica g : Y n → {1, . . . , M }
– p. 10/39
Codifica Canale DMC
Probabilitá di errore quando si codifica indice i:
X
n
n
p(y n /X n (i))I(g(y n ) 6= i)
λi = P r{g(Y ) 6= i/X = i} =
yn
– p. 11/39
Codifica Canale DMC
Probabilitá di errore quando si codifica indice i:
X
n
n
p(y n /X n (i))I(g(y n ) 6= i)
λi = P r{g(Y ) 6= i/X = i} =
yn
Probabilitá massima di errore:
λ(n) = max λi
1≤i≤M
– p. 11/39
Codifica Canale DMC
Probabilitá di errore quando si codifica indice i:
X
n
n
p(y n /X n (i))I(g(y n ) 6= i)
λi = P r{g(Y ) 6= i/X = i} =
yn
Probabilitá massima di errore:
λ(n) = max λi
1≤i≤M
Probabilitá media di errore:
(n)
Pe
M
1 X
=
λi
M
i=1
– p. 11/39
Codifica Canali Rumorosi
Tasso codice (M, n): R =
log M bit
n trasm.
– p. 12/39
Codifica Canali Rumorosi
Tasso codice (M, n): R =
log M bit
n trasm.
Tasso R é ottenibile se esiste sequenza di codici
(⌈2nR ⌉, n) con λ(n) → 0 per n → ∞
– p. 12/39
Codifica Canali Rumorosi
Tasso codice (M, n): R =
log M bit
n trasm.
Tasso R é ottenibile se esiste sequenza di codici
(⌈2nR ⌉, n) con λ(n) → 0 per n → ∞
Si dimostra che: (Teorema di Codifica Canale)
(a) ogni tasso R ≤ C é ottenibile,
(b) nessun tasso R > C é ottenibile
– p. 12/39
Codifica Canali Rumorosi
Tasso codice (M, n): R =
log M bit
n trasm.
Tasso R é ottenibile se esiste sequenza di codici
(⌈2nR ⌉, n) con λ(n) → 0 per n → ∞
Si dimostra che: (Teorema di Codifica Canale)
(a) ogni tasso R ≤ C é ottenibile,
(b) nessun tasso R > C é ottenibile
Capacitá = limite superiore di tutti i tassi ottenibili
– p. 12/39
Coppie Tipiche
(n)
Definizione L’insieme Aǫ delle coppie tipiche {(xn , y n )}
rispetto alla distribuzione p(x, y) è definito da:
(n)
=
(xn , y n ) ∈ X n × Y n :
Aǫ
1
− log p(xn ) − H(X) < ǫ,
n
1
n
− log p(y ) − H(Y ) < ǫ,
n
1
− log p(xn , y n ) − H(XY ) < ǫ
n
Qn
n
n
dove p(x , y ) = i=1 p(xi , xj ).
– p. 13/39
Joint AEP
Teorema Q
Siano (X n , Y n ) seqeuenze di v.c. i.i.d secondo
p(xn , y n ) =
1.
n
i=1 p(xi , xj ).
P r((X n , Y n )
∈
(n)
Aǫ )
Allora,
→ 1 per n → ∞.
– p. 14/39
Joint AEP
Teorema Q
Siano (X n , Y n ) seqeuenze di v.c. i.i.d secondo
p(xn , y n ) =
n
i=1 p(xi , xj ).
(n)
Aǫ )
1.
P r((X n , Y n )
2.
(1 − e)2n(H(X,Y )−ǫ)
∈
Allora,
→ 1 per n → ∞.
≤
(n)
|Aǫ |
≤ 2n(H(X,Y )+ǫ)
– p. 14/39
Joint AEP
Teorema Q
Siano (X n , Y n ) seqeuenze di v.c. i.i.d secondo
p(xn , y n ) =
n
i=1 p(xi , xj ).
(n)
Aǫ )
1.
P r((X n , Y n )
2.
(1 − e)2n(H(X,Y )−ǫ)
∈
Allora,
→ 1 per n → ∞.
≤
(n)
|Aǫ |
≤ 2n(H(X,Y )+ǫ)
3. Se X˜n e Y˜n sono indipendenti e scelte secondo p(xn ) e
p(y n ), quindi P r(x˜n , y˜n ) = p(x˜n )p(y˜n ), allora per n → ∞
(n)
(1−e)2−n(I(X;Y )+3ǫ) ≤ P r((X˜n , X˜n ) ∈ Aǫ ) ≤ 2−n(I(X;Y )−3ǫ) .
– p. 14/39
Teorema di Codifica Canale
Teorema Per ogni tasso R < C, esiste una sequenza di
codici (2nR , n) con probabilità massima di errore λ(n) → 0.
– p. 15/39
Teorema di Codifica Canale
Teorema Per ogni tasso R < C, esiste una sequenza di
codici (2nR , n) con probabilità massima di errore λ(n) → 0.
Dim. La dimostrazione si basa sulle seguenti idee
analisi di sequenze lunghe, in modo da sfruttare la
legge dei grandi numeri e, specificamente, le proprietà
delle coppie tipiche.
– p. 16/39
Teorema di Codifica Canale
Teorema Per ogni tasso R < C, esiste una sequenza di
codici (2nR , n) con probabilità massima di errore λ(n) → 0.
Dim. La dimostrazione si basa sulle seguenti idee
analisi di sequenze lunghe, in modo da sfruttare la
legge dei grandi numeri e, specificamente, le proprietà
delle coppie tipiche.
Calcolo della probabilità di errore mediata su una scelta
random del codice.
– p. 16/39
Codifica Canale - Parte Diretta
Generiamo 2nR parole codice i.i.d. scegliendone i simboli
da X indipendentemente in accordo ad una fissata d.p.
p(x).
n è scelta con probabilità
una sequenza
x
Qn
n
p(x ) = i=1 p(xi )
– p. 17/39
Codifica Canale - Parte Diretta
Generiamo 2nR parole codice i.i.d. scegliendone i simboli
da X indipendentemente in accordo ad una fissata d.p.
p(x).
n è scelta con probabilità
una sequenza
x
Qn
n
p(x ) = i=1 p(xi )
un codice

x1 (1)

..
C=
.

...
xn (1)

..
...
.
.
x1 (2nR ) x2 (2nR ) . . . xn (2nR )
con probabilità P r(C) =
x2 (1)
..
.
Q2nR Qn
w=1
i=1 p(xi (w)).
– p. 17/39
Codifica Canale - Il Modello
Consideriamo il seguente modello
Il codice viene scelto in maniera random (vedi sopra)
– p. 18/39
Codifica Canale - Il Modello
Consideriamo il seguente modello
Il codice viene scelto in maniera random (vedi sopra)
il messaggio W da trasmettere viene scelto
uniformemente a caso: P r(W = w) = 2−nR , per ogni
w = 1, 2, . . . , 2nR .
– p. 18/39
Codifica Canale - Il Modello
Consideriamo il seguente modello
Il codice viene scelto in maniera random (vedi sopra)
il messaggio W da trasmettere viene scelto
uniformemente a caso: P r(W = w) = 2−nR , per ogni
w = 1, 2, . . . , 2nR .
La parola codice X n (w), corrispondente alla w-esima
riga di C viene spedita sul canale.
– p. 18/39
Codifica Canale - Il Modello
Consideriamo il seguente modello
Il codice viene scelto in maniera random (vedi sopra)
il messaggio W da trasmettere viene scelto
uniformemente a caso: P r(W = w) = 2−nR , per ogni
w = 1, 2, . . . , 2nR .
La parola codice X n (w), corrispondente alla w-esima
riga di C viene spedita sul canale.
L’output del canale è una sequenza Y n determinata in
accordo alla distribuzione
P (y n |xn (w)) =
n
Y
p(yi |xi (w)).
i=1
– p. 18/39
Codifica Canale - Il Modello
La sequenza Y n viene decodificata come W̃ se
(X n (W̃ ), Y n ) formano coppia tipica
Non esiste un altro messaggio k t.c. (X n (k), Y n )
formano coppia tipica.
– p. 19/39
Codifica Canale - Il Modello
La sequenza Y n viene decodificata come W̃ se
(X n (W̃ ), Y n ) formano coppia tipica
Non esiste un altro messaggio k t.c. (X n (k), Y n )
formano coppia tipica.
se non esiste un tale W o ce ne è più di uno, si emette
un segnale di errore.
– p. 19/39
Codifica Canale - Il Modello
La sequenza Y n viene decodificata come W̃ se
(X n (W̃ ), Y n ) formano coppia tipica
Non esiste un altro messaggio k t.c. (X n (k), Y n )
formano coppia tipica.
se non esiste un tale W o ce ne è più di uno, si emette
un segnale di errore.
Dichiariamo la codifica errata se W̃ 6= W, e denotiamo
con E tale evento.
– p. 19/39
Codifica Canale
La probabilità di errore. La calcoliamo mediata su tutte le
parole del codice, e mediata su tutti i codici possibili:
P r(E) =
X
(n)
P (C)Pe (C)
C
=
X
P (C)
C
=
1
2nR
1
2nR
nR
2
XX
nR
2
X
λw (C)
w=1
P (C)λw (C)
w=1 C
– p. 20/39
Codifica Canale
Poiché mediamo su tutti i codici
X
P (C)λw (C)
C
non dipende da w. Infatti, guardando a tutti codici, la
stessa parola appare lo stesso numero di volte con ogni
indice.
Quindi possiamo assumere, senza perdita di generalità
che l’indice del messaggio inviato sia W = 1, poiché
P (C) =
1
2nR
nR
2
XX
P (C)λw (C) =
w=1 C
= P r(E|W = 1).
X
P (C)λ1 (C)
C
– p. 21/39
Codifica Canale
Sia Y n la sequenza output quando X n (1) viene trasmesso
(codifichiamo W = 1).
Definiamo ∀i, l’evento “l’ i-esima parola codice e Y n
formano coppia tipica”:
(n)
Ei = {(X n (i), Y n ) ∈ Aǫ },
– p. 22/39
Codifica Canale
Sia Y n la sequenza output quando X n (1) viene trasmesso
(codifichiamo W = 1).
Definiamo ∀i, l’evento “l’ i-esima parola codice e Y n
formano coppia tipica”:
(n)
Ei = {(X n (i), Y n ) ∈ Aǫ },
Per la decodifica scelta, quando X n (1) viene
trasmessa, si ha errore se una si verifica tra:
(n)
∈ Aǫ , i 6= 1: l’ evento
(n)
n
n
(X (1), Y ) 6∈ Aǫ : l’evento E1 .
(X n (i), Y n )
Ei ;
– p. 22/39
Codifica Canale
Quindi
P (E) = P r(E|W = 1) = P (E1 ∪ E2 ∪ E3 ∪ · · · ∪ E2nR )
≤ P (E1 ) +
nR
2
X
P (Ei ).
i=2
– p. 23/39
Codifica Canale
Quindi
P (E) = P r(E|W = 1) = P (E1 ∪ E2 ∪ E3 ∪ · · · ∪ E2nR )
≤ P (E1 ) +
nR
2
X
P (Ei ).
i=2
P (E1 ) ≤ ǫ, per n → ∞ (joint AEP 1.);
– p. 23/39
Codifica Canale
Quindi
P (E) = P r(E|W = 1) = P (E1 ∪ E2 ∪ E3 ∪ · · · ∪ E2nR )
≤ P (E1 ) +
nR
2
X
P (Ei ).
i=2
P (E1 ) ≤ ǫ, per n → ∞ (joint AEP 1.);
X n (1) e X n (i) indipendenti ⇒ Y n e X n (i) indipendenti,
∀i 6= 1.
– p. 23/39
Codifica Canale
Quindi
P (E) = P r(E|W = 1) = P (E1 ∪ E2 ∪ E3 ∪ · · · ∪ E2nR )
≤ P (E1 ) +
nR
2
X
P (Ei ).
i=2
P (E1 ) ≤ ǫ, per n → ∞ (joint AEP 1.);
X n (1) e X n (i) indipendenti ⇒ Y n e X n (i) indipendenti,
∀i 6= 1.
⇒ P (Ei ) ≤ 2−n(I(X;Y )−3ǫ) (joint AEP 3.).
– p. 23/39
Codifica Canale
Otteniamo
P (E) ≤ P (E1 ) +
nR
2
X
P (Ei )
i=2
≤ ǫ+
nR
2
X
2−n(I(X;Y )−3ǫ)
i=2
nR
= ǫ + (2
− 1)2−n(I(X;Y )−3ǫ)
≤ ǫ + 23nǫ 2−n(I(X;Y )−R)
≤ 2ǫ,
se scegliamo n sufficientemente grande e R < I(X; Y ) − 3ǫ.
– p. 24/39
Codifica Canale
Se R < I(X; Y ), possiamo scegliere ǫ e n in modo da
(n)
rendere la media (su tutti i codici) di Pe < 2ǫ.
Che possiamo dire della probabilità massima di errore?
– p. 25/39
Codifica Canale
scegliamo p(x) = p∗ (x) = maxp(x) I(X; Y ) cioè quella
che ottiene la capacità
– p. 26/39
Codifica Canale
scegliamo p(x) = p∗ (x) = maxp(x) I(X; Y ) cioè quella
che ottiene la capacità
quindi possiamo sostituire R < C ad R < I(X; Y ).
– p. 26/39
Codifica Canale
scegliamo p(x) = p∗ (x) = maxp(x) I(X; Y ) cioè quella
che ottiene la capacità
quindi possiamo sostituire R < C ad R < I(X; Y ).
(n)
Se la media (su tutti i codici) di Pe (C) è ≤ 2ǫ, allora
(n)
∗
esiste un codice C tale che Pe (C) ≤ 2ǫ.
– p. 26/39
Codifica Canale
scegliamo p(x) = p∗ (x) = maxp(x) I(X; Y ) cioè quella
che ottiene la capacità
quindi possiamo sostituire R < C ad R < I(X; Y ).
(n)
Se la media (su tutti i codici) di Pe (C) è ≤ 2ǫ, allora
(n)
∗
esiste un codice C tale che Pe (C) ≤ 2ǫ.
eliminiamo da C ∗ ogni parola i con λi > 4ǫ
(n)
1 2nR
(sono meno della metá, altr. Pe (C) > 2nR 2 4ǫ = 2ǫ)
– p. 26/39
Codifica Canale
scegliamo p(x) = p∗ (x) = maxp(x) I(X; Y ) cioè quella
che ottiene la capacità
quindi possiamo sostituire R < C ad R < I(X; Y ).
(n)
Se la media (su tutti i codici) di Pe (C) è ≤ 2ǫ, allora
(n)
∗
esiste un codice C tale che Pe (C) ≤ 2ǫ.
eliminiamo da C ∗ ogni parola i con λi > 4ǫ
(n)
1 2nR
(sono meno della metá, altr. Pe (C) > 2nR 2 4ǫ = 2ǫ)
allora
nR
2ǫ ≥
2
1 X
2nR
λi (C ∗ ) ⇒ ∃(i1 , . . . , i2nR−1 ) s.t. λij (C ∗ ) ≤ 4ǫ.
i=1
– p. 26/39
Codifica Canale
Creiamo un nuovo codice che contiene solo tali parole di C ∗
con prob. di errore piccola
C˜∗ = {X n (ij ) ∈ C ∗ | j = 1, 2, . . . , 2nR−1 }.
– p. 27/39
Codifica Canale
Creiamo un nuovo codice che contiene solo tali parole di C ∗
con prob. di errore piccola
C˜∗ = {X n (ij ) ∈ C ∗ | j = 1, 2, . . . , 2nR−1 }.
Tale codice contiene ovviamente 2nR−1 parole, quindi il
suo tasso è R − n1 che per n grande non differisce
significativamente da R.
– p. 27/39
Codifica Canale
Creiamo un nuovo codice che contiene solo tali parole di C ∗
con prob. di errore piccola
C˜∗ = {X n (ij ) ∈ C ∗ | j = 1, 2, . . . , 2nR−1 }.
Tale codice contiene ovviamente 2nR−1 parole, quindi il
suo tasso è R − n1 che per n grande non differisce
significativamente da R.
Concludendo: per ogni R < C, possiamo scegliere un
codice di tasso R′ = R − n1 , con probabilità massima di
errore λ(n) ≤ 4ǫ.
– p. 27/39
Codifica Canale - Osservazioni
La scelta random del codice serve per la prova non per
la codifica
– p. 28/39
Codifica Canale - Osservazioni
La scelta random del codice serve per la prova non per
la codifica
Mediando proviamo che esiste almeno un codice con le
proprietà desiderate
– p. 28/39
Codifica Canale - Osservazioni
La scelta random del codice serve per la prova non per
la codifica
Mediando proviamo che esiste almeno un codice con le
proprietà desiderate
Tale codice può essere trovato (ricerca esaustiva !?!)
ed il processo di codifica e decodifica rimane
completamente deterministico.
– p. 28/39
Codifica Canale - Osservazioni
La scelta random del codice serve per la prova non per
la codifica
Mediando proviamo che esiste almeno un codice con le
proprietà desiderate
Tale codice può essere trovato (ricerca esaustiva !?!)
ed il processo di codifica e decodifica rimane
completamente deterministico.
La ricerca di tale codice è esponenziale
– p. 28/39
Codifica Canale - Osservazioni
La scelta random del codice serve per la prova non per
la codifica
Mediando proviamo che esiste almeno un codice con le
proprietà desiderate
Tale codice può essere trovato (ricerca esaustiva !?!)
ed il processo di codifica e decodifica rimane
completamente deterministico.
La ricerca di tale codice è esponenziale
Possiamo sceglierlo random e avere buone chance di
trovarne uno con le caratteristiche richieste. Però la
decodifica risulta altamente inefficiente.
– p. 28/39
Codifica Canale - Osservazioni
La scelta random del codice serve per la prova non per
la codifica
Mediando proviamo che esiste almeno un codice con le
proprietà desiderate
Tale codice può essere trovato (ricerca esaustiva !?!)
ed il processo di codifica e decodifica rimane
completamente deterministico.
La ricerca di tale codice è esponenziale
Possiamo sceglierlo random e avere buone chance di
trovarne uno con le caratteristiche richieste. Però la
decodifica risulta altamente inefficiente.
Un problema fondamentale: trovare codici con tasso
prossimo a C e con una struttura che mantenga la
decodifica efficiente
– p. 28/39
Codifica Canale - Parte Inversa
Ci rimane da dimostrare che per ogni sequenza di
codici (2nR , n) con λ(n) → n deve valere R < C.
Cominceremo con il dimostrare due lemmi che ci
serviranno per la dimostrazione.
Pn
n
n
I(X , Y ) ≤ i=1 I(Xi , Yi )
(n)
H(X n |Y n ) ≤ 1 + Pe nR. (Disuguaglianza di Fano)
– p. 29/39
Codifica Canale - Parte Inversa
Lemma (Disuguaglianza di Fano) Consideriamo un DMC.
Sia il messaggio in input W scelto in accordo alla
distribuzione uniforme tra 2nR messaggi. Sia C il codice, Y n
la parola ricevuta in output al canale, g(·) la funzione di
(n)
decodifica e Pe = P r(W 6= g(Y n )). Allora
(n)
H(X n |Y n ) ≤ 1 + Pe nR.
– p. 30/39
Disuguaglianza di Fano
(
1, se g(Y n ) 6= W,
Dim. Definiamo E =
0, se g(Y n ) = W.
Espandiamo H(E, W |Y n ) in due modi diversi
H(E, W |Y n ) = H(W |Y n ) + H(E|W, Y n )
= H(E|Y n ) + H(W |E, Y n )
– p. 31/39
Disuguaglianza di Fano
(
1, se g(Y n ) 6= W,
Dim. Definiamo E =
0, se g(Y n ) = W.
Espandiamo H(E, W |Y n ) in due modi diversi
H(E, W |Y n ) = H(W |Y n ) + H(E|W, Y n )
= H(E|Y n ) + H(W |E, Y n )
Notiamo che H(E|W, Y n ) = 0, H(E|Y n ) ≤ H(E) ≤ 1, e
H(W |E, Y n ) =
1
X
P (E = i)H(W |Y n , E = i)
i=0
(n)
(n)
(n)
= (1 − Pe )0 + Pe log(2nR − 1) ≤ Pe nR.
– p. 31/39
Disuguaglianza di Fano
Dim. (cont.)
Ne consegue che
(n)
H(W |Y n ) ≤ 1 + Pe nR
– p. 32/39
Disuguaglianza di Fano
Dim. (cont.)
Ne consegue che
(n)
H(W |Y n ) ≤ 1 + Pe nR
da cui segue la tesi, in quanto H(X n |Y n ) ≤ H(W |Y n ),
poiché X n è funzione di W.
– p. 32/39
Lemma Sia Y n l’output di un DMC per input P
X n . Allora,
per ogni distribuzione p(xn ), vale I(X n ; Y n ) ≤
n
i=1 I(Xi ; Yi ).
Dim.
I(X n , Y n ) = H(Y n ) − H(Y n |X n )
n
X
H(Yi |Y1 , . . . , Yi−1 , X n )
= H(Y n ) −
= H(Y n ) −
i=1
n
X
H(Yi |Xi ) (no memoria)
i=1
≤
n
X
i=1
H(Yi ) −
n
X
i=1
H(Yi |Xi ) =
n
X
I(Xi ; Yi ).
i=1
– p. 33/39
Lemma Sia Y n l’output di un DMC per input P
X n . Allora,
per ogni distribuzione p(xn ), vale I(X n ; Y n ) ≤
n
i=1 I(Xi ; Yi ).
Corollario Sia Y n l’output di un DMC per input X n . Allora,
per ogni distribuzione p(xn ), vale I(X n ; Y n ) ≤ nR.
– p. 34/39
Codifica Canale - Parte Inversa
Teorema Ogni sequenza di codici (2nR , n) con λ(n) → 0,
deve avere R < C.
Dim.
λ(n)
→0⇒
(n)
Pe
→ 0.
– p. 35/39
Codifica Canale - Parte Inversa
Teorema Ogni sequenza di codici (2nR , n) con λ(n) → 0,
deve avere R < C.
Dim.
λ(n)
→0⇒
(n)
Pe
→ 0.
Consideriamo il messaggio W scelto uniformemente in
{1, 2, . . . , 2nR },
(quindi H(W ) = nR)
– p. 35/39
Codifica Canale - Parte Inversa
Teorema Ogni sequenza di codici (2nR , n) con λ(n) → 0,
deve avere R < C.
Dim.
λ(n)
→0⇒
(n)
Pe
→ 0.
Consideriamo il messaggio W scelto uniformemente in
{1, 2, . . . , 2nR },
(quindi H(W ) = nR)
(n)
Pe
= P r(g(Y n ) 6= W ).
– p. 35/39
Codifica Canale - Parte Inversa
Teorema Ogni sequenza di codici (2nR , n) con λ(n) → 0,
deve avere R < C.
Dim.
λ(n)
→0⇒
(n)
Pe
→ 0.
Consideriamo il messaggio W scelto uniformemente in
{1, 2, . . . , 2nR },
(quindi H(W ) = nR)
(n)
Pe
= P r(g(Y n ) 6= W ).
Allora,
nR = H(W ) = H(W |Y n ) + I(W ; Y n )
≤ H(W |Y n ) + I(X n (W ); Y n )
[W → X n (W ) → Y n ]
(n)
≤ 1 + Pe nR + nC.
– p. 35/39
Parte Inversa (cont.)
Teorema Ogni sequenza di codici (2nR , n) con λ(n) → 0,
deve avere R < C.
Dim. (cont.)
(n)
nR ≤ 1 + Pe nR + nC.
– p. 36/39
Parte Inversa (cont.)
Teorema Ogni sequenza di codici (2nR , n) con λ(n) → 0,
deve avere R < C.
Dim. (cont.)
(n)
nR ≤ 1 + Pe nR + nC.
Dividendo per n otteniamo
1
(n)
R ≤ + Pe R + C
n
– p. 36/39
Parte Inversa (cont.)
Teorema Ogni sequenza di codici (2nR , n) con λ(n) → 0,
deve avere R < C.
Dim. (cont.)
(n)
nR ≤ 1 + Pe nR + nC.
Dividendo per n otteniamo
1
(n)
R ≤ + Pe R + C
n
e per n → ∞ abbiamo la tesi, usando
(n)
Pe
→ 0 e 1/n → 0.
– p. 36/39
Parte Inversa (cont.)
Riscriviamo la disuguaglianza R ≤
(n)
Pe
1
n
(n)
+ Pe R + C come
C
1
≥1− −
R nR
– p. 37/39
Parte Inversa (cont.)
Riscriviamo la disuguaglianza R ≤
(n)
Pe
1
n
(n)
+ Pe R + C come
C
1
≥1− −
R nR
Questo mostra che per R > C la probabilità di errore si
mantiene > 0 per n → ∞.
– p. 37/39
Parte Inversa (cont.)
Riscriviamo la disuguaglianza R ≤
(n)
Pe
1
n
(n)
+ Pe R + C come
C
1
≥1− −
R nR
Questo mostra che per R > C la probabilità di errore si
mantiene > 0 per n → ∞.
ma deve valere per ogni n. Infatti, se avessimo codici
(n)
con Pe = 0 per n piccoli potremmo estenderli a codici
di lunghezza maggiore per concatenazione.
– p. 37/39
Parte Inversa (cont.)
Riscriviamo la disuguaglianza R ≤
(n)
Pe
1
n
(n)
+ Pe R + C come
C
1
≥1− −
R nR
Questo mostra che per R > C la probabilità di errore si
mantiene > 0 per n → ∞.
ma deve valere per ogni n. Infatti, se avessimo codici
(n)
con Pe = 0 per n piccoli potremmo estenderli a codici
di lunghezza maggiore per concatenazione.
In conclusione, non si può ridurre arbitrariamente la
probabilità d’errore a tassi superiori alla capacità.
– p. 37/39
Codifica Sorgente–Canale
Teorema Se V1 , . . . , Vn soddisfano la PEA allora esiste una
(n)
codice sorgente-canale con Pe → 0 se H(V ) < C .
Se H(V ) > C la probabilitá di errore non puó essere resa
arbitrariamente piccola.
– p. 38/39
Codifica Sorgente–Canale
Teorema Se V1 , . . . , Vn soddisfano la PEA allora esiste una
(n)
codice sorgente-canale con Pe → 0 se H(V ) < C .
Se H(V ) > C la probabilitá di errore non puó essere resa
arbitrariamente piccola.
Dim.n
n
n
n
^n
V
X (V )
Y
V
– p. 38/39
Codifica Sorgente–Canale
Teorema Se V1 , . . . , Vn soddisfano la PEA allora esiste una
(n)
codice sorgente-canale con Pe → 0 se H(V ) < C .
Se H(V ) > C la probabilitá di errore non puó essere resa
arbitrariamente piccola.
Dim.n
n
n
n
^n
V
X (V )
(n)
|Aǫ |
2n(H(V )+ǫ)
Y
V
(n)
P (Aǫ )
>1−ǫ
≤
e
PEA ⇒
Codifichiamo solo sequenze tipiche ⇒ 2n(H(V )+ǫ) indici
⇒ se R = H(V ) + ǫ < C possiamo trasmettere sul canale
con prob. err < ǫ
Quindi
(n)
Pe = P (V n 6= V̂ n )
(n)
(n)
≤ P (V n ∈
/ Aǫ ) + P (g(Y n ) 6= V n |V n ∈ Aǫ ) ≤ ǫ + ǫ = 2ǫ
– p. 38/39
Codifica Sorgente–Canale
Parte inversa. Dalla disuguaglianza di Fano
(n)
(n)
n
n
n
H(V |V̂ ) ≤ 1 + Pe log |V | = 1 + Pe n log |V|
– p. 39/39
Codifica Sorgente–Canale
Parte inversa. Dalla disuguaglianza di Fano
(n)
(n)
n
n
n
H(V |V̂ ) ≤ 1 + Pe log |V | = 1 + Pe n log |V|
Quindi
H(V ) =
≤
≤
≤
H(V n )
1
1
H(V1 . . . Vn )
n n
=
= H(V |V̂ ) + I(V n ; V̂ n )
n
n
n
n
1
1
(n)
(1 + Pe n log |V|) + I(V n ; V̂ n )
n
n
1
1
(n)
(1 + Pe n log |V|) + I(X n ; Y n )
n
n
1
(n)
+ Pe log |V| + C
n
– p. 39/39
Codifica Sorgente–Canale
Parte inversa. Dalla disuguaglianza di Fano
(n)
(n)
n
n
n
H(V |V̂ ) ≤ 1 + Pe log |V | = 1 + Pe n log |V|
Quindi
H(V ) =
≤
≤
≤
H(V n )
1
1
H(V1 . . . Vn )
n n
=
= H(V |V̂ ) + I(V n ; V̂ n )
n
n
n
n
1
1
(n)
(1 + Pe n log |V|) + I(V n ; V̂ n )
n
n
1
1
(n)
(1 + Pe n log |V|) + I(X n ; Y n )
n
n
1
(n)
+ Pe log |V| + C
n
Per n → ∞, se
(n)
Pe
→ 0 si ha H(V ) ≤ C .
– p. 39/39