TTI colocviu.

download TTI colocviu.

of 14

Transcript of TTI colocviu.

Intrebrile pt colocviu TTI 1 - 2006 Pe pag urmat sunt subiectele.. 1)e este entropia? (deIinitie, Iormul, unitate de msur) DEF: valoarea medie a inIormatiei proprii: )( )( ) ( )iipxHX E i x = , respectiv: ( ) ( ) ( ) ( ) log ( )i ii i i ix xHX i x px px px == , |biti|. 2)e este debitul de inIormatie? (deIinitie, Iormul, unitate de msur) sec /1-iti X H X Ht: =,Debitul de informa(ie (data rate) este cantitatea de inIormatie transmis prin canal raportat la unitatea medie de timp 3)are sunt propriettile entropiei? Propriet(ile entropiei: 1.entropia este o Iunctie continu de probabilittile simbolurilor sursei 2.entropia este simetric (are aceleasi valori indiIerent cum sunt ordonate probabilittile simbolurilor sursei) 3.entropia este aditiv 4.valoarea entropiei este ntotdeauna pozitiv K X H , 1= = VV = n =

x p x x pX H /5. / log A X H / log = X H dac si numai dac X are distributie p(X) uniIorm pe alIabetul / (simbolurile sunt egal probabile) Pentru simboluri egal probabile:/ mare X H mare. 6.entropia este o Iunctie concav n raport cu probabilitatea p 4)Precizati diIerentele dintre Sursa Discret Fr Memorie (SDFM) si Sursa Discret u Memorie (SDM). Pentru o SDM, probabilitatea de emitere a unui simbol este dependent de simbolul precedent sau de mai multe simboluri emise la momente de timp anterioare, in timp ce pentru SDFM probabilitatea de emitere a unui simbol 3x , la momentul de timp 3t 3 = , este independent de simbolurile emise la momentele de timp anterioare 113t 3

