Pagina documente » Politehnica » Coduri Reed-Muller. Erorile canalului discret si masuri de protectie impotriva lor

Despre lucrare

lucrare-licenta-coduri-reed-muller.-erorile-canalului-discret-si-masuri-de-protectie-impotriva-lor
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-coduri-reed-muller.-erorile-canalului-discret-si-masuri-de-protectie-impotriva-lor


Cuprins

Cuprins
CAPITOLUL 1
1. TEORIA INFORMATIEI.
1.1. MARIMI SI NOTIUNI SPECIFICE TRANSMISIEI INFORMATIEI
1.2. NEDETERMINARE SI INFORMATIE
1.3. SURSE DE INFORMATIE
1.4. CANALE
1.4.1. Probabilitati si entropii in canal
1.4.2. Transinformatia
1.4.3. Capacitatea canalului
1.5. CODURI
1.5.1. Eficienta codarii
1.5.2.
1.6 ERORILE CANALULUI DISCRET SI MASURI DE PROTECTIE iMPOTRIVA LOR
1.6.1. Regula de decizie dupa probabilitatea aposteriori maxima si regula de decizie dupa distanta Hamming minima
1.6.2 Clasificarea codurilor
1.7. CODURI SIMPLE DETECTOARE SAU CORECTOARE DE ERORI
1.7.1. Transmisia pe doua canale pentru corectia pachetelor de erori
Cod cu repetitie detector de erori
1.7.2. Cod cu pondere constanta detector de erori
CAPITOLUL 2
2. CODURI GRUP
1.1. SUBMULTIMI iN SPATIUL VECTORIAL
2.2. Matricea de control
2.2.1. Conditii impuse matricei de control pentru a detecta sau corecta erori
2.2.2 Constructia matricei de control pentru a detecta un numar impar de erori
2.2.3. Constructia matricei de control pentru a detecta doua erori
2.3. GENERAREA CUVINTELOR DE COD
CAPITOLUL 3
3. CODURI REED-MULLER
3.1. Descrierea codului Reed-Muller
3.2 . Codarea codului Reed-Muller
3.3. Decodarea codului Reed-Muller
CAPITOLUL 4
4. APLICATIE PRACTICA
ANEXA

EXTRAS DIN DOCUMENT

? Capitolul 1-Teoria informatiei?

CAPITOLUL 1

1. TEORIA INFORMATIEI.

1.1. M?RIMI SI NOTIUNI SPECIFICE TRANSMISIEI INFORMATIEI

Se cuvine sa facem de la inceput o precizare privind natura zgomotelor care insotesc transmisiile, acestea provenind intr-un mod asemanator modului in care se genereaza semnalele utile. Din acest motiv este necesar sa tratam unitar perturbatiile si semnalele utile. Despre primele stim ca daca s-ar comporta intr-un mod determinist, ar putea fi eliminate in mod integral. Evolutia lor este dictata de legi probabilistice. Acest caracter aleator este insa propriu si semnalul util, pentru ca o evolutie determinista a sa ar insemna cunoasterea sa la punctul de receptie si de aici ar decurge inutilitatea transmisiei. Tocmai caracterul aleator al evolutiei semnalului util este responsabil de necesitatea transmisiei unei informatii.

Dupa cum se vede au fost introduse cateva notiuni pe care le precizam in continuare. Deoarece atat perturbatia cat si semnalul util, au aceeasi natura si uneori aceiasi provenienta, ambele se pot considera ca fiind semnale, adica manifestari concrete fizice capabile sa se propage printr-un mediu numit canal. Notiunea de semnal este utilizata uneori restrans, pentru a denumi semnalul util, acela care va spune ceva receptorului.

O forma particulara a semnalului, extrasa dintr-un ansamblu, constituie un mesaj, atunci cand ansamblul urmeaza a se transimte unui corespondent.

Perturbatia este un semnal care, in procesul de transmisie sau de prelucrare, modifica in mod aleator semnalul util.

O notiune des utilizata este aceea de Informatie. Ca sa intelegem aceasta notiune, sa ne imaginam un ansamblu de N mesaje diferite, fiecare mesaj fiind ales pentru transmisie in mod echiprobabil. Evident probabilitatea emisiei oricarui mesaj este 1/N. Atunci cand se transmite un mesaj, adica se alege un anumit semnal

din ansablul de N mesaje, aceasta concretizare, aceasta realizare, da informatia. Informatia este cu atat mai mare cu cat este mai imprevizibila realizarea evenimentului constituit de transmiterea acelui semnal, deci cu cat este mai mica probabilitatea respectivului mesaj. Informatia depinde deci de probabilitatea realizarii unei anumite situatii si prin definitie este:

,

in care i este informatia, iar p este probabilitatea realizarii evenimentului considerat.

Informatia este generata de o sursa de informatie, aceasta fiind un mecanism prin care se alege, din ansamblul de semnale, tocmai acela care se va transmite acum, aceasta alegere fiind intamplatoare si necunoscuta celui care va primi semnalul. Destinatarul, corespondentul, este locul final unde trebuie sa ajunga mesajul transmis, astfel ca sa duca informatia.

