Decodarea pe baza criteriului probabilitatii conditionate maxime de decizie (mld-maximum likelihood decoding)

DECODAREA PE BAZA CRITERIULUI PROBABILITATII CONDITIONATE MAXIME DE DECIZIE (MLD-MAXIMUM LIKELIHOOD DECODING)

La receptie decoderul va trebui sa decida, pe baza secventei receptionate r care a fost secventa transmisa, deci va estima emisia () pe baza receptiei.

Daca (secventa de cod), nu sint erori la decodare. Daca secventa estimata () difera de o secventa de cod (v), decodarea este eronata. Probabilitatea ca in cazul receptiei lui r sa apara eroare la decodare este :

=: (17)

Probabilitatea de eroare a decoderului se poate exprima si sub forma :

(18)

derivata ca probabilitate marginala din probabilitatea cuplului (E,r) :

p(E,r)=p(E/r)p(r) .

Conform relatiei (18), vom avea o probabilitate minima de eroare la decodare daca p(E/r) va fi minim, dat fiind ca p(r) este independenta de decodare. Deoarece minimizarea lui este echivalenta cu maximizarea lui p(/r) rezulta ca p(E) min se obtine pentru p(v/r) maxim. p(v/r) se poate exprima, conform formulei lui Bayes:

(19)

deci maximizarea lui p(v/r) este echivalenta cu maximizarea lui p(r/v), in ipoteza echiprobabilitatii cuvintelor de cod v. In cazul unui canal fara memorie, pentru care fiecare simbol receptionat depinde doar de simbolul emis, avem :

(20)

unde r_i,v_i sint componentele cuvintului receptionat, respectiv a cuvintului de cod transmis.

Decoderul care face estimarea secventei receptionate prin maximizarea relatiei (20) se numeste decoder dupa probabilitatea conditionata maxima (MLD).

(21)

unde v_i sint componentele lui v.

Deoarece ldx este o functie crescatoare monotona cu x, maximizarea relatiei (21) este echivalenta cu maximixarea logaritmului functiei respective :

(22)

Observatie :

daca cuvintele de cod v nu sint echiprobabile, decoderul MLD nu este totdeauna optimal, dat fiind ca in relatia (20) vor fi ponderate de p(v) ; in numeroase aplicatii nu se cunosc la receptie p(v), fapt pentru care decodarea MLD ramine decodarea practica cea mai buna.

In cazul unui CBS, pentru care =p ,daca si (1-p) daca , pentru un cod bloc de lungime n, relatia (22) se scrie :

max ld p(r/v)=max =max [d(r,v)ld+nld(1-p)] . (23)

Dat fiind ca ld<0 , pentru p<1/2 si nld(1-p) este o constanta pentru orice v, regula MLD de decodare pentru un CBS estimeaza ca acel cuvint v care minimizeaza d(r,v), fapt pentru care decoderul MLD se mai numeste si decoder de distanta minima.

max ld p(r/v)=min d(r,v) (24)

In consecinta un decoder MLD determina distanta dintre r si toate cuvintele de cod posibile v_i si selecteaza acel v_i pentru care d(r,v_i) este minima (). Daca acest minim nu este unic, alegerea intre mai multe cuvinte v_i este arbitrara.

In fig.6 este ilustrat principiul decoderului de distanta minima (MLD). Fie v₁ si v₂ doua cuvinte de cod aflate la o distanta d(v₁,v₂)=

	r1

v1

a

v1

b

c

d

Fig. 6 Ilustrarea principiului decoderului de distanta minima (d=5)