=. p(x1,x2.....xn)Hp(xi) SDFM daca sunt si identic distrubuite p(x1,x2.....)pn(x) p(x1,x2.....xn)p(x1)Hp(xi,xi-1) SDM 5)e este redundanta sursei? (deIinitie, Iormul, unitate de msur) DEF:RSHmax(S)-H(S) |biti/symbol| 6)DeIiniti sursa extins de ordin 3 Sursa extinsa Xn se poate deI pornind de la sursa initiala X astIel:X:/-~ x1,x2..xM} ~ Xn:/n 91,92..9M}simbolurile sursei extinse 9j sunt mesaje Iormate din n simboluri ale sursei primare. Daca e SEFM p(9j)Hp(xi) dc e SEM p(9j)p(x1)Hp(xi,xi-1) 7)are sunt propriettile entropiei reunite a doua variabile aleatoare? H(X,Y) - %%p(xi,yj)log p(xi,yj); p(x,y)p(x)p(y,x) 1.Entropiile reunite sunt comutative: X Y H Y X H , , = . 2.Entropia unei v.a. este mai mic dect entropia reunit a dou v.a: Y X H X H , Acu egalitate dac: X f Y Y X H X H = = ,3.Subaditivitatea Pentru o pereche de v.a., ( , ) XY pxy-, entropia reunit este mai mic sau cel mult egal cu suma entropiilor celor dou variabile: ( , ) ( ) ( ) HXY HX HY A, cu egalitate dac si numai dac X, Y sunt v.a. independente. )are sunt propriettile inIormatiei mutuale? Propriet(ile informa(iei: 1.Evenimentul sigur nu produce inIormatie: 1 i ip x i x == ; 2.nIormatia proprie are valoare pozitiv: 1 i ip x i x A AK ; Observa(ie: Iolosim conventialog =deoarece

lim log xx xF = . 3.Realizarea evenimentului xi prin care v.a. X ia valoarea xi este cu att mai incert cu ct probabilitatea p(xi) are o valoare mai mic: ( ) ( ) ( ) ( )ii px px i x i x. 4.nIormatia este aditiv. Fie dou evenimente independente, 1x si 2x, ce au loc cu probabilittile individuale1( )px si 2( )px. nIormatia obtinut prin realizarea celor dou evenimente egaleaz suma inIormatiilor obtinute prin realizarea Iiecrui eveniment n parte: 1 2 1 2( ) ( ) ( ) i x x i x i x =. 9)and o sursa discreta Iara memorie are entropie maxima? Dar debit maxim? H(S Hmax(S)log2M 1)Precizati diIerentele din punct de vedere inIormational dintre o sursa Iara memorie, de ordin 1 si sursa extinsa de ordin 3.H(Sn)nH(S) ;Hmax (Sn)nHmax (S) RSnn RS Pentru sursa extinsa, entropia H si redundanta RHmax-H au crescut, iar randamentul H/Hmax si redundanta81-relativa nu s-au modiIicat. Acest lucru este normal, daca ne gndim ca, n cazul sursei extinse, un simbol este de Iapt o succesiune de simboluri ale sursei primare si, atunci, entropia, care este inIormatia medie pe simbol (n acest caz, simbol extins) creste. Analog, entropia maxima creste si ea. Explicatia cresterii redundantei nu se mai bazeaza pe semnicatia marimii ci pe ordinul ei (creste valoare entropiei deci si redundanta se amplica). Mult mai relevanta este considerarea redundantei relative. 11)are este scopul codrii sursei? a)Codarea sursa:Reprezentarea eIicienta intr-o Iorma cat mai compacta a simbolurilor emise de sursa Scopul codrii sursei:Reprezentarea cat mai compacta a mesajelor (simbolurilor) de date emise de sursa, bazate pe reducerea redundantei sursei 12)DeIiniti codurile absolut optimale. Un cod absolut optimal este un cod optimal de eficien( unitar min1

= = , obtinut pentru min=si, implicit, min( ) log HS = , caz n care literele alIabetului codului sunt echiprobabile: 1 21( ) ( ) ... ( )

px px px

= = = = . 13)DeIiniti codurile unic decodabile. Cod unic decodabil:un cod pentru care Iiecrei succesiuni de cuvinte de cod i corespunde o singur succesiune de simboluri din alIabetul sursei. Un cod unic decodabil, avnd cardinalitatea alIabetului, ,= , cu care se Iormeaz, , M=$cuvinte de cod de lungime i,1, i M = , satisIace inegalitatea KraIt:%D-liA1Un cod pt a Ii unic decodabil trebuie sa indeplineasca urmatoarea conditie: nici un cuv de cod nu poate Ii prefix si suffix pt alt cuvant. 14)DeIiniti codurile optimale. Un cod optimal va trebui s satisIac cerintele: 1.ricare dou cuvinte de cod trebuie s Iie distincte, adic s aib combinatii distincte de litere din alIabetul codului; 2.ici un cuvnt de cod nu trebuie s Iie preIixul altui cuvnt de cod; 3.uvintele de cod mai probabile trebuie s Iie reprezentate printr-un numr mai mic de simboluri din alIabetul codului: dac( ) ( )i ps p s K , atunci, , 1,i iM A V = ; 4.ele mai putin probabile cuvinte de cod, n numr de , trebuie s Iie de lungimi egale si s diIere numai prin ultimul simbol. 15)Se poate stabili dac un cod este instantaneu cu ajutorul inegalittii KraIt? ExempliIicati. Teorema Mc. Millan: SatisIacerea inegalittii lui KraIt este o conditie necesar si suIicient pentru constructia unui cod instantaneu, pentru care cuvintele de cod au lungimile i. 16)are sunt deosebirile ntre algoritmii de codare compact Shannon-Fano si HuIIman? Codarea Shannon - Fano Dac probabilitatile simbolurilor emise de sursa sunt de Iorma( )i

ips

