8 codarea de canal

7/30/2019 8 Codarea de Canal

1/6

8. CODAREA DE CANAL

Locul codarii de canal intr-o schema de transmisiune a datelor :

Rolul codarii de canal : La trecerea prin canal, se produc modificari aleatoare aleinformatiei din cauza perturbatiilor. De aceea, la iesirea din canal, informatia nu poate fireconstituita fidel. Putem construi totusi, un Codor de canal care sa reduca probabilitatea deeroare printr-o codare adecvata a sirului de simboluri, inainte ca acestea sa fie transmise princanal. La iesirea din canal, Decodorul de canal , face operatia inversa pentru a reconstitui sirulde simboluri.

Observatie : Codarea de canal nu elimina erorile, ci doar reduce probabilitatea lor de aparitie.

8.1. Probabilitatea de eroare la decodare

Fie [ ] [ ] N x x X ,,1= , sursa de informatie care emite la intrarea in canal, si [ ] [ ] M y yY ,,1=, sursa care modeleaza iesirea canalului (se folosesc notatii diferite pentru intrare si iesire

pentru ca receptorul de la iesirea din canal poate schimba alfabetul). Sa presupunem ca inconditiile unei transmisii fara perturbatii, j y se receptioneaza atunci cand a fost transmis i x.

Probabilitatea ca j y sa fie decodat gresit este:

ji y x p /1

Pentru a minimiza aceasta eroare, putem construi un decodor care sa decodeze pe j y insimbolul i x cel mai probabil, adica simbolul pentru care ji y x p / este maxima.Presupunand ca acest simbol este j x , atunci probabilitatea minima ca decodarea sa fiegresita va fi:

j j y x p /1

In medie, probabilitatea de eroare la decodare va fi:

( ) ( )( ) ( ) j j

j j y p y x p E P = /1

Observatii:

U

P

S CoS C A N A L DecSDecCCoC UR


2/6

- decodorul care lucreaza pe acest principiu se numeste Decodor cu rata minima de eroare- aceasta probabilitate poate fi calculata daca se cunoaste matricea de zgomot a canalului si

probabilitatile simbolurilor la intrarea in canal:

( ) j j

j j

j

j j

j

j j

j

j j x p x y p y x p y p y p y x p E P === /1,/1

Exemplul 8.1 : Canalul binar simetric

Fie canalul cu matricea de zgomot: ( )

= p p

p p X Y P

1

1/ unde p este probabilitatea de

transmisie eronata. Pentru un 2,0= p , simbolurile cele mai probabile, cand se receptioneaza,1 y si 2 y , sunt 1 x si, respectiv, 2 x (probabilitatile ji y x p / maxime corespunzatoare

sunt 8,0 ). In plus, daca inainte s-a facut o codare de sursa care a condus la simboluri

echiprobabile :

( ) ( )2

121 == x p x p

atunci probabilitatea totala de eroare a Decodorului cu rata minima de eroare va fi :

( ) ( ) ( ) ( ) 2,02

1121/1 ==== p p x p x y p E P j

j j j

8.2. Codarea prin repetarea simbolurilor

O metoda simpla de codare de canal este prin repetarea simbolurilor. Ea consta din atransmite fiecare simbol de un numar impar de ori. Decodarea se face prin logica majoritara.

Exemplul 8.2 :

a) Codarea unui sir binar prin repetare de trei ori a fiecarui simbol (transmisia se face princanalul din exemplul anterior)

Codarea : 0 -> 0001-> 111

Decodarea : 000->0 111->1001->0 110->1010->0 101->1100->0 011->1

( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) p p p p p

x p x p x p x p x y p decodat

211131

0/1000/0100/0010/0000/0223

+=+=

==+=+=+====

( ) ( ) ( ) p p x y p decodat 211...1/12

+====


3/6

Rezulta :

( ) ( ) ( ) ( ) ( ) ( ) 1,0221

21121/1 2 =+== p p p p x p x y p E P j j

j j

Observatii:

- probabilitatea totala de eroare a scazut la jumatate- se transmit de trei ori mai multe simboluri, deci rata de emisie a sursei (nr de

simboluri pe secunda) trebuie sa fie mai mica decat capacitatea de transmisie acanalului (nr maxim de simboluri pe secunda, care se pot transmite prin canal)

b) Codarea prin repetarea de cinci ori a fiecarui simbol :

( ) ( ) ( ) ( ) ( )( )233225415505 63111110/0 p p p p pC p pC pC x y p decodat ++=++===

( ) ( )( ) 05,063111 23 ++= p p p E P

Observatie :

- probabilitatea de eroare a scazut si mai mult, dar rata de emisie R trebuie sa fie celmult o cincime din capacitate de transmisie C :

5C

R

8.3. Teorema a 2-a a lui Shannon

Teorema : Daca avem o sursa cu o rata de emisie R si un canal cu perturbabii, cu ocapacitate de transmisie RC > , exista un cod cu cuvinte de n , astfel incat probabilitatea deeroare sa fie :

( ) ( ) RnE E P 2

unde ( ) R E este o functie nenegativa numita exponentul erorii.

Observatii :

- Teorema a 2-a a lui Shannon este cunoscuta si sub numele de Teorema codariicanalelor cu perturbatii

- Functia ( ) R E este o caracteristica a canalului de transmisiuneR C

E(R )


4/6

- Teorema a 2-a stabileste ca pe un canal se poate face o transmisie cu probabilitate deeroare ( ) E P oricat de mica, daca rata de emisie a sursei se diminueaza suficient de mult.

- Intr-o aplicatie practica, daca se impune ( ) E P , cunoscand functia ( ) R E , se poatedetermina rata (maxima) de emisie R a sursei sau, daca se impune R , se poate afla ( ) E P cu care se va face transmisia pe canal pentru rata impusa.

8.4. Spatiul cuvintelor

In Exemplul 7.2, fiecare simbol al sursei binare era codat printr-un cuvant de lungime 3,obtinut prin repetarea simbolului. Se obtinea, astfel, o carte de cod constituita din douacuvinte :

Codarea : 0 -> 0001-> 111

La decodare, din cauza perturbatiilor, poate fi receptionat orice cuvant de lungime 3 :

Decodarea : 000->0 111->1001->0 110->1010->0 101->1100->0 011->1

Definitie : Cuvintele emise de codor se numesc cuvinte cu sens, iar restul cuvintelor deaceeasi lungime se numesc cuvinte fara sens. Impreuna, ele constituie multimea cuvintelor

de lungimen

(3=

n in exemplul 7.2).8.5. Reprezentarea grafica a cuvintelor

In Exemplul 8.2, s-au folosit cuvinte de lungime 3. Intr-un spatiu 3D, aceste cuvinte pot fireprezentate prin puncte :

Observatii :


5/6

- cuvintele cu sens sunt marcate cu negru- schimbarea unui bit intr-un cuvant este echivalent cu deplasarea pe una din laturile

cubului, spre unul dintre cuvintele vecine- pentru a trece de la un cuvant cu sens la celalalt, trebuie facuti minim 3 pasi- decodorul cu logica majoritara din Exemplul 8.2 a decodat cuvintele fara sens

cautant cuvantul cu sens cel mai apropiat

8.6. Distanta Hamming

Definitie: Distanta Hamming dintre doua cuvinte este egala cu suma bitilor prin carecuvintele difera.

( ) 3111,000 = H d

Observatie : In reprezentarea grafica, distanta Hamming este numarul minim de pasi necesari pentru a trece de la un cuvant la celalalt.

R.W. Hamming (1915-1998) a lucrat la Los Alamos intre 1944 si 1946 si apoi la Bell Labs siUniv. Princeton.

8.7. Erori detectabile si erori corectabile

Codurile de canal pot fi :

- corectoare de erori (cuvintele fara sens sunt detectate si corectate)- detectoare de erori (cuvintele fara sens sunt detectate si rejectate, iar decodorulcere retransmisia cuvantului)

Codul din Exemplul 8.2. poate corecta o singura eroare (numai cuvintele fara sens care difera printr-un singur bit de un cuvant cu sens sunt corectate). Daca apar doua erori, cuvantul estedecodat gresit. Cu acelasi cod, daca nu se incearca corectare ci se face doar rejectia cuvantuluifara sens, atunci pot fi eliminate doua erori. Spunem ca avem un cod corector de o eroare sidetector de doua erori .

8.8. Specificarea cuvintelor cu sens

Cuvintele cu sens trebuie alese astfel incat distanta Hamming minima dintre ele sa fie cat maimare .

Daca 12min += ed H , codul este corector de e erori si detector de e2 erori.Daca ed H 2min = , codul este corector de 1e erori si detector de 12 e erori.

Exemplu: Codare prin adaugarea bitului de paritate (cuvinte de lungime 3)


6/6

Codarea : 00 -> 00001-> 01110-> 10111-> 110

Observatie : este un cod detector de o eroare (de fapt, detector de orice numar impar de erori).

Exercitiu: Cate erori poate corecta/detecta urmatorul cod:

00000, 00111, 11001, 11110

8 codarea de canal

Documents