Matematica Discreta II
Lezione del giorno 12 dicembre 2007 Probabilità di corretta decodifica.
Se in un codice qualunque la distanza è 2s+1, sappiamo che esso è in grado di correggere s errori (al più) trovando la parola inviata v con la tecnica della parola più vicina.
Tale metodo di decodifica ovviamente può non funzionare in modo esatto se gli errori di trasmissione sono più di s.
Poiché ovviamente non è noto a priori qual è il numero di errori nella trasmissione, facciamo dei ragionamenti probabilistici per verificare se la tecnica della parola più vicina è in ogni caso quella migliore per decodificare correttamente la parola ricevuta w.
Supporremo che il canale di trasmissione sia simmetrico, nel senso che ogni bit della parola inviata abbia la stessa probabilità p (con 0<p<1) di essere modificato per errore (indipendentemente dalla posizione del bit nella parola), e che p rappresenti sia la probabilità che un bit=0 si trasformi in 1, sia quella che un bit=1 si trasformi in 0. La probabilità che un bit sia trasmesso invariato è (1-p).
Sotto queste ipotesi, se v è la parola del codice C che viene inviata, calcoliamo la probabilità che una fissata parola w venga ricevuta al posto di v: ponendo j=(v,w) si ha che sono stati modificati j bits in v per ottenere w (sugli n bits di v), e ciò avviene con probabilità pj(1-p)n-j.
Se z è una parola a distanza (v,z)=i>j, la probabilità che sia stata ricevuta z è pi(1-p)n-i. Se facciamo l’ipotesi (realistica) che p<1/2 (nei casi concreti p è molto vicino a 0), si ha 2p<1, p<(1-p), e il rapporto fra le probabilità è [pj(1-p)n-j]/ [pi(1-p)n-i]=[(1-p)/p]i-j>1 (nei casi concreti p è molto piccolo, quindi tale rapporto è molto grande).
Dunque, aumentando la distanza da v dal valore j al valore i, la probabilità che la parola con tale distanza sia quella ricevuta diminuisce di un fattore =[(1-p)/p]i-j: se allora w è la parola ricevuta, la parola del codice C a distanza minima da w è quella che ha la maggiore probabilità di essere la parola inviata v.
Nel caso di un codice lineare C Z2n, di cui è stata costruita una matrice di decodifica standard, possiamo calcolare a priori la probabilità che l’algoritmo di decodifica della parola a minima distanza fornisca la decodifica esatta, indipendentemente dalla parola w ricevuta.
Siano infatti z1=0, z2,….., zm le parole leader della matrice (con m=2n-k, dove k è la dimensione di C).
Si verifica facilmente che, se w è la parola ricevuta, il nostro algoritmo di decodifica fornisce la decodifica esatta se solo se la parola inviata vC è una delle parole della forma w+zj (per qualche i=1,…,m).
Infatti nel nostro algoritmo la parola w viene decodificata come w+zj (dove zj è la parola leader della riga di w, cioè di [w]), e se correttamente è v=w+zj, allora v è della forma voluta; viceversa se v=w+zj per qualche i=1,…,m, e se zj è la parola leader della riga di w (quindi w+zj=w+(-zj)C), allora si ha zi+(-zj)=(w+zi)+zC, da cui [zi]=[zj], ed i=j (perché le classi corrispondenti alle righe della matrice sono per costruzioni tutte distinte), quindi la nostra decodifica w+zi fornisce correttamente la parola v.
Come conseguenza di tale ragionamento, se vogliamo calcolare la probabilità che l’algoritmo di decodifica fornisca la decodifica esatta, dobbiamo calcolare la probabilità che la parola corretta sia una delle w+zi , sommando le singole probabilità che la parola corretta sia w+zi (fissato i=1,…,m).
Ma se la parola corretta è v=w+zi, ragionando a livello di bits si ha che le posizioni dei bits=1 del leader zi sono esattamente quelli in cui è sono avvenuti gli errori di trasmissione (un bit=1 sommato al corrispondente bit di w lo modifica). Abbiamo già visto che (nell’ipotesi di un canale simmetrico con probabilità p di modifica del singolo bit) la probabilità che w=v+zi sia la parola ricevuta al
posto della parola v è pi(1-p)n-i dove i è il numero di bits modificati: tale numero i coincide dunque con il numero di bits=1 in zi ossia con il peso p(zi).
La probabilità che il nostro algoritmo di decodifica riesca a decodificare correttamente w è dunque la somma dei prodotti pi(1-p)n-i dove i è il peso della parola leader zi (al variare di quest’ultima fra le parole leader).
Poiché il peso di una parola di lunghezza n può variare da 0 ad n, se per ogni j=0,….,n indichiamo con j il numero delle parole leader di peso j (può anche ovviamente essere j=0) , la probabilità che il nostro algoritmo di decodifica riesca a decodificare correttamente è uguale alla sommatoria:
j n n j
0 j
jp (1 p)
.Esempio. Nell’esempio precedente di un codice lineare C di cui abbiamo costruito la matrice standard di decodifica, vi sono 8 parole leader, delle quali (oltre la parola nulla di peso 0), vi sono 6 parole di peso 1, ed 1 parola di peso 2: la probabilità che il nostro algoritmo di decodifica riesca a decodificare correttamente è uguale a: (1-p)6+6p(1-p)5+p2(1-p)4.
Se p=0,01, tale probabilità è circa 0,9986355, quindi la probabilità che la codifica sia errata è circa 1-0,9986355=0,0013645 (circa 7.3 volte inferiore alla probabilità p=0,01 di errore in un singolo bit).
Da notare che, essendo la dimensione =3, i bits di ridondanza sono 6-3=3: questo è il “costo” speso per avere più affidabilità nella trasmissione.
Teoria dei disegni.
E’ un teoria che ha origine dai test industriali.
Supponiamo che un industria produca un numero v di differenti varietà di uno stesso prodotto (v è un intero 1) e voglia sottoporre tali varietà ad un test di qualità: vi saranno delle persone (testers) che effettueranno i test.
Affinché il test sia equilibrato e omogeneo nei risultati, è ovviamente opportuno richiedere che:
- ogni tester testi un numero k di varietà fra le v disponibili, con k uguale per tutti i testers;
- ognuna delle v varietà sia testata dallo stesso numero r di testers
Esempio: sia v=6, k=3, r=2 (in totale 6 varietà, ogni tester ne testa 3 ed ogni varietà viene testata da 2 testers). È possibile, con questi dati, effettuare il test? E con quanti testers? Con i dati precedenti la risposta è positiva; infatti, se l’insieme delle 6 varietà è A=a,b,c,d,e,f si possono impiegare 4 testers per esempio secondo lo schema seguente:
1° tester: {a,b,c}, 2° tester: {b,c,d}, 3° tester: {d,e,f}, 4° tester: {e,f,a}
Problema generale: dati v,k,r generici, è sempre possibile realizzare il test con le modalità descritte sopra ? e in caso affermativo, quanti testers sono necessari ?
Formalizzando il problema (dopo avere notato che in sostanza ogni tester si può identificare con un sottoinsieme dell’insieme delle varietà del prodotto) si perviene alla seguente definizione: fissati i numeri naturali v,k,r si chiama disegno a blocchi di parametri (v,k,r) una struttura formata da:
- un insieme A di cardinalità v;
- alcuni sottoinsiemi non vuoti di A (detti blocchi del disegno), tutti della stessa cardinalità k e tali che ogni elemento di A appartenga esattamente ad r blocchi
L’esempio precedente è un esempio di disegno di parametri (6,3,2).
Problema: quali condizioni si devono imporre sui parametri (v,k,r) affinché il disegno si possa costruire, e come il numero dei blocchi è legato ai 3 parametri ?
Sia dato l’insieme A=a1,a2,…..av e si supponga che si possa costruire il disegno di parametri (v,k,r) con esattamente x blocchi; gli x blocchi B1,B2,…Bx saranno dei sottoinsiemi di A tutti di cardinalità k; ma il numero totale di sottoinsiemi di cardinalità k di un insieme di cardinalità v è uguale al coefficiente binomiale
k
v , quindi una condizione che certamente è verificata è la seguente: numero dei blocchi x
k v .
Costruiamo poi la matrice di incidenza del disegno: è una matrice booleana con v righe ed x colonne, in cui alle righe si fanno corrispondere gli elementi a1,a2,…..av di A, e alle colonne i blocchi B1,B2,…Bx , mentre in ogni casella all’incrocio fra riga i e colonna j si pone il valore 1 se l’elemento ai appartiene al blocco Bj, il valore 0 altrimenti.
Il fatto che ogni blocco abbia cardinalità k dice che ogni colonna contiene esattamente k valori =1.
Il fatto che ogni elemento ai appartenga esattamente ad r blocchi dice che ogni riga contiene r valori
=1.
Se contiamo “per righe” il numero di 1 nella matrice si ottiene rv, mentre se contiamo “per colonne”
si ottiene kx, dunque si ha rv=kx, ossia x=(vr)/k.
Questa eguaglianza ci dice che il numero x di blocchi di un disegno di parametri (v,k,r) dipende dai 3 parametri, ed inoltre (dovendo essere x un numero intero) ci fornisce una seconda condizione che certamente è verificata se il disegno esiste: k è divisore del prodotto vr.
Esempio. Un disegno di parametri (10,7,4) non esiste in quanto 7 non è divisore di 40.
Riassumendo, se si può costruire il disegno di parametri (v,k,r) allora valgono certamente le due condizioni seguenti:
(*) k è divisore del prodotto vr (**) x = (vr)/k
k v
ed inoltre x rappresenta il numero dei blocchi del disegno.
Il risultato più interessante è che, viceversa:
Teorema. Se le due condizioni (*), (**) sono verificate dai numeri naturali v,k,r, allora si può costruire un disegno di parametri (v,k,r).
Dimostrazione: Sia A=a1,a2,…..av l’insieme delle v varietà; essendo vera la (*), il numero x=(vr)/k è intero; essendo vera la (**) è possibile scegliere (in modo random) x sottoinsiemi distinti di A, ognuno di cardinalità k, siano essi B1,B2,…Bx.
Costruiamo una matrice con v righe ed x colonne, con la stessa regola della matrice di incidenza dei disegni: in ogni colonna vi sono k valori =1, e se r1, r2,….., rv rappresentano in ordine il numero di valori =1 nelle righe 1,2,…., v, si ha r1+r2+…..+rv=kx (contando per righe e colonne come sopra).
Se ogni riga della matrice contiene r valori =1, allora il disegno di parametri (v,k,r) è già costruito (con blocchi B1,B2,…Bx). Dunque supponiamo che rir per qualche i.
Per tutti questi indici i per cui rir non si può avere sempre ri>r: se così fosse sarebbe kx=r1+r2+…..
+rv>vr, contro l’ipotesi x=(vr)/k. Analogamente per gli stessi indici non si può avere sempre ri<r . Esisteranno allora almeno 2 indici distinti i, j tali che ri>r>rj. Poiché nella riga i il numero di valori
=1 è maggiore di quello nella riga j, vi sarà almeno una colonna di indice h in cui nella casella della riga i vi è il valore 1 mentre nella casella della riga j vi è il valore 0 (dunque il blocco Bh contiene l’elemento ai ma non l’elemento aj). Modifichiamo allora la matrice, scambiando fra loro questi valori 0 ed 1 nella stessa colonna: dal punto di vista insiemistico modifichiamo il blocco Bh
togliendo l’elemento ai e inserendo l’elemento aj (in particolare non cambia la cardinalità k del blocco). Questo “aggiustamento” porta ad una situazione in cui abbiamo diminuito il numero di 1 in
una riga che ne ha in “eccesso” (rispetto al valore r) e abbiamo aumentato il numero di 1 in una riga che ne ha in “difetto”: iterando il procedimento, dopo un numero finito di aggiustamenti otterremo una matrice in cui ogni riga ha esattamente r valori =1: sarà la matrice di incidenza del disegno cercato, con blocchi B1,B2,…Bx ottenuti modificando i sottoinsiemi scelti in modo random all’inizio del procedimento.
Esempio. Costruiamo un disegno di parametri (5,3,3): sono verificate le condizioni (*), (**) ed il numero di blocchi è x=15/3=5. Scegliamo in modo random 5 sottoinsiemi di A={a1,a2,a3,a4,a5} tutti di cardinalità k=5, per esempio:
B1={a1,a2,a3}, B2={a2,a3,a4}, B3={a3,a4,a5}, B4={a1,a2,a4}, B5={a2,a4,a5} La matrice corrispondente è:
1 0 1 0 0
1 1 1 1 0
0 0 1 1 1
1 1 0 1 1
0 1 0 0 1
L’obiettivo è quello di trasformare i blocchi in modo che ogni riga contenga r=3 valori =1.
La riga 4 ne contiene in eccesso, la riga 5 in difetto: nella colonna 4 vi è un 1 nella riga 4 ed uno 0 nella riga 5, e li scambiamo far loro ottenendo:
1 1 1 0 0
1 0 1 1 0
0 0 1 1 1
1 1 0 1 1
0 1 0 0 1
Analogamente la riga 2 contiene valori 1 in eccesso, la riga 2 in difetto: nella colonna 2 vi è un 1 nella riga 2 ed uno 0 nella riga 1, e li scambiamo far loro ottenendo:
1 1 1 0 0
1 0 1 1 0
0 0 1 1 1
1 1 0 0 1
0 1 0 1 1
Abbiamo ottenuto in ogni riga un numero r=3 di valori =1, dunque il disegno di parametri (5,5,3) è costruito, con blocchi:
B1={a1,a2,a3}, B2={a1,a3,a4}, B3={a3,a4,a5}, B4={a1,a2,a5}, B5={a2,a4,a5}.
