Esercizio - Canale binario simmetrico e codici di canale (domande ed esercizi del corso)

Teoria: Metriche e prestazioni di rete per i servizi multimedialiUna rete è una pila di livelli: ogni livello offre un servizio al superiore tramite un'interfaccia e dialoga con il livello pari con un protocollo; il pacchetto di un livello è il payload del livello inferiore ($\mathrm{PDU}n=\mathrm{PCI}n+\mathrm{SDU}n$), con efficienza $\eta=\frac{|\mathrm{SDU}n|}{|\mathrm{PDU}n|}$. Metriche: bit-rate $R_0$ (livello fisico) $\ge$ throughput $S$ $\ge$ goodput (throughput a lungo termine a livello applicazione). Ritardo nodale $d=d{proc}+d{queue}+d{trans}+d{prop}$ con $d{trans}=\frac LR$ e $d_{prop}=\frac xc$; ritardo end-to-end = somma dei nodali; jitter = variabilità del ritardo; BDP $=S\cdot\mathrm{RTT}$ (con il bit-rate minimo del percorso). Affidabilità: nel canale binario simmetrico $\mathrm{PER}=1-(1-\varepsilon)^L$ e $P(\ell)=\binom L\ell\varepsilon^\ell(1-\varepsilon)^{L-\ell}$; codici di canale $R=\frac kn$, parità, Hamming, interleaving per i burst; perdite per errori o congestione, $\mathrm{PDR}=1-P_{\text{LOSS}}$.Metriche e prestazioni di rete per i servizi multimediali → (BSC, PER, codici a blocchi, parità, Hamming, interleaving). Fonte: domande a risposta multipla ed esempi di preparazione, esercizio delle slide del corso di Reti di Calcolatori, Ing. Informatica UniPD 2025-26. Conti verificati in Python. Si richiamano: $\mathrm{PER}=1-(1-\varepsilon)^L$; probabilità di $\ell$ errori su $L'$ bit $P(\ell)=\binom{L'}\ell\varepsilon^\ell(1-\varepsilon)^{L'-\ell}$; messaggio di $N$ pacchetti corretto con probabilità $(1-\mathrm{PER})^N$; tempo di trasmissione di $N$ pacchetti da $L$ bit a $R_0$: $\frac{NL}{R_0}$.

1. BSC senza codice

Domanda 1 (A). Una sorgente produce pacchetti di $L=1000$ bit (header inclusi) e li invia su un BSC con $\varepsilon=10^{-6}$ e bit-rate $R_0=5$ Mbit/s. Quale affermazione è vera? (a) il ritardo di trasmissione di un messaggio di 750 pacchetti è 150 ms, (b) il PER è all'incirca l'1%, (c) la probabilità che il messaggio sia ricevuto con zero errori è superiore al 50%.

