Surse discrete de informatie

Modelarea matematica a sursei discrete

O sursa discreta de informatii X, de alfabet discret X, emite la momente de timp discrete simboluri cu distributia de probabilitati .

Alfabetul contine simboluri, si .

Succesiunea de simboluri emise de sursa formeaza un sir sau o secventa de date aleatoare de dimensiune n.

Emiterea unui simbol la un anumit moment de timp , reprezinta un eveniment ce poate fi dependent sau nu de evenimentele anterioare, respectiv de simbolurile emise anterior momentului de timp .

Consideram fiecare simbol x_i emis de sursa de informatie ca o valoare particulara pentru v.a. X, avand alfabetul X si distributia de probabilitate ce indeplineste relatia

O secventa n-dimensionala de simboluri emise de sursa, , reprezinta o realizare particulara pentru o secventa indexata de v.a. . Multimea de secvente n-dimensionale formate din simboluri din alfabetul X , apartine alfabetului ce contine elemente.

Probabilitatea de aparitie a unei secvente este:

Distributia de probabilitate n-dimensionala ce caracterizeaza secventa de v.a. satisface conditia:

Daca fiecare simbol este o valoare particulara pentru variabila aleatoare de alfabet X si de distributie atunci secventele de date reprezinta o secventa indexata de variabile aleatoare identice

Daca variabilele aleatoare sunt nu numai identic distribiute dar si independente:

atunci sursa discreta de informatii este fara memorie

Parametrii sursei discrete:

Alfabetul sursei

Durata simbolurilor emise

distributia de probabilitati a simbolurilor emise

dependenta probabilistica intre simboluri ce formeaza un mesaj

2.2. Surse discrete de informatii

Clasificarea surselor discrete:

Surse discrete stationare;

Surse discrete fara memorie;

Surse discrete cu memorie;

Surse Markov;

Surse discrete cu constrangeri;

Surse binare;

Surse extinse.

Surse discrete stationare

Pentru o sursa stationara avem urmatoarele doua conditii:

Probabilitatile de emitere a simbolurilor depind numai de pozitia lor relativa si nu de pozitia lor absoluta. Deci, ele sunt invariante in timp. Daca J este un set de n indici, , atunci:

.

Probabilitatile trebuie sa fie consitente. Aceasta inseamna ca daca este un set de n indici, pentru un n arbitrar si j este un indice care nu apartine lui J, atunci pentru toate valorile posibile ale simbolurilor , are loc relatia:

.

Surse Discrete Fara Memorie (SDFM)

Pentru o SDFM probabilitatea de emitere a unui simbol , la momentul de timp , este independenta de simbolurile emise la momentele de timp anterioare si in consecinta:

.

Deci o SDFM emite o secventa de simboluri independente.

Independenta (i.d.) simbolurilor succesive ne permite sa scriem pentru o secventa

.

Daca toate v.a. din secventa au acelasi alfabet cu sursa X, ele sunt si identic distribuite, reprezentand o secventa i.i.d., deci:

Conditia de independenta intre valorile succesive x₁, x₂,.,x_n ale v.a. se exprima matematic in termenii f.d.p. conditionata n-dimensionala:

.

Pentru primele doua momente de observare, t₁ si t₂, valorile v.a. fiind independente de valorile v.a. rezulta

,

si generalizand: 

.

deci f.d.p. de ordinul n se poate determina cunoscand f.d.p. de ordinul unu.

Daca cele n variabile sunt nu numai independente ci si identic distribuite, formand o secventa de v.a. i.i.d. vom putea scrie:

Surse Discrete Cu Memorie (SDCM)

Pentru o sursa dicreta cu memorie, probabilitatea de emitere a unui simbol este dependenta de simbolul precedent sau de mai multe simboluri emise la momente de timp anterioare.

Surse Markov

Consideram secventa de v.a. generate de sursa X si descrisa de f.d.p. reunita de ordinul n,

Pentru memorie de ordinul 1, valoarea x_n a v.a. depinde de valorile precedente , observate la momentele de timp t_n-1, t_n-2, ., t₂, t₁ numai prin intermediul ultimei valori , observata la momentul de timp t_n-1, deci: 

.

In aceste conditii, sursa se numeste Sursa Markov de ordin 1 sau mai simplu sursa Markov si este complet descrisa de f.d.p. de ordinul doi:

.

Factorizarea distributiei de probabilitati n-dimensionale in termenii distributiilor de ordinul unu si doi este realizata astfel:

.

Surse discrete cu constrangeri

lipseste text

Surse binare

O sursa binara are alfabetul si cardinalitatea alfabetului . O secventa a sursei X este o secventa de biti de lungime n.

Comportamentul statistic al sursei binare fara memorie, in cazul in care v.a. sunt modelate ca v.a. i.i.d., este complet descris de un singur parametru p care specifica probabilitatea ca sursa sa genereze un simbol "1".

.

Considerand o secventa particulara de a simboluri "0" si simboluri "1", probabilitatea de aparitie a intregii secvente este de:

.

2.3. Surse extinse

