Esercizio - Test del DNA con 4, 5 e 7 provette

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (scheda "Channel coding"). Un colpevole ha lasciato il DNA sulla scena del crimine. La polizia individua $16$ sospettati e uno è sicuramente il colpevole. Un agente deve prelevare un tampone di DNA da ogni sospettato: il tampone si mette in una provetta, che si inserisce nell'analizzatore; se nella provetta c'è il DNA del colpevole, una spia si accende. L'agente ha solo $4$ provette, utilizzabili nell'analizzatore una volta sola. a. C'è un modo per individuare il colpevole? b. I test sono inaffidabili: ogni provetta ha probabilità di errore $P_{err}=5\,\%$ (la spia non si accende o non si spegne quando dovrebbe). Qual è la probabilità che un sospettato sia accusato ingiustamente? c. L'agente trova $D$ provette in più da usare insieme alle prime $4$. Due modi: (i) evitare che un innocente sia accusato ingiustamente scartando i test dubbi come inconcludenti; (ii) trovare comunque il colpevole, ma con probabilità di successo maggiore. A cosa corrispondono? Quando falliscono? d. Cosa succede se $D=1$ in (i)? e. Se $D=3$ in (i)? f. Se $D=3$ in (ii)?

Teoria usata: Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione →, Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →, Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →.

a. Una parola di codice per ogni sospettato

L'idea chiave: si può mettere il DNA di più sospettati nella stessa provetta, e la spia si accende se c'è quello del colpevole. Si assegna a ogni sospettato una stringa binaria di $4$ bit $b_1b_2b_3b_4$: sospettato $1$: $0000$, sospettato $2$: $0001$, $\dots$, sospettato $16$: $1111$ ($2^4=16$ stringhe). Il DNA del sospettato va nella provetta $j$ se $b_j=1$ (non va se $b_j=0$). Se il colpevole è il sospettato con stringa $\mathbf b$, la spia $j$ si accende proprio se $b_j=1$: le luci lette (accesa $=1$) sono la stringa del colpevole. Per esempio le luci $0110$ indicano il sospettato $7$ ($0110_2=6$, e si parte da $0000\leftrightarrow$ sospettato $1$).

Sì: con $4$ provette, senza errori, si trova il colpevole. È un codice $(4,4)$: nessuna ridondanza, $d_{min}=1$.

b. Con le provette inaffidabili

