Codarea surselor pentru canale cu perturbatii

Codarea surselor pentru canale cu perturbatii

Aparitia perturbatiilor pe un canal de comunicatie inseamna transformarea din simbolurile transmise in altele. In cazul transmisiei binare, perturbatia inseamna complementarea unui bit (complementare =+1 bit). Se spune ca zgomotul are un caracter aditiv deoarece efectul de perturbare poate fi modelat prin sumarea modulo 2.

Apar 2 probleme :

detectia erorilor

corectia erorilor

1) Detectia erorilor presupune o codare astfel efectuata incat la receptie sa se poata decide daca ceea ce s-a receptionat este corect sau nu. Nu se cunoaste in schimb locul sau pozitia bitului eronat.

Problema aparitiei unei erori e tratata prin a cereri de retransmisie. Asta presupune existenta unui canal de comunicatie revers, e nevoie deci de un canal bidiu.

2) Corectia erorilor presupune realizarea unei codari care sa permita atat identificarea cuvintelor eronate cat si pozitia din structura unui cuvant unde s-a produs eroarea. Cuv. poz. erorii permite corectarea acesteia.

Corectia erorii nu implica canale de comunicatie reverse. Este evident ca in practica corectia erorilor presupune echipamente complexe. Definim codurile bloc ca fiind acele coduri pt. acre toate cuvintele de cod au aceeasi lungime. Vom numi coduri non-bloc sau recurente acele coduri care nu realizeaza o delimitare precisa a cuvintelor de cod. Pentru a evalua nr. de erori detectabile sau corectabile se utilizeaza un parametru algebric si anume distanta Hamming.

Prin definitie vom numi distanta Hamming intre 2 succesiuni binare nr. de (ne) coincidente.

Daca avem: .

.

Daca coincid da 0 iar daca nu da 1.

000, 001, 010, 011, 100, 101, 110, 111 rezulta ca distanta H intre 2 succesiuni alaturate este 1 dar pot exista si succesiuni cu dist. H mai mare.

H=2 000 s1

011 s2 000 (s1)

101 s3 rezulta dist min H este 3

110 s4 111(s2)

Daca presupunem ca pe un canal de comunicatie pot transmite 8 mesaje asociate cu cele 8 succesiuni de cate 8 biti inseamna ca aparitia unei erori va determina ca mesajul receptionat sa fie altul decat cel transmis. Concluzia este ca daca distanta minima h=1 nu se poate detecta apare eroare deoarece prin eroare un mesaj este transformat in alt mesaj. Daca se considera insa cea de-a doua succesiune de simboluri (cele 4 cu dist H=2) si daca pe canalul de comutatie apare o eroare , indiferent de pozitie inseamna ca la receptie se va descoperi o succesiune care nu corespunde nici uneia din cele 4 posibile, deci se decide ca a aparut o eroare. In general pt. a putea detecta erori este nevoie ca distanta minima H sa satisfaca relatia : l+1 unde l numarul de erori detectabile.

Daca presupunem ca in cazul aceleasi transmisii folosim succesiuni cu distanta H=2 s-ar produce o eroare pe prima pozitie si s-a transmis de cuvantul al 2 -lea 011 111, cuvantul astfel obtinut are distanta H = 1 fata de mesajul (s2) al 2-lea transmis, fata de s3 si s4 netransmisi. Deci daca receptionam 111 putem spune cu aceeasi probabilitate ca s-a transmis s2, s3, s4.

000(s1), 011(s2), 101(s3), 111(s4), 000(s1), 111(s2).

Daca consideram s1=000, s2=111 atunci aparitia unei erori pe prima pozitie la transmisia lui s2 ar face sa se receptioneze 011 in loc de 111 mesajele care au distanta H=1 fata de s2 dar care are distanta H2 fata de s1.

Pe    baza evaluarilor statistice se poate arata ca probabilitatea cuvantului. cel mai probabil transmis este cel aflat la distanta H minima fata de cel receptionat rezulta pe baza acestui rationament o noua relatie ce poate fi usor generalizata de forma: 2l + 1, relatie care se interpreteaza astfel:

- daca pe un canal apar e erori sau mai putine atunci distanta H trebuie sa satisfaca ac. inegalitate. Numim ac. expresii relatii deterministe intre distanta H si nr. de erori detectabile.

Sa presupunem in continuare ca o sursa contine N mesaje si se pune problema transmiterii a N mesaje pe canalul de comunicatie.

Daca se realizeaza codare binara folosind k simboluri binare 0,1 (k biti), atunci va fi nevoie de un nr. de simboluri astfel incat 2 N. Se aleg k cel mai mare intreg care satisface aceasta relatie. Daca vrem sa codificam cifrele de la 0 la 9 rezulta N=0 si k =4 (4 biti pentru a reprezenta cu simboluri binare cifrele de la 0 la 9).

Prin urmare pt. ex. considerate ar insemna sa transmitem: 0000 0, 0001 1 . 1001 9. Daca s-ar transmite respectivele cuvinte sub aceasta forma nu se poate realiza nici detectia nici corectia erorilor deoarece nu sunt indeplinite criteriile de distanta H. De obicei se foloseste un numar mai mare de simboluri (biti), fie acest numar n.

Desi din calcule rezulta ca avem nevoie de k biti noi vom folosi n = k    +m (un numar k de biti se vor numi simboluri informationale, restul numindu-se simboluri de control - m ).

Vom spune ca simbolurile k sunt purtatoare de informatie (simboluri informationale). In acest fel se introduce deliberat o redundanta in codare in scopul protejarii informatiei la perturbatii. In cazul in care in structura unui cuvant de cod cele k simboluri informationale sunt plasate grupat la inceputul sau la sfarsitul cuvantului de cod, codul sistematic. Daca nu este nesistematic.