Teoria Transmiterii Si Codificarii Informatiei 2011

Teoria transmiterii i codificrii informaiei

Page 1 of 83

UNIVERSITATEA TITU MAIORESCU

Facultatea de INFORMATIC

Profesor univ. dr. ing. Lector univ. dr.ing.

RCUCIU CIPRIAN GRECU DAN

Curs pentru nvmntul la distan

BUCURETI 2011


Page 2 of 83

UNIVERSITATEA Titu MAIORESCU BUCURETI Facultatea de Informatic nvmnt la Distan

TEORIA TRANSMITERII I CODIFICRII INFORMAIEI

Cursul Teoria transmiterii i codificrii informaiei este o disciplin care ngobleaz ntr-o form unitar concepte din teoria codurilor, teoria semnalelor aleatoare i teoria deciziilor statistice i reprezint una din disciplinele de pregtire care, pentru profilul INFORMATIC, fiind necesar pentru pregtirea studenilor i pentru obinerea creditelor transferabile prin procedurile de evaluare. Modul de prezentare a acestui material are n vedere particularitile nvmntului la distan, la care studiul individual este determinant. Pentru orice nelmuriri fa de acest material v rugm s contactai tutorele de disciplin care are datoria s v ajute oferindu-v toate explicaiile necesare.

Disciplina Teoria transmiterii i codificrii informaiei i propune urmtoarele obiective specifice:

1. nsuirea noiunilor fundamentale din teoria informaiei i din teoria codurilor redundante care stau la baza prelucrrii informaiei, n vederea protejrii acesteia mpotriva perturbaiilor de diferite tipuri.

Dobndirea deprinderilor practice privind realizarea schemelor secveniale liniare de codare i decodare pentru diferite clase de coduri cum sunt: codurile liniare i codurile ciclice.

ntocmirea algoritmilor de codare i decodare i folosirea calculatorului electronic de ctre studeni pentru modelarea canalelor de transmisiuni i a funcionrii dispozitivelor de codare i decodare.

Competenele specifice disciplinei Teoria transmiterii i codificrii informaiei se pot clasifica dup cum urmeaz:

1. Cunoatere i nelegere

Intelegerea noiunilor fundamentale cu care se opereaz n teoria transmiterii i codificrii informaiei:

Cunoasterea si inelegerea algoritmilor de codare i decodare a surselor informaionale care au aplicabilitate n domeniul informaticii;

Cunoasterea si inelegerea algoritmilor de codare i decodare a informaiilor care sunt transmise prin canalul de comunicaie.

2. Explicare i interpretare

Explicarea si interpretarea conceptelor referitoare la entropia informaional, cantitate de informaie etc;

Explicarea modalitatilor de functionare a algoritmilor specifici disciplinei.

3. Instrumental aplicative

Implementarea ntr-un limbaj de programare a algoritmilor specifici disciplinei;


Page 3 of 83

Proiectarea aplicaiilor pentru rezolvarea unor probleme utiliznd instrumente specifice de structurare a datelor;

Corelarea cunotinelor teoretice cu abilitatea de a le aplica n practic;

Elaborarea unui proiect care sa scoat in eviden importana algoritmilor specifici disciplinei.

4. Atitudinale

Manifestarea unor atitudini favorabile fa de tiin i de cunoatere n general;

Formarea obinuinelor de a recurge la concepte i metode informatice de tip algoritmic specifice n abordarea unei varieti de probleme;

Exprimarea unui mod de gndire creativ n structurarea i rezolvarea problemelor.

Structura cursului este urmtoarea: Modulul 1

1. UNITATEA DE NVARE 1 - ELEMENTE DE TEORIA TRANSMITERII INFORMAIEI

2. UNITATEA DE NVARE 2 - MSURI INFORMAIONALE. Modulul 2

1. UNITATEA DE NVARE 3 - CODAREA SURSELOR INFORMAIONALE; 2. UNITATEA DE NVARE 4 - CANALE DE TRANSMITERE A INFORMAIEI Modulul 3

1. UNITATEA DE NVARE 5 - CODURI DETECTOARE I CORECTOARE DE ERORI;

2. UNITATEA DE NVARE 6 CODURI LINIARE

Este foarte important ca parcurgerea materialului sa se faca in ordinea unitilor de nvare incluse. Fiecare UI (unitate de nvare) conine, pe langa prezentarea notiunilor teoretice, exerciii rezolvate, activiti de lucru individual la care sunt prezentate i indicaii de rezolvare, exemple, i teste de autoevaluare. n plus, la sfritul fiecrei UI sunt incluse probleme propuse care testeaza cunoasterea notiunilor teoretice de catre student.

Materialul a fost elaborat astfel incat algoritmii prezentati s poat fi implementati n orice limbaj de programare. Pentru a face o alegere, limbajul de programare folosit in aplicaii va fi limbajul C/C++.

Pachet software recomandat:

Orice IDE (Integrated Development Environment) pentru limbajul C/C++ poate fi folosit, dar

pentru a face o alegere, mai puin costisitoare, de altfel gratuit, v sugerm IDE-ul numit Dev-Cpp care se poate descrca de pe site-ul http://www.bloodshed.net/dev/devcpp.html.

Bibliografia recomandat se regsete la sfritul fiecrui modul informaional.


Page 4 of 83

La stabilirea notei finale se iau n

considerare

Ponderea n notare, exprimat n % {Total = 100%}

rspunsurile la examen (evaluarea final)

rspunsurile finale la lucrrile practice de laborator

testarea periodic prin teme pentru acasa

testarea continu pe parcursul semestrului

activitile gen proiecte

50%

20%

10%

10%

10%

Modalitatea de evaluare final: lucrare scris descriptiv i/sau probleme

Cerine minime pentru nota 5 Cerine minime pentru nota 10

nsuirea cunotinelor de baz

Obinerea unui procent de cel putin 45% din procentul maxim alocat

fiecarei activitati care se considera in

stabilirea notei finale.

Activitate n timpul semestrului

Rezolvarea corect i complet a subiectelor de examen

Efectuarea corecta si completa a temelor pentru acasa

Participarea activ la curs si laborator

Elaborarea unui proiect corect, complet si bine documentat

V precizm de asemenea c, din punct de vedere al verificrilor i al notrii, cu adevrat important este capacitatea pe care trebuie s o dobndii i s o probai de a rezolva toat tipologia de probleme aplicative aferente materialului teoretic prezentat n continuare. De aceea v recomandm s parcurgei cu atenie toate aplicaiile rezolvate, s rezolvai aplicaiile propuse prin testele de autoevaluare i temele de control; fii convini c examenul final apeleaz la tipurile de aplicaii prezente n seciunile menionate anterior.


Page 5 of 83

MODULUL 1

MSURA CANTITATIV A INFORMAIEI

n acest modul sunt prezentate principalele noiuni cu care opereaz teoria informaiei. Notiunea de informatie a aparut mult mai tarziu decat notiunea de energie, iar legile dupa care

informatia apare, se transforma, se pastreaza, se prelucreaza si se foloseste sunt inca insuficient

studiate; abia in zilele noastre se stabilesc bazele intelegerii lor, se elucideaza metodele de studiu si

investigare.

Stabilirea notiunii generalizate de informatie pentru caracterizarea proceselor de conducere

dintr-un punct de vedere unitar,a fost un moment important in stiinta. Intocmai cum introducerea

notiunii de energie a permis sa se analizeze toate fenomenele naturii dintr-un punct de vedere unic,

independent de substratul lor fizic, tot asa,introducerea notiunii de informafie a permis studierea

dintr-un punct de vedere comun a celor mai diferite procese de comanda din natura.

Se numeste informatie orice stire care poarta in sine urma unui fapt, eveniment sau proces

oarecare.

Informatia este comunicarea (mesajul) ce aduce stiri despre fapte, evenimente, obiecte,

procese.In intelesul mai larg, in nofiunea de informatie se pot cuprinde toate stirile despre mediul

care ne inconjoara sau, mai bine zis, care se obtin, in interactiunea omului cu mediul inconjurator. A

obtine o informatie inseamna a afla lucruri ce nu se cunosteau mai inainte sau a obtine noi

cunostinte asupra unui lucru, fapt etc., despre care s-a stiut mai putin inainte.

Acest modul conine dou uniti de nvare i anume: 3. UNITATEA DE NVARE 1 - ELEMENTE DE TEORIA TRANSMITERII

INFORMAIEI 4. UNITATEA DE NVARE 2 - MSURI INFORMAIONALE.

Obiective urmrite: La sfritul parcurgerii acestor uniti de nvare, studenii: vor nelege noiunile fundamentale cu care opereaz Teoria informaiei i care se refer la:

semnal, perturbaie, mesaj, informaie, canale de transmisiuni, codificare, decodificare, probabilitatea erorii de transmisie, complexitatea dispozitivelor de prelucrare a informaiei etc.

vor ti s interpreteze i s opereze cu instrumente matematice care se refer la: modelul probabilistic al surselor discrete de informaie, definiia i proprietile cantitii de informaie: I(x;y), I(X;Y), I(x), I(x/y), I(x;y/z), informaia reciproc dintre un numr arbitrar de evenimente, Entropia i proprietile ei, etc.

vor ti s implementeze ntr-un limbaj de programare sau simulare principalele mrimi studiate.

Timpul mediu necesar nsuirii noiunilor teoretice, formrii deprinderilor de calcul i utilizrii metodelor de rezolvare a problemelor specifice teoriei informaiei este estimat la aproximativ 4-5 ore pentru fiecare unitate de nvare, ntr-un ritm de 2-3 ore pe zi.


Page 6 of 83

MODULUL 1 UNITATEA DE NVARE 1

ELEMENTE DE TEORIA TRANSMITERII INFORMAIEI

1.1. Informatia generaliti.

n procesele de comanda, procesele energetice care insotesc transmiterea informatiei joaca

un rol secundar. Cantitatea de informatie si cu atat mai mult efectul ei,nu sunt determinate de

cantitatea de energie folosita pentru transmiterea infornafiei. Esenta proceselor de conducere, care se

desfasoara pe baza schimbului de informatie, consta tocmai in aceea ca miscarea si actiunea unor

mase materiale mari sau transmiterea si transformarea unor cantitati mari de energie se dirijeaza si

se controleaza cu ajutorul unor mase materiale mici si al unor cantitati reduse de energie.

n teoria informatiei, caracteristica energetica a fenomenelor trece pe plan secundar,

evidentiindu-se in mod deosebit latura informafionala a sistemului.

