Scopul codarii si caile de realizare ale acestui scop (teorema a ii a a lui shannon)

SCOPUL CODARII SI CAILE DE REALIZARE ALE ACESTUI SCOP (TEOREMA A II A A LUI SHANNON)

In cazul transmiterii (stocarii) informatiei prin canale cu perturbatii (medii de stocare), semnalele receptionate pot fi alterate datorita zgomotului, fapt ce impune luarea unor masuri de protectie pentru reducerea acestor efecte nedorite. Problema protectiei la erori s-a intensificat o data cu utilizarea retelelor nationale si internationale de transmisiuni de date de mare viteza in schimbul, procesarea si stocarea informatiilor provenind din cele mai diverse domenii de activitate :public, privat si militar.

Raspunsul la intrebarea :

Cum poate fi realizata protectia la perturbatii in cazul transmiterii sau stocarii informatiei?

a fost dat de C.E.Shannon in lucrarea "A mathematical theory of communication" (1948) si constituie ceea ce este cunoscut sub denumirea de teorema a-II-a lui Shannon (teorema codarii canalelor cu perturbatii). El a demonstrat ca :

pe orice canal cu perturbatii de capacitate C, se poate face o transmisie a unei surse de informatie in timp real (cu un debit ) cu o probabilitate a erorii P(E) oricit de mica, utilizind un cod de lungime n, atfel incit:

(1)

unde :n este lungimea cuvintelor de cod

este o functie pozitiva de , complet determinata de caracteristicile canalului, numita exponent al erorii, de forma (fig 1.):

C

Fig. 1 Graficul exponentului erorii

Observatie :

_i reprezinta debitul informational al sursei : =R, unde R=m/n iar _c este debitul sursei codate, m = numarul simbolurilor informationale

alfabetul canalului a fost presupus binar dar teorema isi pastreza valabilitatea pentru orice baza.

Interpretarea teoremei a-II-a a lui Shannon

aceasta teorema afirma un lucru surprinzator si anume ca indiferent de zgomotul existent intr­-un canal, este posibila o transmitere cu o probabilitate a erorii oricit de mica

fara a da algoritmi de realizare a unei asemenea transmisiuni, teorema arata si caile de realizare ale unei P(E) oricit de mici:

-transmiterea cu debit mic, caz in care se vede din fig. 1 ca creste, deci P(E) scade ; este neutilizata in practica datorita folosirii ineficiente a canalului.

-utilizarea unor lungimi n ale cuvintelor de cod mari, ceea ce inseamna introducerea deliberata de redundanta inainte de transmitere ; aceasta este calea utilizata in practica pentru protectie la perturbatii (folosirea codurilor redundante pentru protectie la erori).

Vom ilustra in continuare printr-un exemplu simplu necesitatea introducerii redundantei pentru realizarea detectiei sau corectiei erorilor :

Exemplul 1

Fie sursa echiprobabila. In ipoteza transmiterii pe un canal binar simetric avind p cunoscut, vom analiza doua situatii :

a)     Codare neredundanta : rezulta lungimea cuvintelor de cod : n=m=1, unde prin m am notat numarul simbolurilor informationale (cele utilizate nemijlocit in codarea informatiei) si deci codul C₁=. In acest caz in urma transmiterii prin CBS vom receptiona tot simboluri 0 si 1, nefiind posibil a face distinctie daca simbolul este corect sau eronat, probabilitatea de eroare fiind in aceste caz :P₁(E)=p.

b)     Codare redundanta : in loc de un singur simbol de informatie, vom transmite n=3 simboluri, deci vom introduce k=n-m=3-1=2 simboluri redundante (de control), astfel incit codul obtinut va fi :

C₂=.

Intrare  Iesire

CBS

Fig. 2 Reprezentarea intrarii si iesirii unui CBS pentru codarea

La transmiterea printr-un CBS se obtine situatia ilustrata in fig 2.Se observa ca din cele 8 secvente posibile de la iesirea CBS, numai doua corespund secventelor de cod, deci in celelate 6 se face detectia erorii. Daca se adopta ca regula de decizie criteriul alegerii majoritare, adica se vor considera ca bune secventele ce contin doi de 0 si un 1 sau doi de 1 si un 0 admitind ca ele corespund secventelor 000 si 111, este posibila corectia si in celelalte situatii detectate ca eronate.

Evident, deciziile luate la receptie sint supuse unui risc ce poate fi evaluat. Chiar si in situtia receptionarii secventelor de cod 000 si 111 exista riscul ca acestea sa provina din eronarea celor trei biti. In ipoteza erorilor independente, valoarea acestui risc este p₃=p³. In mod analog (invitam cititorul sa faca aceasta judecata) se calculeaza riscul aparitiei a doua erori intr-un cuvint de lungime trei p₂=3p²(1-p).

Valoarea totala a riscului in acest caz (probabilitatea de eroare dupa decodare ) este:

P₂(E)=p₂+p₃=3p²(1-p)+p³=p²(3-2p)3p².

Se observa reducerea riscului initial de la P₁(E)=p la P₂(E)= 3p² .

Se pune o a doua intrebare :

Care este pretul platit pentru obtinerea unei probabilitati a erorii oricit de mici pe seama cresterii redundantei?

Raspunsul la intrebare se va obtine rationind dupa cum urmeaza. Daca dorim sa pastram nemodificat debitul sursei de informatie (_i) :

_i= (2)

unde T_bi este durata unui bit informational, atunci prin adaugarea celor k simboluri redundante (fig 3), se obtine :

(3)

in care s-a notat cu T_bc durata corespunzatoare unui bit dintr-un cuvint codat de lungime n.

Fig 3 Ilustrarea relatiei intre duratele bitilor de informatie si a bitilor codati

in cazul pastrarii debitului de informatie nemodificat prin codare

Din (3) obtinem :

. (4)

Raportul :

(5)

poarta denumirea de rata de codare

Relatia (3) poate fi scrisa sub forma :

(6) deci prin codare, la pastrarea = ct., se obtine o crestere a debitului codat . Stiind relatia de directa proportionalitate dintre si banda (B) rezulta ca pretul platit prin codare pentru protectie la erori, la pastrarea unui =ct, este cresterea benzii de transmitere (spatiului de stocare ) si implicit o crestere a zgomotului la receptie. In cazul in care nu este posibila marirea benzii, se procedeaza la utilizarea unor procedee de codare si modulatie ce produc o compresie a benzii (modulatii m-are de faza, modulatie trellis [Sk-88]).

Observatie :

Intreaga discutie facuta in acest paragraf s-a facut in ipoteza unei puteri constante la emisie si fara analiza efectului sistemului de modulatie si a formei semnalelor transmise (modulatia si deciziile statistice constituie obiectul partii a doua a cursului).

In cadrul unui sistem complet de transmisie (stocare ) a informatiei, locul blocului de codare a canalului (C_c) se situeaza ca in fig. 4.

Fig. 4 Pozitionarea blocului de codare a canalului in cadrul unui

sistem complet de transmitere (stocare a informatiei)