Codarea surselor pentru canale pentru perturbații

In cazul transmiterii la mica distanta, perturbatiile sunt neglijabile, incat nu se pune problema protejarii informatiei la perturbatii ci posibilitatea de a transmite o cantitate de informatii intr-un timp cat mai scurt. Prin canal de transmisiuni se intelege orice mediu fizic prin care se poate transmite informatia. Functie de natura fizica a canalului de transmisiuni pot circula numai anumite simboluri, deci, pentru a transmite informatii pe canal, trebuie acceptate pe canal anumite simboluri, multimea acestor simboluri = alfabetul canalului (sau alfabetul codului)

Avand o sursa de o natura fizica oarecare de informatii, va trebui sa transformam mesajele acestora in succesiuni de simboluri acceptate de canal, pe de alta parte pentru a fi posibila transmisiunea, iar pe de alta parte pentru a realiza transmisiunea intr-un timp cat mai scurt.

Presupunem o sursa cu distributia:

Vom defini mai departe aceasta sursa, sursa primara. Presupunem in continuare ca simbolurile acceptate de canal, deci cele care se pot propaga, formeaza multimea X={x1,x2, ,xm}

In vederea realizarii transmisiunii pe un astfel de canal, fiecarui mesaj sk i se va atasa o succesiune de simboluri, din multimea X, succesiune ce va fi denumita prin cuvant de cod.

Notand Ck succesiunea xi1,xi2, ,xiexij=xk , inseamna ca mesajului i-am atasat cuvantul de con Ck. Se formeaza multimea cuvintelor de cod: C={c1,c2, ,cM}. Cod = corespondenta bijectiva intre multime C si S (={s1,s2, ,sM}).

2.2. Definirea codurilor pentru canale fara perturbatii

- aceasta sursa se mai numeste si sursa primara.

Mai presupunem ca un canal de transmisiuni accepta numai simbolurile X = { x1, x2, , xn }.Totalitatea acestor simboluri din multimea X poarta denumirea de alfabetul canalului, sau alfabetul canalului sau sursa secundara.

In scopul realizarii adaptarii sursei primare S la canal va trebui ca fiecarui mesaj sa i se ataseze un cuvant de cod, notat ck , cuvantul de cod fiind format dintr-o succesiune de simboluri din alfabetul codului in felul acesta se obtine o alta multime C C = { c1, c2, ,cN}.Se numeste cod corespondenta bijectiva dintre multimea S si multimea C.

Prin definitie, un cod se numeste nesingular, daca toate cuvintele de cod sunt directe.

Prin definitie, un cod se numeste unic decodabil daca fiecarei succesiuni din alfabetul codului ii corespunde o singura succesiune de mesaje.

Presupunem o sursa S, formata din multimea S = { s1, s2, s3, s4 } si alfabetul X={ 0, 1 }. Presupunem ca mesajului s1 ii atasam c1 format din 1

s2 - c2 - 01

s3 - c3 - 10

s4 - c4 - 11

Se observa ca in codul astfel intocmit, toate cuvintele de cod sunt distincte, deci codul este nesingular, in schimb codul nu este unic decodabil, deoarece, dupa cum se observa, succesiunii 1101 ii pot corespunde 3 succesiuni distincte de mesaje:

1101 s4 s2

s1 s1 s2

s1 s3 s1

Deci nu este unic decodabil.

Pentru a realiza un cod unic decodabil, o prima solutie ar fi ca, dupa fiecare cuvant de cod transmis, sa se insereze un nou simbol din alfabetul codului, distinct de cele folosite in formarea cuvintelor, care sa indice, fie inceputul fiecarui cuvant de cod, fie sfarsitul fiecarui cuvant de cod.

In cazul exemplului considerat, inseamna ca ar trebui un alfabet format din X={0,1,- }, astfel incat daca se receptioneaza succesiune 11- 01 se stie ca s-a transmis s4 s2.

Solutia nu este economica, pe de o parte pentru ca se lungeste succesiunea de simboluri necesara transmisiei, ceea ce inseamna un timp de transmisie mai lung, iar pe de alta parte necesita un canal care accepta 3 simboluri (mai pretentios si greu de realizat).

S-a pus problema construirii de coduri unic decodabile fara necesitatea simbolului de indicare a inceputului sau sfarsitului de cuvant.

Construim 2 coduri:

codul A: s1 - c1 - 0 codul B: s1 - c1 - 0

s2 - c2 - 10 s2 - c2 - 01

s3 - c3 - 110s3 - c3 - 011

s4 - c4 - 1110s4 - c4 - 0111

Prin modul de formare al celor doua coduri se observa ca atat codul A cat si B sunt unic decodabile, deoarece in cazul codului A, 0 specifica sfarsitul fiecarui cuvant de cod, iar la B, 0 specifica inceputul fiecarui cuvant de cod.

Totusi, intre codurile A si B exista o diferenta importanta. In cazul codului A, interpretarea simbolurilor receptionate, adica operatia de decodare, se realizeaza cuvant cu cuvant, in timp ce in cazul codului B, decodarea unui cuvant receptionat nu se poate realiza decat dupa receptionarea primului simbol din cuvantul urmator.

Daca presupunem ca s-ar receptiona 0, in cazul codului A stim sigur ca s-a transmis s1 in timp ce, in cazul codului B , s-ar putea sa se fi transmis fie s1 fie s2 fie s3 fie s4. Abia dupa receptionarea primului simbol din cuvantul urmator, pe poate preciza, la codul B, ca primul 0 corespunde lui s1.

Aceasta diferenta dintre codurile A, B se datoreaza faptului ca, in timp ce in cazul codului A nici un cuvant de cod nu