Asadar, notiunea de informatie este foarte larga si se poate prezenta sub cele mai variate

forme: aceasta constituie o proprietate de seama a informatiei. Prin mijloacele de telecomunicatii -

telefon,telegraf, radio - se transmit informantii. Prin intermediul vazului, auzului, precum si al

celorlalte simturi, omul primeste zilnic tot felul de informafii despre evenimentele din lumea ce il

inconjoara.

Comunicari complexe, ordine si dispozitiuni se transmit cu ajutorul telefonului, telegrafului

si radioului. Comunicari si mai complexe sunt cele transmise prin intermediul televiziunii, unde

imaginile in miscare sunt insotite de semnale audio.La toate aceste sisteme, transmiterea informatiei

este insotita de un fenomen nedorit,de adaugare la informatia transmisa a unor semnale

perturbatoare ce nu au fost produse de sursele initiale de informantii; in telefonie se distorsioneaza

semnalul de vorbire, in televiziune se deformeaza imaginea, in telegrafie apar greseli de imprimare.

Aceste exemple evidentiaza o alta proprietate de baza a informatiei: in nici un sistem fizic

informatia nu apare intr-o forma curata ci este insotita de diferite perturbatii care pot duce la greseli.

De aceea,una din problemele principale ale teoriei informatiei consta in stabilirea metodelor optime

pentru extragerea informatiei din semnalele care sunt insotite de perturbatii. Notiunea de informatie

a cucerit un loc sigur in stiinta numai atunci cand s-a gasit o masura adecvata pentru caracterizarea

ei. O alta proprietate de seama a informatiei este aceea de a putea fi masurata. Nu este suficient insa

sa se gaseasca o modalitate de masurare a informafiei: trebuie sa existe posibilitatea folosirii acestei

masuri, adica sa existe siguranta ca se pastreaza obiectul masuratorii. Tot asa, informatia care ia

nastere in cadrul unui sistem bine definit si se pastreaza in limitele sistemului respectiv, poate fi

masurata, indiferent de natura sistemului.

Problema principala a teoriei informatiei este studierea transformarii, pastrarii si transmiterii

informatiei. Analiza acestui fenomen a fost facuta pentru prima data de inginerii de telecomunicatii,

care s-au ocupat cu organizarea canalelor destinate transmiterii informatiei.

n realitate, informatia se transmite prin intermediul semnalelor care poarta stirea. Tipuri de

informatie :informatii numerice, informatii logice, de tip text, informatii multimedia:audio, imagine,

video, semnale .


Page 7 of 83

1.2. Sistemul de transmitere a informatiei.

Purtatorul material al informatiei - semnalul - isi pastreaza capacitatea sa de a transmite

informatia numai in cadrul unui sistem de transmisiuni; schema bloc destul de generala a unui

sistem de transmisiuni este data in fig.1.1

Fig.1.1

Coderul din fig.1.1 executa orice prelucrare a semnalului generat de sursa. O asemenea

prelucrare poate include, de exemplu, o anumita combinatie de modulatie, comprimare de date sau

introducerea unei redundante pentru lupta cu perturbatiile.

Canalul este mediul fizic utilizat pentru transmiterea semanalului:de exemplu linia

telefonica, linia radio sau radioreleu, dispozitivul de memorie sau organismul uman. Asupra

canalului, de regula, actioneaza diferite perturbatii care in liniile de telefonie pot apare din cauza

modificarilor caracteristicii de frecventa, a convorbirilor ce se induc din alte linii, a zgomotului

termic, a impulsurilor parazite, sursa carora pot fi schemele de comutare, a bruiajului intentionat al

adversarului etc.

Decoderul executa prelucrarea semnalului de la iesirea canalului in scopul de a reproduce la

partea de receptie o copie acceptabila iesirii sursei.

Destinatarul poate fi omul sau un dispozitiv tehnic oarecare. Pentru a simplifica analiza

modelelor de surse si canale este de dorit a separa efectele legate de sursa de efectele legate de

canal.

Sarcina coderului sursei este de a reprezenta iesirea sursei cu ajutorul succesiunilor de

semnale binare, si una din problemele importante ce apar, consta in a stabili cate simboluri binare,in

unitatea de timp sunt necesare pentru reprezentarea semnalului de la iesirea unei surse date.

Sarcina coderului si decoderului canalului consta in a reproduce cat mai sigur succesiunile

binare ale datelor obtinute la iesirea decoderului canalului si una din problemele inportante ce apare

este, daca acest lucru este posibil sa se faca,si cum sa se faca.

Coderul sursei transforma mesajul de la iesirea sursei intr-o succesiune de semnale binare

sau care apartin unui alfabet finit, din care decoderul sursei restabileste mesajul initial cu o precizie

adoptata de catre destinatar. Astfel, independent de proprietatile sursei sau destinatarului, la intrarea

coderului canalului si la iesirea decoderului canalului,se formeaza o succesiune de simboluri binare

sau de simboluri care apartin unui alfabet finit. Reprezentarea informatiei de transmis sub forma

unei succesiuni binare intermediare da posibilitatea sa se calculeze si sa se construiasca dispozitive

de codificare si decodificare de canal, independent de dispozitivele corespunzatoare care se refera la

sursa. Sarcina sistemului de transmisiuni, este de a transmite mesajul de la sursa la destinatar, adica

de a reproduce mesajul de la iesirea sursei la locul indicat de destinatar. Cand spunem reproduce" nu intelegem o reproducere absolut fidela ci o reproducere care corespunde anumitor scopuri

specifice.Criteriul acceptabilitatii depinde de scopul transmisiuni. n descrierea obiectului" transmis prin sistemul de transmisie trebuie inclus si criteriul acceptabilitatii. Astfel, obiectul ce se


Page 8 of 83

transmite nu determina numai proprietatile sursei, ci caracterizeaza proprietatile cuplulul sursa-destinatar". Vom numi acest obiect informatia transmisa".

1.3. Modele de surse informationale.

Ideea fractionarii mesajelor posibile la iesirea sursei intr-o multine discreta de clase are o

importanta fundamentala, intrucat conduce la enumerarea reprezentantilor claselor din intervalul de

timp dat. Multimea claselor se numeste multimea de mesaje posibile din intervalul de timp dat,

admisibile pe timpul transmisiei.Sarcina sistemului de transmisiuni consta in reproducerea mesajului

de la iesirea sursei cu o precizie adoptata de catre destinatar. Existenta criteriului de precizie permite

sa se grupeze toate mesajele posibile, in orice interval de timp, de la iesirea sursei in clase disjuncte.

Sistemul de transmisiuni indica destinatarului clasa din care face parte mesajul respectiv.

Toate sursele in teoria informatiei se modeleaza cu ajutorul proceselor sau succesiunilor

aleatorii. Cea mai simpla clasa de modele de surse este clasa surselor discrete fara memorie. La

aceste surse iesirea este o succesiune (in timp) de litere, fiecare din ele alese dintr-un alfabet dat, a1,

a2, ..., ak. Succesiunea la iesirea sursei este formata din aceste litere alese din alfabet statistic

independent si intamplator, alegere ce are la baza o repartitie oarecare de probabilitati P(a1), ...,

p(ak). n cazul unei codificari de acest tip, combinatiile de cod vor avea aceeasi lungime pentru ca

sa fie posibila decodificarea lor.

Remarcam faptul ca scrierea numerelor, in cazul transmiterii mesajelor admisinile, intr-o

forma binara nu are o importanta principala. Ele pot fi scrise in orice sistem de numeratie.Prezinta

importanta posibilitatea insasi de transformare a mesajului admisibil intr-o succesiune de simboluri

care fac parte dintr-un alfabet finit.Rationamentul prezentat permite sa se presupuna ca numarul de

mesaje admisibile sau numarul de simboluri binare, necesare pentru reprezentarea fiecarui mesaj din

multimea mesajelor posibile , poate fi luata ca o masura a cantitatii de informatie transmisa de sursa

intr-un interval de timp. Dar, dupa cum vom vedea, aceasta presupunere este justa numai intr-un

anumit caz. Numarul M de mesaje admise nu descrie complet multimea mesajelor si este necesar sa

se ia in consideratie si probabilitatile cu care sunt generate aceste mesaje admisibile.

Prima teorema a lui C. Shannon - teorema fundamentala a codificarii in lipsa zgomotelor da

tocmai o limita inferioara si una superioara pentru lungimea medie a combinatiilor de cod.

Probabilitatile p(ai) depind de caracteristicile statistice ale sursei si de procedeul de grupare a

mesajelor posibile in clase de echivalenta. In afara de aceasta, numarul mediu de sinboluri

binare,generate intr-o secunda, depinde de intervalul de timp T cu care s-a lucrat la gruparea

mesajelor in clase de echivalenta. Pentru a mari eficacitatea sistemulul de transmisiuni se cauta sa se

minimizeze numarul mediu de simboluri binare generate intr-o secunda de coderul sursei.

Unul din rezultatele principale ale teoriei transmisiunii informatiei este: in cazul unor

conditii destul de generale poate fi indicat numarul R, care, pentru fiecare cuplu sursa-destinatar,

exprima viteza de generare a informatiei pentru un criteriu de precizie adoptat. Aceasta viteza se

determina ca cel mai mic numar mediu de simboluri binare intr-o secunda, care trebuie sa se

transmita pentru ca mesajul sa poata fi reprodus in conformitate cu criteriul de precizie adoptat.


Page 9 of 83

1.4. Modelul probabilistic al semnalelor.

Avand in vedere ca pentru orice fenomen din natura sau din societate aprecierile cantitative

constituie o conditie de baza a analizei stiintifice s-a cautat o modalitate pentu calculul cantitatii de

informatie si s-a stabilit o unitate de masura pentru informatia continuta intr-un semnal purtator de

informatie. La calculul cantitatii de informatie si la stabilirea unitatii de masura a informatiei se

pleaca de la o descriere probabilistica a semnalelor si se considera semnalele ca evenimente

aleatoare.

Semnalele discrete care intervin in diferite sisteme informationale, destinate transmiterii si

prelucrarii datelor, permit o tratare corespunzatoare probabilistica, iar semnalele continue, de

asemenea, permit o descriere probabilistica dupa discretizare - ceea ce se face cu ocazia observarii

cu o precizie data. Astfel, puten conchide universalitatea cantitatii de informatie obtinuta pe baza

unui model probabilistic.

Unitatea de masura a informatiei se refera numai la partea cantitativa a informatiei si

intotdeauna se face abstractie de continutul semantic al mesajului. Cauza acestei tratari unilaterale

rezida in faptul ca aparatul matematic existent deocamdata,nu ne permite efectuarea unui studiu

calitativ al informatiei. Construirea unui model probabilistic pentru semnalele discrete - utilizate in

cadrul unui sistem informational dat - presupune cunoasterea probabilitatilor cu care apar aceste

semnale in urma unui experiment. Aparitia unui semnal in cadrul unui experiment se considera ca

un eveniment.

n cazul semnalelor discrete, totdeauna se poate realiza o corespondenta biunivoca intre

semnalele posibile si intre o multime de numere naturale X - facand ca fiecarui semnal sa

corespunda un numar natural x X- si astfel multimea semnalelor discrete se poate inlocui cu o multime de numere naturale X. In continuare, prin x se intelege fie un semnal oarecare, fie numarul

natural care corespunde semnalului respectiv.

Modelul probabilistic al semnalelor X este dat prin urmatoarea repartitie a variabilei

aleatoare:

MXXX

M

xPxPxP

xxxX

...

...

21

21 (1,1)

Prin notatia se intelege probabilitatea de aparitie a evenimentului x=xk, adica

probabilitatea de aparitie a semnalului care corespunde lui xk si care face parte din multimea X

considerata. Evident:

11

K

M

K

X xP (1.2)

Probabilitatea ca rezultatul experimentului va fi un element oarecare x, se noteaza cu Px(x)

in care, prin indicele X se accentueaza ca rezultatul experimentului este un semnal din multimea

semnalelor posibile X. In cazul cand nu exista ambiguitati in privinta apartenentei lui x se poate

suprima indicele X. Experimentele cu mai multe rezultate simultane vor fi caracterizate prin

elementele unui produs de multimi si prin probabilitatile de aparitie a acestor elemente.

Atunci cnd se face referire la capacitatea unui sistem de a transmite informaii apare necesitatea de a exprima cantitatea respectiv de informaii.

O informaie este coninut ntr-un mesaj. Un mesaj reprezint o succesiune de

kX xP


Page 10 of 83

simboluri convenionale. Acestea pot fi :cuvinte, sunete, cifre etc.

Fie S={s1,s2,..,sn} o muime de simboluri numite simboluri primare. Un bun exemplu de muime de simboluri primare o constitue alfabetul limbii romne. Fiecare liter constituie n acest caz un simbol primar.

Fie T={t1,t2,..,tm} o mulime de simboluri numite simboluri secundare. Un simbol secundar reprezint o combinaie de simboluri primare. Un bun exemplu de mulime de simboluri secundare este cel al mulimii tuturor cuvintelor aprinnd limbii romne.

S-ar prea c numrul cuvintelor unei limbi ar putea constitui o msur cantitativ a informaiei. ns cuvintele nu au aceeai valoare n ceea ce privete precizia ce este adugat ideii ce trebuie transmis. n consecin, cuvntul nu poate servi ca unitate de msur a informaiei.

Printr-un raionament analog se concluzioneaz c nici litera nu poate constitui unitatea de msur a informaiei. ns putem considera c informaia coninut ntr-un cuvnt trebuie s fie proporional cu numrul de litere coninute de respectivul cuvnt. Mai general, cantitatea de informaie coninut de un simbol secundar este proporional cu numrul simbolurilor primare coninute.

S considerm totalitatea simbolurilor secundare ce corespund combinaiilor posibile de u simboluri primare. Numrul acestor simboluri secundare este nu. S considerm de asemenea dou sisteme pentru care n are valorile n1 i n2. O aceeai cantitate de informaie I reprezentat n cadrul fiecruia dintre cele dou sisteme se va scrie:

= 11 = 22 (1.3)

n acest cadru se impune urmtoarea egalitate:

11 = 2

2 (1.4)

Din (1.3) i (1.4) rezult relaia:

1

log 1=

2

log 2= 0 (1.5)

Relaia (1.5) va fi satisfcut pentru toate valorile lui n numai dac ntre k i n exist relaia:

= 0 log (1.6)

Cum baza algoritmului este arbitrar, o vom alege astfel nct s rezulte:

= log (1.7)

Cantitatea de informaie se poate acum exprima prin:

= log = log (1.8) Rezult astfel o prim msur practic a informaiei: logaritmul numrului de combinaii

posibile a celor n simboluri primare pe lungimi de u simboluri.

Probabilitatea de apariie a unui simbol primar pe o poziie orecare n cuvntul de


Page 11 of 83

reprezentare a informaiei, este: 1

Relaia (1.8) devine:

= log1

= log (1.9)

Relaia (1.9) constitue o expresie pentru cantitatea de informaie. Este necesar n continuare stabilirea unei uniti de msur. Drept unitate de msur a cantitii de informaie s-a luat msura alegerii celei mai simple posibile, alegerea unei posibilitii din dou egal probabile. Deci, unitatea de msur se definete pentru u=1, n=2 i p=1/2. Totodat logaritmul este considerat n baza 2. n concluzie, relaia (1.9) conduce la:

= 1 22 = 1 (1.10)

Aceast unitate informaional a cptat denumirea de bit (de la binary unit) i a fost propus n 1928 de ctre Hartley.

Se pote constata c frecvena simbolurilor primare n cadrul simbolurilor secundare nu este aceeai. Rezult c nici probabilitile de apariie a simbolurilor primare n cadrul simbolurilor secundare purttoare de informaie (n cadrul mesajului) nu sunt egale. Fiecrui simbol primar si i se poate atribui deci o probabilitate aprioric Pi. Ne ateptm astfel ca apariia unui simbol primar ce prezint o probabilitate mic s aduc mai mult informaie. Astfel rezult c dac p=1 evenimentul este sigur i log p=log 1=0, deci informaia coninut este nul.

O surs de informaie emite o multitudine de mesaje diferite de lungime u. De aceea se convine s se exprime nu cantitatea de informaie din fiecare mesaj ci cantitatea medie de informaie pe un mesaj din setul respectiv de mesaje. Cum contribuia unui simbol si din mesaj este log pi, contribuia medie a simbolurilor si din mesaj este upilogp deoarece, pentru u suficient de mare, numrul simbolurilor si n mesaj se apropie de numrul lor mediu, upi, iar contribuia total este numrul lor mediu nmulit cu contribuia fiecruia. Altfel spus, simbolul si poate s apar pe prima poziie a cuvntului sau pe cea de-a doua poziie sau pe cea de-a treia poziie sau .sau pe ultima poziie. Deci:

= 1/ + 1/+ 1/ = / = 1/ = (1.11)

Aici s-a considerat cazul cel mai simplu, cel al probabilitilor pi=1/n egale.

Informaia medie total coninut n mesajul format din u simboluri este suma contribuiilor medii a tuturor celor n simboluri:

= 1 log1 2 log2 = =1 log (1.12)

Informaia medie pe simbol se va scrie:


Page 12 of 83

=

=

=1 log (1.13)

M rimea H a c p tat numele de entropie a sursei de informatie, deoarece formal, ca expresie matematic, ea este analog entropiei termodinamice a unui sistem, stabilit de Boltzmann.

Observaie: Semnificaia fizic a msurii cantitii de informaie astfel obinut este aceea c ea d num rul minim de operaii (de alegeri) necesare pentru a ridica nedeterminarea.

Exerciii rezolvate.

1. Unul din cele M mesaje, egal probabile, furnizeaz 3 bii de informaie. S de determine M.

Rezolvare: = 2 = 3, de unde rezult M=23=8 mesaje.

2. S se determine cantiatea de informaie, coninut ntr-un mesaj de 3,4,5 sau de 6 litere binare, echiprobabile.

Rezolvare: I3=log2 23=3 bii.

I4=log2 24=4 bii.

I5=log2 25=5 bii.

I6=log2 26=6 bii.

3. S se determine cantiatea de informaie furnizat de o liter dintr-un alfabet de 16, 25 i 32 de litere echiprobabile.

Rezolvare: I1=log2 16=4 bii. I2=log2 25=4,64386 bii. I3=log2 32=5 bii.

TESTE DE AUTOEVALUARE

1. S se determine cantitatea de informaie, coninut n 8 mesaje, nelegnd printr-un mesaj o succesiune de 4 semnale ternare echiprobabile.

2. S se determine cantitatea de informaie obinut prin anunarea ieirii din funciune a unui aparat de msur din cele 8 existente.

3. S se determine numrul simbolurilor dintr-un mesaj (lungimea mesajului) care conine o cantitate de informaie de 42 de bii i este format cu ajutorul a 128 de litere echiprobabile.


Page 13 of 83


MSURI INFORMAIONALE

2.1. Modele de surse informationale

Informatia proprie, ca si informatia reciproca se poate considera ca o variabila aleatoare

si se calculeaza valoarea sa medie. Valoarea medie a informatiei proprii pentru evenimente din

multinea X se numeste entropia lui X si se calculeaza cu formula:

(1.14)

sau mai simplu se scrie sub forma:

(1.15)

Variatia entropiei unui sistem de evenimente format din doua evenimente in functie de

repartitia de probabilitati este data in fig 1.2:

Fig.1.2 Entropia semnalului

Fie

KX

K

K

K

XxP

xPXH1

log1

xP

xPXHK

1log

1


Page 14 of 83

(1.16)

atunci:

(1.17)

2.2. Informatia proprie conditionata.

Cantitatea de informatie proprie conditionata a evenimentului X=Xk ,cu conditia ca a

aparut evenimentul Y=Yi se defineste pe produsul cartezian XY si se calculeaza cu formula:

(1.18)

sau mai simplu se scrie:

(1.19)

Aceasta cantitate de informatie proprie a evenimentului X=Xk, conditionata de

evenimentul y=yi se poate interpreta ca informatia necesara pentru specificarea evenimentului

x=xk . dtupa ce a avut loc evenimentul y =yi.

Cu ajutorul relatiilor anterioare se poate exprima cantitatea de informatie reciproca ca o

diferenta intre informatia proprie si informatia proprie conditionata.

(1.20)

de unde

(1.21)

Din relatia anterioara se obtine pe baza reciprocitatii relatia:

(1.22)

In mod analog I(x;y) se poate scrie sub forma:

pp

xxX

1

21

pHp

pp

pXH

1

1log1

1log

i

k

y

x

i

k

Y

X

y

xP

y

xI

1log

i

k

x

y

xP

y

xI

1log

y

xP

xPxP

y

xP

yxI1

log1

loglog;

y

xIxIyxI ;

x

yIyIyxI ;


Page 15 of 83

(1.23)

deci:

(1.24)

unde :