Trecerea prin canal este insotita de perturbatii. Pentru diminuarea efectelor acestora, se utilizeaza diverse procedee de prelucrare a semnalelor, la intrare si la iesire din canal. Aceste prelucrari sunt modulatia/demodulatia, codarea/decodarea. Modulatia este constituita de transformarile la care este supus un semnal, pentru a-l face sa treaca printr-un canal, singur sau impreuna cu altele de acelasi gen. Demodularea este constituita de procesele inverse ce au loc la receptie, cu scopul obtinerii unui semnal, cat mai asemanator celui emis de sursa de informatie. Codarea este prelucrarea la care se supune semnalul pentru a i se mari eficienta transmiterii, in primul rand fiind vorba de semnale numerice. Decodarea este procesul invers codarii, efectuat la receptie.

Eficienta transmisiei se estimeaza in telecomunicatii printr-o comparatie intre semnalul emis, generat de sursa de informatie si semnalul oferit de receptie utilizatorului. Se utilizeaza trei criterii de apreciere a fidelitatii transmisiei si anume: eroarea medie patratica, raportul semnal/zgomot si probabilitatea deciziei false. Primul criteriu de fidelitate se scrie:

,

unde este eroarea, diferenta dintre x(t), semnalul generat de sursa si y(t), semnalul oferit utilizatorului. Bara de deasupra simbolizeaza medierea in timp a marimii. Evident o transmisie este cu atat mai buna, cu cat criteriul de fidelitate, eroarea medie patratica, este mai mica. Cel de al doilea criteriu se scrie:

,

in care n(t) este zgomotul perturbator, care nu se mai separa de semnalul util, x(t). Conform acestui criteriu, un raport semnal/zgomot, mare, indica o transmisie de mare fidelitate. Al treilea criteriu, probabilitatea deciziei false, se refera la transmisiile numerice si exprima probabilitatea de a se remite utilizatorului un cuvant care de fapt nu a fost transmis, invertirea fiind facuta ca urmare a zgomotelor din canal. O transmisie de mare fidelitate inseamna o mica probabilitate a deciziei false.

Acum putem desena o schema de transmisie care sa contina elementele anuntate mai sus. Aici vedem sursa de informatie S, modulatorul M, codorul C, canalul P, decodorul C’, demodulatorul M’ si utilizatorul U.

mesaj semnal perturbatii semnal mesaj

Fig.1.1.

În schema din figura 1.1. se mai pot introduce elemente care sa faciliteze transmisii multiple, a mai multor semnale prin acelasi canal.

1.2. NEDETERMINARE SI INFORMATIE

Consideram un ansamblu de mesaje din care urmeaza a executa transmisia, pe care o vom denumi experiment. Pe masura ce se face transmisia, zicem ca experimentul se realizeaza intr-o forma sau alta, intr-o concretizare sau alta. Înaintea realizarii, deci inaintea transmisiei, nestiind care din mesaje se va scoate din ansamblul considerat, avem o incertitudine. Aceasta se va risipi imediat ce s-a executat alegerea mesajului. Incertitudinea, sau nedeterminarea, existenta inaintea realizarii aleatoare a unui eveniment, este functie de acel eveniment, mai precis este functie de probabilitatea lui apriori. Odata cu inlaturarea incertitudinii, obtinem o informatie despre ansamblul din care s-a extras mesajul. Cele doua marimi, informatia obtinuta si nedeterminarea anterioara, sunt echivalente.

Consideram mesajul emis (t), unul din mai multe posibile a fi omise, precum si probabilitatea sa de a fi selectat la emisie, p(xi). Inceritudinea initiala, inainte de emisie, este functia F(p(xi)), egala cu informatia i(xi) adusa de aparitia mesajului (t). La trecerea prin canal, semnalul(t) se altereaza si la receptie soseste (t),

dependent de (t). În urma observarii semnalului (t), dispare o parte din incertitudinea existenta inainte de observarea lui (t), astfel incat nedeterminarea aposteriori, de dupa observare, F(p(/)), este, de regula, mai mica decat nedeterminarea apriori asupra lui (t). Nedeterminarea aposteriori este aceeasi functie de F de probabilitatea mesajului (t), conditionata insa de realizarea concreta in forma (t). Cantitatea de incertitudine disparuta in urma observarii semnalului (t), este egala cu cantitatea de informatie adusa de (t) despre (t). Deci:

,

Functia F(.), prin care se exprima incertitudinea, poate fi de mai multe feluri. Este necesar sa atribuim acestei functiicalitatea de aditivitate, in cazul in care mesajul considerat este o succesiune de doua sau mai multe semnale elementare,

,

intre care se stabileste o relatie de intersectie, mesajul necesitand prezenta atat a lui, cat si a lui. Evident, probabilitatea mesajului va fi:

,

ceea ce implica urmatoarea expresie pentru functia F de incertitudine:

.

Dorim ca aceasta incertitudine sa fie o suma de incertitudini partiale, fiecare dependenta de semnalul elementar corespunzator, adica: