1 1)Ce este entropia? (definiie, formul, unitate de msur) DEF: valoarea medie a informaiei proprii:? A( )( ) ( )iip xH X E i x = , respectiv:( ) ( ) ( ) ( ) log ( )i ii i i ix xH X i x p x p x p x == X X, [bii]. 2)Ce este debitul de informaie? (definiie, formul, unitate de msur) sec /1biti X H X HtX =,Debitul de informaie (data rate) este cantitatea de informaie transmis prin canal raportat la unitatea medie de timp 3)Care sunt proprietile entropiei? Proprietile entropiei: 1.entropia este o funcie continu de probabilitile simbolurilor sursei 2.entropia este simetric (are aceleai valori indiferent cum sunt ordonate probabilitile simbolurilor sursei) 3.entropia este aditiv 4.valoarea entropiei este ntotdeauna pozitiv0 u X H0 , 1 0 = = VV = n =j k kx p k j x x p k X H G5. G log e X H G log = X H dac i numai dac X are distribuie p(X) uniform pe alfabetul G (simbolurile sunt egal probabile) Pentru simboluri egal probabile:Gmare X H mare. 6.entropia este o funcie concav n raport cu probabilitatea p 4)Precizai diferenele dintre Sursa Discret Fr Memorie (SDFM) i Sursa Discret Cu Memorie (SDCM). Pentru o SDCM, 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 nx X , la momentul de timp nt n = , este independent de simbolurile emise la momentele de timp anterioare 11nt n

=. 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) SDCM 5)Ce este redundana sursei? (definiie, formul, unitate de msur) DEF:RS=Hmax(S)-H(S) [biti/symbol] 6)Definii sursa extins de ordin n Sursa extinsa Xn se poate def pornind de la sursa initiala X astfel:X:G-> {x1,x2.xM} => Xn:Gn {W1,W2.WM}simbolurile sursei extinse Wj sunt mesaje formate din n simboluri ale sursei primare. Daca e SEFM p(Wj)=Hp(xi) dc e SECM p(Wj)=p(x1)Hp(xi|xi-1) 7)Care sunt proprietile entropiei reunite a doua variabile aleatoare? H(X,Y)= - 77p(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 , ecu egalitate dac: X f Y Y X H X H = = ,3.Subaditivitatea Pentru o pereche de v.a., ( , ) X Y p x y- X Y, entropia reunit este mai mic sau cel mult egal cu suma entropiilor celor dou variabile: ( , ) ( ) ( ) H X Y H X H Y e, cu egalitate dac i numai dac X, Y sunt v.a. independente. 2 8)Care sunt proprietile informaiei mutuale? Proprietile informaiei: 1.Evenimentul sigur nu produce informaie:1 0i ip x i x == ; 2.Informaia proprie are valoare pozitiv:0 1 0i ip x i x e eu ; Observaie: folosim convenia0 log0 0=deoarece 0lim log 0xx xp = . 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:( ) ( ) ( ) ( )i j i jp x p x i x i x " . 4.Informaia este aditiv. Fie dou evenimente independente, 1xi 2x , ce au loc cu probabilitile individuale1( ) 0 p x "i 2( ) 0 p x " . Informaia obinut prin realizarea celor dou evenimente egaleaz suma informaiilor obinute prin realizarea fiecrui eveniment n parte: 1 2 1 2( ) ( ) ( ) i x x i x i x =. 9)Cand o sursa discreta fara memorie are entropie maxima? Dar debit maxim? H(S Hmax(S)=log2M 10) Precizati diferentele din punct de vedere informational dintre o sursa fara memorie, de ordin 1 si sursa extinsa de ordin n.H(Sn)=nH(S) ;Hmax (Sn)=nHmax (S) RSn=n RS Pentru sursa extinsa, entropia H si redundanta R=Hmax-H au crescut, iar randamentul L=H/Hmax si redundantaV=1-Lrelativa nu s-au modificat. Acest lucru este normal, daca ne gndim ca, n cazul sursei extinse, un simbol este de fapt o succesiune de simboluri ale sursei primare si, atunci, entropia, care este informatia 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) Care este scopul codrii sursei? a)Codarea sursa:Reprezentarea eficienta intr-o forma 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) Definii codurile absolut optimale. Un cod absolut optimal este un cod optimal de eficien unitar min1llL = = , obinut pentru minl l =i, implicit, min( ) log H S l D = , caz n care literele alfabetului codului sunt echiprobabile: 1 21( ) ( ) ... ( )Dp x p x p xD= = = = . 3 13) Definii codurile unic decodabile. Cod unic decodabil:un cod pentru care fiecrei succesiuni de cuvinte de cod i corespunde o singur succesiune de simboluri din alfabetul sursei. Un cod unic decodabil, avnd cardinalitatea alfabetului| | D =X , cu care se formeaz| | M=Scuvinte de cod de lungime li,1, i M = , satisface inegalitatea Kraft:7D-lie1Un cod pt a fi unic decodabil trebuie sa indeplineasca urmatoarea conditie: nici un cuv de cod nu poate fi prefix si suffix pt alt cuvant.14) Definii codurile optimale. Un cod optimal va trebui s satisfac cerinele: 1.Oricaredoucuvintedecodtrebuiesfiedistincte,adicsaibcombinaiidistinctedeliteredinalfabetul codului; 2.Nici un cuvnt de cod nu trebuie s fie prefixul altui cuvnt de cod; 3.Cuvintele de cod mai probabile trebuie s fie reprezentate printr-un numr mai mic de simboluri din alfabetul codului: dac( ) ( )i jp s p s u , atunci, , 1,i jl l i j M e V = ; 4.Cele mai puin probabile cuvinte de cod, n numr de D, trebuie s fie de lungimi egale i s difere numai prin ultimul simbol. 15) Se poate stabili dac un cod este instantaneu cu ajutorul inegalitii Kraft? Exemplificai. Teorema Mc. Millan: Satisfacerea inegalitii lui Kraft este o condiie necesar i suficient pentru construcia unui cod instantaneu, pentru care cuvintele de cod au lungimile li. 16) Care sunt deosebirile ntre algoritmii de codare compact Shannon-Fano i Huffman? Codarea Shannon - Fano Dac probabilitatile simbolurilor emise de sursa sunt de forma( )ilip s D

