Secondo teorema di Shannon

In teoria dell'informazione, il secondo teorema di Shannon, o teorema della codifica di canale, stabilisce che per quanto un canale di comunicazione sia affetto da rumore, è possibile trasmettere dati (informazione) attraverso il canale stesso con probabilità di errore P_e piccola a piacere fino ad una frequenza massima. Questo sorprendente risultato, noto anche come teorema fondamentale della teoria dell'informazione, fu presentato per la prima volta da Claude Shannon nel 1948.

La capacità di Shannon di un canale di comunicazione, nota anche come limite di Shannon, è il massimo tasso di trasferimento di dati che può fornire il canale per un dato livello di rapporto segnale/rumore, con un tasso di errore piccolo a piacere.

Panoramica

Il teorema, formulato nel 1948 da Claude Shannon, descrive la massima efficienza possibile di un qualunque metodo di correzione degli errori in funzione del livello di rumore. La teoria non spiega come costruire un codice ottimo, ma stabilisce solo quali siano le prestazioni del codice ottimo. Il secondo teorema di Shannon ha numerose applicazioni, sia nel campo delle telecomunicazioni che in quello dell'archiviazione di dati. Questo teorema è alla base della moderna Teoria dell'informazione. Shannon diede solo una traccia della dimostrazione. La prima dimostrazione rigorosa è dovuta a Amiel Feinstein nel 1954.

Il teorema stabilisce che, dato un canale con capacità C, su cui viene trasmessa informazione ad un tasso R, allora se

$R<C$

esiste un codice che consente di rendere la probabilità di errore al ricevitore arbitrariamente piccola. Questo significa che, teoricamente, è possibile trasmettere informazione senza errori (BER=0) a qualunque tasso inferiore a C.

Anche l'inverso è importante. Se

$R>C$

non è possibile raggiungere una probabilità di errore piccola a piacere. Qualunque codice avrebbe una probabilità di errore superiore ad un certo valore maggiore di zero, e questo valore cresce al crescere del tasso. Non è quindi possibile garantire che l'informazione sia trasmessa in maniera affidabile su un canale ad un tasso superiore alla capacità. Il teorema non considera il caso in cui R e C siano uguali.

Semplici schemi, come i codici a ripetizione (ossia trasmetti un unico bit un numero dispari di volte e scegli il bit ricevuto a maggioranza) sono metodi di correzione degli errori inefficienti e non sono in grado di avvicinare il limite di Shannon. Al contrario tecniche avanzate come i codici Reed-Solomon o i Turbo codici, si avvicinano molto di più al limite di Shannon, al costo di un'elevata complessità computazionale. Utilizzando i più recenti codici Turbo e la potenza computazionale disponibile sugli odierni DSP, è oggi possibile avvicinarsi a meno di 1/10 di decibel rispetto al limite di Shannon

Enunciato

Teorema (Shannon, 1948):

1. Per ogni canale discreto senza memoria, la capacità di canale

$C=\max _{P_{X}}\,I(X;Y)$

ha le seguenti proprietà. Per ogni ε > 0 e R < C, per un N grande abbastanza, esiste un codice di lunghezza N e tasso ≥ R ed un algoritmo di decodifica, tale che la massima probabilità di errore di sia ε.

2. Se una probabilità di errore per bit p_b è accettabile, sono raggiungibili tassi fino a R(p_b), dove

$R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.$

e $H_{2}(p_{b})$ è l'entropia di una sorgente binaria

$H_{2}(p_{b})=-\left[p_{b}\log {p_{b}}+(1-p_{b})\log({1-p_{b}})\right]$

3. Per ogni p_b, tassi superiori a R(p_b) non sono raggiungibili.

Traccia della dimostrazione

Come per numerosi altri risultati fondamentali in teoria dell'informazione, la dimostrazione del secondo teorema di Shannon include una dimostrazione della raggiungibilità ed una prova dell'inverso. Queste due componenti servono per limitare, in questo caso, l'insieme dei tassi possibili a cui è possibile comunicare su un canale rumoroso e dimostrare che tali limiti sono limiti in senso stretto.

Le seguenti tracce sono solo un insieme di numerosi metodi proposti nei testi di teoria dell'informazione.

Raggiungibilità per canali discreti senza memoria

Questa particolare di raggiungibilità è simile a quella usata per dimostrare la proprietà di equipartizione asintotica (AEP).

Questa tecnica fa uso di un'argomentazione basata su una scelta di codice casuale, per cui l'insieme delle parole di codice (in inglese codebook) è costruito a caso; questo consente di ridurre la complessità computazionale, provando tuttavia l'esistenza di un codice che soddisfa la probabilità di errore desiderata per ogni tasso inferiore alla capacità di canale.

Utilizzando un'argomentazione legata alla AEP, date delle stringhe di simboli sorgenti lunghe n $X_{1}^{n}$ e delle stringhe lunghe n di uscite del canale $Y_{1}^{n}$, si può definire un insieme congiuntamente tipico nel modo seguente:

$A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}$

$2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}$

$2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}$

${2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}$

Due sequenze ${X_{1}^{n}}$ e $Y_{1}^{n}$ sono congiuntamente tipiche se ricadono nell'insieme congiuntamente tipico appena definito.

Passaggi

