FormularioTelecommunications: definizioni, teoremi e formule delle note, in ordine di capitolo

In questa pagina 7

1. Introduzione

Introduzione alle reti di telecomunicazione

Definizione (telecomunicazione). Un servizio di telecomunicazione (telefonata, e-mail, televisione, navigazione web) è realizzato da un sistema che trasporta informazione da una sorgente a una destinazione poste a distanza. Coinvolge tre entità: il trasmettitore (sorgente, mittente, Tx), il canale (portante, mezzo trasmissivo: cavo, fibra, spazio libero) e il ricevitore (destinazione, utente, terminale, Rx).

Esempio. In una telefonata la voce (sorgente) è convertita in bit e trasmessa (Campionamento e conversione analogico-digitale), il canale è il cavo o il collegamento radio che attenua e aggiunge rumore (Mezzi trasmissivi - cavi, fibre e radio), il ricevitore ricostruisce il segnale.

Definizione (rete di telecomunicazioni). Insieme non isolato di sistemi in cui i ruoli (trasmettitore, ricevitore) degli utenti possono cambiare. Una volta ogni servizio aveva una rete dedicata (rete telefonica POTS, plain old telephone service, per la voce); le reti moderne sono integrate: una sola infrastruttura porta più servizi, voce e dati (ISDN, integrated services digital network, e poi Internet).

Definizione (grafo di una rete). I nodi (nodes) sono gli utenti o i dispositivi che comunicano; gli archi (collegamenti, links, hops) sono i canali, orientati (unidirezionali) o no.

Definizione (protocollo). Insieme di regole su cui gli utenti devono accordarsi per interagire, realizzate tramite lo scambio di dati di controllo.

Esempio. Un messaggio di $1000$ bit scende dal livello 4 al livello 2 con intestazioni di $20$ , $20$ e $14$ bit: sul filo viaggia una PDU da $1000+20+20+14=1054$ bit ( $5{,}4\%$ di overhead); il ricevitore toglie le intestazioni in ordine inverso.

Segnali, potenza e decibel

Definizione (decibel). Per un rapporto di potenze $A=\frac{P_1}{P_2}$ (con $P_1,P_2>0$ ): $[A]_{dB}=10\log_{10}A,\qquad A=10^{[A]_{dB}/10}.$ Per un rapporto di ampiezze (tensioni o correnti) $R=\frac{X_1}{X_2}$ , poiché la potenza è il "segnale al quadrato" ( $P=X^2$ ): $[R]_{dB}=10\log_{10}R^2=20\log_{10}R.$

Esempio. $A=10\to10$ dB; $A=100\to20$ dB; $A=1000\to30$ dB; $A=0{,}1\to-10$ dB; $A=0{,}01\to-20$ dB. Una tensione che raddoppia ( $R=2$ ) fa $20\log_{10}2=6{,}02$ dB, una potenza che raddoppia fa $10\log_{10}2=3{,}01$ dB.

Definizione (supporto, durata, banda). Il supporto è l'insieme dei tempi in cui $x(t)\neq0$ e la durata è la sua misura. La banda completa $\mathcal B$ è l'insieme delle frequenze in cui $X(f)\neq0$ ; la banda si restringe alle frequenze $f\ge0$ e la larghezza di banda $B$ è la sua misura. Per un segnale reale $\lvert X(f)\rvert$ è pari, quindi la banda completa è doppia della banda.

Esempio. $x(t)=\operatorname{rect}\left(\frac tT\right)$ ha supporto $\left[-\frac T2,\frac T2\right]$ e durata $T$ . La sua trasformata è $X(f)=T\operatorname{sinc}(fT)$ (con $\operatorname{sinc}(u)=\frac{\sin\pi u}{\pi u}$ ), diversa da zero per quasi tutte le $f$ : la banda formale è infinita.

Grafico interattivo: Modulo dello spettro del rettangolo di durata T, |X(f)|/X(0) = |sinc(fT)|, in funzione di fT: il primo zero è in fT = 1; la banda a 3 dB (soglia 0,7071) finisce in fT = 0,443, quella a 20 dB (soglia 0,1) in fT = 0,908

Definizione (energia e potenza). L'energia di $x(t)$ è $\mathcal E_x=\int_{-\infty}^{+\infty}\lvert x(t)\rvert^2dt$ (unità: V $^2\cdot$ s, non joule: è un'energia "normalizzata" a una resistenza di $1\ \Omega$ ). La potenza media è $M_x=\lim_{T\to\infty}\frac1{2T}\int_{-T}^{T}\lvert x(t)\rvert^2dt$ (unità: V $^2$ ).

Teorema (Parseval). $\displaystyle\mathcal E_x=\int\lvert x(t)\rvert^2dt=\int\lvert X(f)\rvert^2df$ . La funzione $\mathcal E_x(f)=\lvert X(f)\rvert^2$ è la densità spettrale di energia: l'energia contenuta in una banda si ottiene integrandola. Vedi Segnali - supporto, area, valor medio, energia e potenza.

Esempio. Il rettangolo $x(t)=A\operatorname{rect}\left(\frac tT\right)$ con $A=2$ V e $T=1$ ms. Nel tempo: $\mathcal E_x=A^2T=4\cdot10^{-3}\ \text{V}^2\text{s}$ . In frequenza: $X(f)=AT\operatorname{sinc}(fT)$ e $\int A^2T^2\operatorname{sinc}^2(fT)df=A^2T$ (si usa $\int\operatorname{sinc}^2(u)du=1$ ): stesso valore. Il lobo principale, cioè la banda di primo zero $\lvert f\rvert<\frac1T$ , contiene il $90{,}3\%$ dell'energia (calcolo numerico: $2\int_0^1\operatorname{sinc}^2u\,du=0{,}9028$ ).

Definizione (media, potenza, autocorrelazione). $m_x(t)=E[x_\omega(t)],\qquad M_x(t)=E\left[\lvert x_\omega(t)\rvert^2\right],\qquad r_x(t,\tau)=E\left[x_\omega(t)\,x_\omega^*(t-\tau)\right].$ Sono tre funzioni deterministiche: la media a ogni $t$ è la media sulle realizzazioni (non è la media nel tempo di una realizzazione); la potenza è $M_x(t)=r_x(t,0)$ ; l'autocorrelazione descrive quanto sono legati i valori a distanza $\tau$ (Valore atteso, Covarianza e coefficiente di correlazione).

Esempio. $x_\omega(t)=A\cos(2\pi f_0t+\Theta)$ con $\Theta$ uniforme in $[0,2\pi)$ : $m_x(t)=A\cdot E[\cos(2\pi f_0t+\Theta)]=0$ e $M_x(t)=A^2E[\cos^2(\cdot)]=\frac{A^2}2$ , costanti nel tempo.

Definizione (densità spettrale di potenza). Per un processo WSS la PSD è la trasformata dell'autocorrelazione: $\mathcal P_x(f)=\mathcal F[r_x(\tau)]$ . Vale $\int\mathcal P_x(f)\,df=r_x(0)=M_x$ : la PSD dice come la potenza si distribuisce sulle frequenze, e $\int_{f_1}^{f_2}\mathcal P_x(f)\,df$ è la potenza nella banda $[f_1,f_2]$ . Per un processo reale è pari.

Esempio. Rumore bianco: $r_x(\tau)=\frac{N_0}2\delta(\tau)\Rightarrow\mathcal P_x(f)=\frac{N_0}2$ costante; filtrato in una banda $[-B,B]$ ha potenza $\frac{N_0}2\cdot2B=N_0B$ (da cui il fattore $\frac{N_0}2$ : è la densità bilatera).

Teorema (filtraggio di un processo WSS). Se $x(t)$ è WSS e passa in un sistema LTI con risposta impulsiva $g(t)$ e risposta in frequenza $G(f)$ , anche $y=g*x$ è WSS (e $x,y$ sono congiuntamente WSS) con $m_y=m_xG(0),\qquad r_y=\bar g*g*r_x,\ (\bar g(t)=g(-t)),\qquad\mathcal P_y(f)=\lvert G(f)\rvert^2\mathcal P_x(f).$ Si calcola quindi la potenza in uscita come $M_y=\int\lvert G\rvert^2\mathcal P_x\,df$ .

Esempio. $x$ ha PSD $\mathcal P_x(f)=\frac{N_0}2$ e entra in un passa-basso ideale $G(f)=\operatorname{rect}\left(\frac f{2B}\right)$ : $\mathcal P_y(f)=\frac{N_0}2\operatorname{rect}\left(\frac f{2B}\right)$ e $M_y=N_0B$ . Se il guadagno in banda è $G_0=0{,}5$ in ampiezza, cioè $20\log_{10}0{,}5=-6{,}02$ dB, la potenza si moltiplica per $G_0^2=0{,}25$ , che in potenza è $10\log_{10}0{,}25=-6{,}02$ dB: lo stesso numero di dB, come deve essere per la definizione $20\log_{10}$ per le ampiezze.

Teorema (Jensen). Sia $x$ una variabile aleatoria non quasi certamente costante a valori in un intervallo $J$ e $h$ strettamente concava in $J$ . Allora $E[h(x)]<h(E[x])$ (per $h$ strettamente convessa vale $E[h(x)]>h(E[x])$ ), purché i valori attesi esistano. "Quasi certamente (a.s.)" vuol dire con probabilità 1: per esempio $x$ vale una costante con probabilità 1.

Esempio. $h(t)=\log_2t$ è strettamente concava. Con $x\in\{1,4\}$ equiprobabile: $E[h(x)]=\frac12(0+2)=1$ , mentre $h(E[x])=\log_2 2{,}5=1{,}32$ ; infatti $1<1{,}32$ . Vedi Disuguaglianze di Markov, Chebyshev e Jensen.

2. Sorgenti di informazione

Campionamento e conversione analogico-digitale

Definizione (convertitore A/D). Dal segnale analogico $a(t)$ si ottiene un flusso di bit con questi blocchi in cascata:

filtro anti-aliasing (passa-basso, si veda il §4);

campionatore: preleva $a(nT_s)$ a istanti multipli del periodo di campionamento $T_s$ ; la frequenza di campionamento (o symbol rate) è $F_s=\frac1{T_s}$ campioni al secondo;

quantizzatore $Q$ : associa a ogni campione un valore $a_q(nT_s)$ preso da un insieme finito di $L$ livelli $\mathcal A_q=\{Q_1,\dots,Q_L\}$ ;

bitmap inversa e serializzatore (P/S): ogni livello è rappresentato con una parola di $b$ bit, con $L=2^b$ cioè $b=\log_2L$ , e le parole si mettono in fila.

Esempio. Con $L=8$ livelli servono $b=\log_28=3$ bit per campione, e la bitmap associa $000,001,\dots,111$ agli 8 livelli. Non è obbligatorio che $L$ sia una potenza di 2, ma lo si sceglie così: con $L=6$ servirebbero comunque $\lceil\log_26\rceil=3$ bit e due parole di codice sarebbero sprecate.

Teorema (campionamento). Sia $a(t)$ un segnale a banda limitata, con $A(f)=0$ per $\lvert f\rvert>B$ . Se $F_s=\frac1{T_s}\ge2B$ allora $a(t)$ si ricostruisce esattamente dai campioni $a(nT_s)$ con un filtro interpolatore di risposta in frequenza $G(f)=\begin{cases}T_s&\lvert f\rvert<B\\\text{qualsiasi}&B\le\lvert f\rvert\le F_s-B\\0&\lvert f\rvert>F_s-B\end{cases}$ La frequenza $2B$ è la frequenza di Nyquist (o Nyquist rate), la minima possibile.

Esempio (aliasing). Un tono a $6$ kHz campionato a $F_s=8$ kHz ha campioni $\cos\left(2\pi\frac6{8}n\right)=\cos\left(2\pi\left(1-\frac28\right)n\right)=\cos\left(2\pi\frac28n\right)$ , identici a quelli di un tono a $2$ kHz: il ricevitore non può distinguere i due e ricostruirebbe $2$ kHz. In generale una frequenza $f_0>\frac{F_s}2$ si "ripiega" su $\lvert f_0-kF_s\rvert$ con $k$ intero più vicino. Per un segnale di banda $B=3$ kHz, tra $F_s=1$ , $2$ e $8$ kHz l'unica scelta valida è $F_s=8$ kHz perché solo $8\ge2B=6$ .

Grafico interattivo: Spettro del segnale campionato (triangolo di banda B = 1) con F_s = 3B ≥ 2B: le copie centrate nei multipli di 3 sono separate e un passa-basso con taglio tra B = 1 e F_s − B = 2 recupera il triangolo centrale

Quantizzazione e rumore di quantizzazione

Definizione (quantizzatore). Un quantizzatore è una funzione $Q:\mathbb R\to\mathcal A_q=\{Q_1,\dots,Q_L\}$ che a ogni campione $a(nT_s)$ associa un livello $a_q(nT_s)=Q(a(nT_s))$ . Si divide $\mathbb R$ in $L$ regioni disgiunte $\mathcal R_1,\dots,\mathcal R_L$ separate da $L-1$ soglie $v_2<\dots<v_L$ ; il campione in $\mathcal R_j$ diventa $Q_j$ . Si prende $L=2^b$ con $b$ bit per campione.

Esempio. Le soglie $v=\{-1,0,1\}$ dividono $\mathbb R$ in quattro regioni $(-\infty,-1)$ , $(-1,0)$ , $(0,1)$ , $(1,+\infty)$ ; con i livelli $\{-1{,}5,-0{,}5,0{,}5,1{,}5\}$ il campione $0{,}3$ diventa $0{,}5$ e il campione $-4$ diventa $-1{,}5$ . Si lavora con $L=4$ , quindi $b=2$ bit.

Definizione (quantizzatore uniforme e mid-riser). Il quantizzatore uniforme (PCM, pulse code modulation) ha tutte le regioni interne di ampiezza uguale $\Delta$ (il passo di quantizzazione). Si sceglie il range dinamico $[-v_{sat},v_{sat}]$ ( $v_{sat}$ è la tensione di saturazione) e si divide in $L$ passi: $\boxed{\Delta=\frac{2v_{sat}}{L}=\frac{2v_{sat}}{2^b}},\qquad v_{sat}=2^{b-1}\Delta.$ Nel tipo mid-riser ("la scala sale in zero") le soglie sono i multipli di $\Delta$ (che sono i multipli pari di $\frac\Delta2$ ) e i livelli sono i punti centrali delle regioni, cioè i multipli dispari di $\frac\Delta2$ : $Q_j=\pm\frac\Delta2,\ \pm\frac{3\Delta}2,\ \dots,\ \pm\frac{(L-1)\Delta}2,\qquad\text{soglie }0,\pm\Delta,\pm2\Delta,\dots,\pm\left(\tfrac L2-1\right)\Delta.$ Nel mid-tread invece il valore $0$ è un livello e i livelli sono $0,\pm\Delta,\pm2\Delta,\dots$ . Negli esercizi si usa il mid-riser.

Esempio. $L=8$ ( $b=3$ ) e $v_{sat}=4$ V: $\Delta=\frac{2\cdot4}{8}=1$ V; livelli $\pm0{,}5,\ \pm1{,}5,\ \pm2{,}5,\ \pm3{,}5$ V; soglie $-3,-2,-1,0,1,2,3$ V. L'ingresso $1{,}2$ V cade tra le soglie $1$ e $2$ e diventa $1{,}5$ V (errore $+0{,}3$ V); l'ingresso $-5$ V è oltre la soglia $-3$ V, quindi satura nel livello $-3{,}5$ V (errore $+1{,}5$ V). Non si trova mai il livello $0$ .

Grafico interattivo: Caratteristica del quantizzatore uniforme mid-riser con L = 8 livelli e v_sat = 4 V (Δ = 1 V): 8 gradini larghi 1 V con livelli ±0,5, ±1,5, ±2,5, ±3,5 V; oltre ±3 V l'uscita non cresce più (saturazione). La retta a_q = a sarebbe il caso ideale

Definizione (errore e rumore di quantizzazione). $e_q(nT_s)=a_q(nT_s)-a(nT_s)$ , quindi $a_q=a+e_q$ : all'uscita c'è il segnale più un "rumore" additivo, come se l'errore fosse introdotto dal canale.