= , atunci: 1.se ordoneaz mulimea de simboluri emise de surs n ordine descresctoare a probabilitilor de apariie a simbolurilor; 2.se aplic pe mulimea 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/8,1/8} , atunci codarea Shannon- Fano asigura existenta unui cod absolut optimal. Codarea 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 alfabetului codului, 0 si 1. Partitia se termina cnd fiecare 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 cu 0 si 1. 1.Prin modul n care e fcut codul Huffman, nu exist o soluie unic. 17) Care sunt proprietile codurilor obinute prin algoritmul Huffman? Prin codare Huffman se obtine un cod optimal, unic decodabil(nici un cuvant de cod nu este prefixul sau sufixul altui cuvant), deci si instantaneu (faraprefix).18) Care tip de codare (simbol cu simbol, grupe de cte 2 simboluri sau grupe de cte 3 simboluri) este mai eficient i de ce? In cazul codarii surselor cu memorie, codarea pe grupe de dou simboluri este mai eficient dect codarea simbol cu simbol: Memoria sursei reduce eficiena codului: eficienta codului L=H(X)/log2|X|binar=> |X|=2 => L=H(X) Cred ca cea mai eficienta este codarea pe grupe de cate 2 simboluri 19) Care din codurile urmtoare sunt instantanee i de ce: a) {00, 01, 10, 110, 1110, 1111}; b) {0, 10, 110, 11, 010}; c) {1, 01, 001, 000}; d) {00, 01, 100, 1010}? Instanteneu: a) b) c) d) pt k au proprietatae de prefix, adica nici un cuvant de cod nu este prefixul altui cuvant4 20) Codarea Huffman binar sau ternar poate duce la obinerea unui cod absolut optimal (L=1)? Cnd? Un cod absolut optimal este un cod optimal de eficien unitar min1llL = = , obinut pentru minl l =i, implicit, min( ) log H S l D = , caz n care literele alfabetului codului sunt echiprobabile: 21) Definii capacitatea canalului (definiie, formul, unitate de msur). yCapacitateacanaluluireprezintcantitateamaximdeinformaiecepoatetreceprincanal,adicvaloarea maxim a informaiei mutuale, n funcie de distribuia de probabiliti a alfabetului de intrare: ( )max ( , )P XC I X Y = . ( , ) ( ) ( ) ( , ),[biti/simbol],( ) ( | )( ) ( | )I X Y H X H Y H X YH X H X YH Y H Y X== = Capacitatea unui canal depinde de proprietile fizice ale acestuia, proprieti ce sunt determinate de matricea de zgomot( | ) Y X P . 22) Descriei canalul binar simetric (graful de tranziii, matricea de zgomot, capacitatea canalului). yReprezentarea grafic a CBS i graful de tranziii: Matricea de zgomot P(Y|X)= 1-pp P 1-p yCapacitatea canalului binar simetric este dat de relaia: 1 log (1 ) log(1 ) C p p p p = , [bii/simbol] expresie obinut pentru simboluri echiprobabile(0) (1) 0.5 p p = = . 23) Cum variaz capacitatea Canalului Binar Simetric (CBS) i Canalului Binar cu Anulri (CBA)? 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 = , [bii/simbol] CBA C = max I(x,y)=max[H(y) H(y/x)]=max [(1-q)H(x)] = 1-q ????????????????? 24) Ce reprezint matricea de zgomot a canalului? La ce se folosete? Matricea de tranziie (matricea de zgomot) descrie proprietile canalului cu privire la informaia transmis: _ a1 1 2 1 | | 11 2 2 2 | | 21 | | 2 | | | | | |( | ) (receptionat | transmis ), 1,| |, 1,| |( | ) ( | ) ( | )( | ) ( | ) ( | ).( | ) ( | ) ( | )j iY X P y x i jP y x P y x P y xP y x P y x P y xP y x P y x P y x= = = = |P

