Identificarea surselor discrete de informatie

IDENTIFICAREA SURSELOR DISCRETE DE INFORMATIE

1.1. Obiectivele lucrarii

Prezentarea unor notiuni de baza din teoria informatiei;

Stabilirea unui model informational pentru o sursa de informatie, plecand de la o realizare a acesteia sub forma unui fisier text.

1.2. Introducere

1.2.1. Sistem de transmisiune a informatiei

A transmite o informatie este echivalent cu a face o comunicare despre ceva ce nu se cunoaste. Informatia este cantitativ cu atat mai mare cu cat gradul de incertitudine asociat comunicarii respective este mai mare.

Modelul cel mai simplu al unui sistem de transmisiune a informatiei contine sursa, un canal de transmisiune si destinatarul, si este prezentat in figura 1.1. Un astfel de model este valabil pentru distante mici, unde erorile introduse de perturbatiile de pe canal sunt mici, si pentru situatiile in care sursa poate transmite direct mesaje pe canal fara o prelucrare deosebita.

Sursa este mecanismul prin care, din multimea simbolurilor sursei S, se alege intr-un mod aleator, un simbol particular destinat a fi transmis unui corespondent. In schema din figura 1.1 s-a presupus ca sursa de informatie este o marime fizica de natura electrica. Daca sursa este o marime fizica oarecare, se presupune implicit existenta unui traductor.

Prin canal (sau mediu de transmisiune) se intelege orice sistem fizic prin care se pot propaga semnalele de la un capat la altul al acestuia: cablu coaxial, cablu telefonic sau telegrafic, mediu inconjurator (atmosfera), fibra optica etc. Toate semnalele care influenteaza in mod aleator semnalul util, purtator de informatie, constituie perturbatii.

Destinatarul reprezinta destinatia finala la care trebuie sa ajunga mesajul sursei.

1.2.2. Modelarea surselor discrete de informatie

O multime de evenimente formeaza un sistem complet de evenimente daca acestea sunt incompatibile doua cate doua si reuniunea lor este evenimentul sigur. Altfel spus, la fiecare realizare se obtine unul si numai unul din cele N evenimente, ce definesc multimea.

Vom considera o sursa ca fiind un experiment notat cu S, in care rezultatele acestuia pun in evidenta un numar finit de evenimente, notate s₁,,s_n, asociate cu probabilitatile de realizare p(s₁),..,p(s_n). Sursa se considera un camp de probabilitate complet cu distributia:

(1.1)

Intrucat sursa este completa si simbolurile sunt distincte, sunt valabile relatiile:

(1.2.a)

(1.2.b)

iar probabilitatile de aparitie a simbolurilor satisfac conditiile:

(1.2.c)

(1.2.d)

Daca numarul evenimentelor este finit, sursa se numeste discreta. Daca se indeplineste si conditia (1.2.d), sursa este completa. Sursa este fara memorie daca evenimentele s_k sunt independente, adica furnizarea unui simbol la un moment dat nu depinde de simbolurile furnizate anterior. Totalitatea simbolurilor unei surse formeaza alfabetul sursei. Orice succesiune finita de simboluri, in particular un singur simbol, se numeste cuvant. Totalitatea cuvintelor formate cu un anumit alfabet se numeste limbaj.

In concluzie, pentru a descrie o sursa discreta fara memorie (SDFM) sunt necesare doua marimi: alfabetul sursei si probabilitatile de furnizare a fiecarui simbol.

1.2.3.  Marimi informationale

Informatia reprezinta o notiune (marime) strict legata de un eveniment. Cu cat evenimentul este mai incert, deci cu cat cunoastem mai putin despre el, cu atat cantitatea de informatie este mai mare. 

Referat: Contabilitatea tertilor Referat: Structurarea elementelor de activ si pasiv dupa criterii financiare

Definitia 1.1. Se furnizeaza o unitate de informatie cand sursa poate furniza unul din doua mesaje echiprobabile.

Considerand un eveniment s, cu probabilitatea de realizare p(s), atunci, prin definitie, cantitatea de informatie obtinuta este :

(1.3)

Simbolurile care compun alfabetul sursei pot fi de natura foarte diferita (litere, cifre, ansamblu de idei, imagini etc.), in functie de sursa luata concret in studiu.