Ogni provetta è un BSC senza memoria con $P=0{,}05$ (la spia sbaglia con probabilità $P_{err}$ in un verso o nell'altro). Si trova il colpevole solo se nessuna delle $4$ letture sbaglia: $P[0\ \text{errori}]=(1-P_{err})^4=0{,}95^4=0{,}8145$. Se anche una sola lettura sbaglia si legge un'altra stringa di $4$ bit, che è comunque una stringa valida ($d_{min}=1$, ogni stringa è una parola): si accusa un altro sospettato. $$P[\text{innocente accusato}]=1-(1-P_{err})^4=1-0{,}95^4=0{,}1855\simeq18{,}6\,\%.$$

c. Provette aggiuntive: rivelazione o correzione

Le $D$ provette in più sono bit di ridondanza: con $n=4+D$ provette si usa un codice a blocco $(4+D,4)$. I due modi del testo corrispondono ai due usi di un codice:

• (i) rivelazione d'errore: se la configurazione delle luci non è una parola di codice il test è inconcludente (si scarta). Fallisce solo se l'errore non è rivelato, cioè se i bit sbagliati trasformano la parola trasmessa in un'altra parola di codice ($P_{undetected}$).
• (ii) correzione d'errore: si decodifica a distanza minima, sempre una risposta. Fallisce quando i bit sbagliati portano fuori dalla regione di decisione $\mathcal R_{\boldsymbol\beta}$ della parola trasmessa.

d. $D=1$ in (i): codice a parità $(5,4)$

Con $5$ provette si usa un bit di parità: la quinta provetta contiene il DNA dei sospettati la cui stringa $b_1b_2b_3b_4$ ha parità $p=b_1\oplus b_2\oplus b_3\oplus b_4=1$ (sospettato $1$: $00000$, sospettato $2$: $00011$, $\dots$, sospettato $16$: $11110$). Il codice ha $d_{min}=2$: rivela $1$ errore ma non lo corregge.

Un innocente viene ancora accusato solo se l'errore non è rivelato: un codice di parità non rivela nessun numero pari di errori; con due errori fallisce sempre. Il caso dominante è quello con $2$ errori: $$P_{undetected}\simeq P[2\ \text{errori su }5]=\binom52P_{err}^2(1-P_{err})^3=10\cdot0{,}0025\cdot0{,}8574=2{,}14\,\%.$$ È una valutazione molto precisa (non una stima): con $3$ errori la parità rivela sempre, con $4$ errori sfugge ma con probabilità $\binom54P^4(1-P)=3\cdot10^{-4}$. Valore esatto (tutti gli errori pari): $2{,}146\,\%$. Un altro modo di scriverlo, che include però anche i casi rivelati (3 e 5 errori) e dà una sovrastima, è $1-P[0]-P[1]=1-0{,}95^5-5\cdot0{,}05\cdot0{,}95^4=2{,}26\,\%$. Con la ridondanza il rischio di accusare un innocente scende da $18{,}6\,\%$ a circa $2{,}1\,\%$; in compenso il test è inconcludente quando c'è un numero dispari di errori, con probabilità $5P(1-P)^4+10P^3(1-P)^2+P^5=20{,}5\,\%$ (le provette si possono usare una volta sola, quindi in quei casi non si accusa nessuno).

e. $D=3$ in (i): Hamming $(7,4)$ in sola rivelazione

Con $7$ provette si usa il codice di Hamming $(7,4)$ ($d_{min}=3$, Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →), che rivela fino a $2$ errori. Un errore non rivelato richiede un pattern di errore uguale a una parola di codice non nulla, che ha almeno $3$ bit a $1$. Prima stima (rozza): si prendono tutti i pattern a $3$ errori, $\binom73=35$: $$P_{undetected}\lesssim\binom73P_{err}^3(1-P_{err})^4=35\cdot1{,}25\cdot10^{-4}\cdot0{,}8145=0{,}36\,\%,$$ che è una sovrastima, perché le parole di codice sono solo $16$ su $128$ e non ogni pattern a $3$ errori è una parola. Nel $(7,4)$ ogni parola ha $7$ vicine a distanza $3$, $7$ a distanza $4$ e $1$ a distanza $7$: il numero di pattern a peso $3$ che sono parole è $7$, non $35$: $$P_{undetected}\simeq7P_{err}^3(1-P_{err})^4=7\cdot1{,}25\cdot10^{-4}\cdot0{,}8145=0{,}0713\simeq0{,}07\,\%.$$ (Aggiungendo i pesi $4$ e $7$: $0{,}075\,\%$.) Il rischio di accusare un innocente è ora circa $0{,}07\,\%$: $260$ volte minore del caso senza ridondanza.

f. $D=3$ in (ii): Hamming $(7,4)$ in correzione

Si usa lo stesso codice ma si corregge $1$ errore. Non conta più $P_{undetected}$: si sbaglia quando si esce dalla regione di decisione, cioè con $2$ o più errori (con $2$ errori il decodificatore sbaglia sempre, con $3$ in generale pure): ignorando i casi con $\ge3$ errori, $$P[\hat{\mathbf c}\ne\mathbf c]\simeq\binom72P_{err}^2(1-P_{err})^5=21\cdot0{,}0025\cdot0{,}7738=4{,}06\,\%.$$ (Valore esatto $1-0{,}95^7-7\cdot0{,}05\cdot0{,}95^6=4{,}44\,\%$.) Il colpevole si individua nel $95{,}6\,\%$ dei casi (contro $81{,}5\,\%$ del caso senza ridondanza), e con la correzione c'è sempre una risposta, a differenza del caso (i), dove con probabilità $1-0{,}95^7-0{,}00075\simeq30\,\%$ (almeno un errore, rivelato) il test è inconcludente e non si accusa nessuno.

Confronto finale. Con la stessa ridondanza ($3$ provette in più): la rivelazione dà il $0{,}07\,\%$ di accuse ingiuste ma a volte nessuna risposta; la correzione dà una risposta sempre, ma sbagliata nel $4{,}1\,\%$ dei casi. Rivelare è molto più sicuro che correggere: la correzione "spende" il potere del codice per scegliere, la rivelazione per non sbagliare.