(1.25)

reprezinta cantitatea de informatie proprie a unui eveniment (x;y) din produsul cartezian de

evenimente xy.

Tinand seama ca:

(1.26)

rezulta ca, cantitatea de informatie proprie a unui eveniment (x,y) se poate scrie sub forma:

(1.27)

Luand mediile expresiilor din relatiile anterioare se obtine:

(1.28)

Prima relatie din sistemul de mai sus permite interpretarea lui I(X;Y). Deoarece H(X)

este nedeterminarea lui X,iar H(X/Y) este nedeterminarea lui X dupa receptionarea lui Y, rezulta

ca diferenta H(X) - H(X/Y) arata cu cat s-a micsorat nedeterminarea lui X prin observarea lui y,

adica ce cantitate de informatie se transmite despre X prin observarea lui Y. Iata motivul pentru

care cantitatea de informatie medie I(X;Y) este numita si informatia transmisa sau pe scurt

transinformatia.

yxPyPxPxPyP

yxP

xPyP

y

xPyP

xP

y

xP

yxI,

1log

1log

1log

,logloglog;

yxIyIxIyxI ,;

yxP

yxI,

1log,

y

xPyP

x

yPxPyxP ,

y

xIyIyxI

x

yIxIyxI

,

,

y

xHyHyxH

x

yHxHyxH

yxHyHxHyxI

x

yHyHyxI

y

xHxHyxI

,

,

,;

;

;


Page 16 of 83

Din formula entropiei, data de catre C. Shannon in anul 1948 in lucrarea sa, rezulta ca

entropia U(X) a multimii X depinde numai de probabilitatile de aparitie a elementelor xX. Evident daca multimile X si Y au aceeasi repartitie de probabilitati atunci H(X)=H(y),insa

invers,din egalitatea entropiilor nu rezulta identitatea repartitiilor.

Proprietatea 1. H(X)>0

In adevar,suma H(X) contine termeni de forma P(x)log(1/P(x)),care sunt mai mari sau

egali cu zero pentru 0


Page 17 of 83

(1.32)

Proprietetea 3.

Pentru doua multimi de semnale X si Y ,avem:

(1.33)

in care avem egalitate daca si numai daca X si Y sunt statistic independente.

Exerciii rezolvate.

Conceptia Shannon pleaca de la premiza ca orice informatie cu privire la un eveniment

este utilizata in scopul reducerii gradului de incertitudine asupra realizarii acelui eveniment. Din

punctul de vedere al destinatarului, comunicatia este o variabila aleatoare, continutul

informational fiind cu atat mai mare cu cat el se asteapta mai putin la realizarea acelui

eveniment.

Fie o sursa discreta care emite unul dintre cele q mesaje m m mq1 2, , , cu probabilitatile

de aparitie p p pq1 2, , , . Este evident ca probabilitatile satisfac relatia p p pq1 2 1 .

Continutul informational al mesajului k este notat cu I mk( ) . Pentru ca acest continut sa fie o

masura adecvata a cantitatii de informatie este necesara satisfacerea urmatoarelor proprietati :

(i) daca p p I m I mk j k j ( ) ( )

(ii) daca p I mk k 1 0( )

(iii) daca 0 1 0 p I mk k( )

(iv) (aditivitatea) daca mk si mj sunt mesaje independente

I m m I m I mk j k j( ) ( ) ( )si

O functie continua de variabila pk care satisface proprietatile (i)-(iv) este functia

logaritmica.

I mp

pkk

k( ) log log 1

Daca baza logaritmului este 2, unitatile de masura sunt biti (informationali).

Pentru cazul simplu al unei transmiteri seriale asincrone

kkk

xxx

Xk

1...

11

...21

yHxHyxH ,


Page 18 of 83

se definesc

(a) rata de biti=(durata unui bit)-1

=1/T2 exprimata in biti/secunda (abreviat bps).

(b) rata de bauds=(durata minima intre doua modificari ale semnalului) =1/T1 exprimata

in bauds.

Problema 1

Se considera o trasmisie fax : 2,25106 pixeli cu 12 tonuri de gri, echiprobabile. Care este cantitatea de informatie transmisa ?

Solutie

I=nr.elemente informatie per element=

2 25 10

1

122 25 10 2 3 2 25 10 2 36 2

6

2

2 6

2, log , log , log biti

Problema 2

Un display monocolor cu 24 linii

80 caractere/linie

128 puncte/caracter

3 tonuri de gri/punct

(a) Care este cantitatea de informatie pe pixel, caracter, ecran ?

(b) Care este debitul de informatie stiind ca frecventa cadrelor este de 24 cadre/secunda ?

Solutie

(a) I 24 80 128 32log [ ]biti

(b) 1

f c

RI

I fc

[ ]bps

Problema 3

Un echipament de teletransmisie genereaza cuvinte constituite dintr-un grup de 4

impulsuri de tensiune care pot avea nivelurile 0,1,2 sau 3 volti (echiprobabile) urmate de un

impuls de pauza de nivel -1 volt. Durata tuturor impusurilor este de 1 ms.

(a) Care este debitul de informatie ?

T2

E

M


Page 19 of 83

(b) Care este rata de bauds ?

Solutie

(a) RI

4 4

5 101 62

3

log, [ ]kbps

(b) rbauds baud] kbaud] 1

1010 1

3