= , atunci: 1.se ordoneaz multimea de simboluri emise de surs n ordine descresctoare a probabilittilor de aparitie a simbolurilor; 2.se aplic pe multimea ordonat, algoritmul de codare binar instantanee. Daca probabilitatile simbolurilor emise de sursa S sunt puteri ntregi negative ale lui 2, EX respectiv distributia de probabilitati este p(S)1/2,1/4,1/,1/} , atunci codarea Shannon- Fano asigura existenta unui cod absolut optimal. odarea propriu-zisa consta n aranjarea simbolurilor sursei n ordine descrescatoare a probabilitatilor, urmata de partitii succesive n submultimi de probabilitati egale, carora li se atribuie pe rnd simbolurile alIabetului codului,si 1. Partitia se termina cnd Iiecare submultime contine un singur simbol. Algoritmul de codare entropica binara Huffman consta n aranjarea simbolurilor n ordine descrescatoare a probabilitatilor si gruparea ultimelor doua simboluri ntr-un simbol restrns cu probabilitatea egala cu suma probabilitatilor simbolurilor componente. Procedeul se repeta pna cnd se ajunge la o sursa restrnsa cu numai doua simboluri. Acestea sunt codate cusi 1. 1.Prin modul n care e Icut codul HuIIman, nu exist o solutie unic. 17)are sunt propriettile codurilor obtinute prin algoritmul HuIIman? Prin codare HuIIman se obtine un cod optimal, unic decodabil(nici un cuvant de cod nu este preIixul sau suIixul altui cuvant), deci si instantaneu (faraprefix). 1)are tip de codare (simbol cu simbol, grupe de cte 2 simboluri sau grupe de cte 3 simboluri) este mai eIicient si de ce? n cazul codarii surselor cu memorie, codarea pe grupe de dou simboluri este mai eIicient dect codarea simbol cu simbol: Memoria sursei reduce eIicienta codului: eIicienta codului H(X)/log2,X,binar~ ,X,2 ~ H(X) red ca cea mai eIicienta este codarea pe grupe de cate 2 simboluri 19)are din codurile urmtoare sunt instantanee si de ce: a) , 1, 1, 11, 111, 1111}; b) , 1, 11, 11, 1}; c) 1, 1, 1, }; d) , 1, 1, 11}? nstanteneu: a) b) c) d) pt k au proprietatae de preIix, adica nici un cuvant de cod nu este preIixul altui cuvant 2)Codarea Huffman binar sau ternar poate duce la ob[inerea unui cod absolut optimal ( Cnd Un cod absolut optimal este un cod optimal de eIicient unitar min1

= = , obtinut pentru min=si, implicit, min( ) log HS = , caz n care literele alIabetului codului sunt echiprobabile: 21)DeIiniti capacitatea canalului (deIinitie, Iormul, unitate de msur). OCapacitateacanaluluireprezintcantitateamaximdeinIormatiecepoatetreceprincanal,adicvaloareamaximainIormatieimutuale,nIunctiede distributia de probabilitti a alIabetului de intrare: ( )max ( , )PXC I XY = . ( , ) ( ) ( ) ( , ),|biti/simbol|,( ) ( , )( ) ( , )I XY HX HY HXYHX HX YHY HY X== = apacitatea unui canal depinde de propriettile Iizice ale acestuia, proprietti ce sunt determinate de matricea de zgomot( , ) Y X P . 22)Descrieti canalul binar simetric (graIul de tranzitii, matricea de zgomot, capacitatea canalului). OReprezentarea graIic a S si graIul de tranzitii: Matricea de zgomot P(Y[X) 1-pp P 1-p Oapacitatea canalului binar simetric este dat de relatia: 1 log (1 ) log(1 ) C p p p p = , |biti/simbol| expresie obtinut pentru simboluri echiprobabile() (1) .5 p p = = . 23)um variaz capacitatea analului inar Simetric (S) si analului inar cu Anulri (A)? Capacitatae variaza in functie de H(Y), pt ca H(y[x) este const din matricea de zgomot CBS1 log (1 ) log(1 ) C p p p p = , |biti/simbol| CBA max (x,y)max|H(y)H(y/x)|max |(1-q)H(x)| 1-q ????????????????? 24)e reprezint matricea de zgomot a canalului? La ce se Ioloseste? Matricea de tranzi(ie (matricea de zgomot) descrie propriettile canalului cu privire la inIormatia transmis: =1 1 2 1 , , 11 2 2 2 , , 21 , , 2 , , , , , ,( , ) (receptionat , transmis ), 1,, ,, 1,, ,( , ) ( , ) ( , )( , ) ( , ) ( , ).( , ) ( , ) ( , ) iY X P y x i Py x Py x Py xPy x Py x Py xPy x Py x Py x= = = = |P

. unde probabilitatea( , ) iPy xse numeste probabilitate de tranzi(ie a simbolului ix n simbolul

ysau, altIel spus, este probabilitatea cu care s-a receptionat

yconditionat de transmiterea simbolului ix. Propriet(i: - suma elementelor de pe o linie este 1: ( , ) 1,

i iyPy x x = V. - probabilitatea unui simbol de la iesirea canalului este: ( ) ( ) ( , )i iixPy Px Py x = . 1 1 p p 1-p 1-p probabilitatea de eroare (, 1) ( 1, )i i i ip py x py x = = = = = =xiyi ei ,1} = ,1} = ,1} = 25)e proprietti are matricea probabilittilor reunite a dou variabile aleatoare? P(X,Y)Pdiag(X) P(Y,X); Pdiag(X) este matricea ce are pe diagonala elementele din P(X). Si P(Y,X) matricea de tranzitii (de zgomot) 26)e devine canalul binar cu erori si anulri pentru p? Dar pentru q? EAP(Y,X)| 1-p-q pq| |P 1-p-qq| p ~ P(Y,X)|1-qq | A (cu anulari) |1-qq| q ~ P(Y,X) |1-pp| S (simetric) |p1-p| 27)Pentru un canal binar simetric, cum se pot interpreta situatiile cnd(.5,1) p? Se mai transmite inIormatie? Suma probabilitatilor trebuie sa Iie maxim 1, dar nu e posibila situatia(.5,1) p pentru un canal binar simetric, deci nu se poate transmite inIormatie 2)are sunt parametrii unui canal discret? (parametri, Iormule) OEntropia cmpului de intrare, se deIineste ca entropia v.a.X, de la intrarea n canal: 2( ) ( ) log ( )ii ixHX Px Px = bi[i/simbol). OEntropia cmpului de ieyire, se deIineste ca entropia v.a.Y, de la iesirea din canal: 2( ) ( ) log ( )

