Canale binario simmetrico, codifica di Gray e probabilità di bit

Il demodulatore decide un simbolo (Decisione ottima - criteri MAP e MLIl ricevitore osserva il vettore $\mathbf r$ e deve stimare il simbolo trasmesso $a_0$: lo spazio $\mathbb R^I$ si divide in $M$ regioni di decisione $\mathcal R_j$. La probabilità di decisione corretta è $P[C]=\sum_j\int_{\mathcal R_j}D_j(\boldsymbol\rho),d\boldsymbol\rho$ con $D_j=p_{\mathbf r|a_0}(\boldsymbol\rho|j),p_j$ e si massimizza assegnando ogni $\boldsymbol\rho$ alla regione con $D_j$ più alto: criterio MAP (massimo a posteriori, ottimo). Il criterio ML ($\arg\max_jp_{\mathbf r|a_0}(\boldsymbol\rho|j)$) ignora le probabilità a priori e coincide con MAP per simboli equiprobabili. Il criterio MD (minima distanza, $\arg\min\lVert\boldsymbol\rho-\mathbf s_j\rVert$) coincide con ML se il rumore è AWGN, quindi con simboli equiprobabili e AWGN è ottimo.Decisione ottima - criteri MAP e ML →) e da lì si risale ai bit con la mappa di bit. La probabilità d'errore di simbolo $P[E]$ (Probabilità d'errore e funzione QPer due segnali di energie $E_1,E_2$ con coefficiente di correlazione $\rho=\frac{\langle s_1,s_2\rangle}{\sqrt{E_1E_2}}$ la distanza è $d_{12}=\sqrt{E_1+E_2-2\rho\sqrt{E_1E_2}}$ e, con rumore AWGN, simboli equiprobabili e criterio MD, $P[E]=Q\left(\frac{d_{12}}{2\sigma_I}\right)=Q\left(\sqrt{\frac{E_s(1-\rho)}{N_0}}\right)$ con $\sigma_I^2=\frac{N_0}2$ e $Q$ la coda della gaussiana. Il caso antipodale ($\rho=-1$) dà $Q\left(\sqrt{\frac{2E_s}{N_0}}\right)$, l'ortogonale ($\rho=0$) $Q\left(\sqrt{\frac{E_s}{N_0}}\right)$: 3 dB peggio. Con $M>2$ segnali si usano limiti: $\frac{N^*}M Q\left(\frac{d_{min}}{2\sigma_I}\right)\le P[E]\le(M-1)Q\left(\frac{d_{min}}{2\sigma_I}\right)$ (union bound); la probabilità dipende solo da $\frac{E_s}{N_0}$, cioè dall'SNR.Probabilità d'errore e funzione Q →) non è però la grandezza che interessa agli strati superiori della rete: questi vedono una sequenza di bit, e vogliono sapere con quale probabilità un bit è sbagliato. Questa nota spiega il passaggio, la scelta della mappa di bit e il modello di canale che ne risulta. Versione per Ing. Elettronica: Canale numerico, ISI e codifica di GrayNella catena bit $\to$ BMAP $\to$ modulatore $\to$ canale $\to$ proiezione $\to$ rivelatore $\to$ IMAP, un simbolo da $b=\log_2M$ bit dura $T=T_b\log_2M$. Per non avere interferenza intersimbolo (ISI) le forme d'onda devono essere ortogonali alle loro traslate di $kT$: $\langle\phi_i(t),\phi_j(t-kT)\rangle=0$ per $k\ne0$ (per esempio un impulso che dura al più $T$). Il canale numerico equivalente (bit in ingresso, bit decisi in uscita) è un canale binario simmetrico di probabilità $P_{bit}$; con la codifica di Gray simboli adiacenti differiscono in un solo bit e $P_{bit}\approx\frac{P[E]}{\log_2M}$.Canale numerico, ISI e codifica di Gray →.

1. Il canale binario simmetrico senza memoria (BSC)

Si descrive l'insieme modulatore + canale + demodulatore come un canale numerico che prende in ingresso bit e restituisce bit. Il modello più usato, soprattutto agli strati alti, è il canale binario simmetrico senza memoria (memoryless binary symmetric channel, BSC): è un'approssimazione ingegneristica, ma molto comoda.

• Binario: ingresso e uscita sono bit $\{0,1\}$;
• Simmetrico: ogni bit viene sbagliato (nei due versi, $0\to1$ e $1\to0$) con la stessa probabilità $P_{bit}$, e ricevuto giusto con probabilità $1-P_{bit}$;
• Senza memoria: gli errori sui diversi bit sono indipendenti.

L'ipotesi si giustifica per la modulazione binaria vera e propria (dove l'errore $1\to2$ e $2\to1$ ha la stessa probabilità $Q(\cdot)$ per simmetria).