3 [ [

Problema 4

Fie 12 monede dintre care una este falsa (mai usoara sau mai grea decat celelalte). Se

cere sa se deterrmine numarul minim de cantariri necesar depistarii monedei false si precizarii

daca ea este mai usoara sau mai grea. Se foloseste pentru cantariri o balanta fara mase marcate.

Solutie

cantitatea de informatie necesara determinarii monedei false este I1 2 21

1

12

12 log log

cantitatea de informatie necesara pentru a decide daca moneda este mai grea sau mai usoara

este I2 2 21

1

2

2 log log

cantitatea de informatie totala necesara a fi determinata I I I 1 2 2 24log

cantitatea de informatie furnizata de o cantarire (exista 3 stari ale balantei)

I3 2 21

1

3

3 log log numarul minim de cantariri I kI kk 3 24 3 3 .

sa se propuna un algoritm de depistare.

Problema 5

Sa se reia problema # 3 daca probabilitatile de aparitie a nivelurilor sunt

nivel 0: 1/2

nivel 1:1/4

nivel 2:1/8

nivel 3:1/8

Solutie

R r H

1

5 10

1

2

1

2

1

4

1

42

1

8

1

83log log log

Se reaminteste ca entropia unei surse reprezinta numarul mediu de biti/simbol si ca

entropia este maxima pentru o sursa care genereaza simboluri echiprobabile H nmax log 2 .


Page 20 of 83

TESTE DE AUTOEVALUARE I TEME DE CONTROL

Testul nr. 1

Fie un alfabet format din literele A,B,C. Se cere s se calculeze: a. numrul maxim de mesaje de lungime 3 ce se pot forma cu acest alfabet; b. cantitatea de informaie coninut de un asemenea mesaj.

Testul nr. 2

S se calculeze cantitatea de informaii necesar pentru precizarea poziiei unei figuri pe tabla de ah.

Tem de control

Matricea probabilitilor reunite intrare-ieire asociat unui canal de transmisie este de forma:

4/14/1

4/14/1XYP

Se cere s se calculeze: a. entropia cmpului de la intrare; b. entropia cmpului de la ieire; c. entropia cmpurilor reunite; d. eroarea medie i echivocaia; e. transinformaia i capacitatea canalului.

BIBLIOGRAFIE RECOMANDAT LA MODULUL 1:

[1] A. Sptaru: Teoria Transmisiunii Informaiei, Ed. Didactic i Pedagogic, Bucureti,

1983. [2] A. T. Murgan, I. Spnu, I. Gavt, I. Sztojanov, V. E. Neagoe, A. Vlad: Teoria

Transmisiunii Informaiei - probleme, Ed. Didactic i Pedagogic, Bucureti, 1983

[3] I. Angheloiu, Teoria codurilor, Ed. Militar, Bucureti, 1972. [4] J.C. Moreira, P.G. Farrell, ESSENTIALS OF ERROR-CONTROL CODING, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England,2006.


Page 21 of 83

MODULUL 2 CODAREA SURSELOR INFORMAIONALE.

CANALE DE TRANSMITERE A INFORMAIEI.

Compresia datelor este un proces prin care se urmrete micorarea redundanei mesajului generat de o surs, pentru a reduce resursele necesare memorrii sau transmiterii acestui mesaj. Deoarece, de regul, pentru memorarea sau transmiterea unui mesaj se folosete, eventual ntr-o form intermediar, reprezentarea prin simboluri binare a acestuia, i pentru c cele mai multe metode de compresie folosesc metode de codare binar - binar, putem spune c obiectivul compresiei const n reducerea numrului de simboluri binare necesar pentru reprezentarea mesajului.

Dup cum irul simbolurilor emise de surs este mprit, pentru codare, n subiruri de aceeai lungime sau de lungime variabil, i dup lungimea, constant sau variabil, a cuvintelor de cod, codurile de compresie se clasific n bloc- bloc, bloc variabil, variabil bloc i variabil variabil, bloc bloc indicnd aceeai lungime pentru subirurile sursei i cuvinte de cod de lungime fix, iar variabil variabil corespunznd unor lungimi variabile ale subirurilor i ale cuvintelor de cod. Din punct de vedere al msurii n care mesajul refcut prin decompresie se aseamn cu cel original, asupra cruia s-a acionat prin procesul de compresie, distingem dou categorii de algoritmi de compresie: fr pierderi i cu pierderi.

Algoritmii de compresie cu pierderi au ca rezultat diferene relativ mici ntre mesajul rezultat prin decompresie i cel original i sunt utilizai n compresia imaginilor i a mesajelor video i audio.

n acest modul vor fi prezentate aspecte privind codificarea surselor discrete i vor fi analizai algoritmii Huffman i Shannon-Fano.

De asemenea, va fi studiat problematica, din punct de vedere matematic, canalelor de transmitere a informaiilor.

Acest modul conine dou uniti de nvare i anume: 1. UNITATEA DE NVARE 3 - CODAREA SURSELOR INFORMAIONALE; 2. UNITATEA DE NVARE 4 - CANALE DE TRANSMITERE A

INFORMAIEI Obiective urmrite:

La sfritul parcurgerii acestor uniti de nvare, studenii: vor nelege noiunile fundamentale cu care opereaz Teoria informaiei i care se

refer la: surse discret de informaie fr memorie, Codarea uniform, metodele de codare Shannon Fano i Huffman,etc.

vor ti s interpreteze i s opereze cu instrumente matematice care se refer la: coderul canalului, probabilitatea decodrii eronate la recepie, capacitatea de transmisie a canalului, calculul capacitii canalelor discrete i continue, etc.

vor ti s implementeze ntr-un limbaj de programare sau simulare algoritmii studiai i modele de canale de transmitere a informaiilor.

Timpul mediu necesar nsuirii noiunilor teoretice, formrii deprinderilor de calcul i utilizrii metodelor de rezolvare a problemelor specifice teoriei informaiei este estimat la aproximativ 4-5 ore pentru fiecare unitate de nvare, ntr-un ritm de 2-3 ore pe zi.


Page 22 of 83


CODAREA SURSELOR INFORMAIONALE

1.1 Codificarea surselor discrete.

In general,trecerea de la un sistem de semnale primare la un sistem de semnale secundare

se numeste codificare. Cerinta principala care se pune pentru orice codificare practic utilizabila

este ca codificarea sa fie efectuata in asa fel ca revenirea de la sistemul de semnale secundare la

cele initiale, adica decodificarea sa fie unica.

Pentru a prezenta problematicile legate de codificarea semnalelor prinare cu ajutorul

semnalelor secundare este necesar sa se precizeze forma concreta a semnalelor primare si

secundare. Se considera ca semnalele prinare sunt semnale generate de catre o sursa discreta si

fara memorie, adica semnalele apar sub o forma discreta si probabilitatea de aparitie a unui

simbol nu depinde de celelalte sinboluri anterioare.

Alfabetul sursei discrete se noteaza cu ,deci sursa produce

succesiuni de litere formate cu ajutorul literelor din alfabetul sursei, deci

pentru i=1,2,. Faptul ca sursa este fara memorie se exprima prin interdependenta statistica a

semnalelor,adica probabilitatea unei succesiuni date de n litere de sursa este

egala cu produsul probabilitatilor literelor de sursa ,deci:

(2.1)

1.2 Codificarea neuniforma.

Presupunem ca alfabetul unei surse discrete si fara memorie contine M semnale primare

sau litere notate cu care apar cu probabilitatile . Fiecare

litera a sursei trebuie sa fie codificata printr-o combinatie de semnale secundare luate din

alfabetul codului care contine D semnale .Aceste combinatii se numesc si

cuvinte de cod;cuvintele de cod care corespund semnalelor primare se noteaza cu

,iar totalitatea lor formeaza un cod, .Numarul semnalelor secundare

din cuvantul de cod care,dupa cum s-a vazut,corespunde lui ,se noteaza cu .

LaaaA ....,, 21

nuuu ,....,, 21

Aui

nn ,...,, 21

n

i

in PP1

21 ,....,,

Maaa ,....,, 21 MaPaPaP ,..,, 21

DxxxX ,..,, 21

Maaa ,..,, 21

Mccc ,..,, 21 McccC ,..,, 21

kc ka kn


Page 23 of 83

Dintre toate, codurile unic decodabile prezinta un interes ,din punct de vedere

economic,acel cod care conduce la un -numarul mediu de litere de cod pe litere de sursa-cat

mai mic posibil,unde se mai numeste si lungimea mediea combinatiilor de cod:

(2.2)

Codul in care doua semnale primare distincte sunt codificate printr-o singura combinatie

de cod se numeste cod singular si in mod corespunzator codul in care toate combinatiile de cod

atribuite semnalelor primare sunt distincte se numeste cod nesingular.

Codul se numeste unic decodabile daca succesiunile cuvintelor de

cod,corespunzatoare diferitelor succesiuni de lungime finite a sursei,sunt distincte.

Fie un cuvant de cod .Sirul de litere ,unde se

numeste prefixul lui .

Cu ajutorul notiunii de prefix putem defini subclasa codurilor unic decodabile care

prezinta un interes deosebit din punct de vedere practice.

Codul in care nici un cuvant de cod nu este prefixul unui alt cuvant de cod se numeste

cod cu proprietate de prefix.Din aceasta definitie rezulta ca in cazul unui cod cu proprietate de

prefix,dintr-un cuvant de cod mai lung nu se poate obtine un cuvant de cod mai scurt prin

reducerea (suprimarea) ultinelor simboluri,motiv pentru care codurile cu proprietate de prefix se

numesc si coduri ireductibile.

Codurile cu proprietatea de prefix se mai numesc uneori si coduri instantanee, deoarece o

combinatie de cod se poate recunoaste fara nici o referinta la urmatoarea combinatie de cod. La

decodificarea unei succesiuni de cuvinte de cod dintr-un cod cu proprietatea de prefix se

inainteaza in succesiunea semnnlelor pana la identificarea primului cuvant de cod si apoi lasand

la o parte succesiunea identificata se trece la identificarea urmatoarei succesiuni si a.m.d.

Momentul cand se obtine o succesiune cu sens, arata si sfarsitul unui cuvant de cod, dat fiind

faptul ca nici un cuvant de cod nu este prefixul unui alt cuvant de cod.Relatia care exista intre

codurile cu proprietate de prefix si codurile unic decodabile se pune in evidenta prin urmatoarea

teorema:orice cod cu conditia de prefix este un cod unic decodabil.

Codurile cu proprietate de prefix permit o reprezentare geometrica foarte intuitiva si

convenabila,cu ajutorul unui graf arborescent.Fiecarui cuvant de cod ii corespunde un drum

simplu,sau nodul final de la extremitatea drumului simplu corespunzator

Este important ca in cazul unui cod cu conditia de prefix exista o corespondenta

biunivoca intre cuvintele de cod si intre nodurile finale, deci fiecarui cuvant de cod ii

corespunde un nod final si nu un nod internediar si invers, fiecarui nod final ii corespunde o

combinatie de cod.

De asenenea si codurile care nu au proprietatea de prefix pot sa fie reprezentate grafic cu

ajutorul unui graf arborescent, dar in acest caz cel putin unui cuvant de cod ii corespunde un nod

internediar.

Se observa ca in cazul unui cod D-nar,constructia grafului arborescent corespunzator este

asemanatoare, tinand cont ca din fiecare nod pomesc D arce.

n

n

kM

K

k naPn

1

kcccC ,..,, 21

imiii xxxc ,...,, 21 imii xxx ,...,, 21 mk

ic


Page 24 of 83

1.3. Codarea si decodarea pe canale fara perturbatii.

In cadrul modulului 1 s-a aratat ca un sistem digital de comunicatie presupune un

codor/decodor al sursei. Rolul acestuia este de a mari eficienta transmiterii prin utilizarea unor

mesaje ct mai scurte pentru a transmite aceiasi cantitate de informatie. Aceast operatie numita

generic compresie de date

Definirea unui cod. Fie o sursa discreta fara memorie avnd alfabetul

S s s sN 1 2, ,......, (2.3)

cu probabilitatea de aparitie p s pi i

P p p pN 1 2, ,......, (2.4)

Fie alfabetul canalului

X x x xq 1 2, ,......, (2.5)

constituit dintr-un numar finit de semne (litere, caractere)

Se considera reuniunea secventelor finite de litere din alfabetul canalului:

X X n

n

*

(2.6)

Orice aplicatie S X * se numeste codarea alfabetului S prin alfabetul X

Un element s Xi* * si care corespunde lui si este un cuvnt de cod. Lungimea

cuvntului de cod, notat n s ni i* este numarul de litere cale Il formeaza. Totalitatea cuvintelor de cod constitue codul lui S cu mentiunea ca X

* poate contine si combinatii care nu

apartin codului, numite cuvinte fara sens.

Astfel, un text constituit din secvente de mesaje:

m s s sj i i ik 1 2, ,......, (2.7)

este codat prin secventele de cuvinte de cod (cu sens)

m s s sj i i ik 1 2* * *, ,......, (2.8)


Page 25 of 83

Decodarea implica posibilitatea de a repara cuvintele de cod n mod unic (aplicatia

S X * sa fie injectiva). Un cod cu aceasta probabilitate se numeste regulat (nesingular). Regularitatea este o conditie necesara dar nu suficienta pentru decodare. fie de exemplu

s s1 2 10* *, si s3 01 . Codul 010 poate fi interpretat fie s s1 2

* *, fie s s3 1* *, .

Pentru a distinge fara ambiguitati un text trebuie ca fiecarui succesiune de cuvinte sa-i

corespunda o succesiune unica de litere, adica aplicatia S Xk

k

n

*

1

sa fie si ea injectiva. Un cod de acest tip este un cod unic decodabil. Conditii suficiente care sa asigure aceasta

proprietate sunt:

(a) utilizarea cuvintelor de cod de aceiasi lungime (bloc)

(b) utilizarea unui semn distinct Intre cuvintel (separator)

Exista nsa si coduri care nu necesita utilizarea unui mijloc suplimentar pentru a asigura

proprietate de unic decodabil. Aceste coduri se numesc separabile.

Alcatuirea unui cod. Teorema Kraft

Conditia necesara si suficienta pentru existenta unui cod ireductibil de N cuvinte de

lungime n n nN1 2, ,......, este ca

qni

i

N

11

(2.9)

Observatii

1. Se reaminteste ca q card X este numarul de litere din alfabetul canalului. 2. Daca numarul cuvintelor de lungime k este rk atunci conditia (1.9) devine

r qkk

k

n

11

(2.10)

cu N rkk

n

1

Teorema Mac Millan

Un cod este ireductibil daca si numai daca

n n nN1 2 ...... (2.11)


Page 26 of 83

Criterii de apreciere a unui cod.

Transmiterea mesajelor presupune un cost care creste linear cu timpul. Un criteriu

convenabil de apreciere a unui cod este lungimea medie a unui cuvnt

n p ni ii

n

1

(2.12)

unde pi sunt definite prin (1.4) si ni este numarul de litere din cuvntul de cod cu indicele i.

Este evident ca se cauta ca n sa fie ct mai mic dar trebuie avut In vedere ca el este limitat inferior de entropia informationala pe simbol a alfabetului de cod

nH

q

log2 (2.13)

unde H este entropia sursei. In aceste conditii, eficienta unui cod este

H

n qlog 21 (2.14)

iar redundanta codului este

1 (2.15)

Codurile cu o eficienta egala cu unitatea si deci care au lungimea medie minima se

numesc coduri absolut optimale

Prima teorema a lui Shannon. Pentru orice sursa omogena exista un cod ireductibil

pentru care lungimea medie a cuvintelor este orct de apropiata de marginea sa inferioara.

Aceasta teorema se mai numeste si teorema codarii pe canale neperturbate. Prima

teorema a lui Shannon se refera la problema codarii cu o lungime medie posibila ct mai mica,

pe un canal neperturbat de capacitate data.

Codurile care asigura cea mai mica lungime medie posibila se numesc cvasioptimale sau

compacte.

1.4. Coduri Huffman de dispersie minim.

Acest procedeu se bazeaz pe ideea de a partiiona mulimea mesajelor sursei S = {s1, s2

,..., sN} n submulimile 0 i 1 , astfel nct suma probabilitilor mesajelor incluse n 0 s fie

ct mai apropiat de suma probabilitilor mesajelor incluse n 1.


Page 27 of 83

La rndul lor, submulimile 0 i 1 pot fi partiionate n submulimile 00 i 01 ,

respectiv 10 i 11 astfel nct suma probabilitilor mesajelor incluse n cele patru submulimi

s fie ct mai apropiate posibil. Procedeul se continu n mod similar pn cnd se obin

submulimi ce conin un singur mesaj.

n felul acesta, pentru orice distribuie a sursei S ce urmeaz a fi codat se va obine un

cod compact, adic lungimi medii ale cuvintelor de cod ce nu mai pot fi micorate prin nici un alt

procedeu de codare.

Pentru ca partiiile s satisfac condiiile menionate, se procedeaz

astfel:

1). Se ordoneaz mulimea mesajelor sursei S n ordinea descresctoare a probabilitilor,

obinndu-se astfel mulimea ordonat 0={1, 2, , }, cu p(1) p(2) ... p(), cu

schimbarea eventual a indicilor mesajelor pentru realizarea ordonrii respective;

2). Se reunesc ultimele dou mesaje (de probabilitile cele mai mici) ntr-un nou mesaj,

