Transmiterea Si Codificarea Informatiei

63
1 UNIVERSITATEA TITU MAIORESCU )DFXOWDWHD GH ,1)250$7,&Ă Profesor univ. dr. ing. Lector univ. dr.ing. 5Ă&8&,8 &,35,$1 GRECU DAN &XUV SHQWUX vQYăĠăPkQWXO OD GLVWDQĠă %8&85(ù7, ± 2010

description

codificarea informatiei

Transcript of Transmiterea Si Codificarea Informatiei

  • 1

    UNIVERSITATEA TITU MAIORESCU )DFXOWDWHDGH,1)250$7,&

    Profesor univ. dr. ing. Lector univ. dr.ing. 5&8&,8&,35,$1 GRECU DAN

    &XUVSHQWUXvQYPkQWXOODGLVWDQ

    %8&85(7, 2010

  • 2

    UNIVERSITATE$7LWX0$,25(6&8%8&85(7, )DFXOWDWHDGH,QIRUPDWLF QYPkQWOD'LVWDQ

    TEORIA TRANSMITERII ,&2',),&5,,,1)250$,(,

    &XUVXOTeoria transmiterii LFRGLILFULLLQIRUPDLHLHVWHRGLVFLSOLQFDUH

    vQJREOHD] vQWU-R IRUP XQLWDU FRQFHSWH GLQ WHRULa codurilor, teoria semnalelor aleatoare i teoria deciziilor statistice LUHSUH]LQWXQDGLQGLVFLSOLQHOHGHSUHJWLUHFDUHSHQWUXSURILOXO,1)250$7,&HVWHQHFHVDUSHQWUXSUHJWLUHDVWXGHQLORULSHQWUX RELQHUHD FUHGLWHORU WUDQVIHUDELOH SULQ SURFHGurile de evaluare. Modul de SUH]HQWDUH D DFHVWXL PDWHULDO DUH vQ YHGHUH SDUWLFXODULWLOH vQYPkQWXOXL ODGLVWDQODFDUHVWXGLXOLQGLYLGXDOHVWHGHWHUPLQDQW3HQWUXRULFHQHOPXULULIDGHDFHVWPDWHULDO Y UXJPVFRQWDFWDL WXWRUHOHGHGLVFLSOLQ FDUHDUHGDWRULD V Yajute oferindu-YWRDWHH[SOLFDLLOHQHFHVDUH Disciplina Teoria transmiterii LFRGLILFULLLQIRUPDLHLvLSURSXQHXUPWRDUHOHobiective specifice: QVXLUHD QRLXQLORU IXQGDPHQWDOH GLQ GRPHQLXO Teoriei transmiterii L

    codificULLLQIRUPDLHL. )RUPDUHD GHSULQGHULORU GH PRGHODUH PDWHPDWLF L GH WUDQVSXQHUH vQ

    SURJUDPDUH D XQRU SUREOHPH GH QDWXU WHKQLF VRFLDO VDX HFRQRPLF FXXWLOL]DUHDFXQRWLQHORUvQVXLWH

    )RUPDUHD L GH]YROWDUHD ED]HL PDWHPDWLFH D VWXGHQLORU SHQWUX disciplinele IXQGDPHQWDOHLGHVSHFLDOLWDWHGLQDQLLVXSHULRUL;

    )RUPDUHD L GH]YROWDUHD DSWLWXGLQLORU L GHSULQGHULORU GH DQDOL] ORJLFIRUPXODUH FRUHFW L DUJXPHQWDUH IXQGDPHQWDW vQ UH]ROYDUHD SUREOHPHORUtehnico-HFRQRPLFHLGHVSHFLDOLWDWH

    O compDUDLH FULWLF DPHWRGHORU GH UH]ROYDUH HYLGHQLLQG HYHQWXDO FDOHDRSWLPGHVROXLRQDUH

    9SUHFL]PGHDVHPHQHDFGLQSXQFWGHYHGHUHDOYHULILFULORULDOQRWULLFXDGHYUDW LPSRUWDQWHVWHFDSDFLWDWHDSHFDUH WUHEXLHVRGREkQGLLLVRSUREDLGH D UH]ROYD WRDW WLSRORJLD GH SUREOHPH DSOLFDWLYH DIHUHQWHPDWHULDOXOXL WHRUHWLFSUH]HQWDW vQ FRQWLQXDUH 'H DFHHD Y UHFRPDQGP V SDUFXUJHL FX DWHQLH WRDWHDSOLFDLLOHUH]ROYDWHVUH]ROYDLDSOLFDLLOHSURSXVHSULQ WHVWHOHGHDXWRHYDOXDUHLtemHOH GHFRQWURO ILL FRQYLQLFH[DPHQXO ILQDODSHOHD] OD WLSXULOHGHDSOLFDLLSUH]HQWHvQVHFLXQLOHPHQLRQDWHDQWHULRU

  • 3

    CUPRINS

    MODULUL 1- 0685$&$17,7$7,9$,1)250$,(,pag.4 MODULUL 1- CAPITOLUL 1- ELEMENTE DE 7(25,$75$160,7(5,,,1)250$,(, ..................................................................................................................................pag.5

    1.1. Informatia JHQHUDOLWL..............................................................pag.5

    1.2. Sistemul de transmitere a informatiei. .......................................pag.6

    1.3. 1.3. Modele de surse informationale. .........................................pag.7

    1.4. 1.4. Modelul probabilistic al semnalelor.....................................pag.8 MODULUL 1- CAPITOLUL 2 - 0685,,1)250$,21$/(SDJ

    2.1. Modele de surse informationale.....................................................pag.9 2.2. Informatia proprie conditionata...................................................pag.10

    TESTE DE AUTOEVALUAR(,7(0('(&21752/.......................pag.21 BIBLIOGRAFIE RECOMAN'$7/$02'8/8/....................... pag.21

    MODULUL 2 - CODAREA SURSELOR ,1)250$,21$/( .................... .........pag.22 MODULUL 2- CAPITOLUL 1- &2'$5($6856(/25,1)250$,21$/( .....pag.23

    1.1 Codificarea surselor discrete.......................................................pag.23

    1.2 Codificarea neuniforma................................................................ pag.23

    1.3. Codarea si decodarea pe canale fara perturbatii... pag.25 &RGXUL+XIIPDQGHGLVSHUVLHPLQLPSDJ

    1.5 3URFHGHXOGHFRGDUHELQDU6KDQQRQ Fano. .........................pag.34 TESTE DE AUTOEVALUAR(,7(0('(&21752/................ pag.39

    BIBLIOGRAFIE RECOMAN'$7/$02'8/8/..................pag.40 MODULUL 3- &2'85,'(7(&72$5(,&25(&72$5('((525,................pag.41 MODULUL 3 - CAPITOLUL 1 - CODUR, '(7(&72$5( , &25(&72$5( '(ERORI.....................................................................................................................pag.42

    1.1. Codarea si decodarea pe canale perturbate ..............................pag.42 &RGXULEORFOLQLDUH..pag.44 1.3. Exemple de coduri liniare ...........................................................pag.46

    TESTE DE AUTOEVALUAR(,7(0('(&21752/.................pag.62 BIBLIOGRAFIE RECOMAN'$7/$02'8/8/ ...................pag.63

  • 4

    &RRUGRQDWRUGLVFLSOLQ3URIXQLYGULQJ5&8&,8&,35,$1 Tutori: Lector univ. dr.ing. GRECU DAN

    MODULUL 1

    0685$&$17,7$7,9$INFORMAIEI

    Q DFHVWPRGXO VXQW SUH]HQWDWH SULQFLSDOHOH QRLXQL FX FDUH RSHUHD] WHRULDinformaiei. Notiunea de informatie a aparut mult mai tarziu decat notiunea de energie, iar legile dupa care informatia apare, se transforma, se pastreaza, se prelucreaza si se foloseste sunt inca insuficient studiate; abia in zilele noastre se stabilesc bazele intelegerii lor, se elucideaza metodele de studiu si investigare.

    Stabilirea notiunii generalizate de informatie pentru caracterizarea proceselor de conducere dintr-un punct de vedere unitar,a fost un moment important in stiinta. Intocmai cum introducerea notiunii de energie a permis sa se analizeze toate fenomenele naturii dintr-un punct de vedere unic, independent de substratul lor fizic, tot asa,introducerea notiunii de informafie a permis studierea dintr-un punct de vedere comun a celor mai diferite procese de comanda din natura. Se numeste informatie orice stire care poarta in sine urma unui fapt, eveniment sau proces oarecare.

    Informatia este comunicarea (mesajul) ce aduce stiri despre fapte, evenimente, obiecte, procese.In intelesul mai larg, in nofiunea de informatie se pot cuprinde toate stirile despre mediul care ne inconjoara sau, mai bine zis, care se obtin, in interactiunea omului cu mediul inconjurator. A obtine o informatie inseamna a afla lucruri ce nu se cunosteau mai inainte sau a obtine noi cunostinte asupra unui lucru, fapt etc., despre care s-a stiut mai putin inainte

    7LPSXOPHGLXQHFHVDUvQVXLULLQRLXQLORUWHRUHWLFHIRUPULLGHSULQGHULORUGHFDOFXO L XWLOL]ULL PHWRGHORU GH UH]ROYDUH D SUREOHPelor specifice teoriei LQIRUPDLHL este estimat la aproximativ 6-8 ore pentru fiecare modul vQWU-un ritm de 2-3 ore pe zi.

  • 5

    MODULUL 1 CAPITOLUL 1

    ELEMENTE DE TEORIA TRANSMITERII INFORMAIEI

    1.5. Informatia JHQHUDOLWi.

    Q SURFHVHOH GH FRPDQGD SURFHsele energetice care insotesc transmiterea informatiei joaca un rol secundar. Cantitatea de informatie si cu atat mai mult efectul ei,nu sunt determinate de cantitatea de energie folosita pentru transmiterea infornafiei. Esenta proceselor de conducere, care se desfasoara pe baza schimbului de informatie, consta tocmai in aceea ca miscarea si actiunea unor mase materiale mari sau transmiterea si transformarea unor cantitati mari de energie se dirijeaza si se controleaza cu ajutorul unor mase materiale mici si al unor cantitati reduse de energie.

    Q WHRULD LQIRUPDWLHL FDUDFWHULVWLFD HQHUJHWLFD D IHQRPHQHORU WUHFH SH SODQ VHFXQGDUevidentiindu-se in mod deosebit latura informafionala a sistemului. Asadar, notiunea de informatie este foarte larga si se poate prezenta sub cele mai variate forme: aceasta constituie o proprietate de seama a informatiei. Prin mijloacele de telecomunicatii -telefon,telegraf, radio - se transmit informantii. Prin intermediul vazului, auzului, precum si al celorlalte simturi, omul primeste zilnic tot felul de informafii despre evenimentele din lumea ce il inconjoara. Comunicari complexe, ordine si dispozitiuni se transmit cu ajutorul telefonului, telegrafului si radioului. Comunicari si mai complexe sunt cele transmise prin intermediul televiziunii, unde imaginile in miscare sunt insotite de semnale audio.La toate aceste sisteme, transmiterea informatiei este insotita de un fenomen nedorit,de adaugare la informatia transmisa a unor semnale perturbatoare ce nu au fost produse de sursele initiale de informantii; in telefonie se distorsioneaza semnalul de vorbire, in televiziune se deformeaza imaginea, in telegrafie apar greseli de imprimare. Aceste exemple evidentiaza o alta proprietate de baza a informatiei: in nici un sistem fizic informatia nu apare intr-o forma curata ci este insotita de diferite perturbatii care pot duce la greseli. De aceea,una din problemele principale ale teoriei informatiei consta in stabilirea metodelor optime pentru extragerea informatiei din semnalele care sunt insotite de perturbatii. Notiunea de informatie a cucerit un loc sigur in stiinta numai atunci cand s-a gasit o masura adecvata pentru caracterizarea ei. O alta proprietate de seama a informatiei este aceea de a putea fi masurata. Nu este suficient insa sa se gaseasca o modalitate de masurare a informafiei: trebuie sa existe posibilitatea folosirii acestei masuri, adica sa existe siguranta ca se pastreaza obiectul masuratorii. Tot asa, informatia care ia nastere in cadrul unui sistem bine definit si se pastreaza in limitele sistemului respectiv, poate fi masurata, indiferent de natura sistemului.

    Problema principala a teoriei informatiei este studierea transformarii, pastrarii si transmiterii informatiei. Analiza acestui fenomen a fost facuta pentru prima data de inginerii de telecomunicatii, care s-au ocupat cu organizarea canalelor destinate transmiterii informatiei.

    QUHDOLWDWHLQIRUPDWLDVHWUDQVPLWHSULQLQWHUPHGLXOVHPQDOHORUFDUHSRDUWDVWLUHD7LSXULde informatie :informatii numerice, informatii logice, de tip text, informatii multimedia:audio, imagine, video, semnale .

  • 6

    1.2. Sistemul de transmitere a informatiei.

    Purtatorul material al informatiei - semnalul - isi pastreaza capacitatea sa de a transmite informatia numai in cadrul unui sistem de transmisiuni; schema bloc destul de generala a unui sistem de transmisiuni este data in fig.1.1

    Fig.1.1

    Coderul din fig.1.1 executa orice prelucrare a semnalului generat de sursa. O asemenea prelucrare poate include, de exemplu, o anumita combinatie de modulatie, comprimare de date sau introducerea unei redundante pentru lupta cu perturbatiile.

    Canalul este mediul fizic utilizat pentru transmiterea semanalului:de exemplu linia telefonica, linia radio sau radioreleu, dispozitivul de memorie sau organismul uman. Asupra canalului, de regula, actioneaza diferite perturbatii care in liniile de telefonie pot apare din cauza modificarilor caracteristicii de frecventa, a convorbirilor ce se induc din alte linii, a zgomotului termic, a impulsurilor parazite, sursa carora pot fi schemele de comutare, a bruiajului intentionat al adversarului etc.

    Decoderul executa prelucrarea semnalului de la iesirea canalului in scopul de a reproduce la partea de receptie o copie acceptabila iesirii sursei.

    Destinatarul poate fi omul sau un dispozitiv tehnic oarecare. Pentru a simplifica analiza modelelor de surse si canale este de dorit a separa efectele legate de sursa de efectele legate de canal.

    Sarcina coderului sursei este de a reprezenta iesirea sursei cu ajutorul succesiunilor de semnale binare, si una din problemele importante ce apar, consta in a stabili cate simboluri binare,in unitatea de timp sunt necesare pentru reprezentarea semnalului de la iesirea unei surse date.

    Sarcina coderului si decoderului canalului consta in a reproduce cat mai sigur succesiunile binare ale datelor obtinute la iesirea decoderului canalului si una din problemele inportante ce apare este, daca acest lucru este posibil sa se faca,si cum sa se faca.

    Coderul sursei transforma mesajul de la iesirea sursei intr-o succesiune de semnale binare sau care apartin unui alfabet finit, din care decoderul sursei restabileste mesajul initial cu o precizie adoptata de catre destinatar. Astfel, independent de proprietatile sursei sau destinatarului, la intrarea coderului canalului si la iesirea decoderului canalului,se formeaza o succesiune de simboluri binare sau de simboluri care apartin unui alfabet finit. Reprezentarea informatiei de transmis sub forma unei succesiuni binare intermediare da posibilitatea sa se calculeze si sa se construiasca dispozitive de codificare si decodificare de canal, independent de dispozitivele corespunzatoare care se refera la sursa. Sarcina sistemului de transmisiuni, este de a transmite mesajul de la sursa la destinatar, adica de a reproduce mesajul de la iesirea sursei la ORFXO LQGLFDWGHGHVWLQDWDU&DQGVSXQHPUHSURGXFHQXLQWHOHJHPRUHSURGXFHUHDEVROXWILGHOD

  • 7

    ci o reproducere care corespunde anumitor scopuri specifice.Criteriul acceptabilitatii depinde de scopul transmisiuni. QGHVFULHUHDRELHFWXOXLWUDQVPLVSULQVLVWHPXOGHWUDQVPLVLHWUHEXLHLQFOXVsi criteriul acceptabilitatii. Astfel, obiectul ce se transmite nu determina numai proprietatile sursei, ci caracterizeaza proprietatile cupOXOXO VXUVD-destinatar". Vom numi acest obiect LQIRUPDWLDWUDQVPLVD

    1.3. Modele de surse informationale.

    Ideea fractionarii mesajelor posibile la iesirea sursei intr-o multine discreta de clase are o importanta fundamentala, intrucat conduce la enumerarea reprezentantilor claselor din intervalul de timp dat. Multimea claselor se numeste multimea de mesaje posibile din intervalul de timp dat, admisibile pe timpul transmisiei.Sarcina sistemului de transmisiuni consta in reproducerea mesajului de la iesirea sursei cu o precizie adoptata de catre destinatar. Existenta criteriului de precizie permite sa se grupeze toate mesajele posibile, in orice interval de timp, de la iesirea sursei in clase disjuncte. Sistemul de transmisiuni indica destinatarului clasa din care face parte mesajul respectiv.

    Toate sursele in teoria informatiei se modeleaza cu ajutorul proceselor sau succesiunilor aleatorii. Cea mai simpla clasa de modele de surse este clasa surselor discrete fara memorie. La aceste surse iesirea este o succesiune (in timp) de litere, fiecare din ele alese dintr-un alfabet dat, a1, a2, ..., ak. Succesiunea la iesirea sursei este formata din aceste litere alese din alfabet statistic independent si intamplator, alegere ce are la baza o repartitie oarecare de probabilitati P(a1), ..., p(ak). QFD]XOXQHLFRGLILFDULGHDFHVWWLSFRPELQDWLLOHGHFRGYRUDYHDDFHHDVLOXQJLPHSHQWUXca sa fie posibila decodificarea lor.

    Remarcam faptul ca scrierea numerelor, in cazul transmiterii mesajelor admisinile, intr-o forma binara nu are o importanta principala. Ele pot fi scrise in orice sistem de numeratie.Prezinta importanta posibilitatea insasi de transformare a mesajului admisibil intr-o succesiune de simboluri care fac parte dintr-un alfabet finit.Rationamentul prezentat permite sa se presupuna ca numarul de mesaje admisibile sau numarul de simboluri binare, necesare pentru reprezentarea fiecarui mesaj din multimea mesajelor posibile , poate fi luata ca o masura a cantitatii de informatie transmisa de sursa intr-un interval de timp. Dar, dupa cum vom vedea, aceasta presupunere este justa numai intr-un anumit caz. Numarul M de mesaje admise nu descrie complet multimea mesajelor si este necesar sa se ia in consideratie si probabilitatile cu care sunt generate aceste mesaje admisibile.

    Prima teorema a lui C. Shannon - teorema fundamentala a codificarii in lipsa zgomotelor da tocmai o limita inferioara si una superioara pentru lungimea medie a combinatiilor de cod. Probabilitatile p(ai) depind de caracteristicile statistice ale sursei si de procedeul de grupare a mesajelor posibile in clase de echivalenta. In afara de aceasta, numarul mediu de sinboluri binare,generate intr-o secunda, depinde de intervalul de timp T cu care s-a lucrat la gruparea mesajelor in clase de echivalenta. Pentru a mari eficacitatea sistemulul de transmisiuni se cauta sa se minimizeze numarul mediu de simboluri binare generate intr-o secunda de coderul sursei.

    Unul din rezultatele principale ale teoriei transmisiunii informatiei este: in cazul unor conditii destul de generale poate fi indicat numarul R, care, pentru fiecare cuplu sursa-destinatar, exprima viteza de generare a informatiei pentru un criteriu de precizie adoptat. Aceasta viteza se determina ca cel mai mic numar mediu de simboluri binare intr-o secunda, care trebuie sa se transmita pentru ca mesajul sa poata fi reprodus in conformitate cu criteriul de precizie adoptat.

  • 8

    1.4. Modelul probabilistic al semnalelor. Avand in vedere ca pentru orice fenomen din natura sau din societate aprecierile cantitative constituie o conditie de baza a analizei stiintifice s-a cautat o modalitate pentu calculul cantitatii de informatie si s-a stabilit o unitate de masura pentru informatia continuta intr-un semnal purtator de informatie. La calculul cantitatii de informatie si la stabilirea unitatii de masura a informatiei se pleaca de la o descriere probabilistica a semnalelor si se considera semnalele ca evenimente aleatoare. Semnalele discrete care intervin in diferite sisteme informationale, destinate transmiterii si prelucrarii datelor, permit o tratare corespunzatoare probabilistica, iar semnalele continue, de asemenea, permit o descriere probabilistica dupa discretizare - ceea ce se face cu ocazia observarii cu o precizie data. Astfel, puten conchide universalitatea cantitatii de informatie obtinuta pe baza unui model probabilistic.

    Unitatea de masura a informatiei se refera numai la partea cantitativa a informatiei si intotdeauna se face abstractie de continutul semantic al mesajului. Cauza acestei tratari unilaterale rezida in faptul ca aparatul matematic existent deocamdata,nu ne permite efectuarea unui studiu calitativ al informatiei. Construirea unui model probabilistic pentru semnalele discrete - utilizate in cadrul unui sistem informational dat - presupune cunoasterea probabilitatilor cu care apar aceste semnale in urma unui experiment. Aparitia unui semnal in cadrul unui experiment se considera ca un eveniment.

    QFD]XOVHPQDOHORUdiscrete, totdeauna se poate realiza o corespondenta biunivoca intre semnalele posibile si intre o multime de numere naturale X - facand ca fiecarui semnal sa corespunda un numar natural x X- si astfel multimea semnalelor discrete se poate inlocui cu o multime de numere naturale X. In continuare, prin x se intelege fie un semnal oarecare, fie numarul natural care corespunde semnalului respectiv.

    Modelul probabilistic al semnalelor X este dat prin urmatoarea repartitie a variabilei aleatoare:

    MXXX

    M

    xPxPxPxxxX

    ...

    ...

    21

    21 (1,1)

    Prin notatia kX xP se intelege probabilitatea de aparitie a evenimentului x=xk, adica probabilitatea de aparitie a semnalului care corespunde lui xk si care face parte din multimea X considerata. Evident:

    11

    K

    M

    KX xP (1.2)

    Probabilitatea ca rezultatul experimentului va fi un element oarecare x, se noteaza cu Px(x) in care, prin indicele X se accentueaza ca rezultatul experimentului este un semnal din multimea semnalelor posibile X. In cazul cand nu exista ambiguitati in privinta apartenentei lui x se poate suprima indicele X. Experimentele cu mai multe rezultate simultane vor fi caracterizate prin elementele unui produs de multimi si prin probabilitatile de aparitie a acestor elemente.

  • 9

    MODULUL 1 CAPITOLUL 2

    0685,,1)250$,21$/(

    2.1. Modele de surse informationale Informatia proprie, ca si informatia reciproca se poate considera ca o variabila aleatoare

    si se calculeaza valoarea sa medie. Valoarea medie a informatiei proprii pentru evenimente din multinea X se numeste entropia lui X si se calculeaza cu formula:

    KXKK

    KX xPxPXH

    1log1

    (1,3)

    sau mai simplu se scrie sub forma:

    xPxPXH K1log

    1

    (1.4)

    Variatia entropiei unui sistem de evenimente format din doua evenimente in functie de

    repartitia de probabilitati este data in fig 1.2:

    Fig.1.2 Entropia semnalului

    Fie

  • 10

    ppxxX1

    21

    (1.5) atunci:

    pHppppXH 11log11log

    (1.6)

    2.2. Informatia proprie conditionata. Cantitatea de informatie proprie conditionata a evenimentului X=Xk ,cu conditia ca a aparut evenimentul Y=Yi se defineste pe produsul cartezian XY si se calculeaza cu formula:

    i

    k

    yx

    i

    k

    YX

    yxPy

    xI 1log

    (1.7) sau mai simplu se scrie:

    i

    kx

    yxPy

    xI 1log

    (1.8) Aceasta cantitate de informatie proprie a evenimentului X=Xk, conditionata de evenimentul y=yi se poate interpreta ca informatia necesara pentru specificarea evenimentului x=xk . dtupa ce a avut loc evenimentul y =yi. Cu ajutorul relatiilor anterioare se poate exprima cantitatea de informatie reciproca ca o diferenta intre informatia proprie si informatia proprie conditionata.

    yxPxPxP

    yxP

    yxI 1log1loglog;

    (1.9) de unde

    yxIxIyxI ;

    (1.10) Din relatia anterioara se obtine pe baza reciprocitatii relatia:

    xyIyIyxI ;

    (1.11)

  • 11

    In mod analog I(x;y) se poate scrie sub forma:

    yxPyPxPxPyP

    yxPxPyPyxPyP

    xPyxP

    yxI,1log1log1log,logloglog;

    (1.12)

    deci:

    yxIyIxIyxI ,; (1.13)

    unde :

    yxPyxI ,1log,

    (1.14) reprezinta cantitatea de informatie proprie a unui eveniment (x;y) din produsul cartezian de evenimente xy.

    Tinand seama ca:

    y

    xPyPxyPxPyxP ,

    (1.15) rezulta ca, cantitatea de informatie proprie a unui eveniment (x,y) se poate scrie sub forma:

    yxIyIyxI

    xyIxIyxI

    ,

    ,

    (1.16) Luand mediile expresiilor din relatiile anterioare se obtine:

    yxHyHyxH

    xyHxHyxH

    yxHyHxHyxIxyHyHyxI

    yxHxHyxI

    ,

    ,

    ,;

    ;

    ;

    (1.17)

    Prima relatie din sistemul de mai sus permite interpretarea lui I(X;Y). Deoarece H(X) este nedeterminarea lui X,iar H(X/Y) este nedeterminarea lui X dupa receptionarea lui Y, rezulta ca diferenta H(X) - H(X/Y) arata cu cat s-a micsorat nedeterminarea lui X prin observarea lui y, adica ce cantitate de informatie se transmite despre X prin observarea lui Y. Iata motivul pentru care cantitatea de informatie medie I(X;Y) este numita si informatia transmisa sau pe scurt transinformatia.

  • 12

    Din formula entropiei, data de catre C. Shannon in anul 1948 in lucrarea sa, rezulta ca entropia 8; D PXOWLPLL ; GHSLQGH QXPDL GH SUREDELOLWDWLOH GH DSDULWLH D HOHPHQWHORU [;Evident daca multimile X si Y au aceeasi repartitie de probabilitati atunci H(X)=H(y),insa invers,din egalitatea entropiilor nu rezulta identitatea repartitiilor.

    Proprietatea 1. H(X)>0 In adevar,suma H(X) contine termeni de forma P(x)log(1/P(x)),care sunt mai mari sau

    egali cu zero pentru 0

  • 13

    kkk

    xxxX

    k1...11

    ...21

    (1.21)

    Proprietetea 3. Pentru doua multimi de semnale X si Y ,avem:

    yHxHyxH d, (1.22)

    in care avem egalitate daca si numai daca X si Y sunt statistic independente.

    ([HUFLLLUH]ROYate. Conceptia Shannon pleaca de la premiza ca orice informatie cu privire la un eveniment este utilizata in scopul reducerii gradului de incertitudine asupra realizarii acelui eveniment. Din punctul de vedere al destinatarului, comunicatia este o variabila aleatoare, continutul informational fiind cu atat mai mare cu cat el se asteapta mai putin la realizarea acelui eveniment. Fie o sursa discreta care emite unul dintre cele q mesaje m m mq1 2, , , cu probabilitatile de aparitie p p pq1 2, , , . Este evident ca probabilitatile satisfac relatia p p pq1 2 1 . Continutul informational al mesajului k este notat cu I mk( ) . Pentru ca acest continut sa fie o masura adecvata a cantitatii de informatie este necesara satisfacerea urmatoarelor proprietati : (i) daca p p I m I mk j k j !( ) ( ) (ii) daca p I mk ko o1 0( ) (iii) daca 0 1 0d d tp I mk k( ) (iv) (aditivitatea) daca mk si mj sunt mesaje independente I m m I m I mk j k j( ) ( ) ( )si

    O functie continua de variabila pk care satisface proprietatile (i)-(iv) este functia logaritmica.

    I m p pk k k( ) log log 1

    Daca baza logaritmului este 2, unitatile de masura sunt biti (informationali).

    Pentru cazul simplu al unei transmiteri seriale asincrone

  • 14

    se definesc (a) rata de biti=(durata unui bit)-1 =1/T2 exprimata in biti/secunda (abreviat bps). (b) rata de bauds=(durata minima intre doua modificari ale semnalului) =1/T1 exprimata in bauds.

    Problema 1 Se considera o trasmisie fax : 2,25106 pixeli cu 12 tonuri de gri, echiprobabile. Care este cantitatea de informatie transmisa ?

    Solutie I=nr.elemente informatie per element=

    > @

    2 25 10 1

    122 25 10 2 3 2 25 10 2 36 2

    62

    2 62, log , log , log biti

    Problema 2

    Un display monocolor cu 24 linii 80 caractere/linie 128 puncte/caracter 3 tonuri de gri/punct (a) Care este cantitatea de informatie pe pixel, caracter, ecran ? (b) Care este debitul de informatie stiind ca frecventa cadrelor este de 24 cadre/secunda ?

    Solutie (a) I 24 80 128 32log [ ]biti (b) W 1f c

    R I I fc W [ ]bps

    Problema 3 Un echipament de teletransmisie genereaza cuvinte constituite dintr-un grup de 4 impulsuri de tensiune care pot avea nivelurile 0,1,2 sau 3 volti (echiprobabile) urmate de un impuls de pauza de nivel -1 volt. Durata tuturor impusurilor este de 1 ms. (a) Care este debitul de informatie ?

    T2

    EM

  • 15

    (b) Care este rata de bauds ?

    Solutie

    (a) R I

    W4 45 10

    1 62 3log , [ ]kbps

    (b) rbauds baud] kbaud] 110

    10 133 [ [

    Problema 4

    Fie 12 monede dintre care una este falsa (mai usoara sau mai grea decat celelalte). Se cere sa se deterrmine numarul minim de cantariri necesar depistarii monedei false si precizarii daca ea este mai usoara sau mai grea. Se foloseste pentru cantariri o balanta fara mase marcate.

    Solutie

    x cantitatea de informatie necesara determinarii monedei false este I1 2 21112

    12 log log

    x cantitatea de informatie necesara pentru a decide daca moneda este mai grea sau mai usoara este I2 2 2

    112

    2 log log

    x cantitatea de informatie totala necesara a fi determinata I I I 1 2 2 24log x cantitatea de informatie furnizata de o cantarire (exista 3 stari ale balantei)

    I3 2 2113

    3 log log numarul minim de cantariri I kI kkd d 3 24 3 3.

    x sa se propuna un algoritm de depistare.

    Problema 5 Sa se reia problema # 3 daca probabilitatile de aparitie a nivelurilor sunt nivel 0: 1/2 nivel 1:1/4 nivel 2:1/8 nivel 3:1/8 Solutie

    R r H

    15 10

    12

    12

    14

    142 18

    183

    log log log

    Se reaminteste ca entropia unei surse reprezinta numarul mediu de biti/simbol si ca entropia este maxima pentru o sursa care genereaza simboluri echiprobabile H nmax log 2 .

    Problema 6

  • 16

    Sa se determine capacitatea unui canal binar cu zona de anulare avand graful asociat matricei de tranzitie din figura de mai jos

    Solutie Acest model descrie un canal care perturba simbolurile unei surse binare in masura in

    care la receptie sa poata fi interpretate ca fiind incerte. Metoda scalara > @C H Y H Y Xp xi max ( )( ) H Y p y p yi

    ii( ) ( ) log ( )

    1

    3

    )()1()()()()( 11112211111 xpqxpxypxpxypxpxypyp

    S-a utilizat formula probabilitatii totale, evenimentele x1, x2 fiind mutual exclusive. Analog se poate scrie p y q p x( ) ( ) ( )2 21 p y p y x p x p y x p x q p x p x q q( ) ( ) ( ) ( ) ( )3 3 1 1 3 2 2 1 2 1

    > @

    > @H Y q p x q p x q q q p x q p x

    q p x p x p x p x q q q qq H X q q q q

    ( ) ( ) ( ) log( ) ( ) log ( ) ( ) log( ) ( )

    ( ) ( ) log ( ) ( ) log ( ) ( ) log( ) log( ) ( ) ( ) log( ) log

    1 1 1 1

    1 1 11 1 1

    1 1 2 2

    1 1 2 2

    H YX p x y p y xi j j iji

    ( , ) log1

    3

    1

    2

    Conform regulii de inlantuire

    p x y p y x p xi j j i i( , ) ( )

    Din graf se deduce ca p y x q1 1 1 p y x1 2 0

    BED

    Equation.2

    EM

    BED

    Equation.2

    EM

    BED

    Equation.2

    EM

    BED Equation.2

    EM

    BED Equation.2

    EM

    BED Equation.2

    EM

    BED Equation.2

    EM

    BED Equation.2

    EM

    BED

    Equation.2

  • 17

    p y x2 1 0 p y x q2 2 p y x q3 1 p y x q3 2 1

    Se obtine H Y X q q q q ( ) log( ) log1 1 C q H X q q

    p xi ( )max ( ) ( )

    ( )1 1 1 1

    pentru setul optim de probabilitate la intrare p x p x0 1 0 2 1( ) ( ) .

    Metoda matriciala

    Se considera sursa care genereaza un alfabet de simboluri x i ni , , , 1 si la destinatie

    se receptioneaza un alfabet de simboluri y j mj , , , 1 . Se pot scrie urmatoarele relatii:

    P Y P X P Y X( ) ( ) unde P X( ) este matricea linie a sursei ( )1u n ; P Y( ) este matricea linie a destinatiei ( )1um ; P Y X este matricea dreptunghiulara de zgomot ( )n mu .

    Observatie In matricea de tranzitie (zgomot) liniile sunt asociate intrarilor iar coloanele sunt asociate

    iesirilor. Matricea campurilor reunite (joint) este

    P X Yp x

    p x

    p x

    P Y X

    n

    ( , )

    ( )( )

    ( )

    1

    2

    0 00 0

    0

    Matricea de zgomot P Y X se poate obtine prin impartirea fiecarei linii i prin p(xi). Matricea de echivocatie P XY se poate obtine prin impartirea fiecarei coloane j prin p(yj) .

    Problema 7

    Fie matricea de tranzitie P Y X

    2 3 1 31 3 2 3/ // /

    si p(x1)=3/4 si p(x2)=1/4.

    Se cere sa se calculeze (a) entropia campului de intrare

  • 18

    (b) entropia campului de iesire (c) entropia campurilor reunite (d) eroarea medie (e) echivocatia (f) transinformatia (g) capacitatea canalului si setul optim la intrare (h)eficienta si redundanta relativa a canalului

    Solutie

    (a) H X p x p xii

    i( ) ( ) log ( ) log log log ,

    # 1

    2 34

    34

    14

    14

    2 34

    3 0 81 bit / simbol

    (b) H Y p y p yjj

    j( ) ( ) log ( ) 1

    2

    > @ > @P Y( ) / / / // / / /

    3 4 1 4 2 3 1 3

    1 3 2 37 12 5 12

    H Y( ) log log ,

    712

    712

    512

    512

    0 98 bit / simbol

    (c) H XY p x y p x yi j i jji

    ( , ) log1

    2

    1

    2

    P X Y( , ) //

    / // /

    / // /

    3 4 00 1 4

    2 3 1 31 3 2 3

    1 2 1 41 12 1 6

    H X Y( , ) log log log log ,

    12

    12

    14

    14

    112

    112

    16

    16

    1 73 bit / simbol

    (d) H Y X p x y p y xi j j iji

    ( , ) log ,0 921

    2

    1

    2

    bit / simbol

    sau H YX H X Y H X ( , ) ( ) (e) H XY p x y p x yi j i j

    ji

    ( , ) log1

    2

    1

    2

    unde

  • 19

    P XY

    12712

    14512

    112712

    16512

    67

    35

    17

    25

    si H XY

    12

    67

    14

    35

    112

    17

    16

    25

    0 75log log log log , bit / simbol

    sau H XY H X Y H Y ( , ) ( ) (f) I X Y H X H Y H X Y( , ) ( ) ( ) ( , ) , 0 06 bit / simbol (g) canalul fiind dublu uniform

    C

    log log ( ) log ,2 1

    13

    1 13

    2 1 13

    13

    0 082 bit / simbol

    Setul optim p x p x0 1 0 2( ) , ( ) se obtine din

    > @C H Y H Y Xp xi max ( )( )0

    p y p x p x( ) ( ) ( )1 0 1 0 223

    13

    p y p x p x( ) ( ) ( )2 0 1 0 213

    23

    H Y X p x y p y x p y x p x p y x

    p x p x

    i j j iji

    j i i j iji

    ( , ) log ( ) log

    log log ( ) ( ) log log

    1

    2

    1

    2

    01

    2

    1

    2

    0 1 0 223

    23

    13

    13

    23

    23

    13

    13

    deci H Y X nu depinde de P X( ) C H Yp xi

    max ( ) log log( )0

    23

    2313

    13

  • 20

    dar max ( ) log ( ) ( )( )p xiH Y p y p y

    01 22 1

    12

    p y p y x p x p y x p xp y p y x p x p y x p x( ) ( ) ( )( ) ( ) ( )

    1 1 1 0 1 1 2 0 2

    2 2 1 0 1 2 2 0 2

    p x p x0 1 0 212

    ( ) ( ) .

    Observatie Se mai poate utiliza si relatia p x p x0 1 0 2 1( ) ( )

    (h) K( ) ( , ) ,C I X YC 0 73 R C C I X Y( ) ( , ) , 0 022 bit / simbol

    Problema 8

    Fie un canal binar simetric avand matricea campurilor reunite P X Y( , ) , ?? ,

    0 40 4

    si

    pentru care sursa genereaza simboluri echiprobabile. (a) Calculati matricea P X Y( , ) . (b) Calculati matricea de zgomot. (c) Calculati transinformatia.

    Solutie

    (a) canalul fiind simetric p x y p x y( , ) ( , )2 1 1 2 si folosind proprietatea (iii) a evenimentelor mutual exclusive se obtine p x y p x y p x y p x y( , ) ( , ) ( , ) ( , ) ,1 1 1 2 2 2 1 22 1 01 si

    P X Y( , ) , ,, ,

    0 4 0101 0 4

    .

    (b) P Y X

    0 41 2

    011 2

    0 11 2

    0 41 2

    0 8 0 20 2 0 8

    ,/

    ,/

    ,/

    ,/

    , ,, ,

  • 21

    TESTE DE AUTOEVALUARE ,7(0('(&21752/ Testul nr. 1

    )LHXQDOIDEHWIRUPDWGLQOLWHUHOH$%&6HFHUHVVHFDOFXOH]H a. QXPUXOPD[LPGHPHVDMHGHOXQJLPHFHVHSRWIRUPDFXDFHVWDOIDEHW b. cantitatea de informaie conLQXWGHXQDVHPHQHDPHVDM Testul nr. 2

    6VHFDOFuleze cantitatea de informaLLQHFHVDUSHQWUXSUHFL]DUHDSR]Liei unei figuri pe tabla de ah.

    7HPGHFRQWURO

    0DWULFHD SUREDELOLWilor reunite intrare-ieLUH DVRFLDW XQXL FDQDO GH WUDQVPLVLH HVWH GHforma:

    4/14/14/14/1XYP

    6HFHUHVVHFDOFuleze: a. HQWURSLDFkPSXOXLGHODLQWUDUH b. HQWURSLDFkPSXOXLGHODLHire; c. HQWURSLDFkPSXULORUUHXQLWH d. eroarea medie i echivocaia; e. transinformaia i capacitatea canalului.

    BIBLIOGRAFIE RECOMAN'$7/$02'8/8/

    >@$6SWDUX7HRULD7UDQVPLVLXQLi InformaLHL(G'LGDFWLFL3HGDJRJLF%X- cureti, 1983.

    >@$70XUJDQ,6SkQX,*DYW,6]WRMDQRY9(1HDJRH$9ODG7HRULD

    Transmisiunii Informaiei - SUREOHPH(G'LGDFWLFL3HGDJRJLF%XFXUHti, 1983

    [3] I. Angheloiu, 7HRULDFRGXULORU(G0LOLWDU%XFXUHti, 1972. [4] J.C. Moreira, P.G. Farrell, ESSENTIALS OF ERROR-CONTROL CODING, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England,2006.

  • 22

    MODULUL 2 CODAREA SURSELOR ,1)250$IONALE

    Compresia datelor este un proces de re prin carH VH XUPUeWHPLFRUDUHD UedundaQei mesajului generaWGHRVXUVSentru a reduce resursele necesare memorULL VDX WUDQVPLWHULL Dcestui mesaj. Deoarece, de reJXOpentru memorarea sau transmiterea unui mesaj se foloseWH HYHQWXDO vQWU-o IRUPLQWermediaUUeprezentarea prin simboluri binaUHDDFHVWXLDLSHQWUXFcele mai multe metode de compresie folosesc metode de codare binar - binar, SXWHP VSXQH F RELectivul compresiei cRQVW vQ UHGXFerea numUXOXL de simboluri binare necesar pentru reprezentarea mesajului.

    'XScXPLUXOVLPEROXULORUePLVHGHVXUVHVWHvPSULWpentru codarevQVXELUXUL GH DFHHDL OXQJLPH VDX GH OXQJLPH YDULDELO L GXS OXQJLPea, consWDQWVau vaULDELODcuvintelor de cod, codurile de compresie se clasifLFvQbloc- bloc, bloc variabil, variabil EORF L Yariabil variabil, bloc bloc LQGLFkQGDFHHDLOXQJLPHSHQWUXVXELUXULOHVXUVHLL cuvinte de cod de lungime fi[Lar variabil variabil corespun]kQGXQRUOXQJLPLYDULDELOHDOHVXELUXULORULDOHcuvintelor de cod. Din punct de vedere aOPVXULL vQcDUHPHVDMXOUHIcut prin decompresie se aseaPQ FX FHO RULJLQDO DVXSUD FUXLD V-a acLRQat prin procesul de compresie, distingePGRXFDWHJRULLGHalgoritmi de compresieIUpierdeULLFXSLHUGHUL

    $OJRULWPLL GH FRPSUHVLH IU SLHUGHUL VXQW UHYersibili, prin decompresie RELQkndu-se mesajul originaO vQtocmai. Algoritmii de compresie cu pierderi au ca rezultat diferHQHUelativ micLvQtre mesajul rezultat prin decompreVLHL cel originaOLVXQWXWLOL]aLvQcompreVLDLPDJLQLORULDPesajeORUYLGHRLDXGLR

    Q DFHVW PRGXO YRU IL SUH]HQWDWH DVSHFWH SULYLQG FRGLILFDUHD VXUVHORUGLVFUHWHLYRUILDQDOL]DLDOJRULWPLL+XIIPDQL6KDQQRQ-Fano.

  • 23

    MODULUL 2 CAPITOLUL 1

    CODAREA SURSELOR ,1)250$,21$/(

    1.1 Codificarea surselor discrete.

    In general,trecerea de la un sistem de semnale primare la un sistem de semnale secundare se numeste codificare. Cerinta principala care se pune pentru orice codificare practic utilizabila este ca codificarea sa fie efectuata in asa fel ca revenirea de la sistemul de semnale secundare la cele initiale, adica decodificarea sa fie unica.

    Pentru a prezenta problematicile legate de codificarea semnalelor prinare cu ajutorul semnalelor secundare este necesar sa se precizeze forma concreta a semnalelor primare si secundare. Se considera ca semnalele prinare sunt semnale generate de catre o sursa discreta si fara memorie, adica semnalele apar sub o forma discreta si probabilitatea de aparitie a unui simbol nu depinde de celelalte sinboluri anterioare.

    Alfabetul sursei discrete se noteaza cu ^ `LaaaA ....,, 21 ,deci sursa produce succesiuni de litere nuuu ,....,, 21 formate cu ajutorul literelor din alfabetul sursei, deci

    Aui pentru L Faptul ca sursa este fara memorie se exprima prin interdependenta statistica a

    semnalelor,adica probabilitatea unei succesiuni date nn DDDD ,...,, 21 de n litere de sursa este egala cu produsul probabilitatilor literelor de sursa ,deci:

    n

    iin PP

    121 ,....,, DDDD

    (2.1)

    1.2 Codificarea neuniforma.

    Presupunem ca alfabetul unei surse discrete si fara memorie contine M semnale primare

    sau litere notate cu Maaa ,....,, 21 care apar cu probabilitatile MaPaPaP ,..,, 21 . Fiecare litera a sursei trebuie sa fie codificata printr-o combinatie de semnale secundare luate din alfabetul codului care contine D semnale ^ `DxxxX ,..,, 21 .Aceste combinatii se numesc si cuvinte de cod;cuvintele de cod care corespund semnalelor primare Maaa ,..,, 21 se noteaza cu

    Mccc ,..,, 21 ,iar totalitatea lor formeaza un cod, ^ `McccC ,..,, 21 .Numarul semnalelor secundare din cuvantul de cod kc care,dupa cum s-a vazut,corespunde lui ka ,se noteaza cu kn .

  • 24

    Dintre toate, codurile unic decodabile prezinta un interes ,din punct de vedere economic,acel cod care conduce la un n -numarul mediu de litere de cod pe litere de sursa-cat mai mic posibil,unde n se mai numeste si lungimea mediea combinatiilor de cod:

    kM

    Kk naPn

    1 (2.2)

    Codul in care doua semnale primare distincte sunt codificate printr-o singura combinatie de cod se numeste cod singular si in mod corespunzator codul in care toate combinatiile de cod atribuite semnalelor primare sunt distincte se numeste cod nesingular.

    Codul ^ `kcccC ,..,, 21 se numeste unic decodabile daca succesiunile cuvintelor de cod,corespunzatoare diferitelor succesiuni de lungime finite a sursei,sunt distincte.

    Fie un cuvant de cod imiii xxxc ,...,, 21 .Sirul de litere imii xxx ,...,, 21 ,unde mk d se numeste prefixul lui ic .

    Cu ajutorul notiunii de prefix putem defini subclasa codurilor unic decodabile care prezinta un interes deosebit din punct de vedere practice.

    Codul in care nici un cuvant de cod nu este prefixul unui alt cuvant de cod se numeste cod cu proprietate de prefix.Din aceasta definitie rezulta ca in cazul unui cod cu proprietate de prefix,dintr-un cuvant de cod mai lung nu se poate obtine un cuvant de cod mai scurt prin reducerea (suprimarea) ultinelor simboluri,motiv pentru care codurile cu proprietate de prefix se numesc si coduri ireductibile.

    Codurile cu proprietatea de prefix se mai numesc uneori si coduri instantanee, deoarece o combinatie de cod se poate recunoaste fara nici o referinta la urmatoarea combinatie de cod. La decodificarea unei succesiuni de cuvinte de cod dintr-un cod cu proprietatea de prefix se inainteaza in succesiunea semnnlelor pana la identificarea primului cuvant de cod si apoi lasand la o parte succesiunea identificata se trece la identificarea urmatoarei succesiuni si a.m.d. Momentul cand se obtine o succesiune cu sens, arata si sfarsitul unui cuvant de cod, dat fiind faptul ca nici un cuvant de cod nu este prefixul unui alt cuvant de cod.Relatia care exista intre codurile cu proprietate de prefix si codurile unic decodabile se pune in evidenta prin urmatoarea teorema:orice cod cu conditia de prefix este un cod unic decodabil.

    Codurile cu proprietate de prefix permit o reprezentare geometrica foarte intuitiva si convenabila,cu ajutorul unui graf arborescent.Fiecarui cuvant de cod ii corespunde un drum simplu,sau nodul final de la extremitatea drumului simplu corespunzator

    Este important ca in cazul unui cod cu conditia de prefix exista o corespondenta biunivoca intre cuvintele de cod si intre nodurile finale, deci fiecarui cuvant de cod ii corespunde un nod final si nu un nod internediar si invers, fiecarui nod final ii corespunde o combinatie de cod.

    De asenenea si codurile care nu au proprietatea de prefix pot sa fie reprezentate grafic cu ajutorul unui graf arborescent, dar in acest caz cel putin unui cuvant de cod ii corespunde un nod internediar.

    Se observa ca in cazul unui cod D-nar,constructia grafului arborescent corespunzator este asemanatoare, tinand cont ca din fiecare nod pomesc D arce.

  • 25

    1.3. Codarea si decodarea pe canale fara perturbatii.

    In cadrul modulului 1 s-a aratat ca un sistem digital de comunicatie presupune un codor/decodor al sursei. Rolul acestuia este de a mari eficienta transmiterii prin utilizarea unor PHVDMHFkWPDLVFXUWHSHQWUXDWUDQVPLWHDFHLDVLFDQWLWDWHGHLQIRUPDWLH$FHDVWkRSHUDtie numita JHQHULFFRPSUHVLHGHGDWH Definirea unui cod. )LHRVXUVDGLVFUHWDIDUDPHPRULHDYkQGDOIDEHWXO

    ^ `S s s sN 1 2, ,......, (2.3) cu probabilitatea de aparitie p s pi i

    ^ `P p p pN 1 2, ,......, (2.4) Fie alfabetul canalului

    ^ `X x x xq 1 2, ,......, (2.5) constituit dintr-un numar finit de semne (litere, caractere)

    Se considera reuniunea secventelor finite de litere din alfabetul canalului:

    X Xnn

    * t (2.6)

    Orice aplicatie S Xo * se numeste codarea alfabetului S prin alfabetul X

    Un element s Xi* * si care corespunde lui si HVWH XQ FXYkQW GH FRG /XQJLPHD

    FXYkQWXOXL GH FRG QRWDWk n s ni i* este numarul de litere cale Il formeaza. Totalitatea cuvintelor de cod constitue codul lui S cu mentiunea ca X* poate contine si combinatii care nu apartin codului, numite cuvinte fara sens. Astfel, un text constituit din secvente de mesaje: m s s sj i i ik 1 2, ,......, (2.7) este codat prin secventele de cuvinte de cod (cu sens)

    m s s sj i i ik 1 2* * *, ,......, (2.8)

  • 26

    Decodarea implica posibilitateD GH D UHSDUD FXYLQWHOH GH FRG vn mod unic (aplicatia S Xo * sa fie injectiva). Un cod cu aceasta probabilitate se numeste regulat (nesingular). Regularitatea este o conditie necesara dar nu suficienta pentru decodare. fie de exemplu s s1 2 10* *, si s3 01 . Codul 010 poate fi interpretat fie s s1 2* *, fie s s3 1* *, . Pentru a distinge fara ambiguitati un text trebuie ca fiecarui succesiune de cuvinte sa-i

    corespunda o succesiune unica de litere, adica aplicatia S Xkk

    no

    t

    *

    1 sa fie si ea injectiva.

    Un cod de acest tip este un cod unic decodabil. Conditii suficiente care sa asigure aceasta proprietate sunt: (a) utilizarea cuvintelor de cod de aceiasi lungime (bloc) (b) utilizarea unui semn distinct Intre cuvintel (separator)

    Exista vnsa si coduri care nu necesita utilizarea unui mijloc suplimentar pentru a asigura proprietate de unic decodabil. Aceste coduri se numesc separabile. Alcatuirea unui cod. Teorema Kraft Conditia necesara si suficienta pentru existenta unui cod ireductibil de N cuvinte de lungime n n nN1 2, ,......, este ca

    q nii

    N

    d 1

    1

    (2.9)

    Observatii

    1. Se reaminteste ca q card X este numarul de litere din alfabetul canalului. 2. Daca numarul cuvintelor de lungime k este rk atunci conditia (1.9) devine

    r qk kk

    n d

    11

    (2.10)

    cu N rkk

    n

    1

    Teorema Mac Millan Un cod este ireductibil daca si numai daca

    n n nN1 2d d d...... (2.11)

  • 27

    Criterii de apreciere a unui cod.

    Transmiterea mesajelor presupune un cost care creste linear cu timpul. Un criteriu FRQYHQDELOGHDSUHFLHUHDXQXLFRGHVWHOXQJLPHDPHGLHDXQXLFXYkQW

    n p ni ii

    n

    1

    (2.12)

    unde pi sunt definite prin (1.4) si ni HVWHQXPDUXOGHOLWHUHGLQFXYkQWXOGHFRGFXLQGLFHOHi.

    Este evident ca se cauta ca n VD ILH FkWPDLPLF GDU WUHEXLH DYXW ,Q YHGHUH FD HO HVWHlimitat inferior de entropia informationala pe simbol a alfabetului de cod

    n H qt log2 (2.13)

    unde H este entropia sursei. In aceste conditii, eficienta unui cod este

    K dH

    n qlog21 (2.14)

    iar redundanta codului este

    U K 1 (2.15) Codurile cu o eficienta egala cu unitatea si deci care au lungimea medie minima se numesc coduri absolut optimale Prima teorema a lui Shannon. Pentru orice sursa omogena exista un cod ireductibil pentru care lungimea medie a cuvintelor eVWHRUFkWGHDSURSLDWDGHPDUJLQHDVDLQIHULRDUD. Aceasta teorema se mai numeste si teorema codarii pe canale neperturbate. Prima WHRUHPDDOXL6KDQQRQVHUHIHUDODSUREOHPDFRGDULLFXROXQJLPHPHGLHSRVLELODFkWPDLPLFDpe un canal neperturbat de capacitate data. Codurile care asigura cea mai mica lungime medie posibila se numesc cvasioptimale sau compacte.

  • 28

    1.4. &RGXUL+XIIPDQGHGLVSHUVLHPLQLP. $FHVWSURFHGHXVHED]HD]SHLGHHDGHDSDUWLLRQDPXOLPHDPHVDMHORUVXUVHLS = {s1, s2

    ,..., sN} vQVXEPXOLPLOH L DVWIHO vQFkWVXPDSUREDELOLWLORUPHVDMHORU LQFOXVHvQ V

    ILHFkWPDLDSURSLDWGHVXPDSUREDELOLWLORUPHVDMHORULQFOXVHvQ .

    /D UkQGXO ORU VXEPXOLPLOH L SRW IL SDUWLLRQDWH vQ VXEPXOLPLOH L ,

    respectiv L DVWIHO vQFkW VXPD SUREDELOLWLORU PHVDMHORU LQFOXVH vQ FHOH SDWUXVXEPXOLPL V ILHFkWPDLDSURSLDWHSRVLELO3URFHGHXOVHFRQWLQX vQPRGVLPLODUSkQFkQGVH

    RELQVXEPXOLPLFHFRQLQXQVLQJXUPHVDM

    QIHOXODFHVWDSHQWUXRULFHGLVWULEXLHDVXUVHLS FHXUPHD]DILFRGDWVHYDRELQHXQFRGFRPSDFWDGLFOXQJLPLPHGLLDOHFXYLQWHORUGHFRGFHQXPDLSRWILPLFRUDWHSULQQLFLun alt

    procedeu de codare.

    3HQWUXFDSDUWLLLOHVVDWLVIDFFRQGLLLOHPHQLRQDWHVHSURFHGHD]

    astfel:

    6HRUGRQHD]PXOLPHDPHVDMHORUVXUVHL6vQRUGLQHDGHVFUHVFWRDUHDSUREDELOLWLORU

    RELQkQGX-VH DVWIHO PXOLPHD RUGRQDW ={ }, cu p( ) p( ) ... p( ), cu

    VFKLPEDUHDHYHQWXDODLQGLFLORUPHVDMHORUSHQWUXUHDOL]DUHDRUGRQULLUHVSHFWLYH

    6HUHXQHVFXOWLPHOHGRXPHVDMHGHSUREDELOLWLOHFHOHPDLPLFLvQWU-un nou mesaj,

    notat cu FUXLD L VH DORF R SUREDELOLWDWH HJDO FX VXPD SUREDELOLWLORU PHVDMHORU

    FRPSRQHQWH 6H RUGRQHD] GLQ QRX PHVDMHOH vQ RUGLQHD GHVFUHVFWRDUH D SUREDELOLWLORU

    IRUPkQGX-VHDVWIHOSULPDVXUVUHVWUkQV ={ cu p( ) p( ) ... p( ) ...

    .

    6H UHXQHVF XOWLPHOH GRX PHVDMH GLQ VXUVD UHVWUkQV vQWU-un nou mesaj , de

    SUREDELOLWDWH HJDO FX VXPD SUREDELOLWLORU PHVDMHORU FRPSRQHQWH 6H RUGRQHD] PHVDMHOH vQordine GHVFUHVFWRDUHIRUPkQGX-VHDVWIHOVXUVDUHVWUkQV QPRG analog, din VHIRUPHD]

    VXUVDUHVWUkQV LDDPDLGHSDUWH SkQFkQGVHRELQHRVXUVUHVWUkQV IRUPDWQXPDLGLQ

    GRX mesaje, , cu p( ) . De fapt, va fi i va fi sau invers.

  • 29

    'LQPRGXOGHIRUPDUHDVXUVHORUUHVWUkQVH UH]XOWFPXOLmea S a mesajelor poate fi

    SDUWLLRQDWvQGRXVXEPXOLPL L DVWIHOvQFkWSUREDELOLWLOHS ) i sunt cele

    PDL DSURSLDWH SRVLELO/D UkQGXO ORU VXEPXOLPLOH L SRW IL SDUWLLRQDWH vQ DOWH GRXVXEPXOLPLGHSUREDELOLWLOHFHOHPDLDSURSLDWHSRVLELO3DUWLLRQULOHVHFRQWLQXSkQVHRELQ

    VXEPXOLPLFDUHFRQLQXQVLQJXUPHVDM

    &XYLQWHOHGHFRGFRUHVSXQ]WRDUHILHFUXLPHVDMVHRELQDVWIHO

    - VXEPXOLPii LVHDORFVLPEROXOVDX

    - VXEPXOLPLL LVHDORFVLPEROXOVDX

    - ODILHFDUHSDUWLLRQDUHVHDORFDUELWUDUFHORUGRXVXEPXOLPLVDXRSHUDLDFRQWLQXkQGX-

    VHSkQVHRELQVXEPXOLPLFHFRQLQXn singur mesaj , k= .

    'HRDUHFHDORFDUHDOXLLHVWHDUELWUDUODILHFDUHSDUWLLRQDUHUH]XOWFXQHLVXUVH

    S LVHSRWDWDDRPXOWLWXGLQHGHFRGXUL LQVWDQWDQHHWRDWHvQVDYkQGDFHHDL OXQJLPHPHGLHDcuvintelor de coGFDUHQXPDLSRDWHILPLFRUDWSULQQLFLXQDOWSURFHGHXGHFRGDUHDPHVDMHORU

    luate individual.

    'DFVXUVDSULPDUS poate furniza N PHVDMHDWXQFLVXEPXOLPHDUHVWUkQV , va avea

    N- PHVDMH VXEPXOLPHD UHVWUkQV YD FRQine N- PHVDMH L DD PDL GHSDUWH XOWLPD

    VXEPXOLPHUHVWUkQV YDFRQLQHN n mesaje, care sunt L DGLFVHSRDWHVFULH N-n=2 => n=N-2 (2.16)

    'DFVXEPXOLPLL LVHDORFVLPEROXOLVXEPXOLPLL simbolul "1", celor N-2

    SDUWLLRQUL SXWkQGX-li-VH DORFD DUELWUDU VDX UH]XOW XQ WRWDO GH SRVLELOLWL GH

    FRGDUH'DF vQVVXEPXOLPLL L VHDORFVLPEROXO LDUVXEPXOLPLL simbolul "0",

    PDLUH]XOW SRVLELOLWLGHFRGDUH5H]XOWGHFL FSULQDFHVWSURFHGHXGHFRGDUHVHSRW

    realiza FRGXUL LQVWDQWDQHH WRDWHDYkQG WRDWHDFHHDL OXQJLPHPHGLHD

    cuvintelor de cod.

    3ULQGHILQLLHVHQXPHWHFRGFRPSDFWFRGXOFDUHUHDOL]HD]OXQJLPHDPHGLHPLQLPD

    FXYLQWHORUGHFRG'HRDUHFHSULQSURFHGHXOGHFRGDUH+XIIPDQVHRELQHFHDPDLPLFOXQJLPH

    PHGLH D FXYLQWHORU GH FRG vQVHDPQ F SULQ DFHVW SURFHGHX VH RELQ FRGXUL LQVtantanee

    FRPSDFWH(YLGHQWXQFRGDEVROXWRSWLPDOHVWHLFRPSDFWUHFLSURFDQHILLQGWRWGHDXQDYDODELO

  • 30

    Exemplul 3.1. 6HSUHVXSXQHVXUVDGLVFUHWGHLQIRUPDLHFDUDFWHUL]DWGHGLVWULEXLD

    S :

    &RGDUHDELQDU+XIIPDQDDFHVWHLVXUVHVHSRate realiza astfel:

    Fig. 3.2. Schema de codare pentru exemplul 3.1

    Graful i cuvintele de cod corespunztoare codrii efectuate sunt date vn Fig. 3.3.

    Fig.3*UDIXOFRUHVSXQ]WRUFRGXOXL

  • 31

    &RGXULOH +XIIPDQ GH GLVSHUVLH PLQLP VH RELQ FkQG OD UHRUGRQDUHD VXUVHL UHVWUkQVH

    VLPEROXOFRPSXVVHSODVHD]SHSR]LLDFHDPDLGHVXVSRVLELO vQVXUVDUHVWUkQVQIHOXODFHVWD

    FXYkQWXOGHFRGDWULEXLWVLPEROXOXLFRPSXVYDDYHDFHDPDLPLF OXQJLPHSRVLELO&XPDFHVW

    FXYkQW YD GHYHQL SUHIL[ SHQWUX VLPEROXULOH FRQVWLWXHQWH FXYLQWHOH GH FRG FRUHVSXQ]WRDUH

    DFHVWRUDYRUDYHDROXQJLPHFXRXQLWDWHPDLPDUHGHFkWOXQJLPHDSUHIL[XOXLGHFLLDFHVWHDYRU

    UH]XOWD GH OXQJLPH PLQLP &D XUPDUH GLIHUHQHOH GLQWUH OXQJLPLOH FXYLQWHORU GH FRG GHYLQ

    minime, ceea ce va cRQGXFHHYLGHQWLODRGLVSHUVLHPLQLP

    3HQWUX IL[DUHD LGHLORU VH SUHVXSXQH VXUVD GLVFUHW GH LQIRUPDLH FDUDFWHUL]DW GH

    GLVWULEXLD

    S :

    3HQWUX DFHDVW VXUV VH HIHFWXHD] FRGDUHD +XIIPDQ SODVkQG vQWkL PHVDMHOH VXUVHL

    UHVWUkQVHSHSR]LLLOHFHOHPDLMRVSRVLELOHvQOLVWLDSRLSHSR]LLLOHFHOHPDLGHVXVSRVLELOHQ

    SULPXOFD]UH]XOWVFKHPDGHFRGDUHGLQ)LJLDU JUDIXOLFXYLQWHOHGHFRGFDvQ)LJ

  • 32

    3HQWUXDFHVWFRGOXQJLPHDPHGLHLGLVSHUVLDVXQW

    3HQWUXFD]XOvQFDUHvQFRGDUHD+XIIPDQPHVDMHOHVXUVHLUHVWUkQVHVHSODVHD]SHSR]LLLOH

    FHOHPDLGHVXVvQOLVWVHRELQHVFKHPDGHFRGDUHGLQ)LJLJUDIXOLFXYLQWHOHGHFRGFDvQ

    Fig. 3.7.

  • 33

    Pentru acest cod, lungimea medie este, evideQWDFHHDLvQWLPSFHGLVSHUVLDGHYLQH

    'HL GLQ SXQFW GH YHGHUH LQIRUPDLRQDO FHOH GRX FRGXUL VXQW LGHQWLFH vQ SUDFWLF VH

    SUHIHU IRORVLUHD FHORU GH GLVSHUVLH PLQLP GLQ PRWLYH GH WUDQVPLVLH 'H H[HPSOX GDF VH

    GRUHWHVVHWUDQVPLWPHVDMHDOH VXUVHLFXRYLWH]GHPHVDMHVHFHVWHQHFHVDUXQFDQDO

    FXFDSDFLWDWHDGHELLVHF'HRDUHFHYLWH]DGHJHQHUDUHDELLORURVFLOHD]vQMXUXOYDORULL

    GHELLVHFIXQFLHGHVXFFHVLXQHDGHPHVDMH IXUQL]DWH ODXQPRPHQWGDW LHLUHDVursei

    HVWHvQFUFDW vQWU-un buffer.

    'DFGHH[HPSOXVXUVDJHQHUHD]ODXQPRPHQWGDWLUXULGHPHVDMH L mai multe

    VHFXQGHSHQWUXSULPXOFRGVHJHQHUHD]ELLVHFLvQILHFDUHVHFXQGDUWUHEXLXQEXIIHU

    de capacitatHGHELL&XDOGRLOHDFRGVHJHQHUHD]ELLVHFLEXIIHUXODUWUHEXL

    V DLE FDSDFLWDWHD GH ELL 'DF VH WUDQVPLW LUXUL GH PHVDMH , cu primul cod se

    JHQHUHD]ELLVHFLFDQDOXOQXHIRORVLWODFDSDFLWDWHDVDUPkQkQGXQGHILFLWGH

    ELLVHF SH FkQG FX DO GRLOHD FRG VH JHQHUHD] ELLVHF GHILFLWXO H[LVWHQW vQ H[SORDWDUHD

    FDQDOXOXLILLQGQXPDLGHELLVHF$DGDUGLQPRWLYHGHWUDQVPLVLHHVWHPDLUH]RQDELODVH

    DOHJHDOGRLOHDFRGGHFkWSrimul.

  • 34

    1.53URFHGHXOGHFRGDUHELQDU6KDQQRQ Fano. $FHVW SURFHGHX VH DSOLF GH RELFHL vQ FD]XULOH SDUWLFXODUH vQ FDUH SUREDELOLWLOH GH

    IXUQL]DUHDOHPHVDMHORUVXQWSXWHULvQWUHJLSR]LWLYHDOHOXLDGLFGHIRUPD

    p( = , ( ) k= (2.17)

    unde HVWHXQQXPUvQWUHJSR]LWLY'DFUHODLDHVWHVDWLVIFXWPXOLPHDS = {s1, s2

    ,..., sN} DPHVDMHORUVXUVHLGLVFUHWHGHLQIRUPDLHFHXUPHD]DILFRGDWSRDWHILSDUWLLRQDW vQGRXVXEPXOLPL L DVWIHO vQFkWVXPDSUREDELOLWLORUPHVDMHORU LQFOXVH vQ QRWDWFX

    p( ) V ILHHJDOFXVXPDSUREDELOLWLORUPHVDMHORU LQFOXVH vQ QRWDWFXp( ). Sursa S ILLQGWRWGHDXQDFRPSOHWVHSRDWHVFULH

    (2.18)

    6XEPXOLPLOH L VHSRWSDUWLLRQDODUkQGXOORU vQ L UHVSHFWLYvQ L

    DVWIHO vQFkWVXPDSUREDELOLWLORUPHVDMHORU LQFOXVHvQFHOHSDWUXVXEPXOLPLVILHDFHHDL

    DGLFVHSRDWHVFULHUHODLD

    (2.19)

    6HSURFHGHD] vQPRGDQDORJSkQVHRELQVXEPXOLPLFDUHFRQLQXQVLQJXUPHVDM6H

    REVHUY F ILHFDUH VXEPXOLPH DUH VXPD SUREDELOLWLORU PHVDMHORU LQFOXVH HJDO FX R SXWHUH

    vQWUHDJDOXL3XWHUHDvQWUHDJHVWHHJDOFXQXPUXOLQGLFLORUVXEPXOLPLLUHVSHFWLYH'DF

    VXEPXOLPHDFRQLQHXQVLQJXUPHVDM LDUHXQQXPUGHLQGLFLHJDOFX , atunci se poate

    scrie:

    GH XQGH UH]XOW QHFHVLWDWHD FD VXUVD S FH XUPHD] D IL FRGDW V-L IXUQL]H]H PHVDMHOH FXSUREDELOLWLHJDOHFX ODRSXWHUHvQWUHDJSR]LWLY

    6XUVDILLQGFRPSOHWVHSRDWHVFULH relaia (1.21):

  • 35

    (2.21)

    QORFXLQGvQUH]XOWUHODia (1.22):

    (2.22)

    FHHDFHvQVHDPQFLQHJDOLWDWHDOXLKraft GHYLQHvQDFHVWFD] egalitate.

    &XYLQWHOHGHFRGVHYRURELQe, atunci, astfel:

    6HDWULEXLHVLPEROXOVXEPXOLPLL LVLPEROXOVXEPXOLPLL , (sau invers),

    DVWIHO F WRDWH FXYLQWHOH FRUHVSXQ]WRDUH PHVDMHORU LQFOXVH vQ YRU vQFHSH FX L WRDWH

    FXYLQWHOHFRUHVSXQ]WRDUHPHVDMHORULQFOXVHvQ , vor

    vQFHSHFXVDXLQYHUV

    6H DORF VXEPXOLPLORU L FD DO GRLOHD PHVDM LDU VXEPXOLPLORU L

    FD DO GRLOHD PHVDM VDX LQYHUV Q IHOXO DFHVWD FXYLQWHOH GH FRG FRUHVSXQ]WRDUH

    PHVDMHORULQFOXVHvQ YRUvQFHSHFXFXYLQWHOHGHFRGFRUHVSXQ]WRDUHPHVDMHORULQFOXVHvQ

    YRUvQFHSHFXLDDPDLGHSDUWHFXYLQWHOHGHFRGFRUHVSXQ]WRDUHPHVDMHORU LQGXVHvQ

    vor vQFHSHFX

    2SHUDLDVHFRQWLQXvQDFHODLPRGSkQFkQGvQILHFDUHVXEPXOLPHUPkQHXQVLQJXU

    PHVDM FUXLD vL YD FRUHVSXQGH FXYkQWXO GH FRG IRUPDW GLQ LUXO GH LQGLFL DL VXEPXOLPLL

    UHVSHFWLYH'HRDUHFH OD ILHFDUH SDUWLLRQDUH vQ GRX VXEPXOLPL DWULEXLUHDPHVDMHORU L

    HVWHDUELWUDU UH]XOWFSULQDFHVWSURFHGHXVHSRWRELQHRPXOWLWXGLQHGHFRGXUL LQVWDQWDQHH

    dar toate absolut optimale.

    QSULQFLSLXSURFHGHXOGHFRGDUHGHVFULVV-DUSXWHDDSOLFDvQJHQHUDODGLFLDWXQFLFkQG

    relaLDQXHVWHVDWLVIFXWQDFHVWFD]SDUWLLRQULOHvQVXEPXOLPLWUHEXLHHIHFWXDWHDVWIHO

    vQFkWVXPDSUREDELOLWLORUPHVDMHORULQFOXVHvQVXEPXOLPLOHUHVSHFWLYHVILHFkWPDLDSURSLDWH

    $WULEXLQGVLPEROXULOHLFDvQSURFHGHXOGHVFULV VHRELQWRWGHDXQDFRGXULLQVWDQWDQHH

    &XFkWVXPHOHSUREDELOLWLORUPHVDMHORUFRPSRQHQWHDOHVXEPXOLPLORUUHVSHFWLYHYRUIL

    PDLDSURSLDWHFXDWkWOXQJLPHDPHGLHDFXYLQWHORUGHFRGYDILPDLPLF

  • 36

    Exemplul 3.2. 6HFRQVLGHUVXUVDGLVFUHWGHLQIRUPDLHFDUDFWHUL]DWGHGLVWULEXLD

    S :

    3URFHGHXOGHFRGDUHELQDU6KDQQRQ- )DQRHVWHVLQWHWL]DWvQWDEHOXOGHPDLMRV

    Graful arborescent ataat codului astfel obLQXWHVWHUHSUH]HQWDWvQ)LJ

  • 37

    $SOLFDLH

    Simularea cu ajutorul programului MATLAB a algoritmului de compresie Shannon-Fano

    Q FDGUXO OXFUULORU GH ODERUDWRU YD IL SXV OD GLVSR]LLH R DSOLFDLH VRIWZDUH care LPSOHPHQHD]DOJRULWPXOGHFRPSUHVLH6KDQQRQ-)DQR(FUDQXODSOLFDLHLHVWHSUH]HQWDWvQILJXUDXUPWRDUH

    ExerciLLUH]ROYDWH Exemplu QWDEHOXOGHPDLMRVVXQWSUH]HQWDWHSDWUXFRGXULVHSDUDELOH,

    mesaj A B C D s0 00 0 0 0 s1 01 10 01 10 s2 10 110 011 110 s3 11 1110 0111 111

  • 38

    Folosind codul B, succesiunile s ss s3 1 0 2 se codifica 1110100110. Dupa receptinarea primelor sase biti se poate determina ca s-a receptionat s s3 1 . Daca Insa se folosec codul C, succesiunea s ss s3 1 0 2 se codifica 011010011. Dupa receptionarea primelor sase biti conduce la decodarea s3 dar secventa 01 poate fi interpretata la acel moment fie care s1 fie ca, s2 fie ca s3 , ambiguitatea UH]ROYkQGX-se abia dupa receptia urmatorilor biti. Un cod de tip C se numeste cod instantaneu. &RQGLWLDQHFHVDUDVLVXILFLHQWDFDXQFRGVDILHLQVWDQWDQHXHVWHFDQLFLXQFXYkQWGHFRGVDQXILHSUHIL[DODOWXLFXYkQWGHFRGFRQGLWLDGHSUHIL[

    Se considera sursa care genereaza simbolurile : - s0 cu probabilitatea p1 = 0,5 - s1 cu probabilitatea p2 = 0,25 - s2 cu probabilitatea p3 = 0,125 - s3 cu probabilitatea p4 = 0,125 Se cere sa se determine eficienta codurilor A, B, C si D

    Solutie Entropia sursei este

    H p pi ii

    log log log log21

    4

    2 212

    1214

    142 18

    18

    74

    biti

    Pentru codul A lungimea medie a codului este nA 2 si K UA iar 74

    2 278

    122log

    Codurile B si C cu aceiasi lungime medie

    n nB C 0 5 1 0 25 2 0125 3 0125 4 1875, , , , ,

    K K

    U U

    B C

    B C

    1 751 875

    1415

    115

    ,,

    Codul D are nD 0 5 1 0 25 2 0125 3 1 75, , , , si

    K UD D 1 75

    1 75 21 0

    2

    ,, log

  • 39

    TESTE DE AUTOEVALUAR(,7(0('(&21752/ Testul nr. 1

    1. 6HGVXUVD$SULQXUPDWRDUHDUHSDUWLLHGHSUREDELOLWL

    02.002.002.004.007.007.014.014.048.0987654321 aaaaaaaaaA

    6 VH FRGLILFH VXUVD $ XWLOL]kQG PHWRGD GH FRGLILFDUH +XIIPDQ L V VH FDOFXOH]H

    lungimea medie a cuvintelor de cod.

    Testul nr. 2

    2. 6HGVXUVD$SULQXUPDWRDUHDUHSDUWLLHGHSUREDELOLWL

    02.002.002.004.007.007.014.014.048.0987654321 aaaaaaaaaA

    6 VH FRGLILFH VXUVD$XWLOL]kQGPHWRGD GH FRGLILFDUH6KDQQRQ-)DQR L V VH FDOFXOH]H

    lungimea medie a cuvintelor de cod.

    7HPGHFRQWURO 6HFRQVLGHURVXUVFXDOIDEHWXO > @ > @654321 ,,,,, ssssssS LSUREDELOLWile

    > @ > @2.0,1.0,25.0,3.0,1.0,05.0 P : a. V VH GHWHUPLQH XQ FRG FRPSDFW IRORVLQG DOJRULWPXO GH FRGDUH +XIIPDQ GDF

    alfabetul codului este > @ > @1,0 X LGDFDOIDEHWXOFRGXOXLHVWH > @ > @2,1,0 X ; b. SHQWUX FHOH GRX FD]XUL V VH FDOFXOH]H OXQJLPHD PHGLH D FXYLQWHORU GH FRG i

    eficiena codului.

  • 40

    BIBLIOGRAFIE RECOMAN'$7/$02'8/8/ >@$6SWDUX7HRULD7UDQVPLVLunii InformaLHL(G'LGDFWLFL3HGDJRJLF%X- cureti,

    1983. >@$70XUJDQ,6SkQX,*DYW,6]WRMDQRY9(1HDJRH$9ODG7HRULD

    Transmisiunii Informaiei - SUREOHPH(G'LGDFWLFL3HGDJRJLF%XFXUHti, 1983

    [3] I. AngheloiX7HRULDFRGXULORU(G0LOLWDU%XFXUHti, 1972. [4] J.C. Moreira, P.G. Farrell, ESSENTIALS OF ERROR-CONTROL CODING, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England,2006. >@90XQWHDQX7UDQVPLWHUHDLFRGLILFDUHDLQIRUPDLHL1RWHGHFXUV

  • 41

    MODULUL 3 CODURI DETECTOARE ,&25(&72$5( DE ERORI

    Q FD]XO WUDQVPLVLLORU OD GLVWDQH UHODWLY PDUL SULQ DSDULLD LQHUHQW D

    SHUWXUEDLLORU R SDUWH GLQ VLPEROXULOH GLQ DOIDEHWXO FRGXOXL FH IRUPHD]FXYLQWHOH GH FRG DWDDWH PHVDMHORU SRW IL PRGLILFDWH DVWIHO vQFkW FHHD FH VHUHFHSLRQHD] QX PDL FRUHVSXQGH FX FHHD FH V-D WUDQVPLV 'HRDUHFH vQ PDUHDPDMRULWDWH D VLWXDLLORU SUDFWLFH VH IRORVHWH FD DOIDEHW DO FRGXOXL QXPDL L XRUGHUHDOL]DWYRPFRQVLGHUDvQFRQWLQXDUHGRDUDFHVWFD]QVLWXDLD vQFDUHDOIDEHWXOFRGXOXLHVWHQXPDLLGDWRULWSHUWXUEDLLORUFRGXOXLXQWUDQVPLVSRDWHGHYHQLLLQYHUV'LQDFHDVWFDX]VHVSXQHFSHUWXUEDLLOHFDUHDSDUDXun caracter aditiv.

    0 1

    0 1

    0 1 1 0

    'DFVHWUDQVPLWHLVHUHFHSLRQHD] SHUWXUEDLD 1 = 1. 'LQFRGDUHDPHVDMHORUVXUVHORUSHQWUXFDQDOHFXSHUWXUEDLLVHSXQGRXprobleme:

    1. GHWHFLDHURULORU 2. FRUHFLDDXWRPDWDHURULORU

    1 codarea trebuie astfel efecWXDW vQFkW OD UHFHSLH VSXWHPGHFLGH GDFceea ce s-D UHFHSLRQDW HVWH FRUHFW VDX HURQDW IU SUHWHQLD GH D VWDELOL LORFXULOHvQFXYkQWXOGHFRGvQFDUHV-au introdus erori.

    2 FRGDUHD WUHEXLHDVWIHOHIHFWXDW vQFkW ODUHFHSLHVDYHPSRVLELOLWDtea QXQXPDLDGHFLGHGDFFHHDFHV-DRELQXWHVWHFRUHFWFLLGHDFRUHFWDDXWRPDWHURULOHFDUHDXDSUXWSHFDQDO 3UREOHPDGHWHFLHLHURULORUHVWHPDL VLPSO, vQ VFKLPEQHFHVLW XQFDQDOGHWUDQVPLVLXQLFXGXEOXVHQVGHRDUHFHRULGHFkWHRULODUHFHSLHVHGHWHFWHD]SUH]HQD HURULORU V H[LVWH SRVLELOLWDWHD FHUHULL GH UHWUDQVPLVLH D FXYkQWXOXLUHFHSLRQDW HURQDW 6H FHUH WUDQVPLWHUHD FXYkQWXOXL UHFHSLRQDW HURQDW SkQ FHDFHVWDHVWHUHFHSLRQDWFRUHFWUH]XOWRvQWkU]LHUHODUHFHSLRQDUHDLQIRUPDLHL QVFRSXO vQWRFPLULLFRGXULORUGHWHFWRDUHGHHURULVDXFRUHFWRDUHGHHURULVH IRORVHVF R VHULH vQWUHDJ GH FRGXUL ED]DWH SH GLIHULWH WHRULL PDWHPDWLFH RSULPFODVLILFDUHFRQVWkQGvQ coduri bloc ODFDUHILHFDUHFXYkQWGHFRGDUHDFHHDLOXngime coduri nonbloc (sau recurente) OD FDUH WUDQVPLVLD VH IDFH FXUVLY IU RGHOLPLWDUHSUHFLVDFXYkQWXOXLGHFRG

  • 42

    MODULUL 3

    CAPITOLUL 1

    &2'85,'(7(&72$5(,&25(&72$5( DE ERORI

    3.1. Codarea si decodarea pe canale perturbate S-a aratat anterior ca performanta globala a unui sistem de transmitere de date este probablitatea de eroare.

    7UDQVPLWHUHDvQEDQGDGHED]DVDXPRGXODWLDVXQWDIHFWDWHGHRVHULHGHFRQVWUkQJHULcare fac uneori imposibila obtinerea unei probabilitati de eroare prescrise. Calea prin care se poate obtine probabilitatea de eroare prescrisa este folosirea redundantei controlate. Blocurile functionale care efectueaza aceasta sarcina sunt codorul si decodorul canalului.

    &RGRUXO FDQDOXOXL DGDXJD vQ PRG VLVWHPDWLF ELWL OD PHVDMXO transmis. Acesti biti aditionali, desi nu transporta informatie, fac posibili detectia si corectia erorilor.

    Detectia erorilor si/sau corectia lor coboara probabilitatea de eroare. Problema codarii pe canale perturbate poate fi formulata astfel. Referindu-ne la figura 5.1 sistemul digital de comunicatie urmareste transmiterea iesirii codorului sursei ^ `bk cu un debit rb pe un canal zgomotos.

    Datorita zgomotului fluxului de date receptionate ^ `bk difera uneori de secventa transmisa ^ `bk .

    Se impune ca probabilitatea de eroare P b bk k z VD ILHPDLPLFDGHFkWRDQXPLWDvaloare.

    Codorul canalului si decodorul canalului au ca scop reducerea probabilitatii globale de eroare.

    &RGRUXO vPSDUWHELWLPHVDMXOXL vQEORFXULGHFkWH k ELWLVL vQORFXLHVWHILHFDUHEORFFXXQFXYkQWGHFRGGH n ELWLDGDXJkQG n k ELWL'HFRGRUXOSULPHVWHFXYkQWXOGHFRGFDUHeste uneori DOWHUDWVLvQFHDUFDVDGHFRGH]HFHL k biti ai mesajului.

    Desi biti de control nu aduc nici o informatie receptorului, ei permit decodorului sa GHWHFWH]HVLVDFRUHFWH]HHURULOHGHWUDPVPLWHUHUHGXFkQGSULQDFHDVWDSUREDELOLWDWHDGHeroare.

    3URLHFWDUHDXQXLFRGRUGHFRGRUFRQVWDvQVHOHFWDUHDUHJXOLORUGHJHQHUDUHDFXYLQWHORUde cod pornind de la blocurile mesaj si apoi de extragere a blocurilor mesaj din versiunea receptionaWDGHFXYkQWGHFRG

    QILJXUD.1 este prezentata schema bloc pentru un sistem de codare/decodare.

  • 43

    &RGXULOH FDUH HIHFWXHD]D FRQWUROXO HURULL VXQW FODVLILFDWH vQ FRGXUL EORF VL FRGXULconvolutionare. Din codurile bloc, unui mesaj de k biti i se asocieaza XQFXYkQWGHFRGGHn biti care actioneaza r biti pe baza celor k biti cu continut informational. La receptie biti de control sunt utilizati pentru a verifica biti de informatie din blocul precedent. Pentru codurile FRQYROXWLRQDUHELWLGHFRQWURO VXQW vQPRGFRQWLQXX LQVHUDWL vQWUHELWLGH LQIRUPDWLH ELWLGHFRQWURO YHULILFkQG QX QXPDL ELWL GH LQIRUPDWLH GLQ EORFXO SUHFHGHQW FL VL GLQ DOWH EORFXULanterioare. 'LVWDQWD +DPPLQJ 'LVWDQWD vQtre doua cuvinte binare de lungime n u x x x v y y yn n 1 2 1 2, ,......, ; , ,......, $ ^ ` x yi i, , 01 este numarul pozitiilor GHDFHODVUDQJvQFDUHGRXDFXYLQWHGLIHUD

    d u v x yi ii

    n,

    1

    (3.1)

    Observatie Numarul natural d u v, verifica axiomele distantei

    ( ) , ,

    ( ) ,

    ( ) , , ,

    a d u v d v ub d u v u vc d u v d u w d w v

    t d

    0

    0 (3.2)

    Codor canal

    mesaj k

    mesaj control k n-k

    Modulator

    Canal

    FXYkQWGHFRG n

    mesaj k

    Decodor canal Demodulator

    rb

    r r nkc b

    Fig. 3.1

  • 44

    O reprezentare geometrica a lui u poate fi un punct de coordonate x xn1,...... In Rn . Cele 2n combinatii de n ELWL VXQW YkUIXULOH XQXL KLSHUFXE GH ODWXUD ,Q ILJXUDXUPWRDUHHVWHUHSUH]HQWDWXQDVWIHOGHFXESHQWUXR3 .

    'DFDWRDWHFXYLQWHOHGHFRGDXVHQVDWXQFLRULFHHURDUHFRQGXFH ODXQDOWFXYkQWGH

    cod si nu poatHILGHSLVWDWD'DFDvQVDVHSDUDPGLQFHOH 2n cuvinte de cod, numai 2k atunci este posibil sa se depisteze unele erori singulare deoarece 2n k FRPELQDWH QX DX VHQV QJHQHUDOILHXQFRGvQFDUH toate cuvintele sunt la distante mutuale de cel putin egale cu d0 . Cazul 1

    Conditia necesara si suficienta ca un cod binar sa poata corecta cel mult r erori este

    ca d r0 2 1t Cazul 2

    Daca d r0 2t se pot corecta cel mult r 1 erori.

    3.2. Coduri bloc liniare 6HFRQVLGHUDFRGXUL EORF vQFDUH ILHFDUH vQ ILHFDUHEORFGH k biti mesaj este codat vQWU-un bloc de n k! biti prin adaugarea de n k biti de control. Bitii de control sunt obtinuti pe baza celor k biti mesaj, aVDFXPHVWHLOXVWUDWvQILJXUD.3.

    000

    001 011

    111 010

    110 100

    101

    x1

    x3

    x2

    Fig 3.2

    Distanta Hamming vQWUHGRXDYkUIXULHVWHFHO mai mic numar de laturi care le unesc

  • 45

    Codor canal

    mesaj biti de control

    k biti k n k

    mesaj cod bloc

    Fig. 3.3

    Blocurile de n biti de la iesirea codorului canalului sunt numite cuvinte de cod VLFRGXULOHSHQWUXFDUHELLLPHVDMDSDUODvQFHSXWXOFXYkQWXOXLGHFRGVXQWQXPLWHFRGXUL

    VLVWHPDWLFH Q SOXV GDFD ILHFDUH GL FHOH 2k cuvinte de cod poate fi exprimat ca o combinatie lineara de k vectori independenti, atunci codul este si linear. &RGDUHDFRQVWDvQGRXDHWDSH VHFYHQWDGHELWLLQIRUPDWLRQDOLHVWHVHJPHQWDWHvQEORFXULPHVDMGHFkWH k biti. (2) codorul transforma fieFDUH EORF PHVDM vQWU-un bloc mai mare de n ELWL vQconformitate cu anumite reguli. Acesti n k biti aditionali sunt generati printr-o combinatie lineara de biti mesaj si operatiile pot fi descrise folosind matrice. Blocul mesaj este reprezentat printr-XQYHFWRUOLQLHDYkQG k componente

    > @ ^ ` D d d d cu d i kk i 1 2 01 1...... , ; , (3.3) )LHFDUHEORFPHVDMHVWHWUDQVIRUPDWvQWU-XQFXYkQWGHFRGc de lungime n > @C c c cn 1 2 ...... Se observa ca eficienta acestui cod este k n . Pentru un cod linear, sistematic primii k ELWL DL FXYkQWXOXL GH FRG VXQW ELWLL PHVDMadica

    c d i ki i 1 2, ,......, (3.4)

    Ultimii n k ELWLDLFXYkQWXOXLGHFRGVXQWELWLLGHFRQWUROJHQHUDWLLSHED]DFHORU k ELWLDLPHVDMXOXLvQFRQIRUPLWDWHFXDQXPLWHUHJXOLSUHGHWHUPLQDWH

    mesaj

  • 46

    c p d p d p d

    c p d p d p d

    k k k

    n n k n k k n k k

    1 11 1 21 2 1

    1 1 2 2

    ,

    , , ,

    (3.5)

    Coeficientii pi j, din ecuatiile (3.5) sunt booleene iar sumarea se face modulo -2. Ecuatiile (3.4) si (3.5) pot fi combinate sub o forma matriceala

    > @ > @c c d d

    p p pp p pp p p

    p p p k n

    n k

    n kn kn k

    k k k n k

    1 1

    11 12 1

    21 22 2

    31 32 3

    1 2

    1000 00100 00010 0

    000 01

    ... ...

    ... ...

    ... ...

    ... ...

    ... ...

    ,

    ,

    ,

    , ,

    u

    (3.6)

    sau C D G (3.7) unde G este o matrice de tip k nu numita matricea generatoare a codului si are forma > @G I Pk k n u (3.8)

    Matricea I k este matricea unitate de ordinul k iar P este o matrice arbritara k n ku . Sa remarcam ca specificarea lui P defineste complet codul bloc n k, .

    Proiectarea unui cod bloc n k, prin selectarea unei matrici P trHEXLH VD DLED vQvedere urmatoarele proprieteti - comoditatea implementarii - capacitatea de a corecta erorile singulare si pachetele de erori (burst errors) - eficienta codului da fie ridicata

    Prin eficienta codului se Intelege raportul kn pentru o anumita capacitate de

    detectie/corectie. Trebuie mentionat ca nu exista o procedura de selectie a matricei P care sa satisfaca toate proprietatile de mai sus.

    3.3. Exemple de coduri liniare Codul Hamming

    Cele mai cunoscute coduri liniare sint codurile binare Hamming . Ele se dau cu ajutorul matricei de control H, care este formata din m linii si m2 - 1 coloane, lar coloanele sunt toate elementele nenule de lungime m. Spatiul nul al acestei matrice are distanta minima egala 3, adica este un cod (n k) ce corecteaza o eroare si are urmatoarele caracteristici:

  • 47

    - lungimea combinatiilor de cod este n = 2m -1; - numarul simbolurilor de control este r=n - k ; -numarul simbolurilor informationale este k

    Codul Reed-Muller Reprezinta o categorie de coduri liniare care se deosebesc in mod esential de clasa

    codurilor liniare prin algoritmul de codificare si decodificare (codul Hamming , coduri simetrice pe k pozitii) .

    La acest cod, spre deosebire de codurile simetrice algoritmul de decodificare nu poate fi etapizat, atat detectia, corectia, cat si decodificarea propriu-zisa se produc simultan, rezultand in urma algoritmului, in mod direct simbolurile informationale continute in cuvantul de cod receptionat.

    Lungimea n a coduluLHVWHRSXWHUHDOXLDGLFQ m3HQWUXUQXPUvQWUHJSR]LWLYQXPUXOSR]LLLORULQIRUPDLRQDOHHVWH

    0

    rim

    ik C

    (3.8) 1XPUXOVLPEROXULORUGHFRQWUROHVWHGDWGHUHODLD

    1

    11 ...m

    m m rn k C C (3.9) 'LVWDQDPLQLP+DPPLQJHVWHG m-r

    La codul Reed-Muller, spre deosebire de cele sistematice, algoritmul de decodificare nu poate fi etapizat, adica atat detectia cat si corectia si decodificarea propriu-zisa, se produc simultan, rezultand in urma algoritmului in mod direct simbolurile informationale detinute din codul receptionat. Fie Vn un spatiu vectorial peste GF(2), ndimensionali avand componentele 0 sau 1. )LHX DDDDQVLY EEEEQSHVSDWLXOYHFWRULDO9QVHSRDWHGHILQLSURGXVXO

    YHFWRULDO X [ 9 DE DEDQEQ VL SURGXVXO VFDODU x ii baVu&&* si

    )2(* GFVu &&

    . Se pot observa urmatoarele :

    x produsul scalar este nul daca ponderea produsului vectorial este un numar par ; x fata de operatiile descrise, multimea vectorilor de n elemente formeaza o algebra

    liniara, asociativa si comutativa. Codul Reed-Muller se poate defini cu urmatorii parametrii :

    x n=2m, unde n este dimensiunea vectorilot cuvintelor de cod ;

    x

    r

    k

    knCk

    0 , unde k este numarul de simboluri informationale din cod ; x d=2m-r, unde d este distanta minima a codurilor ; x

    121 ...1 rnmmm CCCkn , pentru care se defineste codul RM(m,r) ;

    x

    21dt

    unde t este numarul de erori pe care il poate corecta codul RM(m,r). Un cod Reed-Muller de ordinul r avand lungimea cuvintelor de cod 2m este un subspatiu vectorial, generat de urmatorii vectori liniari independenti care constituie matricea generatoare : 9 9P

  • 48

    Vm- Vm x Vm- (3.10) 9[9 Vr x Vr-[9 Algoritmul de codificare presupune produsul dintre mesajul informational X=a1xk x Gkxn. Codul Reed-Muller (5,2) Folosind relatiile generale ale codului Reed-Muller(m,r) ne rezulta urmatoarele valori : m=5 ; r=2 ; n=32 ; k=16 ; n-k=16 ; d=8 ; t=3, de aici rezulta ca putem corecta maxim 3 erori pe cuvant. Matricea V pentru RM(5,2) este :

    (1111 1111 1111 1111 1111 1111 1111 1111){V0} (0000 0000 0000 0000 1111 1111 1111 1111){V5} (0000 0000 1111 1111 0000 0000 1111 1111){V4} (0000 1111 0000 1111 0000 1111 0000 1111){V3} (0011 0011 0011 0011 0011 0011 0011 0011){V2} (0101 0101 0101 0101 0101 0101 0101 0101){V1} (0000 0000 0000 0000 0000 0000 1111 1111){V54} (0000 0000 0000 0000 0000 1111 0000 1111){V53} (3.11) (0000 0000 0000 0000 0011 0011 0011 0011){V52} (0000 0000 0000 0000 0101 0101 0101 0101){V51} (0000 0000 0000 1111 0000 0000 0000 1111){V43} (0000 0000 0011 0011 0000 0000 0011 0011){V42} (0000 0000 0101 0101 0000 0000 0101 0101){V41} (0000 0011 0000 0011 0000 0011 0000 0011){V32} (0000 0101 0000 0101 0000 0111 0000 0101){V31} (0001 0001 0001 0001 0001 0001 0001 0001);{V21}

    Se defineste GxmX&&& unde m=(a0 a5 a4 a3 a2 a1 a54 a53 a52 a51 a43 a42 a41 a32 a31

    a21). Algoritmul de decodificare se bazeaza pe relatii de control. Pentru a scrie relatiile de control pentru fiecare componenta a vectorului mesaj informational, se va analiza V, incepand de la ultima linie V21, spre prima linie V0, pentru a identifica numarul componentelor diferite de zero din fiecare linie a matricii. Pentru fiecare componenta nenula din liniile matricii vom scrie cate un set de relatii de control corespunzator componentei informationale din mesajul transmis care are acelasi indice cu vectorul analizat. Mesajul informational este :

    a1 xk=(a0 a5 a4 a3 a2 a1 a5 4 a5 3 a5 2 a5 1 a4 3 a4 2 a4 1 a3 2 a3 1 a2 1). Pentru determinarea lui aij se folosesc urmatoarele sisteme, apeland la logica majoritara. Sumele din sistem sunt modulo2. Se calculeaza valoarea pentru fiecare aij si aij este valoarea majoritara din sistem :

    321021 yyyya

    765421 yyyya

  • 49

    11109821 yyyya

    1514131221 yyyya

    1918171621 yyyya

    2322212021 yyyya

    2726252421 yyyya

    3130292821 yyyya Iar a21 este valoarea majoritara a sistemului.

    541031 yyyya

    763231 yyyya

    13129831 yyyya

    1514111031 yyyya

    2120171631 yyyya

    2322191831 yyyya

    2928252431 yyyya

    3130272631 yyyya Iar a31 este valoarea majoritara a sistemului.

    642032 yyyya

    753132 yyyya

    141210832 yyyya

    151311932 yyyya

    2220181632 yyyya

    2321191732 yyyya

    3028262432 yyyya

    3129272532 yyyya Iar a32 este valoarea majoritara a sistemului.

    981041 yyyya

    11103241 yyyya

    13125441 yyyya

    15147641 yyyya

  • 50

    2524171641 yyyya

    2726191841 yyyya

    2928212041 yyyya

    3130232241 yyyya Iar a41 este valoarea majoritara a sistemului.

    1082042 yyyya

    1193142 yyyya

    14126442 yyyya

    15137542 yyyya

    2624181642 yyyya

    2725191742 yyyya

    3028222042 yyyya

    3129232142 yyyya Iar a42 este valoarea majoritara a sistemului.

    1284043 yyyya

    1395143 yyyya

    14106243 yyyya

    15117343 yyyya

    2824201643 yyyya

    2925211743 yyyya

    3026221843 yyyya

    3127231943 yyyya Iar a43 este valoarea majoritara a sistemului.

    17161051 yyyya

    19183251 yyyya

    21205451 yyyya

    23227651 yyyya

    25249851 yyyya

    2726111051 yyyya

    2928111051 yyyya

  • 51

    3130151451 yyyya Iar a51 este valoarea majoritara a sistemului.

    18162052 yyyya

    19173152 yyyya

    22206452 yyyya

    23217552 yyyya

    262410852 yyyya

    272511952 yyyya

    3028141252 yyyya

    3129151352 yyyya Iar a52 este valoarea majoritara a sistemului.

    20164053 yyyya

    21175153 yyyya

    22186253 yyyya

    23197353 yyyya

    282412853 yyyya

    292513953 yyyya

    3026141053 yyyya

    3127151153 yyyya Iar a53 este valoarea majoritara a sistemului.

    24168054 yyyya

    25179154 yyyya

    261810254 yyyya

    271911354 yyyya

    282012454 yyyya

    292113554 yyyya

    302214654 yyyya

    312315754 yyyya Iar a54 este valoarea majoritara a sistemului.

  • 52

    Dupa ce au fost scrise relatiile de control corespunzatoare vectorilor compusi, se procedeaza in felul urmator:

    x se elimina influenta din relatiile de control a componentelor corespunzatoare vectorilor compusi ;

    x se scriu numarul de relatii de control pentru vectorii simpli, in numar de cate componente diferite de zero sunt pe fiecare din liniile lui V (pentru vectorii simpli).

    8UPDWRUXOSDVHVWHGHWHUPLQDUHDOXL\ :

    y=y-(a54*V54+a53*V53+a52*V52+a51*V51+a43*V43+a42*V42+a41*V41+a32*V32+a31*V31 +a21*V21);

    Pentru a vedea valoarea componentei mesajului informational : (a54 a53 a52 a51 a43 a42 a41 a32 a31 a21) se procedeaza pe baza logicii majoritare.

    101 yya

    321 yya

    541 yya

    761 yya

    981 yya

    13121 yya

    15141 yya

    17161 yya

    19181 yya

    21201 yya

    23221 yya

    25241 yya

    27261 yya

    29281 yya

    31301 yya Iar a1 este valoarea majoritara a sistemului.

    202 yya

    312 yya

    642 yya

    752 yya

    1082 yya

  • 53

    1192 yya

    14122 yya

    15132 yya

    18162 yya

    19172 yya

    22202 yya

    23212 yya

    26242 yya

    27252 yya

    30282 yya

    31292 yya Iar a2 este valoarea majoritara a sistemului.

    31273

    30263

    29253

    28243

    23193

    22183

    21173

    20163

    15113

    14103

    1393

    1283

    733

    623

    513

    403

    yyayyayyayyayyayyayyayyayyayyayyayyayyayyayyayya

    Iar a3 este valoarea majoritara a sistemului.

  • 54

    31234

    30224

    29214

    28204

    27194

    26184

    25174

    24164

    1574

    1464

    1354

    1244

    1134

    1024

    914

    804

    yyayyayyayyayyayyayyayyayyayyayyayyayyayyayyayya

    Iar a4 este valoarea majoritara a sistemului.

    31155

    30145

    29115

    28125

    27115

    26105

    2595

    2485

    2375

    2265

    2155

    2045

    1935

    1825

    1715

    1605

    yyayyayyayyayyayyayyayyayyayyayyayyayyayyayyayya

    Iar a5 este valoarea majoritara a sistemului. Dupa ce au fost evaluate componentele de la a1 la a5, se elimina influenta vectorilor VLPSOLGLQYHFWRUXO\ :

    y \-(a1*V1+ a2*V2+ a3*V3+ a4*V4+ a5*V5)

  • 55

    Pentru a evalua pe a0, observam numarul majoritar de componente din y LDUYDORDUHDcelor mai multe componente va fi valoarea lui a0. Mesajul corectat este : m=(a0 a5 a4 a3 a2 a1 a54 a53 a52 a51 a43 a42 a41 a32 a31 a21)

    Codul BHC Codurile Bose-Chadhuri-Hocquenghem (BCH) constituie o clas de coduri ciclice cu

    o deosebit capacitate de corecie a erorilor, care generalizeaz codurile Hamming pentru

    corecia erorilor multiple.

    Un cod ciclic binar, corector de t HURULDYkQG x Lungimea blocului n= , cu m vQWUHJ

    x 1XPUXOVLPEROXULORUGHFRQWUROQ-k mt, t ,

    x Distana d ,

    se numeWHFRG%+&GDFDUHGUHSWSROLQRPJHQHUDWRUJ[SROLQRPXOGHFHOPDLPLFJUDG

    SHVWHFkPSXO*)FDUHDUHFDUGFLQLHOHPHQWHOH DOHFkPSXOXL*DORLV

    GF( ).

    Prin urmare g( )=0, i=

    Fie polinomul minimal al lui DGLFSROLQRPXOGHFHOPDLPLFJUDGSHVWH

    *) DVWIHO vQFkW $WXQFL SROLQRPXO JHQHUDWRU J[ WUHEXLH V ILH FHO PDL PLF

    multiplu comun (c.m.m.m.c) al polinoamelor ,

    i anume: g(x)= (c.m.m.m.c){ , }.

    8QQXPUSDUi poate fi exprimat sub forma i=k* , k , impar. Atunci =

    este conjugatul elementului . DDUXQSROLQRPFDUHDGPLWHUGFLQLOH

    DGPLWH GUHSW UGFLQL i conjugatele acestora. Prin urmare, i au acelai polinom

    minimal i deci . Atunci polinomul generator este de forma

    g(x)= (c.m.m.m.c){ , }. (3.12)

    *UGXOILHFUXLSROLQRPPLQLPDOILLQGFHOPXOWHJDOFXm , polinomul g(x) va fi de grad cel mult egal cu mt DVWIHOvQFkWQXPUXOVLPEROXULORUGHFRQWUROQ-k , va fi cel mult egal cu mt : n-k mt. /DOLPLWvQFD]XOFRUHFLHLXQHLVLQJXUHHURULW UH]XOWn-k mt.

  • 56

    Codul BCH de lungime , cu m VHQXPHVFFRGXUL%&+vQVHQVUHVWUkQV

    (sau primitive). Aceste coduri sunt generate de elemente pULPLWLYHGHRUGLQPDLPLFGHFkW

    din GF( ).

    Un cod BCH de lungime FRUHFWRU GH R VLQJXU HURDUH HVWH JHQHUDW GH

    polinomul g(x)= .

    Polinoamele minimale ale elementelor din GF( ) generate de g(x)=1+x+

    Exemplu. WUHEXLHVILHGHJUDGP GHFLGHIRUPD

    =1+ (3.13)

    Deoarece

    =1+ (3.14)

    Conform tabelului 3.3 vQVHDPQF

    (3.15)

    LUH]XOW

    Deci

    = 1+x+ (3.16)

  • 57

    Deoarece din 2t- UH]XOWW VHGHGXFHXQFRG%&+FRUHFWRUGHGRXHURUL i de

    lungime n= = 15 este generat de g(x)= (c.m.m.m.c){ ,

    }= (x)=1+ .

    Fie v(x) un polinom de cod cu coeficienLL vQ *) DVRFLDL XQXR FXYkQW GH FRG

    v(x)= 3ROLQRPXO GH FRG DGPLWH UGFLQLOH

    din GF( ).

    'DF HVWHRUGFLQDOXLY[SHQWUX , atunci

    + (3.17)

    Se introduce matricea

    (3.18)

    DVWIHOvQFkWY =0.

    5H]XOW F v HVWH vn spaiul nul al matricei H i deci H este matrice de control a codului.

    Aplicaii

    Simularea cu ajutorul programului MATLAB a codului BCH

    Codurile BCH fac parte din categoria codurilor ciclice 6H YD LPSOHPHQWD vQSURJUDPXO0$7/$%VFKHPDSUH]HQWDWvQILJXUDXUPWRDUH

    Se vor utiliza urmtoarele blocuri: - Random-Integer Generator: genereaz numere vntregi distribuite vn intervalul [0, M-1]. Parametrii blocului sunt:

    - 0-ary number este 2^7 deoarece codul BCH utilizat este BCH(15,7) Lnumerele generate sunt reprezentate vn binar pe 7 bii. - ,nitial seed este [1458]. Modificknd acest parametru se modifica secvena de numere generate. - Sample time este 1. Genereaz ckte un numU la fiecare secunG

    - Integer to Bit Converter: transform un vector de vntregi vntr-un vector de bii. Parametrul blocului este:

    - 1umber of bits per integer este 7. Se lucreaz pe 7 bii. - BCH Encoder: creaz un cod BCH din datele vectorului binar. Parametrii blocului

  • 58

    sunt: - Codeword length N este 15. - Message length Keste 7 deoarece se utilizeaz codul BCH(15,7).

    - Binary Symmetric Channel: introduce erori binare. Parametrii blocului sunt: - Error probability este 0.1, pentru a nu introduce erori. - Input vector length este 15 deoarece cuvkntul de cod cu care se adun este reprezentat pe 15 bii. - Initial seeG este 12345.

    - Sample time este 1 pentru a se genera un eantion la fiecare secXQG- BCH Decoder: decodeaz un cod BCH pentru a reface vectorul binar transmis. Parametrii blocului sunt:

    - Codeword length N este 15 . - Message length Keste 7 deoarece se utilizeaz codul BCH(15,7).

    - Bit to Integer Converter: transform un vector de bii vntr-un vector de vntregi. Parametrul blocului este:

    - 1umber of bits per integer este 7. - Error Meter: compar semnalele de la intrare, le afieaz i evalueaz rata de eroare. Parametrii blocului sunt:

    - Bit per symbol este 7 deoarece utilizeaz 7 bii pentru fiecare simbol transmis. - 1umber of digits on display este 20 deoarece afieaz 20 de simboluri. - 'elay between input (1st port) and output (2nd port) este 0. - Sample time este 1 deoarece se consider un eantion la fiecare secund.

    - Sum: afieaz suma elementelor de la intrare. Parametrii blocului sunt: - Icon shape este rectangular.

    - List of signs este +. - Graph Scope: afieaz numrul de erori. Parametrii blocului sunt:

    - Time range este 10. - y-miQ este -1. - y-ma[ este 5. - Line typeeste 'ro/b*'

    - M ux: multiplexeaz semnalele de la intrare. - Display: afieaz valoarea de la intrare.

    Se va realiza schema bloc aratDW L se va rula pentru diferite valori ale probabilitatii de eroare si se vor analiza rezultatele.

  • 59

    Simularea cu ajutorul programului MATLAB a codului Hamming Q FDGUXO OXFUULORU GH ODERUDWRU YD IL SXV OD GLVSR]LLH R DSOLFDLH VRIWZDUH care

    LPSOHPHQHD] DOJRULWPXO GH FRPSUHVLH 6KDQQRQ-)DQR (FUDQXO DSOLFDLHL HVWH SUH]HQWDW vQILJXUDXUPWRDUH

  • 60

    ([HUFLLLUH]ROYDWH 8QQXPUGHVLPEROXULVHWUDQVPLWFXDMXWRUXOXQXLFRG+DPPLQJJUXSFRUHFWRUGHR

    eroare i detector de erori duble. Se cere: a. V VH GHWHUPLQH QXPUXO VLPEROXULORU GH LQIRUPDie k, al celor de control m, i

    OXQJLPHDFXYkQWXOXLGHcod n; b. VVHVFULHPDWULFHDGHFRQWURO+DFRGXOXL c. VVHVWDELOHDVFH[SUHVLDFRUHFWRUXOXLFRUHVSXQ]WRUHURQULLVLPEROXOXL 2c ; d. VVHGHWHUPLQHFRUHFWRUXOFRUHVSXQ]WRUHURQULLVLPEROXULORU 2c i 1c ; e. VVHGHWHUPLQHFXYLQWHOHGHFRG f. VVHSUHFL]H]HGDF > @0110011 v HVWHXQFXYkQWDODFHVWXLFRG Soluie

    D 1XPUXO VLPEROXULORU GH LQIRUPDie k VH GHWHUPLQ FX UHODLD i UH]XOWN

    0DUJLQHD +DPPLQJ G SHQWUX QXPUul simbolurilor de control:

    GLQFDUHUH]XOWFP

    La aceste simboluri de control, care permit corecLD XQHL HURUL WUHEXLH DGXJDW

    simbolul de verificare la paritate, aDvQFkWQXPUXOWRWDODOVLPEROXULORUGHFRQWUROYDIL

    =m+1=3+1=4

    6WUXFWXUDFXYkQWXOXLGHFRGYDIL

    Unde HVWHVLPEROXOGHYHULILFDUHDSDULWii, iar - simbolurile de control

    pebtru codul corector de o eroare.

    b). Matricea H a codului corector de o eroare este de forma:

    H=[ ]

    respectiv:

    H=

    Cu relaia (2.33) se obine pentru matricea expresia:

  • 61

    =

    F3HQWUXDFHVWFD]FXYkQWXOGHHURDUHHVWHGHIRUPD

    Cu relaLDUH]XOWSHQWUXH[SUHVLDFRUHFWRUXOXL

    Din expresiDFRUHFWRUXOXLUH]XOWFDSDUHRHURDUHFRUHFWDELO pe poziia a

    2-a (z= ).

    G3HQWUXDFHVWFD]FXYkQWXOHURDUHHVWHGHIRUPD

    LUH]XOW:

    =

    &RUHFWRUXODUDWFDSDUGRXHURULGHWHFFWDELOH ).

    H&XYLQWHOHGHFRGVHSRW VFULHFDOFXOkQG VLPEROXULOHGHFRQWUROGLQFHOHGH LQIRUPDie cu

    relaia GLQFDUHUH]XOW

  • 62

    Cuvintele GHFRGVHJVHVFvQWDEHOXOXUPWRU

    Simboluri

    Cuvinte

    0 0 0 0 0 0 0

    1 0 1 0 1 0 1

    1 1 0 0 1 1 0

    0 1 1 0 0 1 1

    1 1 1 1 0 0 0

    0 1 0 1 1 0 1

    0 0 1 1 1 1 0

    1 0 0 1 0 1 1

    I6HFDOFXOHD]FRUHFWRUXO astfel:

    = =

    D