Codici correttori d`errore

Capitolo 7
Strato FisicoCodici correttori d’errore e
capacità di canale
Baccarelli,
Cordeschi, Patriarca, Polli
1
Codici correttori d’errore
Obiettivi:
correggere o rivelare errori nella trasmissione di
segnali numerici (sequenze di simboli, usualmente
binari)
Correzione di errore → Eliminare l’errore dal
segnale ricevuto
Rivelazione di errore → Segnalare l’errore nel
segnale ricevuto
‰richiedere la ritrasmissione
‰scartare parte del segnale
Baccarelli,
Cordeschi, Patriarca, Polli
2
Esempio di correzione di errore
tratto da esperienza comune
Messaggio da trasmettere
....arriverò il 26/4/2002...
Errore di trasmissione; messaggio ricevuto:
....arriverò il 28/4/2002...
Errore non visibile, né recuperabile, in ricezione.
Messaggio codificato :
....arriverò il ventisei aprile prossimo venturo...
Due errori di trasmissione; messaggio ricevuto :
....arriverò il vantisei aprole prossimo venturo...
Errori correggibili da parte del ricevente.
Costo dell’operazione di codifica: un messaggio
con più caratteri alfanumerici,
cioè con una maggiore ridondanza
Baccarelli,
Cordeschi, Patriarca, Polli
3
Ridondanza
Ridondanza di un messaggio discreto (sequenza di simboli):
ρ
=
ΝΤ − Ν I
ΝΤ
=
ΝR
≤1
ΝΤ
dove si è indicato con
NI il numero di simboli strettamente necessario
per trasmettere l’informazione contenuta nel messaggio,
NT il numero totale dei simboli contenuti nel messaggio
stesso
(quindi NR = NT - NI numero di simboli ridondanti).
Il valore della ridondanza è compreso nell’intervallo
messaggio costituito
dal minimo numero
di simboli possibile
0 ≤ ρ ≤ 1
Baccarelli,
Cordeschi, Patriarca, Polli
messaggio
con contenuto
informativo nullo
(solo ridondanza)
4
Canale Discreto
xn
sequenza di
simboli di
ingresso
canale
discreto
yn
sequenza di
simboli di
uscita
per ogni simbolo introdotto all’ingresso
viene prodotto
un simbolo in uscita dal canale
I simboli sono usualmente costituititi da bit,
singoli o raggruppati in parole binarie.
Baccarelli,
Cordeschi, Patriarca, Polli
5
Esempi di canali discreti (1/2)
Sistema di trasmissione per segnali di dati (segnali numerici):
Sorgente
di dati
Destinatario
dei dati
sequenza di
simboli di ingresso
Modulatore
numerico
sequenza di
simboli di uscita
Mezzo
trasmissivo
Demodulatore
numerico
canale discreto
Baccarelli,
Cordeschi, Patriarca, Polli
6
Esempi di canali discreti (2/2)
Sistema di trasmissione per segnali fonici:
altoparlante
microfono
codificatore
PCM
segnali
analogici
sequenza di simboli
di ingresso (bit)
Modulatore
numerico
decodificatore
PCM
sequenza di simboli
di uscita (bit)
Mezzo
trasmissivo
Baccarelli,
Cordeschi, Patriarca, Polli
demodulatore
numerico
7
Canali discreti binari, ideali o
rumorosi
....001011011....
canale
binario
ideale
....001011011....
la sequenza di simboli di uscita è identica a quella di ingresso
....001011011....
canale
binario
rumoroso
....011010010...
.
la sequenza di simboli di uscita contiene errori casuali
Baccarelli,
Cordeschi, Patriarca, Polli
8
Canale discreto binario (1/2)
CANALE BINARIO RUMOROSO
X
0
1
1-p
p
p’
1-p’
0
Y
1
p = probabilità che uno “0” introdotto all’ingresso dia luogo a un “1” in
uscita
= P(Y = 1| X = 0)
p’ = probabilità che un “1” introdotto all’ingresso dia luogo a uno “0” in
uscita
= P(Y = 0 | X = 1)
Baccarelli,
Cordeschi, Patriarca, Polli
9
Canale discreto binario (2/2)
CANALE BINARIO IDEALE
0
X
p = p’ = 0
1
;
1
1
0
1
Y
1 - p = 1 - p’ = 1
Baccarelli,
Cordeschi, Patriarca, Polli
10
Canale Binario Simmetrico
Canale binario con p = p’
X
0
1
1-p
p
p
1-p
0
1
il parametro p è la “probabilità di errore” del canale
che è uguale a
p=P(Y=0|X=1)=P(Y=1|X=0)
Baccarelli,
Cordeschi, Patriarca, Polli
11
Canale discreto generico
a0 , ... , aα-1
alfabeto
di ingresso
a ordine
dell’alfabeto
di ingresso
a0
a1
ai
b0 b ,... , b
0
β-1
b1
.
alfabeto
.
.
.
.
.
P(bk |ai )
.
.
.
bβ-3
bβ-2
bβ-1
aα-2
X
aα-1
P(Y=bk |X=ai)
.
.
.
bk
di uscita
Probabilità
di transizione
del canale
Y
Probabilità di ricevere il simbolo
bk, condizionata all’aver trasmesso
il simbolo ai,
Baccarelli,
Cordeschi, Patriarca, Polli
12
Comportamento del canale
discreto
‰ In funzione del tempo
‰ In funzione della
sequenza di simboli
trasmessa
Le probabilità di transizione
possono variare in funzione
del tempo
Le probabilità di transizione
possono dipendere dai simboli
trasmessi prima del simbolo
attuale (od anche dopo)
Baccarelli,
Cordeschi, Patriarca, Polli
13
Canale binario simmetrico
stazionario e senza memoria
E’ un canale binario simmetrico in cui le probabilità di transizione:
‰sono costanti nel tempo (“stazionarietà”)
‰non dipendono dai simboli trasmessi prima o dopo il
simbolo in esame (il canale “non ha memoria”)
Per questo tipo di canale la probabilità di errore, p , è un
parametro costante che caratterizza completamente il canale
stesso.
Il canale binario simmetrico, stazionario, senza memoria costituisce il
caso di riferimento per lo studio dei codici correttori d’errore binari.
Baccarelli,
Cordeschi, Patriarca, Polli
14
Probabilità di errore p nel BSC
p
0
1 La probabilità p
0.5
intervallo di valori teoricamente possibili
intervallo di valori presi
in considerazione nella
teoria dei codici
è compresa per
definizione
nell’intervallo
0≤p≤1
Un BSC con probabilità di errore
p > 0,5 è equivalente a un BSC con
probabilità d’errore q = 1-p < 0,5
seguito da un invertitore (0→1 ; 1 →0)
Esempio:
Canale radio-mobile (GSM) p≅10-1, p≅10-2,
Downlink satellitare (DVB-S) p≅10-2,
Cavo Coassiale (DVB-C) p≅10-4,
intervallo di valori di
interesse applicativo, con
p sufficientemente
Baccarelli,
piccolo
Cordeschi, Patriarca, Polli
15
Schema di trasmissione con impiego
di codifica per correzione d’errore
probabilità
di errore di
canale = p
Sorgente
binaria
codificatore
sequenza
trasmessa
Canale
binario
simmetrico
probabilità di errore dopo
decodificazione = Pe
decodificatore
sequenza
codificata
destin.
Sequenza decodificata
eventualmente affetta
da errore
La codifica è utile se ha l’effetto di ridurre la probabilità di errore,
ossia se
Pe < p
Baccarelli,
Cordeschi, Patriarca, Polli
16
Esempio di codice correttore
d’errore
Data una sequenza binaria di sorgente, codificare ogni simbolo con una
parola di 3 simboli, secondo la corrispondenza biunivoca
simbolo di
sorgente
0
1
parola
di codice
0 0 0
1 1 1
Esempio:
sequenza di sorgente. . . . 0
1
1
0
1
. . .
sequenza codificata. . . . . 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1…
In base a quale criterio di decodifica il codice corregge gli errori?
Baccarelli,
Cordeschi, Patriarca, Polli
17
Criterio di decisione a Massima
Verosimiglianza (ML) per trasmissioni in
canali binari discreti e rumorosi (1/2)
x
Sequenza
binaria
trasmessa
Canale
binario
r
Sequenza
binaria
ricevuta
Decisore
MLD
x^
Sequenza
decisa
‰ Supponiamo
che la sequenza x=[x0…xn-1] possa assumere uno
degli L possibili valori {c0, c1,…, cL-1} ciascuno dei quali è una
stringa binaria lunga n bit
‰ Indichiamo con r=[r0…rn-1] la stringa binaria ricevuta (ossia
“misurata”) all’uscita del canale binario.
‰ Indichiamo con {P(r|x=ci, i=0,…,(L-1)} le risultanti L
probabilità di transizione del canale binario.
Baccarelli,
Cordeschi, Patriarca, Polli
18
Criterio di decisione a Massima
Verosimiglianza (ML) per trasmissioni in
canali binari discreti e rumorosi (2/2)
Criterio di decisione ML
‰ Ricevuto r, il decisore scegli come decisione quella
tra gli L possibili valori {c0, c1,…, cL-1} alla quale
corrisponde la probabilità di transizione più grande,
ossia in formule
x̂ = arg max {P ( r | x = ci )}
0≤ i ≤ L −1
Baccarelli,
Cordeschi, Patriarca, Polli
19
Esempio di decodifica a massima
verosimiglianza
Canale Binario Simmetrico stazionario
senza memoria, p<0.5
Errori sui bit indipendenti
Messaggi trasmessi lunghi 3 bits
Probabilità che sia commesso
1 errore P1=p (1-p)2
2 errori P2=p2(1-p)
3 errori P3=p3
P3 < P2 <P1
canale
viene da
111 o da 000 ?
101
P(101|111) > P(101|000)
(un solo errore è più
probabile di due)
Baccarelli,
Cordeschi, Patriarca, Polli
111 !
Cioè la sorgente
ha emesso un201
Codici a blocco (n,k)
I simboli binari emessi dalla sorgente sono codificati a
gruppi di k (“parole”)
Il codificatore, ad ogni parola di sorgente di k simboli in
ingresso, associa biunivocamente una parola di codice
formata da n simboli in uscita, con n > k
In generale, un codice a blocco risulta definito da 2k parole di codice di n
simboli, scelte tra le 2n sequenze possibili di n simboli. Ad esempio
Codice a blocco (3,1):
2 parole di sorgente possibili (21 = 2) → 0, 1
2 parole di codice (scelte tra 23 = 8 possibili)→ 000, 111
Codice a blocchi (5,2):
4 parole di sorgente possibili (22 = 4) → 00, 01, 10, 11
4 parole di codice (scelte tra 25 = 32 possibili)→ 00000, 01111, 10110, 11001
Baccarelli,
Cordeschi, Patriarca, Polli
21
Schema generale per la co-decodifica
di un codice a blocco (n,k)
sorgente
parola di sorgente
emessa
formata da k simboli
(2k parole possibili)
destinatario
^
a
a
codificatore
decodificatore
parola di sorgente
decisa,
formata da k simboli
(2k parole possibili),
non necessariamente
uguale ad a, a causa di
errori di decodifica.
canale
parola di codice
c
BSC
r
formata da n simboli
(2k parole scelte tra 2n
possibili)
sequenza ricevuta
formata da n simboli
(2n sequenze possibili, a causa
degli errori di canale)
Baccarelli,
Cordeschi, Patriarca, Polli
22
Distanza di Hamming fra
sequenze binarie
Date due sequenze binarie x ed y formate da m simboli, si
definisce Distanza di Hamming d(x,y) il numero di simboli, in
posizioni omologhe, in cui le due sequenze differiscono.
Si osservi che risulta 0≤d≤n.
Esempio per n = 7:
sequenza x →
sequenza y →
n
0101111
1100011
distanza: d = 3
Baccarelli,
Cordeschi, Patriarca, Polli
23
Distanza minima di Hamming di un
codice a blocchi
Si definisce come distanza minima dmin di Hamming di un codice a
blocco (n,k) il minimo valore della distanza di Hamming tra due parole
qualsiasi appartenenti al codice
Il codice (3,1), ed il codice (5,2) prima definiti hanno ambedue distanza dmin =
3.
000
111
d=3
d=3
d=3
00000
01111
10110
11001
Baccarelli,
Cordeschi, Patriarca, Polli
d=4
d=3
d=4
d=3
24
Relazione tra distanza di un codice e
probabilità di errore dopo
decodificazione (1/2)
canale
0
dal
codificatore
c = [c0 , c1 ,..., cn-1]
1-p
0
al decodificatore
p
1
p
1
r = [r0 , r1 ,..., rn-1]
1-p
‰Sia t (0 ≤ t ≤ n) la distanza di Hamming tra c e r, ossia:
d(r,c) = t
‰Quindi, su n simboli trasmessi abbiamo:
t trasmissioni con errore
n-t trasmissioni senza errore
‰Supponiamo gli errori statisticamente indipendenti (canale senza
memoria), allora la probabilità di transizione di canale è calcolabile
t
come segue
n −1
⎛
⎞
P ( r | c ) = ∏ P ( ri | ci ) = p t (1 − p )
i =0
n −t
p
n
p
1
=⎜
−
)
⎟ (
⎝1− p ⎠
Baccarelli,
Cordeschi, Patriarca, Polli
25
Relazione tra distanza di un codice e
probabilità di errore dopo
decodificazione (2/2)
Criterio di decisione a Massima Verosimiglianza:
data la sequenza r ricevuta, decidere in favore della parola di
codice c per la quale è massima la P(r|c) data dalla
t
⎛ p ⎞
n
P (r | c) = ⎜
⎟ (1 − p )
⎝ 1− p ⎠
Per p≤0.5 il massimo di P(r|c) al variare di c si ha in corrispondenza del
minimo di t.
Criterio della Minima Distanza di Hamming:
data la sequenza ricevuta r, decidere in favore di quella del
codice c* che ha la minima distanza di Hamming da r.
Baccarelli,
Cordeschi, Patriarca, Polli
26
Esempio di decodifica a minima
distanza di Hamming
Codice (5,2) con dmin = 3 :
Parole del codice:
00000 01111
10110
11001
Parola trasmessa: 10110
Errori nel canale Sequenza ricevuta
Parola decisa
0
10110
10110
1
10111
10110
1
10100
10110
1
10010
10110
1
11110
10110
1
00110
10110
2
00111
00111
…
…
…
Baccarelli,
Cordeschi, Patriarca, Polli
3
3
3
3
3
3
2
min d(r,c) = 0
min d(r,c) = 1
min d(r,c) = 1
27
Capacità di correzione di errori
del codice
Sia c(T) la parola di codice trasmessa e sia r la sequenza ricevuta,
con d(r, c(T) ) = t
Dato che r è stata ottenuta da c(T) modificandola in t posizioni,
occorre modificare r in almeno altre dmin - t posizioni per
ottenere un’altra parola di codice, distante almeno dmin da c(T) .
Per t < dmin /2 valgono le relazioni
d(r, c ) ≥ dmin - t > t per ogni c ≠ c(T)
Nelle condizioni dette la decodifica a minima distanza è sempre
corretta. Quindi deduciamo che
un codice a blocco (n,k) con distanza di Hamming dmin
garantisce la correzione di tutte le configurazioni di
errore contenenti un numero di errori
Baccarelli,
t ≤ ⎣(d
min–1)/2⎦
Cordeschi, Patriarca, Polli
28
Capacità di rivelazione d’errore di
un codice a blocco
Un codice a blocco (n,k) può essere anche usato per rivelare errori
di canale nella sequenza ricevuta r.
‰ La presenza di errori viene rivelata tutte le volte che la sequenza
ricevuta r non coincide con alcuna delle parole di codice {c0,c1,…,cL-1}.
‰ Errori di canale che trasformino una parola di codice in un’altra non
possono essere rivelati. Quest’ultima evenienza può evidentemente
verificarsi soltanto se t≥ dmin .
‰ Quindi
un codice a blocco (n,k) con distanza dmin garantisce
la rivelazione di tutte le configurazioni di errore
contenenti un numero di errori t ≤ dmin-1
Correzione d’errore
t ≤ ⎣(dmin–1)/2⎦
Rivelazione d’errore
t ≤ dmin-1
Baccarelli,
Cordeschi, Patriarca, Polli
29
Probabilità d’errore residua dopo
decodificazione (1/2)
Trasmissione senza codifica:
a
sorgente
canale BSC
prob.err. = p
â
destinazione
^
Pe =P(a≠a)=
p
La probabilità di simbolo errato Pe al destinatario è uguale alla
probabilità d’errore del canale, p.
Trasmissione con codifica a correzione d’errore:
sorgente
a
codificatore
c
ĉ
canale BSC
prob.err. p
decodificatore
destinazione
^
Pe = P(c≠c)=
<p
la probabilità Pe di errore “residuo” dopo decodificazione (dovuta
agli errori che non vengono corretti dal decodificatore) è minore
Baccarelli,
della probabilità d’errore del
canale,
p.
Cordeschi, Patriarca, Polli
30
Probabilità d’errore residua (2/2)
Codice (n,k) a distanza dmin
Ha la capacità di correggere tutte le configurazioni d’errore con un
numero massimo di errori t = ⎣(dmin-1)/2⎦
Relazione di calcolo per la Pe =P(c≠c) probabilità di errore sulla
parola di codice:
Pe =
n
∑
i = t +1
⎛n⎞ i
⎛ n ⎞ t +1
n −i
⎜ ⎟ p (1-p ) ≅ ⎜
⎟ p , p << 1/ 2
⎝i⎠
⎝ t + 1⎠
Baccarelli,
Cordeschi, Patriarca, Polli
31
Complessità della co-decodifica
Codificatore:
Accesso a tabella che definisce la corrispondenza biunivoca tra
parole di sorgente e parole di codice. Tale tabella contiene 2k coppie
di elementi.
complessità esponenziale con k
Decodificatore:
Confronto della sequenza ricevuta con le 2k possibili parole di
codice trasmesse.
complessità esponenziale con k
Esistono codici a contenuto algebrico, nei quali le operazioni di codecodifica sono realizzate mediante operazioni algebriche e non mediante
accesso a tabella (teoria algebrica dei codici)
riduzione della complessità (lineare in k)
Baccarelli,
Cordeschi, Patriarca, Polli
32
Ridondanza e “transmission rate”
Si definisce “transmission rate” (tasso di trasmissione) R di un
codice il rapporto tra numero di simboli entranti ed uscenti dal
codificatore
k
R = = 1− ρ
n
dove ρ
n−k
ρ=
n
rappresenta la ridondanza del codice. Poiché n>k, avremo che R<1.
Baccarelli,
Cordeschi, Patriarca, Polli
33
Scelta dei valori di k e di n
Si consideri costante il transmission rate k/n.
All’aumentare di k e di n:
‰ È possibile trovare codici aventi dmin (e quindi
capacità di rivelazione e di correzione d’errore) più
elevata
‰ Aumenta la complessità di co-decodifica
‰ All’aumentare solo di n, diminuisce il
transmission rate R.
Baccarelli,
Cordeschi, Patriarca, Polli
34
La Capacità di Canale – Generalità
(1/4)
S
b( kTb )
CODER
MOD.
s(t )
CANALE
D
bˆ( kTb )
DECODER
DEMOD.
r (t )
‰ Con riferimento allo schema precedente, supponiamo che la sorgente
emette una sequenza di bit {…, b((k-1)Tb), b(kTb),…} a periodo di segnalazione
binaria: Tb=1/fb (sec).
‰ Supponiamo che la sequenza binaria {b(kTb), k=0,±1, ±2…} sia codificata,
modulata, trasmessa nel canale, demodulata e , infine, decodificata nella
^
sequenza { b(kTb), k=0,±1, ±2…}.
‰ Indichiamo con
^
PE P(b(kT
b) ≠ b(kTb) )
Baccarelli,
la risultante probabilità di errore
di decodifica.
Cordeschi,
Patriarca, Polli
35
La Capacità di Canale – Definizione
(2/4)
Per definizione, la capacità C (bit/sec) del canale
trasmissivo è il massimo valore che può assumere fb al
variare in tutti i modi possibili delle coppie MoDemodulatore e Co-Decodificatore sotto il vincolo che
la PE risultante sia nulla.
‰ In formule,
C max{ fb= 1/Tb} (bit/sec),
‰ Sotto il vincolo che
^
PE = P(b ≠ b)=0,
‰
dove il massimo è da intendersi rispetto a tutte le
possibili scelte delle coppie Mo-Demodulatore e CoDecodificatore.
‰
Baccarelli,
Cordeschi, Patriarca, Polli
36
La Capacità di Canale – Proprietà
(3/4)
‰ Dal punto di vista analitico, la capacità C di un
canale è un numero reale e non negativo, che si
misura in (bit/sec).
‰ Dal punto di vista ingegneristico, C
rappresentante la massima velocità con cui una
sorgente binaria connessa al canale può
trasferire simboli d’informazione binari sotto
^
il vincolo che la sequenza {b(kTb), k=0,±1, ±2…}
ottenuta dopo decodificazione coincida con la
sequenza trasmessa {b(kTb), k=0,±1, ±2…} .
Baccarelli,
Cordeschi, Patriarca, Polli
37
La Capacità di Canale – Proprietà
(4/4)
suo specifico valore di
capacità C, che dipende dal tipo e dall’entità
‰ Ogni canale ha un
dei disturbi introdotti dal canale stesso.
‰ I canali
elevate.
migliori sono quelli con capacità più
Baccarelli,
Cordeschi, Patriarca, Polli
38
La capacità del canale “Additive
White Gaussian Noise” (AWGN) (1/3)
‰ Come esempio di calcolo di capacità, consideriamo il seguente
modello di canale, detto canale AWGN a banda limitata.
n(t )
H( f )
s(t )
‰
i.
ii.
r (t )
+
−W
W
f
Essenzialmente il canale,
Somma al segnale modulato s(t) un segnale n(t) di rumore gaussiano
bianco, a media nulla, e con spettro bilatero di densità di potenza
Pnn(f)=N0/2 (Watt/Hz);
Fa transitare il segnale somma risultante s(t)+n(t) attraverso un
filtro passa-basso di larghezza di banda W(Hz).
Baccarelli,
Cordeschi, Patriarca, Polli
39
La capacità del canale Additive White
Gaussian Noise (AWGN) (2/3)
‰ Indichiamo con
T /2
1
2
(t )dt (Watt )
Ps = lim
s
∫
T →+∞ T
− T /2
la potenza del segnale modulato che entra nel canale.
‰ Si può dimostrare che la capacità C (bit/sec) del suddetto canale
è pari a
⎛
Ps ⎞
C = W log 2 ⎜ 1 +
(bit/sec)
⎟
N0W ⎠
⎝
‰ La formula precedente è nota come “formula
Shannon-Hartley”.
Baccarelli,
Cordeschi, Patriarca, Polli
della capacità di
40
La capacità del canale Additive White
Gaussian Noise (AWGN) (3/3)
E’ interessante osservare che :
‰
i.
Per ogni fissato valore della banda W, abbiamo
che:
lim C = 0 , e :
Ps / N 0 → 0
ii.
lim C = +∞
Ps / N 0 → ∞
Per ogni fissato valore del rapporto Ps/N0,
abbiamo che:
Ps
lim C = 0, e: lim C =
(log 2 e ) (bit/sec)
W →0
W →∞
N0
Baccarelli,
Cordeschi, Patriarca, Polli
41