Esempio. Con $\Delta=1$ V (esempio sopra) $M_{e_q}=\frac1{12}=0{,}0833$ V $^2$ , errore efficace $\sqrt{0{,}0833}=0{,}289$ V, che è $\frac{\Delta}{\sqrt{12}}$ e non $\frac\Delta2$ (l'errore massimo): la media del quadrato è minore del quadrato del massimo.

Grafico interattivo: Errore e_q = a_q − a del quantizzatore mid-riser con Δ = 1 V e v_sat = 4 V: dente di sega di ampiezza ±0,5 V (errore granulare) per |a| < 4 V, poi una retta che cresce senza limite (errore di saturazione)

Definizione (SNR di quantizzazione). $\Lambda_q=\frac{E\left[a(nT_s)^2\right]}{E\left[e_q(nT_s)^2\right]}=\frac{M_a}{M_{e_q}},\qquad[\Lambda_q]_{dB}=10\log_{10}\Lambda_q.$ Con segnale a media nulla $M_a=\sigma_a^2$ (varianza); in generale $M_a=\sigma_a^2+m_a^2$ . Più è alto, più il segnale quantizzato è fedele.

Esempio. Segnale con $\sigma_a^2=2$ V $^2$ e rumore $M_{e_q}=0{,}002$ V $^2$ : $\Lambda_q=1000$ , cioè $30$ dB.

Grafico interattivo: SNR di quantizzazione in dB in funzione dei bit b per un segnale gaussiano con v_sat = 4σ (P_sat = 6,3·10⁻⁵): 6,02·b + 4,77 − 12,04, una retta di pendenza 6 dB per bit

Informazione, entropia e informazione mutua

Definizione (informazione). $\displaystyle i(A)=\log_2\frac1{P(A)}$ bit (con $\ln$ si avrebbe il nat). Per la sorgente, $i_x(a)=\log_2\frac1{p_x(a)}$ .

Esempio. L'estrazione del seme di una carta (cuori, quadri, fiori, picche, equiprobabili con $P=\frac14$ ) ha informazione $\log_24=2$ bit; scoprire una carta precisa su 52 vale $\log_252=5{,}70$ bit; un evento certo vale $0$ bit, la testa di una moneta equa $1$ bit.

Definizione (entropia). L'entropia di una variabile aleatoria discreta $x$ è l'informazione media (il valore atteso di $i_x(x)$ ): $\boxed{H(x)=E\left[\log_2\frac1{p_x(x)}\right]=\sum_{a\in\mathcal A_x}p_x(a)\log_2\frac1{p_x(a)}}\quad[\text{bit}].$ Per i termini con $p=0$ si pone $0\cdot\log_2\frac10=0$ (è il limite, si veda sotto).

Esempio. $p=0{,}1$ : $H=0{,}1\log_210+0{,}9\log_2\frac1{0{,}9}=0{,}332+0{,}137=0{,}469$ bit. Una moneta truccata al 90% dà meno di mezzo bit per lancio.

Grafico interattivo: Entropia di una sorgente binaria H(p): massimo 1 bit per p = 1/2 (incertezza massima), zero per p = 0 e p = 1 (esito certo); H(0,1) = 0,469 bit, H(0,2) = 0,722 bit

Teorema (limiti dell'entropia). Se la sorgente ha $M$ simboli:

$H(x)=0$ se e solo se $x$ è quasi certamente (a.s.) costante (un simbolo ha probabilità 1, gli altri 0); altrimenti $H(x)>0$ .

$H(x)\le\log_2M$ , con uguaglianza se e solo se i simboli sono equiprobabili.

Esempio. Probabilità $0{,}35,\ 0{,}22,\ 0{,}20,\ 0{,}13,\ 0{,}10$ : $H=0{,}35\log_2\frac1{0{,}35}+0{,}22\log_2\frac1{0{,}22}+0{,}20\log_2\frac1{0{,}20}+0{,}13\log_2\frac1{0{,}13}+0{,}10\log_2\frac1{0{,}10}=0{,}530+0{,}481+0{,}464+0{,}383+0{,}332=2{,}19$ bit, contro $\log_25=2{,}32$ del caso equiprobabile.

Teorema (entropia congiunta).

Se $y=f(x)$ (dipendenza deterministica) $H(x,y)=H(x)$ ; altrimenti $H(x,y)>H(x)$ . Per simmetria vale lo stesso scambiando i ruoli, quindi $H(x,y)\ge\max\{H(x),H(y)\}$ .

Se $x$ e $y$ sono indipendenti, $H(x,y)=H(x)+H(y)$ ; altrimenti $H(x,y)<H(x)+H(y)$ .

In sintesi $\max\{H(x),H(y)\}\le H(x,y)\le H(x)+H(y)$ .

Esempio. $x$ uniforme in $\{0,1,2\}$ e $y=(x-1)^2$ (cioè $y=1,0,1$ ): le coppie possibili sono $(0,1),(1,0),(2,1)$ ciascuna di probabilità $\frac13$ , quindi $H(x,y)=\log_23=1{,}585=H(x)$ : conoscere $x$ determina $y$ . Invece per $x,y$ indipendenti con $p_x=(\frac12,\frac12)$ e $p_y=(\frac14,\frac34)$ : $H(x,y)=H\left(\frac18,\frac38,\frac18,\frac38\right)=1{,}811=1+0{,}811=H(x)+H(y)$ .

Definizione (entropia condizionata). $H(x|y)=E\left[i_{x|y}(x|y)\right]=\sum_{a}\sum_{b}p_{xy}(a,b)\log_2\frac1{p_{x|y}(a|b)}.$ Dice quanta informazione si guadagna in media scoprendo $x$ quando già si conosce $y$ (l'incertezza su $x$ che resta dopo aver visto $y$ ).

Teorema. (a) $H(x|y)=H(x,y)-H(y)$ . (b) $0\le H(x|y)\le H(x)$ : vale $0$ se $x$ è funzione di $y$ e vale $H(x)$ se e solo se $x$ e $y$ sono indipendenti.

Esempio. Nel caso $y=(x-1)^2$ con $x$ uniforme in $\{0,1,2\}$ : $H(y)=H\left(\frac13,\frac23\right)=0{,}918$ bit, quindi $H(x|y)=1{,}585-0{,}918=0{,}667$ bit (se $y=0$ si sa che $x=1$ ; se $y=1$ resta incerto tra $0$ e $2$ , con probabilità $\frac23$ : $\frac23\cdot1=0{,}667$ ) e $H(y|x)=H(x,y)-H(x)=0$ .

Definizione (informazione mutua). $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)=H(y)-H(y|x).$ È simmetrica ( $I(x;y)=I(y;x)$ ) e vale $0\le I(x;y)\le\min\{H(x),H(y)\}$ : è zero se e solo se $x$ e $y$ sono indipendenti (conoscere $y$ non dice nulla su $x$ ), ed è $H(x)$ se $x$ è una funzione di $y$ .

Esempio. Joint $p_{xy}=\begin{pmatrix}0{,}4&0{,}1\\0{,}1&0{,}4\end{pmatrix}$ (due bit che coincidono col 80%): $H(x)=H(y)=1$ , $H(x,y)=1{,}722$ , quindi $H(x|y)=0{,}722$ e $I(x;y)=1-0{,}722=0{,}278$ bit. Per l'esempio $y=(x-1)^2$ : $I=H(y)-H(y|x)=0{,}918-0=0{,}918$ bit, che è anche $H(x)-H(x|y)=1{,}585-0{,}667$ . Questa grandezza è quella che il canale riesce a trasportare (Capacità di canale) e quella che misura la qualità di una previsione (Esercizio - il meteorologo, entropia e informazione mutua).

Definizione (entropia per simbolo, rate, efficienza). Si definisce $H_s(\vec x)=\frac{H(\vec x)}N\le\log_2M$ (media "per simbolo", non valore atteso statistico). Se la sorgente emette $F_s$ simboli al secondo:

bit-rate nominale $R_b=F_s\log_2M$ (si usano $\log_2M$ bit per simbolo senza codifica);

rate di informazione $R_0=F_sH_s(\vec x)\le R_b$ (bit di informazione davvero prodotti);

efficienza $\eta_x=\frac{H_s(\vec x)}{\log_2M}\le1$ e ridondanza $1-\eta_x$ .

Esempio. $M=4$ con $p=\left(\frac12,\frac14,\frac18,\frac18\right)$ : $H=\frac12+\frac24+\frac38+\frac38=1{,}75$ bit. Con $F_s=1000$ simboli/s: $R_b=2000$ bit/s, $R_0=1750$ bit/s, $\eta=\frac{1{,}75}2=0{,}875$ , ridondanza $12{,}5\%$ .

Codifica di sorgente

Definizione (codice di sorgente). Una sorgente emette parole $\vec x$ di $N$ simboli (dizionario di ingresso $\mathcal D_x$ , entropia $H(\vec x)$ ). Una mappa $\mu_s:\mathcal D_x\to\mathcal C$ associa a ogni parola una parola di codice $\vec b$ scritta con un alfabeto di $M$ simboli (alfabeto binario: $M=2$ ), e deve essere invertibile (diversamente si perderebbe informazione). $L(\vec b)$ è la lunghezza di $\vec b$ ; la lunghezza media è $\tilde L=E\left[L(\vec b)\right]=\sum_{\vec b\in\mathcal C}P(\vec b)\,L(\vec b),$ cioè il valore atteso della lunghezza, vista come variabile aleatoria che dipende dalla parola emessa; e l'efficienza del codice è $\eta=\frac{H(\vec x)}{\tilde L\,\log_2M}$ (per un codice binario $\eta=\frac{H}{\tilde L}$ ).

Esempio. $M=8$ simboli equiprobabili: $H=3$ bit e a lunghezza fissa 3 bit: la codifica non può migliorare ( $\eta=1$ ). Se invece le probabilità sono $\left(\frac12,\frac14,\frac18,\frac18\right)$ , la lunghezza fissa usa 2 bit e $H=1{,}75$ : c'è margine per risparmiare $12{,}5\%$ .

Definizione (decodificabile, a prefisso). Un codice è univocamente decodificabile se due sequenze diverse di parole di codice non danno mai la stessa stringa di bit. Una parola $\vec b$ è prefisso di $\vec b'$ se $L(\vec b)<L(\vec b')$ e $\vec b$ coincide con i primi $L(\vec b)$ simboli di $\vec b'$ . Un codice è a prefisso se nessuna sua parola è prefisso di un'altra.

Esempio. Con $A\to0,\ B\to1,\ C\to01,\ D\to10$ la stringa $0101001101101$ è ambigua ( $0\,1\,0\,1\dots$ = $ABAB\dots$ ma anche $01\,01\dots=CC\dots$ ): il codice non è decodificabile. Con $A\to0,\ B\to10,\ C\to110,\ D\to111$ (a prefisso) la stringa $0\,10\,110\,111\,0$ si legge in un solo modo.

Teorema (Kraft-McMillan). Sia $\mathcal C$ un codice con alfabeto di $M$ simboli e parole di lunghezze $l_1,\dots,l_K$ .

Se $\mathcal C$ è decodificabile, allora $\displaystyle\sum_{i=1}^K\frac1{M^{l_i}}\le1$ (equivalentemente $E\left[\frac1{M^{L(\vec b)}P(\vec b)}\right]\le1$ ).

Viceversa, se $l_1,\dots,l_K$ sono interi con $\sum_iM^{-l_i}\le1$ esiste un codice a prefisso con alfabeto $M$ e quelle lunghezze.

Esempio. Le lunghezze $1,2,3,3$ danno $\frac12+\frac14+\frac18+\frac18=1\le1$ : esiste un codice a prefisso binario (quello dell'esempio sopra con $B\to10$ , $C\to110$ , $D\to111$ ). Le lunghezze $2,2,3,3,3,3,4,4$ (otto parole) danno $2\cdot\frac14+4\cdot\frac18+2\cdot\frac1{16}=\frac12+\frac12+\frac18=\frac98>1$ : nessun codice decodificabile ha queste lunghezze.

Teorema (Shannon). Sia $\mathcal C$ un codice con alfabeto di $M$ simboli per parole $\vec x$ di entropia $H(\vec x)$ .

Se $\mathcal C$ è decodificabile, $\displaystyle\tilde L\ge\frac{H(\vec x)}{\log_2M}$ .

Esiste un codice a prefisso con $\displaystyle\tilde L<\frac{H(\vec x)}{\log_2M}+1$ . Corollario ( $M=2$ ): $\tilde L=H(\vec x)$ se e solo se tutte le probabilità sono potenze di $\frac12$ .

Esempio. Probabilità $\left(\frac12,\frac14,\frac18,\frac18\right)$ e codice $A\to0$ , $B\to10$ , $C\to110$ , $D\to111$ : $H=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=\frac74=1{,}75$ e $\tilde L=\frac12\cdot1+\frac14\cdot2+\frac18\cdot3+\frac18\cdot3=1{,}75$ : $\eta=1$ .

Definizione (codifica di Shannon). Le lunghezze sono $l_i=\lceil\log_2\frac1{P_i}\rceil$ e le parole si assegnano scorrendo l'albero dalle lunghezze più corte alle più lunghe.

Esempio. $P=(0{,}38,\ 0{,}19,\ 0{,}17,\ 0{,}14,\ 0{,}12)$ per $A,\dots,E$ . $\log_2\frac1P=1{,}40,\ 2{,}40,\ 2{,}56,\ 2{,}84,\ 3{,}06$ , quindi $l=(2,3,3,3,4)$ (Kraft: $\frac14+\frac38+\frac1{16}=0{,}6875\le1$ ). Assegnazione canonica: $A=00$ ; poi tre parole di 3 bit: $B=010$ , $C=011$ , $D=100$ ; poi la parola di 4 bit $E=1010$ (si parte da $101$ e si aggiunge uno $0$ , perché $100$ è già usata e $101$ è libero). $\tilde L=0{,}38\cdot2+(0{,}19+0{,}17+0{,}14)\cdot3+0{,}12\cdot4=0{,}76+1{,}5+0{,}48=2{,}74$ bit, a fronte di $H=2{,}184$ bit: $\eta=0{,}797$ .

Teorema 1. In un codice ottimo, se $P_a\le P_b$ allora $L_a\ge L_b$ (la parola più probabile non è più lunga). Teorema 2. In un codice ottimo (binario) i due simboli meno probabili hanno parole di lunghezza massima, uguali in tutto tranne l'ultimo bit (sono "fratelli" nell'albero).

Esempio. Stessi simboli ( $0{,}38,\ 0{,}19,\ 0{,}17,\ 0{,}14,\ 0{,}12$ ). Si uniscono $D+E=0{,}26$ ; poi i due minori sono $C\,(0{,}17)$ e $B\,(0{,}19)$ : $B+C=0{,}36$ ; poi $DE\,(0{,}26)$ e $BC\,(0{,}36)$ : $0{,}62$ ; infine $A\,(0{,}38)+0{,}62=1$ . Codice: $A=0$ , $B=100$ , $C=101$ , $D=110$ , $E=111$ . $\tilde L=0{,}38\cdot1+0{,}62\cdot3=2{,}24$ bit, $\eta=\frac{2{,}184}{2{,}24}=0{,}975$ : è il minimo possibile con parole intere (meglio di Shannon, $2{,}74$ , e di Shannon-Fano, $2{,}26$ ).

3. Sistemi a coda

Processi di arrivo e processo di Poisson

Definizione (sistema a coda, queueing system). È un sistema fatto da clienti che arrivano, un'area di accodamento (queue, buffer) dove attendono e un servizio fornito da $m$ servitori (servers) in parallelo. Si assume che i clienti siano identici, i servitori identici e il servizio instancabile (un servitore libero serve sempre il cliente seguente).

Esempio. Un router riceve pacchetti: i pacchetti sono i clienti, il buffer di uscita è la coda, il collegamento in uscita è un servitore ( $m=1$ ) che "serve" un pacchetto per il tempo che serve a trasmetterlo. Una centrale con $m$ operatori è un sistema a $m$ servitori.

Definizione (processo di arrivo). Il $n$ -esimo cliente $C_n$ arriva all'istante $t_n$ ( $t_0$ è l'istante di riferimento). Il tempo di interarrivo è $\tau_n=t_n-t_{n-1}$ . Il processo di punto è la successione (aleatoria) degli istanti $t_n$ , cioè una sequenza di impulsi di Dirac in $t_n$ ; il processo di conteggio $A(t)$ è il numero di arrivi in $[0,t]$ (una funzione a gradini che sale di 1 a ogni arrivo, il cui "derivato" è il processo di punto: $A(t)=\int_0^t\sum_n\delta(u-t_n)\,du$ , Delta di Dirac e derivate generalizzate).