yHY Py Py = bi[i/simbol). OEntropia cmpului reunite intrare/ieyire, este o msur a incertitudinii globale deIint pe ambele spatii de intrare/iesire: 2( , ) ( , ) log ( , )i ii x yHXY Px y Px y = bi[i/simbol) unde probabilit[ile reunite( , )i Px yse pot calcula cu Iormula lui ayes. Acestea Iormeaz matricea probabilittilor reunite intrare/iesire( , ) XY P , ce are propriettile: ( , ) ( ),ii xPx y Py y = V,( , ) ( ),

ii iyPx y Px x = V, ( , ) 1i i x yPx y =. OEchivoca(ia reprezint incertitudinea medie asupra spa[iului de la intrarea n canal dac spa[iul de la ieire este cunoscut i se deIineste ca entropi a v.a. de intrareX condi[ionat de v.a. de ieireY : 2( , ) ( , ) log ( , )i ii x yHX Y Px y Px y = bi[i/simbol). OEroareamediereprezintincertitudineamedieasupraspa[iului delaieireadincanaldacspa[iul delaintrareeste cunoscutisedeIinesteca entropia v.a. de ieireYcondi[ionat de v.a. de intrareX: 2( , ) ( , ) log ( , )i i ix yHY X Px y Py x = bi[i/simbol). OInforma(iamutual sedefinete cafiind valoarea medieainforma[iei ce seob[ine desprespa[iuldeintrare cnd se cunoatespa[iuldeieire sau a informa[iei transmise prin canal: ( , ) ( ) ( ) ( , ),|biti/simbol|,( ) ( , )( ) ( , )I XY HX HY HXYHX HX YHY HY X== = Pe baza entropiilor deIinite mai sus, putem deIini parametrii caracteristici ai canalelor: OCapacitateacanaluluireprezintcantitateamaximdeinIormatiecepoatetreceprincanal,adicvaloareamaximainIormatieimutuale,nIunctiede distributia de probabilitti a alIabetului de intrare: ( )max ( , )PXC I XY = . apacitatea unui canal depinde de propriettile Iizice ale acestuia, proprietti ce sunt determinate de matricea de zgomot( , ) Y X P . ODebitul informa(ional este cantitatea maxim de inIormatie pe care o poate transmite un canal, raportat la unitatea medie de timp: tCC=:, |bps|. ODebitul de informa(ie (data rate) este cantitatea de inIormatie transmis prin canal raportat la unitatea medie de timp: ( , )tI XYI =:, |bps|. ORedundan(a canalului reprezint rezerva inIormational de care dispune un canal ce transmite cantitatea de inIormatie( , ) I XY : ( , ) R C I XY =, |biti/simbol|. ORedundan(a relativ a canalului este: ( , )1R I XYC C8 = =. OEficien(a canalului arat gradul de ncrcare a canalului din punct de vedere inIormational si este deIinit ca raportul dintre inIormatia mutual si capacitatea canalului: ( , ) I XYC = . 29)Reprezentati prin diagrame Venn Iluxul inIormatiilor printr-un canal discret Ir memorie, explicitnd notatiile. ;l 3)are este scopul codrii canalului?Coduri pentru canale cu perturba[ii Scop: Protectia la perturbatii prin asigurarea la receptie a detectiei si respectiv corectiei erorilor ce pot aparea in procesul de transmisiune 31)Explicati diIerentele dintre un cod bloc sistematic si unul nesistematic. n codul bloc sistematic simbolurie de control sunt separate de cele de inIormatie esistematic- simb de control si cele de inIormatie sunt amestecate sistematice pentru care cuvntul de intrare este parte component a cuvntului de cod, Iie la nceputul, Iie la sIrsitul acestuia. n acest mod nu mai este necesar un circuit de decodare dup cel de corectie a erorilor. 32)e reprezint un cuvnt de cod cu sens? Dar un cuvnt Ir sens? Din multimeade 2n cuvinte de cod de lungime n, 2k cuvinte sunt cuvinte cu sens, iar resul sunt cuvinte de receptie eronata 33)e reprezint matricea de control H si matricea generatoare G pentru un cod bloc? Multimea tuturor vectorilor ortogonali pe vectorii din spatiul V Iormeaza un spatiu ai carui vectori de baza, n numar de m, determina liniile matricei de control H: Vectorii de baza, de dimensiune 3, ai spatiului V, n numar de , determina liniile matricii generatoare G: Prin trans elementare matr H poate Ii adusa la una din Iormele canonice H`|Qm| siH``|mQ| Si G la Iel ~ G`|Pk| si G``|kP|; Formele canonice sunt caracteristicedodurilor sistematice HGT0 PQT Matricea H are m( nr de simb de control)linii si n (lunigimea cuv de cod)coloane Matricea G are k (nr de simb de inIormatie) linii si n coloane 34)e reprezint sindromul pentru un cod bloc? um se calculeaz? Sindromvector coloana corrector Pentru a putea Iolosi corectorii n procesul de corectie trebuie s existe o corespondent biunivoc ntre corector si eroare: e (Iiecrui corector s i corespund o eroare). H(X) H(Y) H(X,Y) I(X,Y)H(Y,X) H(X,Y) a)b) ( , ) HX Y( ) HX( , ) HY X( ) HY( , ) I XY s=HrT=H(ve)T =HvT HeT =HeT 35)nd sindromul pentru un cod bloc este 0? Sindromulestecand nu exista erori la transmitera inI prin canal 36)um se scrie matricea de control H pentru un cod Hamming grup, corector de 1 eroare? oloanele matricii H reprezinta scrierea in binar a numarului coloanei respective. Ex, pt un cod cu m3 si n7, adica o matrice H cu 5 linii si 7 coloane oloana 1 scrierea in binar a lui 1 1 ol 2... 21 ol 33 1 1 Etc

|1111| H| 1 111| |1111| 37)are este structura unui cuvnt de cod pentru codul grup Hamming H(7,4)? n7, k4 ~ m 7-43 ;se construieste matricea H ca mai sus si se stabileste conventia ca acele coloane in care exista un singur '1 reprezintasymbol de control in vectorul cuvantului de cod, iar coloanele cu mai multi de '1 reprezinta simb de inIormatie in vectorul v cuv de cod este sucris sub Iorma vectoriala astIel : v|c1 c2 i3 c4 i5 i6 c7 | 3)e metode de codare exist pentru calculul unui cuvnt de cod al codului grup? Procesul de codare nseamna determinarea simbolurilor de control din simbolurile de informatie. metoda e sistematica si una nesistemaita. dar carecum??????????? u ajutorul matricii H sau G rice cuvnt de cod, Iiind o combinatie liniara a liniilor matricii G, satisIace relatia: HvT =0, unde am Iolosit aritmetica modulo 2. Folosind matricea G, orice cuvnt de cod se poate determina din: v=iG, unde )1 2i =i ii este cuvntul de inIormatie (un vector linie Iormat numai din simboluri de inIormatie). AstIel, orice cuvnt de cod al unui cod liniar se poate determina ca o combinatie liniara 39)Explicati Ienomenul care apare n procesul de decodare, dac cuvntul receptionat contine dou erori (codul utilizat este Hamming grup H(7,4)). 4)um se numeste simbolul de control introdus de codul Hamming grup extins? La ce Ioloseste? Cod extins Daca pe lnga corectia unei erori simple, trebuie sa Iacem si detectia de erori duble, matricea de control va Ii de Iorma: unde H este matricea de control a codului Hamming corector de o eroare. AstIel, la cele m simboluri de control ale codului Hamming se mai adauga un simbol de control c, denumit simbol de veriIicare a paritatii. AstIel, numarul total de simboluri de control este : iar dimensiunea cuvntului de cod: La decodare, se va calcula sindromul: Dacas0 = si s=0, atunci cuvntul receptionat este corect (nu au aparut erori n procesul de transmisie). Daca s = si s=0, atunci cuvntul receptionat are doua erori care sunt doar detectabile, decodorul putnd cere retransmisia cuvntului de cod (ARQ). Dacas =1, atunci cuvntul receptionat are un singur simbol eronat ce poate Ii corectat, sindromul s Iiind reprezentarea n binar a pozitiei unde a aparut eroarea (FE). 41)are sunt propriettile de corectie si de detectie ale codului Hamming grup H(7,4)? Pentru ca un cod sa poata avea proprietati de corectie, este necesar ca din multimea tuturor cuvintelor de lungime 3, numai o parte sa constituie cuvinte de cod cu sens. Rezulta astIel n spatiul cuvintelor o distanta ntre cuvintele de cod )i i1 i2 i3 v =a a a si1 2 3 v =a a a|care a Iost deIinita de Hamming astIel: unde reprezinta adunarea n corpul numerelor reale, iar Wadunarea modulo doi. u alte cuvinte, distanta dintre doua cuvinte de cod reprezinta numarul de pozitii prin care cele doua cuvinte diIera. Se observa ca distanta dintre cuvintele de cod i v siv reprezinta ponderea unui cuvnt de codiv =v Wv : ( , ) ( ) H i d vv =wv . onditia necesara si suIicienta pentru ca un cod sa poata corecta 9erori, este ca distanta minima dintre cuvintele de cod sa Iie: min min d =w =2t1. onditia necesara si suIicienta pentru ca un cod sa poata detecta 9erori, este ca distanta minima dintre cuvintele de cod sa Iie: min min d =w =t1. Se observa ca un cod corector de t erori este detector de 2t erori. Pentru a putea Iace corectia a 9erori, oricare 2t1 coloane ale matricii H trebuie sa Iie i3iar i3depe3de3te (suma oricaror t coloane ale matricii H trebuie sa diIere de suma oricaror altor t coloane ale matricii H). Pentru a putea Iace detectia a t erori, trebuie ca t1 coloane ale matricii H sa Iie i3iar i3depe3de3te. 42)um se pot implementa hardware codurile grup? Un cod binar C (3,) este determinat complet de un set de 2 cuvinte de cod, Iiecare de lungime 3 biti si o Iunctie de transIormare de la cuvintele de inIormatie la cuvintele de cod. Codare Procesul de codare nseamna determinarea simbolurilor de control din simbolurile de informatie. rice cuvnt de cod, Iiind o combinatie liniara a liniilor matricii G, satisIace relatia: H`vx=0, unde am Iolosit aritmetica modulo 2. Folosind matricea G, orice cuvnt de cod se poate determina din: v=i-G, undeeste cuvntul de inIormatie (un vector linie Iormat numai din simboluri de inIormatie). AstIel, orice cuvnt de cod al unui cod liniar se poate determina ca o combinatie liniara a liniilor matricii G. Transmisie prin CBS uvntul eronat va Ii cuvintul transmis v adunat cu un cuvnt eroare e: r=ve. 43)are sunt metodele de codare pentru un cod ciclic? e diIerente exist ntre ele? 44)um se construiesc matricile H si G pentru un cod ciclic? 45)e caracteristici speciale are n plus matricea generatoare G a unui cod ciclic Iat de un cod grup? ???? 46)e diIerente sunt ntre codorul cu circuite de divizare si codorul cu registre de deplasare pentru un cod ciclic? Codarea/decodarea cu circuite de divizare x i x x c x vm =

x gx i xrest x cm Schema codorului: Exemplul 1.(15, 11, 3) 3 15m 4 11 12 = x x q 12 4 6 = x x x x ix x x c=3 14= x x x g x g x c x c x q x g x i mod == Tabelul strilor: c

c1cm-1P2P3xk1xm1xkxmP1g

g1 g2gm-1i(x)c c1c2c3g

g1g4

UTTATSimbol la intrareStarea celuleloresire c c1 2c3UT 1x6 11 2x5 1 3x4 111 4x3 11 5x2 1111 6x11 711111 x x3

16 4 4x x x x x i x= v |11 1111 | ircuitul de decodare Schema Codarea/decodarea cu circuite R R.D. este tot un circuit secvential liniar care poate Iunctiona Ir semnal aplicat din exterior, numai cu semnal de reactie. onexiunile registrului sunt realizate n conIormitate cu coeIicientii polinomului generator g(x). Fie stare initial a registrului: |

=|

====

1....

1 c......... c cU

2 m1 m Schema unui circuit RD: Matricea caracteristic a polinomului g(x) n cazul codrii cu registre de deplasare are urmtoarea Iorm: |

=1 m 2 1 g .. g g g1 .. .. .. .. .. .. .. 1 ..1 TDac starea initial a registrului a Iost S U atunci strile succesive vor Ii: TS, T2S, .. , Tn-1S, Tn umrul strilor Iiind Iinit, registrul ajunge ntotdeauna la starea initial dup un numr de tacte. Pentru ca Iiecare stare a registrului s Iie precedat de o stare unic trebuie s existe matricea T-1. Aceast conditie este ndeplinit dac g 1. umrul total de stri nenule pe care s le genereze un R.D. cu m celule este 3 2m

1. Aceste stri pot Ii generate ntr-un singur ciclu sau n mai multe. Registrul genereaz toate cele 2m1 stri posibile ntr-un singur ciclu dac conexiunile reactiei se Iac conIorm unui polinom primitiv g(x) de grad m. Pentru matricea T polinomul caracteristic este: ) =|

==1 m 3 2 1 g .. g g g g.. .. .. .. .. .. ..1 x x T det xm mmx x g x g g

11 1 ..c

c1 cm-21xmxmP1g

g1g2gm-1cm-1gm-2gm1xnxnz(x) JKP2V`(X) 1cm-2 cm-1c

c121A

g g1gm-1gm1|k|2|m|ntrareSumatoresire21gm 1 onIorm teoremei ayley-Hammilton matricea caracteristic T este o rdcin a polinomului caracteristic (x) g(x) deci:g(T) Se numeste perioada matricii caracteristice T (sau lungimea ciclului strilor distincte pe care le poate avea (R.D.) cel mai mic numr ntreg 3 pentru care:Tn T

Dac S U |. 1|T atunci cele 3 stri nenule sunt: T

U U,TU ,T2U , .. ,Tn-1U;TnU U ntre Ti si -i (i 1, 3) exist o corespondent biunivoc, Ir a se respecta ns indicii. 47)e contin celulele codorului cu circuite de divizare pentru un cod ciclic duptacte? 4)um se realizeaz starea nul pentru codoarele cu circuite de divizare si cu registre de deplasare ale unui cod ciclic? 49)De ce la decodorul cu registru de deplasare al unui cod ciclic se Iolosesc dou decodoare identice? 5)are sunt asemnrile si deosebirile dintre un cod bloc si un cod convolutional? odurile convolutionale diIer de codurile bloc att prin Iaptul c blocul de codare are memorie, ct si prin dependenta celor 3 simboluri de iesire, la Iiecare moment de timp, nu numai de celesimboluri de intrare, ci si de m blocuri desimboluri anterioare de intrare. Un cod convolutional |3, | poate Ii implementat cu un circuit secvential care are 3 iesiri liniare,intrri si m celule de memorie (sau de ntrziere) pentru Iiecare intrare. 51)e metode de codare exist pentru un cod convolutional? Codarea polinomiala se Iace pentru Iiecare iesire c(), =1,3, calculnd polinoamele intermediare ci(),i=1,, =1,3: 52)e reprezint diagrama de stri si diagrama trellis pentru un cod convolutional? iagrama treIIis a coduriIor convoIu|ionaIe Din arborele reprezentat n Iigura 3, unind nodurile S1 ntre ele, apoi nodurile S2, S3 si S4 se obtine diagrama trellis din Iigura 4. onventia utilizat n Iigura 4 pentru a distinge ntre simbolurile de intrare , si ,1 este: o ramur generat de un simbol de intrare , este desenat cu linie continu, iar ramura generat de simbolul de intrare ,1 este desenat cu linie punctat.igura 3. Diagrama arbore a codului convolutional |2,1|, m2. 11 S

