1 UNIVERSITATEA TITUMAIORESCU FacultateadeINFORMATIC Profesor univ. dr. ing. Lector univ. dr.ing.RCUCIU CIPRIANGRECU DAN Curspentrunvmntulladistan BUCURESTI2010 2 UNIVERSITATEA Titu MAIORESCU BUCURESTI Facultatea de InIormatic nvmnt la Distan TEORI A TRANSMI TERI I $I CODIFICRII INFORMAIEI Cursul 'Teoria transmiteriiLFRGLILFULLLQIRUPDLHL este o disciplin care ngobleazntr-oIormunitarconceptedinteoriacodurilor,teoriasemnalelor aleatoare si teoria deciziilor statistice si reprezint una din disciplinele de pregtire care, pentru proIilul INFORMATIC, este necesar pentru pregtirea studenilor si pentruobinereacreditelortransIerabileprinproceduriledeevaluare.Modulde prezentareaacestuimaterialarenvedereparticularitilenvmntuluila distan, la care studiul individual este determinant. Pentru orice nelmuriri Ia de acestmaterialvrugmscontactaitutorelededisciplincarearedatoriasv ajute oferindu-v toate explicaiile necesare. Disciplina 'Teoria transmiteriiLFRGLILFULLLQIRUPDLHLsipropuneurmtoarele obiective specifice: nsusireanoiunilorIundamentaledindomeniulTeorieitransmiterii LcodificULLLQIRUPDLHL.Formareadeprinderilordemodelarematematicsidetranspuneren programareaunorproblemedenaturtehnic,socialsaueconomic,cu utilizarea cunostinelor nsusite.Formareasidezvoltareabazeimatematiceastudenilorpentrudisciplinele Iundamentale si de specialitate din anii superiori; Formareasidezvoltareaaptitudinilorsideprinderilordeanalizlogic, IormularecorectsiargumentareIundamentat,nrezolvareaproblemelor tehnico-economice si de specialitate; Ocomparaiecriticametodelorderezolvareevideniind,eventual,calea optim de soluionare. Vprecizmdeasemeneac,dinpunctdevederealveriIicrilorsialnotrii,cu adevratimportantestecapacitateapecaretrebuiesodobndiisisoprobai dearezolvatoattipologiadeproblemeaplicativeaIerentematerialuluiteoretic prezentatncontinuare.Deaceeavrecomandmsparcurgeicuatenietoate aplicaiilerezolvate,srezolvai aplicaiilepropuseprintesteledeautoevaluaresi temeledecontrol;IiiconvinsicexamenulIinalapeleazlatipuriledeaplicaii prezente n seciunile menionate anterior 3 CUPRINS MODULUL 1- MSURA CANTITATIV A INFORMAIEI .....................................pag.4 MODULUL 1- CAPITOLUL 1- ELEMENTE DE TEORIA TRANSMITERII INFORMAIEI ..................................................................................................................................pag.5 1.1.Informatia - generaIiti...............................................................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 - MSURI INFORMAIONALE ................................pag.9 2.1. Modele de surse informationale.....................................................pag.9 2.2. Informatia proprie conditionata...................................................pag.10 TESTE DE AUTOEVALUARE I TEME DE CONTROL.......................pag.21 BIBLIOGRAFIE RECOMANDAT LA MODULUL 1.......................... pag.21 MODULUL 2 - CODAREA SURSELOR INFORMAIONALE .................... .........pag.22 MODULUL 2- CAPITOLUL 1- CODAREA SURSELOR INFORMAIONALE .....pag.23 1.1Codificarea surselor discrete.......................................................pag.23 1.2Codificarea neuniforma................................................................ pag.23 1.3. Codarea si decodarea pe canale fara perturbatii........ pag.25 1.4. Coduri Huffman de dispersie minim..........................................pag.28 1.5 . ProcedeuI de codare binar Shannon - Fano. .........................pag.34 TESTE DE AUTOEVALUARE I TEME DE CONTROL................ pag.39 BIBLIOGRAFIE RECOMANDAT LA MODULUL 2.....................pag.40 MODULUL 3- CODURI DETECTOARE I CORECTOARE DE ERORI................pag.41 MODULUL3-CAPITOLUL1-CODURIDETECTOAREICORECTOAREDE ERORI.....................................................................................................................pag.42 1.1. Codarea si decodarea pe canale perturbate ..............................pag.42 1.2.Coduri bIocIiniare.....................pag.44 1.3. Exemple de coduri liniare ...........................................................pag.46 TESTE DE AUTOEVALUARE I TEME DE CONTROL.................pag.62 BIBLIOGRAFIE RECOMANDAT LA MODULUL 3: ...................pag.63 4 Coordonator disciplin: ProI. univ. dr.ing. RCUCIU CIPRIAN Tutori: Lector univ. dr.ing. GRECU DAN MODULUL 1 MSURA CANTITATIV A INFORMAIEI nacestmodulsuntprezentateprincipalelenoiunicucareopereazteoria informaiei.Notiuneadeinformatieaaparutmultmaitarziudecatnotiuneade energie,iarlegiledupacareinformatiaapare,setransforma,sepastreaza,se prelucreazasisefolosestesuntincainsuficientstudiate;abiainzilelenoastrese stabilesc bazele intelegerii lor, se elucideaza metodele de studiu si investigare.Stabilireanotiuniigeneralizatedeinformatiepentrucaracterizarea proceselordeconduceredintr-unpunctdevedereunitar,afostunmoment importantin stiinta.Intocmai cumintroducereanotiunii deenergieapermissase analizezetoatefenomenelenaturiidintr-unpunctdevedereunic,independentde substratullorfizic,totasa,introducereanotiuniideinformafieapermisstudierea dintr-unpunctdevederecomunacelormaidiferiteprocesedecomandadin natura. Senumesteinformatieoricestirecarepoartainsineurmaunuifapt, eveniment sau proces oarecare.Informatiaestecomunicarea(mesajul)ceaducestiridesprefapte, evenimente, obiecte, procese.In intelesul mai larg, in nofiunea de informatie se pot cuprindetoatestiriledespremediulcareneinconjoarasau,maibinezis,carese obtin,ininteractiuneaomuluicumediulinconjurator.Aobtineoinformatie inseamna a aflalucruri cenuse cunosteaumaiinainte sau a obtinenoi cunostinte asupra unui lucru, fapt etc., despre care s-a stiut mai putin inainte Timpul mediu necesar nsusirii noiunilor teoretice, Iormrii deprinderilor de calculsiutilizriimetodelorderezolvareaproblemelorspecificeteoriei inIormaieiesteestimatlaaproximativ6-8orepentrufiecaremodul,ntr-unritm de 2-3 ore pe zi. 5 MODULUL 1 CAPITOLUL 1 ELEMENTE DE TEORIA TRANSMITERII INFORMAIEI 1.5.I nformatia - generaliti. nproceseledecomanda,proceseleenergeticecareinsotesctransmitereainformatiei 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, caresedesfasoarapebazaschimbuluideinformatie,constatocmaiinaceeacamiscareasi actiuneaunormasematerialemarisautransmitereasitransformareaunorcantitatimaride energiesedirijeazasisecontroleazacuajutorulunormasematerialemicisialunorcantitati reduse de energie.nteoriainIormatiei,caracteristicaenergeticaaIenomenelortrecepeplansecundar, evidentiindu-se in mod deosebit latura informafionala a sistemului. Asadar, notiunea de informatie este foarte larga si se poate prezenta sub cele mai variate forme:aceastaconstituieoproprietatedeseamaainformatiei.Prinmijloacelede telecomunicatii-telefon,telegraf,radio-setransmitinformantii.Prinintermediulvazului, auzului,precumsialcelorlaltesimturi,omulprimestezilnictotfeluldeinformafiidespre evenimentele din lumea ce il inconjoara. Comunicaricomplexe,ordinesidispozitiunisetransmitcuajutorultelefonului, telegrafuluisiradioului.Comunicarisimaicomplexesuntceletransmiseprinintermediul televiziunii,undeimaginileinmiscaresuntinsotitedesemnaleaudio.Latoateacestesisteme, 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 distorsioneazasemnalul devorbire,in televiziunese deformeazaimaginea,in telegrafie apar greseli de imprimare. Aceste exemple evidentiaza o alta proprietate de baza a informatiei: in nici un sistem fizic informatianuapareintr-oformacurataciesteinsotitadediferiteperturbatiicarepotducela greseli.Deaceea,unadinproblemeleprincipalealeteorieiinformatieiconstainstabilirea metodeloroptimepentruextragereainformatieidinsemnalelecaresuntinsotitedeperturbatii. Notiuneadeinformatieacuceritunlocsigurinstiintanumaiatuncicands-agasitomasura 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 saexisteposibilitateafolosiriiacesteimasuri,adicasaexistesigurantacasepastreazaobiectul masuratorii. Tot asa, informatia careianastere incadrul unuisistembine definit sise pastreaza in limitele sistemului respectiv, poate fi masurata, indiferent de natura sistemului. Problemaprincipalaateorieiinformatieiestestudiereatransformarii,pastrariisitransmiteriiinformatiei.Analiza acestuifenomenafost facuta pentru prima data de inginerii de telecomunicatii, care s-au ocupat cu organizarea canalelor destinate transmiterii informatiei. n realitate, inIormatia se transmite prin intermediul semnalelor care poarta stirea. Tipuri deinformatie :informatiinumerice,informatiilogice,detiptext,informatiimultimedia:audio, imagine, video, semnale . 6 1.2. Sistemul de transmitere a informatiei. Purtatorulmaterial alinformatiei- semnalul -isipastreaza capacitatea sa de a transmite informatianumaiincadrulunuisistemdetransmisiuni;schemablocdestuldegeneralaaunui sistem de transmisiuni este data in fig.1.1 Fig.1.1 Coderul dinfig.1.1 executa orice prelucrare a semnaluluigenerat de sursa. O asemenea prelucrarepoateinclude,deexemplu,oanumitacombinatiedemodulatie,comprimarededatesauintroducerea unei redundante pentru lupta cu perturbatiile. Canalulestemediulfizicutilizatpentrutransmitereasemanalului:deexemplulinia telefonica,liniaradiosauradioreleu,dispozitivuldememoriesauorganismuluman.Asupra canalului, de regula, actioneaza diferite perturbatii care in liniile de telefonie pot apare din cauza modificarilor caracteristicii defrecventa, a convorbirilor ceseinduc dinaltelinii, 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. Destinatarulpoatefiomulsauundispozitivtehnicoarecare. Pentruasimplificaanaliza modelelor de surse si canale este de dorit a separa efectelelegate de sursa deefectelelegate de canal. Sarcinacoderuluisurseiestedeareprezentaiesireasurseicuajutorulsuccesiunilorde semnalebinare,siunadinproblemeleimportanteceapar,constainastabilicatesimboluri binare,in unitatea de timp sunt necesare pentru reprezentarea semnalului delaiesirea unei surse date. Sarcinacoderuluisidecoderuluicanaluluiconstainareproducecatmaisigur succesiunilebinarealedatelorobtinutelaiesireadecoderuluicanaluluisiunadinproblemele 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 saucareapartinunuialfabetfinit,dincaredecoderulsurseirestabilestemesajulinitialcuo precizieadoptatadecatredestinatar.Astfel,independentdeproprietatilesurseisau destinatarului,laintrareacoderuluicanaluluisilaiesireadecoderuluicanalului,seformeazao succesiunedesimboluribinaresaudesimboluricareapartinunuialfabetfinit.Reprezentarea informatieidetransmissubformauneisuccesiunibinareintermediaredaposibilitateasase 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 transmitemesajuldelasursaladestinatar,adicadeareproducemesajuldelaiesireasurseila loculindicat de destinatar. Cand spunem'reproduce" nuintelegem o reproducere absolut Iidela 7 ci o reproducere care corespunde anumitor scopuri specifice.Criteriul acceptabilitatii depinde de scopul transmisiuni. n descrierea 'obiectului" transmis prin sistemul de transmisie trebuie inclus sicriteriulacceptabilitatii.Astfel,obiectulcesetransmitenudeterminanumaiproprietatile sursei,cicaracterizeazaproprietatilecuplulul'sursa-destinatar".Vomnumiacestobiect 'inIormatia transmisa". 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 detimpdat.Multimeaclaselorsenumestemultimeademesajeposibiledinintervaluldetimp dat,admisibilepetimpultransmisiei.Sarcinasistemuluidetransmisiuniconstainreproducerea mesajuluidelaiesireasurseicuoprecizieadoptatadecatredestinatar.Existentacriteriuluide preciziepermitesasegrupezetoatemesajeleposibile,inoriceintervaldetimp,delaiesirea surseiinclase disjuncte. Sistemul de transmisiuniindica destinatarului clasa din careface parte mesajul respectiv. Toate surselein teoriainformatieisemodeleaza 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). n cazul unei codiIicari de acest tip, combinatiile de codvor avea aceeasi lungime pentru ca sa fie posibila decodificarea lor. Remarcam faptul ca scrierea numerelor, in cazul transmiterii mesajelor admisinile, intr-o formabinaranuareoimportantaprincipala.Elepotfiscriseinoricesistemde numeratie.Prezintaimportantaposibilitateainsasidetransformareamesajuluiadmisibilintr-o succesiunedesimboluricarefacpartedintr-unalfabetfinit.Rationamentulprezentatpermitesa se presupuna ca numarul de mesaje admisibile sau numarul de simboluri binare, necesare pentru reprezentareafiecaruimesajdinmultimeamesajelorposibile,poatefiluatacaomasuraa cantitatiideinformatietransmisadesursaintr-unintervaldetimp.Dar,dupacumvomvedea, aceastapresupunereestejustanumaiintr-unanumitcaz.NumarulMdemesajeadmisenu descriecompletmultimeamesajelorsiestenecesarsaseiainconsideratiesiprobabilitatilecu care sunt generate aceste mesaje admisibile. Prima teorema a lui C. Shannon - teorema fundamentala acodificarii in lipsa zgomotelor datocmaiolimitainferioarasiunasuperioarapentrulungimeamedieacombinatiilordecod. Probabilitatilep(ai)depinddecaracteristicilestatisticealesurseisideprocedeuldegruparea mesajelorposibileinclasedeechivalenta.Inafaradeaceasta,numarulmediudesinboluri binare,generateintr-osecunda,depindedeintervaluldetimpTcucares-alucratlagruparea mesajelorin clase de echivalenta. Pentru amari eficacitatea sistemulul de transmisiuni se cauta sa se minimizeze numarul mediu de simboluri binare generate intr-o secunda decoderul sursei. Unuldinrezultateleprincipalealeteorieitransmisiuniiinformatieieste:incazulunor conditiidestuldegeneralepoatefiindicatnumarulR,care,pentrufiecarecuplusursa-destinatar,exprimavitezadegenerareainformatieipentruuncriteriudeprecizieadoptat.Aceastavitezasedeterminacacelmaimicnumarmediudesimboluribinareintr-osecunda, 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. Avandinvederecapentruoricefenomendinnaturasaudinsocietateaprecierile cantitativeconstituieoconditiedebazaaanalizeistiintifices-acautatomodalitatepentu calcululcantitatiideinformatiesis-astabilitounitatedemasurapentruinformatiacontinuta intr-unsemnal purtator deinformatie. La calculul cantitatii deinformatie sila stabilirea unitatii demasuraainformatieisepleacadelaodescriereprobabilisticaasemnalelorsiseconsidera semnalelecaevenimentealeatoare.Semnalelediscretecareintervinindiferitesisteme informationale,destinatetransmiteriisiprelucrariidatelor,permitotratarecorespunzatoare probabilistica,iarsemnalelecontinue,deasemenea,permitodescriereprobabilisticadupa discretizare-ceeacesefacecuocaziaobservariicuopreciziedata.Astfel,putenconchide universalitatea cantitatii de informatie obtinuta pe baza unui model probabilistic. Unitateademasuraainformatieisereferanumailaparteacantitativaainformatieisi intotdeaunasefaceabstractiedecontinutulsemanticalmesajului.Cauzaacesteitratari unilaterale rezida infaptul ca aparatul matematic existent deocamdata,nu ne permite efectuarea unuistudiucalitativalinformatiei.Construireaunuimodelprobabilisticpentrusemnalele discrete-utilizateincadrulunuisisteminformationaldat-presupunecunoasterea probabilitatilorcucareaparacestesemnaleinurmaunuiexperiment.Aparitiaunuisemnalin cadrul unui experiment se considera ca un eveniment. ncazulsemnalelordiscrete, totdeaunasepoate realizaocorespondentabiunivocaintre semnaleleposibilesiintreomultimedenumerenaturaleX-facandcafiecaruisemnalsa corespunda un numar natural xeX- si astfel multimea semnalelor discrete se poate inlocui cu o multimedenumerenaturaleX.Incontinuare,prinxseintelegefieunsemnaloarecare,fie numarul natural care corespunde semnalului respectiv. ModelulprobabilisticalsemnalelorXestedatprinurmatoarearepartitieavariabilei aleatoare: ( ) ( ) ( )||.|

\|=M X X XMx P x P x Px x xX......2 12 1(1,1) Prinnotatia ( )k X x Pseintelegeprobabilitateadeaparitieaevenimentuluix=xk,adica probabilitatea de aparitie a semnalului care corespundeluixk si careface parte dinmultimea X considerata. Evident: ( ) 11==KMKX x P (1.2) Probabilitateacarezultatulexperimentuluivafiunelementoarecarex,senoteazacu Px(x)incare,prinindiceleXseaccentueazacarezultatulexperimentuluiesteunsemnaldin multimea semnalelor posibile X. In cazul cand nu exista ambiguitati inprivinta apartenentei lui xsepoatesuprimaindiceleX.Experimentelecumaimulterezultatesimultanevorfi caracterizateprinelementeleunuiprodusdemultimisiprinprobabilitatiledeaparitieaacestor elemente. 9 MODULUL 1 CAPITOLUL 2 MSURI INFORMAIONALE 2.1. Modele de surse informationale Informatia proprie, ca si informatiareciproca se poate considera ca o variabila aleatoare sisecalculeazavaloareasamedie.Valoareamedieainformatieipropriipentruevenimentedin multinea X se numeste entropia lui X si se calculeaza cu formula: ( ) ( )( )K XKKKXx Px P X H1log1== (1,3) sau mai simplu se scrie sub forma: ( ) ( )( ) x Px P X HK1log1==(1.4) Variatiaentropieiunuisistemdeevenimenteformatdindouaevenimenteinfunctiede repartitia de probabilitati este data in fig 1.2:

Fig.1.2 Entropia semnalului Fie 10 ||.|

\|=p px xX12 1(1.5)atunci: ( ) ( ) ( ) p Hpppp X H = + =1 1log 11log(1.6) 2.2. I nformatia proprie conditionata. CantitateadeinformatieproprieconditionataaevenimentuluiX=Xk,cuconditiacaa aparutevenimentul Y=Yi se defineste pe produsul cartezian XY sise calculeaza cu formula: ||.|

\|=||.|

\|ikyxikYXyxPyxI1log(1.7) sau mai simplu se scrie: ||.|

\|=||.|

\|ikxyxPyxI1log (1.8) AceastacantitatedeinformatieproprieaevenimentuluiX=Xk,conditionatade evenimentuly=yisepoateinterpretacainformatianecesarapentruspecificareaevenimentului x=xk . dtupa ce a avut loc evenimentul y =yi. Cuajutorulrelatiiloranterioaresepoateexprimacantitateadeinformatiereciprocacao diferenta intre informatia proprie si informatia proprie conditionata. ( )( ) ( )||.|

\| =||.|

\|=yxPx P x P yxPy x I1log1log log ;(1.9) de unde ( ) ( )||.|

\| =yxI x I y x I ; (1.10) Din relatia anterioara se obtine pe baza reciprocitatii relatia: ( ) ( )|.|

\| =xyI y I y x I ; (1.11) 11 In mod analog I(x;y) se poate scrie sub forma: ( )( )( )( ) ( )( )( ) ( ) ( ) ( ) ( ) y x P y P x P x P y Py x Px P y PyxP y Px P yxPy x I,1log1log1log,log log log ; + = =||.|

\|=||.|

\|=(1.12) deci: ( ) ( ) ( ) ( ) y x I y I x I y x I , ; + = (1.13) unde : ( )( ) y x Py x I,1log , = (1.14) reprezintacantitateadeinformatieproprieaunuieveniment(x;y)dinprodusulcarteziande evenimente xy. Tinand seama ca: ( ) ( ) ( )||.|

\|=|.|

\|=yxP y PxyP x P y x P, (1.15) rezulta ca, cantitatea de informatie proprie a unui eveniment (x,y) se poate scrie sub forma: ( ) ( )( ) ( )||.|

\|+ =|.|

\|+ =yxI y I y x IxyI x I y x I,,(1.16) Luand mediile expresiilor din relatiile anterioare se obtine: ( ) ( )( ) ( )( ) ( ) ( ) ( )( ) ( )( ) ( )||.|

\|+ =|.|

\|+ = + =|.|

\| =||.|