notat cu 1, cruia i se aloc o probabilitate egal cu suma probabilitilor mesajelor componente.

Se ordoneaz din nou mesajele n ordinea descresctoare a probabilitilor, formndu-se astfel

prima surs restrns 1={1, 2, , 1, } cu p(1) p(2) ... p(1) ... . 3). Se reunesc

ultimele dou mesaje din sursa restrns 1 ntr-un nou mesaj 2, de probabilitate egal cu suma

probabilitilor mesajelor componente. Se ordoneaz mesajele n ordine descresctoare,

formndu-se astfel sursa restrns 2. n mod analog, din 2 se formeaz sursa restrns 3 i

aa mai departe, pn cnd se obine o surs restrns format numai din dou mesaje, =

{ , 1}, cu p( ) (1). De fapt, va fi 0 i 1 va fi 1 sau invers.

Din modul de formare a surselor restrnse , rezult c mulimea S a mesajelor poate fi

partiionat n dou submulimi i 1 astfel nct probabilitile p( ) i (1) sunt cele

mai apropiate posibil. La rndul lor, submulimile i 1 , pot fi partiionate n alte dou

submulimi, de probabilitile cele mai apropiate posibil. Partiionrile se continu pn se obin

submulimi care conin un singur mesaj.

4). Cuvintele de cod corespunztoare fiecrui mesaj se obin astfel:

- submulimii i se aloc simbolul "0" (sau "1");

- submulimii 1 , i se aloc simbolul "1" (sau "0");


Page 28 of 83

- la fiecare partiionare se aloc arbitrar celor dou submulimi "0" sau "1", operaia continundu-

se pn se obin submulimi ce conin un singur mesaj , k={1}.

Deoarece alocarea lui "0" i "1" este arbitrar la fiecare partiionare, rezult c unei surse

S i se pot ataa o multitudine de coduri instantanee, toate, ns, avnd aceeai lungime medie a

cuvintelor de cod, care nu mai poate fi micorat prin nici un alt procedeu de codare a mesajelor

luate individual.

Dac sursa primar S poate furniza N mesaje, atunci submulimea restrns 1 , va avea

N-1 mesaje, submulimea restrns 2 va conine N-2 mesaje i aa mai departe, ultima

submulime restrns va conine N n mesaje, care sunt i 1 , adic se poate scrie:

N-n=2 => n=N-2 (2.16)

Dac submulimii i se aloc simbolul "0" i submulimii 1 simbolul "1", celor N-2

partiionri putndu-li-se aloca arbitrar "0" sau "1", rezult un total de 22 posibiliti de

codare. Dac, ns, submulimii i se aloc simbolul "1", iar submulimii 1 simbolul "0",

mai rezult 22 posibiliti de codare. Rezult, deci, c prin acest procedeu de codare se pot

realiza 22 + 22 = 21 coduri instantanee, toate avnd toate aceeai lungime medie a

cuvintelor de cod.

Prin definiie, se numete cod compact, codul care realizeaz lungimea medie minim a

cuvintelor de cod. Deoarece prin procedeul de codare Huffman se obine cea mai mic lungime

medie a cuvintelor de cod, nseamn c prin acest procedeu se obin coduri instantanee

compacte. Evident, un cod absolut optimal este i compact, reciproca nefiind totdeauna valabil.

Exemplul 3.1.

Se presupune sursa discret de informaie caracterizat de distribuia:

S : 1 2 3

0,1 0,2 0,3 4 5 6

0,15 0,05 0,2

Codarea binar Huffman a acestei surse se poate realiza astfel:


Page 29 of 83

Fig. 3.2. Schema de codare pentru exemplul 3.1

Graful i cuvintele de cod corespunztoare codrii efectuate sunt date n Fig. 3.3.

Fig.3.3. Graful corespunztor codului

Codurile Huffman de dispersie minim se obin cnd la reordonarea sursei restrnse,

simbolul compus se plaseaz pe poziia cea mai de sus posibil n sursa restrns. n felul acesta

cuvntul de cod atribuit simbolului compus va avea cea mai mic lungime posibil. Cum acest

cuvnt va deveni prefix pentru simbolurile constituente, cuvintele de cod corespunztoare

acestora vor avea o lungime cu o unitate mai mare dect lungimea prefixului, deci i acestea vor

rezulta de lungime minim. Ca urmare, diferenele dintre lungimile cuvintelor de cod devin

minime, ceea ce va conduce, evident, i la o dispersie minim.


Page 30 of 83

Pentru fixarea ideilor, se presupune sursa discret de informaie caracterizat de

distribuia:

S : 1 2 3

0,2 0,4 0,2 4 50,1 0,1

Pentru aceast surs se efectueaz codarea Huffman, plasnd nti mesajele sursei

restrnse pe poziiile cele mai jos posibile n list i apoi pe poziiile cele mai de sus posibile. n

primul caz rezult schema de codare din Fig. 3.4, iar graful i cuvintele de cod ca n Fig. 3.5.


Page 31 of 83

Pentru acest cod, lungimea medie i dispersia sunt:

= 0,2 2 + 0,4 1 + 0,2 3 + 0,1 3 + 0,1 4 2,2 /

12 = ( )

2 = 0,22 + 1,22 + 0,82 + 1,82 +

5

=1

1,82 = 8,6

Pentru cazul n care n codarea Huffman mesajele sursei restrnse se plaseaz pe poziiile

cele mai de sus n list, se obine schema de codare din Fig. 3.6 i graful i cuvintele de cod ca n

Fig. 3.7.


Page 32 of 83

Pentru acest cod, lungimea medie este, evident, aceeai, n timp ce dispersia devine:

22 = ( )

2 = 0,22 + 0,22 + 0,22 + 0,82 +

5

=1

0,82 = 1,4

Dei din punct de vedere informaional, cele dou coduri sunt identice, n practic se

prefer folosirea celor de dispersie minim, din motive de transmisie. De exemplu, dac se

dorete s se transmit mesaje ale sursei cu o vitez de 10.000 mesaje/sec., este necesar un canal

cu capacitatea de 22.000 bii/sec. Deoarece viteza de generare a biilor oscileaz n jurul valorii

de 22.000 bii/sec., funcie de succesiunea de mesaje furnizate la un moment dat, ieirea sursei

este ncrcat ntr-un buffer.

Dac, de exemplu, sursa genereaz la un moment dat iruri de mesaje 4 i 5 mai multe

secunde, pentru primul cod se genereaz 40.000 bii/sec. i n fiecare secund ar trebui un buffer

de capacitate de 18.000 bii. Cu al doilea cod se genereaz 30.000 bii /sec. i bufferul ar trebui

s aib capacitatea de 8.000 bii. Dac se transmit iruri de mesaje 2, cu primul cod se

genereaz 10.000 bii/sec. i canalul nu e folosit la capacitatea sa, rmnnd un deficit de 12.000

bii/sec, pe cnd cu al doilea cod se genereaz 20.000bii/sec, deficitul existent n exploatarea

canalului fiind numai de 2.000 bii/sec. Aadar, din motive de transmisie este mai rezonabil a se

alege al doilea cod dect primul.

1.5. Procedeul de codare binar Shannon Fano.

Acest procedeu se aplic de obicei n cazurile particulare n care probabilitile de

furnizare ale mesajelor sunt puteri ntregi pozitive ale lui (1/2), adic, de forma:

p() = (1

2)= 2 , ( ) k=1, (2.17)

unde este un numr ntreg pozitiv. Dac relaia (3.48) este satisfcut, mulimea S = {s1, s2

,..., sN} a mesajelor sursei discrete de informaie ce urmeaz a fi codat poate fi partiionat n

dou submulimi 0 i 1, astfel nct suma probabilitilor mesajelor incluse n 0 , notat cu

p(0 ), s fie egal cu suma probabilitilor mesajelor incluse n 1,, notat cu p(1 ). Sursa S fiind

totdeauna complet, se poate scrie:

p 0 = p 1

p 0 + p 1 = 1 p 0 = p 1 =

1

2= 21 (2.18)


Page 33 of 83

Submulimile 0 i 1 se pot partiiona la rndul lor n 00 i 01 , respectiv n 10 i 11 ,

astfel nct suma probabilitilor mesajelor incluse n cele patru submulimi s fie aceeai, adic

se poate scrie relaia:

p 00 = p 0 1 = p 10 = p 11 =1

2

2= 22 (2.19)

Se procedeaz n mod analog pn se obin submulimi care conin un singur mesaj. Se

observ c fiecare submulime are suma probabilitilor mesajelor incluse egal cu o putere

ntreag a lui (1/2). Puterea ntreag este egal cu numrul indicilor submulimii respective Dac

submulimea conine un singur mesaj, , i are un numr de indici egal cu , atunci se poate

scrie:

= (1/2) = 2 (2.20)