Fie patru situatii a,b,c,d corespunzind receptiei cuvintelor r₁,r₂,r₃ r₄ aflate la distanta 1,2 3 respectiv 4 de v₁. In cazul a, corespunzind existentei unei singure erori in v₁ decoderul va decide ca r₁ provine din v₁ deoarece d(r_{1 ,}v₁)=1< d(v₂,r₁)=4. Decodarea va fi eronata in situtia in care r₁ ar fi provenit din v₂ prin eronarea a 4 simboluri. In cazul b, corespunzator eronarii lui v₁ pe doua pozitii, decoderul va decide ca r₂ provine din v₁ pentru ca d(v₁,r₂)=2< d(v₂,r₂)=3 ; se va produce eroare la decodare in situatia in care r₂ ar fi provenit din v₂ prin eronarea a 3 pozitii. In cazul c decodorul va decide ca r₃ provine din v₂ prin aparitia a doua erori : d(v₂,r₃)=2< d(v₁,r₃)=3. Pentru cazul d, decoderul va decide ca r₄ provine din v₂ prin eronarea unui bit : d(v₂,r₄)=1< d(v₁,r₄)=4.Aceeasi discutie de eroare la decodare poate fi facuta si in aceste ultime cazuri, ca si in situatiile a si b. Figura 6 ilustreaza ca in cazul in care se receptioneaza r₁,r₂,r₃r₄, corespunzator eronarii pe 1,2,3 sau 4 biti, a lui v₁ sau v₂ este posibila detectia erorii. Erori nedetectabile apar cind receptia este eronata pe 5 pozitii.

Acest exemplu ilustreaza faptul ca distanta de cod este un parametru ce indica capacitatea de detectie, respectiv de corectie a unui cod. In [Li-83] se demonstreaza ca :

conditia necesara si suficienta pentru ca un cod sa corecteze maxim t erori este ca :

(25)

conditia necesara si suficienta pentru ca un cod sa detecteze maxim e erori este ca  (26)

conditia necesara si suficienta pentru ca un cod sa poata simultan corecta naxim t erori si detecta maxim e erori este ca

, e>t. (27)

Observatie :

corectia implica in prelabil detectie ; de exemplu pentru d=7 putem avea situatiile :

daca apar 3 erori, toate pot fi detectate si corectate.

daca apar 5 erori, toate sint detectate, dar poate fi corectata numai una.

Acelasi parametru d poate fi utilizat pentru aprecierea capacitatii de corectie a anularilor (erasure correction)[Sk-88]. In cazul canalelor cu anulari, am vazut ca alfabetul de iesire al canalului are un simbol suplimentar (y₃) numit simbol de anulare (stergere). In momentul in care decoderul declara un simbol de anulare, desi valoarea corecta nu este cunoscuta, pozitia se stie, deci corectia erorilor erorilor de anulare trebuie sa fie mai simpla decit a celorlalte erori (care necesita cunoasterea pozitiei si valorii in cazul general). Se demonstreaza ca pentru corectia unui numar de s erori de stergere (anulare) trebuie sa fie indeplinita conditia [Sk-88]:

(28)

Conditia pentru corectia simultana a t erori si s stergeri este :

(29)

Corectia simultana a s erori de stergere si t erori se desfasoara in felul urmator. La inceput cele s pozitii anulate se inlocuiesc cu "0" si cuvintul de cod se decodeaza normal. Apoi cele s pozitii anulate se inlocuiesc cu "1" si se repeta algoritmul de decodare. Din cele doua cuvinte decodate se selecteaza acela corespunzator numarului minim de erori corectate in afara celor s pozitii anulate.

Exemplul 2

Fie codul 0000 0101 1010 1111. Se determina usor ca d=2, de unde, conform relatiei (28) rezulta ca vor putea fi corectate s=1 erori de stergere (anulare).

Fie cuvintul 0101 transmis. La receptie presupunem ca s-a detectat un simbol de anulare

r= x101

Inlocuim x cu 0; se obtine r₁=0101=v₂, deci d(r₁,v₂)=0. Inlocuim x cu 1; se obtine r₂=1101C; determinam d(r₂,v₂)=1, d(r₂,v₃)=3, d(r₂,v₄)=1=v₂.