Il teorema della capacità di Shannon nella teoria dell'informazione e le sue applicazioni

Indice

1 Elementi fondamentali 7

1.1 Entropia . . . 7

1.2 Entropia congiunta . . . 9

1.2.1 Entropia congiunta di variabili aleatorie indipendenti . 9 1.2.2 Entropia di una semplice sorgente di informazione . . . 10

1.3 Entropia condizionata . . . 10

1.4 Informazione mutua . . . 12

1.4.1 Informazione mutua condizionata . . . 13

1.4.2 Entropia ed entropia condizionata . . . 13

1.4.3 Entropia ed entropia congiunta . . . 13

1.5 Teorema dell'elaborazione dei dati . . . 14

1.6 Disuguaglianza di Fano . . . 14

2 Capacità di canale 17 2.1 Canale discreto senza memoria . . . 17

2.1.1 Il canale binario simmetrico (BSC) . . . 18

2.1.2 Il canale binario con cancellazione (BEC) . . . 19

2.2 Capacità di canale . . . 19

2.2.1 Capacità del canale BSC . . . 20

2.2.2 Capacità del BEC . . . 21

3 Proprietà di equipartizione asintotica congiunta 25 3.1 Legge debole dei grandi numeri . . . 25

3.2 AEP congiunta . . . 26

3.2.1 Teorema AEP congiunta . . . 26

3.2.2 Sequenze tipiche . . . 27

3.2.3 Proprietà delle sequenze tipiche . . . 28

3.2.4 Sequenze tipiche condizionate . . . 30

3.2.5 Sequenze particolari . . . 30

4 Teorema della capacità di Shannon 35

4.1 Anticipazione del teorema di Shannon . . . 35

4.2 Schema di riferimento . . . 36

4.3 Teorema di Shannon . . . 37

4.4 Inverso debole . . . 40

5 Canale gaussiano 43 5.1 Capacità del canale AWGN . . . 43

5.1.1 Informazione mutua nel caso di canale continuo . . . . 44

5.1.2 Capacità del canale AWGN . . . 45

5.2 Teorema della capacità nel caso di canale AWGN . . . 47

5.3 Applicazione: segnali a banda limitata . . . 48

5.4 Applicazione: curva limite della capacità . . . 48

6 Applicazioni 51 6.1 I codici lineari a blocco . . . 51

6.1.1 Denizioni . . . 51

6.1.2 Validità dei codici lineari a blocco . . . 52

6.1.3 Codici LDPC . . . 54

6.1.4 Osservazione . . . 54

6.2 Teorema della capacità per canali ad accesso multiplo . . . 54

6.2.1 Schema di riferimento . . . 54

6.2.2 Teorema . . . 55

6.2.3 Concetto di regione di capacità . . . 57

6.3 Canale ad accesso multiplo gaussiano . . . 59

6.4 Conclusioni . . . 60 A Analisi delle caratteristiche delle sequenze tipiche 65 B Caratteristica di una matrice di parità casuale 67

Introduzione

Lo scopo di questo lavoro è presentare il teorema della capacità di Shan-non evidenziandone la sua importanza nella teoria della comunicazione e in particolare nelle telecomunicazioni. Il teorema della capacità è uno dei risultati più importanti della teoria dell'informazione.

La teoria dell'informazione nasce nel 1948 per opera di Claude Elwood Shannon che pubblicò i risultati delle sue ricerche in vari articoli su The Bell Technical System Journal, il primo e più famoso dei quali si intitola-va A mathematical theory of communication. Shannon dimostrò, tramite il teorema della codica di canale, che, per ogni sistema di comunicazione esiste una quantità, detta capacità, che ssa l'estremo superiore del tasso di informazione trasmissibile sul canale con probabilità di errore piccola a piacere.

Prima di questa data si riteneva che per avere una probabilità di errore sempre più piccola fosse inevitabile trasmettere ad un tasso di informazione sempre più basso.

Claude E. Shannon dimostrò che questo era possibile tramite l'uso di codici ma non fornì praticamente nessuna soluzione costruttiva.

Negli ultimi sessanta anni le ricerche teoriche nel campo della teoria del-l'informazione e, in particolare, riguardo al teorema della capacità si sono sviluppate in diverse direzioni.

Da una parte, con la teoria dei codici, si è cercato di trovare codici che permettessero di raggiungere le prestazioni garantite da Shannon; dall'altra si è sviluppato ed esteso il concetto di capacità a vari tipi di canali.

