Cursuri Teoria Transmisiunii Informatiei

4. ENTROPIA SURSELOR DISCRETE DE INFORMATIE

Definitie: Entropia unei surse discrete de informatie este cantitatea de informatie, medie pe simbol, generata de sursa.

Entropia sursei fara memorie

Expresia entropiei:Entropia unei surse fara memorie se calculeaza cu urmatoarea expresie:

Justificare: Fie un sir tipic generat de sursa. Din numararea simbolurilor de acelasi fel rezulta valorile

(). Sirul fiind tipic, pentru , numarul de aparitii ale unui simbol este aproximativ . Deci, probabilitatea estimata de aparitie a sirului este: si, in consecinta, informatia sirului este:

iar entropia

Observatie: Aceasta expresia entropei este valabila si pentru sursele neergodice sau sursele nestationare.Unitatea de masura pentru entropie: bit/simbol.

Proprietatile entropieia) Entropia este totdeauna mai mare sau egala cu zero

b) Continuitate: este continua in raport cu variabilele

c) Simetrie: este simetrica in raport cu variabilele

d) este maxima cand simbolurile sursei sunt echiprobabile

e) Aditivitate:

e1) compunerea simbolurilor descreste entropia

e2) scindarea(descompunerea) simbolurilor creste entropia

Entropia sursei binareFie alfabetul cu probabilitatile

Entropia

Pentru sau ,

Pentru , entropia este maxima

Entropia sursei Markov

Fie sursa Markov de ordin k, cu alfabetul:

si alfabetul starilor:

Definitie: Entropia sursei Markov este informatia medie pe stare, generata de sursa:

unde este informatia medie cand sursa se afla in starea particulara :

Proprietate: Entropia sursei Markov este mai mica decat entropia unei surse fara memorie care ar genera aceleasi simboluri (dependenta de trecut diminueaza (micsoreaza) cantitatea medie de informatie pe simbol):

Justificare:

Demonstratia se bazeaza pe urmatorul rezultat:

Inegalitatea fundamentala (lema):

Fie cu si cu

doua seturi de probabilitati.

Atunci

Demonstratie lema (indicatie): se porneste de la si se noteaza

.Definitie: Marimea se numeste entropie relativa sau distanta Kullback-Liebler. Entropia relative este o marime nenegativa; ea ia valoarea zero cand cele doua distributii sunt egale (se foloseste pentru a masura similaritatea a doua distributii).

Decorelarea sursei MarkovDefinitie: Decorelarea este operatia prin care un semnal numeric, modelat printr-o sursa Markov, este transformat intr-o sursa fara memorie. In practica se realizeaza o quasi-decorelare, adica se obtine o sursa cu memorie de lungime redusa si cu dependenta mica intre simboluri.Cea mai simpla metoda de decorelare este predictia liniara cunoscuta si sub numele de DPCM (Differential Pulse Code Modulation)

Cazul semnalelor 1DFie un semnalul numeric format din urmatoarele esantioane :

Semanalul decorelat se obtinecalculand diferenta intre simbolurile consecutive:

Debit, redundanta, redundanta relativa

Definitie: Debitul de informatie al unei surse este cantitatea medie de informatie generata pe secunda de sursa.

unde este durata unui symbol

Unitatea de masura pentru debit este bit/sec.

Definitie: Redundanta unei surse de informatie este:

Unde este entropia maxima a sursei (entropia in cazul simbolurilor echiprobabile) si este entropia sursei. Unitatea uzuala de masura este bit/simbol.Definitie: Redundanta relativa a unei surse este

Redundanta relativa este adimensionala.

Entropia conjugata a doua surse de informatie

Fie doua surse de informatie:

cu

si

cu

Definitie: Entropia conjugata (sau compusa) a surselor si este

Observatii:a) Informatia conjugata este totdeauna pozitiva

b) Unitatea uzuala de masura pentru informatia conjugata este bit/simbol.Cazuri particulare:

1. Daca sursele de informatie sunt independente:

Demonstratia se bazeaza pe definitia v.a. independente:

2. Daca sursele sunt identice:

3. Daca sursele sunt dependente statistic:

Demonstratia se face folosind inegalitatea fundamentala, in cazul seturilor de probabilitati si .