YYX X Y XX Y. unde probabilitatea( | )j iP y xse numete probabilitate de tranziie a simbolului ixn simbolul jysau, altfel spus, este probabilitatea cu care s-a recepionat jycondiionat de transmiterea simbolului ix . Proprieti: -suma elementelor de pe o linie este 1: 0 1 0 1 p p 1-p 1-p probabilitatea de eroare ( 0 | 1) ( 1| 0)i i i ip p y x p y x = = = = = =xiyi ei {0,1} = X{0,1} = E{0,1} = Y5 ( | ) 1,jj i iyP y x x = V. -probabilitatea unui simbol de la ieirea canalului este: ( ) ( ) ( | )ij i j ixP y P x P y x = . 25) Ce proprieti are matricea probabilitilor 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) Ce devine canalul binar cu erori i anulri pentru p=0? Dar pentru q=0? CBEAP(Y|X)=[ 1-p-q pq] [P 1-p-qq] p=0 => P(Y|X)=[1-q 0 q ] CBA (cu anulari) [ 0 1-qq] q=0 => P(Y|X) = [1-pp] CBS (simetric) [p1-p] 27) Pentru un canal binar simetric, cum se pot interpreta situaiile cnd(0.5,1) p? Se mai transmite informaie? Suma probabilitatilor trebuie sa fie maxim 1, dar nu e posibila situatia(0.5,1) p pentru un canal binar simetric, deci nu se poate transmite informatie 28) Care sunt parametrii unui canal discret? (parametri, formule)yEntropia cmpului de intrare, se definete ca entropia v.a.X , de la intrarea n canal: 2( ) ( ) log ( )ii ixH X P x P x = , ?bii/simbolA. yEntropia cmpului de ieire, se definete ca entropia v.a.Y , de la ieirea din canal: 2( ) ( ) log ( )jj jyH Y P y P y = , ?bii/simbolA. yEntropiacmpuluireuniteintrare/ieire,esteomsur a incertitudiniiglobaledefintpe ambele spaiide intrare/ieire: 2( , ) ( , ) log ( , )i ji j i jx yH X Y P x y P x y = , ?bii/simbolA, unde probabilitile reunite( , )i jP x yse pot calcula cu formula lui Bayes. Acestea formeaz matricea probabilitilor reunite intrare/ieire( , ) X Y P , ce are proprietile: ( , ) ( ),ii j j jxP x y P y y = V,( , ) ( ),ji j i iyP x y P x x = V, ( , ) 1i ji jx yP x y =. yEchivocaiareprezintincertitudineamedieasupraspaiuluidelaintrareancanal,dacspaiuldelaieire este cunoscut i se definete ca entropia v.a. de intrareXcondiionat de v.a. de ieireY : 2( | ) ( , ) log ( | )i ji j i jx yH X Y P x y P x y = , ?bii/simbolA. yEroareamediereprezintincertitudineamedieasupraspaiuluidelaieireadincanal,dacspaiuldela intrare este cunoscut i se definete ca entropia v.a. de ieireYcondiionat de v.a. de intrareX : 2( | ) ( , ) log ( | )i ji j j ix yH Y X P x y P y x = , ?bii/simbolA. yInformaiamutual sedefineteca fiindvaloareamedie ainformaieice seobinedesprespaiuldeintrare cnd se cunoate spaiul de ieire, sau a informaiei transmise prin canal: ( , ) ( ) ( ) ( , ),[biti/simbol],( ) ( | )( ) ( | )I X Y H X H Y H X YH X H X YH Y H Y X== = Pe baza entropiilor definite mai sus, putem defini parametrii caracteristici ai canalelor: 6 yCapacitateacanaluluireprezintcantitateamaximdeinformaiecepoatetreceprincanal,adicvaloarea maxim a informaiei mutuale, n funcie de distribuia de probabiliti a alfabetului de intrare: ( )max ( , )P XC I X Y = . Capacitatea unui canal depinde de proprietile fizice ale acestuia, proprieti ce sunt determinate de matricea de zgomot( | ) Y X P . yDebitulinformaionalestecantitateamaximde informaiepecareopoate transmiteuncanal, raportatla unitatea medie de timp: tCC=X, [bps]. yDebitul de informaie (data rate) este cantitatea de informaie transmis prin canal raportat la unitatea medie de timp: ( , )tI X YI =X, [bps]. yRedundanacanalului reprezint rezervainformaionaldecaredispune uncanalcetransmitecantitateade informaie( , ) I X Y : ( , ) R C I X Y =, [bii/simbol]. yRedundana relativ a canalului este: ( , )1R I X YC CV = =. yEficiena canalului arat gradul de ncrcare a canalului din punct de vedere informaional i este definit ca raportul dintre informaia mutual i capacitatea canalului: ( , ) I X YCL = . 29) Reprezentai prin diagrame Venn fluxul informaiilor printr-un canal discret fr memorie, explicitnd notaiile. ;l 30) Care este scopul codrii canalului?Coduri pentru canale cu perturbaii Scop: Protecia la perturbaii prin asigurarea la recepie a deteciei si respectiv coreciei erorilor ce pot aparea in procesul de transmisiune 31) Explicai diferenele dintre un cod bloc sistematic i unul nesistematic. H(X) H(Y) H(X|Y) I(X,Y)H(Y|X) H(X,Y) a)b) ( | ) H X Y( ) H X( | ) H Y X( ) H Y( , ) I X Y7 In codul bloc sistematic simbolurie de control sunt separate de cele de informatie Nesistematic- simb de control si cele de informatie sunt amestecate sistematice pentru care cuvntul de intrare este parte component a cuvntului de cod, fie la nceputul, fie la sfritul acestuia. n acest mod nu mai este necesar un circuit de decodare dup cel de corecie a erorilor. 32) Ce reprezint un cuvnt de cod cu sens? Dar un cuvnt fr sens? Din multimeade 2n cuvinte de cod de lungime n, 2k cuvinte sunt cuvinte cu sens, iar resul sunt cuvinte de receptie eronata 33) Ce reprezint matricea de control H i matricea generatoare G pentru un cod bloc? Multimea tuturor vectorilor ortogonali pe vectorii din spatiul V formeaza un spatiu ai carui vectori de baza, n numar de m, determina liniile matricei de control H: Vectorii de baza, de dimensiune n, ai spatiului V, n numar de k, determina liniile matricii generatoare G: Prin trans elementare matr H poate fi adusa la una din formele canonice H=[QIm] siH=[ImQ] Si G la fel => G=[PIk] si G=[IkP]; Formele canonice sunt caracteristicedodurilor sistematice HGT=0 P=QT 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 informatie) linii si n coloane 34) Ce reprezint sindromul pentru un cod bloc? Cum se calculeaz? Sindrom=vector coloana corrector Pentru a putea folosi corectorii n procesul de corecie trebuie s existe o coresponden biunivoc ntre corector i eroarez em (fiecrui corector s i corespund o eroare). s=HrT=H(ve)T =HvT HeT =HeT 35) Cnd sindromul pentru un cod bloc este 0? Sindromuleste 0 cand nu exista erori la transmitera inf prin canal36) Cum se scrie matricea de control H pentru un cod Hamming grup, corector de 1 eroare? Coloanele matricii H reprezinta scrierea in binar a numarului coloanei respective.Ex, pt un cod cu m=3 si n=7, adica o matrice H cu 5 linii si 7 coloane Coloana 1 = scrierea in binar a lui 1= 0 0 0 0 1 Col 2.. 2= 0 0 0 1 0Col 33=0 0 0 1 1 Etc [0 0 01111] H=[0 1 10011] [1 0 10101] 37) Care este structura unui cuvnt de cod pentru codul grup Hamming H(7,4)?n=7, k=4 => m= 7-4=3 ;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 informatie in vectorul v cuv de cod este sucris sub forma vectoriala astfel : v=[c1 c2 i3 c4 i5 i6 c7 ] 38) Ce 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. O metoda e sistematica si una nesistemaita dar carecum??????????? Cu ajutorul matricii H sau G Orice cuvnt de cod, fiind o combinatie liniara a liniilor matricii G, satisface relatia: HvT =0, unde am folosit aritmetica modulo 2. Folosind matricea G, orice cuvnt de cod se poate determina din: v=iG, unde ?A1 2 k i =i i L i este cuvntul de informatie (un vector linie format numai din simboluri de informatie). Astfel, orice cuvnt de cod al unui cod liniar se poate determina ca o combinatie liniara 8 39) Explicai fenomenul care apare n procesul de decodare, dac cuvntul recepionat conine dou erori (codul utilizat este Hamming grup H(7,4)). 40) Cum se numete simbolul de control introdus de codul Hamming grup extins? La ce folosete? Cod extins Daca pe lnga corectia unei erori simple, trebuie sa facem si detectia de erori duble, matricea de control va fi de forma: unde H este matricea de control a codului Hamming corector de o eroare. Astfel, la cele m simboluri de control ale codului Hamming se mai adauga un simbol de control c0, denumit simbol de verificare a paritatii. Astfel, numarul total de simboluri de control este : iar dimensiunea cuvntului de cod: La decodare, se va calcula sindromul: Dacas0 =0 si s=0, atunci cuvntul receptionat este corect (nu au aparut erori n procesul de transmisie). Daca s0 =0 si s=0, atunci cuvntul receptionat are doua erori care sunt doar detectabile, decodorul putnd cere retransmisia cuvntului de cod (ARQ). Daca 0 s =1, atunci cuvntul receptionat are un singur simbol eronat ce poate fi corectat, sindromul s fiind reprezentarea n binar a pozitiei unde a aparut eroarea (FEC). 41) Care sunt proprietile de corecie i de detecie 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 n, numai o parte sa constituie cuvinte de cod cu sens. Rezulta astfel n spatiul cuvintelor o distanta ntre cuvintele de cod ?Ai i1 i2 in v =a a La si j j1 j2 jn v =a a La|care a fost definita de Hamming astfel: unde reprezinta adunarea n corpul numerelor reale, iar adunarea modulo doi. Cu alte cuvinte, distanta dintre doua cuvinte de cod reprezinta numarul de pozitii prin care cele doua cuvinte difera. Se observa ca distanta dintre cuvintele de cod i v si j v reprezinta ponderea unui cuvnt de cod k i j v =v v : ( , ) ( ) H i j k d vv =wv . Conditia necesara si suficienta pentru ca un cod sa poata corecta t erori, este ca distanta minima dintre cuvintele de cod sa fie: min min d =w =2t1. Conditia necesara si suficienta pentru ca un cod sa poata detecta t erori, este ca distanta minima dintre cuvintele de cod sa fie: min min d =w =t1. Se observa ca un cod corector de t erori este detector de 2t erori. Pentru a putea face corectia a t erori, oricare 2t+1 coloane ale matricii H trebuie sa fie liniar independente (suma oricaror t coloane ale matricii H trebuie sa difere de suma oricaror altor t 9 coloane ale matricii H). Pentru a putea face detectia a t erori, trebuie ca t+1 coloane ale matricii H sa fie liniar independente. 42) Cum se pot implementa hardware codurile grup? Un cod binar C (n,k) este determinat complet de un set de 2k cuvinte de cod, fiecare de lungime n biti si o functie de transformare de la cuvintele de informatie la cuvintele de cod. Codare Procesul de codare nseamna determinarea simbolurilor de control din simbolurile de informatie. Orice cuvnt de cod, fiind o combinatie liniara a liniilor matricii G, satisface relatia: H*v=0, unde am folosit aritmetica modulo 2. Folosind matricea G, orice cuvnt de cod se poate determina din: v=i-G, undeeste cuvntul de informatie (un vector linie format numai din simboluri de informatie). Astfel, orice cuvnt de cod al unui cod liniar se poate determina ca o combinatie liniara a liniilor matricii G. Transmisie prin CBS Cuvntul eronat va fi cuvintul transmis v adunat cu un cuvnt eroare e: r=ve. 43) Care sunt metodele de codare pentru un cod ciclic? Ce diferene exist ntre ele? 44) Cum se construiesc matricile H i G pentru un cod ciclic? 10 45) Ce caracteristici speciale are n plus matricea generatoare G a unui cod ciclic fa de un cod grup? ???? 46) Ce diferene sunt ntre codorul cu circuite de divizare i 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.C(15, 11, 3) n = 15m = 4k = 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: TACT Simbol la intrare Starea celulelorIeire INc0 c1 C2 c3 OUT 1x6 110000 2x5 001000 3x4 110100 4x3 001010 5x2 101101 6x000110 71101011 x +x3 c0c1cm-1P2P30xk1xm1xk0xmP1g0g1 g2gm-1i(x)c0 c1c2c3g0g1g4INOUT11

