Download - TTI -Teoria Transmisiei Informatiei Note

Transcript
  • 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 vedere cantitativ, doua notiuni echivalente.

    Vorbim despre incertitudine inainte de producerea evenimentului si de informatie dupa

    producerea sa.

    ( ) ( )ii

    xixU =

    i de la information

    Incertitudinea/informatia unui eveniment este o functie de probabilitatea de aparitiei

    p a

    evenimentului:

    ( ) ( ) ( )iii

    pFxixU ==

    3.1.2.Specificarea functiei F

    Trei proprietati intuitive pentru F:

    a) Ftrebuie sa fie descrescatoare (incertitudinea este mai mica atunci cand probabilitatea de

    aparitie a evenimentului este mare).

    b) Ftrebuie sa fie aditiva (incertitudinea asupra a doua evenimente, rezultate din

    experimente independente, trebuie sa fie egala cu suma incertitudinilor asupra celor doua

    evenimente):

    ( ) jiji

    qFpFqpF +=,

    undei

    p sij

    q sunt probabilitatile celor doua evenimente independente.

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

    10/90

    c) ( ) 01 =F (incertitudinea asupra unui eveniment sigur este nula).

    Observatie:Cele doua evenimente pot apartine si aceluiasi experiment; in acest caz,

    independenta se traduce prin conditia ca producerea unuia sa nu influenteze in niciun fel

    producerea celuilalt.

    Functia care indeplineste cerintele b) si c) este logaritmul;pentru a satisface si cerinta a),

    luam negativul logaritmului:

    ( ) ( )ii ppF log=

    Deci, incertitudinea/informatia asupra unui eveniment care are probabilitateai

    p , se

    calculeaza cu :

    ( ) ( ) ( )iii pxixU log==

    Proprietati :

    - informatia este totdeauna o cantitate pozitiva

    - informatia adusa de un eveniment sigur este zero

    3.1.3. Unitati de masura pentru informatie

    a) BIT (BInary uniT)

    Definitie :1 bit este cantitatea de informatie care se obtine cand se realizeaza un eveniment

    cu probabilitatea 1/2.

    ( )2/1log1 2=bit

    b) DIT (Decimal unIT)

    Definitie :1 dit este cantitatea de informatie care se obtine cand se realizeaza un eveniment

    care are probabilitatea 1/10..

    ( )10/1log1 10=dit

    c) NAT (Natural uniT)

    Definitie :1 nat este cantitatea de informatie care se obtine cand se realizeaza un eveniment

    cu probabilitatea 1/e.

    ( )enat /1ln1 =

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

    11/90

    Transformarea unitatilor :

    bitdit 32,31 =

    bitnat 44,11 =

    3.1.4. Informatia mutuala a doua evenimente

    De ce este necesar studiul a doua evenimente ? In transmisia semnalelor, pe canalul de

    comunicatie, de cele mai multe ori, apar perturbatii care modifica semnalul. De aceea,

    semnalul de la intrarea in canal si cel de la iesire se descriu prin doua v.a. diferite, Xsi Y.

    Daca puterea perturbatiilor este finita, atunci aceste v.a. nu sunt independente.

    Fie ix si jy doua realizari particulare ale lui Xsi Y. Sa pp. Ca numai jy este observabil.

    Informatia mutuala a celor doua evenimente este:

    ) ( ) )jiiji

    yxUxUyxi /, =

    unde ji yxU / este incertitudinea care ramane asupra lui ix dupa producerea lui jy (cand se

    cunoastej

    y ) .

    ( ) ( ) ( )( ) ( )

    ji

    ji

    jiijiypxp

    yxpyxpxpyxi

    ,log/loglog, =+=

    Observatie:informatia mutuala poate fi si negativa.

    Exemplu:

    ( ) 2/1=ixp ) 4/1/ =ji yxp

    121, ==ji yxi

    Cazuri posibile de dependenta intre Xsi Y:

    a) Xsi Y sunt identice (maxim de dependenta):

    ( )iji xpyxp =, si ( )iji xiyxi =,

    b) Xsi Y sunt diferite, dar dependente statistic

    1/

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

    12/90

    c) Xsi Y sunt independente statistic

    ( ) jiji

    ypxpyxp =, si 0, =ji yxi

    3.2. Surse discrete de informatie

    3.2.1. Definitii si notatii

    Definitie :

    Sursa discreta de informatie este un mecanism de generare a unui sir de

    v.a.discrete : KK ,,,, 11 + kkk XXX , unde keste, de cele mai multe ori, un indice de timp.

    Sursa de informatie este definita printr-unalfabet [ ] [ ]NxxxX ,,, 21 K= , care estemultimea realizarilor particulare ale v.a. KK ,,,, 11 + kkk XXX si

    unset de probabilitati [ ] [ ]NpppP ,,, 21 K= , unde ( )ii xpp = (setul de probabiliti poate variain functie de k; on acest caz, spunem ca sursa este nestationara).

    1=i

    ip

    Definitii :

    Simbolul (saulitera) este elemental fundamental, ireductibil, care contine informatie.

    Nxxx ,,, 21 K sunt simboluri

    Alfabetuleste totalitatea simbolurilor diferite care pot fi generate de sursa.[ ]X este alfabetul sursei

    Cuvantuleste o succesiune de simboluri (Exemplu: un byte este o succesiune de 8

    simboluri binare).

    Limbaeste totalitatea cuvintelor formate cu un alphabet (Exemplu: 256 de cuvinte

    binare de 8 biti).

    Exemple de surse discrete:

    1. Banda cu text de la TV este o sursa care emite litere: IN TARA AU FOST

    INUNDATII

    2. Un semafor este o sursa cu trei simboluri: rosu, galben, verde

    3. Un iPod este o sursa care genereaza simboluri binare care sunt convertite intr-o

    melodie.

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

    13/90

    3.2.2. Clasificarea surselor discrete

    a) Din punctual de vedere al dependentei dintre v.a kX .:

    - surse fara memorie

    - surse cu memorie

    Definitie:Sursa fara memorie(simpla sau independenta) genereaza v.a. independente. Cu

    alte cuvinte, probabilitatea de a genera un anumit simbolix la momentul knu depinde de

    simbolurile generate anterior.

    )(,...),/( 21 ikkkik xXpXXxXp ===

    Definitie:Sursa cu memoriegenereaza v.a. dependente.

    Definitie:Dimensiunea memorieisursei este egala cu numarul de simboluri anterioare care

    conditioneaza probabilitatea de aparitie a unui nou simbol.

    Exemplu: )/( 1= kik XxXp este o sursa cu memorie de lungime 1.

    b) Din punctul de vedere al stabilitatii setului de probabilitati

    - surse stationare

    - surse nestationare

    Definitie:o sursa stationara are un set de probabilitati care nu variaza in functie de k.

    )()( ikik xXpxXp === + oricare ar fi k, sau i .

    Un caz particular al surselor stationare este sursa ergodica. Pentru a defini sursa ergodica, ne

    bazam pe notiunea de sir tipic.

    Definitie:Sir tipic

    Fie un sir de simboluri generat de sursa, suficient de lung a.i. sa putem estima

    probabilitatile de aparitie a simbolurilor folosind definitia probabilitatii ca raport intre

    numarul de cazuri favorabile si numarul total de cazuri.

    Daca intr-un sir, probabilitatile astfel estimate sunt egale cu probabilitatile din setul

    sursei, atunci sirul este tipic.

    Altfel spus, daca n este lungimea sirului tipic considerat si in este numarul de

    simboluri ix din sir, atunci ii npn = oricare ar fi i.

    Definitie:O sursa ergodicaeste o sursa care genereaza numai siruri tipice.

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

    14/90

    Observatie: Definitiile stationaritatiisi ergodicitatiide mai sus sunt valabile pentru sursa

    fara memorie. In cazul sursei cu memorie, ele se enunta inlocuind notiunea de simbolcu cea

    de stare(definitia starii este data in subcapitolul de Surse Markov).

    3.3. Surse Markov

    Sursa Markov este un model matematic des folosit in practica pentru a descrie sursele discrete

    de informatie, cu memorie. Exista diverse definitii pentru sursa Markov.

    3.3.1. Definitii si notatii

    Definitia I :Sursa Markoveste o sursa discreta, cu memorie de lungime constanta.

    Definitie:Ordinulsursei Markov este dat de lungimea memoriei.

    Definitie:Stareasursei Markov la un momentul keste data de sirul de simboluri de

    lungime egala cu ordinul sursei, generat anterior.

    Exemplu :Sursa Markov binara de ordinul 2

    Alfabetul : [ ] [ ]1,0=X Probabilitatile de aparitie a simbolurilor sunt probabilitati conditionate, de forma

    ),/( 21 = kkik XXxXp

    )0,0/0(p )1,0/0(p )0,1/0(p )1,1/0(p

    )0,0/1(p )1,0/1(p )0,1/1(p )1,1/1(p

    Multimea starilor [ ] [ ]11100100=S

    Surse ergodice

    Surse stationare

    Surse discrete

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

    15/90

    Multimea starilor are RN , unde Neste dimensiunea alfabetului, iar R este ordinul sursei.

    Definitie:Probabilitatea ca sursa Markov sa fie intr-o anumita stare este egala cu

    probabilitatea de aparitie a sirului de simboluri care constituie starea.

    Definitia II:O sursa Markov se defineste prin urmatoarele marimi:

    Alfabetul simbolurilor: [ ] [ ]NxxxX ,,, 21 K=

    Setul de probabilitati ale simbolurilor: ( )[ ] [ ]N

    pppXP ,,, 21 K= cu =i

    ip 1

    Multimea starilor: [ ] kNk sssS ,,, 21 K=

    Setul de probabilitati ale starilor: ( )[ ] kNk

    qqqSP ,,, 21 K= unde ( )ii spq = si

    =i

    iq 1

    Relatia dintre probabilitatile simbolurilor si probabilitatile starilor este (T. probabilitatiitotale) :

    ( ) ( ) ( )=j

    jjii spsxpxp / ( )=j

    jjii qsxpp /

    Fiecare simbol nou generat constituie, impreuna cu cele anterioare, o noua stare :

    Exemplu : Sursa Markov binara de ordinul 2

    )0,0/1(p )0,0/0,1(p

    Probabilitatea ca sursa sa genereze simbolul 1 cand se afla in starea 0,0 este totuna cu

    probabilitatea ca sursa sa treaca din starea 0,0 in starea 1,0.

    Definitia III: O sursa Markov este o sursa cu memorie la care probabilitatea de aparitie a

    unei stari nu depinde decat de starea anterioara.

    3.3.2. Descrierea surselor Markov prin diagrame de stare

    Exemplu :Sursa binara Markov de ordinul 2

    [ ] [ ] [ ]11100100,,, 4321 == ssssS

    3/1)0,0/0,0()0,0/0( ==pp 3/2)0,0/0,1()0,0/1( ==pp

    3/2)1,0/0,0()1,0/0( ==pp 3/1)1,0/0,1()1,0/1( ==pp

    3/1)0,1/1,0()0,1/0( ==pp 5/2)0,1/1,1()0,1/1( ==pp

    4/1)1,1/1,0()1,1/0( ==pp 4/3)1,1/1,1()1,1/1( ==pp

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

    16/90

    Observatie : Descrierea prin diagrame de stare este utila cand sursa Markov este stationara.

    3.3.3. Descrierea surselor Markov prin matricea de tranzitie siprin vectorul probabilitatilor starilor

    Definitie : Matricea de tranzitieare ca elemente probabilitatile conditionate ale sursei

    Markov.

    =

    kkkk

    k

    NNNN

    N

    ppp

    ppp

    T

    ,2,1,

    ,12,11,1

    unde jip , este probabilitatea ca sursa sa treaca din starea is in starea js .

    Proprietate: suma elementelor de pe orice linie este egala cu 1, de aceea spunem ca Teste o

    matrice stohastica.

    Definitie : Vectorul probabilitatilor starilor este constituit din probabilitatile tuturor

    starilor:

    RN

    qqSP K1=

    Observatie: Matricea de tranzitie este utila in descrierea surselor Markov nestationare

    (probabilitatile starilor variaza in timp, nu si probabilitatile de trecere de la o stare la alta).

    Daca ( )kSP este vectorul probabilitatilor starilor la momentul ksi ( )1kSP acelasi vectorinaintea ultimei tranzitii, atunci:

    ( ) ( )TSPSP kk 1= (conform Teoremei probabilitatii totale)

    1/33/4

    01

    2/3

    2/32/3

    1/4

    1/3 1/3 00

    10

    11

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

    17/90

    Prin tranzitivitate:

    ( ) ( ) ( ) ( ) kkkk TSPTSPTSPSP 0

    2

    21 ==== K

    unde ( )0SP este vectorul probabilitatilor in starea initiala a sursei

    Definitie : Sursa Markov este regulatadaca, atunci cand n , ( )nSP devine constant. Inacest caz, ( )

    nSP se numeste distributie de echilibrusau asimptotica a starilor sursei Markov.

    Exemplu :sursa Markov regulate (binara de ordinul 1).

    ( ) [ ]3/23/10 =SP

    =

    2/12/1

    4/34/1T

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

    18/90

    4. ENTROPIA SURSELOR DISCRETE DE INFORMATIE

    Definitie :Entropiaunei surse discrete de informatie este cantitatea de informatie, medie pe

    simbol, generata de sursa.

    4.1. Entropia sursei fara memorie

    4.1.1.Expresia entropiei

    Entropia unei surse fara memorie se calculeaza cu urmatoarea expresie :

    ( ) )(logi

    i

    i ppXH =

    Justificare: Fie nXXXS ,,,: 21 K un sir tipic generat de sursa. Din numararea simbolurilor

    de acelasi fel rezulta valorile Nnnn ,,, 21 K ( nni

    i = ). Sirul fiind tipic, pentru 1>>n ,

    numarul de aparitii ale unui simbol este aproximativ ii npn . Deci, probabilitatea estimata de

    aparitie a sirului este: ( ) ( )npnpp npppSp K21 21= si, in consecinta, informatia sirului este:

    ( ) ( ) ( )== ii ppnSpSi loglog

    iar entropia ( ) ( )

    )(log ii

    i ppn

    SiXH ==

    Observatie :Aceasta expresia a entropei este valabila si pentru sursele neergodice sau surselenestationare.

    Unitatea de masura pentru entropie: bit/simbol.

    4.1.2. Proprietatile entropiei

    a) Entropia este totdeauna mai mare sau egala cu zero

    b) Continuitate : ( )XH este continua in raport cu variabilelei

    p

    c) Simetrie : ( )XH este simetrica in raport cu variabilele ip

    d) ( )XH este maxima cand simbolurile sursei sunt echiprobabilee) Aditivitate:

    e1) compunerea simbolurilor descreste entropia

    e2) scindarea simbolurilor creste entropia

    Justificarea proprietatii d): Demonstratia se face folosind metoda multiplicatorului lui

    Lagrange

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

    19/90

    4.1.3.Entropia sursei binare

    Fie alfabetul [ ] [ ]21 ,xxX = cu probabilitatile [ ] [ ]ppP = 1

    Entropia ( ) ( ) ( ) ( )ppppXH = 1log1log Pentru 0=p sau 1=p , ( ) simbbitXH /0= Pentru 2/1=p , entropia este maxima ( ) simbbitXH /1=

    4.2. Entropia sursei Markov

    Fie sursa Markov de ordin k, cu alfabetul :

    [ ] [ ]NxxxX ,,, 21 K

    =

    si alfabetul starilor :

    [ ] kNk

    sssS ,,, 21 K=

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

    ( ) ( ) ( )jk

    j

    jk sSHspSH =

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

    ( ) ( ) ( )jii

    jijk sspsspsSH = log

    Proprietate :Entropia sursei Markov este mai mica decat entropia unei surse fara memorie

    care ar genera aceleasi simboluri (dependenta de trecut diminueaza cantitatea medie de

    informatie pe simbol):

    H(X)

    p1/2 1

    1

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

    20/90

    ( ) ( )0SHSH k <

    Justificare:

    Demonstratia se bazeaza pe urmatorul rezultat:

    Inegalitatea fundamentala (lema):

    Fie [ ] [ ]NpppP ,,, 21 K= cu 1=i

    ip si

    [ ] [ ]N

    qqqQ ,,, 21 K= cu 1=i

    iq

    doua seturi de probabilitati.

    Atunci 0log2 i

    i

    i

    ip

    qp

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

    xp

    q

    i

    i = .

    Definitie:Marimeai

    i

    i

    iq

    pp

    2log se numeste entropie relativasaudistanta

    Kullback-Liebler. Entropia relativa este o marime nenegativa; ea ia valoarea zero cand cele

    doua distributii sunt egale (se foloseste pentru a masura similaritatea a doua distributii).

    4.3. Decorelarea sursei Markov

    Definitie : Decorelareaeste 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 DPCM (Differential Pulse Code Modulation)

    4.3.1. Cazul semnalelor 1D

    Fie un semnalul numeric format din urmatoarele esantioane : KK ,,,, 21 nxxx

    Semanalul decorelat se obtine calculand diferenta intre simbolurile consecutive :

    KK ,,,, 1121 nn xxxxx

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

    21/90

    4.3.2. Cazul semnalelor 2D

    Fie imaginea constituita din pixelii :

    KKKKK

    KK

    KK

    KKKKK

    KK

    jijii

    jijii

    jj

    iii

    iii

    iii

    ,1,1,

    ,11,11,1

    ,11,11,1

    Imaginea decorelata este constituita din pixelii diferenta 1,1,1,1, 75,05,075,0 += jijijiji iiid :

    KKKKK

    KK

    KK

    KKKKK

    KK

    jijii

    jijii

    jj

    ddi

    ddi

    iii

    ,1,1,

    ,11,11,1

    ,11,11,1

    4.4. Debit, redundanta, redundanta relativa

    Definitie : Debitul de informatieal unei surse este cantitatea medie de informatie generata

    pe secunda de sursa.

    ( ) ( )

    XHXH

    t = unde este durata unui simbol

    Unitatea de masura pentru debit este bit/sec.

    Definitie : Redundantaunei surse de informatie este:

    ( ) ( ) ( )XHXHXR = max

    Unde ( )XHmax este entropia maxima a sursei (entropia in cazul simbolurilor echiprobabile) si( )XH este entropia sursei.

    Unitatea uzuala de masura este bit/simbol.

    Definitie : Redundantarelativa a unei surse este

    ( ) ( ) ( )

    ( )XHXHXH

    Xmax

    max = ( ) [ ]10X

    Redundanta relativa este adimensionala.

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

    22/90

    4.5. Entropia conjugata a doua surse de informatie

    Fie doua surse de informatie:

    [ ] [ ]NxxxX ,,, 21 K=

    [ ] [ ]N

    pppP ,,, 21 K= cu 1=i

    ip

    si

    [ ] [ ]MyyyY ,,, 21 K= [ ] [ ]MqqqQ ,,, 21 K= cu 1=

    i

    iq

    Definitie : Entropia conjugata(sau compusa) a surselor Xsi Yeste

    ( ) ( ) ( )ji

    i j

    ji yxpyxpYXH ,log,, =

    Observatii:

    a) Entropia conjugata este totdeauna pozitiva

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

    Cazuri particulare :

    1. Daca sursele de informatie sunt independente :

    ( ) ( ) ( )YHXHYXH +=,

    Demonstratia se bazeaza pe definitia v.a. independente: ( ) jiji ypxpyxp =,

    2. Daca sursele sunt identice:

    ( ) ( ) ( )YHXHYXH ==,

    3. Daca sursele sunt dependente statistic:

    ( ) ( ) ( )YHXHYXH +,

    Demonstratia se face folosind inegalitateafundamentala,in cazul seturilor de

    probabilitati ji yxp , si ( ) ji ypxp .

    4.6. Informatia mutuala a doua surse

    Definitie : Informatia mutualaa doua surse Xsi Yeste media informatiilor mutuale a

    perechilor de simboluri ji yx , generate de surse:

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

    23/90

    ( ) ( )( ) ( )

    ji

    ji

    i j

    jiypxp

    yxpyxpYXI

    ,log,, =

    Unitatea de masura pentru ( )YXI , este bit/simbol.

    Cazuri particulare :

    1. Daca Xsi Ysunt independente:

    ( ) 0, =YXI

    Demonstratia se bazeaza pe definitia v.a. independente: ) ( ) )jiji

    ypxpyxp =, .

    2. Daca Xsi Ysunt identice:

    ( ) ( ) ( )YHXHYXI ==,

    3. Daca Xsi Ysunt dependente statistic:

    ( ) ( )XHYXI , si ( ) ( )YHYXI ,

    Proprietati:

    1. ( ) ( ) ( ) ( )YXHYHXHYXI ,, +=

    Justificare: Se calculeaza expresia din stanga, scriindu-i pe ( )XH si ( )YH ca functii

    de probabilitatile ambelor v.a. De exemplu, ( ) ( )=j

    jii yxpxp , , conform Teoremei

    probabilitatii totale.

    2. Informatia mutuala este o marime nenegativa: ( ) 0, YXI .

    Justificare:Rezulta din proprietatea entropiei conjugate ( ) ( ) ( )YHXHYXH +,

    Observatie:Desi informatia mutuala a doua simboluri poate fi si negativa, informatia

    mutuala a doua surse este totdeauna nenegativa.

    4.7. Entropia conditionata a sursei de informatie

    Definitie : Entropia sursei X, conditionata de sursa Y, este cantitatea medie de

    incertitudine care ramane asupra lui X, cand se cunoaste Y.

    ( ) ( ) ji

    i j

    ji yxpyxpYXH = log,

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

    24/90

    Observatie:ji

    i

    jij yxpyxpyXH = log este incertitudinea medie asupra lui X, cand

    Ya generat simbolulj

    y . In medie, aceasta incertitudinea este

    ( ) ( )=j

    jj yXHypYXH .

    Cazuri particulare:

    1. Daca Xsi Ysunt independente:

    ( ) ( )XHYXH =

    Demonstratia se bazeaza pe definitia v.a. independente: ( ) jiji

    ypxpyxp =, .

    2. Daca Xsi Ysunt identice:

    ( ) 0=YXH

    3. Daca Xsi Ysunt dependente statistic:

    ( ) ( )XHYXH /

    4.8. Relatii intre entropii (Diagrame Venn)

    4.8.1. Reprezentarea entropiilor prin Diagrame Venn:

    Sursele X si Y sunt independent

    Sursele X si Y sunt identice

    H(X) H(Y)

    H(X)

    H(Y)

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

    25/90

    Sursele X si Y sunt dependente statistic

    4.8.2. Relatii intre entropii

    ( ) ( ) ( )XHXYHYXH +=, si ( ) ( ) ( )YHYXHYXH +=,

    ( ) ( ) ( ) ( ) ( )YHXHYXHXHYXH + ,/

    4.9. Generalizare (cazul a n surse)

    Diagrama Venn pentru 3 surse de informatie :

    a) ( ) ( ) ( ) ( )YXZHXYHXHZYXH ,,, ++= (se deduce din Diagrama Venn)

    unde ( ) ( ) jik

    i j k

    kji yxzpzyxpYXZH ,log,,, =

    b) ( ) ( ) ( )ZHXZHYXZH ,0

    Pentru n surse, prin analogie cu relatiile anterioare, putem scrie:

    a) ( ) ( ) ( ) ( )111211 ,,,, +++= nnn XXXHXXHXHXXH KKK

    H(X/Y) H(Y/X)

    H(Y/X,Z)H(X/Y,Z)

    H(Z/X,Y)

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

    26/90

    Daca sursele sunt independente, atunci: ( ) ( )=i

    in XHXXH ,,1 K

    b) ( ) ( ) ( ) ( )nnnnnn

    XHXXHXXXHXXXH 12111 ,,,,0 KKK

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

    27/90

    5. CANALE DE TRANSMITERE A INFORMATIEI

    Definitie : Un canal de transmitere a informatieieste 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.

    5.1. Clasificari ale canalelor

    a) Dupa domeniul de valori al v.a. X si Yde 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

    5.2. 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 RC A N A LS U

    [X] [Y]

    P

    Mod DeM

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

    28/90

    5.2.1. Marimi caracteristice

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

    [ ] [ ]NxxX ,,1 K=

    [ ] [ ]NppP ,,1 K=

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

    utilizator):

    [ ] [ ]M

    yyY ,,1 K=

    [ ] [ ]MqqQ ,,1 K=

    Din cauza perturbatiilor de pe canal, Xsi Ysunt, in general, diferite.

    Spatiul produs:

    [ ]

    ( ) ( ) ( )( ) ( ) ( )

    ( ) ( ) ( )

    =

    MNNN

    M

    M

    yxyxyx

    yxyxyx

    yxyxyx

    YX

    ,,,

    ,,,

    ,,,

    ,

    21

    22212

    12111

    K

    KKKK

    K

    K

    Matricea probabilitatilor corespunzatoare spatiului produs:

    ( )[ ]

    ( ) ( ) ( )

    ( ) ( ) ( )

    ( ) ( ) ( )

    =

    MNNN

    M

    M

    yxpyxpyxp

    yxpyxpyxp

    yxpyxpyxp

    YXP

    ,,,

    ,,,

    ,,,

    ,

    21

    22212

    12111

    K

    KKKK

    K

    K

    Matricea de zgomot a canalului:

    ( )[ ]

    ( ) ( ) ( )( ) ( ) ( )

    ( ) ( ) ( )

    =

    NMNN

    M

    M

    xypxypxyp

    xypxypxyp

    xypxypxyp

    XYP

    K

    KKKK

    K

    K

    21

    22221

    11211

    Matricea de zgomot este stohastica:

    1=i

    jixyp (suma elementelor de pe orice linie este 1).

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

    29/90

    Canalele studiate sunt stationare, deci ./ ctxyp ij = in timp.

    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 / .

    5.2.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: ( ) ( ) ( )ji

    i 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.

    ( )11 /xyp

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

    30/90

    Cazuri particulare :

    a) Canale cu perturbatii infinite (Xsi Ysunt independente)

    ( ) ( ) ( )YHXHYXH +=,

    ( ) ( )XHYXH = (la iesire, nu aflam nimic despre X; incertitudinea asupra lui Xramane lafel de mare)

    ( ) ( )YHXYH = (toata informatia de la iesire este eronata)

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

    b) Canale fara perturbatii (sursele Xsi Ysunt identice)

    ( ) ( ) ( )YHXHYXH ==,

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

    ( ) 0=XYH (nu exista erori la iesirea din canal)

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

    c) Canale cu perturbatii finite (Xsi Ysunt diferite, dar dependente statistic)

    ( ) ( ) ( )YHXHYXH +

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

    31/90

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

    aceste probabilitati pot fi controlate, intr-otransmisie printr-un canal cu perturbatii.

    Unitatea de masura pentru capacitate este bit/simbol.

    Definitie : Redundantacanalului este : ( )YXICR ,= [bit/simbol].

    Definitie : Redundanta relativaa canalului este :( )

    [ ]1,0,

    1 =C

    YXIC .

    Definitie : Randamentulsau eficientacanalului arata cat de mica este cantitatea medie de

    informatie transmisa prin canal, in raport cu capacitatea canalului.

    ( )[ ]1,0

    ,=

    C

    YXIC

    Observatie:redundanta si radamentul sunt marimi complementare: CC = 1

    Definitie :Debitulde informatie prin canal este : ( ) ( )

    YXIYXI

    t

    ,, = [bit/sec], unde este

    durata unui simbol.

    Observatie:Debitul maximde informatie prin canal este:

    CCt = .

    Proprietati :

    a) Capacitatea canalului este o marime nenegativa :

    0C (deoarece ( ) 0, YXI )

    b) ( )XHC (deoarece ( ) ( )XHYXI , )

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

    5.4. Calculul capacitatii canalului discret

    Date initiale :probabilitatile matricii de zgomot ( )[ ]XYP / .

    Etape:

    1) AplicandMetoda multiplicatorului lui Lagrage, se calculeaza probabilitatilemax

    ip ,

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

    obtinute.

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

    32/90

    Rezolvare:

    Se construieste functia:

    ( ) ( )

    +=

    1/ iipXYHYH

    Pentru a pune in evidenta probabilitatileip in expresia lui ( )YH , probabilitatile [ ]Q se scriu:

    ( ) ( ) ( ) ( ) i

    i

    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 cui

    p :

    ( ) ( ) ( )

    ( ) ( )

    =

    =

    j

    ijij

    i

    j i

    ijiij

    i

    xypxyp

    p

    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

    probabilitatilemax

    ip , care maximizeaza si, deci, informatia transmisa prin canal:

    ( ) ( ) ( ) 0/log/log/log1

    =++ jijij

    j

    jij xypxypqxype Nipentru ,1=

    Grupand termenii cu sume si constantele, se obtin ecuatiile:

    ( ) ctq

    xypxyp

    j j

    ij

    ij =/

    log/ Nipentru ,1=

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

    33/90

    Completand aceste ecuatii cu:

    ( )=i

    iijj pxypq / Mjpentru ,1=

    si

    =iip 1

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

    obtine probabilitatile maxi

    p si maxjq , 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 analitica,

    capacitatea se calculeaza cu metode numerice (algoritmullui 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

    5.5. Modele de canale discrete

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

    se poate calcula analitic.

    5.5.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:

    ( )

    =

    61

    21

    31

    2

    1

    6

    1

    3

    1

    /XYP

    Proprietati:

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

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

    34/90

    ( ) ) )

    ( ) ( ) ( )

    ( ) ( ) ( ) ( ) ctxpctxypxypxp

    xypxpxyp

    xypyxpXYH

    i

    i

    j

    ijij

    i

    i

    ij

    ji

    iij

    ij

    ji

    ji

    ===

    ==

    ==

    /log/

    /log/

    /log,/

    ,

    ,

    b) Capacitatea canalului este:

    [ ]( )

    [ ]( ) ( )[ ]

    [ ]( ) ( )XYHYHXYHYHYXIC

    PPP/max/max,max ===

    5.5.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

    Proprietate:

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

    sunt echiprobabile:

    ( ) ( ) ( ) ( ) .1

    /1

    / ctNxypNxpxypyp iij

    i

    iijj ===

    5.5.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

    Proprietati:

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

    este:

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

    35/90

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

    5.5.4. Canalul slab simetric

    Definitie: Canalul slab simetric este uniform fata de intrare si are suma probabilitatilor de pefiecare coloana constanta.

    Exemplu:

    ( )

    =

    6

    1

    2

    1

    3

    12

    1

    6

    1

    3

    1

    /XYP

    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 ===

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

    este:

    ( )XYHMC /log =

    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.

    5.6. Exemple de canale discrete

    5.6.1. Canalul binar simetric

    Matrice de zgomot:

    ( )

    =

    pp

    ppXYP

    1

    1/

    peste probabilitatea de transmisie eronata.

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

    36/90

    Reprezentare grafica:

    0 0

    1 1

    Calculul capacitatii:

    ( ) ( )XYHXYHC /1/2log ==

    unde

    ( ) ( ) ( )

    ( ) ( )pppp

    xypxypXYH

    j

    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=

    p

    1-p

    1-p

    p

    H(X), C

    p1/2 1

    1

    C

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

    37/90

    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)

    Matricea de zgomot: ( )

    =

    2/12/1

    2/12/1/XYP

    Capacitatea : simbolbitC /0=

    5.6.2. Canalul binar cu erori si anulari

    Matrice de zgomot:

    ( )

    =

    qqpp

    qpqpXYP

    1

    1/ Canalul este uniform doar fata de intrare.

    peste probabilitatea de transmisie eronata.

    qeste probabilitatea ca simbolul receptionat sa fie anulat.

    Reprezentare grafica:

    0=X 0=Y

    aY=

    1=X 1=Y

    Calculul capacitatii:

    Canalul este uniform fata de intrare:

    [ ]( )[ ] ( )XYHYHC

    P/max =

    1-p-q

    q

    p

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

    38/90

    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 , ( ) K==aYp si ( ) K== 1Yp

    ca functii de x

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

    - se rezolva ecuatia( )

    0=

    x

    YH

    - cu solutia ecuatiei de mai sus, se obtine [ ] ( )[ ]YHPmax

    Exercitiu:

    Calculul capacitatii canalului binar cu erori si anulari.

    Raspuns: ( ) ( ) ( ) ( )qpqpppqqqC ++= 1log1log1log11 .

    Observatie: Capacitatea canalului devine zero pentru2

    1 qp

    = (se rezolva ecuatia

    0=

    p

    C

    si se obtine solutia 2

    1 q

    p

    = )

    5.6.3. Canalul binar cu anulari

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

    Matricea de zgomot:

    ( )

    = qq

    qq

    XYP 10

    01

    /

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

    39/90

    Reprezentarea grafica:

    0=X 0=Y

    aY=

    1=X 1=Y

    Capacitatea: qC = 1

    1-q

    1-q

    q

    q

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

    40/90

    6. SURSE DE INFORMATIE SI CANALE CONTINUE

    6.1. Entropia sursei de informatie continue

    Definitie : Sursa continua de informatieeste un mecanism de generare a unui sir de

    v.a.continue KK ,,,, 11 + kkk XXX , unde keste, de cele mai multe ori, un indice de timp.

    kX sunt v.a. continue, care iau valori in R .

    kX poate fi si complexa (de exemplu, cand prin Tranformare Fourier, s-a trecut in domeniul

    frecventelor).

    V. a. Continue kX sunt caracterizate de o densitatea de probabilitate )(xf

    Definitie : Entropia unei surse de informatie continue este:

    ( ) ( ) ( )= R dxxfxfXH2log

    Observatie : ( )XH poate fi si negativa pentru ca )(xf poate fi > 1 .

    Exemplu:v.a. Xcu distributie uniforma pe intervalul [ ]2/10

    ( ) [ ]

    =restin

    xxf

    _0

    2/102

    ( ) 122log2

    2/1

    0

    2/1

    02

    === dxdxXH

    6.1.1. Semnificatia entropiei unei surse continue

    Faptul ca ( )XH poate fi si negativa pune un semn de intrebare asupra semnificatiei acesteimarimi, in cazul surselor de informatie continue.

    Fie un semnal continuu in amplitudine, modelat printr-un sir de v.a. continue kX cu

    distributia ( )xf . Altfel spus, fie o sursa de informatie continua, pe care o notam cu X. Pp.

    pentru simplitate ca realizarile particulare ale lui kX sunt cuprinse in intervalul [ ]Nq0 ,unde q este un numar pozitiv, iar Nun numar natural.

    Prin cuantizare cu cuanta q , toate valorile semnalului cuprinse intr-un anumit interval de

    latime q , devin egale cu o valoare fixa (semnalul continuu este discretizat) :

    daca ( )[ ]nqqnxt 1 atunci nqxx nt = (cu tx s-a notat realizarea particulara a lui

    tX la momentul t).

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

    41/90

    Semnalul discret poate fi modelat de un sir de v.a. discrete ( )qkX , altfel spus, sursa de

    informatie continua devine o sursa discreta ( )qX .

    V.a.( )qkX iau valori in multimea [ ] [ ]NxxxX ,,, 21 K= unde nqxn = .

    Multimea probabilitatilor sursei discrete este constituita din urmatoarele valori:

    ( ) ( )( )

    ( )nqqfdxxfxpnq

    qn

    n = 1

    Entropia sursei discrete este:

    ( ) ( ) ( ) ( ) ( )( )nqqfnqqfxpxpXHN

    n

    n

    N

    n

    n

    q ==

    ==11

    loglog

    Prelucrand relatia entropiei, obtinem :

    ( ) ( ) ( ) ( )( ) = =

    =N

    n

    N

    n

    q nqfnqqfnqqfqXH1 1

    loglog

    La limita, cand cuanta q tinde catre zero :

    ( ) ( )xfnqf si dxq

    si relatia entropieidevine:

    ( ) ( ) ( ) ( ) ( )XHqdxxfxfdxxfqXH q +== logloglog

    Concluzie:

    a) ( )qXH este entropia unei surse de informatie discrete, deci are semnificatia unei informatiimedii. La limita, cand 0q , sursa devine continua si ( )( )q

    qXH

    0lim

    este informtia medie a

    sursei continue, ceea ce nu este acelasi lucru cu ( )XH din cauza termenului qlog . Deci,entropia sursei continue nu are semnificatia unei cantitati medii de informatie.

    b) La limita, termenul qlog tinde catre infinit, de aceea, spunem ca informatia medie asursei continue este infinita(in timp ce entropia ( )XH este de cele mai multe ori o marimefinita).

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

    42/90

    6.1.2. Inegalitatea fundamentala in cazul distributiilor continue

    Fie ( )xf si ( )xg doua densitati de probabilitate.Se poate arata, cu acelasi demers logic ca in cazul distributiilor discrete, ca:

    ( ) ( )( )

    R xf

    xgxf 0log

    ( ) ( )

    ( )R

    xg

    xfxf log se numeste entropie relativasaudistanta Kullback-Leiblerin cazul

    distributiilor continue. Este o marime nenegativa; ia valoarea zero cand cele doua distributiisunt indentice.

    6.1.3. Cazuri de entropie maxima

    Maximul absolut al entropiei surselor continue este infinit. Ne intereseaza maximul inanumite conditii restrictive.

    a) V.a. iau valori intr-un domeniu finit [ ]ba

    Se cauta maximul lui ( ) ( ) ( )=b

    a

    dxxfxfXH 2log cu restrictia ( ) =b

    a

    dxxf 1

    Indicatie:Se foloseste metoda multiplicatorului lui Lagrange; se construieste functia

    ( ) ( )

    +=

    b

    a

    dxxfxH 1 si se deriveaza in raport cu f .

    Rezultat:distributia care maximizeaza entropia este distributia uniforma.

    ( ) ( ) [ ]

    =restin

    baxabxf

    _0

    /1

    ( ) ( )abXH = logmax

    b) V.a. ia numai valori pozitive si are media statistica m

    Se cauta maximul lui ( ) ( ) ( )

    =0

    2log dxxfxfXH cu restrictiile ( )

    =0

    1dxxf si media

    statistica m .

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

    43/90

    Indicatie:Se foloseste metoda multiplicatorului lui Lagrange; se construieste functia:

    ( ) ( ) ( )

    +

    +=

    00

    1 mdxxxfdxxfxH si se deriveaza in raport cu f .

    Rezultat:distributia care maximizeaza entropia este distributia exponentiala.

    ( )

    =

    restin

    xmexf

    mx

    _0

    0

    ( )e

    mmXH

    loglogmax +=

    c)V.a. ia numai valori pe R si are are media statistica 0 si varianta 2 .

    Se cauta maximul lui ( ) ( ) ( )

    = dxxfxfXH 2log cu restrictiile ( )

    = 1dxxf , media

    statistica 0=m si varianta 2 .

    Indicatie:Se foloseste metoda multiplicatorului lui Lagrange; se construieste functia:

    ( ) ( ) ( ) ( )

    +

    +

    +=

    0

    22

    00

    1 dxxfxdxxxfdxxfxH si se deriveaza in raport cu

    f .

    Rezultat:distributia care maximizeaza entropia este distributia gaussiana:

    ( ) ( )eXH 2logmax

    =

    6.1.4. Variatia entropiei cu schimbarea spatiului de reprezentare a semnalului

    Fie un semnal continuu, modelat printr-un sir de v.a. continueN

    XX ,,1 K , dependente

    statistic (cazul majoritatii semnalelor intalnite in practica), unde, de multe ori, indicele este un

    indice de timp . Altfel spus, fie o sursa de informatie continua, cu memorie.

    ( )

    2

    22 2/xxxf

    =

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

    44/90

    Printr-o transformare F (de exemplu, Fourier), se trece din spatiul N-dimensional al

    esantioanelor temporale, intr-un alt spatiu spatiul N-dimensional (al esantioanelor frecventiale,

    daca am aplicat Transformarea Fourier). In acest spatiu, semnalul este reprezentat prin sirul de

    v.a. : N ,,1 K .

    [ ]N ,,1 K =F( [ ]NXX ,,1 K )

    Pp. ca densitatile de probabiliate conjugate ale celor doua siruri de v.a. sunt :

    ( )NXXf ,,1 K in spatiul esantioanelor temporale

    si

    ( )NVVg ,,1 K in spatiul esantioanelor frecventiale.

    Probabilitatile ca sirurile sa aiba realizari particulare foarte apropiate de sirurile de valori :

    Nxx ,,1 K si N ,,1 K

    sunt

    ( ) NN

    dxdxxxf KK 11 ,, si ( ) NN ddg KK 11 ,,

    Variatiile dXdxdx N =K1 determina variatiile dVdd N = K1 .

    Se poate arata ca

    =

    X

    VJ

    dX

    dVunde cu

    X

    VJ s-a notat jacobianul transformarii:

    =

    N

    NN

    N

    dx

    d

    dx

    d

    dx

    d

    dx

    d

    X

    VJ

    K

    KKK

    K

    1

    1

    11

    1

    Cum transformarea F , face numai o schimbare de coordonate (nu de semnal), trebuie

    satisfacuta relatia:

    ( ) ( ) NNNN ddgdxdxxxf = KKKK 1111 ,,,,

    Impartind relatia prinNdxdx K1 , se obtine:

    ( ) ( )

    =

    X

    VJgxxf NN ,,,, 11 KK

    ceea ce conduce la urmatoarea relatie intre entropiile semnalului inainte si dupa transformare:

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

    45/90

    ( ) ( ) ( )

    ( ) ( )

    ( ) ( ) ( )

    ( ) ( )VHdxdxX

    UJxxf

    ddggdxdxX

    U

    Jxxf

    dxdxX

    UJgxxf

    dxdxxxfxxfXH

    N

    X

    N

    NNV

    NNX

    N

    NN

    X

    N

    NN

    X

    N

    +

    =

    =

    =

    =

    =

    ==

    KK

    KKKKK

    KKK

    KKK

    11

    11111

    111

    111

    log,,

    ,,log,,log,,

    ,,log,,

    ,,log,,

    ceea ce arata ca, in general, entropia semnalului se schimba atunci cand se aplica o

    transformare.

    Se poate arata ca, in cazul unei transformari ortogonale (Fourier, Cosinus, etc.) :

    1=

    X

    VJ

    si atunci

    ( ) ( )VHXH = deoarece ( ) 1,, 11 =V

    NN dxdxxxf KK .

    Concluzie:O transformare ortogonala nu schimba entropia unui semnal.

    6.2. Canale continue de transmisie a informatiei

    Printr-un canal continuu, trec semnale continue atat in timp cat si in amplitudine. De aceea,

    intrarea si iesirea canalului sunt modelate prin doua surse continue de informatie.

    In acest capitol, se studiaza canalele continue fara memorie (esantioanele semnalului continuu

    in aplitudine sunt independente) si stationare (distributia valorilor esantioanelor nu se schimba

    in timp).

    Fie Xsursa continua de la intrare, cu densitatea de probabilitate ( )xfX Ysursa continua de la iesire, cu densitatea de probabilitate ( )yfY

    6.2.1. Informatia mutuala in canalele continue

    Pentru a deduce informatia medie transmisa prin canalul continuu, vom porni de la rezultatul

    obtinut pentru canalul discret si, prin trecere la limita, vom obtine informatia mutuala in

    canalul continuu.

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

    46/90

    Pp ca semnalul de la intrare este esantionat cu frecventa W2 , unde Weste frecventa maxima

    din spectrul semnalului (criteriul lui Nyquist). Aceasta ipoteza nu reduce generalitatea

    rezultatelor urmatoare deoarece un semnal continuu poate fi reconstruit identic din

    esantioanele sale daca acestea au o frecventa W2 .

    Pp., de asemenea, ca semnalul este cuantizat cu cuanta q . Rezultatul este un semnal discret

    care poate fi modelat printr-o sursa de informatie discreta avand alfabetul:

    [ ] [ ]NxxxX ,,, 21 K= unde nqxn =

    si probabilitatile :

    [ ] ( ) ( ) ( )[ ]NxpxpxpP ,,, 21 K= unde ( ) ( )qxfxp nXn

    La iesirea din canal, prin esantionare (sincrona cu intrarea) si cuantizare cu cuanta q , se

    obtine un semnal discret care poate fi modelat de o sursa de informatie discreta avand

    alfabetul:

    [ ] [ ]M

    yyyY ,,, 21 K= unde mqym =

    si probabilitatile:

    [ ] ( ) ( ) ( )[ ]N

    ypypypQ ,,, 21 K= unde ( ) ( )qyfyp mYm

    Informatia medie pe esantion transmisa prin canal este (cf. rezultatului obtinut la canalele

    discrete):

    ( ) ( ) ( ) ( )

    =

    ==

    i j YX

    YX

    YX

    i j ji

    ji

    ji

    qyqfxf

    qyxfqyxf

    ypxp

    yxp

    yxpYXI

    )()(

    ),(log),(

    ,

    log,,

    2

    ,2

    ,

    unde ( )yxf YX ,, este densitatea de probabilitate conjugate a v.a. x si y .

    La limita, cand 0q , suma dubla se transforma intr-o integralax

    ( ) ( ) ( )

    ( ) ( )dxdy

    yfxf

    yxfyxfYXI

    YX

    YX

    YX =,

    log,,,

    ,

    Prelucrand integrala dubla, se ajunge la o relatie similara cazului canalelor discrete:

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

    47/90

    ( ) ( ) ( ) ( ) ( )

    ( )

    ( ) ( ) ( ) ( )

    ( ) ( ) ( ) ( ) ( ) ( )XYHYHdxdyxyfyxfdyyfyf

    dxdyxyfyxfdydxyxfyf

    dxdyyxf

    xfyxfdxdyyfyxfYXI

    YXYXYY

    YXYXYXY

    YX

    X

    YXYYX

    //log,log

    /log,),(log

    ,log,log,,

    ,,

    ,,,

    ,

    ,,

    =+=

    =+=

    ==

    unde, prin analogie cu cazul discret, se defineste eroarea medie prin canalul continuu:

    ( ) ( ) ( )dxdyxyfyxfXYHYXYX = /log,/ ,,

    Observatie: Spre deosebire de entropie, care isi pierde semnificatia la trecerea de la discret la

    continuu, ( )YXI , isi pastreaza semnificatia de cantitatea medie de informatiepe esantion.

    Pe durata D a semnalului, daca esantioanele de semnal sunt independente, se transmite o

    cantitate de informatie egala cu ( )YXIWD ,2 , unde WD 2 este numarul total deesantioane transmise.

    6.2.2. Proprietatile informatiei mutuale in canalele continue

    a) Informatia mutuala este o marime nenegativa:

    ( ) 0, YXI

    Justificare:

    Ne bazam pe inegalitatea fundamentala, in cazul continuu. Considerand densitatile de

    probabilitate ( )yxf YX ,, si ( ) ( )yfxf YX , se poate scrie urmatoarea inegalitate:

    ( ) ( ) ( ) ( )

    ( )0

    ,log,,

    ,

    , = dxdyyxfyfxf

    yxfYXIYX

    YX

    YX

    b) Informatia mutuala este, in general, o marime finita.

    c)Relatia ( ) ( )XHYXI , din cazul discret, nu mai este valabila, deoarece entropia incontinuu nu mai are aceeasi semnificatie ca in discret (in unele cazuri, entropia poate fi chiar

    negativa).

    d) ( )YXI , este invarianta la schimbarea coordonatelor

    Pp. ca esabtioanele semnalelor de la intrarea si iesire din canal, sunt transformate in

    esantioane de frecventa, prin aplicarea Transformarii Fourier:

    UX F si VY F

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

    48/90

    Se poate demonstra ca:

    ( ) ( )VUIYXI ,, =

    6.2.3. Capacitatea canalelor continue

    Definitie : Capacitatea canalului continuueste data de maximul cantitatii de informatie

    care poate fi transmisa prin canal in unitatea de timp ( .)sec1=D

    ( )( )[ ]

    ( )( ) ( )[ ]XYHYHWYXIWC

    xfxf XX

    /max2,2max ==

    Pentru calculul capacitatii, se fac urmatoarele ipoteze:

    a) Pp. ca avem urmatoarele limitari de putere pentru semnale si zgomotul din canal :

    XP este puterea semnalului la intrarea in canal

    YP este puterea semnalului la iesirea din canal

    N este puterea zgomotului din canal

    b) Pp. ca zgomotul este aditiv si independent de semnalulX, transmis prin canal. Se poate

    demostra ca, in acest caz :

    NPPXY

    +=

    c) Pentru fiecare valoare particulara a lui, 0xX = , incertitudinea medie asupra iesirii este data

    numai de zgomot. Prin cuantizarea zgomotului cu cuanta q , numarul de nivele pe care

    zgomotul le poate lua este:

    q

    NK=

    Daca zgomotul este stationar si are o distributie uniforma, atunci nivelele de cuantizare sunt

    echiprobabile, iar entropia conditionata este egala cu:

    ( )q

    NKxXYH loglog/ 0 ===

    Daca, in plus, canalul este simetric in raport cu valorile luiX, atunci eroarea medie pentru

    toate valorile lui Xare expresia de mai sus. Deci, entropia conditionata nu depinde de

    distributia lui X, iar capacitatea devine:

    ( )( )

    =

    q

    NYHWC

    xfX

    logmax2

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

    49/90

    Prin cuantizarea semnalului de la iesire cu cuanta q , se obtin m nivele diferite:

    q

    Pm

    y=

    Entropia la iesire isi atinge maximul cand nivelele sunt echiprobabile :

    ( )( )

    q

    PYH

    y

    xfX

    logmax =

    Deci, capacitatea canalului este:

    +=

    =

    N

    PW

    N

    PWC x

    y1loglog2

    Prin trecere la limita, pentru 0q , din relatia anterioara se obtine capacitatea canaluluicontinuu :

    +=

    N

    PWC x1log

    ceea ce arata ca, in cazul canalului continuu, capacitatea creste cu banda si cu puterea

    semnalului de la intrare si descreste cu puterea zgomotului.

    Daca zgomotul de pe canal este alb si de densitate spectrala de putere 0N , atunci 0WNN= .

    si:

    +=

    0

    1logWN

    PWC x

    Reprezentarea grafica a acestei relatii, arata o curba a capacitatii tinzand asimptotic spre:

    00

    1loglimN

    P

    WN

    PWC xx

    W=

    +=

    Concluzie:Cresterea largimii de banda peste o anumita valoare nu mai este rationala deoarece

    capacitatea canalului nu mai creste decat foarte putin.

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

    50/90

    W

    C

    (Px/N0) loge

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

    51/90

    7. CODAREA DE SURSA

    Locul codarii de sursa intr-o schema de transmisiune a datelor :

    Rolul codarii de sursa :

    - adaptarea slfabetului sursei la alfabetul canalului

    - adapatarea statistica (simboluri echiprobabile pentru alfabetul de canal)

    Observatii :

    - codarea de sursa priveste sursele discrete de informatie

    - codarea de sursa nu rezolva problema erorilor cauzate de perturbatii

    - prin codare, sursa de informatie, numita si sursa primara, este transformata intr-o

    noua sursa de informatie, numita sursa secundara, care debiteaza informatie pe

    canal.

    Doua exemple de codare :

    Fie o sursa de informatie primara care genereaza simboluri dintr-un alfabet :

    [ ] [ ]4321 ,,, xxxxX = cu probabilitatile [ ]

    =81,

    81,

    41,

    21P

    Simbolurile trebuie transmise pe un canal binar cu alfabetul [ ]1,0 . De aceea, ele trebuietranscrise in binar, inainte de transmisie. Transcrierea in binar - codarea- se poate face in

    multe feluri. De exemplu:

    1) 001 x

    102 x

    013 x

    114

    x

    2) 01 x

    012 x

    0113 x

    1114 x

    S CoS C A N A L UDecS

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

    52/90

    Definitie: Codareaeste operatia prin care fiecare simbol al sursei primare este inlocuit

    printr-o succesiune de simboluri ale alfabetului canalului. Decodareaeste operatia inversa

    codarii.

    Definitie: Cuvantul de cod este succesiunea finita de simboluri din alfabetul canalului, cu

    care este inlocuit un simbol al sursei primare

    Definitie: Coduleste totalitatea cuvintelor de cod folosite in codarea unei surse.

    Definitie: Lungimea unui cuvant de codeste egala cu numarul de simboluri din alfabetul

    canalului, care constituie cuvantul de cod.

    Observatii:

    - Codarea stabileste o corespondenta biunivoca intre simbolurile sursei primare si

    cuvintele codului

    - O succesiune de simboluri ale alfabetului canalului, care nu corespunde niciunui

    simbol al sursei, se numeste cuvant fara sens. Prin analogie, un cuvant de cod se

    mai numeste si cuvant cu sens.

    Exemplele de mai sus cuprind un cod de lungime fixa (exemplul 1), care are toate cuvintele

    de aceeasi lungime, si un cod de lungime variabila (exemplul 2), care are cuvinte de lungime

    variabila. In acest caz, se defineste notiunea de lungime medie a cuvinelor de cod.

    Definitie: Lungime mediea cuvintelor de cod se calculeaza cu expresia :

    =

    =N

    i

    iilpl

    1

    unde cui

    l s-a notat lungimea cuvintelor, iar cui

    p , probabilitatile simbolurilori

    x .

    Exemplu: 7,18

    143

    8

    13

    8

    12

    4

    11

    2

    1=+++=l

    Observatii:

    - lungimea medie a cuvintelor de cod se numeste, pe scurt, lungime a codului

    - la codurile formate din cuvinte de lungime fixa, lungimea codului este egala cu

    lungimea unui cuvant de cod ( )llli == .

    De cele mai multe ori, prin codarea cu cuvinte de lungime variabila, se realizeaza o compresie

    a datelor (reducere a volumului de date).

    Definitie: Raportul de compresieobtinut prin codare cu un cod de lungime variabila l se

    calculeaza cu expresia :

    l

    lR=

    unde cu l s-a notat lungimea unui cod de lungime fixa, obtinut cu acelasi alfabet al canalului.

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

    53/90

    Exemplu: 15,17,1

    2=R (compresia care se obtine in cazul sursei din exemplul de mai sus)

    Definitie: Rata de compresie este inversul raportului de compresie :

    Rrata

    1=

    7.1. Clasificarea codurilor de sursa

    CODURI reversibile de lungime variabila unic decodabile instantanee

    neinstantanee

    nu sunt unic decodabile

    de lungime fixa

    ireversibile

    7.1.1. Coduri ireversibile si coduri reversibile

    Exemplu :

    1) Cod binar ireversibil (la decodare, codul lui 1x nu poate fi distins de cel al lui 2x ; la fel

    pentru 3x si 4x )

    01 x

    02 x

    13 x

    14 x

    2) Cod binar reversibil

    001 x

    102 x 013 x

    114 x

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

    54/90

    7.1.2.Coduri unic decodabile si coduri care nu sunt unic decodabile

    Exemplu :

    1) Cod care nu este unic decodabil :

    01 x

    012 x

    113 x

    0113x

    La decodare, grupul 011 poate fi interpretat fie ca simbolul 4x , fie ca grupul de simboluri

    13xx .

    2) Cod unic decodabil

    01 x

    012 x

    0113x

    01114x

    Orice cuvant de cod poate fi decodat intr-un singur simbol.

    7.1.3.Coduri neinstanee si coduri instantanee

    Exemplu :

    1) Cod neinstantaneu :

    01 x

    012 x

    0113x

    01114x

    Trebuie asteptat primul simbol al urmatorului cuvat de cod pentru a face decodarea cuvantului

    receptionat (acest cod se mai numeste si cod cu separator).

    2) Cod instantaneu

    01 x

    012 x

    0113x

    1114x

    Decodarea se poate face la primirea ultimului simbol al cuvantului de cod.

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

    55/90

    Observatie:

    - codurile instantanee sunt cele mai utilizate in practica.

    7.2. Coduri instantanee sau ireductibile

    Definitie : Fie cuvantul de cod C, constituit din n simboluri ale alfabetului de canal :

    [ ]nccC K1=

    Sirul format din primele ksimboluri, se numeste prefix al cuvantului.

    Teorema : Conditia necesara si suficienta ca un cod sa fie instantaneu este ca niciun cuvant sa

    nu fie prefix al altui cuvant mai lung.

    Observatii:

    - spunem despre un cod instantaneu ca are proprietatea de prefix.

    - codurile instantanee se mai numesc si ireductibile.

    7.3. Inegalitatea Kraft-McMillan

    Teorema: Fie sursa primara de informatie cu alfabetul :

    [ ] [ ]NxxX ,,1 K=

    si alfabetul de canal [ ] [ ]DccC ,,1 K= , cu simbolurile caruia se vor forma cuvinte de codpentru sursa primara. O conditie necesara si suficienta pentru a construi un cod ireductibil

    (instantaneu) cu cuvinte de lungime Nll ,,1 K este :

    11

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

    56/90

    Daca ( )XH este entropia sursei, atunci fiecare simbol dc poarta in medie o cantitate deinformatie:

    ( )l

    XH

    Aceasta cantitate, nu poate fi mai mare decat entropia maxima a sursei secundare

    ( ) DCH 2max log= :

    ( )D

    l

    XH2log

    Deci, limita inferioara pentru lungimea medie a oricarui cod este:

    ( )D

    XHl

    2

    minlog

    =

    Observatii:

    - daca codarea se face cu alfabet binar, atunci limita inferioara pentru l este chiar

    entropia sursei primare ( )XH - rezultatele acestei sectiuni sunt valabile pentru toate tipurile de coduri, deci si

    coduri ireductibile (instantanee)

    - aceasta relatie poate fi interpretata si ca o a doua definitie a entropiei

    Definitie : Entropiaunei surse este egala cu lungimea medie a unui cod binar minim cu care

    sursa poate fi codata (nu totdeauna acest cod exista).

    7.5 . Coduri absolut optimale

    In practica, ne intereseaza codurile cu l cat mai mic.

    Definitie: Codurile care au( )D

    XHll

    logmin == se numesc coduri absolut optimale.

    Conform Sectiunii 7.4, cantitatea medie de informatie transmisa fiecarui simbol de canal prin

    codare, altfel spus entropia sursei secundara ( )CH , este invers proportionala cu l :

    ( ) ( )l

    XHCH =

    Aceasta relatie arata ca l isi atinge minimul cand ( )CH este maxim, adica atunci cand, princodare, simbolurile dc ajung sa fie transmise echiprobabil:

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

    57/90

    ( ) ( )D

    cpcp D1

    1 ===K

    Considerand ca nu exista dependenta statistica intre simbolurile dc , care intra in componenta

    cuvintelor de cod, rezulta urmatoarele probabilitati pentru cuvintele de cod si, deci, pentru

    simbolurie sursei primare:

    ( )il

    iD

    xp

    =

    1 unde il este lungimea cuvantului de cod pentru ix .

    Cum ( ) 1=i

    ixp , rezulta ca, o conditie pentru a avea un cod absolut optimal este:

    11

    ==

    N

    i

    liD

    Observatii:

    - egalitatea de mai sus este o conditie de existenta pentru codurile absolut optimale;

    in cazul codarii binare, aceasta conditie se traduce prin a cere ca simbolurile sursei

    primare sa aibe probabilitati care sunt puteri intregi negative ale lui 2 (exemplu:

    [ ]

    =

    8

    1,

    8

    1,

    4

    1,

    2

    1P

    - codurile absolut optimale sunt un caz limita pentru Inegalitatea Kraft-McMillan,

    deci pot fi si ireductibile

    7.6. Coduri optimale

    Codarea unuei surse de informatie cu un cod binar absolut optimal este posibila numai daca

    probabilitatile sursei satisfac conditia:

    ( )il

    iD

    xp

    =

    1

    ( )( )

    i

    i

    i xpD

    xpl 2

    2

    2 loglog

    log==

    De cele mai multe ori, ( )i

    xp2log este un numar zecimal. De aceea, se construiesc cuvinte

    de cod cu lungimea minima posibila, adica ( ) ii xpl 2log= . Aceste cuvinte satisfacconditia:

    ( )1

    log

    log

    2

    2 +D

    xpl ii i

    Amplificand inegalitatile cu ( )ixp si insumandu-le dupaI, rezulta:

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

    58/90

    ( )( ) ( )

    ( )

    +i

    i

    i

    i

    i

    i

    ii xpD

    xpxp

    lxp2

    2

    log

    log

    Deci

    ( ) 1log2

    +D

    XHl ceea arata ca se poate gasi un cod unic decodabil, care sa aibe

    lungimea mai mica decat limita superiora( )

    1log2

    +D

    XH.

    Vom demonstra, in continuare, ca aceste coduri satisfac Inegaliatea Kraft-McMillan,

    deci ca ele sunt si coduri ireductibile (instantanee).

    Deoarece( )

    =

    D

    xpl ii

    2

    2

    log

    log, putem scrie:

    ( )i

    i lD

    xp

    2

    2

    log

    log ( ) il

    i Dxp i

    Insumand dupa i, rezulta :

    ( ) i

    l

    i

    iiDxp 1

    i

    liD

    Deci, acsete coduri satisfac Inegalitatea Kraft-McMillan care este conditia necesara si

    suficienta pentru a avea un cod ireductibil.

    Definitie: Codurile constituite din cuvinte de lungime ( ) ii xpl 2log= sunt codurioptimale.

    7.7. Capacitatea, eficienta si redundanta codurilor

    Definitie: Capacitatea unui codeste maximul cantitatii medii de informatie ce poate fi

    transmisa de simbolurile din alfabetul canalului :

    ( ) DCHC logmax ==

    Definitie: Eficienta unui codse defineste prin :

    1min =l

    l

    ( ) ( )( )D

    CH

    D

    l

    XH

    l

    D

    XH

    loglog

    log===

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

    59/90

    Definitie: Redundanta unui codse defineste prin :

    ( )[ ]1,0

    log11 ==

    D

    CH

    Observatie:Capacitatea, eficienta si redundanta codului sunt marimi similare celor

    prezentate la capitolul de Canale discrete. Expresiile sunt diferite pentru ca, in cazul canalelor,se foloseste notiunea de cantitate medie de informatie pe simbolurile generate de sursa

    primara, iar in cazul codurilor, se considera informatia medie pe simbolurile sursei secundare.

    7.8. Extensia unei surse de informatie

    Fie o sursa de informatie cu alfabetul :

    [ ] [ ]NxxX ,,1 K= si probabilitatile [ ] ( ) ( )[ ]NxpxpP ,,1 K=

    Presupunem ca sursa Xgenereaza urmatorul sir de v.a., care iau valori in alfabetul sursei:

    KK ,,,,,,, 1223210 +nn XXXXXX

    Definitie : Extensia de ordin 2 a sursei X, este o sursa notata 2X , care genereaza sirul:

    KK ,,,, 10 nZZZ

    unde v.a.n

    Z sunt siruri de doua v.a. consecutive ale sirului KK ,,,,,,, 1223210 +nn XXXXXX

    Mai precis: ( )100 ,XXZ = , ( )321 ,XXZ = , , ( )122 , += nnn XXZ

    Observatii:

    - extensia de ordin m se noteaza cu mX si este o sursa ale carei simboluri sunt siruri de

    lungime m

    - alfabetul extensiei mX este constituit din mN simboluri (siruri).

    Teorema : Entropia extensiei mX , fara memorie, este de mori mai mare decat entropia surseiX:

    ( ) ( )XmHXH m =

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

    60/90

    7.9. Prima Teorema a lui Shannon

    Conform rezultatelor din Sectiunile 7.4 si 7.6, lungimea unui cod folosit pentru codarea unei

    surse de informatie fara memorie X, satisface urmatoarele inegalitati :

    ( ) ( )1

    loglog 22+

    D

    XHl

    D

    XH

    Aceasta dubla inegalitate este valabila si pentru extensia mX , care este tot o sursa fara

    memorie :

    ( ) ( ) ( )1

    loglog 22+

    D

    XHl

    D

    XH mmm

    unde ( )ml este lungimea medie a cuvintelor de cod pentru simbolurile sursei extinse, care

    sunt siruri de msimboluri ale sursei initiale. Deci, ( ) lml m = , unde l este lungimea medie acuvintelor de cod pentru simbolurile sursei initiale.

    Aplicand rezultatul Sectiunii 7.8, dubla inegalitate devine:

    ( ) ( )mD

    XHl

    D

    XH m 1

    loglog 22+

    ceea ce reprezinta expresia matematica a Primei teoreme a lui Shannon

    Prima teorema a lui Shannonsau Teorema codarii canalelor fara zgomot: Codand siruri

    de simboluri suficient de lungi, ne putem apropia oricat de mult de codarea absolut optimala.

    7.10. Algoritmi de codare entropica

    7.10.1. Codarea Shannon-Fano

    7.10.2. Codarea Huffman

    7.10.3. Codarea aritmetica

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

    61/90

    8. CODAREA DE CANAL

    Locul codarii de canalintr-o schema de transmisiune a datelor :

    Rolul codarii de canal : La trecerea prin canal, se produc modificari aleatoareale

    informatiei din cauza perturbatiilor. De aceea, la iesirea din canal, informatia nu poate fi

    reconstituita fidel. Putem construi totusi, un Codor de canalcare sa reduca probabilitatea de

    eroare printr-o codare adecvata a sirului de simboluri, inainte ca acestea sa fie transmise prin

    canal. La iesirea din canal,Decodorul de canal, face operatia inversa pentru a reconstitui sirul

    de simboluri.

    Observatie:Codarea de canal nu elimina erorile, ci doar reduce probabilitatea lor de aparitie.

    8.1. Probabilitatea de eroare la decodare

    Fie [ ] [ ]NxxX ,,1 K= , sursa de informatie care emite la intrarea in canal, si [ ] [ ]MyyY ,,1 K= ,sursa care modeleaza iesirea canalului (se folosesc notatii diferite pentru intrare si iesire

    pentru ca receptorul de la iesirea din canal poate schimba alfabetul). Sa presupunem ca in

    conditiile unei transmisii fara perturbatii, jy se receptioneaza atunci cand a fost transmis jx .

    Probabilitatea ca jy sa fie decodat gresit este:

    jj yxp /1

    Deoarece, intr-o transmisie printr-un canal cu zgomot, in general probabilitatea de transmisie

    corecta este mai mare decat probabilitatea de transmisie eronata, rezulta ca jj yxp / este

    probabilitatea care minimizeaza probabilitatea de decodare gresita jj yxp /1 .

    Pentru a minimiza numarul de erori, putem deci construi un decodor care sa decodeze pe jy

    in simbolul ix cel mai probabil, adica simbolul pentru care )ji yxp / este maxima.

    In medie, probabilitatea de eroare la decodare va fi:

    ( ) ( )( ) ( )j

    j

    jj ypyxpEP = /1

    U

    P

    S CoS C A N A L DecSDecCCoC UR

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

    62/90

    Observatii:

    - decodorul care lucreaza pe acest principiu se numesteDecodor cu rata minima de eroare

    - aceasta probabilitate poate fi calculata daca se cunoaste matricea de zgomot a canalului si

    probabilitatile simbolurilor la intrarea in canal:

    ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( )jjjjj

    j

    jj

    j

    jj

    j

    jj xpxypxpxypypypyxpEP === /1//1

    Exemplul 8.1 : Canalul binar simetric

    Fie canalul cu matricea de zgomot: ( )

    =

    pp

    ppXYP

    1

    1/ unde p este probabilitatea de

    transmisie eronata. Pentru un 2,0=p , simbolurile cele mai probabile, cand se receptioneaza,

    1y si 2y , sunt 1x si, respectiv, 2x (probabilitatile ji yxp / maxime corespunzatoare sunt

    8,0 ). In plus, daca inainte s-a facut o codare de sursa care a condus la simboluri

    echiprobabile :

    ( ) ( )2

    121 == xpxp

    atunci probabilitatea totala de eroare aDecodorului cu rata minima de eroareva fi :

    ( ) ( ) ( ) ( ) 2,02

    1121/1 ==== ppxpxypEP j

    j

    jj

    8.2. Codarea prin repetarea simbolurilor

    O metoda simpla de codare de canal esteprin repetarea simbolurilor. Ea consta din a

    transmite fiecare simbol de un numar impar de ori. Decodarea se face prin logica majoritara.

    Exemplul 8.2 :

    a) Codarea unui sir binar prin repetare de trei ori a fiecarui simbol (transmisia se face prin

    canalul din exemplul anterior)

    Codarea: 0 -> 000

    1-> 111

    Decodarea: 000->0 111->1

    001->0 110->1

    010->0 101->1

    100->0 011->1

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

    63/90

    ( ) ( ) ( ) ( ) ( )

    ( ) ( ) ( ) ( )ppppp

    xpxpxpxpxypdecodat

    211131

    0/1000/0100/0010/0000/0

    223+=+=

    ==+=+=+====

    ( ) ( ) ( )ppxyp decodat 211...1/12

    +====

    Rezulta :

    ( ) ( ) ( ) ( ) ( ) ( ) 1,022

    121121/1

    2=+== ppppxpxypEP j

    j

    jj

    Observatii:

    - probabilitatea totala de eroare a scazut la jumatate

    - se transmit de trei ori mai multe simboluri, deci rata de emisie a sursei (nr de

    simboluri pe secunda) trebuie sa fie mai mica decat capacitatea de transmisie a

    canalului (nr maxim de simboluri pe secunda, care se pot transmite prin canal)

    b) Codarea prin repetarea de cinci ori a fiecarui simbol :

    ( ) ( ) ( ) ( ) ( )( )23322541

    5

    50

    5 63111110/0 pppppCppCpCxyp decodat ++=++===

    ( ) ( )( ) 05,063111 23 ++= pppEP

    Observatie :

    - probabilitatea de eroare a scazut si mai mult, dar rata de emisie R trebuie sa fie cel

    mult o cincime din capacitate de transmisie C :

    5

    CR

    8.3. Teorema a 2-a a lui Shannon

    Teorema : Daca avem o sursa cu o rata de emisie R si un canal cu perturbabii, cu o

    capacitate de transmisie RC > , exista un cod cu cuvinte de n , astfel incat probabilitatea de

    eroare sa fie :

    ( ) ( )RnEEP 2

    unde ( )RE este o functie nenegativa numita exponentul erorii.

    RC

    E(R)

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

    64/90

    Observatii :

    - Teorema a 2-a a lui Shannon este cunoscuta si sub numele de Teorema codarii

    canalelor cu perturbatii

    - Functia ( )RE este o caracteristica a canalului de transmisiune- Teorema a 2-a stabileste ca pe un canal se poate face o transmisie cu probabilitate de

    eroare ( )EP oricat de mica, daca rata de emisie a sursei se diminueaza suficient de mult.- Intr-o aplicatie practica, daca se impune ( )EP , cunoscand functia ( )RE , se poate

    determina rata (maxima) de emisie R a sursei sau, daca se impune R , se poate afla ( )EP cucare se va face transmisia pe canal pentru rata impusa.

    8.4. Spatiul cuvintelor

    In Exemplul 8.2, fiecare simbol al sursei binare era codat printr-un cuvant de lungime 3,

    obtinut prin repetarea simbolului. Se obtinea, astfel, o carte de cod constituita din doua

    cuvinte :

    Codarea: 0 -> 000

    1-> 111

    La decodare, din cauza perturbatiilor, poate fi receptionat orice cuvant de lungime 3 :

    Decodarea: 000->0 111->1

    001->0 110->1

    010->0 101->1

    100->0 011->1

    Definitie :Cuvintele emise de codor se numesc cuvinte cu sens, iar restul cuvintelor deaceeasi lungime se numesc cuvinte fara sens.Impreuna, ele constituie multimea cuvintelor

    de lungime n ( 3=n in exemplul 8.2).

    8.5. Reprezentarea grafica a cuvintelor

    In Exemplul 8.2, s-au folosit cuvinte de lungime 3. Intr-un spatiu 3D, aceste cuvinte pot fi

    reprezentate prin puncte :

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

    65/90

    Observatii :

    - cuvintele cu sens sunt marcate cu negru

    - schimbarea unui bit intr-un cuvant este echivalent cu deplasarea pe una din laturile

    cubului, spre unul dintre cuvintele vecine

    - pentru a trece de la un cuvant cu sens la celalalt, trebuie facuti minim 3 pasi

    - decodorul cu logica majoritara din Exemplul 8.2 a decodat cuvintele fara senscautant cuvantul cu sens cel mai apropiat

    8.6. Distanta Hamming

    Definitie:Distanta Hammingdintre doua cuvinte este egala cu suma bitilor prin care

    cuvintele difera.

    ( ) 3111,000 =Hd

    Observatie :In reprezentarea grafica, distanta Hamming este numarul minim de pasi necesari

    pentru a trece de la un cuvant la celalalt.

    R.W. Hamming (1915-1998) a lucrat la Los Alamos intre 1944 si 1946 si apoi la Bell Labs si

    Univ. Princeton.

    8.7. Erori detectabile si erori corectabile

    Codurile de canal pot fi :

    - corectoare de erori (cuvintele fara sens sunt detectate si corectate)

    -

    detectoare de erori (cuvintele fara sens sunt detectate si rejectate, iar decodorulcere retransmisia cuvantului)

    Codul din Exemplul 8.2. poate corecta o singura eroare (numai cuvintele fara sens care difera

    printr-un singur bit de un cuvant cu sens sunt corectate). Daca apar doua erori, cuvantul este

    decodat gresit.

    Cu acelasi cod, daca nu se incearca corectare ci se doreste doar detectarea cuvantului fara sens,

    atunci pot fi detectate doua erori. Spunem ca avem un cod corector de o eroare si detector de

    doua erori.

    8.8. Specificarea cuvintelor cu sens

    Cuvintele cu sens trebuie alese astfel incat distanta Hamming minima dintre ele sa fie cat mai

    mare.

    Daca 12min += edH , codul este corector de e erori si detector de e2 erori.

    Daca edH 2min = , codul este corector de 1e erori si detector de 12 e erori.

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

    66/90

    Exemplu: Codare prin adaugarea bitului de paritate (cuvinte de lungime 3)

    Codarea: 00 -> 000

    01-> 011

    10-> 101

    11-> 110

    Observatie:este un cod detector de o eroare (de fapt, detector de orice numar impar de erori).

    Exercitiu:Cate erori poate corecta/detecta urmatorul cod:

    00000, 00111, 11001, 11110

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

    67/90

    9. CODURI CORECTOARE/ DETECTOARE DE ERORI

    Clasificare :

    - coduribloc: - codurigrup

    - coduriciclice

    - coduriconvolutionale

    Codurile bloc se obtin taind sirul de simboluri ce urmeaza sa fie codat in blocuri de lungime

    fixa, numiteblocuri de informatie, la care se aduaga simboluri de control, calculate pe baza

    simbolurilor de informatie. Simbolurile de control contituieblocul de control.

    Coduri bloc :

    - sistematice(simbolurile de control sunt grupate la inceputul sau sfarsitul

    cuvatului)

    - nesistematice(simbolurile de control sunt inserate in blocul de informatie)

    La codarea cu coduri convolutionale, sirul de simboluri de informatie se prelucreaza

    continuu.

    9.1. Coduri grup

    Formalism matematic :

    blocul de informatie : [ ]kiii K1=

    blocul de control : [ ]mccc K1= cuvantul de cod : [ ] [ ]

    nkm vviiccv KKK 111 ==

    cuvantul de eroare : [ ]n K1= cuvantul de cod eronat : =vv'

    Lungimea cuvantului de cod este kmn += .

    Observatii :

    Bloc de control Bloc de informatie

    CUVANT de COD

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

    68/90

    - cuvintele corecte sunt cuvintele de cod ; ele se mai numesc si cuvinte cu sens

    - cuvintele eronate se mai numesc si cuvinte fara sens

    - cuvantul de cod este un vector de dimensiune n

    - elementele vectorilor sunt numere binare

    - cuvintele de cod apartin unui spatiu vectorial, care are o structura de grupin raport

    cu operatiile de a