Fie o sursa cu N simboluri. Informatiile care se obtin la furnizarea fiecarui simbol s₁, s₂, , s_N sunt i(s₁), i(s₂), , i(s_N) si definesc o variabila aleatoare discreta, ce va fi notata cu I, si are distributia:

                     (1.4)

Definitia 1.2. Valoarea  medie a variabilei aleatoare discrete I se numeste entropia sursei S, si se va nota cu H(S).

™

In baza definitiei 1.2, se poate scrie relatia de calcul a entropiei unei surse discrete si fara memorie:

(1.5)

Entropia este informatia medie pe simbol sau, altfel formulat, este incertitudinea medie asupra simbolurilor sursei S.

Limba vorbita sau scrisa este o sursa de informatie discreta cu memorie. Aceasta pentru ca dupa anumite litere, din cauza regulilor ortoepice ale limbii, urmeaza numai anumite litere stabilite de gramatica fiecarei limbi. De exemplu, in limba romana:

inainte de consoanele b, d, g si v se scrie z;

inainte de l, m, n se scrie s;

Daca un text este considerat ca o sursa fara memorie, atunci entropia este maxima. Intrucat, de cele mai multe ori, probabilitatea de aparitie a unei litere este conditionata de una sau mai multe litere scrise anterior, textul literar sau tehnico-stiintific trebuie modelat ca o sursa cu memorie.

Ordinul sursei cu memorie difera de la o limba la alta, si duce la scaderea entropiei, deci aparitia unei redundante. Redundanta unei limbi, deci folosirea unui surplus de litere pentru a transmite informatie putina, are avantajul protectiei transmiterii informatiei impotriva perturbatiilor, cand, desi unele litere nu se aud sau nu se inteleg, cuvantul in ansamblu se poate intelege. Limba vorbita sau scrisa este redundanta pentru ca unele cuvinte se repeta, in mod inutil uneori, o idee (informatie) continuta in sensul altor cuvinte pronuntate anterior. Ideal, entropia unei limbi este de 1 bit/litera.

Definitia 1.3 Debitul de informatie al unei surse discrete, complete si fara memorie, este cantitatea medie de informatie furnizata in unitatea de timp.

™

Daca t_i este durata necesara transmiterii simbolului s_i atunci durata medie de emisie a unui simbol este :

                  (1.6)

Debitul de informatie H_t(S) al sursei S este:

(1.7)

Definitia 1.4: Eficienta unei sursei discrete este raportul dintre entropie si valoarea maxima a entropiei:

(1.8)

Definitia 1.5: Redundanta unei surse discrete de informatie este diferenta dintre valoarea maxima posibila a entropiei si valoarea curenta:

[bit simbol (1.9)

Exista posibilitatea de a defini si o redundanta relativa dupa relatia:

                                             (1.10)

1.3. Desfasurarea lucrarii

1.     Se considera un fisier text oarecare, cu un numar de maxim 20 linii. Se scrie un program pentru stabilirea modelului informational al sursei ce a furnizat fisierului text. Se determina numarul de simboluri distincte si frecventa de aparitie a simbolurilor.

2.     Vom prezenta in continuare programul in Matlab plus pseudocodul acestuia, program ce satisface cerintele punctului 1 si anume determinarea numarului de simboluri si frecventa lor de aparitie.

Exemplu:

2.1.sursa.txt='ana _ are _ mere _ mari'

txt=ana _ are _ mere _ mari

S=[an _ remi]

F=[4 1 3 3 3 2 1]

2.2.sursa.txt='astazi _ este _ o _ zi _ frumoasa _ de _ primavara _ dar _ tot _ nu _ este _ ca _ o _ zi _ de _ vara'

txt=astazi _ este _ o _ zi _ frumoasa _ de _ primavara _ dar _ tot _ nu _ este _ ca _ o _ zi _ de _ vara

S=[astzi _ eofrumdpvnc]

F=[11 4 4 3 4 15 6 4 1 5 2 2 3 1 2 1 1]

3.     Sursa studiata se considera ca fiind o sursa discreta si fara memorie. Sa se calculeze entropia , eficienta  si redundanta sursei.