1. Nello stile dell'argomentazione della codifica casuale, si generano a caso $2^{nR}$ parole di codice di lunghezza n dalla densità di probabilità Q.
2. Questo codice è noto sia al trasmettitore che al ricevitore; si assume anche che entrambi conoscano la matrice di transizione $p(y|x)$ per il canale in uso.
3. Un messaggio W è scelto secondo la distribuzione uniforme sull'insieme delle possibili parole di codice. Ossia, $Pr(W=w)=2^{-nR},w=1,2,...,2^{nR}$.
4. Il messaggio è spedito sul canale.
5. Il ricevitore riceve il messaggio secondo la distribuzione $P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))$
6. Inviando le parole di codice sul canale, si riceve $Y_{1}^{n}$, e si decodifica in un qualche simbolo sorgente se esiste esattamente una parola di codice che è congiuntamente tipica con Y. Se non esistono parole di codice congiuntamente tipiche, o se ce n'è più di una, allora si compie un errore. Un errore avviene anche quando una parola di codice decodificata non corrisponde alla parola di codice inviata. Questa tecnica è indicata con il nome di codifica per insieme tipico.

La probabilità di errore è divisa in due parti:

1. Primo, può esserci errore se non esiste una sola sequenza X congiuntamente tipica con la sequenza Y ricevuta.
2. Secondo, può esserci errore se una sequenza X incorretta è congiuntamente tipica con la sequenza Y ricevuta.

• In base alla assunzione di casualità del codice, si può imporre che la probabilità media di errore mediata su tutti i codici, non dipende dall'indice inviato. Quindi si può, senza perdita di generalità, assumere W=1.

• Dalla AEP congiunta, è noto che la probabilità che non esistano (o esista più di una) sequenze X congiuntamente tipiche, tende a 0 al crescer di n. Si può limitare superiormente tale probabilità con $\varepsilon$.

• Inoltre dalla AEP congiunta, è noto che la probabilità che una particolare $X_{1}^{n(i)}$ e la risultante $Y_{1}^{n}$ da W=1 siano congiuntamente tipiche è $\leq 2^{-n(I(X;Y)-3\varepsilon )}$.

Definita:

$E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,...,2^{nR}$

l'evento che un messaggio sia congiuntamente tipico con la sequenza ricevuta quando è inviato il messaggio 1.

$P(error)=P(error|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})$

$\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}$

Si può osservare che al tendere all'infinito di n, se $R<I(X;Y)$ per il canale, la probabilità di errore tende a zero.

Infine, avendo dimostrato che l'insieme medio delle parole di codice è "buono", esiste certamente un insieme di parole di codice le cui prestazioni sono migliori di quello medio, e questo soddisfa la nostra necessità di avere una probabilità di errore piccola a piacere nella comunicazione sul canale rumoroso.

Dimostrazione inversa debole per canali discreti senza memoria

Si supponga di avere un codice composto da $2^{nR}$. Sia W estratta uniformemente su questo insieme come indice. Siano $X^{n}$ e $Y^{n}$ le parole di codice e quelle ricevute, rispettivamente

1. $nR=H(W)=H(W|Y^{n})+I(W;Y^{n})\;$ usando uguaglianze legate all'entropia ed all'informazione mutua.
2. $\leq H(W|Y^{n})+I(X^{n}(W);Y^{n})$ dato che X è una funzione di W
3. $\leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})$ utilizzando la disuguaglianza di Fano
4. $\leq 1+P_{e}^{(n)}nR+nC$ per il fatto che la capacità è il massimo dell'informazione mutua.

Il risultato di questi passaggi è che $P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}$. Al tendere della lunghezza n all'infinito, si ottiene che $P_{e}^{(n)}$ è limitato superiormente da 0 se R è più grande di C; si possono invece ottenere tassi d'errore bassi a piacere se R è minore di C.

Dimostrazione inversa forte per canali discreti senza memoria

Un teorema inverso forte, dimostrato da Wolfowitz nel 1957, stabilisce che

$P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-n(R-C)}$

per una qualche costante positiva $A$. Mentre l'inverso debole stabilisce che la probabilità di errore è strettamente superiore rispetto a 0 al tendere di $n$ all'infinito, il teorema forte afferma che l'errore tende esponenzialmente a 1. Quindi, $C$ è una soglia che divide tra comunicazione perfettamente affidabile e completamente inaffidabile.

Teorema della codifica di canale per canali senza memoria non stazionari

Si assuma che il canale sia privo di memoria, ma che le sue probabilità di transizione varino in funzione del tempo, in un modo noto sia al trasmettitore che al ricevitore.

La capacità di canale è data da

$C=\lim \;\inf \;\;\max _{p^{(}X_{1}),p^{(}X_{2}),...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i})$

Il massimo si ottiene per le distribuzioni che raggiungono la capacità per ogni canale, ossia

$C=\lim \;\inf \;\;{\frac {1}{n}}\sum _{i=1}^{n}C_{i}$

dove $C_{i}$ è la capacità dell'i-simo canale.

Traccia della dimostrazione

La dimostrazione segue sostanzialmente gli stessi passaggi del Primo teorema di Shannon. La raggiungibilità deriva dalla codifica casuale, con ogni simbolo scelto a caso dalla distribuzione che raggiunge la capacità per un particolare canale. Argomentazioni basate sulla tipicalità usano la definizione data di insieme tipico per sorgenti non stazionarie definita nella AEP.

Il limite inferiore entra in gioco quando ${\frac {1}{n}}\sum _{i=1}^{n}C_{i}$ non converge.

Bibliografia

• Claude E. Shannon, A Mathematical Theory of Communication Urbana, IL:University of Illinois Press, 1949 (ristampato nel 1998).
• Robert M. Fano, Transmission of information; a statistical theory of communications., M.I.T. Press, 1961.
• Thomas Cover, Joy Thomas, "Elements of Information Theory", 2ª edizione, Wiley & Sons, 2006

Voci correlate

• Teoria dell'informazione
• Primo teorema di Shannon