Per quanto riguarda il primo punto, con i codici LDPC e i Turbocodici, si sono nalmente raggiunti i limiti individuati da Shannon nello sfruttamento del canale. Gli LDPC (l'acronimo signica Low Density Parity Check ) sono stati scoperti da Robert G. Gallagher negli anni sessanta ma per molti decenni sono stati dimenticati per la complessità della decodica.

Il problema è stato risolto nel 1992 da Berroux e Glavieux con l'intro-duzione dei Turbocodici e della tecnica di decodica iterativa. Quest'ultima

sfrutta il concetto di Message Passing che può essere applicato anche ai codici LDPC.

Riguardo al secondo punto, il teorema della capacità è stato esteso anche ad altri canali come quello ad accesso multiplo. Anche in questo caso i risultati teorici sono di alcuni decenni fa ma la realizzazione è relativamente recente: il sistema CDMA è stato proposto per la prima volta alla ne degli anni ottanta.

Vediamo brevemente il percorso del lavoro. Nel primo e secondo capitolo si introdurranno le grandezze fondamentali della teoria dell'informazione e la caratterizzazione del canale. Nel terzo si introdurranno i concetti di sequenze congiuntamente tipiche, fondamento di una delle dimostrazioni possibili del teorema sulla codica di canale. Questa verrà svolta nel quarto capitolo. Nel capitolo quinto si estenderà il teorema della capacità al caso di canale AWGN per arrivare a presentare la curva limite della capacità di un tale canale. Inne nel capitolo sesto passeremo alle due applicazioni sopra menzionate: i codici a parità e il canale ad accesso multiplo.

Nelle due appendici, si trovano programmi che riguardano la proprietà di equipartizione asintotica e la caratteristica di una matrice di parità casuale. Resta inne da citare alcune applicazioni: i codici LDPC sono attual-mente presenti nello standard della televisione digitale satellitare di seconda generazione (DVB-S2) e nello standard IEEE802.16 che riguarda le Wireless-MAN; i Turbocodici e la tecnica CDMA sono utilizzati nel sistema UMTS, i primi nella trasmisione dati, la seconda nella parte radio (Node-B).

Il lavoro è basato principalmente su [2] e su [7]. La lettura di [8] è, anche dopo sessanta anni, molto interessante.

Capitolo 1

Elementi fondamentali

Nella teoria dell'informazione il teorema della capacità di Shannon per-mette di raggiungere risultati notevoli anche al di fuori dei sistemi di comu-nicazione.

In tutti i casi si parte da alcune quantità di base, non tutte presenti in questo lavoro; alla base si pone l'entropia di una variabile aleatoria, da cui derivano l'entropia congiunta, l'entropia condizionale e l'informazione mutua. L'informazione è legata ad un esperimento casuale e corrisponde alla rimozione dell'incertezza data dalla sua realizzazione.

Una sorgente (discreta), in un sistema di comunicazione, non è altro che un esperimento casuale che può essere modellato in maniera più o meno ranata; la misura dell'incertezza della sorgente è l'entropia della sorgente. L'entropia è una estensione del concetto di probabilità: come la probabi-lità è la misura dell'incertezza di un evento, così l'entropia è una misura dell'incertezza dell'esperimento casuale.

In questo capitolo deniremo prima l'entropia di una variabile aleato-ria e successivamente l'entropia congiunta, quella condizionata, l'informa-zione mutua e alcune relazioni utili; per nire daremo gli enunciati di due importanti teoremi che ritroveremo nella dimostrazione del teorema della capacità.

1.1 Entropia

Data una variabile aleatoria X denita su un alfabeto X con funzione di distribuzione pX(x), si denisce entropia (se esiste) la quantità

H(X) = −X

x∈X

La base del logaritmo è sottinteso essere la base due, in questo modo l'unità di misura dell'entropia è il bit (di informazione).

Se si considera la particolare trasformazione di variabile aleatoria g(x) = pX(x)si può scrivere in maniera più compatta

H(X) = −E[log pX(x)].

Questo modo di interpretare l'entropia sarà utile nel teorema sulla proprietà di equipartizione asintotica congiunta che vedremo nel prossimo capitolo.

L'entropia è una quantità sempre non negativa per costruzione e ammette massimo quando la variabile aleatoria ha distribuzione uniforme. Quindi:

Hmax(X) = log |X |,

ricordando che |X | è la cardinalità di X . Per dimostrare questa proprietà utilizziamo la disuguaglianza di Gibbs.

Teorema 1.1 (Disuguaglianza di Gibbs). Dati i numeri positivi p1,...,pn e

q1,...,qn tali che Pn_i=1pi = 1 e Pn_i=1qi = 1 allora: n X i=1 pilog pi ≥ n X i=1 pilog qi.

L'uguaglianza vale se e solo se pi = qi per ogni i.

Possiamo adesso calcolare il massimo dell'entropia.

Teorema 1.2 (Massimo dell'entropia di una variabile aleatoria). Il massimo dell'entropia di una variabile aleatoria si ha con la distribuzione uniforme. Dimostrazione. Ponendo qi = 1/N per ogni i nella disuguaglianza di Gibbs,

si ottiene − n X i=1 pX(xi) log pX(xi) ≤ − n X i=1 pX(xi) log 1/N = log N,

con l'uguaglianza che vale se e solo se pX(xi) = 1/N per ogni i.

Esempio 1.1. Calcoliamo un'entropia notevole: l'entropia di una variabile aleatoria binaria. Se X = {0, 1} e pX(0) = p allora

H(X) = −p log p − (1 − p) log(1 − p).

La gura 1.1 illustra l'andamento dell'entropia in funzione di p.

Il graco dimostra che l'entropia è una misura dell'incertezza di un espe-rimento casuale. Se p = 1/2 l'incertezza è massima mentre è nulla se e solo se esiste un evento certo. Inoltre, come si vede, l'entropia è non negativa.

Figura 1.1: Entropia di una variabile binaria

1.2 Entropia congiunta

Date due variabili aleatorie X ed Y denite su due alfabeti X e Y con funzione di distribuzione congiunta pXY(x, y), si denisce (se esiste) entropia

congiunta la quantità H(X, Y ) = −X x∈X X y∈Y pXY(x, y) log pXY(x, y).

L'entropia congiunta è una generalizzazione dell'entropia di una variabile aleatoria a più variabili aleatorie ed è, anche questa, per costruzione non negativa. La denizione si può estendere agevolmente a più di due variabili aleatorie 1 _{e quindi} H(X1, ..., Xn) = − X x∈X1 ... X x∈Xn pX1...Xn(x1, ..., xn) log pX1...Xn(x1, ..., xn).

Anche in questo caso si può scrivere in forma più compatta come H(X1, ..., Xn) = −E[log pX1...Xn(x1, ..., xn)].

Dato un esperimento casuale descrivibile con più variabili aleatorie, l'entro-pia congiunta rappresenta l'incertezza dell'esperimento casuale descritto da queste.

Esaminiamo la relazione tra entropia congiunta ed entropia delle singole variabili aleatorie.

1.2.1 Entropia congiunta di variabili aleatorie

indipen-denti

Se le variabili aleatorie sono indipendenti (pXY(x, y) = pX(x)pY(y)) allora

H(X, Y ) = H(X) + H(Y ).

Nel caso di n variabili aleatorie indipendenti si ha H(X1, ..., Xn) = n X i=1 H(Xi).

1.2.2 Entropia di una semplice sorgente di informazione

La sorgente che consideriamo emette n simboli indipendenti e ad ogni simbolo si associa una variabile aleatoria. Supponiamo che le variabili alea-torie che rappresentano ogni simbolo abbiano la stessa distribuzione. L'in-formazione emessa dalla sorgente di inL'in-formazione è l'entropia congiunta delle variabili associate agli n simboli e quindi

H(X1, ..., Xn) = n

X

i=1

H(Xi) = nH(X),

dove Xi = X per ogni i.

Questa può essere una misura, approssimata, dell'incertezza di una qual-siasi sorgente.

1.3 Entropia condizionata

Date due variabili aleatorie denite sugli alfabeti X e Y con funzione di distribuzione congiunta pXY(x, y), l'entropia di Y condizionata a X = x è

denita (se esiste) come

H(Y |X = x) = −X

y∈Y

pY |X(y|x) log pY |X(y|x).

L'entropia condizionata è la media pesata di questa quantità per ogni x, quindi

H(Y |X) = −X

y∈Y

X

x∈X

pY |X(y|x)pX(x) log pY |X(y|x).

Oppure, più sinteticamente,

H(Y |X) = −E[log pY |X(y|x)].

L'entropia condizionata è legata all'entropia congiunta ed alla entropia semplice dalla relazione

H(X, Y ) = −X

x∈X

X

y∈Y

= −X

x∈X

X

y∈Y

pXY(x, y) log[pX|Y(x|y)pY(y)]

= −X

x∈X

X

y∈Y

pXY(x, y) log pX|Y(x|y) −

X x∈X X y∈Y pXY(x, y) log pY(y) = −X x∈X X y∈Y

pXY(x, y) log pX|Y(x|y) −

X

y∈Y

pY(y) log pY(y)

= H(X|Y ) + H(Y ).

Nel caso in cui le variabili aleatorie sono indipendenti, H(X|Y ) = H(X) e si trova il risultato già noto.

Teorema 1.3 (Sviluppo dell'entropia condizionata). Consideriamo n varia-bili aleatorie X1,...,Xncon distribuzione di probabilità congiunta pX1...Xn(x1, ..., xn).

Allora H(X1, ..., Xn) = n X i=1 H(Xi|Xi−1, ..., X1).

Dimostrazione. La prova si basa sulla ripetuta applicazione dell'espansione dell'entropia congiunta di due variabili. Quindi:

H(X1, X2) = H(X1) + H(X2|X1), H(X1, X2, X3) = H(X1) + H(X2, X3|X1) = H(X1) + H(X2|X1) + H(X3|X2, X1), H(X1, ..., Xn) = H(X1) + H(X2|X1) + ... + H(Xn|Xn−1, ..., X1) = n X i=1 H(Xi|Xi−1, ..., X1).

1.4 Informazione mutua

L'informazione mutua si ricava manipolando la relazione H(X) + H(Y |X) = H(Y ) + H(X|Y ). Si ottiene con un semplice passaggio

H(X) − H(X|Y ) = H(Y ) − H(Y |X) = I(X; Y ) = I(Y ; X).

La quantità I(X; Y ) è l'informazione mutua ed è simmetrica. L'informazione mutua rappresenta l'informazione che una variabile aleatoria fornisce rispetto ad un altra variabile aleatoria. In questo senso è una misura della correlazione tra due variabili aleatorie ed infatti, nel caso di indipendenza, è nulla. Prima di esplicitare l'informazione mutua esponiamo le tre classiche espressioni di questa quantità:

I(X; Y ) = H(Y ) − H(Y |X),

I(X; Y ) = H(X) − H(X|Y ),

I(X; Y ) = H(X) + H(Y ) − H(X, Y ).

Esplicitando la prima delle espressioni (viste sopra tralasciando da ora in poi gli estremi della sommatoria),

I(X; Y ) = H(X) − H(X|Y )

= −XpX(x) log pX(x) +

X X

pXY(x, y) log pX|Y(x|y)

= −X XpXY(x, y) log pX(x) +

X X

pXY(x, y) log pX|Y(x|y)

=X XpXY(x, y) log pX|Y(x|y) pX(x) =X XpXY(x, y) log pXY(x, y) pX(x)pY(y) .

1.4.1 Informazione mutua condizionata

Al contrario dell'entropia, non è ovvio generalizzare l'informazione mutua; l'espressione I(X; Y ; Z) è sicamente priva di senso anche se si può analizzare e trovare delle relazioni con le entropie presentate. Esiste una informazione mutua, quella condizionata, che si può generalizzare e che utilizzeremo più avanti. La sua forma è

I(X; Y |Z) = H(X|Z) − H(X|Z, Y )

=X X XpXY |Z(x, y|z)log

pXY |Z(x, y|z)

pX|Z(x|z)pY |Z(y|z)

.

L'informazione mutua condizionata è nulla se e solo se le variabili aleatorie X ed Y sono condizionalmente indipendenti rispetto a Z.

1.4.2 Entropia ed entropia condizionata

Si può dimostrare che l'informazione mutua è sempre non negativa e quindi

H(X) ≥ H(X|Y ).

Se e solo se le variabili aleatorie sono indipendenti, H(X|Y ) = H(X). Sintetizzando, si può dire che il condizionamento riduce sempre l'incer-tezza riguardante una variabile aleatoria.

1.4.3 Entropia ed entropia congiunta

Dalla osservazione precedente e da

H(X, Y ) = H(X|Y ) + H(Y ) = H(Y |X) + H(X) deriva

H(X, Y ) ≤ H(X) + H(Y ).

L'uguaglianza vale se e solo se le variabili aleatorie X e Y sono indipendenti. Inoltre, poichè H(X|Y ), H(Y |X) ≥ 0, allora

H(X, Y ) ≥ H(Y ), H(X).

L'uguaglianza vale se e solo se le variabili aleatorie X e Y sono in corrispon-denza biunivoca.

1.5 Teorema dell'elaborazione dei dati

Consideriamo tre variabili aleatorie X,Y e Z che formano una catena di Markov. Questo signica che

pXY Z(x, y, z) = pX(x)pY |X(y|x)pZ|Y(z|y),

e, in maniera equivalente, che

pXY |Z(x, y|z) = pX|Y(x|y)pZ|Y(z|y),

poichè pXZ|Y(x, z|y) = pXY Z(x, y, z) pY(y) = pXY(x, y)pZ|Y(z, y) pY(y)

= pX|Y(x|y)pZ|Y(z|y).

Allora

I(X; Z) ≤ I(X; Y ) e

I(X; Z) ≤ I(Y ; Z).

Se consideriamo un sistema di comunicazione composto da due canali in ca-scata dove X è la variabile aleatoria che rappresenta l'ingresso, Y è quella che rappresenta l'ingresso al secondo canale e Z quella che rappresenta l'uscita, il teorema della elaborazione dei dati aerma che l'informazione mutua non può aumentare in seguito ad una elaborazione.

1.6 Disuguaglianza di Fano

Esistono diverse forme della disuguaglianza di Fano. La forma che presen-tiamo aerma che, date due qualsiasi variabili aleatorie, denita la quantità

p = Pr(X 6= Y ), allora

H(p) + p log |X | ≥ H(X|Y ),

dove H(p) è, sinteticamente, l'entropia di una variabile aleatoria binaria di parametro p. Si osservi che, se p = 0, l'equivocazione H(X|Y ) è, corretta-mente, nulla.

Maggiorando H(p) con 1, si ottiene

p ≥ H(X|Y ) − 1 log |X |

che evidenzia il legame tra probabilità di errore p ed equivocazione H(X|Y ). Se X è la variabile aleatoria che rappresenta l'ingresso al canale ed Y quella che rappresenta l'uscita, la disuguaglianza di Fano aerma che la pro-babilità di errore nel ricostruire l'ingresso, osservando l'uscita, è legata alla equivocazione H(X|Y ).

Capitolo 2

Capacità di canale

Nella teoria dell'informazione un sistema di comunicazione discreto può essere schematizzato nel seguente modo (gura 2.1):

Figura 2.1: Schema di un sistema di comunicazione

Il canale, inteso in senso lato, comprende modulatore, demodulatore e canale sico. Quest'ultimo aggiunge al segnale rumore sico ed interferenza. Vedremo successivamente il signicato dei blocchi codicatore e decodica-tore.

Si può dare del canale una descrizione complessa; ci limiteremo in questo lavoro al canale discreto senza memoria.

Il capitolo è diviso in due parti: nella prima caratterizzeremo il cana-le discreto senza memoria, nella seconda deniremo la capacità di canacana-le. Analizzeremo due esempi di canale: il canale binario simmetrico (BSC) ed il canale binario con cancellazione (BEC).

2.1 Canale discreto senza memoria

Per caratterizzare un canale abbiamo bisogno della funzione di distribu-zione congiunta delle sequenza in uscita al canale condizionata alle sequenze

in ingresso (pY1...Yn|X1...Xn(y1, ..., yn|x1, ..., xn)). L'assenza di memoria implica che pY1...Yn|X1...Xn(y1, ..., yn|x1, ..., xn) = n Y i=1 pYi|Xi(yi|xi).

Il canale senza memoria è denito dall'alfabeto nito dei simboli di ingresso X, dall'alfabeto nito dei simboli di uscita Y e dalla matrice di transizione [P ] del canale i cui elementi sono pij = pY |X(yi, xj). Date le probabilità

dei simboli di sorgente pX(x) sotto forma di vettore, si possono ricavare

le probabilità dei simboli di uscita dal canale, sempre in forma di vettore, tramite l'espressione

pY(y) = [P ]pX(x).

Si noti che in generale l'alfabeto di ingresso può essere diverso dall'alfabeto di uscita.

Nel caso binario il modello di canale più comune è il BSC, un altro mo-dello è il BEC. Esamineremo entrambi come esempi di canali discreti senza memoria.

2.1.1 Il canale binario simmetrico (BSC)

Lo schema del canale binario simmetrico è dato in gura 2.2:

Figura 2.2: Canale binario simmetrico

L'alfabeto di ingresso coincide con quello di uscita ed è dato da X = Y = {0, 1}. La matrice di transizione assume la forma

[P ] = 1 − p p p 1 − p

 .

Figura 2.3: Canale binario con cancellazione

2.1.2 Il canale binario con cancellazione (BEC)

Anche questo è un canale binario perchè tale è l'ingresso. Lo schema è il seguente (gura 2.3):

L'alfabeto di ingresso è X = {0, 1} mentre quello di uscita è Y = {0, e, 1}. La matrice di transizione è [P ] =   1 − α 0 α α 0 1 − α  .

2.2 Capacità di canale

Poichè l'informazione mutua quantica l'informazione che la variabile aleatoria Y (l'uscita del canale) fornisce rispetto alla variabile aleatoria X (l'ingresso di questo), è interessante valutare se questa quantità ammette massimo ed il valore che questo assume negli esempi visti sopra. Per far questo rielaboriamo l'espressione dell'informazione mutua tramite lo sviluppo

I(X; Y ) =X XpXY(x, y) log pXY(x, y) pX(x)pY(y) =X XpY |X(y|x)pX(x) log pY |X(y|x) pY(y) , dove pY(y) = X x pXY(x, y) = X x pY |X(y|x)pX(x).

Come si vede l'informazione mutua dipende sia dal canale sia dalla distribu-zione di probabilità dei simboli di sorgente. Si può dimostrare che l'informa-zione mutua ammette massimo perchè è una funl'informa-zione concava in pX(x)ma la

dimostrazione non è interessante per lo scopo di questo lavoro. Quello che è importante notare è che, per sfruttare appieno un sistema di comunicazione è necessario adattare la sorgente al canale. La distribuzione di probabilità dei simboli in ingresso al canale deve essere quella che massimizza l'informazione mutua.

Il massimo dell'informazione mutua è C = max

pX(x)

I(X; Y ),

ed è chiamata capacità. Calcoliamo adesso la capacità del canale binario simmetrico e del canale binario con cancellazione.

2.2.1 Capacità del canale BSC

Nel calcolo della capacità di un sistema di comunicazione si usa di solito, per comodità di calcolo, la forma dell'informazione mutua

I(X; Y ) = H(Y ) − H(Y |X).

Infatti i termini pY |X(y|x) sono subito a disposizione. Si può quindi

svilup-pare l'entropia condizionata scrivendo

H(Y |X) =XpX(x)H(Y |X = x),

e si osserva che H(Y |X = 0) è uguale a H(Y |X = 1) per la simmetria del canale ed inoltre sono entrambi pari all'entropia della variabile binaria di parametro p = pY |X(0|1) = pY |X(1|0). Chiamata H(p) questa quantità si

ottiene

H(Y |X) =XpX(x)H(p) = H(p),

e, per concludere,

I(X; Y ) = H(Y ) − H(p).

L'adattamento al canale si raggiunge per simboli di sorgente equiprobabili, per cui H(Y ) = 1. Concludendo

CBSC = 1 − H(p).

La gura 2.4 illustra l'andamento della capacità in funzione del parametro p. Il graco mostra che, correttamente, il canale ha una capacità nulla se p = 1/2 mentre ha capacità massima pari ad un bit se p = 0 o p = 1. Anche l'ultimo caso è corretto perchè se il canale commuta sempre i simboli di ingresso è suciente invertire la regola di decisione per ricevere sempre il simbolo corretto.

Figura 2.4: Capacità del BSC

2.2.2 Capacità del BEC

In questo caso il calcolo della capacità è più complesso ma si parte comun-que sviluppando la forma dell'informazione mutua vista nel BSC. Eseguiamo il seguente sviluppo, dove la variabile aleatoria binaria E assume valore 0 se Y = e ed 1 altrimenti:

I(X; Y ) = H(Y ) − H(Y |X)

= H(Y, E) − H(Y |X)

= H(E) + H(Y |E) − H(Y |X).

L'informazione di H(Y ) è la stessa di H(Y, E) poichè la funzione massa di probabilità congiunta assume i valori tabellati in gura 2.5.

Infatti, con alcuni passaggi 1_,

H(Y, E) = −X XpY E(y, e) log pY E(y, e)

= −X

y∈Y

pY E(y, 1) log pY E(y, 1) −

X

y∈Y

pY E(y, 0) log pY E(y, 0)

= − X

y=0,1

pY(y) log pY(y) − pY(e) log pY(e)

= −X

y∈Y

pY(y) log pY(y)

= H(Y ).

Figura 2.5: pY E(y, e)

Ricordando la gura 2.2 si ricava che H(E) è l'entropia di una variabile aleatoria binaria di parametro α. Passiamo ad H(Y |E) e poniamo pX(0) =

p0; abbiamo

pE(0) = αp0+ α(1 − p0) = α

e ricordando che

pY |E(y|e) = pY E(y, e)/pE(e),

si hanno nella tabella di gura 2.6 i valori della distribuzione condizionata. Per nire servono i valori di pY(y):

pY(y) =   pY(0) pY(e) pY(1)  = [P ]pX(x) =   1 − α 0 α α 0 1 − α    p0 1 − p0  =   (1 − α)p0 α (1 − α)(1 − p0)  . Possiamo sviluppare adesso l'entropia di Y condizionata ad E:

H(Y |E) = pE(0)H(Y |E = 0) + pE(1)H(Y |E = 1)

Figura 2.6: pY |E(y|e) = −pY(e) log pY(e) α − pY(0) log pY(0) 1 − α − pY(1) log pY(1) 1 − α = (1 − α)H(p0),

per i valori di pY(y) calcolati sopra e la denizione di entropia.

Riguardo a H(Y |X) ricordiamo la matrice di transizione del canale con

cancellazione: _  1 − α 0 α α 0 1 − α  . Senza svolgere i calcoli si può concludere che:

H(Y |X) = H(α).

Abbiamo adesso tutti gli elementi per calcolare l'informazione mutua e quindi la capacità.

I(X; Y ) = H(Y ) − H(Y |X) = (1 − α)H(p0) + H(α) − H(α) = (1 − α)H(p0).

Anche in questo caso, data la simmetria del canale, l'adattamento si ottiene per simboli di sorgente equiprobabili (questo implica H(p0) = 1). La capacità

del canale con cancellazione è

Il signicato del risultato è intuitivo: poichè una frazione α di bit può essere persa a causa del canale, è possibile ricostruire al massimo una frazione 1−α di bit.

La capacità è la grandezza fondamentale di un sistema di comunicazione. Il teorema di Shannon sulla codica di canale aerma che, per ogni tasso di codica inferiore alla capacità, si può trovare una sequenza di codici con probabilità massima di errore tendente a zero per n (numero di simboli di codice) tendente ad innito. In altre parole, se rimaniamo sotto la capacità, possiamo costruire codici che garantiscono una probabilità di errore piccola a piacere.

Capitolo 3

Proprietà di equipartizione

asintotica congiunta

La proprietà di equipartizione asintotica congiunta (AEP congiunta) ca-ratterizza il comportamento di una lunga sequenza di un vettore di variabili aleatorie. In questo capitolo forniremo le proprietà generali per poi deriva-re alcuni casi notevoli per questo lavoro. Sfruttederiva-remo queste proprietà, in particolare, nella dimostrazione del teorema sulla capacità di Shannon che daremo nel prossimo capitolo. Dopo aver denito la proprietà di equiparti-zione asintotica, ne dimostreremo le proprietà fondamentali; sfrutteremo un caso particolare per chiarire l'ultima e più importante proprietà. Per primo riepiloghiamo la legge debole dei grandi numeri.

3.1 Legge debole dei grandi numeri

Data una sequenza di n variabili aleatorie Xi i.i.d. con valor medio µ e

varianza σ2_{, si dimostra la seguente tesi:}

lim n→+∞Pr (     1 n n X i=1 Xi− µ      <  ) = 1.

La media di una sequenza di n variabili aleatorie Xi indipendenti ed

identi-camente distribuite (i.i.d.) tende in probabilità, per n → ∞, al valor medio di Xi. Deniamo Zn = 1 n n X i=1 Xi. Si osservi che E[Zn] = µ,

e che

σ2_Z

n =

σ2

n . Per la disuguaglianza di Chebychev,

Pr{|Zn− µ| > } ≤ σ_Z2_n  , ammessa l'esistenza di σ2 Zn. Quindi, sostituendo Zn e σ 2 Zn, si ottiene: Pr (     1 n n X i=1 Xi− µ      >  ) ≤ σ 2 n

e, facendo il limite di entrambi i membri per n → ∞, si ottiene la tesi.

3.2 AEP congiunta

Alcune denizioni:

• (X(1)_{, ..., X}k_{) è un vettore di k variabili aleatorie con distribuzione}

congiunta pX(1)_...X(k)(x(1), ..., x(k));

• X(1)_{× ... × X}(k) _{è l'insieme delle realizzazioni di (X}(1)_{, ..., X}(k)_);

• (x(1)_{, ..., x}(k)_{) è un elemento di X}(1)_{× ... × X}(k)_.

• S è un sottoinsieme ordinato di (X(1)_{, ..., X}(k)₎;

• Sn _{è l'insieme delle realizzazioni s}n _{lunghe nk date da S}n_{, ripetizione}

indipendente di S.

Come vedremo, nel caso k = 1, le denizioni precedenti si riducono alla denizione di sequenze lunghe n di variabili aleatorie indipendenti. Tuttavia per questo lavoro interessano anche i casi k = 2 e k = 3.

3.2.1 Teorema AEP congiunta

Premettiamo che Pr{Sn= sn} = n Y i=1 Pr{Si = si},

Verichiamo che, per ogni sottoinsieme S ⊆ (X(1)_{, ..., X}(k)_), lim n→+∞Pr     −1 nlog pSn(S n_{) − H(S)}     <   = 1.

La dimostrazione procede sfruttando l'indipendenza delle ripetizioni e la legge debole dei grandi numeri. Deniamo

Zn= −

1

nlog pSn(S

n_),

che è la trasformazione di variabili aleatorie in cui la funzione di cambiamen-to di variabili è la funzione di distribuzione congiunta della ripetizione del vettore delle variabili aleatorie (X(1)_{, ..., X}(k)_).

Poichè le n ripetizioni del vettore di variabili aleatorie (X(1)_{, ..., X}(k)₎sono

indipendenti, allora Zn = − 1 nlog pSn(S n₎ = −1 n log n Y i=1 pSi(Si) = −1 n n X i=1 log pSi(Si) = 1 n n X i=1 log 1 pSi(Si) . La variabile aleatoria Zn è la media di log_p 1

Si(Si) e per denizione E  log 1 pSi(Si)  = E  log 1 pS(S)  = H(S).

Per n → ∞ vale la legge debole dei grandi numeri e la media coincide, in probabilità, con il valor medio di log 1

p_Si(Si). La tesi deriva di conseguenza.

3.2.2 Sequenze tipiche

L'insieme delle n-sequenze -tipiche A(n)

 è composto dagli elementi da

tutte le realizzazioni dei 2k _{sottoinsiemi S tali che}

2−n(H(S)+) ≤ pSn(sn) ≤ 2−n(H(S)−).

Denotiamo inne con A(n)

 (S) la restrizione di A(n) ad un sottoinsieme S ⊂

(X(1)...X(k)).

Caso k = 1

Nel caso k = 1, S = (X(1)_{)e quindi la ripetizione della variabile aleatoria}

X(1) riduce il problema a quello di una sequenza di variabili aleatorie i.i.d.. Le realizzazioni che cerchiamo devono essere tali che

2−n(H(S)+) ≤ pSn(sn) ≤ 2−n(H(S)−).

Caso k = 2

Nel caso k = 2, S = (X(1)_{, X}(2)_{), in questo caso le sequenze -tipiche}

devono vericare che

2−n(H(X(1))+)≤ p_X(1) 1 ...X (1) n (x (1) 1 , ..., x (1) n ) ≤ 2 −n(H(X(1)_)−) ; 2−n(H(X(2))+)≤ p_X(2) 1 ...X (2) n (x (2) 1 , ..., x (2) n ) ≤ 2 −n(H(X(2)_)−) ; 2−n(H(S)+) ≤ pSn(sn) ≤ 2−n(H(S)−).

Nelle condizioni precedenti pX(1)(x(1))e p_X(2)(x(2))sono le distribuzioni

mar-ginali.

3.2.3 Proprietà delle sequenze tipiche

Per ogni  > 0 esiste un ¯n tale che per n > ¯n l'insieme delle sequenze tipiche gode delle seguenti due proprietà:

• Pr(A(n) (S)) > 1 − ;

• |A(n) (S)| > (1 − )2n(H(S)−);

• |A(n) (S)| ≤ 2n(H(S)+).

Inne poniamo che S1, S2 ⊆ (X(1)...X(k)) 1. Se (s1, s2) ∈ A (n)

 (S1, S2), allora

• pS1|S2(s1|s2) ≤ 2

n(H(S1|S2)+).

La prima proprietà deriva dal teorema AEP applicato ad S ⊆ (X(1)_...X(k)₎

e ai suoi sottoinsiemi.

La seconda proprietà deriva dalla prima, infatti

1_{Non è necessario che S}

1 ed S2 siano disgiunti poichè vale la relazione H(Si, Sj|Sj) =

1 −  < Pr(A(n)_ (S)) ≤ X sn_∈A(n)  (S) 2−n(H(S)−) = |A(n)_ (S)|2−n(H(S)−). Quindi |A(n)_ (S)| > (1 − )2n(H(S)−).

Passiamo alla terza proprietà eseguendo il seguente sviluppo,

1 = X sn_∈A(n)  (S) pSn(sn) ≥ X sn_∈A(n)  (S) pSn(sn) ≥ X sn_∈A(n)  (S) 2−n(H(S)+) = |A(n)_ (S)|2−n(H(S)+). Quindi |A(n)  (S)| ≤ 2 n(H(S)+)_.

Per quanto riguarda l'ultima proprietà, di cui non diamo una dimostrazione rigorosa ma approssimata, è suciente osservare che, per denizione, data una coppia di ripetizioni indipendenti (sn

1, sn2) ∈ A (n)  (S1, S2), allora psn 1(s n 1) ≈ 2 −n(H(S1)) e psn 1sn2(s n 1, sn2) ≈ 2 −n(H(S1,S2))_, quindi psn 1|sn2(s n 1|sn2) = psn 1sn2(s n 1, sn2) psn 1(s n 1) ≈ 2−n(H(S1|S2))_.

Caso k = 1

Nel caso di n sequenze di variabili aleatorie i.i.d. (S = (X(1)_{)) la}

pri-ma proprietà aerpri-ma che nell'insieme delle possibili realizzazioni, esiste un sottoinsieme di queste che ha probabilità quasi unitaria di vericarsi: le realizzazioni di questo sottoinsieme sono chiamate sequenze tipiche. Per la seconda e terza proprietà le sequenze tipiche sono approssimativamente equi-probabili con equi-probabilità 2−n(H(X(1)₎

e quindi il numero di sequenze tipiche è 2n(H(X(1)₎

.

In generale nell'insieme delle realizzazioni delle ripetizioni indipendenti Sn, esiste un sottoinsieme di sequenze di Sn, chiamate congiuntamente ti-piche, la cui probabilità di realizzarsi è praticamente unitaria. Il numero di queste sequenze è approssimativamente pari a 2nH(S) _{ed ogni sequenza tipica}

ha approssimativamente la stessa probabilità di vericarsi (≈ 2−nH(S)_).

3.2.4 Sequenze tipiche condizionate

Dati S1, S2 ⊆ (X(1)...X(k)) deniamo

A(n)_ (S1|s2),

l'insieme delle sn

1 sequenze congiuntamente tipiche con una sequenza sn2. Per

ogni  > 0 esiste un ¯n tale che, per n > ¯n, • Pr A(n) (S1|s2) > 1 − ; • |A(n) (S1|s2)| ≤ 2n(H(S1|S2)); • (1 − )2n(H(S1|S2)) ≤P sn 2∈S2npS n 2(s n 2)|A (n)  (S1|s2)|.

Omettiamo la dimostrazione perché si tratta di applicare pedissequamente le prime tre proprietà delle sequenze congiuntamente tipiche ad una distri-buzione di probabilità condizionata.

3.2.5 Sequenze particolari

Dati S1, S2, S3 ⊆ (X(1)...X(k)) deniamo ˆS1, ˆS2 e ˆS3 insiemi di variabili

aleatorie tali che

• le distribuzioni di probabilità di (Si, Sj) e di ( ˆSiSˆj) per i, j = 1, 2, 3 e

i 6= j sono uguali;

Enunciamo la probabilità che le sequenze ˆS1, ˆS2 e ˆS3 siano congiuntamente tipiche. Allora Pr{( ˆS1 n , ˆS2 n , ˆS3 n ) ∈ A(n)_ (S1, S2, S3)} ≥ (1 − )2−n(I(S1;S2|S3)+6) e Pr{( ˆS1 n , ˆS2 n , ˆS3 n ) ∈ A(n)_ (S1, S2, S3)} ≤ 2−n(I(S1;S2|S3)−6). Praticamente Pr{( ˆS1 n , ˆS2 n , ˆS3 n ) ∈ A(n)_ (S1, S2, S3)} ≈ 2−nI(S1;S2|S3)

Anche di queste due proprietà omettiamo la dimostrazione poiché si tratta di sviluppare la relazione Pr{( ˆS1 n , ˆS2 n , ˆS3 n ) ∈ A(n)_ (S1, S2, S3)} = X (sn 1,sn2,sn3)∈A (n)  (S1,S2,S3) pSn 1|S3n(s n 1|s n 3)pSn 2|S3n(s n 2|s n 3)psn 3(s n 3),

ricordando che, per i, j = 1, 2, 3 e i 6= j, p_Sˆ_in_ˆ Sj n(sn i, s n j) = pSn iSjn(s n i, s n j), e quindi p_Sˆ_in(sni) = pSn i(s n i).

A questo punto si utilizzano le maggiorazioni o minorazioni delle distribuzioni di probabilità, la cardinalità di A(n)

 (S1, S2, S3)e le proprietà dell'entropia che

sono state viste. Caso particolare

Consideriamo il caso in cui S ⊆ (X(1)_{, X}(2)_{) dove le variabili aleatorie}

X(1) e X(2) sono indipendenti. Allora, deniti S1 = (X(1)), S2 = (X(2)) e

S3 = (X(1), X(2)), costruiamo tre insiemi di variabili aleatorie ˆS1, ˆS2 e ˆS3 con

le caratteristiche dette. Per l'indipendenza vale che p_Sˆ₁n_Sˆ₂n(sn1, s n 2) = pSn 1S2n(s n 1, s n 2) = pSn 1(s n 1)pSn 2(s n 2), quindi pSn 1|S3n(s n 1|sn3)pSn 2|Sn3(s n 2|sn3)psn 3(s n 3) = pSn 3(s n 3)

= pSn 1Sn2(s n 1, s n 2) = pSn 1(s n 1)pSn 2(s n 2), per costruzione. Per concludere Pr{( ˆS1 n , ˆS2 n , ˆS3 n ) ∈ A(n)_ (S1, S2, S3)} ≈ 2−nI(S1;S2).

La proprietà di equipartizione asintotica congiunta, in questo caso, stabilisce che, nell'insieme delle sequenze di vettori (sn

1, sn2), sono presenti 2nH(S1,S2)

sequenze di vettori congiuntamente tipiche. Abbiamo visto nel primo ca-pitolo che H(S1, S2) ≤ H(S1) + H(S2) e questo implica che 2nH(S1,S2) ≤

2n(H(S1)+H(S2)): non tutte le coppie di sequenze di vettori tipiche sono

con-giuntamente tipiche. La probabilità che una qualsiasi coppia di sequenze di vettori sia congiuntamente tipica è 2−nI(S1;S2). Se consideriamo 2nI(S1;S2)

coppie di sequenze ne esiste, con alta probabilità, una congiuntamente tipica. Utilizzeremo il concetto di sequenze congiuntamente tipiche in varie di-mostrazioni che vedremo in seguito.

3.3 Osservazione

Per dimostrare che i concetti esposti permettono di interpretare alcuni aspetti della tecnologia attuale, consideriamo il caso k = 1 e supponiamo che la variabile aleatoria X(1) _{sia binaria e rappresenti la correttezza di un}

pacchetto di dati. Se dobbiamo trasmettere una grossa mole di dati in una rete di telecomunicazioni, per avere un minore tempo di trasmissione, la dividiamo in pacchetti.

Osserviamo che, data una probabilità di errore per bit pe ed un numero

di bit per pacchetto pari ad m,

Pr{pacchetto corretto} = (1 − pe)m,

quindi a parità di pe un pacchetto piccolo (cella) è più probabile che sia

corretto, come ovvio, rispetto ad un pacchetto lungo.

Inoltre, e no ad ora non abbiamo detto nulla a riguardo, la velocità della convergenza in probabilità delle sequenze tipiche è dell'ordine di 2√n_{, dove n}

è il numero di pacchetti.

Per questi due motivi conviene scegliere pacchetti piccoli e quindi nume-rosi a parità di quantità di dati che si vuole trasmettere.

Questo, accanto ad un minor tempo di trasmissione, può essere una spiegazione della tecnologia ATM.

Purtroppo nella trasmissione di dati può non interessare quello che ab-biamo detto ma la correttezza di tutti i pacchetti. L'insieme delle sequenze tipiche non include la sequenza più probabile che è quella che interessa.

Nella rete Internet si è risolto il problema alla radice: sfruttando la poten-za dei terminali odierni si utilizpoten-za uno strato di controllo (TCP) complesso spostando la questione dell'adabilità della trasmissione agli estremi della rete.

Il principio di ATM resta comunque valido poichè lo strato IP di Internet spesso lavora su ATM.

Capitolo 4

Teorema della capacità di

Shannon

Con i concetti introdotti nei precedenti capitoli possiamo arontare la dimostrazione del teorema di Shannon sulla codica di canale. Il capitolo è diviso in quattro parti: nella prima parte daremo una anticipazione del teorema, nella seconda deniremo lo schema e i termini di riferimento, nella terza e nella quarta daremo una dimostrazione del teorema, occupandoci, rispettivamente, dell'implicazione diretta ed inversa. Per quanto riguarda quest'ultima forniremo solo una dimostrazione debole (inverso debole).

Vericheremo che la capacità di canale è il logaritmo del numero mas-simo di sequenze distinguibili che si possono trasmettere con il canale a disposizione.

4.1 Anticipazione del teorema di Shannon

Un canale rumoroso non permette che la comunicazione sia adabile. Tuttavia utilizzando ripetutamente il canale è possibile trovare un sottoin-sieme di sequenze in ingresso al canale che vengono ricevute in maniera a-dabile: sfruttiamo quindi la proprietà di equipartizione asintotica congiunta per k = 2: la coppia (X(1)_{, X}(2)_{) = (X, Y )} rappresenta rispettivamente il

simbolo di ingresso ed il simbolo di uscita dal canale.

Il nostro scopo è valutare quante sono le sequenze in ingresso distinguibili. Per la proprietà di equipartizione asintotica possiamo aermare che, ri-spettivamente in ingresso ed in uscita al canale, sono presenti ≈ 2nH(X) _e

≈ 2nH(Y ) sequenze tipiche. Inoltre esistono ≈ 2nH(X,Y ) sequenze (Xn_{, Y}n₎

congiuntamente tipiche.

sottoin-sieme più ampio di sequenze alle quali possiamo risalire, senza ambiguità, osservando la sequenza di uscita. Per ogni sequenza tipica in ingresso al canale, esistono ≈ 2nH(Y |X) _{sequenze tipiche equiprobabili in uscita. Il}

nu-mero di sequenze tipiche in uscita è ≈ 2nH(Y )_{: dividendo questa quantità}

per 2nH(Y |X) _{individuiamo il numero di insiemi disgiunti corrispondenti alle}

sequenze tipiche in ingresso distinguibili (vedi gura 4.1).

Figura 4.1: Signicato di H(Y |X)

Otteniamo

2n(H(Y )−H(Y |X)) = 2nI(X;Y ).

Quindi possiamo trasmettere un numero di sequenze pari a ≈ 2nI(X;Y ).

Adat-tando la sorgente al canale il numero di sequenze distinguibili è pari a ≈ 2nC_.

Come sottolineato più volte sopra, queste aermazioni sono solo ap-prossimazioni poichè la proprietà di equipartizione asintotica si basa sulla convergenza in probabilità delle quantità viste nel terzo capitolo.

4.2 Schema di riferimento

Lo schema a cui faremo riferimento è rappresentato in gura 4.2:

Il canale (discreto senza memoria) è descritto da (X ,pY |X(y|x),Y). Per

denire un codice (M,n) poniamo che:

• W è un messaggio estratto dall'insieme {1, ..., M} con distribuzione di probabilità uniforme;

Figura 4.2: Schema di riferimento

• g : Yn _{→ {1, ..., M }} è la funzione che rappresenta la regola

determini-stica di decodica;

• λw = Pr(g(Yn) 6= i|Xn = xn(w))e la probabilità di errore

condiziona-ta;

• λ(n)_{= max}

w={1,...,M }λwè la massima probabilità di errore condizionata;

• Pe(n) = _M1 PM_w=1λw è la media aritmetica della probabilità di errore

condizionata;

• R = log M_n è il tasso del codice.

Si osservi che, essendo la distribuzione di probabilità uniforme, allora P(n) e è

la probabilità dell'evento {W 6= g(Yn_)} che rappresenta l'evento errore del

codice scelto. Inoltre P(n)

e ≤ λ(n).

Il criterio di decisione del decodicatore consiste nello scegliere, come pa-rola di codice trasmessa, quella congiuntamente tipica con la papa-rola ricevuta.

4.3 Teorema di Shannon

Questa è l'enunciazione del teorema:

Teorema 4.1. Per un canale discreto senza memoria per ogni tasso di codice R < C esiste una sequenza di codici (2nR,n) con probabilità massima di errore

λ(n) → 0. Qualsiasi sequenza di codici con λ(n)_{→ 0 deve avere R ≤ C.}

Dimostriamo la prima parte del teorema lasciando la seconda alla sezione successiva.

Dimostrazione. Fissiamo una distribuzione pX(x) dei simboli X.

Generia-mo un codice (2nR_{,n) casuale secondo la distribuzione p}

probabilità di ogni parola di codice è Pr(xn) = n Y i=1 pX(xi).

La probabilità di generare un particolare codice C è:

Pr(C) = 2nR Y w=1 n Y i=1 pX(xi(w)).

Nel teorema non calcoleremo la P(n)

e di un codice ma la probabilità di errore

media Pr(E) di tutti i codici generati secondo la distribuzione pX(x). La

probabilità di errore media Pr(E) è la media pesata su tutti i codici delle rispettive probabilità di errore medie, quindi

Pr(E ) =X C Pr(C)P_e(n) =X C Pr(C) 1 2nR 2nR X w=1 λw(C) = 1 2nR 2nR X w=1 X C λw(C) Pr(C) =X C Pr(C)λ1(C) = Pr(E |W = 1).

Il penultimo passaggio dipende dalla simmetria presente nella costruzione dei codici, poichè consideriamo tutti i codici possibili. La Pr(E) quindi non dipende dal particolare messaggio trasmesso e si può scegliere come messaggio trasmesso W = 1. Deniamo adesso i seguenti eventi:

Ew = {(Xn(w), Yn) ∈ A(n) }.

Si ricorda che inviamo la parola di codice Xn_{(1) relativa al messaggio W =}

1. Sviluppiamo la probabilità di errore Pr(E|W = 1) considerando che il decodicatore commette un errore se:

• la parola di codice trasmessa e la sequenza ricevuta non sono congiun-tamente tipiche;

• una o più parole di codice errate sono congiuntamente tipiche con la sequenza ricevuta. Quindi: Pr(E |W = 1) = Pr(E₁c∪ E2∪ ... ∪ E2nR|W = 1) ≤ Pr(E₁c|W = 1) + 2nR X i=2 Pr(Ei|W = 1),

dove nell'ultimo passaggio si sfrutta il bound di unione. Per la proprietà di equipartizione asintotica ∀, ∃n1 tale che, per n > n1:

Pr(E₁c|W = 1) ≤ .

Resta da sviluppare il secondo termine della somma. Sempre per la proprietà di equipartizione asintotica, per k = 2 e S = (X, Y ), abbiamo

Pr(Ei|W = 1) ≤ 2−n(I(X;Y )−3).

Quindi

Pr(E ) ≤  + (2nR− 1)2−n(I(X;Y )−3) ≤  + 23n₂−n(I(X;Y )−R)

. Se R < I(X; Y ) − 3, ∀, ∃n2 tale che, per n > n2:

2nR

X

i=2

Pr(Ei|W = 1) ≤ .

Qundi, per n > max{n1, n2}:

Pr(E ) ≤ 2.

Per completare il teorema servono tre considerazioni consequenziali: 1. se pX(x) è la distribuzione di probabilità che raggiunge la capacità di

canale allora si può sostituire R < I(X; Y ) con R < C;

2. attraverso una ricerca esaustiva su tutti i codici (2nR_{,n) si sceglie il}

codice C∗ _{migliore; poichè Pr(E) ≤ 2 per n grande allora}

Pr(E |C∗) = 1 2nR 2nR X w=1 λw(C∗) ≤ 2,

per n grande, considerando, come detto, la distribuzione di probabilità uniforme dei messaggi.

3. nel codice C∗ _{scartiamo la metà delle parole di codice con λ}

w più alta.

Questo nuovo codice ha tutte le probabilità di errore condizionali minori o uguali a 4. Il nuovo codice ha tasso R∗ _{= R −} 1

n, trascurabile per n

grande.

Possiamo allora concludere che si può costruire un codice con tasso R∗ _e

massima probabilità di errore λ(n) _{≤ 4.}

Per cui, se R < C, esiste una sequenza di codici (2nR_{, n)con λ}(n) _{→ 0.}

4.4 Inverso debole

L'inverso debole stabilisce che non si può raggiungere una probabilità di errore piccola a piacere se il tasso delle sequenze di codici è maggiore della capacità.

Per dimostrare questa implicazione è necessaria la disuguaglianza di Fano, il teorema dell'elaborazione dei dati e, poichè utilizziamo ripetutamente il canale, un lemma che lega I(Xn_{; Y}n₎con la capacità di canale. Dimostriamo

quindi il lemma:

Lemma 4.1. Dato un canale discreto senza memoria (X , pY |X(y|x), Y) di

capacità C, poniamo Yn la sequenza in uscita rispetto ad una sequenza Xn

in ingresso. Si verica che, ∀pXn(xn),

I(Xn; Yn) ≤ nC. Dimostrazione.

I(Xn; Yn) = H(Yn) − H(Yn|Xn)

= H(Yn) − n X i=1 H(Yi|Y1, ..., Yn, Xn) = H(Yn) − n X i=1 H(Yi|Xi),

per le proprietà dell'entropia condizionata e per la denizione di canale discreto senza memoria. Si osservi che, sempre per le proprietà dell'entropia,

H(Yn) ≤ n X i=1 H(Yi), e quindi I(Xn; Yn) ≤ n X i=1 H(Yi) − n X i=1 H(Yi|Xi)

= n X i=1 I(Xi|Yi) ≤ nC, sfruttando la denizione di capacità.

Il lemma permette di aermare che usare più volte il canale non aumenta la capacità di canale per simbolo trasmesso.

Possiamo adesso dimostrare l'inverso del teorema di Shannon riprendendo l'enunciato:

Teorema 4.2 (Inverso debole). Qualsiasi sequenza di codici (2nR_{,n) con}

λ(n) _{→ 0per n → ∞ deve avere R < C.}

Premettiamo che le variabili aleatorie W , Xn, Yn e ˆ_W, dove quest'

ulti-ma rappresenta l'uscita del decodicatore, forulti-mano una catena di Markov e quindi potremo utilizzare il teorema della elaborazione dei dati.

Dimostrazione. Poichè la variabile aleatoria W ha distribuzione uniforme su {1, ..., 2nR_{}, per le proprietà dell'entropia.}

nR = H(W ), Sviluppando l'entropia di W ,

H(W ) = H(W | ˆW ) + I(W ; ˆW ),

applicando la disuguaglianza di Fano alle variabili aleatorie W e ˆW, H(W | ˆW ) + I(W ; ˆW ) ≤ 1 + P_e(n)nR + I(W ; ˆW ), e inoltre,

1 + P_e(n)nR + I(W ; ˆW ) ≤ 1 + P_e(n)nR + I(Xn; Yn) ≤ 1 + P_e(n)nR + nC.

Il penultimo passaggio deriva dal teorema dell'elaborazione dei dati e l'ultimo dal lemma dimostrato sopra. Dividendo per n otteniamo

R ≤ P_e(n)R + nC + 1 n.

Facendo il limite di entrambi i membri di n → ∞, considerando che, se λ(n) _{→ 0per n → ∞, allora anche P}(n)

e → 0, otteniamo la tesi.

Si può dimostrare che P(n)

e → 1 esponenzialmente se R > C.

Veriche-remo questa aermazione, nel caso particolare di canale binario simmetrico, nel prossimo capitolo.

Capitolo 5

Canale gaussiano

Nella realtà dei sistemi di telecomunicazioni siamo di fronte a vari tipi di canale, come il canale AWGN, in cui l'ingresso e l'uscita sono valori reali.

Il nostro scopo è estendere il concetto fondamentale di capacità a canali continui.

Per far questo generalizzeremo l'informazione mutua a variabili aleatorie reali e valuteremo il massimo dell'informazione mutua; a questo punto de-niremo tale quantità capacità e daremo una giusticazione del suo signicato a canali AWGN.

Per nire dedurremo e rappresenteremo la curva limite di Shannon sul piano (Eb/N0,R/B). Questa curva serve a valutare la bontà dei codici che

sfruttiamo in sistemi reali.

5.1 Capacità del canale AWGN

Il canale AWGN è rappresentato schematicamente in gura 5.1.

Anche in questo caso ci interessa valutare l'informazione che l'uscita fornisce dell'ingresso.

5.1.1 Informazione mutua nel caso di canale continuo

Estendiamo, tramite una operazione di limite, il concetto di informazione mutua al caso continuo. Per questo consideriamo le variabili aleatorie X e Y con densità di probabilità rispettivamente fX(x)e fY(y). Allora

pi = Pr(i∆x < X ≤ (i + 1)∆x) ≈ fX(xi)∆x,

e questa è la probabilità che la variabile aleatoria X si trovi nell'i-esimo intervallo ∆ dell'insieme di denizione. Analogamente

pj = Pr(j∆y < Y ≤ (j + 1)∆y) ≈ fY(yj)∆y.

Riprendiamo l'espressione dell'informazione mutua

I(X; Y ) = +∞ X i=−∞ +∞ X i=−∞ p(i, j)∆x∆ylog p(i, j) p(i), p(j), e facendo il limite per ∆x → 0e ∆y → 0 si ottiene

I(X; Y ) = Z +∞ −∞ Z +∞ −∞ fXY(x, y) log fXY(x, y) fX(x)fY(y) dxdy. Questa è l'informazione che Y fornisce su X.

Questa operazione di limite non si può fare con l'entropia poiché l'opera-zione limite fa tendere l'entropia all'innito. Questo risultato ha comunque un signicato sico poichè un numero reale ha innite cifre decimali e quindi l'informazione è innita.

Partendo dall'espressione dell'informazione mutua possiamo ricavare una nuova quantità: l'entropia dierenziale.

I(X; Y ) = Z +∞ −∞ Z +∞ −∞ fXY(x, y) log fXY(x, y) fX(x)fY(y) dxdy = − Z +∞ −∞ fX(x) log fX(x)dx + Z +∞ −∞

fX|Y(x|y) log fX|Y(x|y)dx

= h(X) − h(X|Y )

La quantità h(X) è chiamata entropia dierenziale e si possono ripetere per questa le considerazioni svolte nel primo capitolo; si può quindi denire una entropia dierenziale congiunta e condizionata (vedi sopra) e una informa-zione mutua condizionata con le stesse relazioni viste e si possono fare le analoghe estensioni.

In questo lavoro l'entropia dierenziale è solo una grandezza di appoggio, per cui non ci soermeremo oltre riguardo al suo signicato sico.

5.1.2 Capacità del canale AWGN

Deniamo capacità C del canale AWGN il massimo dell'informazione mutua al variare di f(x) con il vincolo

E[X2] = P.

Prima di dimostrare che il signicato della capacità C è analogo al caso di canale discreto senza memoria calcoliamo il massimo dell'informazione mutua.

Calcolo della capacità di un canale AWGN

Si tratta di trovare la distribuzione di probabilità che massimizza l'infor-mazione mutua. Una strada agevole per far questo è prima trovare quale è la distribuzione di probabilità che massimizza l'entropia dierenziale di una variabile aleatoria. Il problema si risolve con la tecnica dei moltiplicatori di Lagrange: h(X) = − Z fX(x) log 1 fX(x) dx, con i vincoli _Z x2fX(x)dx = P e _Z fX(x)dx = 1.

Quindi, il problema si traduce nella ricerca di fX(x)tale che

Z fX(x) log 1 fX(x) dx + λ Z (x2fX(x) − P )dx + µ Z (fX(x) − 1)dx = max. Derivando per fX(x), Z  log  1 fX(x)  + 1 ln 2 + λx 2_{+ µ}  dx = 0. Ponendo uguale a zero l'integrando si ottiene

fX(x) = 2−( 1 ln 2+λx 2_+µ) = c2−λx2, dove c = 2−ln 21 −µ.

Sostituendo nel vincolo di normalizzazione, c Z 2−λx2 ln 2ln 2dx = c Z e−x2 λln 2dx = 1 e quindi, c = _q 1 2π_{2λ ln 2}1 = 2−ln 21 −µ.

Il vincolo sulla varianza impone che 1

2λ ln 2 = P.

In conclusione si ottiene che la distribuzione di ingresso che massimizza l'entropia dierenziale, con il vincolo sulla varianza, è una gaussiana N (0, P ). Il valore che l'entropia dierenziale assume, se la variabile aleatoria è gaussiana con varianza P , (omettiamo i calcoli) è pari a

h(X) = 1

2log(2πeP )

Abbiamo dimostrato che, a parità di varianza, la distribuzione che fornisce la massima entropia dierenziale è la gaussiana (il valor medio è irrilevante, quindi non porta informazione). Il ragionamento è logico poichè la gaussiana è la distribuzione che rappresenta i fenomeni più caotici e quindi più incerti. Valutiamo la capacità C = maxfX(x)I(X; Y )con il vincolo sulla varianza

P.

I(X; Y ) = h(Y ) − h(Y |X) = h(Y ) − h(X + Z|X)

= h(Y ) − h(Z|X) = h(Y ) − h(Z).

L'ultimo passaggio è legittimato dal fatto che il rumore è indipendente dal-l'ingresso.

Sappiamo che h(Z) = 1

2log(2πeN ) poichè Z ∈ N (0, N); h(Y ) è pari a

X + Z, X è massima per una distribuzione gaussiana e la somma di variabili aleatorie gaussiane è una gaussiana, quindi Y ∈ N (0, N + P ) con valore h(Y ) = 1₂log[2πe(N + P )], allora

C = 1

2log[2πe(N + P )] − 1

= 1 2log  1 + P N  .

Al contrario della capacità di canale del caso discreto, nel caso continuo la capacità può assumere valori arbitrariamente grandi: un simbolo a valori reali può infatti fornire una informazione innita.

5.2 Teorema della capacità nel caso di canale

AWGN

La dimostrazione rigorosa del teorema della capacità in presenza di ru-more additivo gaussiano bianco richiederebbe molto spazio e la necessità di estendere al caso continuo il concetto di sequenze congiuntamente tipiche.

Cerchiamo di sfruttare il teorema della capacità del caso discreto. In un canale AWGN, riducendoci all'essenziale, in ingresso abbiamo un numero reale ed in uscita un numero reale.

Un numero reale si rappresenta, in generale, con innite cifre prima e dopo la virgola (al limite si tratta di zeri) a cui si aggiunge davanti un simbolo binario (+ o −).

Un canale AWGN è quindi equivalente ad inniti canali discreti senza memoria, ognuno associato ad una cifra con l'aggiunta di uno per il segno. La posizione della virgola non deve essere fornita per costruzione.

Tralasciamo il calcolo della capacità (nota) partendo da questi inniti sistemi discreti senza memoria e vediamo se è possibile trovare una sequenza di codici tali che la probabilità media di errore e la probabilità condizionata massima tendono a 0 per n → ∞.

Ad ogni canale discreto senza memoria possiamo applicare il teorema della capacità visto: per ogni cifra e per il segno esiste una sequenza di codici tali che la probabilità media di errore e la probabilità condizionata massima tendono a 0 per n → ∞.

Come parola di codice si prende quella sequenza di numeri reali formata dalle cifre degli inniti codici associati ad ogni sistema discreto.

Nel caso di canale AWGN valgono le stesse considerazioni del teorema della capacità nel caso discreto riguardo alla probabilità di errore media e probabilità condizionata massima.

5.3 Applicazione: segnali a banda limitata

Ogni segnale a durata limitata ha banda innita. Sappiamo d'altra parte che si può denire una banda essenziale nita dove è contenuta la maggior parte dell'energia.

Senza entrare nei dettagli sappiamo che un tale segnale a durata e banda essenziale nita, può essere sviluppato su una opportuna base e che la dimen-sione dello spazio generato dalla base è pari a 2BT : B è la banda essenziale e T la durata.

Nel caso di segnali a banda essenziale B, data la potenza P , l'energia è pari a P T e l'energia per campione è quindi P T

2BT = P 2B.

Nel caso del rumore il discorso è analogo: la potenza del rumore è 2BN0T

2

e quindi per campione avrò BN0T

2BT = N0

2 .

Poichè in ogni secondo ci sono 2B campioni, allora C = 2B1 2log  1 + P N0B  = B log  1 + P N0B  , con unità di misura bit.

5.4 Applicazione: curva limite della capacità

Abbiamo visto che la formula della capacità per segnali limitati (pratica-mente) in banda è C = B log  1 + P N0B  . Riprendiamo il concetto di tasso R del codice.

Come abbiamo visto

R = numero di bit di informazione numero di bit sici .

Poichè si trasmettono k bit di informazione al secondo, si avrà Eb = PsTb =

Ps

R,

dove Tb è la durata di un bit sico. Si denisce inoltre, con il termine di

ecienza di banda, la quantità nota r = R

con unità di misura bit/secondo Hz . Allora, sostituendo, C B = log(1 + r Eb N0 ).

Per il teorema della capacità di Shannon deve essere r < C

B e quindi bisogna

individuare il luogo dei punti tali che

r < log  1 + rEb N0  .

In gura 5.2 è rappresentato il limite di Shannon e la zona conseguibi-le teoricamente, a patto di trovare il codice. Il punto interrogativo indica la prestazione di un Turbocodice ed è rarontata con la prestazione di un convoluzionale.

Figura 5.2: Curva limite di Shannon

Capitolo 6

Applicazioni

Esamineremo, in quest'ultimo capitolo i codici a parità ed il canale ad accesso multiplo. Per quanto riguarda il primo argomento si tratta di dimo-strare che, se tra i codici ci restringiamo al sottoinsieme dei codici a parità, che brevemente riprenderemo, allora i risultati del teorema della capacità di Shannon continuano a valere e possiamo trovare codici a parità che forniscano una probabilità di errore piccola a piacere. Riguardo al secondo applichere-mo il concetto di sequenze congiuntamente tipiche e il teorema della capacità di Shannon al canale ad accesso multiplo nel caso di due sorgenti. I risultati comunque si possono estendere a più sorgenti. Lo scopo è di capire le diverse tecniche in uso dal punto di vista della teoria dell'informazione.

6.1 I codici lineari a blocco

6.1.1 Denizioni

I codici lineari sono codici con una struttura algebrica. Un codice (n,k) di questo tipo è un codice che associa, a k = nR bit di informazione, 2k

parole di codice di n bit. Nei codici a parità il codice è una trasformazione lineare dallo spazio vettoriale Fk_{allo spazio vettoriale F}n_{, sul campo di Galois}

{(0, 1), +, −}.

Poiché ogni parola di codice deve essere l'immagine di una sola sequenza di bit di informazione, la matrice che rappresenta la trasformazione lineare , detta matrice generatrice, deve avere rango pieno.

L'insieme delle parole di codice, detto dizionario, è, quindi, un sottospazio vettoriale di Fn. Ogni dizionario possiede come parola di codice la parola

nulla e la combinazione lineare di parole di codice è ancora una parola di codice.

Ai ni della decodica si considera la matrice [H], detta matrice di con-trollo di parità. Questa matrice ha come righe una base del sottospazio ortogonale al codice. La matrice di controllo di parità [H] di un codice (n,k) ha n − k righe ed n colonne.

Da questo deriva che, se yn _{è una parola di codice,}

yn[HT] = 0,

e questa è una tecnica per vericare se la parola ricevuta è una parola di codice. La matrice [H] permette di controllare se le equazioni di parità della parola ricevuta sono vericate.

Un codice lineare a blocco è un codice a correzione d'errore e utilizza la tecnica della sindrome che ripetiamo brevemente. Dato il vettore ricevuto yn, si eseguono le seguenti operazioni:

• si eettua l'operazione xn_{[H] = s}n−k;

• individuata la sindrome sn−k _{si risale alla sequenza errore ˆe}n _{di peso di}

Hamming minore che può averla generata;

• si eettua l'operazione di stima della sequenza trasmessa ˆxn_{= y}n_{+ ˆe}n_.

6.1.2 Validità dei codici lineari a blocco

Dimostreremo in questa sezione che i codici lineari a blocco vericano il teorema di Shannon.

Teorema 6.1. Dato un canale binario simmetrico con capacità C per ogni tasso R < C esiste una sequenza di codici (n,k) lineari a blocco con probabilità di errore media che tende a 0.

Dimostrazione. Premettiamo che la generazione di una matrice di parità ca-suale implica che questa matrice non ha necessariamente rango pieno. Si potrebbe comunque calcolare la caratteristica media di una matrice di parità casuale e vericare che la dimostrazione resta valida.

Per quanto riguarda il criterio di decisione considereremo l'insieme tipico A(n) delle sequenze di errore en; data la sindrome ricevuta vericheremo se

nell'insieme tipico A(n)

 esiste una sequenza encoincidente con quella ricevuta:

avremo allora la sequenza di correzione cercata. Nel caso che en _{∈ A/} (n)  o

esiste almeno una ˆen dierente da en con la stessa sindrome, abbiamo un

errore. Deniamo le due probabilità di errore rispettivamente Pr(EI|Hi) e

Esaminiamo separatamente i due termini. Per le proprietà del condizio-namento e per quelle delle sequenze tipiche,

lim

n→∞Pr(e

n _{∈ A/} (n)  ) = 0.

Passiamo al secondo termine e deniamo:

• n(Hi)il numero di sequenze tipiche ˆenche dieriscono da quella corretta

data la matrice di controllo di parità Hi.

Allora P (EII|Hi) ≤ X en_∈A(n)  Pr(en|Hi)n(Hi).

Si osservi che Pr(en_{|H) = Pr(e}n₎, poichè i vettori errore non dipendono dalla

matrice di parità.

Eseguiamo adesso la media su tutti i possibili codici:

2nk X i=1 Pr(EII|Hi) Pr(Hi) = [ X en_∈A(n)  Pr(en)](|A(n)_ | − 1)2−(n−k) ≤   X en_∈A(n)  Pr(en)  (|A(n)_ |)2−(n−k). dove 2n−k _{è la cardinalità dell'insieme delle sindromi.}

Si osservi che la cardinalità di A(n)

 è pari a 2H(e

n₎

e, per le proprietà dell'entropia, H(en_{) = nH(e). In pratica H(e) = H(p) che è l'entropia della}

probabilità di errore di un canale binario simmetrico.

Facendo il limite, tenendo conto delle proprietà dell'insieme tipico, il secondo termine tende a zero se

nH(p) − n + k < 0, quindi

k

n < 1 − H(p) = CBSC

6.1.3 Codici LDPC

I codici LDPC sono codici a blocco, lineari e sistematici la cui matrice di controllo di parità H ha una bassa densità di 1.

Questi codici hanno applicazione nella trasmissione digitale non real-time e utilizzano come base della tecnica di decodica il message passing. Questi aspetti esulano dallo scopo del presente lavoro. Essendo dei codici a parità, la dimostrazione resta valida se si ridenisce la quantità

2nk

X

i=1

P (Hi)n(Hi).

Quindi anche per i codici LDPC valgono le stesse considerazioni fatte no ad adesso.

6.1.4 Osservazione

Il teorema della capacità di Shannon scoprì e legittimò l'esistenza di codici ottimi e spinse alla loro ricerca. Solo negli ultimi decenni, con la riscoperta dei codici LDPC, siamo arrivati a codici che forniscono prestazioni vicine al limite di Shannon in presenza di canale AWGN.

Questo è stato il risultato più signicativo del teorema della capacità.

6.2 Teorema della capacità per canali ad

acces-so multiplo

Nel caso di canali con due sorgenti si procede in maniera analoga al caso (degenere) di canale singolo.

6.2.1 Schema di riferimento

Il canale ad accesso multiplo (discreto senza memoria) è descritto da (X1,X2,pY |X1X2(y|x1, x2),Y). Per denire un codice (M1,M2,n) poniamo che:

• W1 e W2 sono i messaggi estratti dagli insiemi {1, ..., M1}e {1, ..., M2}

con distribuzione di probabilità uniforme; • Xn

1 : {1, ..., M1} → Xn e X2n : {1, ..., M2} → Xn sono le funzioni di

codica;

• g : Yn _{→ {1, ..., M}

1} × {1, ..., M2} è la funzione che rappresenta la

• λw1w2 = Pr(g(Y

n_{) 6= (w}

1, w2)|X1n = xn1(w1), X2n = xn2(w1)) è la

proba-bilità di errore condizionata; • λ(n)_{= max}

w1w2λw1w2 è la massima probabilità di errore condizionata;

• Pe(n) = _2n(R1+R2)1 P_wM₁1₌₁PM_w22₌₁Pr{g(Yn) 6= (w1, w2)|(w1, w2)} è la

pro-babilità media di errore del codice;

• R1 = log M_n 1 e R2 = log M_n 2 sono i tassi del codice.

6.2.2 Teorema

Teorema 6.2. Per un canale ad accesso multiplo (con due utenti) discreto senza memoria, per tassi di codice R1 e R2 tali che

R1 < I(X1; Y |X2),

R2 < I(X2; Y |X1)

e

R1+ R2 < I(X1, X2; Y ),

dove X1 e X2 sono i simboli in ingresso al canale, associati ai due utenti,

e Y è il simbolo ricevuto, esiste una sequenza di codici (2nR1,2nR2,n) con

probabilità massima di errore λ(n)_{→ 0 per n → ∞.}

Dimostrazione. Fissiamo pX1X2(x1, x2) = pX1(x1)pX2(x2)e generiamo un

co-dice casuale formato da 2nR1 parole di codice, riferite al primo utente, e 2nR2

parole di codice, riferite al secondo utente. L'insieme delle possibili parole di codice è dato da 2n(R1+R2). La probabilità del codice è

Pr{C} = 2nR1 Y w1=1 n Y i=1 pX1(x1i) 2nR2 Y w2=1 n Y j=1 pX2(x2i).

La tecnica di decodica è analoga al caso di un solo utente; ricevuto yn _si

risale agli xn

1 ed xn2 congiuntamente tipici: se una coppia (xn1,xn2) esiste ed è

unica la decodica è eseguita, altrimenti si genera un errore.

L'analisi della probabilità media di errore del codice procede sulla falsa-riga del caso di canale con un solo utente: per simmetria

Deniamo gli eventi

Ew1w2 = {(X

n

1(w1), X2n(w2), yn)}.

e, per il bound di unione,

P_e(n)= Pr(E₁₁c ∪ (∪(w1,w2)6=(1,1)Ew1w2)|(W1, W2) = (1, 1)) ≤ Pr(E₁₁c |(W1, W2) = (1, 1)) + X (w16=1,w2=1) Pr(Ew1,1|(W1, W2) = (1, 1)) + X (w1=1,w26=1) Pr(E1,w2|(W1, W2) = (1, 1)) + X (w16=1,w26=1) Pr(Ew1,w2|(W1, W2) = (1, 1)).

Per quanto riguarda il primo termine, osserviamo che, per ogni  > 0 esiste un n1 tale che, per n > n1,

Pr(E₁₁c |(W1, W2) = (1, 1)) ≤ .

Sfruttiamo le proprietà delle sequenze congiuntamente tipiche per trovare una maggiorazione degli ultimi tre termini. Poniamo i seguenti tre casi:

1. S1 = (X1), S2 = (Y ) e S3 = (X2);

2. S1 = (X2), S2 = (Y ) e S3 = (X1);

3. S1 = (X1, X2) e S2 = (Y ).

Ogni posizione implica, rispettivamente, che:

1. per ogni  > 0 esiste un n2 tale che, per n > n2,

Pr(Ew1,1|(W1, W2) = (1, 1)) ≤ 2

−n(I(X1;Y |X2)−3)_;

2. per ogni  > 0 esiste un n3 tale che, per n > n3,

Pr(E1,w2|(W1, W2) = (1, 1)) ≤ 2

3. per ogni  > 0 esiste un n4 tale che, per n > n4, Pr(Ew1,w1|(W1, W2) = (1, 1)) ≤ 2 −n(I(X1,X2;Y )−4)_. Sostituendo P_e(n)≤  + 2nR1₂−n(I(X1;Y |X2)−3) +2nR2₂−n(I(X2;Y |X1)−3) +2n(R1+R2)₂−n(I(X1,X2;Y )−4)_.

Prendendo ¯n = max{n1, n2, n3, n4}si dimostra che Pe(n)→ 0 per n → ∞ se

R1 < I(X1; Y |X2),

R2 < I(X2; Y |X1)

e

R1+ R2 < I(X1, X2; Y ).

Con un discordo analogo al caso di canale singolo si può dimostrare che anche λ(n) _{→ 0 per n → ∞: è suciente scegliere, tramite una ricerca}

esaustiva, il codice migliore ed eliminare la metà peggiore delle parole di codice concatenate.

Questo signica non solo che per n grande è possibile trovare un codice con Pe(n) piccola a piacere, ma anche che che la probabilità di trovarlo aumenta

con n: per n → ∞ tutti i codici sono ottimi.

Con gli strumenti delle sequenze congiuntamente tipiche si può dimostrare che, per qualsiasi numero di utenti m nito, il teorema, con le modiche del caso, resta valido. Naturalmente si individuerà una regione di tassi di codice permissibili m-dimensionale.

Si osservi inne che la scelta della distribuzione uniforme per le due sor-genti è, anche in questo caso, conservativa, poichè la distribuzione uniforme è la più caotica se l'alfabeto è nito.

6.2.3 Concetto di regione di capacità

Nel caso di canale ad accesso multiplo con due utenti, le tre relazioni R1 < I(X1; Y |X2),

R2 < I(X2; Y |X1)

e

R1+ R2 < I(X1, X2; Y ).

individuano una regione di tassi di codice permissibili che, si può dimostrare, essere convessa. In altre parole, dati due vettori tassi di codice ( ˆR1, ˆR2) e

( ¯R1, ¯R2), il vettore (R1, R2) = λ( ˆR1, ˆR2) + (1 − λ)( ¯R1, ¯R2), dove 0 < λ < 1 è

un vettore di tassi di codice permissibile.

Data una particolare distribuzione pX1(x1)pX2(x2), la regione della

capa-cità è del tipo rappresentativo in gura 6.1.

Figura 6.1: Regione della capacità

Osserviamo che

I(X1, X2; Y ) = I(X1; Y ) + I(X2; Y |X1),

ma se pX1X2|Y(x1, x2|y) = pX1|Y(x1|y)pX2|Y(x2|y), ovvero se i canali sono

indipendenti, allora

I(X1, X2; Y ) = I(X1; Y ) + I(X2; Y ),

e quindi le due sorgenti possono trasmettere al tasso massimo.

La regione della capacità è allora un rettangolo e il vertice (R1, R2) =

(I(X1; Y ), I(X2; Y )) è il punto che garantisce la trasmissioni con i tassi più