Esempio. Con $P_{bit}=10^{-6}$ la probabilità di ricevere la sequenza $010$ avendo trasmesso $111$ è: primo bit sbagliato, secondo giusto, terzo sbagliato, $P_{bit}(1-P_{bit})P_{bit}=10^{-12}(1-10^{-6})\approx10^{-12}$ (è una sequenza precisa, non un conteggio di errori).

Canale numerico generale. Il BSC è un caso speciale di canale numerico $\mathcal A\to\mathcal A$, in cui ogni simbolo $j$ viene ricevuto come $k$ con una probabilità condizionata $P_{j\to k}=P_{k|j}$ (tutte le frecce di un diagramma ingresso-uscita, tutte diverse in generale; per esempio per un simbolo interno di una PAM gli errori verso i due vicini sono gli unici che contano).

2. Differenza tra $P[E]$ e $P_{bit}$

Se si raggruppano i bit in blocchi di $n=\log_2M$ (modulazione $M$-aria), l'evento "simbolo sbagliato" $E$ si ha quando almeno uno dei bit del gruppo è sbagliato; un bit può essere giusto anche se il gruppo contiene errori. Visto come $n$ trasmissioni su un BSC: $$P[E]=1-P[C]=1-(1-P_{bit})^n\ \approx\ n\,P_{bit}\quad(\text{per }P_{bit}\ll1),\qquad P_{bit}\le P[E].$$ (Sviluppo di Taylor: $(1-p)^n=1-np+O(p^2)$.) Di conseguenza, per un'applicazione che vede una sequenza di bit, $P_{bit}$ si chiama anche bit error rate (BER), con un'impostazione più sperimentale che matematica. Una modulazione $M$-aria ha una $P[E]$ più alta di quella binaria (si sbaglia più facilmente tra tanti simboli), ma in compenso in ogni tempo di simbolo si trasmettono più bit, $R_b=\frac{\log_2M}T$ (Spazio dei segnali e Gram-SchmidtNella modulazione digitale ogni simbolo di un alfabeto di $M$ elementi è associato a una forma d'onda $s_j(t)$ di energia finita, trasmessa in un tempo di simbolo $T$. Le forme d'onda sono elementi dello spazio $\mathcal L^2$ con prodotto scalare $\langle x,y\rangle=\int xy^*,dt$ e energia $E_x=\lVert x\rVert^2$; con una base ortonormale ${\varphi_i}_{i=1}^I$ ($I\le M$, trovata con Gram-Schmidt) ogni segnale è un punto $\mathbf s_j=[\langle s_j,\varphi_i\rangle]_i$ e l'insieme dei punti è la costellazione. Il rumore bianco gaussiano ha componenti sulla base indipendenti $\mathcal N(0,\frac{N_0}2)$ (la parte fuori dallo spazio dei segnali è irrilevante), quindi il ricevuto è $\mathbf r=\mathbf s_j+\mathbf w$.Spazio dei segnali e Gram-Schmidt →).

3. Dalla probabilità di simbolo a quella di bit: la distanza di Hamming

Il passaggio inverso ($P[E]\to P_{bit}$) dipende da come sono assegnati i bit ai simboli (la mappa di bit). Se tra due parole di bit $\mathbf b,\mathbf c\in\mathbb Z_2^n$ ci sono $q$ bit diversi, quando si sbaglia il simbolo scambiando l'uno con l'altro una frazione $\frac qn$ dei bit del gruppo è sbagliata: è indifferente quali, basta il numero. Il numero di bit diversi è la distanza di Hamming $$d_H(\mathbf b,\mathbf c)=\#\{i:\ b_i\ne c_i\}=\sum_{i=1}^nb_i\oplus c_i\qquad(\oplus=\text{XOR, somma modulo 2}).$$ Con $\mathbf c_j$ la parola di bit del simbolo $j$ e $P_{j|k}$ la probabilità di decidere $j$ avendo trasmesso $k$ ($j\ne k$): $$\boxed{P_{bit}=\sum_{k=1}^M\sum_{j\ne k}p_k\,P_{j|k}\,\frac{d_H(\mathbf c_j,\mathbf c_k)}{\log_2M}}$$ (è una media pesata: ogni tipo di errore di simbolo contribuisce con la sua probabilità e con la frazione di bit sbagliati che comporta). Se tutti gli $\frac{d_H}{\log_2M}$ fossero uguali a $1$ si avrebbe $P_{bit}=P[E]$. Chiaramente la mappa va scelta con saggezza: distanze di Hamming piccole per le coppie di simboli con alta probabilità di confusione, e come principio generale le coppie più probabili sono i simboli vicini nella costellazione.

4. La codifica di Gray