In discutarea conceptelor de teoria informatiei, gasim adeseori folositor sa consideram blocuri de simboluri mai degraba decat simboluri individuale, fiecare bloc constand din n simboluri succesive ale sursei. Putem considera fiecare asemenea bloc ca fiind produs de o sursa extinsa cu un alfabet al sursei care are blocuri distincte.

de extins

2.4. Entropia surselor discrete

Surse discrete fara memorie (memorie zero)

Pentru o sursa discreta fara memorie X, cantitatea de informatie continuta de sirul de n date , reprezentand realizarile independente si identic distribuite, egaleaza suma informatiei medii continuta intr-un simbol:

Daca datele sunt i.i.d., atunci

Surse discrete cu memorie

Pentru o sursa discreta cu memorie X, simbolurile sursei X sunt dependente probabilistic, adica:

,

iar cantitatea de informatie continuta de sirul de n date este mai mica decat suma informatiei medii continuta intr-un simbol:

Daca datele sunt i.d., atunci

Surse discrete, extinse, fara memorie

In discutarea conceptelor de teoria informatiei, gasim adeseori folositor sa consideram blocuri de simboluri mai degraba decat simboluri individuale, fiecare bloc constand din n simboluri succesive ale sursei. Putem considera fiecare asemenea bloc ca fiind produs de o sursa extinsa cu un alfabet al sursei care are blocuri distincte.

In cazul unei surse discrete fara memorie, simbolurile sursei sunt statistic independente. Deci, probabilitatea unui simbol al sursei Xⁿ cu alfabetul este egala cu produsul probabilitatilor celor n simboluri ale sursei X cu X

Putem asadar sa ne asteptam, intuitiv ca entropia sursei extinse H(Xⁿ) sa fie egala cu de n ori entropia sursei originale H(X). Adica putem scrie:

Exemplul 1: SDFM - Entropia sursei primare

Fie o sursa discreta fara memorie X, cu alfabetul sursei si cu probabilitatile de emitere a simbolurilor: .

Entropia sursei X se poate calcula ca fiind:

Consideram in continuare extensia de ordinul doi a sursei. Daca alfabetul sursei X este format din trei simboluri, rezulta ca alfabetul sursei extinse X² are noua simboluri.

In tabelul de mai jos se prezinta cele noua simboluri din alfabetul X ², notate cu ,    impreuna cu blocurile de simboluri ale sursei primare luate doua cate doua si probabilitatile aferente.

Folosind relatia de definitie, putem calcula entropia sursei extinse ca fiind:

Putem observa ca intr-adevar are loc relatia .

Exemplul 2: SDCM - Entropia sursei primare

Se considera sursa binara S descrisa de alfabetul si de probabilitatile de aparitie ale simbolurilor

Probabilitatile conditionate de emitere a unui simbol sunt:

Pentru sursa primara S, calculam entropia:

biti/simbol.

Entropia maxima a sursei primare este:

Redundanta sursei primare este:

biti/simbol.

Exemplul 3: SDFM - Entropia sursei extinse

Sursa extinsa de ordinul 2, S², este descrisa de alfabetul .

Deoarece simbolurile emise de sursa sunt independente (sursa este fara memorie), atunci:

Entropia sursei extinse de ordin 2, fara memorie, este:

biti/simbol.

Entropia maxima a sursei extinse de ordin 2, este:

biti/simbol,

iar redundanta:

biti/simbol.

Exemplul 4: SDCM - Entropia sursei extinse

Pentru sursa discreta, de ordin 2, cu memorie, , emiterea unui simbol depinde de emiterea simbolului precedent, probabilitatile simbolurilor extinse fiind:

In aceste conditii, entropia sursei extinse de ordin 2 este:

biti/simbol biti/simbol.

Entropia maxima a sursei extinse de ordin 2, cu memorie, este:

biti/simbol.

Redundanta SDCM este mai mare decat redundanta SDFM:

biti/simbol biti/simbol.

2.5. Rata entropiei surselor discrete

Entropia sursei extinse de ordin n, , este de obicei o functie nemarginita nedescrescatoare de n, deoarece este rezonabil sa presupunem ca pentru multe surse, multe din iesirile surselor contribuie la entropie. De exemplu, pentru un numar infinit de v.a. , entropia conditionata este strict pozitiva. Din acest motiv, este mai folositor sa folosim entropia medie pe litera (rata entropiei) definita astfel:

.

Observatie:

Pentru o sursa fara memorie X, de entropie , avem:

,

deci in acest caz, entropia medie pe litera este chiar entropia pe litera actuala.

Dupa cum se stie, entropia conditionata , cunoscuta ca entropie de inovatie, joaca acelasi rol ca si

Proprietatile entropiei medii pe litera:

1. este necrescatoare in raport cu n;
2. ;
3. este necrescatoare in raport cu n;
4. .

Rata entropiei este definita ca:

Se poate arata ca rata entropiei joaca acelasi rol pentru surse stationare precum o face entropia pentru surse fara memorie, descriind cea mai mica rata posibila pentru compresia de date.