de unde rezult necesitatea ca sursa S ce urmeaz a fi codat s-i furnizeze mesajele cu

probabiliti egale cu la o putere ntreag, pozitiv.

Sursa fiind complet, se poate scrie relaia (1.21):

() = 1=1 (2.21)

nlocuind (1.20) n (1.21), rezult relaia (1.22):

2 = 1=1 (2.22)

ceea ce nseamn c inegalitatea lui Kraft devine n acest caz egalitate.

Cuvintele de cod se vor obine, atunci, astfel:

1. Se atribuie simbolul "0" submulimii 0 i simbolul "1" submulimii 1 , (sau invers),

astfel c toate cuvintele corespunztoare mesajelor incluse n 0 vor ncepe cu "0" i toate

cuvintele corespunztoare mesajelor incluse n 1 , vor

ncepe cu "1" (sau invers);

2. Se aloc submulimilor 00 i 10 ca al doilea mesaj "0", iar submulimilor 01 i 11 ca

al doilea mesaj "1" (sau invers). n felul acesta, cuvintele de cod corespunztoare mesajelor

incluse n 00 vor ncepe cu 00, cuvintele de cod corespunztoare mesajelor incluse n 10 vor

ncepe cu 10 i aa mai departe, cuvintele de cod corespunztoare mesajelor induse n 11 vor

ncepe cu 11.


Page 34 of 83

3. Operaia se continu n acelai mod, pn cnd n fiecare submulime rmne un singur

mesaj, cruia i va corespunde cuvntul de cod format din irul de indici ai submulimii

respective. Deoarece la fiecare partiionare n dou submulimi atribuirea mesajelor "0" i "1"

este arbitrar, rezult c prin acest procedeu se pot obine o multitudine de coduri instantanee,

dar toate absolut optimale.

n principiu, procedeul de codare descris s-ar putea aplica n general, adic i atunci cnd

relaia (1.21) nu este satisfcut. n acest caz, partiionrile n submulimi trebuie efectuate astfel

nct suma probabilitilor mesajelor incluse n submulimile respective s fie ct mai apropiate.

Atribuind simbolurile "0" i "1" ca n procedeul descris, se obin totdeauna coduri instantanee.

Cu ct sumele probabilitilor mesajelor componente ale submulimilor respective vor fi

mai apropiate, cu att lungimea medie a cuvintelor de cod va fi mai mic.

Exemplul 3.2.

Se consider sursa discret de informaie caracterizat de distribuia:

S : 1 2 3

22 22 23 4 5

23 24 6 7 8

24 24 24

Procedeul de codare binar Shannon - Fano este sintetizat n tabelul de mai jos:

Graful arborescent ataat codului astfel obinut este reprezentat n Fig. 3.8


Page 35 of 83

Aplicaie

Simularea cu ajutorul programului MATLAB a algoritmului de compresie

Shannon-Fano n cadrul lucrrilor de laborator va fi pus la dispoziie o aplicaie software care

implemeneaz algoritmul de compresie Shannon-Fano. Ecranul aplicaiei este prezentat n figura urmtoare.


Page 36 of 83

Exerciii rezolvate.

1. n tabelul de mai jos sunt prezentate patru coduri separabile,

mesaj A B C D

s0 00 0 0 0

s1 01 10 01 10

s2 10 110 011 110

s3 11 1110 0111 111

Folosind codul B, succesiunile s s s s3 1 0 2 se codifica 1110100110. Dupa receptinarea

primelor sase biti se poate determina ca s-a receptionat s s3 1 . Daca Insa se folosec codul C,

succesiunea s s s s3 1 0 2 se codifica 011010011. Dupa receptionarea primelor sase biti conduce la

decodarea s3 dar secventa 01 poate fi interpretata la acel moment fie care s1 fie ca, s2 fie ca s3 ,

ambiguitatea rezolvndu-se abia dupa receptia urmatorilor biti. Un cod de tip C se numeste cod

instantaneu.

Conditia necesara si suficienta ca un cod sa fie instantaneu este ca nici un cuvnt de cod

sa nu fie prefix al altui cuvnt de cod (conditia de prefix).

Se considera sursa care genereaza simbolurile :

- s0 cu probabilitatea p1 = 0,5 - s1 cu probabilitatea p2 = 0,25 - s2 cu probabilitatea p3 = 0,125 - s3 cu probabilitatea p4 = 0,125

Se cere sa se determine eficienta codurilor A, B, C si D

Rezolvare :

Entropia sursei este

H p pi ii

log log log log21

4

2 2

1

2

1

2

1

4

1

42

1

8

1

8

7

4biti

Pentru codul A lungimea medie a codului este nA 2 si

A iar

7

4

2 2

7

8

1

22log

Codurile B si C cu aceiasi lungime medie

n nB C 0 5 1 0 25 2 0 125 3 0 125 4 1 875, , , , ,


Page 37 of 83

B C

B C

1 75

1 875

14

15

1

15

,

,

Codul D are nD 0 5 1 0 25 2 0125 3 1 75, , , , si

D D 1 75

1 75 21 0

2

,

, log

TESTE DE AUTOEVALUARE

Testul nr. 1

1. Se d sursa A prin urmatoarea repartiie de probabiliti:

02.002.002.004.007.007.014.014.048.0

987654321 aaaaaaaaaA

S se codifice sursa A utiliznd metoda de codificare Huffman i s se calculeze lungimea medie a cuvintelor de cod.

Testul nr. 2

2. Se d sursa A prin urmatoarea repartiie de probabiliti:

02.002.002.004.007.007.014.014.048.0

987654321 aaaaaaaaaA

S se codifice sursa A utiliznd metoda de codificare Shannon-Fano i s se calculeze lungimea medie a cuvintelor de cod.

Tem de control

Se consider o surs cu alfabetul 654321 ,,,,, ssssssS i probabilitile 2.0,1.0,25.0,3.0,1.0,05.0P :

a. s se determine un cod compact folosind algoritmul de codare Huffman, dac

alfabetul codului este 1,0X i dac alfabetul codului este 2,1,0X ; b. pentru cele dou cazuri s se calculeze lungimea medie a cuvintelor de cod i

eficiena codului.


Page 38 of 83


CANALE DE TRANSMITERE A INFORMAIEI

Definitie : Un canal de transmitere a informatiei este constituit din mediul de

transmitere si echipamentele care fac posibile transmiterea informatiei de la sursa la utilizator.

Mediul de transmisie : fire de cupru, fibrele optice, atmosfera, etc.

2.1.Clasificari ale canalelor

a) Dupa domeniul de valori al v.a. X si Y de la intrarea, respectiv iesirea canalului :

- continuu/continuu

- discret/continuu

- continuu/discret

- discret/discret

b) Dupa evolutia in timp a v.a. X si Y :

- continuu in timp - discret in timp

c) Dupa redundanta transmisiei :

- canal fara memorie - canal cu memorie

d) Dupa statistica trasmisiei :

- stationar - nestationar

2.1.Canale discrete de transmitere a informatiei

Aceasta sectiune priveste canalele discrete/discrete, fara memorie si stationare. Notiunile

prezentate nu depind de tipul de continuitatea in timp.

S R C A N A L S D

[X] [Y]

P

Mod DeM


Page 39 of 83

2.3.1. Marimi caracteristice

Fie X , sursa de informatie care genereaza la intrarea in canal:

NxxX ,,1 (2.29)

NppP ,,1 (2.30)

si Y , sursa de informatie care modeleaza iesirea din canal (sursa de informatie pentru utilizator):

MyyY ,,1 (2.31) MqqQ ,,1 (2.32)

Din cauza perturbatiilor de pe canal, X si Y sunt, in general, diferite.

Spatiul produs:

MNNN

M

M

yxyxyx

yxyxyx

yxyxyx

YX

,,,

,,,

,,,

,

21

22212

12111

(2.33)

Matricea probabilitatilor corespunzatoare spatiului produs:

MNNN

M

M

yxpyxpyxp

yxpyxpyxp

yxpyxpyxp

YXP

,,,

,,,

,,,

,

21

22212

12111

(2.34)

Matricea de zgomot a canalului:

NMNN

M

M

xypxypxyp

xypxypxyp

xypxypxyp

XYP

21

22221

11211

(2.35)

Matricea de zgomot este stohastica:

1i

ji xyp (suma elementelor de pe orice linie este 1).


Page 40 of 83

Canalele studiate sunt stationare, deci ./ ctxyp ij . Canalele sunt fara memorie, deci probabilitatea de aparitie a lui jy nu depinde decat de simbolul

generat simultan la intrarea in canal, simbolul ix pentru ij xyp / .

2.3.2. Reprezentarea grafica a transmisiei prin canalele discrete

1x 1y

2x 2y

.

My

Nx

5.2.3. Entropii caracteristice

Entropia la intrarea in canal: ii

i xpxpXH log

Entropia la iesirea din canal: ii

i ypypXH log

Entropia reunita a intrarii si iesirii: jii j

ji yxpyxpYXH ,log,,

Echivocatia: i

ji

j

ji yxpyxpYXH log,

Definitie: Echivocatia este cantitatea medie de incertitudinea care ramane asupra simbolurilor de

la intrarea in canal, atunci cand se cunosc simbolurile de la iesire.

Eroarea medie: i

ij

j

ji xypyxpXYH log,

Definitie: Eroarea medie este cantitate medie de informatie eronata, la iesirea din canal.

Informatia medie transmisa prin canal: ji

ji

i j

jiypxp

yxpyxpYXI

,log,,

Definitie: Informatia medie este cantitatea medie de informatie care se transmite corect prin

canal.

Cazuri particulare :

a) Canale cu perturbatii infinite ( X si Y sunt independente)

11 / xyp


Page 41 of 83

YHXHYXH , (2.36)

XHYXH (la iesire, nu aflam nimic despre X ; incertitudinea asupra lui X ramane la fel de mare)

YHXYH (toata informatia de la iesire este eronata)

0, YXI (informatia medie transmisa prin canal este nula)

b) Canale fara perturbatii (sursele X si Y sunt identice)

YHXHYXH , (2.37)

0YXH (cunoscand iesirea din canal, nu mai exista nicio incertitudine asupra lui X )

0XYH (nu exista erori la iesirea din canal)

)(, XHYXI (informatia de la intrare se transmite integral prin canal)

c) Canale cu perturbatii finite ( X si Y sunt diferite, dar dependente statistic)

YHXHYXH , (2.38)

XHYXH (cunoscand iesirea din canal, incertitudine asupra lui X devine mai mica)