1 1 S1 11 S2 1 1 S3 11 S

1 1 S1 11 S

1 1 S1 11 S2 1 1 S3 11 S2 1 1 S3 11 1 1 S1 11 S

Simbol intrare ' Simbol intrare '1 11 S

1 1 S1 11 S2 1 1 S3 11 S

1 1 S1 11 S

1 1 S1 11 S2 1 1 S3 11 S2 1 1 S3 11 1 1 S1 S

Trellis-ul este Iormat din () nivele, undeeste lungimea secventei de inIormatie, iar m1 este lungimea de constrngere. ivelele n trellis sunt notate cu , 1, 2,..., -1. Primele (-1) nivele sunt corespunztoare plecrii codorului din starea initial a, iar ultimele (-1) nivele corespund ntoarcerii circuitului codor n starea S1. S considerm acum o portiune din trellis corespunztoare momentelor de timp de lala 1. Presupunem ~2 pentru exemplul nostru, deci starea curent a codorului poate Ii una din cele patru posibile S1, S2, S3 sau S4. Aceast portiune din trellis este prezentat n Iigura 5. odurile din stnga reprezint starea posibil la momentul de timp curent, iar nodurile din dreapta starea viitoare. Datorit caracterului periodic al acestei structuri, putem uni nodurile din stnga cu cele din dreapta. btinem astIel, /,7,2,/089,70 a codorului, artat n Iigura 6. Aceast diagram este de Iapt un graI orientat, nodurile graIului reprezentnd strile codorului, iar arcele graIului tranzitiile posibile Iunctie de simbolurile de la intrarea codorului. Dac la intrare avem ,, tranzitia este desenat cu linie continu, iar dac avem ,1 cu linie punctat. Eticheta Iiecrui arc reprezint simbolurile de la iesirea codorului. 53)Un cod convolutional poate Ii sistematic? n ce conditii? Acest codor nu este sistematic , deoarece nu exista nici o iesire la care sa se regaseasca identic simbolurile de la intrare , sau, cu alte cuvinte, nu exista nici o cale de la intrare la iesire care sa nu aiba sumatoare sau registre de memorie. Un cod este sistematic daca exista cel putin un polinom generator de forma ()=1. igura 5. Diagrama Iluture pentru codul |2,1|, cu m2 si 1 2 2 2( ) 1 , ( ) 1 g g== .. simbol de intrare ' simbol de intrare '1 11 11 1 1 1 1 S

S11 S21 S311 S

S11 S21 S311 igura 4. Diagrama trellis pentru codul |2,1|, cu m3 si 1 2 2 2( ) 1 , ( ) 1 g g== .. simbol de intrare 'simbol de intrare '1 11 S

S11 S21 S311 11 1 1 11 11 1 1 11 1 1 1 11 1 11 1 1 1 11 1 11 1 1 1 11 1 11 1 1 1 11 1 1234

-1

1