• (a) $\frac{750\cdot1000}{5\cdot10^6}=0{,}15$ s $=150$ ms: vera.
• (b) $\mathrm{PER}=1-(1-10^{-6})^{1000}\approx9{,}995\cdot10^{-4}\approx0{,}1\%$: falsa (un fattore 10 sotto l'1%). Approssimazione: $L\varepsilon=10^{-3}$.
• (c) $(1-\mathrm{PER})^{750}=(0{,}9990005)^{750}\approx0{,}472=47{,}2\%$: falsa, è sotto il 50%. (Controllo: $e^{-L\varepsilon N}=e^{-0{,}75}=0{,}472$.)

Domanda 2 (preparazione). Un pacchetto di 2000 bit e $\varepsilon=10^{-5}$: PER? (a) $\approx2\%$, (b) $0{,}2\%$, (c) $20\%$, (d) $0{,}02\%$. $\mathrm{PER}=1-(1-10^{-5})^{2000}=0{,}0198\approx2\%$: (a). Con $L\varepsilon=0{,}02$ le altre sono errori di una o due potenze di 10.

Esercizio 3 (slide, parte senza codice). $L=500$ bit, $\varepsilon=2\cdot10^{-6}$, $R_0=10$ Mbit/s, messaggio di $N=1000$ pacchetti.

• Q1, tempo: $T=\frac{1000\cdot500}{10^7}=50$ ms.
• Q2, PER: $1-(1-2\cdot10^{-6})^{500}=9{,}995\cdot10^{-4}\approx0{,}100\%$.
• Q3, messaggio corretto: $(1-\mathrm{PER})^{1000}=0{,}3679=36{,}8\%$ (infatti $L\varepsilon N=1$ e $e^{-1}=0{,}368$).

2. BSC con un codice che corregge un errore

Domanda 4 (A). Come nella domanda 1 ma si usa un codice di correzione degli errori con $R=\frac{500}{511}$ (rapporto $k/n$); il codice può correggere un bit errato e rilevarne due; probabilità che $\ell$ bit su $L'$ siano errati $P(\ell)=\binom{L'}\ell\varepsilon^\ell(1-\varepsilon)^{L'-\ell}$. Quale affermazione è falsa? (a) il ritardo di trasmissione di un messaggio di 750 pacchetti è 150 ms, (b) il PER (probabilità che un pacchetto ricevuto non sia decodificabile) è $\approx5{,}2\cdot10^{-7}$, (c) la probabilità che il messaggio sia ricevuto correttamente è $\approx99{,}9609\%$.

• Dimensione del pacchetto codificato: $L'=1000\cdot\frac{511}{500}=1022$ bit (si aggiungono 22 bit di protezione).
• (a) $\frac{750\cdot1022}{5\cdot10^6}=0{,}1533$ s $=153{,}3$ ms: falsa (150 ms è il tempo senza codice; il codice allunga la trasmissione perché ogni pacchetto è più lungo). È l'opzione cercata.
• (b) Un pacchetto è decodificato correttamente con 0 o 1 errore: $\mathrm{PER}=1-P(0)-P(1)=5{,}2138\cdot10^{-7}$: vera. Approssimazione: con tre o più errori trascurabili, $\mathrm{PER}\approx P(2)=\binom{1022}2\varepsilon^2=521\,731\cdot10^{-12}=5{,}21\cdot10^{-7}$.
• (c) $(1-\mathrm{PER})^{750}=(1-5{,}2138\cdot10^{-7})^{750}=0{,}999609=99{,}9609\%$: vera.

Esercizio 5 (slide, parte con il codice). $L=500$ bit, $\varepsilon=2\cdot10^{-6}$, $R=\frac{500}{511}$, $N=1000$, 10 Mbit/s. Il codice corregge 1 bit e rileva 2.

• Q4, tempo: $T=\frac{1000\cdot511}{10^7}=51{,}1$ ms (il 2,2% in più).
• Q5, PER: la probabilità di ricevere correttamente è $P(0)+P(1)$ con $L'=511$: $P(0)=0{,}9989785$, $P(1)=1{,}020958\cdot10^{-3}$, quindi $\mathrm{PER}=1-P(0)-P(1)=5{,}2087\cdot10^{-7}$ (la slide: $5{,}20866\cdot10^{-7}$). Con l'approssimazione $P(2)=\binom{511}{2}\varepsilon^2=5{,}2069\cdot10^{-7}$: molto vicina.
• Q6, messaggio corretto: $(1-5{,}2087\cdot10^{-7})^{1000}=0{,}999479=99{,}9479\%$.
• Conclusione: con un overhead di $\frac{11}{511}\approx2{,}2\%$ il PER scende da $10^{-3}$ a $5{,}2\cdot10^{-7}$ e la probabilità di ricevere il messaggio senza errori sale da $36{,}8\%$ a $99{,}95\%$. (La slide dice "scende da $10^{-4}$", ma il PER senza codice calcolato in Q2 è $0{,}100\%=10^{-3}$: è un refuso.) Inoltre senza codice un errore su bit non verrebbe rilevato; con il codice sì. La probabilità di avere più di 2 errori vale $1-\sum_{\ell=0}^2P(\ell)=1{,}77\cdot10^{-10}$: i pacchetti con tre o più errori, che sfuggirebbero alla rilevazione, sono meno di 2 ogni dieci miliardi.

3. Parità e codice di Hamming

Domanda 6 (A, teoria). (1) I codici a controllo di parità: (a) permettono di rilevare ed eventualmente correggere errori, (b) permettono solo di correggere. (2) Il bit-rate $R=\frac kn$ in un codice di canale: (a) controlla il compromesso tra overhead e capacità di rilevamento e correzione, (b) controlla il compromesso tra complessità ed efficacia, (c) permette di far fronte ai burst se scelto adeguatamente. (3) I burst di errori si controllano efficacemente (seppur introducendo ritardo): (a) con l'interleaving, (b) con codici convoluzionali, (c) con codici a bit-rate molto alto.

Risposte e perché: (1) (a) un codice di parità (un singolo bit) rileva, e con strutture più ricche (Hamming) corregge; (b) è falsa perché la sola parità non corregge. (2) (a): $R=\frac kn$ misura il rapporto dati/totale: più è vicino a 1, meno overhead ma meno protezione; (b) la complessità non dipende da $R$; (c) non è il valore di $R$ che combatte i burst. (3) (a): l'interleaving distribuisce un burst su più blocchi (introduce ritardo); (b) i convoluzionali non servono contro i burst e (c) un rapporto $R$ vicino a 1 significa meno protezione.

Esercizio 7 (parità, costruito). Blocco $1011001$ ($k=7$): numero di 1 $=4$, quindi $b_8=0$ (somma modulo 2 $=0$): blocco trasmesso $10110010$. Se si riceve $10110110$ (un errore) la somma è $1$: errore rilevato. Se si ricevono due errori, per esempio $10000010$ (bit 3 e bit 4 cambiati: la somma resta 0), non si rileva nulla: un numero pari di errori sfugge. $R=\frac78=0{,}875$, overhead $\frac18=12{,}5\%$.

Esercizio 8 (Hamming, costruito). Con le regole $b_5=b_1\oplus b_2\oplus b_4$, $b_6=b_1\oplus b_3\oplus b_4$, $b_7=b_2\oplus b_3\oplus b_4$ si codifica $x=1011$: $b_5=1\oplus0\oplus1=0$, $b_6=1\oplus1\oplus1=1$, $b_7=0\oplus1\oplus1=0$, quindi $y=1011\,010$. Si riceve $\hat y=1001\,010$ (cambiato il bit 3). Controlli: $\{1,2,4,5\}$: $1+0+1+0=0$ OK; $\{1,3,4,6\}$: $1+0+1+1=1$ non OK; $\{2,3,4,7\}$: $0+0+1+0=1$ non OK. Il bit errato sta nell'intersezione dei controlli che falliscono, $\{1,3,4,6\}\cap\{2,3,4,7\}=\{3,4\}$; il 4 appartiene anche al controllo $\{1,2,4,5\}$ che è OK, quindi è il bit 3: si corregge $1001\to1011$. Dati recuperati: $1011$ ✓.

Esercizio 9 (interleaving, costruito). I 21 bit $1,\dots,21$ sono scritti per righe in una matrice $3\times7$ (righe $1..7$, $8..14$, $15..21$) e trasmessi per colonne: ordine di trasmissione $1,8,15,2,9,16,3,10,17,\dots$. Ogni riga è un blocco del codice (7,4) (corregge un errore).

• Burst di 3 bit consecutivi sul canale (per esempio i primi tre, $1,8,15$): dopo il de-interleaving un solo errore per riga: tutti correggibili.
• Burst di 4 bit consecutivi ($1,8,15,2$): i bit $1$ e $2$ cadono nella stessa riga (due errori nello stesso blocco): il codice (7,4) non li corregge. Quindi con $3$ righe l'interleaving corregge burst fino a lunghezza 3: la profondità deve essere almeno la lunghezza massima del burst (a prezzo di ritardo: bisogna riempire la matrice prima di trasmettere).

Errori tipici

• Valutare il PER come $1-\varepsilon^L$ (è $1-(1-\varepsilon)^L$) o come $\varepsilon$ (probabilità di un solo bit).
• Dimenticare di allungare il pacchetto con la ridondanza ($L'=L/R$): il tempo di trasmissione cresce del $\frac1R$.
• Usare $L$ al posto di $L'$ nelle probabilità $P(\ell)$ quando c'è un codice.
• Considerare corretto il pacchetto solo con 0 errori in presenza di un codice che ne corregge 1: si sommano $P(0)$ e $P(1)$.
• Pensare che il codice di parità rilevi anche gli errori in numero pari.