FormularioFondamenti di Segnali e Telecomunicazioni: definizioni, teoremi e formule delle note, in ordine di capitolo

1. Probabilità

Probabilità per le telecomunicazioni - eventi e variabili aleatorie discrete

Teorema (probabilità dell'unione). $$P(x\cup y)=P(x)+P(y)-P(x\cap y).$$ Se i due eventi sono disgiunti (non possono accadere insieme, $P(x\cap y)=0$) si riduce a $P(x\cup y)=P(x)+P(y)$.

Teorema. Per costanti $A,B$ e v.a. $x,y$ qualsiasi (anche dipendenti): $E(Ax+By)=A\,E(x)+B\,E(y)$.

Variabili aleatorie continue - uniforme, gaussiana, esponenziale e funzione Q

Teorema del limite centrale. Siano $y_1,\dots,y_N$ v.a. indipendenti con la stessa densità, media $m=E(y_i)$ e varianza $\sigma^2=E\big[(y_i-m)^2\big]$. Allora, al crescere di $N$, $$\frac1{\sqrt N}\sum_{i=1}^{N}\big(y_i-m\big)\ \longrightarrow\ \mathcal N(0,\sigma^2).$$

2. Segnali

Segnali a tempo continuo - sinusoidi, rect e trasformazioni dell'asse dei tempi

Definizione (rettangolo). $$\operatorname{rect}(t)=\begin{cases}1&t\in\left[-\frac12,\frac12\right]\\0&\text{altrove}\end{cases}$$ È un impulso di altezza $1$ e larghezza $1$, centrato in $0$. Il numero $3\operatorname{rect}(t)$ è lo stesso impulso con altezza $3$.

Definizione (triangolo). $$\operatorname{triang}(t)=\begin{cases}t+1&t\in[-1,0)\\1-t&t\in[0,1]\\0&\text{altrove}\end{cases}=1-|t|\ \text{ per }|t|\le1.$$ Altezza $1$ in $t=0$, base $2$ (da $-1$ a $1$), simmetrico.

Campionamento e interpolazione - mantenimento, lineare e ideale

Teorema del campionamento. Se il segnale $s(t)$ ha banda limitata $B$ (la sua trasformata di Fourier è nulla per $|f|>B$) e il periodo di campionamento soddisfa $$T\le\frac1{2B}\qquad\Longleftrightarrow\qquad F_s=\frac1T\ge2B,$$ allora il segnale si ricostruisce esattamente dai suoi campioni con l'interpolatore ideale: $$s(t)=\sum_{m=-\infty}^{+\infty}s(mT)\,\operatorname{sinc}\Big(\frac{t-mT}{T}\Big).$$

3. Modulazione digitale e spazio dei segnali

Demodulatore digitale - proiezione del rumore e teorema di irrilevanza

Teorema (irrilevanza). Se, dato il simbolo $m$, $\mathbf r^{(II)}$ è indipendente da $\mathbf r^{(I)}$, e inoltre la densità di $\mathbf r^{(II)}$ non dipende dal simbolo, $p_{\mathbf r^{(II)}|a_0}(\mathbf r^{(II)}\mid m)=p_{\mathbf r^{(II)}}(\mathbf r^{(II)})$ per ogni $m$, allora $$\hat a_0=\arg\max_m\ p_{\mathbf r^{(I)}|a_0}\left(\mathbf r^{(I)}\mid m\right)P_{a_0}(m):$$ la parte $\mathbf r^{(II)}$ è irrilevante e può essere scartata.

6. Codifica di canale

Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico

Definizione. Un codice a blocco $(n,k)$ associa a ogni sequenza di $k$ bit di informazione $\mathbf b=[b_1,\dots,b_k]^T$ una parola di codice $\mathbf c=[c_1,\dots,c_n]^T$ di $n>k$ bit, in modo biunivoco. L'insieme delle parole è il codice $\mathcal C$.

Definizione. Un canale binario simmetrico senza memoria (BSC, binary symmetric channel) ha ingresso $x$ e uscita $y$ in $\{0,1\}$ e $$P(y=1\mid x=0)=P(y=0\mid x=1)=P_{bit},\qquad y_i=x_i\oplus\varepsilon_i,$$ con gli errori $\varepsilon_i\in\{0,1\}$ indipendenti nel tempo, $P(\varepsilon_i=1)=P_{bit}$.

Definizione. La distanza di Hamming tra due sequenze binarie $\boldsymbol\alpha,\boldsymbol\beta$ di $n$ bit è il numero di posizioni in cui sono diverse: $$d_H(\boldsymbol\alpha,\boldsymbol\beta)=\sum_{i=1}^n(\alpha_i\oplus\beta_i),$$ dove $\alpha_i\oplus\beta_i$ vale $1$ se i bit sono diversi e $0$ se sono uguali ("differenza binaria").

Definizione. La distanza minima del codice è la minima distanza di Hamming tra due parole diverse: $$d_{min}=\min_{\boldsymbol\alpha,\boldsymbol\beta\in\mathcal C,\ \boldsymbol\alpha\ne\boldsymbol\beta}d_H(\boldsymbol\alpha,\boldsymbol\beta).$$

Definizione. Il tasso (rate) del codice è $R=\dfrac kn\le1$.

Codici a blocco lineari - matrice generatrice, forma sistematica e bound di Singleton

Definizione. La norma (peso) di Hamming $\|\mathbf x\|_H=w_H(\mathbf x)$ è il numero di $1$ presenti nella sequenza. Valgono $\|\mathbf x\|_H\ge0$, $\|\mathbf x\|_H=0\iff\mathbf x=\mathbf0$, $\|\alpha\mathbf x\|_H=|\alpha|\,\|\mathbf x\|_H$ e la disuguaglianza triangolare $\|\mathbf x+\mathbf y\|_H\le\|\mathbf x\|_H+\|\mathbf y\|_H$.

Definizione. Un codice a blocco $\mathcal C=\{\mathbf c_1,\dots,\mathbf c_{2^k}\}$ è lineare se è un sottospazio lineare dello spazio delle sequenze di lunghezza $n$ (Sottospazi vettorialiUn sottospazio vettoriale è un sottoinsieme che è spazio vettoriale con le stesse operazioni: basta che sia chiuso per somma e per prodotto per scalari. Deve contenere il vettore nullo. In R^2 i sottospazi sono {0}, le rette per l'origine e tutto R^2.Sottospazi vettoriali →): contiene la parola nulla e la somma di due parole qualunque è ancora una parola.

Definizione. Una matrice $G$ di dimensioni $n\times k$ è la matrice generatrice di un codice lineare se ha rango $k$ e $$\mathbf c=G\,\mathbf b\iff\mathbf c\in\mathcal C\qquad(\mathbf b\in\{0,1\}^k).$$ Il bit $i$-esimo della parola è il prodotto della riga $i$ di $G$ per $\mathbf b$: $c_i=\mathbf G_{i,\cdot}\,\mathbf b$ (somma modulo 2).

Definizione. $G$ è in forma sistematica se $$G=\begin{bmatrix}I_k\\A\end{bmatrix},\qquad A\ \text{di dimensioni }(n-k)\times k,\qquad G\mathbf b=\begin{bmatrix}\mathbf b\\A\mathbf b\end{bmatrix}.$$ I primi $k$ bit della parola sono i bit di informazione, gli altri $n-k$ sono i bit di parità $\mathbf p=A\mathbf b$.

Definizione. Il peso di Hamming del codice è $w_H(\mathcal C)=\min_{\mathbf c\in\mathcal C,\ \mathbf c\ne\mathbf0}w_H(\mathbf c)$, il minimo numero di $1$ tra le parole non nulle.

Teorema. In un codice lineare la distanza minima è uguale al peso minimo: $d_{min}=w_H(\mathcal C)$.

Dimostrazione. $d_{min}=\min_{\mathbf c_i\ne\mathbf c_j}d_H(\mathbf c_i,\mathbf c_j)=\min_{\mathbf c_i\ne\mathbf c_j}\|\mathbf c_i-\mathbf c_j\|_H$. Il codice è lineare, quindi $\mathbf c_i-\mathbf c_j=\mathbf c_i+\mathbf c_j$ è una parola di codice, non nulla perché $\mathbf c_i\ne\mathbf c_j$; viceversa ogni parola non nulla $\mathbf c$ si ottiene come $\mathbf c-\mathbf 0$ con $\mathbf 0\in\mathcal C$. Quindi il minimo sulle coppie è il minimo sulle parole non nulle: $\min_{\mathbf c\ne\mathbf 0}\|\mathbf c\|_H=w_H(\mathcal C)$. $\square$

Teorema (bound di Singleton). Per un codice lineare $(n,k)$ $$d_{min}\le n-k+1.$$

Dimostrazione. Si sceglie una $G$ in forma sistematica (si può sempre: cambia al più l'ordine dei bit, non $d_{min}$). La colonna $i$ è $\begin{bmatrix}\mathbf e_i\\A_{\cdot,i}\end{bmatrix}$, con $\mathbf e_i$ il vettore con un solo $1$ in posizione $i$ e $A_{\cdot,i}$ lunga $n-k$. Il suo peso è al più $1+(n-k)$. Essendo una parola di codice, $d_{min}\le w_H\le1+n-k$. $\square$

Matrice di controllo di parità, sindrome e coset

Definizione. Una matrice $H$ di dimensioni $\ell\times n$ è una matrice di controllo di parità del codice lineare $\mathcal C$ se $$H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C\qquad(\mathbf r\in\{0,1\}^n).$$

Teorema. $H$ è una matrice di controllo di parità del codice con generatrice $G$ se e solo se $$HG=0\qquad\text{e}\qquad\operatorname{rango}(H)=n-k.$$ (dimensioni: $H$ è $\ell\times n$, $G$ è $n\times k$, $0$ è $\ell\times k$; da cui $\ell\ge n-k$.)

Dimostrazione ($\Leftarrow$). Se $\mathbf r\in\mathcal C$ allora $\mathbf r=G\mathbf b$ e $H\mathbf r=(HG)\mathbf b=\mathbf 0$. Viceversa, se $H\mathbf r=\mathbf 0$, $\mathbf r$ sta nello spazio nullo di $H$ (Nucleo e immagineIl nucleo (vettori mandati in 0) e l'immagine (vettori raggiunti) di una funzione lineare sono sottospazi; f è iniettiva se e solo se Ker f = {0}; dim Ker f + dim Im f = dim V (nullità + rango); l'antimmagine di un vettore è una soluzione particolare più il nucleo.Nucleo e immagine →), che per il teorema della dimensione ha dimensione $n-\operatorname{rango}(H)=k$, quindi contiene $2^k$ sequenze. Ma le $2^k$ parole di codice stanno già nello spazio nullo (primo verso): non c'è posto per altre. Quindi $H\mathbf r=\mathbf 0\Rightarrow\mathbf r\in\mathcal C$.

($\Rightarrow$). Le colonne di $G$ sono parole di codice, e $H\mathbf r=\mathbf 0$ per ogni parola, quindi $HG=0$. Lo spazio nullo di $H$ è il codice, di dimensione $k$, quindi il rango di $H$ è $n-k$. $\square$

Teorema. $d_{min}$ è il minimo numero di colonne di $H$ linearmente dipendenti (che sommano a $\mathbf 0$).

Definizione. Data la sequenza ricevuta $\boldsymbol\gamma$ (lunga $n$), la sindrome è $$\boldsymbol\sigma=H\boldsymbol\gamma\qquad(n-k\text{ bit}).$$

Definizione. L'insieme $\boldsymbol\varepsilon_0+\mathcal C$ degli errori con sindrome $\boldsymbol\sigma$ è il coset associato a $\boldsymbol\sigma$. Un coset leader è un vettore del coset di peso di Hamming minimo.

Codici di Hamming e bound di Hamming

Definizione. Un codice di Hamming è un codice lineare la cui matrice di controllo di parità $H$ ha per colonne tutte le sequenze binarie non nulle lunghe $n-k$, ciascuna presa una sola volta. L'ordine delle colonne non conta.

Teorema. Ogni codice di Hamming ha $d_{min}=3$.

Dimostrazione. Per il teorema della sezione 2 di Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset →, $d_{min}$ è il minimo numero di colonne di $H$ che sommano a $\mathbf 0$.

1. Nessuna parola di peso 1. Una parola di peso $1$ con l'$1$ in posizione $i$ darebbe $H\mathbf c=\mathbf h_i$, la colonna $i$: ma per costruzione in $H$ non ci sono colonne nulle.
2. Nessuna parola di peso 2. Con due $1$ in posizioni $i\ne j$ si avrebbe $H\mathbf c=\mathbf h_i+\mathbf h_j$, la somma di due colonne diverse: non può essere $\mathbf 0$ perché in $H$ non ci sono colonne ripetute.
3. Esiste una parola di peso 3. Si scelgono $i\ne j$. La somma $\mathbf h_i+\mathbf h_j$ non è nulla (le colonne sono diverse) e diversa da $\mathbf h_i$ e da $\mathbf h_j$ (perché né $\mathbf h_j$ né $\mathbf h_i$ sono nulle); quindi è una sequenza non nulla di $n-k$ bit diversa da $\mathbf h_i$ e $\mathbf h_j$, e siccome $H$ contiene tutte le sequenze non nulle, è una terza colonna $\mathbf h_k$ con $k\ne i,j$. Allora $\mathbf h_i+\mathbf h_j+\mathbf h_k=\mathbf 0$: la sequenza con tre $1$ in $i,j,k$ è una parola di codice. $\square$

Definizione. Un codice per cui le sfere di raggio $t$ attorno alle parole riempiono tutto lo spazio senza sovrapporsi (il bound di Hamming vale con l'uguaglianza) è un codice perfetto.

7. Teoria dell'informazione

Entropia - informazione di un evento, disuguaglianza di Jensen e valore massimo

Definizione (entropia). L'entropia di $x$ è il valore atteso dell'informazione (Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →): $$\boxed{H(x)=E\left[i_x(x)\right]=\sum_{a\in\mathcal A_x}P_x(a)\log_2\frac1{P_x(a)}=-\sum_aP_x(a)\log_2P_x(a)\quad[\text{bit}].}$$ Per i valori con $P_x(a)=0$ si pone $0\cdot\log_2\frac10=0$ (il limite di $p\log\frac1p$ per $p\to0$ è $0$), cioè i simboli impossibili non contano.

Definizione (funzione strettamente concava). $f$ è strettamente concava se, comunque si scelgano $N$ pesi $k_1,\dots,k_N>0$ con $\sum_{n}k_n=1$ e $N$ punti distinti $a_1,\dots,a_N$, $$\sum_{n=1}^Nk_nf(a_n)<f\left(\sum_{n=1}^Nk_na_n\right).$$

Teorema (disuguaglianza di Jensen). Se $f$ è strettamente concava e $x$ è una variabile aleatoria discreta non costante, $$\boxed{E\left[f(x)\right]<f\left(E[x]\right).}$$ Se $x$ è costante vale l'uguaglianza. In particolare, per il logaritmo: $E\left[\log_2x\right]\le\log_2E[x]$.

Teorema. Una variabile aleatoria discreta $x$ con alfabeto di cardinalità $M$ ha $$\boxed{0\le H(x)\le\log_2M\ \text{bit},}$$ e $H(x)=\log_2M$ se e solo se $x$ è uniforme sull'alfabeto: $P_x(a)=\frac1M$ per ogni $a$.

Entropia congiunta e condizionata e informazione mutua

Definizione (entropia congiunta). $$H(x,y)=E\left[i_{x,y}(x,y)\right]=\sum_{a,b}P_{x,y}(a,b)\log_2\frac1{P_{x,y}(a,b)}.$$

Proprietà. Se $y=f(x)$ con $f$ funzione ordinaria (a ogni $a$ corrisponde un solo $b=f(a)$), allora $H(x,y)=H(x)$.

Proprietà. Se $x$ e $y$ sono indipendenti, $H(x,y)=H(x)+H(y)$.

Teorema. In generale $H(x,y)\le H(x)+H(y)$, con disuguaglianza stretta se $x$ e $y$ non sono indipendenti. Inoltre $$\boxed{\max\{H(x),H(y)\}\le H(x,y)\le H(x)+H(y)\le\log_2M_x+\log_2M_y,}$$ dove $M_x,M_y$ sono le cardinalità degli alfabeti.

Definizione. $H(x|y)$ è la media di $H(x|y=b)$ sui valori di $y$: $$\boxed{H(x|y)=E_y\left[H(x|y=y)\right]=\sum_bP_y(b)\,H(x|y=b)=\sum_{a,b}P_{x,y}(a,b)\log_2\frac1{P_{x|y}(a|b)}.}$$

Definizione (informazione mutua). $$\boxed{I(x;y)=H(x)+H(y)-H(x,y)=H(x)-H(x|y)=H(y)-H(y|x)=I(y;x).}$$

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

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

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

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

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

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

Codici a prefisso - Kraft-McMillan e limiti di Shannon sulla lunghezza media

Definizione (lunghezza media delle parole di codice). $$L_y=E\left[l(\mathcal M_s(\underline x))\right]=\sum_{\underline a\in\mathcal D_x}l\left(\mathcal M_s(\underline a)\right)\,p_{\underline x}(\underline a)\quad[\text{simboli di codice per parola}].$$

Definizione. In un codice a prefisso nessuna parola di codice è il prefisso (la parte iniziale) di un'altra parola.

Teorema (Kraft-McMillan). Sia $M_y$ la cardinalità dell'alfabeto di codice.

1. (Condizione necessaria.) Per ogni codificatore decodificabile senza perdite, con parole di lunghezza $l_1,\dots,l_N$, $$\boxed{\sum_{i=1}^N\frac1{M_y^{\,l_i}}\le1.}$$
2. (Esistenza.) Se $l_1,\dots,l_N$ sono interi che soddisfano la disuguaglianza (con $M_y$ intero), esiste un codice a prefisso con alfabeto di cardinalità $M_y$ e parole di lunghezza $l_1,\dots,l_N$.

Teorema (Shannon, codifica di sorgente). Per un codificatore senza perdite con alfabeto di cardinalità $M_y$:

1. (Limite inferiore.) Ogni codice decodificabile ha $\displaystyle L_y\ge\frac{H(\underline x)}{\log_2M_y}$.
2. (Esistenza.) Esiste un codice a prefisso con $\displaystyle L_y<\frac{H(\underline x)}{\log_2M_y}+1$.

In sintesi, esiste sempre un codice a prefisso con $$\boxed{\frac{H(\underline x)}{\log_2M_y}\le L_y<\frac{H(\underline x)}{\log_2M_y}+1.}$$ Per il codice binario ($M_y=2$): $H(\underline x)\le L_y<H(\underline x)+1$, in bit per parola.

Codici di Shannon, Huffman ed Elias e codifica aritmetica

Definizione. Per una sorgente con parole $\underline a_i\in\mathcal D_x$ di probabilità $p_i$, il codice di Shannon ha lunghezze $$l_i=\left\lceil\log_{1/M_y}p_i\right\rceil=\left\lceil\log_{M_y}\frac1{p_i}\right\rceil,\qquad\text{per }M_y=2:\ l_i=\left\lceil-\log_2p_i\right\rceil=\left\lceil i(\underline a_i)\right\rceil.$$

Definizione. Un codice di sorgente è ottimo se ha la lunghezza media minima tra i codici a prefisso per quella sorgente.

Teorema 1. In un codice a prefisso ottimo le parole di probabilità più bassa hanno lunghezza maggiore o uguale: se $p(x_1)<p(x_2)$ allora $l(y_1)\ge l(y_2)$.

Teorema 2. Nel dizionario di un codice a prefisso ottimo ci sono almeno due parole di lunghezza massima $\underline b'$ e $\underline b''$ che differiscono solo nell'ultimo simbolo.