Tasso d'informazione, capacità di canale e teorema di Shannon

Le due note precedenti hanno dato gli strumenti: entropia (Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →) e informazione mutua (Entropia congiunta e condizionata e informazione mutuaPer due variabili aleatorie discrete $x,y$ l'entropia congiunta è $H(x,y)=E\left[\log_2\frac1{P_{x,y}(x,y)}\right]$ e vale $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, con l'uguaglianza a destra se e solo se $x$ e $y$ sono indipendenti e $H(x,y)=H(x)$ se $y=f(x)$. L'entropia condizionata $H(x|y)=E_y[H(x|y=y)]$ soddisfa la regola della catena $H(x,y)=H(x|y)+H(y)=H(y|x)+H(x)$. L'informazione mutua $I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)$ è simmetrica, $0\le I\le\min{H(x),H(y)}$, nulla per variabili indipendenti.Entropia congiunta e condizionata e informazione mutua →). Ora si mettono in un sistema di comunicazione: quanti bit al secondo produce una sorgente, quanti ne può portare un canale, e a quali condizioni si può trasmettere senza errori (con probabilità d'errore piccola a piacere).

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 →. Versione per Ing. delle Telecomunicazioni: Capacità di canaleLa capacità di un canale è il massimo, sulle statistiche di ingresso, della velocità di informazione $R=F,I_s(\mathbf c,\tilde{\mathbf c})$ (informazione mutua per simbolo per la velocità di simbolo). Teorema di Shannon: se la velocità informativa è $R<C$ esistono codici con probabilità d'errore residua piccola a piacere; se $R>C$ no. BSC senza memoria: $C_s=1+P\log_2P+(1-P)\log_2(1-P)$ bit/simbolo. Canale AWGN: $C=B\log_2(1+\mathrm{SNR})$ con $\mathrm{SNR}=P_{rx}/(N_0B)$; per $B\to\infty$ la capacità non cresce indefinitamente ma tende a $P_{rx}/(N_0\ln2)$. Limite per il rapporto $E_b/N_0$: $\ge\ln2=-1{,}59$ dB.Capacità di canale →.

Sorgente, canale e destinazione

Lo schema della teoria dell'informazione è

$$\text{SORGENTE}\ \xrightarrow{\ x_n\ }\ \boxed{\text{CANALE}}\ \xrightarrow{\ y_n\ }\ \text{DESTINAZIONE}.$$

La sorgente emette il simbolo $x_n$ al tempo discreto $nT$, con valori in un alfabeto $\mathcal A_x$ (segnale digitale); $T$ è il periodo di simbolo. All'uscita del canale c'è il simbolo $y_n$ in un alfabeto $\mathcal A_y$. Il canale è descritto dalle probabilità di transizione $P_{y|x}(b|a)$; è senza memoria se l'uscita $y_n$ dipende solo dall'ingresso $x_n$ dello stesso istante, e le transizioni sono le stesse a ogni istante.

Entropia per simbolo e tasso d'informazione

Se si considera una sequenza (vettore) di simboli $\underline x=[x_{-N},\dots,x_N]$ lunga $2N+1$, la sua entropia $H(\underline x)$ cresce con la lunghezza: per simboli indipendenti ed equidistribuiti (i.i.d., si dice anche "equidistribuiti" per dire che hanno la stessa densità) $$H(\underline x)=\sum_nH(x_n)=(2N+1)H(x_n)\ \xrightarrow{N\to\infty}\ \infty.$$ Per confrontare sorgenti diverse si divide per la lunghezza $L(\underline x)$ del vettore.

Definizione (entropia per simbolo). $$H_s(\underline x)=\frac{H(\underline x)}{L(\underline x)},\qquad H_s(\underline x)=\lim_{N\to\infty}\frac{H([x_{-N},\dots,x_N])}{2N+1}\ \text{per sequenze infinite.}$$ Per simboli i.i.d. $H_s(\underline x)=H(x_n)$.

Esempio (finestra di attività). Una sorgente emette $P$ simboli attivi indipendenti con $P_x(1)=P_x(-1)=0{,}5$ (ciascuno con $H=1$ bit), preceduti e seguiti da simboli sempre nulli ($P_x(0)=1$, $H=0$). La sequenza infinita ha $H(\underline x)=P\cdot1=P$ bit, finita, quindi $H_s=\lim\frac P{2N+1}=0$. L'entropia per simbolo dice che, in media su un tempo infinito, il messaggio ha informazione trascurabile: conta la finestra attiva, non il silenzio.

Se la sorgente emette un simbolo ogni $T$ secondi, il numero di bit al secondo di informazione prodotta è il tasso d'informazione:

Definizione (tasso d'informazione della sorgente). $$R(\underline x)=\frac{H_s(\underline x)}T\quad[\text{bit/s}],\qquad\frac1T=\text{simboli al secondo}.$$

Il tasso nominale è invece quello dei simboli presi come se fossero equiprobabili: $R_{\text{nom}}=\frac{\log_2M_s}{T_s}$ ($M_s$ cardinalità dell'alfabeto). Poiché $H_s\le\log_2M_s$ (Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimoL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit (zero per l'evento certo, additiva per eventi indipendenti). L'entropia di una variabile aleatoria discreta è l'informazione media, $H(x)=E[i_x(x)]=\sum_aP_x(a)\log_2\frac1{P_x(a)}$; vale $0\le H(x)\le\log_2M$ con $M$ cardinalità dell'alfabeto, e il massimo $\log_2M$ si raggiunge se e solo se i simboli sono equiprobabili (dimostrazione con la disuguaglianza di Jensen, perché il logaritmo è strettamente concavo).Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo →) vale sempre $R\le R_{\text{nom}}$.

Tasso d'informazione del canale e capacità

Con la stessa idea, l'informazione mutua per simbolo tra due sequenze è $$I_s(\underline x;\underline y)=H_s(\underline x)+H_s(\underline y)-H_s(\underline x,\underline y).$$

Definizione (tasso d'informazione del canale $g$). $$R(g)=\frac{I_s(\underline x;\underline y)}T\quad[\text{bit/s}],\qquad\underline x=\text{ingresso},\ \underline y=\text{uscita}.$$

Dipende dal canale (la transizione $P_{y|x}$) e dall'ingresso (la densità $p_{\underline x}$), perché $I_s=H_s(\underline x)-H_s(\underline x|\underline y)$. Poiché $I_s\le\min\{H_s(\underline x),H_s(\underline y)\}\le H_s(\underline x)$, si ha $R(g)\le R(\underline x)$: il canale non può trasportare più informazione di quanta ne produca la sorgente.

Definizione (capacità di un canale). È il massimo del tasso d'informazione del canale al variare di tutte le statistiche dell'ingresso: $$\boxed{C=\max_{p_{\underline x}}R(g)\quad[\text{bit/s}].}$$ Per un canale senza memoria con simboli indipendenti l'informazione mutua per simbolo è $I(x_n;y_n)$ e quindi $C=\max_{p_x}\frac{I(x;y)}T$.

Per un canale senza memoria il calcolo si riduce a una ricerca di massimo: si sceglie la densità d'ingresso $p_x$ che rende massima $I(x;y)=H(y)-H(y|x)$. Si procede così: (1) si trova $P_y$ in funzione di $p_x$ (formula delle probabilità totali, 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 →); (2) si calcola $H(y|x)=\sum_aP_x(a)H(y|x=a)$, che usa solo le righe della matrice del canale; (3) si massimizza.

Esempio (canale $M$-ario deterministico). Alfabeti $\mathcal A_x=\mathcal A_y=\{1,\dots,5\}$, con transizioni deterministiche: $1\to2$, $2\to4$, $3\to1$, $4\to1$, $5\to1$ (probabilità $1$).

• Con ingresso uniforme su $5$ simboli ($P_x=\frac15$): $P_y(1)=\frac35$, $P_y(2)=P_y(4)=\frac15$, gli altri $0$. Poiché il canale è deterministico $H(y|x)=0$ e $I(x;y)=H(y)=\frac15\log_25+\frac15\log_25+\frac35\log_2\frac53=1{,}371$ bit.
• Con ingresso uniforme sui soli simboli $\{1,2,3\}$ (probabilità $\frac13$) le uscite sono $2,4,1$, tutte diverse, quindi $H(y)=\log_23=1{,}585$ bit. Non si può fare meglio: $y$ assume solo $3$ valori ($1,2,4$), quindi $I(x;y)\le H(y)\le\log_23$. Dunque $C=\log_23=1{,}585$ bit per simbolo (cioè $\frac{\log_23}T$ bit/s), e si raggiunge usando un solo ingresso per ogni uscita distinta. L'ingresso uniforme su $5$ simboli, più "naturale", dà di meno.

Teorema di Shannon per la codifica di canale

Si considera un canale $M$-ario senza memoria con periodo di simbolo $T$ e capacità $C$ [bit/s]. Una sorgente di simboli emette un simbolo ogni $T_s$ su un alfabeto di $M_s$ simboli, quindi ha tasso nominale $R=\frac{\log_2M_s}{T_s}$.

$$\text{SORGENTE}\xrightarrow[T_s]{\ x,\ |\mathcal A_x|=M_s\ }\boxed{\text{COD}}\xrightarrow[T]{\ c,\ |\mathcal A_c|=M\ }\boxed{\text{CANALE (capacità }C)}\xrightarrow{\ \tilde c\ }\boxed{\text{DEC}}\xrightarrow{\ \hat x\ }$$

Teorema (Shannon).

1. Se $\boxed{R\le C}$, per ogni $\delta>0$ e per ogni $n$ abbastanza grande esistono: a) un codice di canale con parole lunghe $n$ e $2^{nRT}$ parole; b) un decodificatore con probabilità d'errore sulla parola $P[\underline c\ne\hat{\underline c}]<\delta$.
2. Se $\boxed{R>C}$ esiste un $\delta>0$ tale che ogni codice a correzione d'errore ha probabilità d'errore sulla parola $\ge\delta$.

Si legge così: sotto la capacità si può rendere l'errore piccolo a piacere usando parole lunghe (la lunghezza $n$ cresce quando $\delta$ diminuisce); sopra la capacità l'errore non si può eliminare qualunque sia il codice. Il teorema è di esistenza: non dice come costruire il codice.

Il caso binario. Se alfabeto sorgente e alfabeto del canale sono binari ($M_s=M=2$) il codice è un insieme di $2^k$ parole di lunghezza $n$ (un codice a blocco, Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P_{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico →). Dal teorema $2^k=2^{nRT}$, quindi $k=nRT$ e il rate del codice è $$\frac kn=RT\quad\text{con}\quad R=\frac1{T_s}\ \text{(un bit ogni }T_s\text{)}.$$ La condizione $R\le C$ diventa $$\boxed{\frac kn\le CT=\max_{p}I(c;\tilde c)\ \le1\ \text{bit.}}$$ Il rate di un codice sul canale è al più l'informazione mutua massima per uso del canale, a sua volta $\le1$ bit (il canale è binario). Questo numero, in bit per uso del canale, si chiama anche efficienza spettrale.

Come si usa negli esercizi. Per rispondere a "è possibile una codifica di canale con probabilità d'errore residua piccola a piacere?":

1. si calcola il tasso della sorgente (bit/s) che entra nel codificatore di canale;
2. si calcola la capacità del canale (bit/s);
3. si dice sì se tasso $\le C$, no se tasso $>C$.

Esempio. Una sorgente emette un simbolo ogni $20\ \mu$s con alfabeto $\{0,1,2\}$: $R=\frac{\log_23}{20\ \mu\text{s}}=79{,}25$ kbit/s. Un canale binario simmetrico con $P_{bit}=10^{-3}$ e periodo di bit $T=10\ \mu$s ha $C=\frac{1-h(10^{-3})}{T}=\frac{0{,}9886}{10\ \mu\text{s}}=98{,}86$ kbit/s $>79{,}25$ kbit/s: la codifica esiste. Con $T=15\ \mu$s sarebbe $C=65{,}9$ kbit/s e non esisterebbe.

Il tasso nominale è il caso peggiore. Se la sorgente ha entropia $H_s<\log_2M_s$ conviene prima ridurre il tasso con una codifica di sorgente (Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza mediaLa codifica di sorgente senza perdite associa a ogni parola emessa dalla sorgente una parola di codice binaria (o $M_y$-aria) di lunghezza variabile, in modo invertibile; la qualità si misura con la lunghezza media $L_y=\sum p_{\underline x}(\underline a),l(\underline a)$. In un codice a prefisso nessuna parola è l'inizio di un'altra, quindi la decodifica è istantanea. Kraft-McMillan: ogni codice decodificabile ha $\sum M_y^{-l_i}\le1$, e se interi $l_i$ la soddisfano esiste un codice a prefisso con quelle lunghezze. Shannon: $\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1$ per il codice a prefisso ottimo, con $L_y=\frac{H}{\log_2M_y}$ solo se le probabilità sono potenze di $\frac1{M_y}$.Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media →), e poi confrontare con $C$ il tasso dei bit che escono dal codificatore di sorgente, che si avvicina a $H_s/T_s$ (negli esercizi si indica quale dei due usare).

Capacità del canale AWGN

Per il canale AWGN con ingresso $s$ e uscita $r=s+w$, $w\sim\mathcal N(0,\sigma^2)$, simboli reali ($I=1$ dimensione), con energia di simbolo $E_s$ e periodo $T$:

$$\boxed{C=\frac{I}{2T}\log_2\left(1+\frac{E_s}{\sigma^2}\right)\ \text{[bit/s]}=\max_{p_s}\frac{I(r;s)}T,}\qquad\text{SNR}=\frac{E_s}{\sigma^2}.$$

Il massimo si ottiene con un ingresso gaussiano $s\sim\mathcal N(0,E_s)$, che è approssimato da una PAM con $M$ grande (e, in generale, da un codice con distribuzione "gaussiana" dei punti). Per $I$ dimensioni reali indipendenti, ciascuna con energia $E_s$ e rumore $\sigma^2$, le capacità si sommano e compare il fattore $I$. Per $I=1$ la capacità per uso è $\frac12\log_2(1+\text{SNR})$ bit.

Esempi. $\text{SNR}=15$: $\frac12\log_216=2$ bit per uso, quindi con $T=1\ \mu$s si ha $C=2$ Mbit/s. $\text{SNR}=10$ dB $=10$: $\frac12\log_211=1{,}730$ bit per uso. Raddoppiare l'SNR aumenta $C$ di meno di $\frac12$ bit per uso (il logaritmo cresce lentamente): per guadagnare $1$ bit per uso occorre quadruplicare circa l'SNR.

Capacità del canale binario simmetrico (BSC)

Un canale binario simmetrico senza memoria inverte ogni bit con probabilità $P_{bit}$, indipendentemente dagli altri:

Poiché il canale è senza memoria, $C=\max_{P_b}\frac{I(b;\hat b)}T$ con $I(b;\hat b)=H(\hat b)-H(\hat b|b)$.

1. $H(\hat b|b)$. Per ingresso $b=0$ l'uscita vale $0$ con probabilità $1-P_{bit}$ e $1$ con probabilità $P_{bit}$: $H(\hat b|b=0)=(1-P_{bit})\log_2\frac1{1-P_{bit}}+P_{bit}\log_2\frac1{P_{bit}}=h(P_{bit})$. Per $b=1$ è la stessa cosa. Quindi, qualunque sia $P_b$, $H(\hat b|b)=P_b(0)h(P_{bit})+P_b(1)h(P_{bit})=h(P_{bit})$: non dipende dall'ingresso.
2. Massimizzazione. Resta da rendere massima $H(\hat b)$, entropia di una variabile binaria, che vale al più $1$ bit con $P_{\hat b}(0)=P_{\hat b}(1)=0{,}5$. Con $P_b(0)=P_b(1)=0{,}5$ l'uscita è uniforme (formula delle probabilità totali: $P_{\hat b}(0)=0{,}5(1-P_{bit})+0{,}5P_{bit}=0{,}5$), quindi il massimo si raggiunge con ingresso uniforme.

$$\boxed{C=\frac1T\left[1-h(P_{bit})\right]=\frac1T\left[1+P_{bit}\log_2P_{bit}+(1-P_{bit})\log_2(1-P_{bit})\right].}$$

Valori. $P_{bit}=10^{-3}$: $C T=0{,}9886$; $10^{-2}$: $0{,}9192$; $0{,}1$: $0{,}5310$; $0{,}2$: $0{,}2781$; $0{,}5$: $0$. Un codice di rate $\frac12$ può riuscire solo se $P_{bit}\le0{,}110$. Con $T_b=1$ ms, $P_{bit}=0{,}1$ dà $C=531$ bit/s.

Esempio (canale binario non simmetrico). Un canale con $P_{y|x}(0|0)=P_{y|x}(0|1)=0{,}1$ e $P_{y|x}(1|0)=P_{y|x}(1|1)=0{,}9$ ($T=1$ s) è binario (ingresso e uscita a due valori) ma non simmetrico, perché il suo "errore" dipende dal simbolo. Per qualsiasi ingresso $P_x(0)=q$ si ha $P_y(0)=0{,}1q+0{,}1(1-q)=0{,}1$, costante: $H(y)=h(0{,}1)=0{,}469$ bit. Anche $H(y|x=0)=H(y|x=1)=h(0{,}1)$, quindi $I(x;y)=0{,}469-0{,}469=0$ per ogni $q$ e $C=0$. Le due righe della matrice sono uguali: l'uscita non dipende dall'ingresso, e l'informazione mutua è nulla. Un vero BSC con $P_{bit}=0{,}9$ avrebbe invece le righe $(0{,}1;\ 0{,}9)$ e $(0{,}9;\ 0{,}1)$, diverse tra loro, e capacità $1-h(0{,}9)=0{,}531$ bit per uso (basta invertire i bit in uscita): è la curva a "U" della capacità, che vale di nuovo $1$ a $P_{bit}=1$.

Capacità del canale con cancellazione

Un canale con ingresso binario $\{0,1\}$ e uscita ternaria $\{0,E,1\}$: con probabilità $1-\alpha$ il bit arriva corretto, con probabilità $\alpha$ viene cancellato (il ricevitore sa che l'ha perso e non ne conosce il valore, $E$ = erasure). È un canale senza memoria con matrice $P_{y|x}$ (righe: ingressi $0,1$; colonne: uscite $0,E,1$):

Si pone $P_x(0)=\gamma$.

1. Uscita. $P_y(0)=(1-\alpha)\gamma$, $P_y(1)=(1-\alpha)(1-\gamma)$, $P_y(E)=\alpha\gamma+\alpha(1-\gamma)=\alpha$.
2. $H(y)$. $H(y)=(1-\alpha)\gamma\log_2\frac1{(1-\alpha)\gamma}+(1-\alpha)(1-\gamma)\log_2\frac1{(1-\alpha)(1-\gamma)}+\alpha\log_2\frac1\alpha$. Usando $\log_2\frac1{(1-\alpha)\gamma}=\log_2\frac1{1-\alpha}+\log_2\frac1\gamma$ e raccogliendo, i termini con $\log_2\frac1{1-\alpha}$ si sommano in $(1-\alpha)\log_2\frac1{1-\alpha}$ (perché $\gamma+(1-\gamma)=1$) e resta $(1-\alpha)h(\gamma)$: $$H(y)=(1-\alpha)h(\gamma)+h(\alpha).$$
3. $H(y|x)$. Per $x=0$ l'uscita vale $0$ con probabilità $1-\alpha$ e $E$ con probabilità $\alpha$: $H(y|x=0)=h(\alpha)$. Lo stesso per $x=1$ (uscite $1$ ed $E$). Quindi $H(y|x)=h(\alpha)$, indipendente da $P_x$.
4. Massimizzazione. $I(x;y)=(1-\alpha)h(\gamma)+h(\alpha)-h(\alpha)=(1-\alpha)h(\gamma)$, massima per $\gamma=\frac12$ ($h=1$):

$$\boxed{C=\frac{1-\alpha}T\ \text{bit/s}.}$$

È la frazione di bit che arriva: $\alpha=0$ è il canale binario ideale ($C=\frac1T$), $\alpha=1$ cancella tutto ($C=0$). Per $\alpha=0{,}2$ e $T=1$ ms: $C=800$ bit/s.

Confronto. A parità di probabilità $0{,}1$ la cancellazione lascia $C T=0{,}9$ e il BSC $0{,}531$: sapere dove sono i bit persi vale molto di più che non sapere dove sono gli errori.

Canali in parallelo e canali alternati

Un canale i cui bit pari e dispari hanno statistiche diverse si studia come due canali in parallelo, ciascuno usato una volta ogni $2T_b$. Esempio (lezione): bit trasmessi ogni $T_b=1$ ms, errori indipendenti con probabilità $P_P$ ai tempi pari e $P_D$ ai tempi dispari.

1. Quando è un BSC senza memoria? Quando ogni bit ha la stessa probabilità d'errore: $P_P=P_D$ (qualunque ne sia il valore). Con $P_P\ne P_D$ gli errori dipendono dal tempo, quindi non è un BSC.
2. Capacità con $P_P=P_D=0{,}1$: $C=\frac{1-h(0{,}1)}{T_b}=531$ bit/s.
3. Probabilità d'errore media con $P_P=0{,}1$, $P_D=0{,}2$: metà dei bit ha $0{,}1$ e metà $0{,}2$, quindi $P(E)=\frac{0{,}1+0{,}2}2=0{,}15$ Questa è solo la probabilità d'errore media: la capacità non si ricava da essa, ma si ragiona sui due canali separati (punto 4).
4. Capacità con $P_P=0{,}1$ e $P_D=0$. Due canali paralleli, ciascuno con periodo di simbolo $2T_b$: il pari è un BSC con $P_{bit}=0{,}1$ e capacità $C_P=\frac{0{,}531}{2T_b}=265{,}5$ bit/s; il dispari non ha errori e $C_D=\frac1{2T_b}=500$ bit/s. La capacità del canale complessivo è la somma: $C_{\text{tot}}=C_P+C_D=765{,}5$ bit/s (maggiore dei $531$ bit/s del canale con $0{,}1$ su tutti i bit, e minore dei $1000$ bit/s del canale ideale). Si usa un codificatore e un decodificatore separati per ciascun canale.

Questo ragionamento è svolto per esteso, con le domande del tema d'esame, in Esercizio - canale binario con errori diversi sui bit pari e dispari (compito del 25 giugno 2024, es. 179).

Errori comuni

• Scrivere la capacità del BSC come $1-P_{bit}$: è $1-h(P_{bit})$, con l'entropia binaria.
• Dimenticare di dividere per $T$ (o per $2T_b$ nei canali in parallelo) quando la capacità è richiesta in bit/s.
• Dire che con un canale non simmetrico serve $P_x$ uniforme: l'ingresso uniforme massimizza l'informazione mutua solo per i canali simmetrici o a cancellazione; in generale si massimizza $H(y)-H(y|x)$ su $P_x$ (nell'esempio deterministico a $5$ ingressi l'uniforme non è ottima).
• Confondere tasso nominale e tasso d'informazione, o scordare il tasso del codificatore di canale: il confronto con $C$ si fa sui bit che entrano nel codificatore.
• Usare $\frac1T\log_2(1+\text{SNR})$ per il canale AWGN reale: per un simbolo a una dimensione c'è un fattore $\frac12$.
• Calcolare la capacità di canali in parallelo come la media delle capacità senza dividere per il numero di canali, o senza considerare che ciascuno è usato la metà delle volte.

Domande d'esame

1. Si enunci il teorema di Shannon per la codifica di canale. Tasso nominale $R=\frac{\log_2M_s}{T_s}$ e canale di capacità $C$: se $R\le C$ per ogni $\delta>0$ e $n$ grande esistono un codice con $2^{nRT}$ parole lunghe $n$ e un decodificatore con probabilità d'errore sulla parola $<\delta$; se $R>C$ ogni codice ha probabilità d'errore $\ge\delta>0$.
2. Si calcoli la capacità del canale binario simmetrico. $H(\hat b|b)=h(P_{bit})$ non dipende dall'ingresso, $H(\hat b)\le1$ con uguaglianza per ingresso uniforme: $C=\frac{1-h(P_{bit})}T$.
3. Si calcoli la capacità del canale binario con cancellazione di probabilità $\alpha$. $H(y)=(1-\alpha)h(\gamma)+h(\alpha)$, $H(y|x)=h(\alpha)$, massimo con $\gamma=\frac12$: $C=\frac{1-\alpha}T$.

Esercizi svolti

• Esercizio - canale binario con errori diversi sui bit pari e dispari (compito del 25 giugno 2024, es. 179): canale con errori diversi sui bit pari e dispari, canali in parallelo e capacità $765{,}5$ bit/s.
• Esercizio - canale binario non simmetrico, informazione mutua, Huffman ed Elias sulle coppie e canale a cancellazione (compito del 10 febbraio 2021, es. 123): canale non simmetrico, ingresso che massimizza $H(y)$ e canale a cancellazione.
• Esercizio - canale binario con rumore aleatorio, capacità e Huffman sulle triplette (secondo compitino dell'11 gennaio 2019, es. 90): canale con rumore aleatorio che diventa un BSC con errore $0{,}34$.
• Esercizio - entropia, Kraft-McMillan ternario, Huffman e capacità di due canali binari in cascata (secondo compitino del 14 gennaio 2025, es. 186): massimo di $H(Y|X)$, BSC con $a=b$ e cascata di due BSC.
• Esercizio - capacità di un canale 4-PSK, entropia di un codice a blocco, distanza minima e decodifica (compito dell'11 febbraio 2025, es. 192): condizione di Shannon con una 4-PSK, rate e decodifica di un codice a blocco.
• Esercizio - Kraft-McMillan, Huffman, due canali binari alternati e codice di Hamming (15,11) (compito del 13 febbraio 2026, es. 201): massimo periodo di bit per due BSC alternati (con la correzione della soluzione del corso).
• Esercizio - rate di informazione, codice di Hamming (7,4) e capacità del canale binario simmetrico (compito del 6 luglio 2026, es. 204): rate di informazione, periodo massimo con $P_{bit}=10^{-4}$ e Hamming $(7,4)$.
• Esercizio - Huffman, codice di Shannon, funzione deterministica di una sorgente e informazione mutua di un canale (secondo compitino del 9 gennaio 2026, es. 196): informazione mutua di un canale con ingresso uniforme e capacità numerica.