10 8 6 4 4x x x x x i x= v = [ 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 ] Circuitul de decodare Schema 8.7.8. Codarea/decodarea cu circuite R.D. R.D. este tot un circuit secvenial liniar care poate funciona fr semnal aplicat din exterior, numai cu semnal de reacie. Conexiunile registrului sunt realizate n conformitate cu coeficienii polinomului generator g(x). Fie stare iniial a registrului: |

=|

====

1....001 c.........0 c0 cU02 m1 m Schema unui circuit RD: Matricea caracteristic a polinomului g(x) n cazul codrii cu registre de deplasare are urmtoarea form: |

=1 m 2 1 0g .. g g g1 .. 0 0 0.. .. .. .. ..0 .. 1 0 00 .. 0 1 0TDac starea iniial a registrului a fost S = U atunci strile succesive vor fi: TS, T2S, .. , Tn-1S, Tn = I Numrul strilor fiind finit, registrul ajunge ntotdeauna la starea iniial dup un numr de tacte. Pentru ca fiecare stare a registrului s fie precedat de o stare unic trebuie s existe matricea T-1. Aceast condiie este ndeplinit dac g0 = 1. Numrul total de stri nenule pe care s le genereze un R.D. cu m celule este n = 2m 1. Aceste stri pot fi generate ntr-un singur ciclu sau n mai multe. Registrul genereaz toate cele 2m 1 stri posibile ntr-un singur ciclu dac conexiunile reaciei se fac conform unui polinom primitiv g(x) de grad m. Pentru matricea T polinomul caracteristic este: c0c1 cm-21xm0xmP1g0g1g2gm-1cm-1gm-2gm1xn0xnz(x)JKP2V(X) 1cm-2 cm-1c0c121ABg0 g1gm-1gm1[k]2[m]IntrareSumatorIesire2112 ? A =|

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