\| =yxH y H y x HxyH x H y x Hy x H y H x H y x IxyH y H y x IyxH x H y x I,,, ;;;(1.17) PrimarelatiedinsistemuldemaisuspermiteinterpretarealuiI(X;Y).DeoareceH(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 carecantitateadeinformatiemedieI(X;Y)estenumitasiinformatiatransmisasaupescurt transinformatia. 12 Dinformulaentropiei,datadecatreC.Shannoninanul1948inlucrareasa,rezultaca entropiaU(X)amultimiiXdepindenumaideprobabilitatiledeaparitieaelementelorxtX. EvidentdacamultimileXsiYauaceeasirepartitiedeprobabilitatiatunciH(X)=H(y),insa invers,din egalitatea entropiilor nu rezulta identitatea repartitiilor. Proprietatea 1. H(X)>0Inadevar,sumaH(X)continetermenideformaP(x)log(1/P(x)),caresuntmaimarisau egali cu zero pentru 0 +(1.19) in care avem egalitate daca si numai daca x=y. Aceasta inegalitate scoate in evidenta proprietatea de convexitate a functiei logaritmice,o proprietate care de asemenea joaca un rol important in teoria informatiei. Fig.1.3. Proprietatea 2. Fie X multimea formata din K semnale ,atunci: ( ) K x H log s(1.20) unde avem egalitate,daca si numai daca repartitia lui X este uniforma adica: 13 ||.|

\|=k k kx x xXk1...1 1...2 1(1.21) Proprietetea 3. Pentru doua multimi de semnale X si Y ,avem: ( ) ( ) ( ) y H x H y x H + s ,(1.22) in care avem egalitate daca si numai daca X si Y sunt statistic independente. Exerciii rezolvate. ConceptiaShannonpleacadelapremizacaoriceinformatiecuprivirelauneveniment este utilizata in scopul reducerii gradului de incertitudine asupra realizarii acelui eveniment. Din punctuldevederealdestinatarului,comunicatiaesteovariabilaaleatoare,continutulinformationalfiindcuatatmaimarecucatelseasteaptamaiputinlarealizareaacelui eveniment. Fie o sursa discreta care emite unul dintre celeqmesajem m mq 1 2, , , cu probabilitatile deaparitiepp pq 1 2, , ,.Esteevidentcaprobabilitatilesatisfacrelatiap p pq 1 21 + + + =. Continutulinformationalalmesajului kestenotatcuI mk( ) .Pentrucaacestcontinutsafieo masura adecvata a cantitatii de informatie este necesara satisfacereaurmatoarelor proprietati : (i) dacap p I m I mk j k j< > ( ) ( )(ii) dacap I mk k 1 0 ( )(iii) daca0 1 0 s s > p I mk k( )(iv)(aditivitatea)dacamksimjsuntmesajeindependente = + I m m I m I mk j k j( ) ( ) ( ) si Ofunctiecontinuadevariabilapkcaresatisfaceproprietatile(i)-(iv)estefunctia logaritmica. I mppkkk( ) 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/T1exprimata 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 101122 25 10 2 3 2 25 10 2 362622 62, log , log , log biti Problema 2 Un display monocolor cu24 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)t = 1fc RII fc= = t[ ] bps Problema 3 Unechipamentdeteletransmisiegenereazacuvinteconstituitedintr-ungrupde4 impulsuridetensiunecarepotaveanivelurile0,1,2sau3volti(echiprobabile)urmatedeun 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)RI= ==t4 45 101 623log, [ ] kbps(b)rbaudsbaud] kbaud] = = =11010 133[ [ Problema 4 Fie12monededintrecareunaestefalsa(maiusoarasaumaigreadecatcelelalte).Se ceresasedeterrminenumarulminimdecantaririnecesardepistariimonedeifalsesiprecizarii daca ea este mai usoara sau mai grea. Se foloseste pentru cantariri o balanta fara mase marcate. Solutie -cantitatea de informatie necesara determinarii monedei false esteI1 2 2111212 = = log log-cantitatea de informatie necesara pentru a decide daca moneda este mai grea sau mai usoara esteI2 2 21122 = = log log-cantitatea de informatie totala necesara a fi determinataI I I = + =1 2 224 log-cantitateadeinformatiefurnizatadeocantarire(exista3starialebalantei) I3 2 21133 = = log log numarul minim de cantaririI kI kks s =324 3 3. -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 10121214142 18183log log logSereamintestecaentropiauneisursereprezintanumarulmediudebiti/simbolsica entropia este maxima pentru o sursa care genereaza simboluri echiprobabileH nmaxlog =2. Problema 6 16 Sasedeterminecapacitateaunuicanalbinarcuzonadeanulareavandgrafulasociat matricei de tranzitie din figura de mai jos Solutie Acestmodeldescrieuncanalcareperturbasimbolurileuneisursebinareinmasurain care la receptie sa poata fi interpretate ca fiind incerte. Metodascalara ( )| |C H Y H Y Xp xi= max ( )( ) H Y p y p yiii( ) ( ) log ( ) = =13 ( ) ( ) ( ) ) ( ) 1 ( ) ( ) ( ) ( ) (1 1 1 1 2 2 1 1 1 1 1x p q x p x y p x p x y p x p x y p y p = = + = S-a utilizat formula probabilitatii totale, evenimentele x1, x2 fiindmutual exclusive. Analog se poate scrie p y q p x ( ) ( ) ( )2 21 = ( ) ( ) ( ) p y p y xp x p y x p x q p x p x q q ( ) ( ) ( ) ( ) ( )3 3 1 1 3 2 2 1 21 = + = + = = | || |H Y q p x q p x q q q p x q p xqp 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 11 1 11 1 11 1 2 21 1 2 2 ( ) ( )H YX p x y p y xi j jij i= = = ( , ) log1312 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 11 = ( )p y x1 20 =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 10 =( )p y x q2 2= ( )p y x q3 1=( )p y x q3 21 = Se obtine ( )H Y X q q q q = ( )log( ) log 1 1 C q H X q qp xi= = = ( ) max ( ) ( )( )1 1 1 1 pentru setul optim de probabilitate la intrarepx px0 1 0 21 ( ) ( ) = = . Metoda matriciala Se considera sursa care genereaza un alfabet de simbolurix i ni , , , = 1 si la destinatie se receptioneaza un alfabet de simboluriy j mj , , , = 1. Se pot scrie urmatoarele relatii: ( )P Y P X P Y X ( ) ( ) = undeP X ( ) este matricea linie a sursei( ) 1 n ; P Y ( )este matricea linie a destinatiei( ) 1 m ; ( )P Y X este matricea dreptunghiulara de zgomot( ) n m . Observatie In matricea de tranzitie (zgomot) liniile sunt asociate intrarilor iar coloanele sunt asociate iesirilor.Matriceacampurilor reunite (joint) este ( )P X Yp xp xp xP Y Xn( ,)( )( )( )=

(((((120 00 00

Matricea de zgomot ( )P Y X se poate obtine prin impartirea fiecarei linii i prin p(xi). Matricea de echivocatie ( )P XYse poate obtine prin impartirea fiecarei coloane j prinp(yj) . Problema 7 Fie matricea de tranzitie ( )P Y X =

((2 3 1 31 3 2 3/ // / sip(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 xiii( ) ( ) log( ) log log log , = = +|\

|.|= ~=12343414142343 0 81 bit / simbol (b)H Y p y p yjjj( ) ( ) log( ) = =12 | | | |P Y ( ) / // // // / =

((= 3 4 1 4 2 3 1 31 3 2 37 12 5 12 H Y ( ) log log , = +|\

|.|=7127125125120 98 bit / simbol (c) ( )( )H XY p xy p x yi j ijj i= = = ( , ) log1212 P X Y ( ,)/// // // // /=

((

((=

((3 4 00 1 42 3 1 31 3 2 31 2 1 41 12 1 6 H X Y ( ,) log log log log , = + + +|\

|.|=1212141411211216161 73 bit / simbol (d) ( ) ( )H Y X p xy p y xi j jij i= == = ( , ) log , 0 921212bit / simbol sau ( )H Y X H X Y H X = ( ,) ( )(e) ( )( )H XY p xy p x yi j ijj i= = = ( , ) log1212

unde 19 ( )P XY =

((((((((((=

(((((12712145121127121651267351725 si ( )H XY = + + +|\

|.|=126714351121716250 75 log log log log , bit / simbol sau ( )H XY H X Y H Y = ( ,) ( ) (f)IX Y H X H Y H X Y ( ,) ( ) ( ) ( ,) , = + = 0 06 bit / simbol (g) canalul fiind dublu uniform C= + |\

|.||\

|.|+ = log log ( ) log , 2 1131132 1 13130 082 bit / simbol Setul optimp 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 22313= + p y p x p x ( ) ( ) ( )2 0 1 0 21323= + ( ) ( ) ( ) ( )( )H Y X p x y p y x p y x p x p y xp x p xi j jij ij i i jij i= = == +

((+ = +

((= = = = ( , ) log ( ) loglog log ( ) ( ) log log1212012120 1 0 22323131323231313 deci ( )H Y Xnu depinde deP X ( ) C H Yp xi= + +

((max ( ) log log( )023231313 20 darmax ( ) log ( ) ( )( ) p xi H Y p y p y01 22 112= = = = ( ) ( )( ) ( )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 22 2 1 0 1 220 2= += + p x p x0 1 0 212( ) ( ) = = . Observatie Se mai poate utiliza si relatiap x p x0 1 0 21 ( ) ( ) + = (h)q()( ,), CIX YC= = 0 73 R C C IX Y () ( ,) , = = 0 022 bit / simbol Problema 8 FieuncanalbinarsimetricavandmatriceacampurilorreuniteP X Y ( ,), ?? ,=

((0 40 4si pentru care sursa genereaza simboluri echiprobabile. (a) Calculati matricea P X Y ( ,) . (b) Calculati matricea de zgomot. (c) Calculati transinformatia. Solutie (a)canalulfiindsimetric = p x y p x y ( , ) ( , )2 1 1 2sifolosindproprietatea(iii)aevenimentelor mutual exclusive se obtinep x y p x y p x y p xy ( , ) ( , ) ( , ) ( , ) ,1 1 1 2 2 2 1 22 1 01 + + = =siP X Y ( ,), ,, ,=

((0 4 0101 0 4. (b) ( )P Y X =

((((((=

((0 41 2011 20 11 20 41 20 8 0 20 2 0 8,/,/,/,/, ,, , 21 TESTE DE AUTOEVALUARE I TEME DE CONTROL Testul nr. 1 Fie un alIabet Iormat din literele A,B,C. Se cere s se calculeze: a.numrul maxim de mesaje de lungime 3 ce se pot Iorma cu acest alIabet; b.cantitatea de informaie coninut de un asemenea mesaj. Testul nr. 2 S se calculeze cantitatea de informaii necesar pentru precizarea poziiei unei figuri pe tabla de sah. 7HPGHFRQWURO Matriceaprobabilitilorreuniteintrare-iesireasociatunuicanaldetransmisieestede forma: ( )((

=4 / 1 4 / 14 / 1 4 / 1X Y PSe cere s se calculeze: a.entropia cmpului de la intrare; b.entropia cmpului de la iesire; c.entropia cmpurilor reunite; d.eroarea medie si echivocaia; e.transinformaia si capacitatea canalului. BIBLIOGRAFIE RECOMANDAT LA MODULUL 1: |1| A. Sptaru:TeoriaTransmisiunii Informaiei, Ed. Didacticsi Pedagogic, Bu- curesti, 1983. |2| A. T. Murgan,I. Spnu, I. Gavt, I. Sztojanov, V. E. Neagoe, A. Vlad:Teoria Transmisiunii Informaiei- probleme, Ed. DidacticsiPedagogic,Bucuresti, 1983 [3] I. Angheloiu, Teoria codurilor, Ed. Militar, Bucuresti, 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 INFORMAIONALE

Compresiadateloresteunprocesdereprincareseurmrestemicsorarearedundaneimesajuluigeneratdeosurs,pentruareduceresursele necesarememorriisautransmiteriiacestuimesaj.Deoarece,deregul,pentrumemorareasautransmitereaunuimesajsefoloseste,eventualntr-o Iormintermediar,reprezentarea prin simboluri binare a acestuia, si pentru c celemaimultemetodedecompresiefolosescmetodedecodarebinar-binar, putemspunecobiectivulcompresieiconstnreducereanumruluide simboluri binare necesar pentru reprezentarea mesajului. Dup cum sirul simbolurilor emise de surs este mprit, pentru codare, n subsirurideaceeasilungimesaudelungimevariabil,siduplungimea, constant sau variabil, a cuvintelor de cod, codurile de compresie se clasific n bloc-bloc,blocvariabil,variabilblocsivariabilvariabil,blocbloc indicnd aceeasi lungimepentru subsirurile sursei si cuvintede cod delungime fix,iarvariabilvariabilcorespunzndunorlungimivariabileale subsirurilor sialecuvintelordecod.Dinpunct devederealmsuriincaremesajul reIcut prindecompresieseaseamncuceloriginal,asupracruias-aacionatprin procesul de compresie, distingem dou categorii de algoritmi de compresie: Ir pierderi si cu pierderi. AlgoritmiidecompresieIrpierderisuntreversibili,prindecompresie obinndu-semesajul originalntocmai.Algoritmii decompresiecupierderi au ca rezultat diferene relativ mici ntremesajulrezultatprin decompresie sicel original si suntutilizai n compresia imaginilor si a mesajelor video si audio. nacestmodulvorIiprezentateaspecteprivindcodiIicareasurselor discrete si vor Ii analizai algoritmii HuIIman si Shannon-Fano. 23 MODULUL 2 CAPITOLUL 1 CODAREA SURSELOR INFORMAIONALE 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 carese 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. Pentruaprezentaproblematicilelegatedecodificareasemnalelorprinarecuajutorul semnalelorsecundareestenecesarsaseprecizezeformaconcretaasemnalelorprimaresi secundare.Seconsideracasemnaleleprinaresuntsemnalegeneratedecatre osursadiscretasi faramemorie,adicasemnaleleaparsuboformadiscretasiprobabilitateadeaparitieaunui simbol nu depinde de celelalte sinboluri anterioare. Alfabetulsurseidiscretesenoteazacu { }La a a A ...., ,2 1=,decisursaproduce succesiunidelitere nu u u ,...., ,2 1formatecuajutorulliterelordinalfabetulsursei,deciA uiepentrui1,2,.. Faptulcasursaestefaramemorieseexprimaprininterdependentastatisticaa semnalelor,adica probabilitatea unei succesiuni date( )nno o o o ,..., ,2 1= de n litere de sursa este egala cu produsul probabilitatilor literelor de sursa ,deci: ( ) ( )[==nii nP P12 1,...., , o o o o(2.1) 1.2 Codificarea neuniforma. Presupunem ca alfabetul unei surse discrete sifaramemorie contine M semnale primare sauliterenotatecu Ma a a ,...., ,2 1careaparcuprobabilitatile( ) ( ) ( )Ma P a P a P ,.., ,2 1.Fiecare literaasurseitrebuiesafiecodificataprintr-ocombinatiedesemnalesecundareluatedin alfabetulcoduluicarecontineDsemnale { }Dx x x X ,.., ,2 1=.Acestecombinatiisenumescsi cuvintedecod;cuvinteledecodcarecorespundsemnalelorprimare Ma a a ,.., ,2 1senoteazacu Mc c c ,.., ,2 1,iar totalitatea lor formeaza un cod, { }Mc c c C ,.., ,2 1=.Numarul semnalelor secundare din cuvantul de cod kc care,dupa cum s-a vazut,corespunde lui ka,se noteaza cu kn . 24 Dintretoate,codurileunicdecodabileprezintauninteres,dinpunctdevedere economic,acelcod care conducela un n -numarulmediu delitere de cod peliterede sursa-cat mai mic posibil,unde n se mai numeste si lungimea mediea combinatiilor de cod: ( )kMKk n a P n==1(2.2) Codul in care doua semnale primare distincte sunt codificate printr-o singura combinatie de cod se numeste cod singular si inmod corespunzator codul in care toate combinatiile de cod atribuite semnalelor primare sunt distincte se numeste cod nesingular.Codul { }kc c c C ,.., ,2 1=senumesteunicdecodabiledacasuccesiunilecuvintelorde cod,corespunzatoare diferitelor succesiuni de lungime finite a sursei,sunt distincte. Fie un cuvant de cod im i i ix x x c ,..., ,2 1=.Sirul de litere im i ix x x ,..., ,2 1,unde m k s se numeste prefixul lui ic. Cuajutorulnotiuniideprefixputemdefinisubclasacodurilorunicdecodabilecare prezinta un interes deosebit din punct de vedere practice. Codulincareniciuncuvantdecodnuesteprefixulunuialtcuvantdecodsenumeste cod cu proprietate de prefix.Din aceasta definitie rezulta cain cazul unui cod cu proprietate de prefix,dintr-uncuvantdecodmailungnusepoateobtineuncuvantdecodmaiscurtprin 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 decodificareauneisuccesiunidecuvintedecoddintr-uncodcuproprietateadeprefixse inainteaza in succesiunea semnnlelor pana la identificarea primului cuvant de cod si apoi lasand laopartesuccesiuneaidentificatasetrecelaidentificareaurmatoareisuccesiunisia.m.d. Momentulcandseobtineosuccesiunecusens,aratasisfarsitulunuicuvantdecod,datfiind faptulcaniciuncuvantdecodnuesteprefixulunuialtcuvantdecod.Relatiacareexistaintre 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. Codurilecuproprietatedeprefixpermitoreprezentaregeometricafoarteintuitivasi convenabila,cuajutorulunuigrafarborescent.Fiecaruicuvantdecodiicorespundeundrum simplu,sau nodul final de la extremitatea drumului simplu corespunzatorEsteimportantcaincazulunuicodcuconditiadeprefixexistaocorespondenta biunivocaintrecuvinteledecodsiintrenodurilefinale,decifiecaruicuvantdecodii corespundeunnodfinalsinuunnodinternediarsiinvers,fiecaruinodfinaliicorespundeo 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 codii corespunde un nodinternediar. 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. Incadrulmodulului1s-aaratatcaunsistemdigitaldecomunicatiepresupuneun codor/decodoralsursei.Rolulacestuiaestedeamarieficientatransmiteriiprinutilizareaunor mesaje ct mai scurte pentru a transmite aceiasi cantitate de inIormatie. Aceast operatie numita generic , compresie de date Definirea unui cod. Fie o sursa discreta Iara memorie avnd alIabetul { } S s s sN=1 2, ,......,(2.3) cu probabilitatea de aparitie( ) p s pi i= { } P pp pN=1 2, ,......,(2.4) Fie alfabetul canalului { }X xx 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*=>

(2.6) Orice aplicatieS X * se numeste codarea alfabetului Sprin alfabetul X Unelements Xi* *e sicarecorespundeluisiesteuncuvntdecod.Lungimea cuvntuluidecod,notat ( )n s ni i*= estenumaruldeliterecaleIlformeaza.Totalitatea cuvintelor de cod constitue codul lui S cu mentiunea caX* 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 Decodareaimplicaposibilitateadeareparacuvinteledecodnmodunic(aplicatia S X * sa fie injectiva). Un cod cu aceasta probabilitate se numeste regulat (nesingular). Regularitatea este o conditienecesara darnu suficienta pentru decodare. fie de exemplu s s1 210* *, = sis301 = . Codul 010 poate fi interpretat fies s1 2* *,fies s3 1* *, . Pentruadistingefaraambiguitatiuntexttrebuiecafiecaruisuccesiunedecuvintesa-i corespunda o succesiune unica de litere, adica aplicatiaS Xkkn>*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) Existansasicoduri carenunecesita utilizarea unuimijlocsuplimentar pentru a asigura proprietate de unic decodabil. Aceste coduri se numesc separabile. Alcatuirea unui cod. Teorema Kraft ConditianecesarasisuficientapentruexistentaunuicodireductibildeNcuvintede lungimen n nN 1 2, ,......,este ca q niiN=s11 (2.9) Observatii 1. Se reaminteste ca( ) q card X =este numarul de litere din alfabetul canalului. 2. Daca numarul cuvintelor de lungime k esterk atunci conditia (1.9) devine r qkkkn s=11(2.10) cuN rkkn==1 Teorema Mac Millan Un cod este ireductibil daca si numai daca n n nN 1 2s s s ...... (2.11) 27 Criterii de apreciere a unui cod.Transmitereamesajelorpresupuneuncostcarecrestelinearcutimpul.Uncriteriu convenabil de apreciere a unui cod este lungimea medie a unui cuvnt n pni iin= =1(2.12) undepi sunt definite prin (1.4) sini este numarul de litere din cuvntul de cod cu indicele i. Esteevidentcasecautacan saIiectmaimicdartrebuieavutInvederecaeleste limitat inferior de entropia informationala pe simbol a alfabetului de cod nHq>log2(2.13) unde H este entropia sursei. In aceste conditii, eficienta unui cod este q =sHn q log21(2.14) iar redundanta codului este q = 1 (2.15)

Codurilecuoeficientaegalacuunitateasidecicareaulungimeamedieminimase numesc coduri absolut optimale Prima teorema a lui Shannon. Pentru orice sursa omogena exista un cod ireductibil pentru care lungimea medie a cuvintelor eVWHRUFkWGHDSURSLDWDGHPDUJLQHDVDLQIHULRDUD. Aceastateoremasemainumestesiteoremacodariipecanaleneperturbate.Prima teorema alui Shannonse reIerala problema codarii cu olungimemedie posibilactmaimica, pe un canal neperturbat de capacitate data. Codurile care asigura cea mai mica lungime medie posibila se numesc cvasioptimale sau compacte. 28 1.4. Coduri Huffman de dispersie minim. Acest procedeu se bazeaz pe ideea de a partiiona mulimea mesajelor sursei S = {s1, s2 ,..., sN}n submulimile si , astIelnct suma probabilitilormesajelorinclusens Iie ct mai apropiat de suma probabilitilor mesajelor incluse n . Larndullor,submulimilesipotIipartiionatensubmulimilesi, respectivsiastIelnctsumaprobabilitilormesajelorinclusencelepatru submulimisIiectmaiapropiateposibil.Procedeulsecontinunmodsimilarpncndse obin submulimi ce conin un singur mesaj. nIelul acesta, pentru orice distribuie asurseiS ce urmeaz aIicodat se va obine un cod compact, adic lungimi medii ale cuvintelor de cod ce nu mai pot Ii micsorate prin nici un alt procedeu de codare. Pentru ca partiiile s satisIac condiiile menionate, se procedeaz astfel: 1). Se ordoneaz mulimea mesajelor sursei S n ordinea descresctoare a probabilitilor, obinndu-seastIelmulimeaordonat={ },cup( ) p( ) ...p( ),cu schimbarea eventual a indicilor mesajelor pentru realizarea ordonrii respective; 2). Se reunesc ultimele dou mesaje (de probabilitile cele mai mici) ntr-un nou mesaj, notatcu,cruiaisealocoprobabilitateegalcusumaprobabilitilormesajelor componente.Seordoneazdinnoumesajelenordineadescresctoareaprobabilitilor, Iormndu-se astIel prima surs restrns={cu p( )p( ) ... p( ) ... . 3).Sereunescultimeledoumesajedinsursarestrnsntr-unnoumesaj,de probabilitateegalcusumaprobabilitilormesajelorcomponente.Seordoneazmesajelen ordine descresctoare, Iormndu-se astIel sursa restrns. n mod analog, din se Iormeaz sursarestrns siasamaideparte, pncndseobineosursrestrnsIormatnumaidin dou mesaje,, cu p( ). De fapt, va fisi va fi sau invers. 29 Din modul de Iormare a surselor restrnse, rezult c mulimea S a mesajelor poate fi partiionat n dou submulimi si astIel nct probabilitile p( ) si sunt cele maiapropiateposibil.Larndullor,submulimilesi,potIipartiionatenaltedou submulimi, de probabilitile cele mai apropiate posibil. Partiionrile se continu pn se obin submulimi care conin un singur mesaj. 4). Cuvintele de cod corespunztoare Iiecrui mesaj se obin astIel: - submulimii i se aloc simbolul "0" (sau "1"); - submulimii , i se aloc simbolul "1" (sau "0"); - la Iiecare partiionare se aloc arbitrar celor dou submulimi "0" sau "1", operaia continundu-se pn se obin submulimi ce conin un singur mesaj, k= . Deoarece alocarea lui "0" si "1" este arbitrar la Iiecare partiionare, rezult c unei surse S i se pot atasa omultitudine de coduriinstantanee, toate, ns, avnd aceeasilungimemediea cuvintelor de cod, care nu mai poate Ii micsorat prin nici un alt procedeu de codare a mesajelor luate individual. Dac sursa primar S poate furniza N mesaje, atunci submulimea restrns, va avea N-1mesaje,submulimearestrnsvaconineN-2mesajesiasamaideparte,ultima submulime restrns va conine Nn mesaje, care sunt si , adic se poate scrie: N-n=2 => n=N-2 (2.16) Dac submulimii i se aloc simbolul "0" si submulimii simbolul "1", celor N-2 partiionriputndu-li-sealocaarbitrar"0"sau"1",rezultuntotaldeposibilitide codare.Dac,ns,submulimiiisealocsimbolul"1",iarsubmulimiisimbolul"0", mairezultposibilitidecodare.Rezult,deci,cprinacestprocedeudecodaresepot realizacoduriinstantanee,toateavndtoateaceeasilungimemediea cuvintelor de cod. Prin deIiniie,senumeste cod compact, codul care realizeazlungimeamedieminima cuvintelor de cod. Deoarece prin procedeul de codare HuIIman se obine ceamaimiclungime medieacuvintelordecod,nseamncprinacestprocedeuseobincoduriinstantanee compacte. Evident, un cod absolut optimal este si compact, reciproca neIiind totdeauna valabil. 30 Exemplul 3.1. Se presupune sursa discret de inIormaie caracterizat de distribuia: S : Codarea binar HuIIman a acestei surse se poate realiza astfel: Fig. 3.2. Schema de codare pentru exemplul 3.1 Grafulsicuvinteledecodcorespunztoarecodriiefectuatesunt date n Fig. 3.3. Fig.3.3. GraIul corespunztor codului 31 CodurileHuIImandedispersieminimseobincndlareordonareasurseirestrnse, simbolul compus se plaseaz pe poziia ceamai de sus posibilnsursa restrns. nIelul acesta cuvntuldecodatribuitsimboluluicompusvaaveaceamaimiclungimeposibil.Cumacest cuvntvadevenipreIixpentrusimbolurileconstituente,cuvinteledecodcorespunztoare acestora vor avea o lungime cu o unitate mai mare dect lungimea preIixului, deci si acestea vor rezultadelungimeminim.Caurmare,diIereneledintrelungimilecuvintelordecoddevin minime, ceea ce va conduce, evident, si la o dispersie minim. PentruIixareaideilor,sepresupunesursadiscretdeinIormaiecaracterizatde distribuia: S : PentruaceastsursseeIectueazcodareaHuIIman,plasndntimesajelesursei restrnse pe poziiile cele mai jos posibile n list si apoi pe poziiile cele mai de sus posibile. n primul caz rezult schema de codare din Fig. 3.4, iar graIul si cuvintele de cod ca n Fig. 3.5. 32 Pentru acest cod, lungimea medie si dispersia sunt:

Pentru cazul n care n codarea HuIIman mesajele sursei restrnse se plaseaz pe poziiile cele mai de sus n list, se obine schema de codare din Fig. 3.6 si graIul si cuvintele de cod ca n Fig. 3.7. 33 Pentru acest cod, lungimea medie este, evident, aceeasi, n timp ce dispersia devine: DesidinpunctdevedereinIormaional,celedoucodurisuntidentice,npracticse preIerIolosireacelordedispersieminim,dinmotivedetransmisie.Deexemplu,dacse doreste s se transmit mesaje ale sursei cu o vitez de 10.000 mesaje/sec., este necesar un canal cu capacitatea de 22.000 bii/sec. Deoarece viteza de generare a biilor oscileaznjurulvalorii de22.000bii/sec.,IunciedesuccesiuneademesajeIurnizatelaunmomentdat,iesireasursei este ncrcat ntr-un buffer.Dac, de exemplu, sursa genereaz la un moment dat siruri de mesajesimai multe secunde, pentru primul cod se genereaz 40.000 bii/sec. si n Iiecare secund ar trebui un buIIer de capacitate de 18.000 bii. Cu al doilea cod se genereaz 30.000 bii /sec. sibuIIerul ar trebui saibcapacitateade8.000bii.Dacsetransmitsiruridemesaje,cuprimulcodse genereaz 10.000 bii/sec. si canalul nu e Iolosit la capacitatea sa, rmnnd un deIicit de 12.000 bii/sec,pecndcualdoileacodsegenereaz20.000bii/sec,deIicitulexistentnexploatarea canalului Iiind numai de 2.000 bii/sec. Asadar, din motive de transmisie este mai rezonabil a se alege al doilea cod dect primul. 34 1.5. Procedeul de codare binar Shannon - Fano. Acestprocedeuseaplicdeobiceincazurileparticularencareprobabilitilede Iurnizare ale mesajelor sunt puteri ntregi pozitive ale lui (1/2), adic, de Iorma: p( =,( )k= (2.17) unde este un numr ntreg pozitiv. Dac relaia (3.48) este satisIcut, mulimeaS = {s1, s2 ,..., sN}a mesajelor sursei discrete de inIormaie ce urmeaz aIi codat poate Ii partiionatn dousubmulimisi,astIelnctsumaprobabilitilormesajelorinclusen,notatcu p( ),sIieegalcusumaprobabilitilormesajelorinclusen,,notatcup( ).SursaS Iiind totdeauna complet, se poate scrie: (2.18) Submulimile sise pot partiionala rndullorn si, respectivn si , astIelnct suma probabilitilormesajelorinclusen cele patru submulimisIie aceeasi, adic se poate scrie relaia: (2.19) Seprocedeaznmodanalogpnseobinsubmulimicareconinunsingurmesaj.Se observcIiecaresubmulimearesumaprobabilitilormesajelorincluseegalcuoputere ntreag a lui (1/2). Puterea ntreag este egal cu numrul indicilor submulimii respective Dac submulimea conine un singur mesaj,, si are unnumr de indici egal cu, atunci se poate scrie: deunderezultnecesitateacasursaSceurmeazaIicodats-siIurnizezemesajelecu probabiliti egale cu la o putere ntreag, pozitiv. Sursa Iiind complet, se poate scrie relaia (1.21): 35 (2.21) nlocuind (1.20) n (1.21), rezult relaia (1.22): (2.22) ceea ce nseamn c inegalitatea lui Kraft devine n acest caz egalitate. Cuvintele de cod se vor obine, atunci, astfel: 1. Se atribuie simbolul "0" submulimii si simbolul "1" submulimii, (sau invers), astIelctoatecuvintelecorespunztoaremesajelorinclusenvorncepecu"0"sitoate cuvintele corespunztoare mesajelor incluse n, vor ncepe cu "1" (sau invers); 2.Sealocsubmulimilorsicaaldoileamesaj"0",iarsubmulimilorsi caaldoileamesaj"1"(sauinvers).nIelulacesta,cuvinteledecodcorespunztoare mesajelor incluse n vor ncepe cu 00, cuvintele de cod corespunztoare mesajelor incluse n vorncepe cu 10 siasamai departe, cuvintele de cod corespunztoaremesajelorindusen vor ncepe cu 11. 3. Operaia se continu n acelasi mod, pn cnd n Iiecare submulime rmne un singur mesaj,cruiaivacorespundecuvntuldecodIormatdinsiruldeindiciaisubmulimii respective.DeoarecelaIiecarepartiionarendousubmulimiatribuireamesajelor"0"si"1" estearbitrar,rezultcprinacestprocedeusepotobineomultitudinedecoduriinstantanee, dar toate absolut optimale. n principiu, procedeul de codare descris s-ar putea aplica n general, adic si atunci cnd relaia (1.21) nu este satisIcut. n acest caz, partiionrile n submulimi trebuie eIectuate astIel nct suma probabilitilor mesajelor incluse n submulimile respective s Iie ct mai apropiate. Atribuind simbolurile "0" si "1" ca n procedeul descris, se obin totdeauna coduri instantanee. Cu ct sumele probabilitilor mesajelor componente ale submulimilor respective vor Ii mai apropiate, cu att lungimea medie a cuvintelor de cod va Ii mai mic. 36 Exemplul 3.2. Se consider sursa discret de inIormaie caracterizat de distribuia: S : Procedeul de codare binar Shannon - Fano este sintetizat n tabelul de mai jos: Graful arborescent atasat codului astfel obinut este reprezentat n Fig. 3.8 37 $SOLFDLH SimulareacuajutorulprogramuluiMATLABaalgoritmuluidecompresie Shannon-Fano ncadrullucrrilordelaboratorvaIipusladispoziieoaplicaiesoItwarecare implemeneaz algoritmul de compresie Shannon-Fano.Ecranul aplicaiei este prezentat n Iigura urmtoare. Exerciii rezolvate. Exemplu n tabelul de mai jos sunt prezentate patru coduri separabile, mesajABCD s0 00000 s1 01100110 s2 10110011110 s3 1111100111111 38 FolosindcodulB,succesiuniles ss s3 1 0 2secodifica1110100110.Dupareceptinarea primelorsasebitisepoatedeterminacas-areceptionats s3 1.DacaInsasefoloseccodulC, succesiuneas ss s3 1 0 2secodifica011010011.Dupareceptionareaprimelorsasebiticonducela decodareas3 dar secventa 01 poate fi interpretata la acel moment fie cares1fie ca,s2fie cas3, ambiguitatea rezolvndu-se abia dupa receptia urmatorilor biti. Un cod de tip C se numeste cod instantaneu.Conditia necesara si suIicienta ca un cod sa Iie instantaneu este ca nici un cuvnt de cod sa nu Iie preIix al altui cuvnt de cod (conditia de preIix). 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 log2142 2121214142 181874biti Pentru codul A lungimea medie a codului estenA= 2 siq Aiar = = =742 278122log Codurile B si C cu aceiasi lungime medie n nB C= = + + + = 0 5 1 0 25 2 0125 3 0125 4 1875 , , , , , q q B CB C= = == =1 751 8751415115,, Codul D arenD= + + = 0 5 1 0 25 2 0125 3 1 75 , , , ,siq D D= = =1 751 75 21 02,, log 39 TESTE DE AUTOEVALUARE I TEME DE CONTROL Testul nr. 1 1.Se d sursa A prin urmatoarea repartiie de probabiliti: ||.|

\|=02 . 0 02 . 0 02 . 0 04 . 0 07 . 0 07 . 0 14 . 0 14 . 0 48 . 09 8 7 6 5 4 3 2 1a a a a a a a a aA

SsecodiIicesursaAutilizndmetodadecodiIicareHuIImansissecalculeze lungimea medie a cuvintelor de cod. Testul nr. 2 2.Se d sursa A prin urmatoarea repartiie de probabiliti: ||.|

\|=02 . 0 02 . 0 02 . 0 04 . 0 07 . 0 07 . 0 14 . 0 14 . 0 48 . 09 8 7 6 5 4 3 2 1a a a a a a a a aA

SsecodiIicesursaAutilizndmetodadecodiIicareShannon-Fanosissecalculeze lungimea medie a cuvintelor de cod. 7HPGHFRQWURO Se consider o surs cu alIabetul| | | |6 5 4 3 2 1, , , , , s s s s s s S =si probabilitile | | | | 2 . 0 , 1 . 0 , 25 . 0 , 3 . 0 , 1 . 0 , 05 . 0 = P : a.ssedetermineuncodcompactIolosindalgoritmuldecodareHuIIman,dac alfabetul codului este| | | | 1 , 0 = Xsi dac alIabetul codului este| | | | 2 , 1 , 0 = X ; b.pentruceledoucazurissecalculezelungimeamedieacuvintelordecodsi eficiena codului. 40 BIBLIOGRAFIE RECOMANDAT LA MODULUL 2: |1| A. Sptaru:TeoriaTransmisiunii Informaiei, Ed. Didacticsi Pedagogic, Bu- curesti, 1983. |2| A. T. Murgan,I. Spnu, I. Gavt, I. Sztojanov, V. E. Neagoe, A. Vlad:Teoria Transmisiunii Informaiei- probleme, Ed. DidacticsiPedagogic,Bucuresti, 1983 [3] I. Angheloiu, Teoria codurilor, Ed. Militar, Bucuresti, 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. |5| V. Munteanu, Transmiterea si codiIicarea inIormaiei, Note de curs. 41 MODULUL 3 CODURI DETECTOARE I CORECTOARE DE ERORI ncazultransmisiilorladistanerelativmari,prinapariiainerenta perturbaiilor,opartedinsimboluriledinalIabetulcodului,ceIormeaz cuvinteledecodatasatemesajelor,potIimodiIicate,astIelnctceeacese recepioneaznumaicorespundecuceeaces-atransmis.Deoarecenmarea majoritateasituaiilorpracticeseIolosestecaalIabetalcoduluinumai0si1 (usor de realizat)vom consideran continuare doar acest caz. n situaian care alIabetul codului este numai 0 si 1, datorit perturbaiilor codului, un 0 transmis poate deveni 1 si invers. Din aceast cauz se spune c perturbaiile care apar au un caracter aditiv. 01

0 1 01 10 Dac se transmite 0 si se recepioneaz1 perturbaia0 1 = 1. Din codareamesajelor (surselor) pentru canale cu perturbaii se pun dou probleme: 1. detecia erorilor 2. corecia automat a erorilor 1codareatrebuieastfelefectuatnctlarecepiesputemdecidedac ceeaces-arecepionatestecorectsaueronat,Irpreteniadeastabilisi locurile n cuvntul de cod n care s-au introdus erori. 2codareatrebuieastIeleIectuat,nctlarecepiesavemposibilitatea nu numai a decide dac ceea ce s-a obinut este corect, ci si de a corecta automat erorile care au aprut pe canal. Problemadetecieierorilorestemaisimpl,nschimbnecesituncanal de transmisiuni cu dublu sens, deoarece, ori de cte ori la recepie se detecteaz prezenaerorilor,sexisteposibilitateacereriideretransmisieacuvntului recepionateronat.Seceretransmitereacuvntuluirecepionateronatpnce acesta este recepionat corect ; rezult o ntrziere la recepionarea inIormaiei.nscopulntocmiriicodurilordetectoaredeerorisaucorectoaredeerori, seIolosescoserientreagdecoduri,bazatepediIeriteteoriimatematice,o prim clasiIicare constnd n : coduri blocla care Iiecare cuvnt de cod are aceeasi lungimecodurinonbloc(saurecurente)lacaretransmisiaseIacecursiv,Iro delimitare precis a cuvntului de cod. 42 MODULUL 3 CAPITOLUL 1 CODURI DETECTOARE I CORECTOARE DE ERORI 3.1. Codarea si decodarea pe canale perturbate S-aaratatanteriorcaperformantaglobalaaunuisistemdetransmiterededateeste probablitatea de eroare.Transmitereanbanda debaza saumodulatia sunt aIectate de o serie de constrngeri care fac uneori imposibila obtinerea unei probabilitati de eroare prescrise. Caleaprincaresepoateobtineprobabilitateadeeroareprescrisaestefolosirea redundanteicontrolate.Blocurilefunctionalecareefectueazaaceastasarcinasuntcodorulsi decodorul canalului.Codorulcanaluluiadauganmodsistematicbitilamesajultransmis.Acestibiti 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 ^ ` bkcu un debitrb pe un canal zgomotos.Datoritazgomotuluifluxuluidedatereceptionate ^ `

bkdiferauneoridesecventa transmisa ^ `bk. Seimpunecaprobabilitateadeeroare P b bk k

z saIiemaimicadectoanumita valoare.Codorul canalului si decodorul canalului au ca scop reducerea probabilitatii globale de eroare.Codorulmparte bitimesajuluinblocuri dectek bitisinlocuiesteIiecarebloc cu un cuvnt de cod den biti, adaugndn k biti. Decodorul primeste cuvntul de cod, care este uneori alterat si ncearcasa decodeze ceikbiti ai mesajului.Desibitidecontrolnuaducnicioinformatiereceptorului,eipermitdecodoruluisa detecteze si sa corecteze erorile de tramsmitere reducnd prin aceasta probabilitatea de eroare.Proiectarea unui codor/decodor consta n selectarea regulilor de generare a cuvintelor decodporninddelablocurilemesajsiapoideextragereablocurilormesajdinversiunea receptionata de cuvnt de cod.n Iigura 3.1 este prezentata schema bloc pentru un sistem de codare/decodare. 43 CodurilecareeIectueazacontroluleroriisuntclasiIicaten:coduriblocsicoduri convolutionare. Din codurile bloc, unui mesaj dekbiti i se asocieaza un cuvnt de cod den biti care actioneazarbiti pe baza celorkbiti cu continut informational. La receptie biti de control sunt utilizati pentru a verifica biti de informatie din bloculprecedent. Pentru codurile convolutionare,bitidecontrolsuntnmodcontinuuinseratintrebitideinIormatie;bitide controlveriIicndnunumaibitideinIormatiedinbloculprecedentcisidinalteblocuri anterioare. DistantaHamming.Distantantredouacuvintebinaredelungime nu x x x v y y yn n= =1 2 1 2, ,......, ; , ,......, ${ } ( )x yi i, , e 0 1 estenumarulpozitiilor de acelas rang n care doua cuvinte diIera ( )d u v x yi iin, = =1 (3.1) Observatie Numarul natural( )d u v ,verifica axiomele distantei ( ) ( )( )( ) ( ) ( )( ) , ,( ) ,( ) , , ,ad u v d v ub d u v u vc d u v d u w d w v= >= =s +00(3.2) Codor canal mesaj k mesaj control kn-k Modulator Canal cuvnt de cod n mesaj k Decodor canal Demodulator rb r rnkc b= Fig. 3.1 44 Oreprezentaregeometricaaluiu poatefiunpunctdecoordonatex xn 1,...... In Rn.Cele2ncombinatiidenbitisuntvrIurileunuihipercubdelatura1.InIigura urmtoareeste reprezentat un astIel de cub pentruR3. Dacatoatecuvinteledecodausens,atuncioriceeroareconducelaunaltcuvntde cod si nu poate Ii depistata. Daca nsa separam din cele2n cuvinte de cod, numai2k atunci esteposibilsasedepistezeuneleerorisingularedeoarece2n k combinatenuausens.n general, Iie un cod n care toate cuvintele sunt la distante mutuale de cel putin egale cud0. Cazul 1 Conditianecesara si suficienta ca un cod binar sa poata corecta celmultrerori este cad r02 1 t Cazul 2 Dacad r02 tse pot corecta cel multr 1 erori. 3.2.Coduri blocliniare Seconsideracoduribloc,ncareIiecare,nIiecareblocdek bitimesajestecodat ntr-unblocden k ! bitiprinadaugareaden kbitidecontrol.Bitiidecontrolsunt obtinuti pe baza celorkbiti mesaj, asa cum este ilustrat n Iigura 3.3. 000 001 011 111 010 110100 101 x1 x3 x2 Fig 3.2 Distanta Hammingntre doua vrIuri este celmai micnumardelaturicare le unesc 45 Codor canal mesaj biti de control kbiti kn k mesajcod bloc Fig. 3.3 Blocurile den biti de la iesirea codorului canalului sunt numite cuvinte de cod si codurile pentru care biii mesaj apar la nceputul cuvntului de cod sunt numite coduri sistematice.nplusdacaIiecaredicele2kcuvintedecodpoatefiexprimatcao combinatie lineara dekvectori independenti, atunci codul este si linear. Codarea consta n doua etape: (1) secventa de biti inIormationali este segmentate n blocuri mesaj de ctekbiti. (2)codorultransformafiecareblocmesajntr-unblocmaimaredenbitin conformitate cu anumite reguli. Acestin k biti aditionali sunt generati printr-o combinatie lineara de biti mesaj si operatiile pot fi descrise folosind matrice. Blocul mesaj este reprezentat printr-un vector linie avndk componente | | { }( )D d d d cu d i kk i= e e1 20 1 1 ...... , ; ,(3.3) Fiecare bloc mesaj este transIormat ntr-un cuvnt de cod cde lungimen | |C c c cn=1 2......Se observa ca eficienta acestui cod estek n. Pentruuncodlinear,sistematicprimiik bitiaicuvntuluidecodsuntbitiimesaj adica c d i ki i= =1 2 , ,......, (3.4) Ultimiin k biti ai cuvntului de cod sunt bitii de control generatii pe baza celorkbiti ai mesajului n conIormitate cu anumite reguli predeterminate: mesaj 46 c pd pd p dc p d p d p dk k kn n k n k k n k k+ = + + += + + +1 11 1 21 2 11 1 2 2,, , ,

(3.5) Coeficientiipi 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 dp p pp p pp p pp p pk nn kn kn kn kk k k n k1 111 12 121 22 231 32 31 21000 00100 00010 0000 01... ...... ...... ...... ...... ...,,,, ,=

((((((( (3.6) sau C D G = (3.7) undeGesteomatricedetipk n numitamatriceageneratoareacoduluisiare forma | |G I Pkk n=(3.8) MatriceaI kestematriceaunitatedeordinulk iarP esteomatricearbritara ( )k n k . Sa remarcam ca specificarea luiPdefineste complet codul bloc( )n k , . Proiectareaunuicodbloc( )n k , prinselectareauneimatriciP trebuiesaaiban vedere urmatoarele proprieteti - comoditatea implementarii - capacitatea de a corecta erorile singulare si pachetele de erori (burst errors) - eficienta codului da fie ridicata PrineficientacoduluiseIntelegeraportul knpentruoanumitacapacitatede detectie/corectie. Trebuie mentionat ca nu exista o procedura de selectie a matriceiPcare sa satisfaca toate proprietatile de mai sus. 3.3. Exemple de coduri liniare Codul Hamming CelemaicunoscutecoduriliniaresintcodurilebinareHamming.Elesedaucu ajutorulmatriceidecontrolH,careesteformatadinmliniisi m2-1coloane,larcoloanele sunt toate elementele nenule de lungime m. Spatiul nul al acestei matrice are distanta minima egala 3, adica este un cod (nk) 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 Reprezintaocategoriedecoduriliniarecaresedeosebescinmodesentialdeclasa codurilorliniareprinalgoritmuldecodificaresidecodificare(codulHamming,coduri simetrice pe k pozitii) . La acest cod, spre deosebire de codurile simetrice algoritmul de decodificare nu poate fietapizat,atatdetectia,corectia,catsidecodificareapropriu-zisaseproducsimultan, rezultand in urma algoritmului, in mod direct simbolurile informationale continute in cuvantul de cod receptionat.Lungimea n a codului este o putere a lui 2, adic n2m. Pentru r, numr ntreg pozitiv, numrul poziiilor inIormaionale este0rimik C== (3.8) Numrul simbolurilor de control este dat de relaia 111 ...mm m rn k C C = + + +(3.9) Distana minim Hamming ested2m-r LacodulReed-Muller,spredeosebiredecelesistematice,algoritmuldedecodificare 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. FieVnunspatiuvectorialpesteGF(2),ndimensionaliavandcomponentele0sau1. Fie u(a1,a2,a3,.,an) si v(b1,b2,b3,.,bn), pe spatiul vectorial Vn se poate deIini produsul vectorialuxV(a1*b1,a2*b2,.an*bn)siprodusulscalar - =i ib a V u&&*si ) 2 ( * GF V u e&&. Se pot observa urmatoarele : -produsul scalar este nul daca ponderea produsului vectorial este un numar par ; -fatadeoperatiiledescrise,multimeavectorilordenelementeformeazaoalgebra liniara, asociativa si comutativa. Codul Reed-Muller se poate defini cu urmatorii parametrii : -n=2m, unde n este dimensiunea vectorilot cuvintelor de cod ; - ==rkknC k0, unde k este numarul de simboluri informationale din cod ; -d=2m-r, unde d este distanta minima a codurilor ; - 1 2 1... 1 + + + + = r nm m mC C C k n , pentru care se defineste codul RM(m,r) ; - ((

=2 1 dt 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,generatdeurmatoriivectoriliniariindependenticareconstituiematricea generatoare : V01111 1111 1111 ...1111 Vm0000 0000 0000 ...1111 48 Vm-10000 1111 0000 .. 1111 ............ Vm x Vm-1 ........(3.10) ............. V2 x V1 .......... .............. Vr x Vr-1 x V1 ....... AlgoritmuldecodificarepresupuneprodusuldintremesajulinformationalX=a1xkx Gkxn. CodulReed-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 : (11111111111111111111111111111111){V0} (00000000000000001111111111111111){V5} (00000000111111110000000011111111){V4} (00001111000011110000111100001111){V3} (00110011001100110011001100110011){V2} (01010101010101010101010101010101){V1} (00000000000000000000000011111111){V54} (00000000000000000000111100001111){V53} (3.11) (00000000000000000011001100110011){V52} (00000000000000000101010101010101){V51} (00000000000011110000000000001111){V43} (00000000001100110000000000110011){V42} (00000000010101010000000001010101){V41} (00000011000000110000001100000011){V32} (00000101000001010000011100000101){V31} (00010001000100010001000100010001);{V21} Se defineste G x m X&&&

unde m=(a0 a5 a4 a3 a2 a1 a54 a53 a52 a51 a43 a42 a41 a32 a31 a21). Algoritmuldedecodificaresebazeazaperelatiidecontrol.Pentruascrierelatiilede 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 scriecateunsetderelatiidecontrolcorespunzatorcomponenteiinformationaledinmesajul transmis care are acelasi indice cu vectorul analizat. Mesajul informational este : a1xk=(a0a5a4a3a2a1a54a53a52a51a43a42a41a32a31a21). 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 : 3 2 1 0 21y y y y a 7 6 5 4 21y y y y a 49 11 10 9 8 21y y y y a 15 14 13 12 21y y y y a 19 18 17 16 21y y y y a 23 22 21 20 21y y y y a 27 26 25 24 21y y y y a 31 30 29 28 21y y y y a Iar a21 este valoarea majoritara a sistemului. 5 4 1 0 31y y y y a 7 6 3 2 31y y y y a 13 12 9 8 31y y y y a 15 14 11 10 31y y y y a 21 20 17 16 31y y y y a 23 22 19 18 31y y y y a 29 28 25 24 31y y y y a 31 30 27 26 31y y y y a Iar a31 este valoarea majoritara a sistemului. 6 4 2 0 32y y y y a 7 5 3 1 32y y y y a 14 12 10 8 32y y y y a 15 13 11 9 32y y y y a 22 20 18 16 32y y y y a 23 21 19 17 32y y y y a 30 28 26 24 32y y y y a 31 29 27 25 32y y y y a Iar a32 este valoarea majoritara a sistemului. 9 8 1 0 41y y y y a 11 10 3 2 41y y y y a 13 12 5 4 41y y y y a 15 14 7 6 41y y y y a 50 25 24 17 16 41y y y y a 27 26 19 18 41y y y y a 29 28 21 20 41y y y y a 31 30 23 22 41y y y y a Iar a41 este valoarea majoritara a sistemului. 10 8 2 0 42y y y y a 11 9 3 1 42y y y y a 14 12 6 4 42y y y y a 15 13 7 5 42y y y y a 26 24 18 16 42y y y y a 27 25 19 17 42y y y y a 30 28 22 20 42y y y y a 31 29 23 21 42y y y y a Iar a42 este valoarea majoritara a sistemului. 12 8 4 0 43y y y y a 13 9 5 1 43y y y y a 14 10 6 2 43y y y y a 15 11 7 3 43y y y y a 28 24 20 16 43y y y y a 29 25 21 17 43y y y y a 30 26 22 18 43y y y y a 31 27 23 19 43y y y y a Iar a43 este valoarea majoritara a sistemului. 17 16 1 0 51y y y y a 19 18 3 2 51y y y y a 21 20 5 4 51y y y y a 23 22 7 6 51y y y y a 25 24 9 8 51y y y y a 27 26 11 10 51y y y y a 29 28 11 10 51y y y y a 51 31 30 15 14 51y y y y a Iar a51 este valoarea majoritara a sistemului. 18 16 2 0 52y y y y a 19 17 3 1 52y y y y a 22 20 6 4 52y y y y a 23 21 7 5 52y y y y a 26 24 10 8 52y y y y a 27 25 11 9 52y y y y a 30 28 14 12 52y y y y a 31 29 15 13 52y y y y a Iar a52 este valoarea majoritara a sistemului. 20 16 4 0 53y y y y a 21 17 5 1 53y y y y a 22 18 6 2 53y y y y a 23 19 7 3 53y y y y a 28 24 12 8 53y y y y a 29 25 13 9 53y y y y a 30 26 14 10 53y y y y a 31 27 15 11 53y y y y a Iar a53 este valoarea majoritara a sistemului. 24 16 8 0 54y y y y a 25 17 9 1 54y y y y a 26 18 10 2 54y y y y a 27 19 11 3 54y y y y a 28 20 12 4 54y y y y a 29 21 13 5 54y y y y a 30 22 14 6 54y y y y a 31 23 15 7 54y y y y a Iar a54 este valoarea majoritara a sistemului. 52 Dupaceaufostscriserelatiiledecontrolcorespunzatoarevectorilorcompusi,se procedeaza in felul urmator: xseeliminainfluentadinrelatiiledecontrolacomponentelorcorespunzatoare vectorilor compusi ; xsescriunumarulderelatiidecontrolpentruvectoriisimpli,innumardecate componente diferite de zero sunt pe fiecare din liniile lui V (pentru vectorii simpli). Urmatorul pas este determinarea lui y` : 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. 1 0 1y y a 3 2 1y y a 5 4 1y y a 7 6 1y y a 9 8 1y y a 13 12 1y y a 15 14 1y y a 17 16 1y y a 19 18 1y y a 21 20 1y y a 23 22 1y y a 25 24 1y y a 27 26 1y y a 29 28 1y y a 31 30 1y y a Iar a1 este valoarea majoritara a sistemului. 2 0 2y y a 3 1 2y y a 6 4 2y y a 7 5 2y y a 10 8 2y y a 53 11 9 2y y a 14 12 2y y a 15 13 2y y a 18 16 2y y a 19 17 2y y a 22 20 2y y a 23 21 2y y a 26 24 2y y a 27 25 2y y a 30 28 2y y a 31 29 2y y a Iar a2 este valoarea majoritara a sistemului. 31 27 330 26 329 25 328 24 323 19 322 18 321 17 320 16 315 11 314 10 313 9 312 8 37 3 36 2 35 1 34 0 3y y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y a Iar a3 este valoarea majoritara a sistemului. 54 31 23 430 22 429 21 428 20 427 19 426 18 425 17 424 16 415 7 414 6 413 5 412 4 411 3 410 2 49 1 48 0 4y y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y a Iar a4 este valoarea majoritara a sistemului. 31 15 530 14 529 11 528 12 527 11 526 10 525 9 524 8 523 7 522 6 521 5 520 4 519 3 518 2 517 1 516 0 5y y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y ay y a Iar a5 este valoarea majoritara a sistemului. Dupaceaufostevaluatecomponenteledelaa1laa5,seeliminainfluentavectorilor simpli din vectorul y` : y y`-(a1*V1+ a2*V2+ a3*V3+ a4*V4+ a5*V5) 55 Pentruaevaluapea0,observamnumarulmajoritardecomponentediny iarvaloarea celor 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 odeosebitcapacitatedecorecieaerorilor,caregeneralizeazcodurileHammingpentru corecia erorilor multiple. Un cod ciclic binar, corector de t erori, avndxLungimea blocului n= , cu m , ntreg xNumrul simbolurilor de control n-k mt, t , xDistana d , senumestecodBHCdacaredreptpolinomgeneratorg(x)polinomuldecelmaimicgrad peste cmpul GF(2) care are ca rdcini elementele ale cmpului Galois GF( ). Prin urmareg( )=0,i=Fiepolinomulminimalallui,adicpolinomuldecelmaimicgradpeste GF(2)astIelnct 0.Atuncipolinomulgeneratorg(x)trebuiesIiecelmaimic multiplu comun (c.m.m.m.c) al polinoamelor, si anume: g(x)= (c.m.m.m.c){ ,}. Un numr par i poate fi exprimat sub forma i=k* , k , impar. Atunci=este conjugatulelementului. Dar un polinom care admite rdcinile admitedreptrdcinisiconjugateleacestora.Prinurmare,siauacelasipolinom minimalsi deci. Atunci polinomul generator este de formag(x)= (c.m.m.m.c){ ,}.(3.12) Grdul Iiecrui polinom minimal Iiind cel mult egal cu m , polinomul g(x) va fi de grad cel mult egal cu mt , astIel nct numrul simbolurilor de control, n-k , va fi cel mult egal cu mt : n-kmt. La limit, n cazul coreciei unei singure erori, t1, rezult n-kmt. 56 Codul BCH delungime, cu m 10 , se numesc coduri BCHn sens restrns (sau primitive). Aceste coduri sunt generate de elemente primitive de ordin mai mic dect din GF( ). UncodBCHdelungimecorectordeosingureroareestegeneratde polinomul g(x)= . Polinoamele minimale ale elementelor din GF( ) generate de g(x)=1+x+ Exemplu.trebuie s Iie de grad m4 , deci de Iorma=1+(3.13) Deoarece=1+ (3.14) Conform tabelului 3.3 nseamn c (3.15) si rezult Deci= 1+x+ (3.16) 57 Deoarece din 2t-13 rezult t2, se deduce un cod BCH corector de dou eroriside lungimen==15estegeneratdeg(x)=(c.m.m.m.c){ , }= (x)=1+ . Fiev(x)unpolinomdecodcucoeficieniinGF(2),asociaiunuocuvntdecod v(x)= .Polinomuldecodadmiterdcinile din GF( ). Dac este o rdcin a lui v(x) pentru 1 , atunci+(3.17) Se introduce matricea(3.18) astIel nct v=0. RezultcvestenspaiulnulalmatriceiHsideciHestematricedecontrola codului. Aplicaii Simularea cu ajutorul programului MATLAB a codului BCH CodurileBCHfacpartedincategoriacodurilorciclice.Sevaimplementan programul MATLAB schema prezentat n Iigura urmtoare. Se vor utiliza urmtoarele blocuri: - Random-I ntegerGenerator:genereaznumerentregidistribuiten intervalul [0, M-1]. Parametrii blocului sunt: - M-ary number`este2^7deoarececodul BCHutilizatesteBCH(15,7) si numerele generate sunt reprezentate n binar pe 7 bii. - Initial seed`este [1458]. Modificnd acest parametru se modifica secvena de numere generate. - Sample time` este 1. Genereaz cte un numr la fiecare secund. -I ntegertoBitConverter:transformunvectordentregintr-unvectordebii. Parametrul blocului este: - Number of bits per integer` este 7. Se lucreaz pe 7 bii. -BCHEncoder:creazuncodBCHdindatelevectoruluibinar.Parametriiblocului 58 sunt: - Codeword length N` este 15. - Message length K` este 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 cuvntul de cod cu care se adun este reprezentat pe 15 bii. - Initial seed` este 12345. - Sample time` este 1pentru a se genera unesantionlafiecare secund.-BCH Decoder:decodeaz un cod BCH pentru a reface vectorul binar transmis. Parametrii blocului sunt: - Codeword length N` este 15 . - Message length K` este 7 deoarece se utilizeaz codul BCH(15,7). -BittoI ntegerConverter:transform un vectorde bii ntr-un vectordentregi. Parametrul blocului este: - Number of bits per integer` este 7. - ErrorMeter:comparsemnaleledelaintrare,leafiseazsievalueazratadeeroare. Parametrii blocului sunt: - Bit per symbol` este 7deoarece utilizeaz7bii pentrufiecaresimbol transmis. -Number of digits on display` este 20 deoarece afiseaz 20 de simboluri. - Delay between input (1st port) and output (2nd port)` este 0. -Sampletime`este1deoareceseconsiderunesantionlafiecare secund. - Sum: afiseaz suma elementelor de la intrare. Parametrii blocului sunt: - Icon shape` este rectangular. - List of signs` este +. -Graph Scope: afiseaz numrul de erori. Parametrii blocului sunt: - Time range` este 10. - y-min` este -1. - y-max` este 5. - Line type` este 'ro/b*' - Mux: multiplexeaz semnalele de la intrare. - Display: afiseaz valoarea de la intrare. Sevarealizaschemablocaratat sisevarula pentru diferitevalorialeprobabilitatii de eroare si se vor analiza rezultatele. 59 Simularea cu ajutorul programului MATLAB a codului Hamming ncadrullucrrilordelaboratorvaIipusladispoziieoaplicaiesoItwarecare implemeneazalgoritmuldecompresieShannon-Fano.Ecranulaplicaieiesteprezentatn Iigura urmtoare. 60 Exerciii rezolvate. Un numr de 8 simboluri se transmit cu ajutorul unui cod Hamming grup corector de o eroare si detector de erori duble. Se cere: a.ssedeterminenumrulsimbolurilordeinIormaiek,alcelordecontrolm,si lungimea cuvntului de cod n; b.s se scrie matricea de control H a codului; c.s se stabileasc expresia corectorului corespunztor eronrii simbolului 2c ; d.s se determine corectorul corespunztor eronrii simbolurilor 2csi 1c ; e.s se determine cuvintele de cod; f.s se precizeze dac> @ 0 1 1 0 0 1 1veste un cuvnt al acestui cod. Soluiea).NumrulsimbolurilordeinIormaieksedetermincurelaiasi rezult k3. MargineaHammingdpentrunumrulsimbolurilordecontrol: , din care rezult c m3. Laacestesimboluridecontrol,carepermitcoreciauneierori,trebuieadugat simbolul de verificare la paritate, asa nct numrul total al simbolurilor de control va Ii: =m+1=3+1=4 Structura cuvntului de cod va Ii: Unde este simbolul de veriIicare a paritii, 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 =c). Pentru acest caz cuvntul de eroare este de Iorma: Cu relaia (2.34) rezult pentru expresia corectorului Din expresia corectorului rezult c apare o eroare corectabil ( pe poziia a 2-a (z= ). d). Pentru acest caz cuvntul eroare este de Iorma: si rezult: =Corectorul arat c apar dou erori detecctabile ( ). e).CuvinteledecodsepotscriecalculndsimboluriledecontroldinceledeinIormaiecu relaia, din care rezult:

62 Cuvintele de cod se gsesc n tabelul urmtor. Simboluri Cuvinte 0000000 1010101 1100110 0110011 1111000 0101101 0011110 1001011 I). Se calculeaz corectorul astfel: = =Deoarece iar z0 cuvntul dat este un cuvnt al acestui cod, ceea ce era usor de constatat si prin inspectarea tabelului anterior, n care l regsim sub Iorma cuvntului. TESTE DE AUTOEVALUARE I TEME DE CONTROL Testul nr. 1 Se consider un cod grup cu matricea de control de forma:

0 1 1 0 01 0 0 1 01 1 0 0 1Ha.s se determine proprietile de corecie ale codului. Codul este perfect? b.s se stabileasc dac matricea: 63

1 0 0 1 10 1 1 0 1Gpoate s Iie matricea generatoare a codului. c.s se scrie cuvintele de cod utiliznd matricele H si G. BIBLIOGRAFIE RECOMANDAT LA MODULUL 3: |1|A.Sptaru:TeoriaTransmisiuniiInIormaiei,Ed.DidacticsiPedagogic,Bu- curesti, 1983. |2| A. T. Murgan,I. Spnu, I. Gavt, I. Sztojanov, V. E. Neagoe, A. Vlad:Teoria Transmisiunii Informaiei- probleme, Ed. DidacticsiPedagogic,Bucuresti, 1983 |3| I. Angheloiu, Teoria codurilor, Ed. Militar, Bucuresti, 1972. [4]J.C.Moreira,P.G.Farrell,ESSENTIALSOFERROR-CONTROLCODING,John Wiley&SonsLtd,TheAtrium,SouthernGate,Chichester,WestSussexPO198SQ, England,2006.