Per "codifica" qui si intende la mappa di bit. Una rappresentazione di $M=2^n$ simboli con stringhe di $n$ bit è una codifica di Gray se $$d_H\left(\mathbf c_j,\mathbf c_{j+1}\right)=1\qquad\forall j=1,\dots,M-1,$$ cioè simboli adiacenti sono codificati con parole che differiscono per un solo bit. È una proprietà, non una definizione univoca: esistono molte codifiche di Gray. Una si ottiene con la procedura "a specchio" (reflected binary code): si parte da $0,1$; si riflette la lista e si aggiunge $0$ davanti alla prima metà e $1$ davanti alla seconda:

(per $n=3$: $000,001,011,010,110,111,101,100$). Per le proprietà cicliche, anche la distanza tra il primo e l'ultimo è $d_H=1$ ($000$ e $100$): importante per la PSK, dove i simboli stanno su una circonferenza e il primo è adiacente all'ultimo.

Perché serve. Quando il rumore è moderato, l'errore di simbolo più probabile è quello verso un simbolo adiacente (il punto ricevuto esce dalla regione attraversando il confine più vicino); verso un simbolo non adiacente la probabilità è molto più piccola, perché la distanza è maggiore e la $Q$ cala rapidamente ($\approx Q\left(3\frac{d}{2\sigma_I}\right)\ll Q\left(\frac d{2\sigma_I}\right)$). Con Gray ogni errore verso un vicino cambia un solo bit: $$\boxed{P_{bit}\approx\frac{P[E]}{\log_2M}\qquad\text{(codifica di Gray, }\tfrac{E_s}{N_0}\text{ non troppo basso)}}$$ Si trascurano gli errori verso simboli non adiacenti, che hanno probabilità $O(Q^2)$ o comunque molto minore; per questo l'approssimazione richiede implicitamente $P_{bit}$ piccola (è un'ipotesi nascosta, ma c'è). Con $P_{bit}\approx P[E]/\log_2M$ ci si riconduce a un modello BSC.

Esempio ($8$-PAM, $\frac{E_s}{N_0}=20$ dB). $P[E]=2\left(1-\frac18\right)Q\left(\sqrt{\frac{6\cdot100}{63}}\right)=1{,}75\,Q(3{,}086)=1{,}77\cdot10^{-3}$ (Modulazioni PAM, PSK, QAM e FSKLe modulazioni pratiche usano un solo impulso base $h(t)$ (energia $E_h$) e coefficienti scelti in un insieme regolare. PAM: $s_n=\alpha_nh(t)$, $\alpha_n\in{-M+1,\dots,M-1}$, punti su una retta, $d_{min}=2\sqrt{E_h}$, $E_s=\frac{M^2-1}3E_h$, $P[E]=2\left(1-\frac1M\right)Q\left(\sqrt{\frac{6E_s}{(M^2-1)N_0}}\right)$. QAM: coefficienti complessi su due portanti in quadratura, base di dimensione 2, per $M=L^2$ $E_s=\frac{M-1}3E_h$ e $P[E]\approx4\left(1-\frac1{\sqrt M}\right)Q\left(\sqrt{\frac{3E_s}{(M-1)N_0}}\right)$. PSK: ampiezza costante, fasi $\theta_n=\frac{(2n-1)\pi}M$, punti su una circonferenza, $E_s=\frac{E_h}2$, $P[E]\approx2Q\left(\sqrt{\frac{2E_s}{N_0}}\sin\frac\pi M\right)$. FSK: due sinusoidi a frequenze diverse, $\rho\approx\operatorname{sinc}(4f_dT)$. Con la codifica di Gray $P_{bit}\approx\frac{P[E]}{\log_2M}$.Modulazioni PAM, PSK, QAM e FSK →). Con la codifica di Gray ($000,001,011,010,110,111,101,100$ dal punto più a sinistra) $P_{bit}=\frac{1{,}77\cdot10^{-3}}3=5{,}9\cdot10^{-4}$; il calcolo esatto, sommando per ogni coppia di simboli $P_{j|k}\frac{d_H}3$, dà $5{,}916\cdot10^{-4}$, praticamente identico. Con la mappa binaria naturale ($000,001,010,\dots,111$) si avrebbe $9{,}3\cdot10^{-4}$ (il $57\%$ in più): per esempio i simboli $011$ e $100$ sono adiacenti ma differiscono in tre bit.