YHXYH (o parte a informatiei de la iesirea din canal este corecta)

)(, XHYXI (informatia de la intrare se transmite partial prin canal)

5.3. Capacitatea canalului discret

Definitie : Capacitatea unui canal este informatia medie maxima, care se poate transmite prin

canal :

YXICP

,max (2.39)

Observatie: maximul se ia dupa probabilitatile sursei de la intrarea in canal, pentru ca aceste

probabilitati pot fi controlate, intr-o aplicatie practica.


Page 42 of 83

Unitatea de masura pentru capacitate este bit/simbol.

Definitie : Redundanta canalului este : YXICR , [bit/simbol].

Definitie : Redundanta relativa a canalului este : 1,0,1

C

YXIC .

Definitie : Randamentul sau eficienta canalului arata cat de mica este cantitatea medie de

informatie transmisa prin canal, in raport cu capacitatea canalului.

1,0,

C

YXIC

(2.40)

Observatie: redundanta si radamentul sunt marimi complementare: CC 1

Definitie : Debitul de informatie prin canal este :

YXIYXI t

,, [bit/sec], unde este

durata unui simbol.

Observatie: Debitul maxim de informatie prin canal este:

CCt .

Proprietati :

a) Capacitatea canalului este o marime nenegativa :

0C (deoarece 0, YXI ) (2.41)

b) Capacitatea canalului este mai mica sau egala cu entropia sursei de la intrare:

XHC (deoarece XHYXI , ) (2.42)

c) Capacitatea este o functie continua in raport probabilitatile XP .

2.3. Calculul capacitatii canalului discret

Date initiale : probabilitatile matricii de zgomot XYP / . Etape:

1) Aplicand Metoda multiplicatorului lui Lagrage, se calculeaza probabilitatile maxip , care

maximizeaza functia XYHYHYXI /, . 2) Capacitatea se obtine calculand XYHYHYXI /, pentru probabilitatile

obtinute.


Page 43 of 83

Rezolvare:

Se construieste functia:

1/

i

ipXYHYH

Pentru a pune in evidenta probabilitatile ip in expresia lui YH , probabilitatile Q se scriu:

ii

iji

i

ij

i

jij pxypxpxypyxpq ,

Se calculeaza derivatele partiale ale lui in raport cu ip :

- derivata lui YH in raport cu ip :

j

jij

j

jij

j

ij

j j

ijj

i

j

ji

qxype

qxypxype

xype

qp

q

q

YH

p

YH

log/log

1log//

log

1

/log

1log

- derivata lui XYH / in raport cu ip :

j

ijij

i

j i

ijiij

i

xypxypp

xyppxyp

p

XYH/log/

/log//

- derivata termenului in :

i

i

i

p

p 1

Se egaleaza derivatele partiale ale lui cu zero; din rezolvarea sistemului, rezulta

probabilitatile maxip , care maximizeaza si, deci, informatia transmisa prin canal:

0/log/log/log

1

j

ijij

j

jij xypxypqxype

Nipentru ,1

Grupand termenii cu sume si constantele, se obtin ecuatiile:

ctq

xypxyp

j j

ij

ij /

log/ Nipentru ,1


Page 44 of 83

Completand aceste ecuatii cu:

i

iijj pxypq / Mjpentru ,1

si

i

ip 1

se obtine un sistem cu 1MN ecuatii si acelasi numar de necunoscute, din care se pot obtine

probabilitatile maxip si max

jq , care maximizeaza informatia transmisa prin canal.

Capacitatea canalului se calculeaza cu relatia:

i j j

ij

iijq

xyppxypC

max

max/

log/

Observatii:

- acest sistem nu are, in general, o solutie analitica; cand nu exista o solutie analita, capacitatea se calculeaza cu metode numerice (algoritmului Frank-Wolfe, care este bazat

pe metoda gradientului, sau algoritmul iterativ al lui Arimoto si Blahut)

- daca alfabetele surselor de la intrarea si de la iesirea din canal au acelasi numar de simboluri si, daca, determinantul matricii de zgomot este diferit de zero, atunci sistemul

are solutie analitica

2.4. Modele de canale discrete

Aceasta sectiune cuprinde patru cazuri particulare de canale (modele), pentru care

capacitatea se poate calcula analitic.

2.4.1. Canalul uniform fata de intrare

Definitie: Fiecare linie a matricii de zgomot a canalului uniform fata de intrare este o permutare

a altei linii (pe fiecare linie gasim aceleasi probabilitati, diferit ordonate).

Exemplu:

6

1

2

1

3

12

1

6

1

3

1

/ XYP

(2.43)

Proprietati: a) Eroarea medie nu depinde de probabilitatile simbolurilor de la intrarea in canal:


Page 45 of 83

ctxpctxypxypxp

xypxpxyp

xypyxpXYH

i

i

j

ijij

i

i

ij

ji

iij

ij

ji

ji

/log/

/log/

/log,/

,

,

(2.44)

b) Capacitatea canalului este:

XYHYHXYHYHYXIC

PPP/max/max,max

(2.45)

2.4.2. Canalul uniform fata de iesire

Definitie: Fiecare coloana a matricii de zgomot a canalului uniform fata de iesire este o

permutare a altei coloane (pe fiecare coloana gasim aceleasi probabilitati, diferit ordonate).

Exemplu:

3,07,0

7,03,0

5,05,0

/ XYP

(2.46)

Proprietate:

a) Daca simbolurile de la intrarea in canal sunt echiprobabile, atunci si cele de la iesire sunt echiprobabile:

.1/1/ ctN

xypN

xpxypypi

ij

i

iijj (2.47)

2.4.3. Canalul simetric

Definitie: Canalul simetric este canalul uniform atat fata de intrare cat si fata de iesire.

Exemplu:

3,05,02,0

2,03,05,0

5,02,03,0

/ XYP (2.48)

Proprietati: a) Capacitatea canalului se obtine pentru simboluri echiprobabile la intrarea in canal si este:

XYHMC /log unde M este numarul de simboluri ale sursei de la iesirea din canal (simbolurile de la iesire sunt echiprobabile, daca si cele de la intrare sunt echiprobabile).


Page 46 of 83

2.4.4. Canalul slab simetric

Definitie: Canalul slab simetric este uniform fata de intrare si are suma probabilitatilor de pe

fiecare coloana constanta.

Exemplu:

6

1

2

1

3

12

1

6

1

3

1

/ XYP (2.49)

Proprietati:

a) Daca simbolurile de la intrarea in canal sunt echiprobabile, atunci si cele de la iesire sunt echiprobabile:

.1/1/ ctN

xypN

xpxypypi

ij

i

iijj (2.50)

b) Capacitatea canalului se obtine pentru simboluri echiprobabile la intrarea in canal si este:

XYHMC /log (2.51)

Observatie: Uniformitatea fata de iesire nu este indispensabila pentru a putea avea o expresie

analitica pentru capacitatea canalului. Aceasta conditie poate fi relaxata la conditia ca suma

probabilitatilor de pe coloane sa fie constanta.

2.5. Exemple de canale discrete

2.5.1. Canalul binar simetric

Matrice de zgomot:

pp

ppXYP

1

1/

(2.52)

Reprezentare grafica:

0 0

1 1

p 1-p

1-p

p


Page 47 of 83

Calculul capacitatii:

XYHXYHC /1/2log

unde

pppp

xypxypXYHj

ijij

1log1log

/log//2

1

deci

ppppC 1log1log1

Cazuri particulare:

a) Canal fara perturbatii:

Matricea de zgomot:

10

01/ XYP

Reprezentare grafica: 0 0

1 1

Capacitatea este maxima : simbolbitC /1

Observatie:

Celalalt punct de maxim al capacitatii corespunde canalului inversor:

01

10/ XYP 0 0

simbolbitC /1

1 1

b) Canalul cu perturbatii infinite (foarte puternice)

H(X), C

p 1/2 1

1


Page 48 of 83

Matricea de zgomot:

2/12/1

2/12/1/ XYP

Capacitatea : simbolbitC /0

2.5.2. Canalul binar cu erori si anulari

Matrice de zgomot:

qqpp

qpqpXYP

1

1/ Canalul este uniform doar fata de intrare.

Reprezentare grafica:

0X 0Y

aY

1X 1Y

Calculul capacitatii:

XYHYHC

P/max

unde

qpqpqqpp

xypxypXYHj

ijij

1log1loglog

/log//2

1

Calculul lui

YHP

max :

- se noteaza xXp 0 si xXp 11

- se exprima ii

i xpxYpYp

2

1

/00 , aYp si 1Yp ca

functii de x

- se exprima YH ca functie de x , folosind probabilitatile calculate mai sus

1-p-q

q

p


Page 49 of 83

- se rezolva ecuatia

0

x

YH

- cu solutia ecuatiei de mai sus, se obtine

YHP

max

Exercitiu:

Calculul capacitatii canalului binar cu erori si anulari.

Raspuns qpqpppqqqC 1log1log1log11 .

Observatie: Capacitatea canalului devine zero pentru 2

1 qp

(se rezolva ecuatia 0

p

C

si se obtine solutia 2

1 qp

)

2.5.3. Canalul binar cu anulari

Este un caz particular al canalului binar cu erori si anulari ( 0q ).

Matricea de zgomot:

qq

qqXYP

10

01/

(2.53)

Reprezentarea grafica:

0X 0Y

aY

1X 1Y

Capacitatea: qC 1

1-q

1-q

q

q


Page 50 of 83

Exercitii rezolvate.

1. Sa se determine capacitatea unui canal binar cu zona de anulare avand graful asociat matricei de tranzitie din figura de mai jos

Solutie

Acest model descrie un canal care perturba simbolurile unei surse binare in masura in

care la receptie sa poata fi interpretate ca fiind incerte.

Metoda scalara

C H Y H Y Xp xi

max ( )( )

H Y p y p yii

i( ) ( ) log ( )

1

3

)()1()()()()( 11112211111 xpqxpxypxpxypxpxypyp

S-a utilizat formula probabilitatii totale, evenimentele x1, x2 fiind mutual exclusive.

Analog se poate scrie

p y q p x( ) ( ) ( )2 21

p y p y x p x p y x p x q p x p x q q( ) ( ) ( ) ( ) ( )3 3 1 1 3 2 2 1 2 1

H Y q p x q p x q q q p x q p x

Date post:	02-Mar-2016
Category:	Documents
Upload:	dragos-iulian
View:	254 times
Download:	1 times

Teoria Transmiterii Si Codificarii Informatiei 2011

Documents