Matematica Discreta III
Lezione del giorno 16 maggio 2008
Abbiamo dimostrato che, se C Z
2nun codice lineare, allora: la decodifica (mediante il principio della minima distanza) è corretta il pattern di errore è una delle parole leaders.
Dal risultato precedente segue che la probabilità di corretta decodifica (nel caso di un codice lineare C Z
2n) si ottiene sommando le probabilità che il pattern di errore coincida con uno dei leaders (al variare del leader). Supponiamo come sempre che il canale di trasmissione sia simmetrico con probabilità di errore p (nel singolo bit): se z è un generico leader, e se t=(z) è il suo peso (cioè il numero dei bits =1) la probabilità che il pattern di errore sia z coincide la probabilità che vi siano esattamente s errori di trasmissione, ossia coincide con p
t(1-p)
n-t= p
(w)(1-p)
n-(w). Se sommiamo queste quantità al variare del leader w otteniamo la probabilità di corretta decodifica; poiché il peso di una parola di lunghezza n varia da 0 ad n, se nella somma raggruppiamo gli addendi con lo stesso peso si ottiene alla fine:
Corollario. La probabilità di corretta decodifica nel caso di un codice lineare C Z
2nè uguale a:
t n t
n 0 t
t
p (1 p)
A
(*)
dove A
tindica il numero di leaders di peso t nella matrice di decodifica di C, per ogni t=0,….,n . In particolare tale probabilità non dipende dalla parola trasmessa ma solo dal codice C (al contrario di quanto avviene nei codici generici, come visto in precedenti esempi).
Esempio: in un esempio precedente si è costruita la matrice di decodifica 8x8 di un codice lineare C di lunghezza 6 e dimensione 3, in cui vi sono 8 leaders dei quali: 1 di peso 0; 6 di peso 1;1 di peso 1 (in questo caso A
0=1, A
1=6, A
2=1, A
3=A
4=A
5=A
6=0).
Dunque se il canale di trasmissione è simmetrico con probabilità di errore p, utilizzando tale codice la probabilità di corretta decodifica è:
(1-p)
6+6p(1-p)
5+p
2(1-p)
4=(1-p)
4(1+4p-4p
2)
Se per esempio p=0,01 (statisticamente 1 bit ogni 100 è errato) allora tale probabilità è circa 0,998635, quindi la probabilità di errata decodifica è circa 1-0,998635=0,001365. I bits di informazione sono 3 (perché dimC=3), e 3 sono i bits di ridondanza che controllano gli errori: se avessimo trasmesso una parola di lunghezza 3 attraverso lo stesso canale (pura informazione senza controllo di errore), la probabilità che essa venisse ricevuta correttamente sarebbe (1-p)
30,9703, quindi la probabilità che essa venisse ricevuta in modo errato sarebbe circa 1-0,9703=0,0297 (più di 20 volte superiore alla probabilità 0,001365) : tale migliore prestazione è stata ottenuta mediante la
“spesa” dei 3 bits di ridondanza.
L’ultimo teorema dimostrato afferma in pratica che i patterns di errore che il codice lineare C riesce a correggere sono esattamente i leaders della matrice di decodifica.
Se è la distanza del codice lineare C, e se s=(-1)/2, sappiamo che C è in grado di correggere (al più) un numero s di errori: il numero di errori coincide con il peso del pattern di errore, dunque tutte le parole di Z
2ndi peso s saranno presenti come leaders nella matrice di decodifica.
Potranno però egualmente essere presenti come leaders anche parole di peso >s, rappresentanti egualmente dei pattern di errore che il codice C riesce a correggere.
Esempio: il codice C dell’esempio precedente (in cui =3, s=1) è in grado di correggere (al più) 1
errore, ed infatti nella matrice di decodifica tutte le parole di peso 1 sono presenti come leaders. Vi
è però anche una parola leader 00101 di peso 2, ed essa rappresenta un pattern di errore che il
codice C riesce egualmente a correggere: in pratica se gli errori nella parola trasmessa sono 2 ma
esattamente nel 4° e 6° bit, allora C riesce a decodificare esattamente la parola trasmessa (mediante il principio della minima distanza).
Nella formula (*), i coefficienti A
tsono in genere difficili da calcolare a priori, senza costruire l’intera matrice di decodifica. Però l’osservazione precedente permette il calcolo esplicito di alcuni di essi: poiché tutte le parole di peso ≤s=(-1)/2 sono presenti come leaders, e poiché per ogni t=0,1,….,s il numero di parole di lunghezza n e peso t coincide con il coefficiente binomiale
t
n ,
la probabilità di corretta decodifica per un codice lineare di lunghezza n diventa:
t n t
s 0 t
p) (1 t p
n
+
n t n t1 s t
t
p (1 p)
A
(dove At indica il numero di leaders di peso t) Mentre i coefficienti della prima sommatoria possono essere calcolati a priori, quelli della seconda possono essere calcolati solo conoscendo la matrice di decodifica.
Nel caso però di un codice lineare perfetto (per es. un codice H(r) di Hamming) dimostriamo che tutti i coefficienti A
tcon t>s sono nulli, ossia che tutti i leaders hanno peso s: se infatti per assurdo esistesse un leader z con peso t>s, per costruzione della matrice di decodifica la parola del codice a distanza minima da z sarebbe quella nella stessa colonna, quindi nella prima colonna ossia la parola nulla 0, da cui si avrebbe (z,0)=(w)=t>s, in contraddizione con la proprietà che in un codice perfetto ogni parola si trova a distanza s da una e una sola parola del codice.
Dunque per un [n,k,]-codice lineare perfetto C la formula della probabilità di corretta decodifica diventa:
t n t
s 0 t
p) (1 t p
n
