Capacità di canale

Con la Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente → si è visto quanto si può comprimere un messaggio (il limite è l'entropia); con le modulazioni e il Link budgetIl sistema di trasmissione si modella con un canale che attenua ($a_{ch}$) e filtra il segnale, un rumore additivo bianco gaussiano (AWGN) che si somma dopo il canale, e un ricevitore con cifra di rumore $F_{rc}$. Il link budget è il bilancio che dà l'SNR in ricezione, $\text{SNR}=\frac{P_{tx}}{a_{ch},kT_0F_{rc},B}=\frac{M_{tx}}{a_{ch}N_0B}$, che deve superare una soglia; in dB (banda stretta) $\text{SNR}{dB}=(P{tx}){dBm}+114-(a{ch}){dB}-(F{rc}){dB}-10\log{10}B_{MHz}$. Lo si usa per ricavare la potenza minima, la banda massima o la distanza massima di un collegamento.Link budget → si è visto come si trasmette un segnale su un canale rumoroso. Resta la domanda decisiva: quanta informazione al secondo si può far passare in un canale in modo affidabile? La risposta, di Shannon, è la capacità del canale. Nel linguaggio del corso: il canale è un tubo con delle perdite; la capacità è la sua portata massima, e oltre quella portata qualcosa si perde per forza.

Vedi anche la versione per Ing. Elettronica: Capacità di canale - canale binario simmetrico, a cancellazione e AWGNLa capacità $C=\max_{p_x}I(x;y)$ è il massimo di informazione mutua tra ingresso e uscita del canale; per il teorema di Shannon si può comunicare con probabilità d'errore arbitrariamente piccola se e solo se il rate è minore di $C$. Per il canale binario simmetrico $C=1-H_2(p)$ bit per uso (ingresso uniforme), per il canale a cancellazione $C=1-\varepsilon$, per l'AWGN $C=\frac12\log_2(1+\text{SNR})$ per uso reale, cioè $C=B\log_2(1+\text{SNR})$ bit/s su una banda $B$. Il limite $R_b<C$ dà il minimo $\frac{E_b}{N_0}\ge\frac{2^\nu-1}\nu$ ($-1{,}59$ dB per $\nu\to0$).Capacità di canale - canale binario simmetrico, a cancellazione e AWGN →.

Informazione mutua: richiamo

Per due variabili aleatorie $X$ (ingresso) e $Y$ (uscita) di un sistema di trasmissione (Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →): $$I(X,Y)=H(X)+H(Y)-H(X,Y)=H(Y)-H(Y|X)=H(X)-H(X|Y).$$ Proprietà: è simmetrica, $I(Y,X)=I(X,Y)$, e $0\le I(X,Y)\le\min\{H(X),H(Y)\}$. Si legge come "quanta informazione di $X$ si ritrova in $Y$": è il collegamento tra ingresso e uscita, un po' come il trasferimento di potenza ma per l'informazione. Due casi estremi:

• canale perfetto ($Y$ funzione deterministica di $X$ e viceversa): $H(X|Y)=0$, $I(X,Y)=H(X)$: tutta l'informazione passa;
• $X$ e $Y$ indipendenti: $H(Y|X)=H(Y)$, $I(X,Y)=0$: l'uscita non dice nulla sull'ingresso.

Esempio. $X$ bit equiprobabile, $Y=X$: $I=H(X)=1$ bit. $Y$ è un bit equiprobabile indipendente da $X$: $I=1+1-2=0$.

Per messaggi lunghi si usa l'entropia per simbolo $H_s(\mathbf x)$; analogamente si definisce l'informazione mutua per simbolo $I_s(\mathbf x,\mathbf y)$. Trasmettendo una parola di codice $\mathbf c$ e ricevendo $\tilde{\mathbf c}$ si considera $I_s(\mathbf c,\tilde{\mathbf c})$. Attenzione: questa grandezza riguarda il canale (non il codice): dal punto di vista dell'informazione $\mathbf b$ ha lo stesso contenuto di $\mathbf c$ (sono una funzione dell'altra: $\mathbf c$ ha solo un po' di ridondanza in più).

Definizione (velocità di informazione attraverso il canale). Se $F=1/T$ è la velocità di simbolo, $$R(\mathbf c)=F\,I_s(\mathbf c,\tilde{\mathbf c})\quad[\text{bit/s}].$$ Non va confusa con la velocità di informazione della sorgente (quella che si legge dall'entropia della sorgente).

Definizione di capacità

Definizione (capacità di Shannon). $\displaystyle C=\max_{\text{statistiche di }\mathbf c}R(\mathbf c)$.

Per "tutte le possibili scelte di $\mathbf c$" non si intendono i valori ma solo le statistiche (la distribuzione di probabilità di ciò che si trasmette). Quasi sempre i canali sono senza memoria e allora (togliendo il pedice $s$) $$C=\max_{\mathbf c}F\,I_s(\mathbf c,\tilde{\mathbf c})=F\max_{\mathbf c}I(\mathbf c,\tilde{\mathbf c})=F\,C_s,\qquad C_s=\max I(\mathbf c,\tilde{\mathbf c})\ \ [\text{bit/simbolo}].$$ Da qui si vede che $C_s$ è la capacità per simbolo, mentre la capacità $C$ (in bit/s) dipende anche dalla velocità di simbolo $F$, che è indipendente.

Cosa influenza $I(\mathbf c,\tilde{\mathbf c})$? Esplicitando $I=H(\tilde{\mathbf c})-H(\tilde{\mathbf c}|\mathbf c)$: $$I(\mathbf c,\tilde{\mathbf c})=\sum_{\boldsymbol\gamma,\boldsymbol\xi}p_{\mathbf c}(\boldsymbol\gamma)\,p_{\tilde{\mathbf c}|\mathbf c}(\boldsymbol\xi|\boldsymbol\gamma)\log_2\frac{p_{\tilde{\mathbf c}|\mathbf c}(\boldsymbol\xi|\boldsymbol\gamma)}{\sum_a p_{\mathbf c}(a)\,p_{\tilde{\mathbf c}|\mathbf c}(\boldsymbol\xi|a)}$$ (il denominatore è la probabilità totale di ricevere $\boldsymbol\xi$, Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →). Dipende da due ingredienti:

1. $p_{\mathbf c}(\boldsymbol\gamma)$: probabilità a priori di trasmettere $\boldsymbol\gamma$ (la si può scegliere);
2. $p_{\tilde{\mathbf c}|\mathbf c}(\boldsymbol\xi|\boldsymbol\gamma)$: transizioni del canale (non le si sceglie).

Per calcolare $C$ si sceglie la statistica di $\mathbf c$ in modo da massimizzare $I$: ciò che resta dipende solo dal canale.

Esempio: canale binario simmetrico (BSC)

Il BSC senza memoria ha un solo parametro, $P=P_{bit}$ (si inverte con probabilità $P$). Le informazioni condizionate $i_{\tilde{\mathbf c}|\mathbf c}(\xi|\gamma)=-\log_2p_{\tilde{\mathbf c}|\mathbf c}(\xi|\gamma)$ valgono $-\log_2P$ se $\xi\ne\gamma$ e $-\log_2(1-P)$ se $\xi=\gamma$. Quindi l'entropia condizionata (non dipende dalla statistica di $\mathbf c$: ogni ingresso ha lo stesso comportamento) $$H(\tilde{\mathbf c}|\mathbf c)=-P\log_2P-(1-P)\log_2(1-P)=h(P),$$ l'entropia binaria (Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →). Massimizzare $I=H(\tilde{\mathbf c})-h(P)$ significa massimizzare $H(\tilde{\mathbf c})$, che per un bit vale al più $1$, ed è raggiunto con ingressi equiprobabili (se $c$ è equiprobabile lo è anche l'uscita, per simmetria). Allora $$\boxed{C_s=1+P\log_2P+(1-P)\log_2(1-P)=1-h(P)}\quad\text{[bit/simbolo]}.$$ Casi: $P=0$ (o $P=1$): $C_s=1$ (canale perfetto, o perfetto con un NOT); $P=\frac12$: $C_s=0$ (canale inutile).

Esempi numerici. $P=10^{-2}$: $C_s=0{,}919$; $P=0{,}05$: $0{,}714$; $P=0{,}1$: $0{,}531$; $P=0{,}11$: $0{,}500$ (a quel punto metà della capacità è persa); $P=0{,}2$: $0{,}278$; $P=0{,}3$: $0{,}119$.

La curva è simmetrica rispetto a $P=\frac12$ (un canale che sbaglia quasi sempre si "inverte"), ha massimo $1$ agli estremi e minimo $0$ in $P=\frac12$.

Il teorema di Shannon per la codifica di canale

Si abbia un canale di capacità $C$ e una sorgente il cui messaggio ha velocità di informazione $R$ (vedi $R_b$ come velocità informativa dopo la codifica di sorgente).

Teorema (parte diretta). Se $R<C$ allora per ogni $\delta>0$ e per $n$ sufficientemente grande esistono un dizionario $\mathcal D_b$ di parole di informazione, una codifica di canale $\mu_C$ con parole di lunghezza $n$ e una decodifica $\mu_d$ inversa di $\mu_C$ tali che la probabilità d'errore residua sui bit è $P[b_\ell\ne\hat b_\ell]<\delta$.

Cioè: se $R<C$ (non importa di quanto) l'errore residuo non è nullo, ma può essere piccolo a piacere. Due avvertenze: ciò può richiedere parole molto lunghe ($n\gg1$) e il teorema è solo di esistenza (non dice come costruire il codice, a differenza della codifica di sorgente, dove Huffman e Shannon-Fano sono costruttivi).

Teorema (parte inversa). Se $R>C$ allora esiste $\delta>0$ tale che in ogni codifica $\mu_C$ si ha $P[b_\ell\ne\hat b_\ell]>\delta$.

La parte inversa non dice che la codifica fallisce sicuramente, ma che non si può avere un errore residuo arbitrariamente piccolo. Spesso il teorema si semplifica in: $R<C$ va tutto bene, $R>C$ va tutto male (approssimazione ingegneristica). Si può enunciare anche con la velocità nominale di bit $R_b<C$ (funziona, perché la velocità informativa non supera quella nominale) e con l'errore sulla parola $P[\mathbf c\ne\hat{\mathbf c}]$.

Esempio. BSC con $P=0{,}1$ ($C_s=0{,}531$): un codice con tasso $k/n<0{,}531$ può in linea di principio dare errore arbitrariamente piccolo; l'Hamming $(7,4)$ ha tasso $4/7=0{,}571>0{,}531$ e quindi, con questo canale, nessun codice di tasso $0{,}571$ potrà mai portare l'errore sotto una soglia positiva; invece un $(15,7)$ (tasso $0{,}467$) non è escluso dal teorema (non è garantito che esista, ma non è escluso).

Per i limiti teorici: per la sorgente sono stretti (la codifica di sorgente raggiunge davvero l'entropia); per il canale si è creduto a lungo che fossero lasche, finché si sono scoperti codici avanzati (LDPC, codici turbo) che quasi li raggiungono.

Capacità del canale AWGN

Si può applicare l'impostazione di Shannon a un canale fisico con rumore AWGN? Ingresso $s$ e uscita $r$ sono ora vettori continui; con alcune complicazioni matematiche l'estensione è possibile, con densità di probabilità al posto delle probabilità: $$I(X,Y)=E\Big[\log_2\frac{p_{XY}(x,y)}{p_X(x)p_Y(y)}\Big]=E\Big[\log_2\frac{p_{Y|X}(y|x)}{p_Y(y)}\Big].$$ Il canale è $r=g\,s+w$ (guadagno $g$, rumore $w$ gaussiano, senza ISI e senza memoria): idealmente si ripete la trasmissione ogni $n$ ottenendo sempre la stessa statistica, quindi si omette $n$ e $I_s(s,r)=I(s,r)$.

Passo 1: l'informazione mutua. Dato $s$, $r=gs+w$ ha la densità di $w$ traslata: $p_{r|s}(r|s)=p_w(r-gs)$. Quindi $I(s,r)=E\big[\log_2\frac{p_w(w)}{p_r(r)}\big]$ e dipende dall'ingresso solo tramite $p_r$. La densità di $w$ è gaussiana a media nulla (Distribuzione gaussiana (normale)N(μ, σ²) ha densità e^(−(x−μ)²/(2σ²)) / √(2πσ²), a campana centrata in μ con larghezza σ; media μ, varianza σ²; si standardizza con Z = (X − μ)/σ ~ N(0, 1) e si calcola P(X ≤ x) = Φ((x − μ)/σ), con Φ(−z) = 1 − Φ(z); aX + b è ancora gaussiana, N(aμ + b, a²σ²).Distribuzione gaussiana (normale) →) $$p_w(w)=\frac1{\sqrt{2\pi}\sigma_w}e^{-w^2/2\sigma_w^2}.$$ Passo 2: ingresso ottimo. Si può dimostrare (omesso) che $I$ è massima quando anche $s$ è gaussiano a media nulla (bianco). Allora $r$, somma di gaussiane a media nulla, è gaussiana con varianza $\sigma_r^2=g^2\sigma_s^2+\sigma_w^2$.

Passo 3: il calcolo. Si ha $$\log_2\frac{p_w(w)}{p_r(r)}=\log_2\frac{\sigma_r}{\sigma_w}+\log_2e\Big(\frac{r^2}{2\sigma_r^2}-\frac{w^2}{2\sigma_w^2}\Big)$$ (i fattori $\sqrt{2\pi}$ si semplificano, e $\log_2e^{x}=x\log_2e$). Il valore atteso del secondo termine è $\log_2e\,(\frac12-\frac12)=0$ perché $E[r^2]=\sigma_r^2$ e $E[w^2]=\sigma_w^2$ (varianze). Resta $$\max_sI(s,r)=\frac12\log_2\frac{\sigma_r^2}{\sigma_w^2}=\frac12\log_2\Big(1+\frac{g^2\sigma_s^2}{\sigma_w^2}\Big)=\frac12\log_2(1+\mathrm{SNR}),$$ dove $\mathrm{SNR}=g^2\sigma_s^2/\sigma_w^2$ è il rapporto tra la potenza del segnale ricevuto e quella del rumore. Questa è l'informazione che porta ogni campione.

Passo 4: dal campione al secondo. Il segnale $s(t)$ è gaussiano bianco in banda $\mathcal B$, $|\mathcal B|=B$, con densità spettrale di potenza $A_0\,\mathrm{rect}(f/2B)$: per il teorema del campionamento (Teorema del campionamento, interpolazione e aliasingTeorema di Shannon: un segnale a banda limitata $\omega_M$ si ricostruisce esattamente dai campioni se $T_c<\pi/\omega_M$ (frequenza di campionamento maggiore di quella di Nyquist $2f_{\max}$), con la formula di interpolazione ideale $x(t)=\sum_nx(nT_c)\operatorname{sinc}\left(\frac{t-nT_c}{T_c}\right)$. Sotto Nyquist c'è aliasing: le frequenze alte si confondono con quelle basse e l'informazione è persa.Teorema del campionamento, interpolazione e aliasing →) $B=1/(2T)$, cioè si hanno $F=1/T=2B$ campioni indipendenti al secondo (è anche una dimostrazione alternativa che la banda minima è $B_{min}=1/2T$). Quindi $$C=F\max I(s,r)=\frac1T\cdot\frac12\log_2(1+\mathrm{SNR})=\frac1{2T}\log_2(1+\mathrm{SNR}),$$ $$\boxed{C=B\log_2(1+\mathrm{SNR})}\quad[\text{bit/s}].$$

È la formula chiave dei sistemi di comunicazione fisici: lega la capacità alla potenza e all'energia, tramite $$M_{s_{tx}}=A_0(2B)=\sigma_s^2,\quad M_{s_{rx}}=M_{s_{tx}}g^2,\quad M_w=N_0B=\sigma_w^2,\quad\mathrm{SNR}=\frac{M_{s_{rx}}}{M_w},\quad E_s=M_s\,T.$$ Per un canale con attenuazione $a_{ch}=1/g^2$ e ricevitore con cifra di rumore $F_r$ (Rumore termico, temperatura e cifra di rumoreOgni dispositivo elettrico produce un rumore additivo $w(t)$; la causa principale è il rumore termico (effetto Johnson-Nyquist): una resistenza $R$ alla temperatura $T$ ha PSD $\mathcal P_w=2kTR,\gamma(f)\approx2kTR$, e su un carico adattato la densità di potenza elettrica è $\frac12kT$ (bianca), cioè in banda $B$ una potenza $kTB$ ($kT_0=-174$ dBm/Hz). Si descrive il rumore di una sorgente con la temperatura di rumore $T_s=\frac{p_w}{k/2}$, e quello aggiunto da un doppio bipolo con $T_A$ o con la cifra di rumore $F=1+\frac{T_A}{T_0}$ ($T_0=290$ K, $F\ge1$). Un doppio bipolo passivo a $T_0$ ha $F=a$. In cascata $T_c=T_1+\frac{T_2}{g_1}+\dots$, $F_c=F_1+\frac{F_2-1}{g_1}+\dots$: il primo stadio è il più importante.Rumore termico, temperatura e cifra di rumore →, Link budgetIl sistema di trasmissione si modella con un canale che attenua ($a_{ch}$) e filtra il segnale, un rumore additivo bianco gaussiano (AWGN) che si somma dopo il canale, e un ricevitore con cifra di rumore $F_{rc}$. Il link budget è il bilancio che dà l'SNR in ricezione, $\text{SNR}=\frac{P_{tx}}{a_{ch},kT_0F_{rc},B}=\frac{M_{tx}}{a_{ch}N_0B}$, che deve superare una soglia; in dB (banda stretta) $\text{SNR}{dB}=(P{tx}){dBm}+114-(a{ch}){dB}-(F{rc}){dB}-10\log{10}B_{MHz}$. Lo si usa per ricavare la potenza minima, la banda massima o la distanza massima di un collegamento.Link budget →): $$\mathrm{SNR}=\frac{P_{tx}}{a_{ch}\,\tfrac12kT_{eff}\,(2B)}=\frac{P_{tx}}{a_{ch}\,k\,T_0F_r\,B}.$$ (La resistenza caratteristica $Z_0$ non serve perché si lavora in termini elettrici; servirebbe per il calcolo statistico con $M_w=kT_0F_rB\,Z_0$.)

Esempi. $B=1$ MHz e $\mathrm{SNR}=20$ dB ($100$ in lineare): $C=10^6\log_2101=6{,}66$ Mbit/s. Un $\mathrm{SNR}$ di $0$ dB dà $1$ bit/s/Hz, $10$ dB dà $3{,}46$, $20$ dB dà $6{,}66$, $30$ dB dà $9{,}97$: ogni $10$ dB in più (cioè un fattore $10$ in potenza) aggiungono solo circa $3{,}3$ bit/s/Hz.

Come aumentare $C$. Aumentando $B$ (banale, ma vero) o l'SNR, ma quest'ultimo dà solo una crescita logaritmica (logaritmo in base 2, non in base 10: attenzione al trabocchetto).

Cosa succede al crescere della banda

Se si aumenta $B$ senza cambiare gli altri parametri ($P_{tx}$, $a_{ch}$, $F_r$, $T_0$) la capacità cresce, ma l'SNR cala perché il rumore è proporzionale a $B$. Posto $S=P_{tx}/a_{ch}$ (potenza ricevuta) e $N_0=kT_0F_r$: $$C(B)=B\log_2\Big(1+\frac{S}{N_0B}\Big)\xrightarrow[B\to\infty]{}\ ?\qquad(\infty\cdot0\ \text{forma indeterminata}).$$ Si risolve con il limite notevole $\log(1+x)\sim x$ per $x\to0$ (Limiti notevoli di funzioniI limiti notevoli per le forme 0/0 (log(1+x)/x, (e^x − 1)/x, ((1+x)^α − 1)/x, sin x/x, (1 − cos x)/x², arctan x/x...) con le dimostrazioni, e la loro forma come asintoticità: log(1+f) ~ f, e^f − 1 ~ f, sin f ~ f, 1 − cos f ~ f²/2 quando f → 0.Limiti notevoli di funzioni →, Asintoticità e o-piccolo per funzionif ~ g per x → x0 se f/g tende a 1, f = o(g) se tende a 0; le relazioni dipendono da x0. Regole di calcolo con gli o-piccoli e gerarchia delle funzioni infinite per x → +∞: log < potenze < esponenziali < x^x.Asintoticità e o-piccolo per funzioni →), da scrivere in base naturale: $\log_2(1+x)=\frac{\ln(1+x)}{\ln2}\sim\frac x{\ln2}$. Con $x=\frac S{N_0B}\to0$: $$\lim_{B\to\infty}C=\lim_{B\to\infty}B\,\frac{S}{N_0B\ln2}=\frac{S}{N_0\ln2}\simeq1{,}443\,\frac S{N_0}.$$ La capacità non cresce indefinitamente: ha un asintoto (saturazione). Andamento sublineare.

Esempio. $S/N_0=10^6$ Hz: $C(10^5)=0{,}35$, $C(10^6)=1{,}00$, $C(10^7)=1{,}375$, $C(10^9)=1{,}442$ Mbit/s, contro l'asintoto $1{,}4427$ Mbit/s. Sul $x=B/(S/N_0)=1$ la capacità è già il $69\,\%$ del massimo; oltre $x\approx10$ allargare la banda non serve più. Vedi l'Esercizio - Capacità al crescere della banda.

Un limite sull'energia per bit

Se si trasmette alla velocità $R_b$ con energia per bit $E_b$, la potenza ricevuta è $S=E_bR_b$ e, con efficienza spettrale $\eta=R_b/B$, l'SNR è $\mathrm{SNR}=\frac{E_bR_b}{N_0B}=\eta\frac{E_b}{N_0}$. La condizione di Shannon $R_b<C$ diventa $\eta<\log_2\!\big(1+\eta\frac{E_b}{N_0}\big)$, cioè $$\frac{E_b}{N_0}>\frac{2^\eta-1}{\eta}\ \xrightarrow[\eta\to0]{}\ \ln2=0{,}693\ (-1{,}59\ \text{dB}).$$ Nessun sistema, per quanto sofisticato, può funzionare in modo affidabile con $E_b/N_0$ minore di $-1{,}59$ dB (limite di Shannon). Valori: $\eta=1$: $0$ dB; $\eta=2$: $1{,}76$ dB; $\eta=4$: $5{,}74$ dB; $\eta=8$: $15{,}0$ dB. Le modulazioni (Efficienza spettrale e banda delle modulazioniLa forma $h_{Tx}(t)$ dell'impulso decide la banda e l'ISI: il rettangolo non ha ISI ma una banda enorme (lobi del sinc), il sinc ha banda minima $\frac1{2T}$ ma non è realizzabile e richiede sincronizzazione perfetta, e il coseno rialzato con roll-off $\beta$ ha banda $(1+\beta)\frac1{2T}$ ed è ISI-free ai campionamenti. L'efficienza spettrale è $\nu=\frac{R_b}{B}$ [bit/s/Hz], con massimo $\nu_{max}=\frac{R_b}{B_{min}}$ e $B_{min}=\frac1{2T}$ (banda base), $\frac1T$ (QAM, PSK passabanda), $\frac M{2T}$ (ortogonale), $\frac M{4T}$ (biortogonale). L'SNR di riferimento $\Gamma=\frac{E_s}{TN_0B_{min}}=\frac{P_{tx}}{kT_{eff,rc}B_{min}a_{ch}}\ge\Lambda$ permette di confrontare le modulazioni a $P_{bit}$ fissata; il limite di Shannon è $\nu\le\log_2(1+\Gamma)$.Efficienza spettrale e banda delle modulazioni →) si confrontano con questa curva: a $P_{bit}=10^{-5}$ la BPSK ($\eta=1$) ha bisogno di circa $9{,}6$ dB, cioè sta $\approx9{,}6$ dB sopra il limite $0$ dB. (Questo paragrafo è un completamento dalle formule del corso.)

Un caso particolare: canale a cancellazione

Un canale con ingresso binario e tre uscite $\{0,1,\text{errore}\}$, in cui ogni bit passa intatto con probabilità $q$ e viene sostituito dal simbolo "errore" (cancellazione, erasure) con probabilità $1-q$, non sbaglia mai un bit: lo perde soltanto. Ingresso $X$ con $P[X=1]=\pi$: $H(Y)=h(1-q)+q\,h(\pi)$ (prima si sceglie se c'è cancellazione, poi, se non c'è, il valore) e $H(Y|X)=h(1-q)$ per ogni ingresso. Quindi $I=q\,h(\pi)$, massimo per $\pi=\frac12$: $$C_s=q\ \text{bit/simbolo}.$$ Con $q=0{,}25$ (simulazione d'esame 2013): $C_s=0{,}25$ bit/simbolo. Intuitivamente, la frazione $q$ di simboli non cancellati porta un bit ciascuno.

Errori comuni

• Dire che la capacità "è la velocità del canale": è il massimo di una grandezza statistica (informazione mutua per simbolo per $F$), e dipende da $B$, SNR e dal tipo di canale.
• Usare l'SNR in dB nella formula di Shannon (serve il valore lineare) o un logaritmo in base $10$ (serve la base $2$).
• Pensare che $C\to\infty$ con $B\to\infty$: a potenza fissata satura a $S/(N_0\ln2)$.
• Concludere dalla parte inversa che con $R>C$ "tutto va male in ogni caso" (non si ha errore arbitrariamente piccolo, ma non si dice che la trasmissione sia impossibile).

Collegamenti

Per i codici concreti: Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione →, Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →. Per l'uso nel livello di collegamento (capacità e collisioni, SINR): Livello di collegamento - LLC, MAC e ipotesi di lavoroIl livello di collegamento vede un canale fisico con errori residui e deve offrire ai livelli superiori un canale affidabile; ha due sottolivelli: LLC (correzione residua, ARQ con ACK/NACK) e MAC (chi trasmette, perché con più trasmettitori il rapporto giusto è la SINR e non l'SNR e la capacità cala). Per analizzarlo si usano ipotesi standard: pacchetti di $L$ bit, probabilità $p$ di pacchetto errato (i.i.d., $p=1-(1-P_{bit})^L\simeq LP_{bit}$), coda sempre piena (heavy traffic), tempo di pacchetto $t_P=L/R_b$, $t_{RTT}=t_P+t_A+2\tau_P$, timeout stringente, ACK/NACK senza errori, ritrasmissioni illimitate ($E[#tx]=1/(1-p)$). Le metriche sono throughput (frazione di tempo d'aria) e ritardo (fino alla ricezione corretta). Una collisione è la sovrapposizione, anche minima, di due pacchetti.Livello di collegamento - LLC, MAC e ipotesi di lavoro →.