Il secondo teorema di Shannon

Il secondo teorema di Shannon
Appunti scritti da Alberto Leporati
e-mail: [email protected]
Dipartimento di Informatica, Sistemistica e Comunicazione (DISCo)
Università degli Studi di Milano — Bicocca
Via Bicocca degli Arcimboldi 8, 20126 Milano
1
Alcuni preliminari matematici
Nel corso della dimostrazione del secondo teorema di Shannon utilizzeremo la
seguente maggiorazione:
λn X
n
k=0
k
≤ 2nH(λ)
con 0 < λ <
1
2
dove H(·) è la funzione entropia per una sorgente binaria (o Bernoulliana), in
grado cioè di emettere due simboli. Si assume che λn sia un intero.
Useremo inoltre la legge debole dei grandi numeri.
Teorema 1 (Legge debole dei grandi numeri). Siano X1 , X2 , . . . , Xn variabili casuali indipendenti, con la stessa distribuzione di probabilità, aventi media
µ e varianza σ 2 . Allora, per ogni ε > 0 e δ > 0 esiste un intero n0 tale che, per
ogni n > n0 ,
" n
#
1 X
P Xi − µ ≤ ε ≥ 1 − δ
n
i=1
o, equivalentemente,
" n
#
1 X
P Xi − µ > ε < δ
n
i=1
Il teorema afferma che la media dei valori di X1 , X2 , . . . , Xn può essere portata, con alta probabilità, vicino quanto si vuole al valore atteso µ. Una interpretazione alternativa ed equivalente è la seguente: la probabilità che la media
dei valori di X1 , X2 , . . . , Xn si discosti da µ di una quantità ε > 0 scelta a piacere
può essere resa arbitrariamente piccola.
1
Si pensi, ad esempio, a X1 , X2 , . . . , Xn come alle variabili casuali che descrivono i risultati di n esperimenti identici e indipendenti. Ogni esperimento darà
in media il valore µ. La legge dei grandi numeri ci dice che si può portare il
valore medio della sequenza di esperimenti vicino quanto si vuole al valore medio
µ di ogni singolo esperimento. Ciò non avviene con certezza, ma con probabilità
vicina a 1 quanto si vuole.
Useremo la legge dei grandi numeri quando codificheremo i messaggi in estensioni molto grandi del canale. Spediremo nel canale sequenze di n cifre binarie.
La spedizione di ciascuna cifra binaria costituirà un esperimento Bernoulliano che
avrà probabilità di errore pari a Q. Nella spedizione del blocco di n cifre binarie
ci attenderemo quindi un numero medio di errori pari a nQ. La legge dei grandi
numeri ci assicurerà che il numero di errori che si sono effettivamente verificati,
diviso per n, potrà essere portato vicino a Q quanto si vuole, con probabilità
vicina a 1 quanto si vuole, a patto di lavorare con valori di n sufficientemente
grandi (lavorando quindi in estensioni del canale sufficientemente grandi, ovvero
spedendo sequenze sufficientemente lunghe di cifre binarie).
2
Il secondo teorema di Shannon
Dimostriamo ora un risultato fondamentale della Teoria dell’Informazione: in
un canale, anche in presenza di rumore, si riesce a trasmettere avvicinandosi
arbitrariamente alla capacità del canale, mantenendo l’affidabilità del canale (cioè
la probabilità di ricevere correttamente i messaggi) arbitrariamente vicina a 1.
Dimostreremo il teorema per il canale binario simmetrico (CBS), sia perché
la dimostrazione è più semplice, sia perché è il tipo di canale più usato in pratica. Daremo anche alcune indicazioni su come estendere il teorema a canali più
generali.
2.1
Regole di decisione
Dato un canale, supponiamo di aver ricevuto il simbolo bj ∈ B. Come facciamo
a decidere quale simbolo ai ∈ A è stato spedito? La scelta dipende dal canale,
ovvero dalle probabilità P (bj |ai ), e anche da come lo si usa, cioè dalle probabilità
p(ai ) associate ai simboli ai ∈ A.
Ad esempio, consideriamo il canale descritto dalla seguente matrice:
a1
a2
b1 b2 b3
0.6 0.5 0.4
0.4 0.5 0.6
e supponiamo che i simboli in ingresso siano equiprobabili:
p(a1 ) = p(a2 ) =
2
1
2
Allora, se riceviamo b1 è ragionevole supporre che sia stato spedito a1 . Analogamente, se riceviamo b3 è ragionevole supporre che che sia stato spedito a2 . Se
invece riceviamo b2 , potrebbe essere stato spedito sia a1 che a2 . Indichiamo con
d(bj ) il simbolo di A scelto tramite la regola di decisione d, quando si riceve il
simbolo bj .
In generale, una regola di decisione è una funzione d : B → A che ad ogni
simbolo di B associa uno e un solo simbolo di A. Poiché |B| = s e |A| = q, ci
sono q s diverse regole di decisione. Tra tutte queste si sceglie solitamente una
regola di decisione di massima verosimiglianza, che prescrive di prendere — per
ogni simbolo di B ricevuto — il simbolo di A più probabile. Se assumiamo che i
simboli di A vengano scelti dal mittente con probabilità uniforme, una regola di
decisione di massima verosimiglianza prescrive di associare a bj ∈ B il simbolo
a∗ ∈ A per il quale:
P (a∗ |bj ) ≥ P (ai |bj )
∀i
Essendo queste delle probabilità all’indietro, usando il teorema di Bayes possiamo
esprimerle come:
P (bj |a∗ ) p(a∗ )
P (bj |ai ) p(ai )
≥
p(bj )
p(bj )
∀i
Poiché abbiamo supposto che i simboli di A siano equiprobabili (e quindi p(a∗ ) =
p(ai ) = 1q ), otteniamo:
P (bj |a∗ ) ≥ P (bj |ai )
∀i
Per il canale di cui sopra abbiamo quindi le seguenti due regole di decisione
di massima verosimiglianza:
Regola 1
Regola 2
d(b1 ) = a1
d(b2 ) = a1
d(b3 ) = a2
d(b1 ) = a1
d(b2 ) = a2
d(b3 ) = a2
Si osservi che, in generale, la regola di decisione di massima verosimiglianza non
è unica.
Poiché scegliamo di associare a∗ al simbolo bj osservato, la probabilità di
commettere un errore è data da:
P (E|bj ) = 1 − P (a∗ |bj )
L’errore medio PE è dato quindi da:
X
PE =
P (E|bj )p(bj )
B
=
X
B
p(bj ) −
X
B
3
P (a∗ |bj )p(bj )
=1−
X
P (a∗ |bj )p(bj )
B
=1−
X P (bj |a∗ ) p(a∗ )
p(bj )
B
p(bj )
= essendo i simboli di A equiprobabili, vale p(a∗ ) =
1 X
=1−
P (bj |a∗ )
q
1
q
B
2.2
Il canale binario simmetrico (CBS)
Dimostriamo ora il teorema di Shannon per il CBS:
P
0
0
Q
Q
1
1
P
dove P è la probabilità di avere una trasmissione corretta, e Q = 1 − P è la
probabilità di avere un errore di trasmissione. Assumiamo Q < 12 , dato che:
• se Q = 12 , abbiamo un canale completamente rumoroso, in cui i simboli di
uscita sono indipendenti dai simboli dati in ingresso, e la capacità è 0;
• se Q > 12 , il canale sbaglia a trasmettere la maggior parte delle volte.
Tuttavia, possiamo scambiare il ruolo di 0 e 1 in uscita e ottenere un canale
in cui Q < 12 .
Lavoriamo con l’n–esima estensione del canale; in altre parole, spediamo blocchi
di n bit. Indichiamo con (CBS)n l’n–esima estensione del CBS. Inoltre, indichiamo con A e con B rispettivamente gli alfabeti di ingresso e di uscita di (CBS)n .
Si noti che l’n–esima estensione di un CBS è un canale uniforme.
Ci sono 2n configurazioni di n bit, e quindi potremmo pensare di porre A =
B = {0, 1}n . Tuttavia, se vogliamo proteggerci dal rumore non possiamo usare
tutte le 2n possibili configurazioni per A: come abbiamo visto studiando i codici
a correzione d’errore, i messaggi validi devono costituire un sottoinsieme di tutti
i possibili messaggi che transitano lungo il canale, e devono avere tra loro una
distanza di Hamming abbastanza grande. D’altra parte, dal canale può uscire
qualunque sequenza di n cifre binarie, e quindi avremo A ⊂ B = {0, 1}n (dove
con ⊂ si intende l’inclusione stretta).
Quanti messaggi ci vogliono allora per avvicinarsi alla capacità di canale? Se
supponiamo di usare M messaggi equiprobabili, l’informazione data da ciascuno
4
è:
I(ai ) = log2
1
= log2 M
1/M
Come abbiamo visto, la capacità di un CBS è:
C = 1 − H(P ) = 1 − H(Q)
per messaggi formati da una cifra binaria; pertanto, per l’n–esima estensione la
capacità è:
nC = n[1 − H(Q)]
Per avvicinarsi alla capacità di canale deve valere:
I(ai ) = log2 M = n(C − ε1 )
con ε1 > 0, ovvero:
2nC
2nε1
Questo significa che, facendo crescere n, il denominatore può essere reso arbitrariamente grande; in altre parole, stiamo prendendo come messaggi validi una
piccola frazione di tutti i possibili messaggi di lunghezza n.
M = 2n(C−ε1 ) =
2.3
Codifica casuale
La seconda questione è: come facciamo a costruire un codice i cui messaggi validi
siano equiprobabili e abbastanza distanti tra loro? Dato che non lo sappiamo
fare in generale, ci affidiamo a una codifica casuale. Infatti, se n è grande allora
due punti scelti a caso nello spazio n–dimensionale saranno molto probabilmente
distanti fra loro.
Per codificare ogni messaggio, lanciamo una moneta per n volte e registriamo
la sequenza di 0 e 1 risultante. Faremo quindi in totale nM lanci della moneta, e
otterremo uno dei 2nM possibili codici. Un metodo alternativo (ed equivalente a
quello appena descritto) di costruire il codice casuale è quello di scrivere tutte le
possibili sequenze di n cifre binarie su altrettante striscioline di carta, metterle
in un contenitore e fare M estrazioni casuali con reimmissione. Con entrambi
i metodi è possibile che due messaggi diversi vengano codificati con la stessa
sequenza di n cifre binarie; tuttavia, per n grande la probabilità che ciò avvenga
è molto bassa.
Immaginiamo ora gli M messaggi validi immersi nello spazio di Hamming
n–dimensionale (cioè lo spazio n–dimensionale in cui la distanza è quella di Hamming). La probabilità che si verifichi un errore di trasmissione in qualsiasi cifra
di ogni messaggio è Q = 1 − P , e quindi durante la trasmissione di un messaggio
ci attendiamo che avvengano mediamente nQ errori. Consideriamo una sfera il
cui centro è il messaggio inviato ai , con un raggio pari a nQ. Supponiamo di
5
incrementare il raggio della quantità nε2 (cioè di una piccola frazione di n), con
ε2 > 0. Il nuovo raggio è:
r = n(Q + ε2 )
Il valore di ε2 deve essere abbastanza piccolo da valere Q + ε2 < 12 ; il valore di
ε2 rispetto a ε1 verrà determinato più avanti.
Per la legge dei grandi numeri, se n è grande il messaggio ricevuto bj si troverà
fuori dalla nuova sfera con probabilità molto bassa. Quindi, se usiamo la regola
di decisione di massima verosimiglianza e siamo in grado di dimostrare che quasi
sicuramente nessuna sfera si interseca con altre sfere, abbiamo che il ricevente
può quasi essere sicuro su quale messaggio è stato spedito. Guardando le cose
dal punto di vista del ricevente, ciò equivale a considerare una sfera centrata
nel messaggio ricevuto bj , e la probabilità che il messaggio ai inviato si trovi
all’interno della sfera.
La regola di decisione di massima verosimiglianza ha una semplice interpretazione in termini di distanza di Hamming. Sia ai il messaggio inviato dal mittente,
e bj quello ricevuto. Se la distanza di Hamming tra ai e bj è D, allora ai e bj
differiscono in esattamente D posizioni, e la probabilità di ricevere bj avendo
spedito ai è uguale alla probabilità che avvengano D trasmissioni (di una singola
cifra binaria) errate e n − D trasmissioni corrette:
P (bj |ai ) = QD (1 − Q)n−D
Essendo Q < 12 , questa quantità diminuisce all’aumentare di D. Quindi, più
lontano è bj da ai e minore è la probabilità di riceverlo. La regola di decisione di
massima verosimiglianza seleziona il messaggio valido che massimizza P (bj |ai ),
ovvero il messaggio valido più vicino a bj rispetto alla distanza di Hamming.
Quindi, correggere il messaggio ricevuto scegliendo il messaggio valido che
ha distanza di Hamming minima equivale ad utilizzare la regola di massima
verosimiglianza. Ciò avviene sempre quando si è in presenza di rumore bianco.
Nel caso in cui due o più messaggi validi si trovino alla stessa distanza (minima)
dal messaggio ricevuto, il ricevente non può far altro che tirare a indovinare.
Se i messaggi validi che hanno distanza minima dal messaggio ricevuto sono k,
otterremo il messaggio corretto con probabilità k1 .
La regola di massima verosimiglianza è però difficile da analizzare. Useremo
pertanto un’altra regola di decisione che è molto simile. Nonostante tale regola
non sia cosı̀ buona quanto la regola di massima verosimiglianza, ci consentirà
comunque di ottenere una probabilità d’errore piccola quanto vogliamo. La regola
di decisione adottata consiste nel considerare la sfera di raggio r = n(Q + ε2 ),
centrata in bj e, se c’è un solo messaggio a ∈ A all’interno di questa sfera,
sceglierlo.
Scriviamo ora una formula che esprime la probabilità di non riuscire a decodificare correttamente il messaggio, utilizzando tale regola. Si verifica un errore
se ai non si trova all’interno della sfera S(r) centrata in bj , oppure se in tale sfera
6
c’è più di un simbolo di A (dato che in tal caso non sappiamo quale scegliere per
decodificare bj ). Quindi la probabilità PE d’errore è:
PE = P[ai 6∈ S(r)] + P[ai ∈ S(r)] · P[almeno un altro messaggio valido ∈ S(r)]
Poiché P[ai ∈ S(r)] ≤ 1, possiamo scrivere:
PE ≤ P[ai 6∈ S(r)] + P[almeno un altro messaggio valido ∈ S(r)]
La frase “almeno un altro messaggio valido ∈ S(r)” significa “uno o più messaggi validi diversi da ai ∈ S(r)”. Poiché, dato un numero finito di eventi
E1 , E2 , . . . , En (non necessariamente disgiunti) vale:
P[E1 ∨ E2 ∨ . . . ∨ En ] ≤ P[E1 ] + P[E2 ] + . . . + P[En ]
allora:
P[almeno un altro messaggio valido ∈ S(r)] ≤
X
P[a ∈ S(r)]
a∈A\{ai }
da cui:
PE ≤ P[ai 6∈ S(r)] +
X
P[a ∈ S(r)]
a∈A\{ai }
Il primo termine è la probabilità che il messaggio valido ai non si trovi nella sfera
di raggio r (che è di poco maggiore della distanza di Hamming corrispondente a
nQ errori di trasmissione, che è il numero di errori che ci aspettiamo in media)
centrata in bj , che è il messaggio ricevuto. Tale probabilità è uguale alla probabilità che il messaggio bj ricevuto non si trovi nella sfera di raggio r centrata in
ai . Il secondo termine è la somma, su tutti i messaggi non inviati, che ciascuno
di questi si trovi nella sfera di raggio r centrata in bj . Speriamo che, usando una
codifica casuale, la probabilità che uno di questi messaggi si trovi in tale sfera sia
molto bassa. Questa speranza nasce dal fatto che, per n molto grande, è molto
improbabile che due messaggi presi a caso nello spazio n–dimensionale si trovino
vicini.
Per la legge dei grandi numeri, il primo termine (che dipende solamente da ai )
può essere reso più piccolo di qualunque reale positivo δ = δ(ε2 , n) (la cui scelta
cioè dipende da ε2 e da n) prefissato aumentando il valore di n, cioè la lunghezza
dei messaggi trasmessi. Infatti, come abbiamo detto, il numero medio di errori
che si verificano durante la trasmissione di una sequenza di n cifre binarie è nQ.
Per ogni valore fissato di n ci sarà una probabilità che il numero effettivo di errori
superi il suo valore medio di nε2 o più. Man mano che n cresce, però, ciò diventa
sempre meno probabile; più precisamente, per la legge debole dei grandi numeri
vale:
∀ ε2 , δ > 0 ∃ n0
tale che ∀ n > n0
P[numero di errori > nQ + nε2 ] < δ
7
h
i
(equivalentemente, P numero din errori−nQ ≤ ε2 ≥ 1 − δ). Questo significa
che, prendendo n sufficientemente grande, possiamo essere sicuri che:
P[ai 6∈ S(nQ + nε2 )] < δ
con δ arbitrariamente piccolo. Pertanto abbiamo:
X
PE ≤ δ +
P[a ∈ S(r)]
a∈A\{ai }
2.4
Il codice casuale medio
Per poter valutare la sommatoria presente nell’ultima disuguaglianza, facciamo
ora la media su tutti i possibili codici casuali.
In ogni codifica casuale abbiamo M = 2n(C−ε1 ) messaggi di lunghezza n, e
ci sono 2nM possibili codici casuali. Supponiamo che tutti questi codici siano
1
equiprobabili, cioè che ciascuno venga scelto con probabilità 2nM
. Indichiamo
f
con PE la media, pesata con tali probabilità, delle probabilità di errore. Tenendo
conto che δ è una costante, e che |A| = M , abbiamo:
e
Pf
E ≤ δ + (M − 1) · P[a ∈ S(r)]
e ∈ S(r)]
≤ δ + M · P[a
(a 6= ai )
(1)
(la tilde indica sempre la media calcolata su tutti i possibili codici casuali).
e ∈ S(r)] (per a 6= ai ) fissiamo l’attenzione su un qualunque
Per calcolare P[a
messaggio a 6= ai . La probabilità che a ∈ S(r) è il rapporto tra il volume della
sfera e il volume totale dello spazio. Indichiamo con N (r) il numero di punti
presenti all’interno della sfera S(r). Poiché il volume totale dello spazio è 2n ,
abbiamo:
e ∈ S(r)] = N (r)
P[a
2n
Dato che stiamo lavorando in uno spazio di Hamming, vale:
N (r) = 1 +
X
r n
n
n
n
+
+ ... +
=
1
2
r
k
k=0
Ricordiamo inoltre che vale:
r = n(Q + ε2 )
e
Q + ε2 <
1
2
Possiamo applicare la disuguaglianza:
λn X
n
k=0
k
≤ 2nH(λ) ,
8
con 0 < λ <
1
2
a N (r), ponendo λ = Q + ε2 ; otteniamo:
N (r) ≤ 2nH(λ)
e quindi:
e ∈ S(r)] ≤ 2−n[1−H(λ)]
P[a
(con a 6= ai )
Tornando a Pf
E , l’equazione (1) diventa:
−n[1−H(λ)]
Pf
E ≤δ+M ·2
(2)
Ricordiamo che la capacità dei CBS è:
C = 1 − H(P ) = 1 − H(Q)
Pertanto, l’esponente che compare nell’equazione (2) può essere scritto come:
1 − H(λ) = 1 − H(Q + ε2 )
= 1 − H(Q) + H(Q) − H(Q + ε2 )
= C − [H(Q + ε2 ) − H(Q)]
(3)
Dato che la funzione entropia ha la convessità verso il basso, e può essere
limitata superiormente tracciando una retta tangente in qualsiasi punto di ascissa
Q ∈ (0, 1), vale:
dH H(Q + ε2 ) ≤ H(Q) + ε2 ·
dx Q
dove:
Essendo Q <
1
2
dH 1
1−Q
1
= log
= log − log
dx Q
Q
1−Q
Q
vale:
2Q < 1
e quindi:
da cui
Q<1−Q
da cui
dH 1−Q
>0
= log
dx Q
Q
Pertanto l’equazione (3) diventa:
1 − H(λ) ≥ C − ε2 log
dove abbiamo posto:
ε3 = ε2 log
9
1−Q
= C − ε3
Q
1−Q
Q
1−Q
>1
Q
Quindi l’equazione (2) diventa:
−n(C−ε3 )
Pf
E ≤δ+M ·2
≤ δ + 2n(C−ε1 ) 2−n(C−ε3 )
≤ δ + 2−n(ε1 −ε3 )
Questo significa che se scegliamo ε2 abbastanza piccolo da avere:
ε1 − ε3 = ε1 − ε2 log
1−Q
>0
Q
allora l’errore medio Pf
E può essere reso arbitrariamente piccolo scegliendo n
sufficientemente grande.
Avendo dimostrato che il codice medio, calcolato su tutti i possibili codici
casuali, soddisfa i requisiti richiesti, esisterà almeno un codice casuale che li
soddisfa. Abbiamo cosı̀ dimostrato il secondo teorema di Shannon, che possiamo
parafrasare come segue.
Teorema 2 (Secondo teorema di Shannon). Esistono codici che sono arbitrariamente affidabili e che possono trasmettere una quantità di informazione
arbitrariamente vicina alla capacità di canale (usando un’opportuna estensione
del CBS).
Cosa impariamo da questo teorema? Anzitutto impariamo che esistono dei
“buoni” codici dal punto di vista teorico. Il teorema di Shannon non ci mostra esattamente come costruire un buon codice, e quindi la dimostrazione non
è costruttiva. D’altra parte, il teorema ci fornisce un metodo che genererà dei
buoni codici in media, e quindi non si può neanche dire che la dimostrazione sia
puramente esistenziale. Vediamo anche che in tali codici bisogna spedire dei messaggi molto lunghi, e quindi in ogni messaggio bisognerà correggere molti errori.
Spedire messaggi molto lunghi significa che il mittente dovrà raccogliere molte
informazioni prima di spedire ogni messaggio, il che non è molto pratico. Inoltre, il ricevente dovrà utilizzare delle tabelle di decodifica molto grosse: infatti,
essendo il codice utilizzato casuale, non siamo in grado di dare una descrizione
compatta dei processi di codifica e decodifica, come avviene ad esempio per i
codici di Hamming. Si tratta quindi di un importante risultato teorico, che però
non ci aiuta molto nella pratica.
2.5
Il teorema di Shannon per canali generici
La dimostrazione del teorema di Shannon per canali generici segue lo schema della
dimostrazione per i CBS. La grossa differenza è che dobbiamo trovare una metrica
equivalente a quella di Hamming (che tra l’altro va bene solo per un canale dotato
di rumore bianco). Dobbiamo poi contare il numero di possibili messaggi che si
trovano all’interno di una “sfera”, definita usando tale metrica. Infine, la formula
10
che esprime la capacità di canale non è più C = 1 − H(P ) = 1 − H(Q), ma
dobbiamo tornare alla definizione.
La metrica di cui abbiamo bisogno deve tener conto della probabilità che
si verifichino errori durante la trasmissione. Se il rumore non è più bianco, le
sfere diventano degli ovali che sono più lunghi nelle direzioni in cui gli errori
sono più probabili. Si prendono poi degli ovali aventi raggi tali che ci sia la
stessa probabilità di errore in ogni direzione, centrati nel simbolo bj ricevuto, e
li si ingrandisce come prima, in modo tale che (per la legge dei grandi numeri)
quando n è sufficientemente grande, quasi certamente il messaggio ai spedito si
trovi all’interno dell’ovale. Il valore di n deve anche essere abbastanza grande
in modo tale che la probabilità che gli ovali si sovrappongano sia bassa. Infine,
scegliamo il numero M di messaggi da spedire in modo da avvicinarci alla capacità
del canale.
Per il resto, la dimostrazione procede come quella per il CBS.
3
La disuguaglianza di Fano
Dimostriamo ora la disuguaglianza di Fano, che ci servirà per dimostrare l’inverso
del teorema di Shannon.
Poniamo innanzitutto:
X
PE =
P (a, b)
B,A\{a∗ }
e
PE = 1 − PE =
X
P (a∗ , b)
B
Consideriamo l’espressione:
q−1
1
+ PE log
PE
PE
X
q−1 X
1
=
P (a, b) log
+
P (a∗ , b) log
PE
PE
B
B,A\{a∗ }
H(PE ) + PE log(q − 1) = PE log
L’equivocazione H(A|B) vale:
X
H(A|B) =
p(b)H(A|b)
B
=
X
p(b)
B
=
X
P (a|b) log
A
P (a, b) log
B,A
=
X
X
B,A\{a∗ }
1
P (a|b)
1
P (a|b)
P (a, b) log
X
1
1
+
P (a∗ , b) log
P (a|b)
P (a∗ |b)
B
11
La differenza vale:
H(A|B) − H(PE ) − PE log(q − 1) =
X
X
PE
PE
P (a, b) log
+
P (a∗ , b) log
(q − 1)P (a|b)
P (a∗ |b)
∗
B
B,A\{a }
Applichiamo ora la disuguaglianza:
ln x ≤ x − 1
ovvero (cambiando base):
log x
≤x−1
log e
da cui
log x ≤ (x − 1) log e
ad ogni termine della somma. Tralasciando il fattore log e (che non cambia il
risultato che otterremo) abbiamo:
H(A|B) − H(PE ) − PE log(q − 1) ≤
X
X
PE
PE
∗
≤
P (a, b)
−1 +
P (a , b)
−1
(q − 1)P (a|b)
P (a∗ |b)
∗
B
B,A\{a }
PE
=
q−1
X
p(b) − PE + PE
X
p(b) − PE
B
B,A\{a∗ }
X
X
PE
=
(q − 1)
p(b) + PE
p(b) − (PE + PE )
q−1
B
B
= PE + PE − (PE + PE ) = 0
Pertanto vale:
H(A|B) ≤ H(PE ) + PE log(q − 1)
che viene detta disuguaglianza di Fano.
L’uguaglianza vale quando ln x = x − 1, ovvero quando x = 1. Dato che abbiamo usato la disuguaglianza ln x ≤ x−1 in due posti diversi, si ha l’uguaglianza
quando valgono entrambe le seguenti condizioni:
1. P (a|b) =
PE
q−1
2. P (a∗ |b) = 1 − PE
∀ b, ∀ a 6= a∗
∀b
Tuttavia, la seconda condizione è inclusa nella prima (cioè la prima implica la
seconda). Infatti possiamo scrivere:
X
P (a|b) = 1
∀b
A
12
e quindi:
X
P (a|b) + P (a∗ |b) = 1
∀b
A\{a∗ }
Per la condizione 1, questa diventa:
PE X
1 + P (a∗ |b) = 1
q−1
∗
∀b
A\{a }
Essendo |A| = q, si ottiene:
PE
(q − 1) + P (a∗ |b) = 1
q−1
∀b
che è proprio la condizione 2.
4
L’inverso del teorema di Shannon
Mostriamo ora che la probabilità d’errore non può essere resa arbitrariamente
piccola se si supera la capacità del canale. In altre parole, non possiamo usare
M = 2n(C+ε)
con ε > 0
messaggi validi equiprobabili, soddisfacendo i requisiti del teorema di Shannon.
Infatti, supponiamo per assurdo di poterlo fare. Allora la variazione di entropia deve essere minore o uguale della capacità dell’n–esima estensione del
CBS:
H(A) − H(A|B) ≤ nC
(4)
dato che la capacità dell’n–esima estensione del CBS è, per definizione, il valore
massimo di tale variazione. Dato che la probabilità di scegliere ogni messaggio
1
valido è M
, abbiamo:
X 1
log M
M
= log M = n(C + ε)
H(A) =
Pertanto, dalla (4) abbiamo:
n(C + ε) − nC = nε ≤ H(A|B)
e quindi, dalla disuguaglianza di Fano:
nε ≤ H(A|B) ≤ H(PE ) + PE log(M − 1)
Ricordiamo ora che vale H(PE ) ≤ 1. Inoltre M − 1 < M , da cui log(M − 1) <
log M . Otteniamo quindi:
nε ≤ 1 + PE · n(C + ε)
13
da cui:
PE ≥
nε − 1
ε − 1/n
=
n(C + ε)
C+ε
n→+∞
−→
ε
>0
C +ε
Possiamo concludere che, per n che tende all’infinito, PE non si avvicina
ε
a 0 ma si avvicina alla quantità C+ε
, che è positiva. Questo significa che la
probabilità d’errore non può essere resa arbitrariamente piccola se si supera la
capacità del canale.
Riferimenti bibliografici
[1] N. Abramson. Information Theory and Coding. McGraw-Hill, 1963.
[2] R. H. Hamming. Coding and Information Theory. Second Edition. Prentice
Hall, Englewood Cliffs, 1986.
14