TTI -Teoria Transmisiei Informatiei Note

download TTI -Teoria Transmisiei Informatiei Note

of 90

  • date post

    22-Feb-2018
  • Category

    Documents

  • view

    237
  • download

    0

Embed Size (px)

Transcript of TTI -Teoria Transmisiei Informatiei Note

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    1/90

    TTI - Teoria Transmisiei Informatiei

    Note de curs

    Daniela Coltuc

    2010

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    2/90

    Notatii si abrevieri

    X variabila aleatoare

    ix realizare particulara a variabilei aleatoare X

    ( ) ( ) iii pEpExp === probabilitatea ca evenimentul iE sa se realizeze

    ( )xF functie de repartitie sau distributie a unei variabile aleatoare

    ( )xf densitate de probabilitate a unei variabile aleatoare

    [ ]X alfabetul sursei

    [ ])(XP setul de probabilitati asociat alfabetului [ ]X

    ( )XH entrpia sursei cu alphabet [ ]X

    v.a. variabila aleatoare

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    3/90

    1. INTRODUCERE

    Teoria Informatiei raspunde la doua intrebari fundamentale in telecomunicatii :

    - Cat de mult se poate transmite printr-un canal de comunicatie ?(In anii 40,

    comunitatea stiintifica credea ca marind cantitatea de informatie transmisa printr-un

    canal, creste si probabilitatea eronarii ei ; Shannon a surpris lumea stiintifica, aratand

    ca transmisia poate fi facuta corect, cu conditia ca rata de transmisie sa nu depaseasca

    capacitatea canalului; capacitatea canalului se poate calcula din caracteristicile

    zgomotului existent in canal)

    - Cat de mult pot fi compresate datele ?(Shannon a aratat ca datele reprezentand

    procese aleatoare ca muzica sau vorbirea, nu pot fi compresate sub o anumita limita pe

    care a numit-o entropie, un termen folosit deja in termodinamica ; apoi a aratat ca daca

    entropia este mai mica decat capacitatea canalului, atunci transmisia datelor se poate

    face fara erori)

    Teoria Informatiei are contributii si in alte domenii (Fig. dinElements of InformationTheory,

    Thomas M. Cover, Joy A. Thomas)

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    4/90

    Theoria Informatiei a fost elaborata de Claude Shannon (1916-2001).

    Biografie

    1935 Licenta la Michigan University

    1936 Asistent de cercetare la MIT (Mesechusetts Institute of Technolgy)

    Master

    1940 Doctorat in matematica cu teza Mathematics in genetics

    15 anila Bell Laboratories in compania unor personalitati din lumea stiintei : John Pierce

    (comunicatiile prin satelit), Harry Nyquist (Teoria semnalelor), Hendrik Bode (diagramele),

    inventatorii tranzistorului (Shokley, Bardee,Brattain).

    1948 Shannon a elaborat Teoria informatiei, una dintre teoriile cu cel mai mare impact in

    secolul XX.

    1.1. Schema generala a unui sistem de comunicatii

    Definitie : Un sistem de transmisiune (de comunicatie) este un ansamblu fizic care realizeaza

    transmiterea unui mesajde la o sursala un utilizator.

    S sursa de mesaje

    CoS Codor de sursa (compresia datelor)

    CoC Codor de canal (protectie contra perturbatiilor)

    m modulator

    CANAL Canal de comunicatie

    Dm demodulator

    P PerturbatiiDecC Decodor de canal

    DecS Decodor de sursa

    U Utilizator

    Observatie : Aceasta este o schema completa; in functie de de aplicatie, unele bolcuri pot

    lipsi.

    m dm

    S CoS CoC C A N A L DecC DecS U

    P

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    5/90

    2. INTRODUCERE IN TEORIA PROBABILITATILOR

    2.1. Experiment aleator, evenimente

    Definitie :Un experiment aleatoreste un experiment cu mai multe rezultate posibile.

    Definitie :Rezultatele unui experiment aleator se numesc evenimente.

    Exemplu :aruncarea unui zar

    Este un experiment cu 6 evenimente posibile.

    Multimea evenimentelor posibile [ ]61 ,, EE K= Multimea evenimentelor se poate largi adaugand: - evenimentul sigur (orice fata)

    - evenimentul imposibil (fata 7)

    - evenimente compuse (fata para)

    Rezultatul unui experiment aleator nu este cunoscut dinainte ; realizarea unui anumit

    eveniment este caracterizata de o probabilitate.

    2.2. Probabilitatea unui evenimenti

    E

    Definitia 1(clasica, de acum cateva secole): ( )p

    f

    iN

    NEp = unde fN este numarul de cazuri

    favorabile evenimentului si pN numarul de cazuri posibile.

    Definitia 2 (Von Mises, inceput de sec XX): ( )n

    nEp a

    ni

    = lim unde an este numarul de

    aparitii ale evenimentului si n este numarul total de exeperimente.

    Definitia 3 (Kolmogoroff, 1933): Axiomele probabilitatilor

    a) 0p probabilitatea este un numar nenegativ

    b) ( ) 1=Sp probabilitatea evenimentului sigur este 1c) ( ) ( ) ( )2121 EpEpEEp +=+ probabilitatea a doua evenimenete mutual exclusive,

    1E si 2E , este egala cu suma probabilitatilor evenimentelor.

    2.3.Variabila aleatore

    Variabila aleatoare este o notiune folosita pentru a descrie evenimentele rezultate in urma

    unui experiment aleator.

    Definitie: Variabila aleatoare(v.a.) este o functie care asociaza fiecarui eveniment o valoare

    numerica.

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    6/90

    Notam cu Xv.a.

    X: R (Xasociaza fiecarui eveniment o valoare numerica)

    Exemplu:

    Zarul X: [ ] [ ]6,5,4,3,2,1,, 61 = EE K

    Observatie:

    a) Oricarei submultimi a multimii valorilor lui Xii corespunde un eveniment

    b) 6,5,4,3,2,1 se numesc realizari particulare a le v.a. X.

    2.4. Probabilitatile unei v.a.

    Notam probabilitatea ca un eveniment iE sa se realizeze cu:

    ( ) ( ) ( ) iiii pxpxXpEp ====

    Exemplu:

    Zarul : multimea valorilor lui Xeste discreta

    Temperatura ia valori intr-un interval.

    Definitia 1 (tipul v.a.) : V.a. discreta ia valori intr-o multime discreta

    V.a. continua ia valori intr-un interval

    V.a. mixta

    Definitie: Functia de repartitiea unei v.a. (sau distributia v.a.)

    ( ) { }xXpxF =

    Definitie: Densitatea de probabilitatea v.a. (derivata functiei de repartitie)

    ( )dx

    dFxf =

    Exemplu:

    Zarul: Functia de repartitie este o functie in scara scara

    Densitatea de probabilitate este o serie de functii Dyrac

    Densitate de probabilitate gaussiana (sau normala): ( )( )

    2

    22 2/

    =xx

    xf unde este

    media v.a., iar 2 este varianta v.a. ( se numeste dispersie).

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    7/90

    Alte modele de distributii continue:

    Densitatea de probabilitate uniforma: ( ) [ ]

    =restin

    axaxf

    _0

    0/1

    Densitatea de probabilitate exponentiala: ( )

    =

    restin

    xexf

    x

    _0

    0

    Definitia 2 (tipul v.a.) : O v.a. este discreta daca are o functie de repartitie in scara; o v.a. este

    continua daca are o functie de repartitie continua.

    2.5. Probabilitati conditionate

    Exemplu:La aruncarea cu zarul, probabilitatea de a avea un 2 cand stim ca fata aparuta este

    para.

    Definitie: Probabilitatea unui eveniment iE , conditionat de un alt eveniment ,M, este

    probabilitatea de a se realizaiE cand M este deja realizat

    ( ) ( )

    ( )MpMEp

    MEp ii

    ,/ = unde ( )MEp

    i, este probabilitatea ca atat

    iE cat si Msa

    se realizeze.

    Observatie: iE si Mpot fi evenimente ale aceluiasi experiment (aceeasi v.a.) sau pot fi

    evenimente a doua experimente diferite (2 v.a.).

    ( )( )

    j

    ji

    jixp

    xxpxxp

    // = (aceeasi v.a.)

    ( )( )

    j

    ji

    jiyp

    yxpyxp

    // =

    Teorema lui Bayes: ( ) ( )

    ( )jiij

    ji

    yp

    xpxypyxp

    // =

    Teorema probabilitatii totale :

    ( ) ( ) ( ) ( ) ( ) ( ) ( )NNiiii ypyxpypyxpypyxpxp /// 2211 +++= K

    UndeN

    yyy ,,, 21 K constituie o partitie a multimii valorilor v.a. Y.

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    8/90

    Observatii:

    a) Functia de repartitie si densitatea de probabilitate se definesc si pentru v.a. conditionate

    ( ) { }MxXpMxF = ( )

    ( )dx

    MxdF

    Mxf =

    b) Functia de repartitie si densitatea de probabilitate se definesc si pentru 2 sau mai multe v.a.

    ( ) { }yYxXpyxF = ,, ( ) ( )

    dxdy

    yxdFyxf

    ,, =

    2.6. Notiunea de independenta statistica

    Definitie:Doua evenimente, iE si jE , sunt independente daca

    ( ) jiji

    EpEpEEp =,

    Definitie: Doua v.a., Xsi Y, sunt independente daca oricare dintre realizarile lor particulare

    sunt independente.

    ( ) jiji

    ypxpyxp =, unde ix este o realizare particulara a lui Xsi

    jy este o realizare particulara a lui Y.

    2.7. Semnalele numerice ca siruri de v.a.

    Cum se ajunge la un semnal numeric? Prin esantionarea si cuantizarea semnalului continuu.

    Un semnal numeric poate fi modelat ca un sir de v.a.: KK ,,,, 11 + kkk XXX , unde keste

    indice de timp. Toate v.a. iau valori in aceeasi multime si, daca semnalul este stationar, au

    acelasi set de probabilitati.

  • 7/24/2019 TTI -Teoria Transmisiei Informatiei Note

    9/90

    3. SURSE DE INFORMATIE

    3.1. Informatia

    3.1.1. Definitii si notatii

    Definitie: Informatia este cantitateade incertitudine pe care o avem asupra producerii unui

    eveniment, rezultat in urma unui experiment aleator.

    Fie un experiment aleator ale carui rezultate sunt descrise prin v.a. X, care ia valori in

    multimea [ ] [ ]nxxxX ,,, 21 K= . Incertitudinea asupra evenimentului iE , caruia ii corespunde

    realizarea particularai

    x , se noteaza:

    ( ) ( )ii

    xUxXUi

    EU ===

    Ude la uncertainty

    Incertitudineasi informatiasunt, din punct de ve