Esempio. Pacchetti con $m_\tau=0{,}5$ s: $\lambda=2$ pacchetti/s. Se arrivano $90$ clienti all'ora $\lambda=\frac{90}{3600}=0{,}025$ s $^{-1}$ , e $m_\tau=40$ s.

Grafico interattivo: Densità del tempo di interarrivo (media 1, λ = 1): esponenziale (Poisson, k = 1), Erlang-2 e Erlang-5 (tasso kλ per ogni fase). Al crescere di k la densità si stringe attorno alla media 1: gli arrivi diventano sempre più regolari, fino al caso deterministico

Definizione (processo di Poisson). Un processo di conteggio $A(t)$ è di Poisson se il numero di arrivi in intervalli disgiunti è (1) indipendente e (2) di Poisson con parametro $\int_{\mathcal J}\lambda(t)\,dt$ per l'intervallo $\mathcal J$ . È omogeneo se $\lambda(t)=\lambda$ . In un intervallo di durata $T$ vale $P[k\text{ arrivi in }T]=\frac{(\lambda T)^k}{k!}e^{-\lambda T},\qquad E=\operatorname{Var}=\lambda T.$

Esempio. $\lambda=2$ s $^{-1}$ e $T=1{,}5$ s: la media è $\lambda T=3$ e $P[k]=\frac{3^k}{k!}e^{-3}$ , con $e^{-3}=0{,}0498$ : $P[0]=0{,}0498$ , $P[1]=0{,}1494$ , $P[2]=P[3]=0{,}2240$ , $P[4]=0{,}1680$ . Il caso $k=0$ , $e^{-\lambda T}$ , è quello che compare nei protocolli ALOHA (nessun altro pacchetto nell'intervallo di vulnerabilità, Accesso al mezzo - ALOHA, CSMA e protocolli deterministici).

Grafico interattivo: Probabilità del numero k di arrivi in un intervallo con media λT = 3 (Poisson), istogramma con una barra per ogni k: massimo 0,224 per k = 2 e 3, coda lunga a destra; P[0] = e^(-3) = 0,0498

Teorema. Gli interarrivi di un processo di Poisson omogeneo di tasso $\lambda$ sono i.i.d. con densità esponenziale $p_\tau(a)=\lambda e^{-\lambda a}\mathbb 1(a)$ , funzione di distribuzione $P_\tau(a)=1-e^{-\lambda a}$ e media $E[\tau]=\frac1\lambda$ .

Proprietà (memoryless). Per un interarrivo esponenziale $P[\tau\le a\mid\tau\ge s]=P[\tau\le a-s]$ per $a>s$ : l'attesa residua ha la stessa distribuzione, traslata, indipendentemente da quanto si è già aspettato.

Esempio. $\lambda=2$ s $^{-1}$ . Probabilità che l'attesa superi 1,5 s dato che è già durata 1 s: $P[\tau>1{,}5\mid\tau>1]=\frac{e^{-3}}{e^{-2}}=e^{-1}=0{,}368=P[\tau>0{,}5]$ .

Definizione (processo di servizio). Il cliente $C_n$ occupa un servitore per un tempo di servizio $y_n$ . Si suppone che i $y_n$ siano i.i.d., con densità $p_y$ e funzione di distribuzione $P_y$ , indipendenti dagli arrivi. Il tasso di servizio di un servitore è $\mu=\frac1{E[y]}=\frac1{m_y}\quad[\text{clienti/s}],$ il numero di clienti che servirebbe al secondo se avesse sempre da lavorare. Con $m$ servitori in parallelo il tasso massimo è $m\mu$ .

Esempio. $R_b=50$ kbit/s e pacchetti di $1000$ bit: $\mu=\frac{50\,000}{1000}=50$ pacchetti/s, tempo di servizio $20$ ms.

Sistemi a coda M-M-1 e M-M-m

Formula di Erlang C. La probabilità che un cliente che arriva trovi tutti i servitori occupati (e debba attendere) è, per PASTA, $C=P[x\ge m]=\sum_{k\ge m}\pi_k=\frac{\pi_m}{1-\rho}=\frac{G^m}{m!\,(1-\rho)}\,\pi_0.$

Esempio. $m=2$ , $\mu=1$ s $^{-1}$ , $\lambda=1{,}6$ s $^{-1}$ : $G=1{,}6$ , $\rho=0{,}8$ . $\pi_0=\left[1+1{,}6+\frac{1{,}6^2}{2}\cdot\frac1{0{,}2}\right]^{-1}=\frac1{9}=0{,}1111$ ; $C=\frac{G^2}{2(1-\rho)}\pi_0=\frac{1{,}28}{0{,}2}\cdot\frac19=0{,}711$ . $E[q]=\frac{0{,}711\cdot1{,}6}{0{,}4}=2{,}844$ ; $E[x]=4{,}444$ ; $E[w]=\frac{0{,}711}{2-1{,}6}=1{,}778$ s; $E[s]=2{,}778$ s. (Una simulazione con $3\cdot10^5$ clienti dà $E[w]=1{,}75$ e $E[s]=2{,}75$ .)

Grafico interattivo: Probabilità di accodamento (Erlang C) in funzione del fattore di carico ρ = λ/(mμ) per m = 1, 2, 3 servitori: a parità di ρ, più servitori significano meno probabilità di dover attendere (m = 1: C = ρ; m = 2: 2ρ²/(1+ρ); m = 3: 4,5ρ³/(1+2ρ+1,5ρ²)); in ρ = 0,8 valgono 0,8, 0,711 e 0,647

Sistemi a coda M-G-1 e formula di Little

Definizione (stabilità). Un sistema è stabile se $\lim_{t\to\infty}P[x(t)=k]=\pi_k$ esiste, con $\sum_k\pi_k=1$ , e non dipende dallo stato iniziale $x(0)$ . Se $x(t)\to\infty$ le $\pi_k$ sono tutte $0$ e il sistema è esplosivo (instabile).

Esempio. Con $\mu=1000$ pacchetti/s: se $\lambda=800$ , $\rho=0{,}8<1$ , $\eta=800$ pacchetti/s e $S=0{,}8$ (il servitore è occupato l'80% del tempo). Se $\lambda=1200$ , $\rho=1{,}2$ : instabile, escono solo $\eta=1000$ pacchetti/s ( $S=1$ ) e la coda cresce di $200$ pacchetti al secondo.

Teorema (formula di Little). In una struttura "conservativa" (che non crea né distrugge clienti), se i valori medi esistono, il numero medio di clienti presenti è uguale al tasso di ingresso per il tempo medio di permanenza: $\boxed{E[x]=\lambda\,E[s].}$ Non fa ipotesi sulla distribuzione di arrivi e servizi, sulla disciplina (anche non FIFO), sul numero di servitori, né sulla dipendenza tra arrivi e servizio. Vale se i processi sono ergodici, in modo che le medie temporali coincidano con quelle statistiche.

Esempio. In un router entrano $\lambda=500$ pacchetti/s e in media se ne trovano $E[x]=10$ nel sistema: ogni pacchetto resta in media $E[s]=\frac{10}{500}=20$ ms. Se la trasmissione di un pacchetto dura $\frac1\mu=1$ ms, ne aspetta $E[w]=20-1=19$ ms in coda, e in coda ci sono $E[q]=500\cdot0{,}019=9{,}5$ pacchetti; il servitore è occupato per $E[z]=500\cdot0{,}001=0{,}5$ del tempo ( $9{,}5+0{,}5=10$ ✓). Little non dice com'è fatto il sistema: lega solo le tre medie.

Formula di Pollaczek-Khinchin. $\boxed{E[w]=\frac{\lambda\,E[y^2]}{2(1-\rho)}}$

Esempio. Collegamento da $1$ Mbit/s, $\lambda=800$ pacchetti/s, pacchetti da $1000$ bit ( $\mu=1000$ pacchetti/s, $\rho=0{,}8$ ). M/D/1 (lunghezza fissa): $E[w]=\frac{0{,}8}{2\cdot1000\cdot0{,}2}=2$ ms, $E[s]=3$ ms, $E[x]=0{,}8+\frac{0{,}64}{0{,}4}=2{,}4$ pacchetti (Little: $800\cdot0{,}003=2{,}4$ ✓). M/M/1 (lunghezza esponenziale di media $1000$ bit): $E[w]=4$ ms, $E[s]=5$ ms, $E[x]=4$ . Con servizio uniforme in $[0,2/\mu]$ ( $E[y^2]=\frac4{3\mu^2}$ , $c^2=\frac13$ ): $E[w]=\frac{1+1/3}2\cdot4=2{,}67$ ms (una simulazione con $6\cdot10^5$ clienti dà $2{,}66$ ). Altro esempio, pacchetti fissi con $\lambda=50$ pacchetti/s e $\mu=100$ ( $\rho=0{,}5$ ): $E[w]=\frac{0{,}5}{2\cdot100\cdot0{,}5}=5$ ms, $E[s]=15$ ms, $E[x]=0{,}5+\frac{0{,}25}{1}=0{,}75$ .

Grafico interattivo: Tempo medio nel sistema normalizzato E[s]·μ in funzione del fattore di carico ρ: M/M/1, 1/(1−ρ), e M/D/1, 1 + ρ/(2(1−ρ)). Entrambe divergono per ρ → 1; a ρ = 0,8 valgono 5 e 3

4. Mezzi trasmissivi

Potenza elettrica, impedenza e adattamento di carico

Formula (potenza elettrica e densità di potenza elettrica). $P=\int_{-\infty}^{+\infty}p_v(f)\,df,\qquad p_v(f)=\mathcal P_v(f)\,\frac{R(f)}{\lvert Z(f)\rvert^2}\quad[\text{W/Hz}].$ Se $v$ è limitata alla banda $\mathcal B$ (di frequenze positive, di larghezza $B$ ), poiché $p_v(f)$ è pari: $P=2\int_{\mathcal B}p_v(f)\,df$ .

Esempio. Su un'impedenza puramente resistiva $R=50\ \Omega$ una tensione ha PSD costante $\mathcal P_v=10^{-6}$ V $^2$ /Hz per $|f|<B=100$ kHz. Potenza statistica: $M_v=2B\,\mathcal P_v=2\cdot10^5\cdot10^{-6}=0{,}2$ V $^2$ . Potenza elettrica: $P=\frac{M_v}{R}=\frac{0{,}2}{50}=4$ mW $=6{,}02$ dBm.

Teorema (massimo trasferimento di potenza, load matching). La potenza trasferita al carico è massima se $Z_L(f)=Z_S^*(f)\qquad(R_L=R_S,\ X_L=-X_S).$ Il carico deve avere la stessa resistenza e la reattanza opposta: è il coniugato, non l'impedenza uguale.

Esempio. Sorgente con $Z_S=50+j30\ \Omega$ : il carico ottimo è $Z_L=50-j30\ \Omega$ . Con $Z_L=50+j30\ \Omega$ (uguale invece che coniugata) il denominatore vale $(100)^2+(60)^2=13\,600$ e non $(100)^2=10\,000$ : la potenza trasferita è $\frac{10\,000}{13\,600}=74\%$ del massimo.

Grafico interattivo: Frazione della potenza massima trasferita al carico in funzione di ρ = R_L/R_S (con le reattanze compensate): massimo 1 per ρ = 1, vale 8/9 = 0,889 per ρ = 1/2 o ρ = 2, e tende a 0 per ρ → 0 (cortocircuito) e ρ → ∞ (circuito aperto)

Doppi bipoli, guadagno e attenuazione

Definizione (guadagno di potenza). $g(f)=\frac{p_{v_{out}}(f)}{p_{v_{in}}(f)}\qquad(\text{rapporto tra le densità di potenza elettrica in uscita e in ingresso}).$ Quando $g(f)<1$ (il doppio bipolo dissipa invece di amplificare, per esempio un cavo) è più comodo usare l'attenuazione $a(f)=\frac1{g(f)} .$

Esempio. Un cavo che lascia passare il 10% della potenza ha $g=0{,}1\Rightarrow g_{dB}=-10$ dB, cioè $a=10\Rightarrow a_{dB}=+10$ dB. Un amplificatore con $g=100$ ha $g_{dB}=+20$ dB.

Grafico interattivo: Scala dei decibel: guadagno in dB, 10·log₁₀(g), in funzione del guadagno lineare g (asse orizzontale logaritmico). Moltiplicare g per 10 aggiunge sempre 10 dB; g = 1 (nessuna variazione) corrisponde a 0 dB; g = 2 a circa 3 dB; g < 1 (attenuazione) dà dB negativi

Rumore termico, temperatura e cifra di rumore

Formula (Friis). $T_c=T_1+\frac{T_2}{g_1}+\frac{T_3}{g_1g_2}+\cdots,\qquad F_c=F_1+\frac{F_2-1}{g_1}+\frac{F_3-1}{g_1g_2}+\cdots,\qquad g_c=g_1g_2g_3\cdots$ (tutte le grandezze in lineare).

Grafico interattivo: Cifra di rumore (in dB) di una cascata di due stadi in funzione del guadagno g₁ (in dB) del primo, con F₁ = 3 dB e F₂ = 10 dB: F = F₁ + (F₂ − 1)/g₁. Con g₁ = 0 dB il secondo stadio pesa tutto (F ≈ 11 dB); aumentando g₁ il secondo quasi sparisce e F tende a F₁ = 3 dB

Link budget

Formula (link budget in dB). $\text{SNR}_{dB}=(P_{tx})_{dBm}+114-(a_{ch})_{dB}-(F_{rc})_{dB}-10\log_{10}B_{MHz}.$

Esempio 1 (radio locale). $P_{tx}=10$ mW $=10$ dBm, $a_{ch}=90$ dB, $F_{rc}=17$ dB, $B=60$ kHz $=0{,}06$ MHz ( $10\log_{10}0{,}06=-12{,}2$ ): $\text{SNR}_{dB}=10+114-90-17+12{,}2=29{,}2\ \text{dB}\ (\approx830).$ Verifica in lineare: $\frac{10^{-2}/10^{9}}{1{,}38\cdot10^{-23}\cdot290\cdot50{,}1\cdot6\cdot10^4}=\frac{10^{-11}}{1{,}20\cdot10^{-14}}=830$ ✓.

5. Modulazione digitale

Spazio dei segnali e Gram-Schmidt

Definizione (prodotto scalare, norma, energia). $\langle x,y\rangle=\int_{-\infty}^{+\infty}x(t)\,y^*(t)\,dt,\qquad E_x=\langle x,x\rangle=\int_{-\infty}^{+\infty}\lvert x(t)\rvert^2dt,\qquad\lVert x\rVert=\sqrt{E_x}.$ Il quadrato della norma è l'energia del segnale; due segnali sono ortogonali se $\langle x,y\rangle=0$ .

Esempio. $s_1=A\operatorname{rect}\left(\frac{t-T/2}T\right)$ (ampiezza $A$ per $0<t<T$ ): $E_1=\int_0^TA^2dt=A^2T$ . Con $A=2$ V e $T=1$ ms: $E_1=4\cdot10^{-3}$ V $^2$ s (le unità dell'energia sono V $^2\cdot$ s, quelle della norma V $\sqrt{\text{s}}$ ).

Teorema di irrilevanza. Se il vettore ricevuto si può scrivere $\mathbf r=[\mathbf r_1\mid\mathbf r_2]$ e la densità di $\mathbf r_2$ condizionata a $\mathbf r_1$ e al simbolo trasmesso $a_0$ non dipende da $a_0$ , $p_{\mathbf r_2|\mathbf r_1,a_0}(\boldsymbol\rho_2\mid\boldsymbol\rho_1,j)=p_{\mathbf r_2|\mathbf r_1}(\boldsymbol\rho_2\mid\boldsymbol\rho_1),$ allora la decisione ottima può basarsi sul solo $\mathbf r_1$ : $\mathbf r_2$ è irrilevante.

Dimostrazione. Il criterio ottimo (MAP: Decisione ottima - criteri MAP e ML) massimizza $p_{\mathbf r|a_0}(\boldsymbol\rho\mid j)\,p_j$ . Scrivendo $p_{\mathbf r|a_0}=p_{\mathbf r_2|\mathbf r_1,a_0}\cdot p_{\mathbf r_1|a_0}$ (regola della catena, Formula delle probabilità totali e formula di Bayes) il primo fattore non dipende da $j$ per ipotesi e si può portare fuori dalla massimizzazione: resta $\max_j\,p_{\mathbf r_1|a_0}(\boldsymbol\rho_1\mid j)\,p_j$ . $\square$

Esempio. Se $\frac{N_0}2=2\cdot10^{-6}$ V $^2$ /Hz, la varianza per dimensione è $\sigma_I^2=2\cdot10^{-6}$ V $^2$ s e $\sigma_I=1{,}41\cdot10^{-3}$ V $\sqrt{\text{s}}$ . Confrontata con le coordinate dell'esempio di Gram-Schmidt ( $\approx0{,}03\div0{,}06$ V $\sqrt{\text{s}}$ ) il rumore è piccolo: la distanza minima $d_{min}=0{,}577\cdot0{,}0632=0{,}0365$ V $\sqrt{\text{s}}$ vale $\frac{d_{min}}{2\sigma_I}=12{,}9$ deviazioni standard, un SNR altissimo.

Decisione ottima - criteri MAP e ML

Criterio MAP (maximum a posteriori probability). $\boxed{\hat a_0=\arg\max_{j}D_j(\boldsymbol\rho)=\arg\max_j\ p_{\mathbf r|a_0}(\boldsymbol\rho\mid j)\,p_j,\qquad\mathcal R_j=\left\{\boldsymbol\rho:\ j=\arg\max_kD_k(\boldsymbol\rho)\right\}}$ È il criterio ottimo: massimizza $P[C]$ .

Criterio ML (maximum likelihood). $\hat a_0=\arg\max_j\ p_{\mathbf r|a_0}(\boldsymbol\rho\mid j).$

Teorema. Se i simboli sono equiprobabili ( $p_j=\frac1M$ ) il MAP coincide con il ML (e quindi il ML è ottimo). Dimostrazione: $\arg\max_j\frac1M\,p(\boldsymbol\rho|j)=\arg\max_jp(\boldsymbol\rho|j)$ , perché $\frac1M$ è una costante e non cambia dove sta il massimo.

Criterio MD (minimum distance). $\hat a_0=\arg\min_j\ \text{dist}(\boldsymbol\rho,\mathbf s_j)=\arg\min_j\lVert\boldsymbol\rho-\mathbf s_j\rVert .$ Si calcola la distanza del punto ricevuto da ciascun punto della costellazione e si sceglie il più vicino.

Teorema. Se il rumore è AWGN, MD coincide con ML. Dimostrazione. La verosimiglianza è $p_{\mathbf r|a_0}(\boldsymbol\rho|j)=(\pi N_0)^{-I/2}\exp\left(-\frac{\lVert\boldsymbol\rho-\mathbf s_j\rVert^2}{N_0}\right)$ . Il fattore davanti non dipende da $j$ e l'esponenziale è crescente, quindi massimizzare la verosimiglianza equivale a massimizzare $-\lVert\boldsymbol\rho-\mathbf s_j\rVert^2$ , cioè a minimizzare la distanza. $\square$

Probabilità d'errore e funzione Q

Definizione (funzione $Q$ ). Se $z\sim\mathcal N(0,1)$ , $Q(x)=P[z>x]=\int_x^{+\infty}\frac1{\sqrt{2\pi}}e^{-t^2/2}\,dt=\frac12\operatorname{erfc}\left(\frac x{\sqrt2}\right).$ Per una gaussiana generica $w\sim\mathcal N(0,\sigma^2)$ : $P[w>k]=Q\left(\frac k\sigma\right)$ (Distribuzione gaussiana (normale)).

Grafico interattivo: log₁₀ Q(x) in funzione di x (tabella della funzione Q: ogni 1,1 unità di x circa un decimo in meno; Q(3) = 1,3·10⁻³, Q(4,753) = 10⁻⁶, Q(6) = 10⁻⁹). Calcolata con l'approssimazione di Börjesson-Sundberg Q(x) ≈ e^(−x²/2)/(√(2π)·[0,661·x + 0,339·√(x² + 5,51)]), che differisce dal valore esatto meno dello 0,4%

Formula (probabilità d'errore, modulazione binaria). $\boxed{P[E]=Q\left(\frac{d_{12}}{2\sigma_I}\right)\overset{\sigma_I^2=N_0/2}{=}Q\left(\sqrt{\frac{E_s\,(1-\rho)}{N_0}}\right)}\qquad(E_1=E_2=E_s)$ Con due soli simboli ogni errore è un errore su un bit: $P_{bit}=P[E]$ (il canale numerico equivalente è un canale binario simmetrico, Canale binario simmetrico, codifica di Gray e probabilità di bit).

Trasmissione digitale di segnali analogici (PCM)

Formula ( $\Lambda_{PCM}$ ). $\boxed{\Lambda_{PCM}=\frac{\Lambda_q}{1+4P_{bit}\left(2^{2b}-1\right)}}\qquad\textbf{(scala lineare!)}$

Esempio ( $b=8$ , segnale uniforme, $\Lambda_q=4^8$ : $48{,}2$ dB). Con la formula:

Grafico interattivo: SNR complessivo Λ_PCM (dB) di un segnale uniforme a fondo scala in funzione di log₁₀ P_bit, per b = 4, 8, 12 bit: finché P_bit è piccola vale il plateau 6,02·b dB (24, 48, 72 dB) della sola quantizzazione; oltre la soglia P_bit ≈ 1/(4·4^b) tutte le curve si fondono nella retta −10·log₁₀(4P_bit), indipendente da b

6. Controllo d'errore

Codici a blocco - distanza minima, rivelazione e correzione

Definizione (codice a blocco binario $(n,k)$ ). Una sequenza di $k$ bit di informazione $\mathbf b=(b_1,\dots,b_k)\in\mathcal A^k$ (parola di informazione, $\mathcal A=\mathbb Z_2=\{0,1\}$ ), che sono $2^k$ possibili, viene trasformata dalla mappa di codifica $\mu_C$ in una parola di codice (codeword) $\mathbf c=\mu_C(\mathbf b)=(c_1,\dots,c_n)\in\mathcal A^n$ di $n>k$ bit. Le parole di codice sono ancora $2^k$ ma stanno in uno spazio più grande, di $2^n$ elementi: l'insieme $\mathcal C=\mu_C(\mathcal A^k)\subset\mathcal A^n$ è il codice. Si chiama tasso di codifica (coding rate) il rapporto $k/n<1$ .

Esempio. Il codice a ripetizione con $k=1$ , $n=3$ ha $2^1=2$ parole di codice, $\mathcal C=\{000,111\}$ , dentro uno spazio di $2^3=8$ sequenze: le altre sei ( $001,010,\dots$ ) non sono parole di codice; sono quelle che si ricevono quando il canale sbaglia. Il tasso è $1/3$ .

Definizione (codice sistematico). Un codice è sistematico se la parola di informazione $\mathbf b$ compare come prefisso della parola di codice: $\mathbf c=(\,\mathbf b\mid c_{k+1}\dots c_n\,)$ . Gli altri $n-k$ bit sono i bit di ridondanza (o di parità).

Definizione (distanza di Hamming). $d_H(\mathbf x,\mathbf y)$ è il numero di posizioni in cui $\mathbf x$ e $\mathbf y$ differiscono, cioè il numero minimo di salti per passare dall'una all'altra. È una vera distanza (simmetrica, $\ge0$ , nulla solo se uguali, vale la disuguaglianza triangolare). Esempio. $d_H(001001,001011)=1$ ; $d_H(1011,0110)=3$ (differiscono nei bit $1,2,4$ ).

Definizione (distanza minima di un codice). $d_{min}=\min_{\substack{\boldsymbol\gamma_1,\boldsymbol\gamma_2\in\mathcal C\\ \boldsymbol\gamma_1\ne\boldsymbol\gamma_2}}d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2).$ È il minimo numero di salti per andare da un sasso colorato a un altro sasso colorato.

Esempio. Ripetizione $m=3$ : $d_H(000,111)=3=d_{min}$ . Codice $\{00,11\}$ ( $m=2$ ): $d_{min}=2$ .

Teorema (potere di rivelazione). Un codice a blocco con distanza minima $d_{min}$ usato per rivelare garantisce la rivelazione di ogni situazione con al più $d_{min}-1$ bit sbagliati, cioè con $\#errori<d_{min}$ . Dimostrazione. Si parte da un sasso colorato (la parola trasmessa) e si fanno meno di $d_{min}$ salti (gli errori): non si può arrivare a un altro sasso colorato, perché ogni altro sasso colorato dista almeno $d_{min}$ . Quindi la parola ricevuta non è di codice: nessun errore non rivelato è possibile.

Esempio. Un codice con $d_{min}=3$ rivela ogni pattern di $1$ o $2$ errori; con $3$ errori potrebbe finire su un'altra parola di codice (a distanza $3$ ), e l'errore non verrebbe visto.

Teorema (condizione sufficiente per ML = MD). Su un BSC senza memoria con $P_{bit}<1/2$ , la decisione ML coincide con quella a distanza minima di Hamming. Dimostrazione. Sia $d=d_H(\boldsymbol\gamma,\tilde{\mathbf c})$ con $\boldsymbol\gamma=\mu_C(\boldsymbol\beta)$ . Allora $p_{\tilde{\mathbf c}|\mathbf b}(\boldsymbol\xi|\boldsymbol\beta)=P_{bit}^{\,d}(1-P_{bit})^{n-d}=\Big(\frac{P_{bit}}{1-P_{bit}}\Big)^{d}(1-P_{bit})^{n}.$ Il fattore $(1-P_{bit})^n$ è costante. Se $P_{bit}<\frac12$ allora $\frac{P_{bit}}{1-P_{bit}}<1$ , e una potenza di un numero minore di $1$ è tanto più grande quanto più piccolo è l'esponente $d$ . Massimizzare la likelihood equivale quindi a minimizzare $d$ . $\square$

Teorema (potere di correzione). Un codice con distanza minima $d_{min}$ usato con decodifica a distanza minima garantisce di correggere ogni caso con meno di $d_{min}/2$ bit sbagliati: la correzione è buona se $t<d_{min}/2$ errori, cioè $t\le\frac{d_{min}-2}{2}\ (d_{min}\text{ pari}),\qquad t\le\frac{d_{min}-1}{2}\ (d_{min}\text{ dispari}).$ Dimostrazione (per assurdo). Si invia $\boldsymbol\gamma_1$ e si riceve $\tilde{\mathbf c}$ con $d_H(\boldsymbol\gamma_1,\tilde{\mathbf c})=t<d_{min}/2$ . Supponiamo che si decodifichi un'altra parola $\boldsymbol\gamma_2\in\mathcal C$ , $\boldsymbol\gamma_2\neq\boldsymbol\gamma_1$ . Poiché MD sceglie la parola più vicina, $d_H(\boldsymbol\gamma_2,\tilde{\mathbf c})\le d_H(\boldsymbol\gamma_1,\tilde{\mathbf c})=t<d_{min}/2$ . Ma per la disuguaglianza triangolare $d_H(\boldsymbol\gamma_2,\tilde{\mathbf c})\ \ge\ d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2)-d_H(\boldsymbol\gamma_1,\tilde{\mathbf c})\ >\ d_{min}-\frac{d_{min}}2=\frac{d_{min}}2,$ contraddizione. $\square$

Esempio. $d_{min}=3$ : o si rivelano $2$ errori, o se ne corregge $1$ . $d_{min}=4$ : o si rivelano $3$ errori, o se ne corregge $1$ (la condizione $t<2$ dà $t=1$ ); in quest'ultimo caso si possono ancora rivelare, ma non correggere, i pattern con $2$ errori (a metà strada tra due parole di codice).

Teorema (limite di Hamming). Se un codice a blocco $(n,k)$ garantisce di correggere fino a $t$ errori, allora $\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr\quad\Longleftrightarrow\quad k\le n-\log_2\sum_{r=0}^t\binom nr.$ Dimostrazione. Si ricorda che $\mathbf b\in\mathcal A^k$ ha $2^k$ valori, $\mathbf c\in\mathcal C\subseteq\mathcal A^n$ ha $2^k$ valori scelti in un insieme di $2^n$ elementi. Garantire la correzione di $t$ errori significa che se $d_H(\mathbf c,\tilde{\mathbf c})=r\le t$ allora $\tilde{\mathbf c}\in\mathcal R_{\mathbf b}$ con $\mathbf b=\mu_C^{-1}(\mathbf c)$ . Quindi $\mathcal R_{\mathbf b}$ contiene almeno tutte le $n$ -uple che differiscono da $\mathbf c$ in al più $t$ posizioni, che sono $\sum_{r=0}^t\binom nr$ (c'è $1$ parola con $0$ errori, $n$ con $1$ errore, $\binom n2$ con $2$ , …): $|\mathcal R_{\mathbf b}|\ \ge\ \sum_{r=0}^t\binom nr$ (disuguaglianza e non uguaglianza: la regione può contenere altri elementi). La proprietà vale per ogni regione; sommando su tutte le $2^k$ parole di informazione $\mathbf b$ , $\sum_{\mathbf b}|\mathcal R_{\mathbf b}|\ \ge\ 2^k\sum_{r=0}^t\binom nr.$ Ma le $\mathcal R_{\mathbf b}$ sono disgiunte e ricoprono tutto $\mathcal A^n$ , quindi la somma vale $|\mathcal A^n|=2^n$ . Allora $2^n\ge2^k\sum_{r=0}^t\binom nr$ e, prendendo $\log_2$ , $n\ge k+\log_2\sum_{r=0}^t\binom nr$ . $\square$

Esempio. Hamming $(7,4)$ con $t=1$ : $\sum=\binom70+\binom71=8$ , $2^4\cdot8=128=2^7$ : uguaglianza, le regioni ricoprono lo spazio senza avanzi (codice perfetto, Codici di Hamming e CRC). Per un codice con $n=15$ e $t=1$ : $k\le15-\log_2(16)=11$ (è l'Hamming $(15,11)$ ). Per $n=25$ , $t=1$ : $\sum=26$ , $k\le25-\log_2 26=20{,}30$ , quindi $k\le20$ : il $(25,16)$ del corso, che corregge $1$ errore, ha tasso $0{,}64$ contro un massimo teorico $20/25=0{,}8$ . Per $n=23$ , $t=3$ il limite dà $k\le12$ (il codice di Golay $(23,12)$ lo raggiunge).

Codici a blocco lineari e sindrome

Definizione (peso di Hamming). $\|\mathbf c\|_H=d_H(\mathbf c,\mathbf 0)=$ numero di bit uguali a $1$ in $\mathbf c$ $=\sum_{j=1}^nc_j$ (somma in $\mathbb R$ , non modulo $2$ ), dove $\mathbf 0$ è la parola nulla (tutti zeri). Vale $d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2)=\|\boldsymbol\gamma_1-\boldsymbol\gamma_2\|_H=\|\boldsymbol\gamma_1+\boldsymbol\gamma_2\|_H$ .

Esempio. $\boldsymbol\gamma_1=1011$ , $\boldsymbol\gamma_2=0110$ : $\boldsymbol\gamma_1+\boldsymbol\gamma_2=1101$ , peso $3=d_H(\boldsymbol\gamma_1,\boldsymbol\gamma_2)$ (le posizioni $1,2,4$ differiscono).

Definizione (codice lineare). Un codice a blocco è lineare se l'insieme delle parole $\mathcal C=\mu_C(\mathbb Z_2^k)$ è un sottospazio (Sottospazi vettoriali) di $\mathbb Z_2^n$ .

Teorema (distanza minima di un codice lineare). In un codice lineare $d_{min}$ coincide con il peso di Hamming minimo delle parole non nulle: $d_{min}=\min_{\boldsymbol\gamma\in\mathcal C\setminus\{\mathbf0\}}\|\boldsymbol\gamma\|_H.$ Dimostrazione. Per definizione $d_{min}=\min_{\gamma_1\ne\gamma_2}d_H(\gamma_1,\gamma_2)=\min\|\gamma_1-\gamma_2\|_H$ . Basta mostrare che l'insieme delle differenze $\boldsymbol\gamma_1-\boldsymbol\gamma_2$ con $\boldsymbol\gamma_1\ne\boldsymbol\gamma_2$ è esattamente l'insieme delle parole di codice non nulle. Una differenza è una parola di codice (linearità) e non è nulla perché $\gamma_1\ne\gamma_2$ . Viceversa, sia $\boldsymbol\gamma\in\mathcal C$ non nulla: allora $\boldsymbol\gamma=\boldsymbol\gamma-\mathbf0$ è la differenza di due parole del codice, perché $\mathbf0\in\mathcal C$ . $\square$

Esempio. Il codice $\mu_1$ dell'Esercizio - Codici (4,2) lineari o no e probabilità di errore non rivelato, $\{0011,0110,1010,1100\}$ , non è lineare: manca $\mathbf 0$ . Il $\mu_2$ , $\{0000,0110,1011,1101\}$ , lo è: pesi $0,2,3,3$ , $d_{min}=2$ .

Definizione (matrice generatrice). Se si prendono $k$ parole di codice linearmente indipendenti $\boldsymbol\gamma_1,\dots,\boldsymbol\gamma_k$ (Combinazioni lineari e dipendenza lineare) e le si mettono in colonna si ottiene $G=[\boldsymbol\gamma_1\ \boldsymbol\gamma_2\ \dots\ \boldsymbol\gamma_k]$ ( $n\times k$ ), una matrice generatrice del codice. Le $\boldsymbol\gamma_j$ sono una base di $\mathcal C$ (Generatori e basi, Dimensione: $\dim\mathcal C=k$ ).

Esempio. Il codice $\mu_2$ dell'esercizio, $c_1=b_1$ , $c_2=b_2$ , $c_3=b_1+b_2$ , $c_4=c_2+c_3=b_1$ , ha $G=\begin{pmatrix}1&0\\0&1\\1&1\\1&0\end{pmatrix}.$ La prima colonna è $(1,0,1,1)^T=1011$ (la parola associata a $\mathbf b=10$ ), la seconda $(0,1,1,0)^T=0110$ (per $\mathbf b=01$ ); la parola per $\mathbf b=11$ è la loro somma $1101$ , e per $\mathbf b=00$ si ha $0000$ .

Teorema (forma di $G$ per un codice sistematico). Un codice lineare sistematico ammette una matrice generatrice $G=\begin{pmatrix}I_k\\ A\end{pmatrix},$ con $I_k$ la matrice identità $k\times k$ e $A$ una matrice $(n-k)\times k$ detta matrice di parità. Dimostrazione. Per definizione di sistematico $c_j=b_j$ per $1\le j\le k$ : le prime $k$ righe di $G$ sono $I_k$ . Gli altri $n-k$ bit sono combinazioni lineari dei $b_j$ e le loro righe formano $A$ . $\square$

Lemma. Ogni codice lineare ha un equivalente sistematico. Idea della dimostrazione. Data una $G$ a rango pieno, con operazioni elementari su righe e colonne (l'eliminazione di Gauss-Jordan, Eliminazione di Gauss) la si riduce a $G'=\binom{I_k}{A}$ .

Teorema (limite di Singleton). Per ogni codice lineare $(n,k)$ , $d_{min}\le n-k+1$ . Dimostrazione. Si usa il lemma. Ogni colonna di $G'=\binom{I_k}{A}$ è una parola di codice che ha al più un $1$ nella parte superiore ( $I_k$ ) e al più $n-k$ uni nella parte inferiore ( $A$ ): peso $\le1+(n-k)$ . Quindi esiste una parola non nulla di peso $\le n-k+1$ e $d_{min}\le n-k+1$ . $\square$

Definizione (matrice di controllo di parità). Per un codice lineare $(n,k)$ la matrice di controllo di parità è una matrice $H$ di tipo $\ell\times n$ (in generale $\ell\ge n-k$ , in pratica $\ell=n-k$ ) tale che $H\mathbf c=\mathbf 0\iff\mathbf c\in\mathcal C,$ dove $\mathbf 0$ è il vettore nullo con $\ell$ elementi. (Non va confusa con la matrice di parità $A$ , che è un'altra cosa.)

Teorema (proprietà caratteristica). $H$ ( $\ell\times n$ ) è la matrice di controllo del codice con matrice generatrice $G$ se e solo se $HG=O$ e $\mathrm{rank}(H)=n-k$ . Dimostrazione (sketch). ( $\Rightarrow$ ) $G$ è fatta di parole di codice, quindi $H\boldsymbol\gamma_j=\mathbf0$ per ogni colonna: $HG=O$ (la matrice nulla $\ell\times k$ ). ( $\Leftarrow$ ) $\mathcal C$ è lo spazio nullo di $H$ (Nucleo e immagine), che ha dimensione $n-\mathrm{rank}(H)=n-(n-k)=k$ ; e $HG=O$ dice che lo span di $G$ (dimensione $k$ ) è contenuto nel nucleo di $H$ : avendo la stessa dimensione coincidono. $\square$

Teorema (matrice $H$ di un codice sistematico). Se $G=\binom{I_k}{A}$ allora $H=[\,-A\mid I_{n-k}\,]=[\,A\mid I_{n-k}\,]\quad\text{in }\mathbb Z_2.$ Dimostrazione. $H$ ha rango $n-k$ per la presenza di $I_{n-k}$ . Inoltre $HG=[-A\mid I_{n-k}]\binom{I_k}{A}=-A\,I_k+I_{n-k}A=-A+A=O$ . Per la proprietà caratteristica $H$ è la matrice di controllo. $\square$ (Il teorema vale anche sui campi non binari, dove il segno conta.)

Esempio. Hamming $(7,4)$ ( $n-k=3$ ): $H=[A\mid I_3]=\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}.$ Controllo su $\boldsymbol\gamma_1=1000110$ : la prima riga di $H$ somma i bit $1,2,4,5$ di $\boldsymbol\gamma_1$ ( $1+0+0+1=0$ ), la seconda i bit $1,3,4,6$ ( $1+0+0+1=0$ ), la terza i bit $2,3,4,7$ ( $0+0+0+0=0$ ): $H\boldsymbol\gamma_1=\mathbf0$ . Lo stesso vale per $\boldsymbol\gamma_2,\boldsymbol\gamma_3,\boldsymbol\gamma_4$ ( $HG=O$ , verificato al calcolatore). Le colonne di $H$ sono $110,\ 101,\ 011,\ 111,\ 100,\ 010,\ 001$ : tutte le $7$ sequenze non nulle di $3$ bit, e quindi tutte distinte e non nulle.

Definizione (laterale, o coset). Ognuna delle classi della partizione si chiama coset: $\mathbb Z_2^n$ è partizionato in $2^{n-k}$ coset, ciascuno associato a una sindrome e con $2^k$ elementi; uno di essi (sindrome nulla) è l'insieme delle parole di codice $\mathcal C$ .

Definizione (coset leader). A ogni sindrome $\boldsymbol\sigma$ si associa un elemento speciale $\varepsilon(\boldsymbol\sigma)=\arg\min_{\mathbf c\in\mathbb Z_2^n:\ H\mathbf c=\boldsymbol\sigma}\|\mathbf c\|_H,$ cioè l'elemento del coset di peso di Hamming minimo. Se più elementi hanno peso minimo se ne sceglie uno con una regola qualsiasi. Evidentemente $\varepsilon(\mathbf0_{n-k})=\mathbf0_n$ .

Teorema (decodifica a sindrome). Ricevuto $\tilde{\mathbf c}$ con sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ , la decodifica a distanza minima (MD) è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)\ \ (=\tilde{\mathbf c}+\varepsilon(\boldsymbol\sigma)\text{ in }\mathbb Z_2).$ Dimostrazione. Primo, $\hat{\mathbf c}$ è una parola di codice: $H\hat{\mathbf c}=H\tilde{\mathbf c}-H\varepsilon(\boldsymbol\sigma)=\boldsymbol\sigma-\boldsymbol\sigma=\mathbf0$ . Poi, come funziona MD? Se $\mathcal C=\{\boldsymbol\gamma_1,\dots,\boldsymbol\gamma_{2^k}\}$ si fanno $2^k$ ipotesi: $\tilde{\mathbf c}=\boldsymbol\gamma_j+\tilde{\mathbf e}_j$ , dove $\tilde{\mathbf e}_j$ è il possibile vettore d'errore (con un $1$ nei bit invertiti), e si sceglie quello con meno uni (distanza di Hamming minima). I vettori $\tilde{\mathbf e}_j$ (1) sono tutti diversi, (2) sono $2^k$ , (3) hanno tutti sindrome $\boldsymbol\sigma$ : infatti $\boldsymbol\sigma=H\tilde{\mathbf c}=H(\boldsymbol\gamma_j+\tilde{\mathbf e}_j)=H\tilde{\mathbf e}_j$ . Sono quindi tutto il coset di $\boldsymbol\sigma$ , e quello di peso minimo è per definizione $\varepsilon(\boldsymbol\sigma)$ . La decodifica MD è $\tilde{\mathbf c}=\hat{\mathbf c}+\varepsilon(\boldsymbol\sigma)$ , cioè quanto affermato. $\square$

Codici di Hamming e CRC

Definizione (codice di Hamming). Per ogni $h\ge2$ è il codice lineare con $H$ di tipo $h\times n$ che ha per colonne tutte le $2^h-1$ sequenze binarie non nulle di $h$ bit: $n=2^h-1$ , $k=n-h=2^h-h-1$ .

Teorema (proprietà del codice di Hamming). (1) $d_{min}=3$ . (2) Corregge ogni errore singolo. (3) Per qualunque pattern di $2$ errori la decodifica a sindrome sbaglia. (4) È un codice perfetto: le regioni di decisione sono tutte le sfere di raggio $1$ attorno alle parole e coprono esattamente tutto lo spazio. Dimostrazione. (1) Colonne non nulle: nessuna parola di peso $1$ ; colonne distinte: nessuna parola di peso $2$ (la somma di due colonne distinte non è nulla). Tra tre colonne ce ne sono sempre dipendenti: prese due colonne distinte $\mathbf h_a,\mathbf h_b$ , la loro somma è un'altra colonna non nulla $\mathbf h_c$ (perché le colonne sono tutte le sequenze non nulle), e $\mathbf h_a+\mathbf h_b+\mathbf h_c=\mathbf0$ . Dunque esiste una parola di peso $3$ : $d_{min}=3$ (si ricordi che $d_{min}$ è il numero minimo di colonne di $H$ linearmente dipendenti). (2) Un errore singolo in $j$ ha sindrome $\mathbf h_j$ , diversa da ogni altra colonna e non nulla: il coset leader è $\mathbf e_j$ . (3) Con due errori in $a$ e $b$ la sindrome è $\mathbf h_a+\mathbf h_b=\mathbf h_c$ : il decodificatore "corregge" la posizione $c$ introducendo un terzo errore. (4) Le sfere di raggio $1$ hanno ciascuna $1+n$ elementi e sono $2^k$ : $2^k(1+n)=2^k\cdot2^h=2^n$ , uguaglianza nel limite di Hamming (Codici a blocco - distanza minima, rivelazione e correzione). $\square$

Definizione (codice CRC). Si fissa un polinomio generatore $g(x)$ di grado $r$ , con termine noto $1$ (per esempio $g(x)=x^4+x+1\leftrightarrow10011$ ). Dato il messaggio $m(x)$ di $k$ bit, si calcola il resto $\rho(x)=\big(m(x)\,x^r\big)\ \mathrm{mod}\ g(x)\qquad(\deg\rho<r)$ e si trasmette la parola $c(x)=m(x)\,x^r+\rho(x)$ , cioè il messaggio seguito dagli $r$ bit del resto (codice sistematico).

Capacità di canale

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 (capacità di Shannon). $\displaystyle C=\max_{\text{statistiche di }\mathbf c}R(\mathbf c)$ .

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$ .

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$ .

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).

7. Livello di collegamento e reti

Accesso al mezzo - ALOHA, CSMA e protocolli deterministici

Definizione (intervallo di vulnerabilità). L'intervallo in cui altre trasmissioni causano collisione. Per l'ALOHA ha durata $2t_P$ .

Formula (throughput dell'ALOHA puro). $\boxed{S=G\,e^{-2G}}.$

Esempio. $G=0{,}1$ : $P_{success}=e^{-0{,}2}=0{,}819$ , $S=0{,}082$ ; $G=0{,}5$ : $S=0{,}184$ ; $G=2$ : $P_{success}=e^{-4}=0{,}018$ , $S=0{,}037$ (canale sommerso dalle collisioni).

Grafico interattivo: Throughput S contro traffico offerto G: ALOHA puro ha massimo 1/(2e) ≈ 0,184 in G=1/2, slotted ALOHA 1/e ≈ 0,368 in G=1; oltre il massimo il throughput scende verso zero.

Formula (CSMA non persistente, completamento). Con $a=\tau_P/t_P$ e traffico offerto $G$ (se $\tau_P=0$ , $S=G/(1+G)\to1$ per $G\to\infty$ ): $S=\frac{G\,e^{-aG}}{G(1+2a)+e^{-aG}}.$ (È la formula standard, usata per i grafici delle slide: non è dedotta nel corso. Per $a=0{,}01$ il massimo è $S\simeq0{,}815$ in $G\simeq9{,}5$ ; per $a=0{,}1$ , $S\simeq0{,}515$ in $G\simeq2{,}6$ ; per $a=1$ , $S\simeq0{,}144$ : peggio dello slotted ALOHA.)

Grafico interattivo: Throughput di CSMA non persistente per a=τ_P/t_P=0,01 e 0,1 contro slotted ALOHA, con G in scala logaritmica: con a piccolo il CSMA arriva a 0,82 (a=0,01), ma con a=0,1 il massimo cala a 0,52.