Costellazioni a due dimensioni. Per la QAM si fa una "doppia Gray": gruppi di bit separati per la componente in fase e per quella in quadratura, ognuno con una Gray lungo il proprio asse, in modo che i vicini orizzontali e verticali differiscano di un solo bit (Modulazioni PAM, PSK, QAM e FSKLe modulazioni pratiche usano un solo impulso base $h(t)$ (energia $E_h$) e coefficienti scelti in un insieme regolare. PAM: $s_n=\alpha_nh(t)$, $\alpha_n\in{-M+1,\dots,M-1}$, punti su una retta, $d_{min}=2\sqrt{E_h}$, $E_s=\frac{M^2-1}3E_h$, $P[E]=2\left(1-\frac1M\right)Q\left(\sqrt{\frac{6E_s}{(M^2-1)N_0}}\right)$. QAM: coefficienti complessi su due portanti in quadratura, base di dimensione 2, per $M=L^2$ $E_s=\frac{M-1}3E_h$ e $P[E]\approx4\left(1-\frac1{\sqrt M}\right)Q\left(\sqrt{\frac{3E_s}{(M-1)N_0}}\right)$. PSK: ampiezza costante, fasi $\theta_n=\frac{(2n-1)\pi}M$, punti su una circonferenza, $E_s=\frac{E_h}2$, $P[E]\approx2Q\left(\sqrt{\frac{2E_s}{N_0}}\sin\frac\pi M\right)$. FSK: due sinusoidi a frequenze diverse, $\rho\approx\operatorname{sinc}(4f_dT)$. Con la codifica di Gray $P_{bit}\approx\frac{P[E]}{\log_2M}$.Modulazioni PAM, PSK, QAM e FSK →). Per la PSK si usa una Gray ciclica lungo la circonferenza.

5. Probabilità di bit senza Gray: ortogonale e biortogonale

Quando i simboli sono equidistanti (modulazione ortogonale) tutti gli errori di simbolo sono equiprobabili: dato un simbolo trasmesso, gli altri $M-1$ sono ricevuti con la stessa probabilità, e la mappa di bit non può farci niente. In $n=\log_2M$ bit, per ogni posizione di bit, esattamente $2^{n-1}=\frac M2$ delle $M-1$ parole diverse differiscono in quel bit, quindi la frazione di bit sbagliati dato un errore di simbolo è $$\frac{P_{bit}}{P[E]}=\frac{M/2}{M-1}=\frac M{2(M-1)},$$ e vale $\frac23$ per $M=4$, $\frac47$ per $M=8$, e tende a $\frac12$ per $M$ grande (un simbolo sbagliato "a caso" ha metà dei bit sbagliati).

Esempio ($4$-aria ortogonale, esercizio di Bressanone). Quattro segnali ortogonali con parole $00,01,10,11$: i tre errori $1\to2$, $1\to3$, $1\to4$ sono equiprobabili. Numero medio di bit sbagliati: $\frac23\cdot1+\frac13\cdot2=\frac43$ su $2$, cioè una frazione $\frac23$. Con $P[E]\simeq3Q\left(\sqrt{\frac{E_s}{N_0}}\right)$ (union bound con $M-1=3$): $$P_{bit}=\frac23P[E]=2\,Q\left(\sqrt{\frac{E_s}{N_0}}\right).$$

Esempio ($4$-aria biortogonale). Segnali $\pm s_1,\pm s_2$ (due ortogonali e i loro opposti): errori verso i due ortogonali (vicini a $d_{min}$) molto più probabili di quello verso l'opposto. Con una mappa di Gray ciclica ($s_1=00$, $s_3=01$, $s_2=11$, $s_4=10$) i due vicini ortogonali di ogni simbolo sono a distanza di Hamming $1$, mentre l'opposto (il più lontano) ha la parola complementare, a distanza $2$: è la scelta "furba", i simboli più lontani hanno la sequenza più diversa. Con $P[E]\simeq(M-2)\,Q\left(\sqrt{\frac{E_s}{N_0}}\right)=2Q\left(\sqrt{\frac{E_s}{N_0}}\right)$ si ha $$P_{bit}\simeq\frac{P[E]}2=Q\left(\sqrt{\frac{E_s}{N_0}}\right).$$ Per i casi di $4$-PPM ortogonale e biortogonale con numeri si veda Esercizio - quaternaria ortogonale e biortogonale con impulsi rettangolari e Esercizio - quaternaria ortogonale e biortogonale, probabilità di bit.

Errori comuni

• Identificare $P[E]$ e $P_{bit}$: sono uguali solo con $M=2$ (ma $P_{bit}\le P[E]\le nP_{bit}$ in generale).
• Usare $P_{bit}\approx\frac{P[E]}{\log_2M}$ senza la codifica di Gray, o per SNR così bassi che gli errori verso simboli non adiacenti non sono più trascurabili.
• Sbagliare la sequenza di Gray: non è la sequenza binaria naturale; ciò che conta è che i vicini differiscano in un bit (anche tra il primo e l'ultimo, per la PSK).
• Dimenticare che per la modulazione ortogonale tutti gli errori sono equiprobabili e vale $\frac{M}{2(M-1)}$.
• Moltiplicare per $\binom nk$ per una sequenza precisa: la probabilità di una sequenza precisa è $P_{bit}^k(1-P_{bit})^{n-k}$, senza coefficiente binomiale.