11 1 0..gm = 1 Conform teoremei Cayley-Hammilton matricea caracteristic T este o rdcin a polinomului caracteristic ______(x) = g(x) deci:g(T) = 0 Se numete perioada matricii caracteristice T (sau lungimea ciclului strilor distincte pe care le poate avea (R.D.) cel mai mic numr ntreg n pentru care:Tn = T0 = IDac S0 = U =[0 0 1]T atunci cele n stri nenule sunt: T0U = U,TU ,T2U , .. ,Tn-1U;TnU = U ntre Ti i Ei (i = 1, n) exist o coresponden biunivoc, fr a se respecta ns indicii. 47) Ce conin celulele codorului cu circuite de divizare pentru un cod ciclic dup k tacte? 48) Cum se realizeaz starea nul pentru codoarele cu circuite de divizare i cu registre de deplasare ale unui cod ciclic? 49) De ce la decodorul cu registru de deplasare al unui cod ciclic se folosesc dou decodoare identice? 50) Care sunt asemnrile i deosebirile dintre un cod bloc i un cod convoluional?Codurile convoluionale difer de codurile bloc att prin faptul c blocul de codare are memorie, ct i prin dependena celor n simboluri de ieire, la fiecare moment de timp, nu numai de cele k simboluri de intrare, ci i de m blocuri de k simboluri anterioare de intrare. Un cod convoluional [n, k] poate fi implementat cu un circuit secvenial care are n ieiri liniare, k intrri i m celule de memorie (sau de ntrziere) pentru fiecare intrare.51) Ce metode de codare exist pentru un cod convoluional? Codarea polinomiala se face pentru fiecare iesire cj(D), j=1,n, calculnd polinoamele intermediare cij(D),i=1,k, j=1,n: 52) Ce reprezint diagrama de stri i diagrama trellis pentru un cod convoluional?Diagrama trellis a codurilor convoluionale 13 Din arborele reprezentat n figura 3, unind nodurile S1 ntre ele, apoi nodurile S2, S3 i S4 se obine diagrama trellis din figura 4. Convenia utilizat n figura 4 pentru a distinge ntre simbolurile de intrare 0 i 1 este: o ramur generat de un simbol de intrare 0 este desenat cu linie continu, iar ramura generat de simbolul de intrare 1 este desenat cu linie punctat. Trellis-ul este format din (k0+K) nivele, unde k0 este lungimea secvenei de informaie, iar K=m+1 este lungimea de constrngere. Nivelele n trellis sunt notate cu j=0, 1, 2,..., k0+K-1. Primele (K-1) nivele sunt corespunztoare plecrii codorului din starea iniial a, iar ultimele (K-1) nivele corespund ntoarcerii circuitului codor n starea S1. Figura 3. Diagrama arbore a codului convoluional [2,1], m=2. 00 11 S0 10 01 S1 11 00 S2 01 10 S3 00 11 S0 10 01 S1 00 11 S0 10 01 S1 11 00 S2 01 10 S3 11 00 S2 01 10 S3 00 11 10 01 S1 00 11 S0 Simbol intrare 0 Simbol intrare 1 00 11 S0 10 01 S1 11 00 S2 01 10 S3 00 11 S0 10 01 S1 00 11 S0 10 01 S1 11 00 S2 01 10 S3 11 00 S2 01 10 S3 00 11 10 01 S1 00 S0 Figura 4. Diagrama trellis pentru codul [2,1], cu m=3 i 1 2 2 2( ) 1 , ( ) 1 g D D g D D D == .. simbol de intrare 0simbol de intrare 1 00 11 S0=00 S1=10 S2=01 S3=11 j=0 00 11 10 01 00 11 00 11 10 01 00 11 01 10 01 11 10 00 00 11 01 10 01 11 10 00 00 11 01 10 01 11 10 00 00 11 01 10 01 11 10 00 1234k0-1k0k0+1 14 S considerm acum o poriune din trellis corespunztoare momentelor de timp de la j la j+1. Presupunem j>=2 pentru exemplul nostru, deci starea curent a codorului poate fi una din cele patru posibile S1, S2, S3 sau S4. Aceast poriune din trellis este prezentat n figura 5. Nodurile 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. Obinem astfel, diagrama de stare a codorului, artat n figura 6. Aceast diagram este de fapt un graf orientat, nodurile grafului reprezentnd strile codorului, iar arcele grafului tranziiile posibile funcie de simbolurile de la intrarea codorului. Dac la intrare avem 0, tranziia este desenat cu linie continu, iar dac avem 1 cu linie punctat. Eticheta fiecrui arc reprezint simbolurile de la ieirea codorului. 53) Un cod convoluional poate fi sistematic? n ce condiii? 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 g(D)=1. Figura 5. Diagrama fluture pentru codul [2,1], cu m=2 i 1 2 2 2( ) 1 , ( ) 1 g D D g D D D == .. simbol de intrare 0 simbol de intrare 1 00 11 00 11 10 01 10 01 S0=00 S1=10 S2=01 S3=11 S0=00 S1=10 S2=01 S3=11 j