Informatia mutuala a doua surse

Definitie: Informatia mutuala a doua surse si este media informatiilor mutuale a perechilor de simboluri generate de surse:

Unitatea de masura uzuala pentru este bit/simbol.

Cazuri particulare:

1. Daca si sunt independente:

; Demonstratia se bazeaza pe definitia v.a. independente: .

2. Daca si sunt identice:

3. Daca si sunt dependente statistic: si

Proprietati:

1.

Justificare: Se calculeaza expresia din stanga, scriindu-i pe si ca functii de probabilitatile ambelor v.a. De exemplu, , conform Teoremei probabilitatii totale. Informatia mutuala este o marime nenegativa: .

Justificare: Rezulta din proprietatea entropiei conjugate

Observatie: Desi informatia mutuala a doua simboluri poate fi si negativa, informatia mutuala a doua surse este totdeauna nenegativa. Entropia conditionata a sursei de informatieDefinitie: Entropia sursei , conditionata de sursa , este cantitatea medie de incertitudine care ramane asupra lui , cand se cunoaste .

Observatie: este incertitudinea medie asupra lui , cand a generat simbolul . In medie, aceasta incertitudinea este

.Cazuri particulare:

1. Daca si sunt independente:

Demonstratia se bazeaza pe definitia v.a. independente: .

2. Daca si sunt identice:

3. Daca si sunt dependente statistic:

Relatii intre entropii (Diagrame Venn)

Reprezentarea entropiilor prin Diagrame Venn:Sursele X si Y sunt independent

Sursele X si Y sunt identice

Sursele X si Y sunt dependente statistic

Relatii intre entropii

si

Generalizare(cazul a surse)

Diagrama Venn pentru 3 surse de informatie :

a) (se deduce din Diagrama Venn)

unde

b)

Pentru surse, prin analogie cu relatiile anterioare, putem scrie:a)

Daca sursele sunt independente, atunci:

b)

H(Y/X,Z)

H(X/Y,Z)

H(Z/X,Y)

5

_1284694165.unknown

_1284697672.unknown

_1284699941.unknown

_1284738453.unknown

_1285514495.unknown

_1294654917.unknown

_1294657345.unknown

_1294658091.unknown

_1285692112.unknown

_1285692220.unknown

_1285437838.unknown

_1285438771.unknown

_1285439716.unknown

_1285440308.unknown

_1285440584.unknown

_1285439023.unknown

_1285438624.unknown

_1285437598.unknown

_1285437659.unknown

_1284738505.unknown

_1284737113.unknown

_1284737501.unknown

_1284737865.unknown

_1284737338.unknown

_1284735706.unknown

_1284735799.unknown

_1284735568.unknown

_1284698984.unknown

_1284699278.unknown

_1284699323.unknown

_1284699882.unknown

_1284699186.unknown

_1284699225.unknown

_1284698343.unknown

_1284698373.unknown

_1284698135.unknown

_1284698148.unknown

_1284697688.unknown

_1284695874.unknown

_1284697122.unknown

_1284697257.unknown

_1284697391.unknown

_1284697208.unknown

_1284695992.unknown

_1284696031.unknown

_1284695978.unknown

_1284694474.unknown

_1284694920.unknown

_1284695826.unknown

_1284694651.unknown

_1284694356.unknown

_1284694438.unknown

_1284694295.unknown

_1284221152.unknown

_1284380273.unknown

_1284381542.unknown

_1284381624.unknown

_1284381689.unknown

_1284380911.unknown

_1284381280.unknown

_1284381311.unknown

_1284380490.unknown

_1284221290.unknown

_1284379755.unknown

_1284380006.unknown

_1284380053.unknown

_1284221321.unknown

_1284221232.unknown

_1284221255.unknown

_1284221206.unknown

_1284218698.unknown

_1284220357.unknown

_1284220906.unknown

_1284221005.unknown

_1284220404.unknown

_1284220311.unknown

_1284218153.unknown

_1284218516.unknown

_1284218636.unknown

_1284218419.unknown

_1284209772.unknown

_1284217910.unknown

_1284217979.unknown

_1283825904.unknown

_1283831165.unknown

_1283825891.unknown