Codarea surselor pentru canale de comunicatie fara perturbatii

Codarea surselor pentru canale de comunicatie fara perturbatii

Transmiterea informatiei la distanta, este afectata de erori sub forma perturbatiei. Atunci cand nu seiau in considerare aceste perturbatii, transmisiunea urmareste obtinerea debitului de informatie maxim. Transmiterea informatiilor pe un canal de comunicatie impune utilizarea unor multimi de simboluri acceptate de canalul de comunicatie, multime care se numeste alfabetul canalului sau alfabetul codului. Pentru a transmite informatii cu debit cat mai mare, se pune problema ca timpul necesar transmiterii unui simbol sa fie cat mai mic. Pentru o sursa S, presupunem ca canalul de comunicatie accepta simbolurile : X = , numit alfabetul canalului(codului). Pentru a putea transmite mesaje sursei S, este necesar sa se ataseze fiecarui mesaj al sursei S o succesiune de simboluri din alfabetul codului. Daca sursa are N mesaje, inseamna ca vom genera astfel o multime C numita a cuvintelor de cod, avand un numar de elemente egal cu numarul mesajelor : . Vom numi cod , corespondenta bijectiva dintre multimea mesajelor S si multimea cuvintelor de cod C.

Def.: un cod se numeste nesingular, daca tate cuvintele de cod sunt distincte.

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

Se cosidera o sursa S ce contine 4 mesaje : si un un alphabet al canalului X=. Trebuie sa generam o succesiune de coduri binare pentru fiecare mesaj al sursei S.

Sa presupunem ca mesajului :

Remarcam ca acest cod este nesingular dar este si unic decodat, deoarece o succesiune 1101 poate sa genereze 3 succesiuni distincte de mesaje :

Pentru ca sa fie unic decodabil, o prima solutie ar fi ca dupa fiecare cuvant de cod transmis sa se introduca un simbol distinct de delimitare la inceputul sau sfarsitul cuvantului . S-a propus o solutie particulara de construire a uni cod fara necesitatea de a marca un simbol distinct la inceputul sau sfarsitul unui cuvant.

Fie codul A constituit astfel:

si

Ambele sun tunic decodabile deoarece in cazul codului A, o este sfarsit de cuvant, iar in cazul codului B, 0 este inceput de cuvant.

Diferenta esentiala intre cele 2 coduri este:

-in cazul codului A interpretarea simbolurilor receptionate(decodarea), se realizeaza cuvant cu cuvant, in timp ce in cazul codului B decodarea se realizeaza numai dupa receptionarea primului simbol din cuvantul ce urmeaza. Diferenta evidentiata se datoreaza faptului ca in cazul codului A nici un cuvant de cod nu este prefix pentru altul, in timp ce la codul B acest lucru nu e valabil. Vom numi coduri instantanee, acele coduri pentru care nici un cuvant de cod nu este prefix pentru altul. In cazul codurilor binare, o regula simpla de construire a unui cod instantaneu este urmatoarea: se divide multimea mesajelor in cantitati cat mai egale construindu-se astfel 2 submultimi si atribuindu-se simbolul 0 uneia si 1 celeilalte.Asta inseamna ca din S am generat si . Acestea sunt din nou divizate, atribuindu-se 0 si 1 pentru fiecare.

etc.

Curs 8

K = M - numarul simbolurilor din alfabetul codului

l - lungimea cuvantului de cod

N- numarul acestora

Observatii legate de aceasta torema:

1. Daca s-a construit un cod avand lungimea cuvantului l . l care respecta inegalitatea lui Kraft atunci nu trebuie sa se traga concluzia ca acel cod este instantaneu.

Teorema precizeaza doar ca intotdeauna ce aceste lungimi (l . l) se poate construi un cod instantaneu.

2. Alta interpretare a teoremei

Daca lungimile cuvintelor e cod nu satisfac inegalitatea lui Kraft atunci inseamna ca prin nici un procedeu de codare nu se poate construi un cod instantaneu.

3. Daca un cod este instantaneu el este si unic decodabil. Codurile instantanee sunt o subclasa a celor unic decodabile.