03. Elemente de Teoria Transmisiei Informatiei

3ELEMENTE DE TEORIA TRANSMISIEI INFORMAIEI

3.1 Entropia informaional Informaia este un mesaj ce aduce o precizare ntr-o problem ce comport un anumit grad de incertitudine. Dei exist o mare diversitate de informaie, att din punctul de vedere a formei de prezentare, a coninutului, a sursei care o genereaz ct i a modului de recepionare, oamenii de tiin i-au pus problema msurrii ei cantitative. S-a constatat c informaia i nedeterminarea sunt mrimi direct proporionale. Se consider un experiment X n cadrul cruia se pot realiza un numr finit de n evenimente elementare: x1, x2, x3, ..,xn. Probabilitile de apariie ale acestor evenimente le vom nota cu p1, p2, p3, .., pn (pi = numrul cazurilor favorabile evenimentului xi / numrul cazurilor egal posibile ale experimentului). Se presupune c sistemul de evenimente este un sistem complet: pi 0 i = 1, n n i pi = 1 i=1 Experimentul pune n eviden un anumit cmp de probabilitate {X, x, p(x)} i o anumit repartiie:

x1 X = p1

x p

2 2

... x n ... p n

Sisteme de calcul i operare

Deoarece nu se cunoate apriori rezultatul experimentului X, nseamn c acesta conine un anumit grad de nedeterminare. Putem afirma c: n urma realizrii unui experiment se obine informaie dac i numai dac rezultatul experimentului nltur o anumit nedeterminare; informaia i nedeterminarea sunt mrimi direct proporionale; informaia nlocuiete nedeterminare. Aceste particulariti au condus la utilizarea aceleiai uniti de msur att pentru cantitatea de informaie ct i pentru nedeterminare. Nedeterminarea unui experiment depinde de probabilitile de realizare a evenimentelor. Dac se noteaz cu H msura gradului de nedeterminare, pentru experimentul X, aceasta va fi o funcie de probabilitile evenimentelor: H(X) = H(p1, p2, ., pn) n anul 1948, Claude E. Shannon a folosit pentru prima dat formula:H( p1 , p2 ... pn ) = pi log 2 pii =1 n

Msura nedeterminrii, dat de aceast formul, se numete, conform lui Claude Shannon, entropia experimentului X sau entropia informaional. n acest sens, unitatea de msur a informaiei definit ca fiind cantitatea de informaie obinut prin precizarea unei variante din dou egal probabile se numete bit (binary digit), cu multiplii: 1 octet (byte) = 8 bii 1 kilo octet = 210 octei 1 Mega octet = 210 ko = 220 octei 1 Giga octet = 210 Mo = 230 octei 1 Tera octet = 210 Go = 240 octei 1 Peta octet = 210 To = 250 octei 1 cuvnt (word) = 16 / 32 / 64 bii; lungimea variaz n funcie de tipul calculatorului.

Elemente de teoria transmisiei informaiei

Principalele proprieti ale entropiei informaionale sunt: P1. Entropia informaional, fiind msura informaiei, este o entitate nenegativ: H(p1, p2, ., pn) 0. P2. Dac pentru un indice i{1, 2, .., n} avem pi =1, atunci entropia informaional este nul: H(p1, p2, ., pn) = 0. P3. Entropia unui sistem de evenimente este maxim cnd evenimentele au aceeai probabilitate de apariie: H(p1, p2, ., pn) H(1/n, 1/n, 1/n,, 1/n). P4. Evenimentele imposibile nu modific valoarea entropiei informaionale a unui sistem: H(p1, p2, ., pn, 0) = H(p1, p2, ., pn). P5. Entropia produsului mai multor surse independente de informaie este egal cu suma entropiilor fiecrei surse luate separat: H(X1 x X2 xXn) = H(X1) + H(X2) +.. H(Xn). Produsul mai multor surse de informaie reprezint un experiment compus care const din realizarea simultan a cte unui eveniment corespunztor fiecrei surse. este: P6. Entropia produsului a dou surse oarecare X i Y de informaie H(X x Y) = H(X) + H(Y/X). H(Y/X) reprezint cantitatea medie de informaie ce se obine n urma realizrii experimentului Y, condiionat de experimentul X.H(Y/ X) = p( xk )H(Y/ xk )k=1 n


unde: p(xk) probabilitatea realizrii evenimentului xk X ; H(Y/xk) entropia experimentului Y, condiionat de evenimentul xk X.H(Y/ x k ) = p( y i / x k ) log 2 p( y i / x k )i =1 m

iar p(yi/xk) este probabilitatea realizrii evenimentului elementar yi Y ( i = 1 , m ) cnd s-a realizat evenimentul xk X ( k = 1, n ). Dac X i Y sunt experimente oarecare sunt respectate proprietile: P7. H(Y/X) H(Y) P8. H(X x Y) H(X) + H(Y) P9. H(X/Y) = H(Y/X) + H(X) - H(Y) 3.2 Sistem de transmisie a informaiei Schema general a unui sistem de transmisie a informaiei include: sursa, canalul (ce poate fi supus perturbaiilor) i recepia (figura 3.1).

Figura 3.1 Schema unui sistem de transmisie a informaiei fr codificare


Fie: X mulimea mesajelor emise de o surs de informaie (intrarea

sistemului); Y mulimea mesajelor care se recepioneaz (ieirea sistemului); p(y/x) probabilitatea de a recepiona mesajul y Y cnd s-a emis x X. Sistemul de transmisia informaiei este format din dou mulimi finite X i Y i o probabilitate condiionat p(y/x), definit pe Y pentru orice x X i se noteaz cu [X, p(y/x), Y]. Sursa sistemului de transmisie a informaiei este reprezentat prin cmpul de probabilitate {X, x, p(x)}, fiind dat probabilitatea de emisie p(x) pentru x X, astfel nct p( x ) = 1.x X

Recepia sistemului de transmisie a informaiei este reprezentat prin cmpul de probabilitate {Y, y, p(y)}, fiind dat probabilitatea de emisie p(x) pentru x X, iar probabilitatea de recepie se calculeaz prin relaia: p( y) = p( x ) p( y / x ) .x X

Mediul prin care se propag semnalele purttoare de informaie, de la surs la recepie, se numete canalul sistemului de transmisia informaiei. A cunoate canalul de comunicaie al unui sistem, revine la a cunoate probabilitile p(y/x) pentru toate mesajele x X i y Y. Dac p(y/x) ia numai valorile 0 sau 1 pentru orice x X i y Y, asupra canalului nu acioneaz perturbaiile. n caz contrar, canalul prezint perturbaii. ntr-un sistem de transmisia informaiei [X, p(y/x), Y], avnd sursa {X, x, p(x)} i recepia {Y, y, p(y)}, expresiile:H( X ) = H( Y ) =

x X

p( x ) log

2

p( x ) p( y)

y Y

p( y) log

2

reprezint entropiile cmpului de evenimente de la intrare i cmpului de evenimente de la ieire.


Dac se noteaz cu p(x/y) probabilitatea de a se emite mesajul x X cnd se recepioneaz y Y, expresia:H( X / y ) = x X

p( x / y) log

2

p( x / y )

reprezint cantitatea de informaie care trebuie emis de ctre surs pentru a recepiona mesajul y Y. Cantitatea medie de informaie emis ce este necesar pentru a recepiona ntreaga mulime a mesajelor y Y va fi:H( X / Y ) =

y Y

p( y ) H ( X / y ) .

Entropia H(X / Y) se numete echivocaie, fiind msura echivocului care exist n cmpul de la intrare cnd se cunoate cmpul de la ieire (figura 3.2). n mod asemntor, se determin entropia H(Y/X), care se numete eroare medie i este msura incertitudinii cmpului de la ieire cnd se cunoate cmpul de la intrare (figura 3.3). Expresia: I(X,Y) = H(X) - H(X/Y) reprezint informaia transmis prin canal i se mai numete transinformaie. n lipsa perturbaiilor p(x/y) = p(y/x) = 1 sau p(x/y) = p(y/x) = 0 i H(X/Y) = H(Y/X) = 0.

Figura 3.2 Reprezentarea grafic a echivocului


Figura 3.3 Reprezentarea grafic a incertitudinii

3.3 Codificarea informaiei n sistemele de calcul

Conform principiilor de structur i funcionalitate, n calculator sunt recunoscute numai cifrele binare (0 i 1). Se tie c informaia cel mai frecvent este codificat cu ajutorul cifrelor zecimale, literelor alfabetului (caracterele majuscule i minuscule) i diverse semne speciale. Pentru a putea fi prelucrat i eventual transmis cu ajutorul unui sistem de calcul informaia va fi codificat binar. Informaia i codificarea sunt entiti inseparabile. Fie X={x1, x2, x3,..., xN}, mulimea simbolurilor primare emise de o surs de informaie i A={a1, a2,..., aD}, mulimea simbolurilor codului folosit. Cu simbolurile: a1, a2,..., aD se formeaz un numr N de cuvinte de cod: C = {c1, c2,..., cN}.Cuvintele de cod sunt succesiuni finite de simboluri ale mulimii A. Codificarea este operaia de stabilire a unei corespondene biunivoce ntre simbolurile xi X i ci C.

Fie:

c1: a1 a2 a3 x1 c2: a2 a1 a3 x2 c3:

Totalitatea cuvintelor ci (i = 1n) formeaz un cod. Cu ajutorul simbolurile mulimii A se pot forma cuvinte crora s nu le corespund elemente din mulimea X. Acestea sunt cuvinte fr sens. Cuvintele crora le corespund simboluri din alfabetul sursei se numesc cuvinte cu sens sau cuvinte de cod.


Practic, codificarea reprezint o schimbare n forma de prezentare a informaiei, necesar n procesul prelucrrii sau transmisiei. n momentul realizrii codificrii apare i problema transformrii inverse, ce permite revenirea la forma iniial. Aadar, dac exist funcia cod: f:XC trebuie s existe i funcia invers: f-1: C X. Operaia de revenire din mulimea secvenelor de cod n mulimea simbolurilor primare prin intermediul funciei f-1 se numete decodificare. Una din restriciile necesare realizrii codificrii o reprezint lungimea secvenei de cod. Numrul de simboluri elementare dintr-un cuvnt reprezint lungimea acestuia. Dac toate cuvintele de cod au aceeai lungime, codificarea se numete uniform. Stabilirea numrului (NR) de secvene distincte de lungime n, ce se pot crea cu D simboluri elementare, se determin aplicnd formula combinrilor cu repetiie: NR = Dn Pentru realizarea codificrii este necesar ca NR N (N fiind numrul de simboluri primare ce aparin lui X). Pentru codificarea informaiei utilizate ntr-un sistem de calcul mulimea simbolurilor codului este A = {0,1} i innd cont de relaia de mai sus avem: N 2n Prin logaritmarea relaiei se va obine: log2 N n ntr-o codificare uniform, lungimea n a secvenelor de cod trebuie s fie cel puin egal cu entropia maxim a sursei. Cnd se urmrete mrirea eficienei transmisiunii, cuvintele de cod pot avea lungimi diferite, astfel nct lungimea medie l a unui cuvnt s fie ct mai mic.


Fie sursa primar X = {x1, x2,..., xN} avnd probabilitile de realizare P = {p(x1), p(x2),..., p(xN)} iar mulimea cuvintelor de cod C = {c1, c2,..., cN} cu probabilitile PC = {p(c1), p(c2),...,p(cN)} = {p(x1),..., p(xN)}. Lungimile cuvintelor de cod sunt: L = {l1, l2,...,lN}, li fiind numrul de simboluri din alfabetul codului, care compun cuvntul ci. Lungimea medie a unui cuvnt de cod se va calcula dup formula:l =

p( x )i i=1

N

li

Entropia sursei, care este aceeai cu entropia cuvintelor codului, va fi:H(X) = H(C) = -

p( x )i i =1

N

log 2 p( x i )

Dac alfabetul codului este A = {a1, a2,..., aD}, avnd probabilitile PA = {p(a1), p(a2),..., p(aD)}, entropia va fi:H(A) = -

i =1

D

p( a i ) log 2 p( a i ) log 2 D

Informaia medie pe cuvnt va fi:H(C) = H(X) = l H(A) .

nlocuind pe H(A) prin relaia precedent se va obine:H(X) l log2 D

l

H(X) = lmin log2 D

Relaia obinut arat c lungimea medie l a unui cuvnt de cod are o margine inferioar egal cu entropia sursei mprit la valoarea maxim a entropiei alfabetului codului sau informaia medie pe un simbol din H(X) alfabetul codului nu poate fi mai mare dect valoarea maxim a l H(X) log2 D . alfabetului codului log2D, adic l


Pentru realizarea unei codificri se mai ine seama de:Capacitatea codului, valoarea maxim a entropiei alfabetului codului:

Ccod = max H(A) = log2D.Eficiena codului, raportul dintre lungimea medie minim i l cod = min . nlocuind lungimea medie a unui cuvnt de cod: l l min i l se va obine: H(X) / log 2 D H(A) cod = = . log 2 D H(X) / H(A)

Redundana codului este mrimea complementar eficienei: H(A) . R cod = 1 - cod = 1 H max (A) 3.4 Coduri numerice i alfanumerice

Codurile n care sunt reprezentate numai numere se numesc coduri numerice, iar cele care cuprind numerele, literele i semnele speciale se numesc coduri alfanumerice. Dintre codurile alfanumerice amintim: Codul BCD (Binary Coded Decimal), reprezint unul din primele coduri utilizate n tehnica de calcul. O secven de cod are lungimea de ase bii/caracter. Codul EBCDIC (Extended Binary Coded Decimal Information Interchange Code), secvenele de cod au o lungime de opt bii/caracter. Standardul ASCII (American Standard Code for Information Interchange) secvenele de cod au o lungime de opt bii/caracter. Standardul Unicode utilizeaz secvene de cod cu lungimea de 16 bii/caracter. Acest cod a fost conceput s nlocuiasc standardul ASCII, prin intermediul cruia se pot reprezenta maximum 256 (28) caractere. Codul ASCII este un subset al standardului Unicode. Caracterele de baz din toate limbile scrise existente pot fi reprezentate prin standardul Unicode.


Codurile normalizate au fost realizate n aa fel nct s uureze modul de prelucrare a informaiei. Astfel, partea stng a codului permite identificarea imediat a naturii informaiei codificate (litere, cifre, funcii), urmtoarele poziii ale codului sunt organizate ntr-un mod care s uureze conversia n vederea calculelor (n cazul cifrelor) sau ordonarea alfabetic (n cazul literelor).Coduri alfanumericeTabelul 3.1

Caracterul 0 1 2 3 9 a b z A B Z LF(line feed)

Codul ASCII 0011 0000 0011 0001 0011 0010 0011 0011 0011 1001 0110 0001 0110 0010 0111 1010 0100 0001 0100 0010 0101 1010 0000 1010

Codul EBCDIC 1111 0000 1111 0001 1111 0010 1111 0011 1111 1011 1000 0001 1000 0010 1010 1001 1100 0001 1100 0010 1110 1001 0010 0101

Codul UNICODE (0030)H (0031)H (0032)H (0033)H (0039)H (0061)H (0062)H (007A)H (0041)H (0042)H (005A)H (000A)H

Codurile numerice au fost introduse pentru a se opera mai uor cu informaia numeric. Codurile numerice pot fi: ponderate; neponderate.

Un cod numeric este ponderat dac unei cifre zecimale i corespunde o succesiune de cifre binare, n care fiecare cifr de rang j are asociat o anumit pondere Pj. Fie N un numr zecimal:N = zk zk-1 zk-2 .... z0 zi {0, 1, ....9} i = 0, k


Oricare ar fi cifra zecimal zi, aceasta se va reprezenta printr-o secven binar ce satisface relaia:zi =

ajj=1

n

Pj

,

unde: aj{0,1},

P j {0, 1, 2, ....9} constituie ponderea corespunztoare rangului j, iar n numrul de simboluri din secvena binar asociat cifrei zecimale.

Dintre codurile ponderate amintim (tabelul 3.2):Codul 8421, codul binar-zecimal natural, avnd ca ponderi puterile lui 2 (23,22,21,20). Coduri ponderateTabelul 3.2

Cifra zecimal 0 1 2 3 4 5 6 7 8 9

Codul 8421 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

Codul 2421 0000 0001 0010 0011 0100 1011 1100 1101 1110 1111

Codul 8421 0000 0111 0110 0101 0100 1011 1010 1001 1000 1111

Codul bichinar 50 43210 01 00001 01 00010 01 00100 01 01000 01 10000 10 00001 10 00010 10 00100 10 01000 10 10000

Codul 2421 (Aiken), la care codificarea primelor cinci cifre zecimale (04) este identic secvenelor din codul 8421. Codificarea cifrei zecimale 5 se obine din secvena corespunztoare cifrei zecimale 4 prin schimbarea simbolurilor binare 0 n 1 i 1 n 0. Astfel, fiecare complement fa de 9 al unei


cifre zecimale se reprezint printr-o secven ce rezult complementnd fa de 1 simbolurile binare din secvena cifrei zecimale respective. Codurile ce au aceast proprietate se numesc autocomplementare, prezentnd avantaje n efectuarea operaiilor aritmetice. Pentru codul 8421 ponderile sunt puteri ale lui 2, ns dou sunt negative. Este un cod auto-complementar. Codul bichinar (50 43210) conine secvene de cte apte simboluri binare mprite n dou grupe. Acest cod a fost folosit la primele calculatoare electronice. Alte coduri numerice ponderate sunt: 4221, 5421, 7421, 6421 (tabelul 3.3).Coduri ponderate (a doua parte)Tabelul 3.3

Cifra zecimal 0 1 2 3 4 5 6 7 8 9

Codul 4221 0000 0001 0010 0011 0110 1001 1100 1101 1110 1111

Codul 5421 0000 0001 0010 0011 0100 1000 1001 1010 1011 1100

Codul 7421 0000 0001 0010 0011 0100 0101 0110 0111 1001 1010

Codul 6421 0000 0011 0010 0101 0100 0111 1000 1011 1010 1101

Din categoria codurilor neponderate, amintim (tabelul 3.4): Codul EXCES 3 a fost realizat de G. Stibitz i se remarc prin aceea c: o este un cod autocomplementar; o cifrei zecimale zero i corespunde o secven binar ce conine cifre binare de 1.


Codul Gray se caracterizeaz prin aceea c dou secvene de cod consecutive difer printr-o singur poziie binar. Dac notm cu: a8, a4, a2, a1 cifrele binare ale secvenelor codului 8421, n ordinea ponderilor i cu b4, b3, b2 i b1 cifrele binare ale secvenelor Gray, n ordinea de la stnga la dreapta, acestea din urm pot fi calculate folosind relaiile: b8 = a8; b3 = a8 a4; b2 = a4 a2; b1 = a2 a1. Codul 2 din 5 este un cod pseudo-ponderat. Secvenele de cod pentru cifrele zecimale 1 9 au asociate ponderile 74210, numai codificarea cifrei zecimale 0 face excepie de la aceast regul. Caracteristica secvenelor de cod este aceea c din cele cinci cifre binare dou sunt semnificative (au valoarea 1). Coduri neponderateTabelul 3.4

Cifra zecimal 0 1 2 3 4 5 6 7 8 9

Codul Exces 3 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100

Codul Gray 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101

Codul 2 din 5 (74210) 11 000 00 011 00 101 00 110 01 001 01 010 01 100 10 001 10 010 10 100

Codul de bare reprezint un sistem de codificare prin care se permite identificarea automat sau semiautomat a diverselor entiti (legitimaii, cri, bilete de avion, produse din cele mai variate etc.). Codul de bare are avantajul de a fi relativ simplu de produs i recunoscut. El poate fi aplicat direct pe orice produs (pe ambalajul acestuia) sau ulterior, ca etichet. Majoritatea codurilor de bare au la baz principiul binar, reprezentarea fcndu-se printr-un numr de linii sau linii i spaii cu o anumit lime. Secvena de linii sau linii i spaii reprezint un caracter numeric sau alfanumeric.


Pentru exemplificare vom considera codul 2/5 (2 din 5) (tabelul 3.5), cod numeric (sunt reprezentate cifrele de la 0 la 9). Codificarea se face prin trasarea a dou linii late i trei nguste. Raportul de imprimare linie ngust/linie lat este de 1/2 sau 1/3. Spaiile nu conin informaie.Codul de bare 2/5Tabelul 3.5

Caracter Linia1 Linia2 1 1 0 2 0 1 3 1 1 4 0 0 5 1 0 6 0 1 7 0 1 8 1 0 9 0 1 0 0 0 start 1 1 stop 1 0 1: linie lat 0: linie ngust

Linia3 0 0 0 1 1 1 0 0 0 1 0 1

Linia4 0 0 0 0 0 0 1 1 1 1

Linia5 1 1 0 1 0 0 1 0 0 0

Figura 3.4 Reprezentarea numrului 19 prin codul de bare 2/5


Dac n cazul codului 2 din 5 spaiile nu conin informaie, exist i un cod asemntor n care densitatea informaiei reprezentate este mai mare; acest cod se numete codul 2 din 5 intercalat iar n acest caz spaiile conin informaii n acelai mod ca i liniile. Codificarea informaiei permite rezolvarea unor probleme ce pot apare n transmisia, stocarea sau prelucrarea acesteia, cum ar fi: detectarea i corectarea erorilor pentru a se asigura integritatea informaiei; compresia pentru minimizarea cantitii de informaie; criptarea pentru a se garanta securitatea informaiei.

3.5 Coduri detectoare i corectoare de erori

Codificarea se efectueaz avnd ca scop principal protejarea informaiei de perturbaiile ce pot s apar ntr-un sistem de transmisie. De aceea, nainte de a emite simbolurile de informaie pe canalul de comunicaie, ce poate fi supus perturbaiilor, se adaug o anumit informaie redundant, de obicei prin introducerea unor simboluri suplimentare, numite simboluri de control. Rolul acestor simboluri de control este acela de a indica utilizatorului prezena erorilor i chiar s-i dea posibilitatea de a le corecta. Codurile obinute astfel, prin mrirea redundanei, se numesc coduri detectoare i corectoare de erori. n acest caz, schema unui sistem de transmiterea informaiei este reprezentat n figura 3.5.

Figura 3.5 Sistem de transmisia informaiei


Se poate face o clasificare a codurilor detectoare i corectoare de erori dup modul de prelucrare al simbolurilor. Dac prelucrrile necesare obinerii proprietilor de detecie sau de corecie se fac n blocuri de n simboluri, avem coduri bloc. Dac prelucrarea simbolurilor generate de surs se realizeaz n mod continuu, avem de-a face cu coduri convoluionale (recurente). Din categoria codurilor bloc se disting: codurile grup, secvenele de cod sunt considerate ca fiind elemente dintr-un spaiu vectorial; codurile ciclice, secvenele de cod sunt considerate ca fiind elemente ntr-o algebr.

3.5.1

Distana de cod

Fie c = [a1,....,an], un cuvnt de cod, conform unei codificri binare ai {0,1} pentru i = 1, n . Notm cu W mulimea tuturor cuvintelor (N=2n), care are o structur de spaiu vectorial, iar mulimea cuvintelor cu sens o notm cu V (presupunem c NC=2k) ce are o structur de subspaiu vectorial. Dac toate secvenele care se pot realiza sunt cuvinte de cod (W=V), nu va exista posibilitatea de a detecta sau corecta erorile ce apar n procesul de transmitere pe canal. Practic, dac un cuvnt de cod se modific prin canal, datorit perturbaiilor, se va obine tot un cuvnt de cod, respectiv un cuvnt cu sens. Pentru a avea posibilitatea de a detecta prezena erorilor n secvenele de cod recepionate, mulimea W a cuvintelor se va divide n dou submulimi: a cuvintele cu sens (V) i submulimea cuvintelor fr sens (F). La un anumit grad de redundan atribuit unei codificri se pot stabili mai multe coduri. Dintre acestea nu toate ofer posibiliti n depistarea erorilor i eventual corectarea lor. Codurile care asigur o anumit capacitate de detecie i eventual corecie cu ajutorul unor redundane minime se numesc coduri optimale. Pentru a realiza codificarea se va lua n calcul parametrul denumit distana de cod (distana Hamming). n spaiul n dimensional al cuvintelor de cod se introduce funcia distan D(vi,vj) care satisface proprietile unui spaiu metric.


Prin definiie aceast funcie este:D( vi, vj ) = ( aik ajk ) ,k =1 n

unde

vi = [ai1, ai2, , ain] i vj = [aj1, aj2,, ajn]

iar se refer la adunarea modulo 2 n timp ce +, la adunarea n corpul numerelor reale. Se poate spune c distana dintre dou cuvinte de cod este egal cu numrul de simboluri prin care cele dou cuvinte se deosebesc.Exemplul 1

S se calculeze distana de cod ntre secvenele de cod reprezentate n figura 3.6.Rezolvare. n figura 3.6.a) toate secvenele de cod sunt cuvinte cu sens. Calculnd distanele de cod, avem:

D(v0,v1)=(0 0) + (0 0) + (0 1) = 1 D(v0,v2)=(0 0) + (0 1) + (0 0) = 1 D(v0,v3)=(0 0) + (0 1) + (0 1) = 2 D(v0,v4)=(0 1) + (0 0) + (0 0) = 1 . . D(v0,v7)=(0 1) + (0 1) + (0 1) = 3 D(v1,v2)=(0 0) + (0 1) + (1 0) = 2 . . D(v1,v7)=(0 1) + (0 1) + (1 1) = 2 . . D(v6,v7)=(0 1) + (1 1) + (1 1) = 1 Se constat c: Dmin=1.


Figura 3.6 Reprezentarea geometric a secvenelor de cod

n (figura 3.6.b) numai dou secvene sunt cuvinte cu sens, iar distana de cod va fi : D(v0,v7)=(0 1) + (0 1) + (0 1) = 3 Probabilitatea de detecie i corecie a unui cod depinde de distana minim ntre dou cuvinte de cod. Se poate demonstra c pentru un cod ce poate detecta un numr de e erori existente n una din secvenele sale, este necesar ca: Dmin e + 1 iar pentru a detecta e erori i a corecta c erori, avnd c e, este necesar ca: Dmin e + c + 1 Pentru realizarea unor structuri de cod optime se va ine seama de: numrul secvenelor ce aparin codului (NC); lungimea cuvintelor de cod; distana minim de cod (Dmin). Operaia de determinare a simbolurilor de control funcie de simbolurile de informaie se numete codificare redundant.


3.5.2

Codul Hamming

Se consider un spaiu m-dimensional, denumit spaiu de corecie, care are 2m elemente corectori (z). Rolul corectorilor este de a indica poziiile din cuvintele de cod n care au aprut erori. Se definete operatorul H, ce stabilete o coresponden univoc ntre mulimea tuturor cuvintelor recepionate i mulimea corectorilor, astfel:H{vi} = z

Dac vi= vi, atunci H{vi} = 0. Structura cea mai simpl pentru operatorul H se obine dac se va considera o transformare liniar, definit prin ecuaiile: h11 a1 + h12 a2 + . h1n an = em h21 a1 + h22 a2 + . H2n an = em-1. .

hm1 a1 + hm2 a2 + . Hmn an = e1 unde: hij - parametrii care determin transformarea H; ai - simbolurile cuvntului recepionat; ei - elementele corectorului z. Ecuaiile se pot scrie sub form matricial utiliznd notaiile:

h1 n h 2n - este matricea de control; hmn em v = [ a1 a2 an ] - cuvnt recepionat i z = - cuvnt corector. e2 e1

h11 h12 h 21 h 22 H = hm1 hm 2


Folosind aceste notaii putem scrie: H vT = z, iar n cazul cnd v = v vom avea:H vT = 0

Aceasta este relaia care se va folosi pentru determinarea celor m simboluri de control, n funcie de simbolurile generate de sursa de informaie (n numr de k). Operaia prin care se determin valorile simbolurilor de control n funcie de simbolurile generate de sursa de informaie se numete codificare redundant. Codul Hamming asigur detecia i corecia unei singure erori. Pentru a indica poziia erorii ntr-unul din cele n simboluri ale cuvntului de cod sau pentru a indica absena erorilor este necesar ca numrul corectorilor 2m n + 1. Cum n = k + m, o s avem: 2m m + k + 1. Aceasta este relaia prin care se determin numrul m al simbolurilor de control cnd se cunoate numrul k al simbolurilor de informaie, n cazul coreciei unei singure erori. Codul Hamming este caracterizat de o matrice de control Hm,n, n care coloana hi este reprezentarea binar a numrului i.H = [h1h2....hn]

Se consider cuvntul eroare, cu o singur poziie eronat: e=[0,...,j,...0] (j=1)

Dac se transmite mesajul vi se va recepiona: v`i=vi e (perturbaie aditiv) Corectorul corespunztor va fi: T T T Z = H v = H ( v i e ) = H v H eT i i


Deoarece H v = 0 este relaia ce se folosete pentru determinareai

T

celor n simboluri de control, vom avea:0 . . Z = H e T = [h1 h 2 ..... h j .... h n ] j = h j . . 0 Aadar, corectorul este reprezentarea binar a numrului j, indicnd poziia n care exist eroarea. Pentru a simplifica operaia de calcul a celor m simboluri de control, acestea se vor alege astfel nct s corespund vectorilor coloan hi cu o singur component diferit de 0. Notnd cu ci simbolurile de control i cu aj pe cele de informaie, vectorul cuvnt de cod va fi: v=[c1c2a3c4....an]. T innd seama de relaia H v = 0 obinem: i c1 c 2 a3 [h1 h 2 .... h n ] = 0 sau . . a n 0 0 . . . . 1 0 . . . . . 1 ........ ........ 0 1 . . . . . 1 0 . . . . 1 c1 c 2 . = 0 . . a n


relaie echivalent cu m ecuaii n care simbolurile c1, c2, intervin o singur dat: c1 a 3 a 5 ..... a n = 0 c 2 a 3 a 6 ..... a n = 0 . . c m a m+1 ....... a n = 0

tiind c 0 0 = 0 i 1 1= 0 se vor determina simbolurile de control c1, c2,...,cm. La recepionarea cuvintelor de cod v', acestea se introduc ntr-un dispozitiv pentru a calcula corectorul, utiliznd relaia:' c1 e m ' . c2 Z = H v ,T = = [h1...... h n ] . e2 . e1 a ' n

n mod analog calculului anterior i innd seama de structura matricii de control H se va obine:' e1 = c1 a '3 ..... a 'n ................. e ' ' ' m = c m a m +1 ...+ a n

Numrul binar (em.....e2,e1) se decodific i se obine poziia erorii, conform relaiei de mai sus. Vom particulariza pentru k=4, numrul simbolurilor de informaie. Din relaia: 2m m + k + 1, avem c 2m 5 + m, de unde se va obine m 3. Considernd m=3 vom avea n = m + k = 7.


Matricea de control este: H3,7=[h1h2.....h7], iar vectorul cuvnt de cod va fi: v=[c1c2a3c4a5a6a7]. Aplicnd relaia HvT=0 vom avea: c1 c2 0 0 0 1111a 3 0 11 0 0 11 = 0 c4 1 0 1 0 1 0 1a 5 a 6 a 7

Prin efectuarea calculelor se obine:c4 a5 a 6 a 7 = 0 c4 = a5 a 6 a 7 c 2 a 3 a 6 a 7 = 0 c 2 = a 3 a 6 a 7 c a a a = 0 c = a a a 3 5 7 5 7 1 1 3

Calcularea corectorului la recepie se obine din relaia:' c1 c '2 a '3 ' c 4 ' a 5 ' a 6 ' a 7

e 4 0 0 0 1 1 1 e 2 = 0 1 1 0 0 1 e1 1 0 1 0 1 0

1 1 1


Efectund calculele se va obine:e4 = c '4 a '5 a '6 a '7 e2 = c '2 a '3 a '6 a '7 e = c' a ' a ' a ' 3 5 7 1 1

Combinaia binar (e4,e2,e1) decodificat indic poziia eronat. Codul Hamming poate corecta erorile simple ns nu poate corecta nici o eroare dubl.Exemplul 2. S se determine secvenele codului Hamming corespunztoare cifrelor zecimale 7,8 i 9 tiind c n codificarea primar s-a folosit codul 8421. Este respectat condiia distanei minime? Rezolvare Pentru calcularea cifrelor de control c1,c2,c4 din secvenele codului Hamming (tabelul 3.6) se utilizeaz relaiile obinute anterior. Secvenele de codTabelul 3.6Cifra zecimal Secvenele codului

8421 a3 7 8 9 0 1 1 a5 1 0 0 a6 1 0 0 a7 1 0 1 c1 0 1 0 c2 0 1 0

Hamming (calculate) a3 0 1 1 c4 1 0 1 a5 1 0 0 a6 1 0 0 a7 1 0 1

Deoarece codul Hamming detecteaz i corecteaz o singur eroare va fi necesar ca Dmin 3. Vom calcula distana minim n raport cu secvenele codului Hamming obinute: D(v7,v8)=(0 1) + (0 1) + (0 1) + (1 0) + (1 0) + + (1 0) + (1 0) = 7 D(v7,v9)=3 D(v8,v9)=4 Condiia distanei minime de cod este respectat, Dmin =3.


Exemplul 3

Fie mesajul recepionat 1111000. a) tiind c reprezint o secven a codului Hamming, s se verifice corectitudinea lui. n caz de eroare, presupunnd c o singur poziie este eronat, s se asigure corecia. b) Crei cifre zecimale i corespunde mesajul corectat, dac ntr-o prim codificare a fost folosit codul 8421.Rezolvare Apelnd la relaiile:e4 = c '4 a '5 a '6 a '7 e2 = c '2 a '3 a '6 a '7 e = c' a ' a ' a ' 3 5 7 1 1

vom calcula (e4, e2, e1), avnd:c'1 1 c'2 1 a'3 1 c'4 1 a'5 0 a'6 0 a'7 0

e4 = 1 0 0 0 = 1 e2 = 1 1 0 0 = 0 e = 1 1 0 0 = 0 1

Deoarece (e4,e2,e1) (0,0,0), mesajul recepionat este eronat. Dac o singur cifr binar a mesajului a fost modificat, atunci se poate face corecia; cunoscnd poziia eronat prin decodificarea lui (e4,e2,e1)= (100)2 (4)10 cifra c'4 devine 0. Mesajul corect este 1110000 acesta corespunde cifrei zecimale 8. Aceasta s-a obinut prin decodificarea cifrelor binare: a'3 a'5 a'6 a'7.3.5.3 Coduri liniare cu control ncruciat.

Un alt model de cod binar utilizat frecvent const din structurarea informaiei pe blocuri de secvene de cod i ataarea unui bit de control, o dat fiecrei secvene i alt dat la fiecare coloan ce conine biii de acelai rang din toate secvenele.


Un astfel de control se numete prin paritate ncruciat. Blocul de informaie codificat ce se va emite este:Simboluri informaionale Controlul liniei

a11 a12 ....a1n ............ ............ am1 am2 ....amnControl coloan

l1 . . lm

c1 c2.......cn

unde: n realizeaz paritatea par a ik k =1 li = n (i =1, m ) a ik 1 realizeaz paritatea impar k =1 i se numete paritate lateral sau transversal, iar

m a kj realizeaz paritatea par k =1 cj = m (j=1,n ) a kj 1 realizeaz paritatea impar k =1 i se numete simbol de paritate longitudinal. Controlul erorilor pe principiul paritii ncruciate poate conduce la: depistarea erorilor att prin paritate transversal ct i prin paritate longitudinal; depistarea numai prin paritate transversal sau longitudinal; erorile s nu fie depistate.


Blocul de informaie ce se recepioneaz va fi:Simboluri informaionale a'11 a'12 ..a'1n a'21 a'22 ..a'2n . a'm1 a'm2 ..a'mn c'1 c'2 c'n Controlul liniei l'1 l'2 . . l'm

Control coloan

l'm+1 (c'n+1)

La recepie se vor calcula:lic = a ik [ 1] , i = 1, mk =1 n

ic jc = a kj [1] , j = 1, nk=1 m

folosind acelai tip de paritate ca la emisie. Comparnd paritile recepionate cu cele calculate, se poate afirma c blocul de informaie a fost transmis: a) fr erori, dac l'i = l ic pentru i = 1, m i c'j = cjc pentru j = 1, n ; b) cu erori, dac i{1, 2,, m} astfel nct l'i lic j{1, 2,, n} astfel nct c'j cjc.Exemplul 4

sau

tiind c ntr-o transmisie de date se utilizeaz detectarea erorilor prin paritate ncruciat, care este blocul de informaie ataat emisiei cifrelor zecimale de la 4 la 9, codificate primar cu ajutorul codului EXCES 3. O secven este reprezentat prin codificarea unei singure cifre zecimale.


RezolvareInformaia transmis Cifra zecimal 4 5 6 7 8 9 Secvena S1 S2 S3 S4 S5 S6 Control coloan Simbolurile informaionale EXCES 3 x1 x2 x3 x4 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 Control linie 1 1 0 0 1 0 1

Exemplul 5.

Cunoscnd c a fost transmis un bloc de date n condiiile exemplului 4 i s-a recepionat:0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1

S se verifice corectitudinea recepiei.Informaia recepionat x'1 x'2 x'3 x'4 l'i 0 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0

S1 S2 S3 S4 S5 S6 C'j Cj calculat

li calculat 0 1 0 0 1 0 1


Avem:

l'1 l1 calculat i l'3 l3 calculat; c'4 c4 calculat i c'5 c5 calculat.

Erorile sunt n secvenele: S1 i S3 pe poziiile x'4 i l'1.3.5.4 Coduri polinomiale ciclice

Codurile ciclice sunt coduri bloc n care cele n+1 simboluri ce formeaz o secven de cod sunt considerate ca fiind coeficienii unui polinom de grad n i anume: M(x) = anxn +an-1xn-1 ++a0 unde ai {0, 1} , i = 1, n . Codurile polinomiale ciclice au proprietatea: dac M = (an,an-1,....a0) este un cuvnt cu sens, atunci orice permutare ciclic a simbolurilor sale este un cuvnt cu sens M1 = (ai,ai-1,....,a0anan-1,....,ai+1). Mulimea tuturor cuvintelor formeaz o algebr, iar mulimea cuvintelor cu sens formeaz un ideal. n cazul utilizrii codurilor polinomiale ciclice, mesajului M ce se va transmite i se asociaz polinomul M(x) i apoi printr-un algoritm de codificare se transform ntr-un polinom T(x), astfel nct T(x) s fie multiplul al polinomului G(x), numit polinomul de generare. Pentru realizarea codificrii se pot utiliza algoritmul de nmulire sau algoritmul de mprire. Folosind algoritmul de nmulire: T(x)=M(x)G(x) (operaiile de nmulire i adunare ale coeficienilor polinoamelor se fac n modulo 2) nu se obine o separare a simbolurilor redundante de cele informaionale, acesta fiind principalul motiv pentru care se prefer algoritmul de mprire, dei este ceva mai complicat. Algoritmul de codificare prin mprire este: Fie mesajul M: (an,an-1,.....,a0), care cuprinde n+1 cifre binare informaionale. Acestuia i se asociaz un polinom n nedeterminata x: M(x) = anxn +an-1xn-1 ++a0 (ai {0, 1}, i = 1, n ); Se alege polinomul G(x) de grad r, acesta fiind polinomul de genarare al codului: G(x) = brxr + br-1xr-1 +..+ b0, bj {0, 1}, j = 1, r ; nmulind M(x) cu xr se va obine M'(x)=M(x)xr


Se mparte M'(x) la G(x):

R(x) M (x) = C(x) G(x) G(x)Gradul polinomului R(x) va fi mai mic, cel mult egal cu r-1. Coeficienii polinomului R(x), de grad r-1, constituie simbolurile de control asociate mesajului informaional. Se adun R(x) cu M'(x) obinndu-se polinomul T(x) = M' (x) R(x). Coeficienii polinomului T(x) constituie mesajul ce se va transmite: T: (anan-1....a0cr-1.....c0) care conine n poziiile semnificative cele n+1 simboluri informaionale iar n poziiile mai puin semnificative cele r simboluri de control. Polinomul ataat mesajului transmis este un multiplu al polinomului de generare. Avem:

R(x) T(x) M (x) R(x) M (x) = = G(x) G(x) G(x) G(x) R(x) M (x) M (x) = C(x) nlocuind prin relaia se va obine: G(x) G(x) G(x)T(x) R(x) R(x) = C(x) = C(x) G(x) G(x) 14 244 4 G(x) 3=0

Cu alte cuvinte, polinomul T(x) este divizibil prin G(x). Aceast proprietate este folosit drept criteriu pentru detecia erorilor. La recepie, dac mesajul recepionat este T', acestuia i se asociaz polinomul T'(x). Putem scrie c T'(x)=T(x) E(x), unde E(x) este polinomul erorilor. Aplicnd criteriul de detecie a erorilor, obinem:T (x) T(x) E(x) T(x) E(x) E(x) = = = C(x) G(x) G(X) G(x) G(x) G(x)


Se observ c dac E(x) este multiplu al lui G(x), mesajul recepionat este validat, dei conine erori. Dac E(x) nu este multiplu al lui G(x) atunci eroarea este sesizat. Prin aceast metod sunt determinate toate pachetele de erori de lungime mai mic dect gradul lui G(x)+1. Se numete pachet de erori o succesiune de simboluri, corecte sau eronate, n care primul i ultimul simbol sunt eronate.Exemplul 6

Mesajul binar M: 1110101 se transmite dup codificarea prin polinomul de generare G(x) = x3 + x + 1. Care este reprezentarea binar a mesajului transmis?Rezolvare.

Mesajului binar M : 1110101 i se asociaz polinomul M(x): 6 5 4 2 M(x) = x + x + x + x + 1; 3 M'(x) = M(x) x ; deoarece gradul lui G(x) este 3. 9 8 7 5 3 M'(x) = x + x + x + x + x Se mparte M'(x) la G(x):

M (x) R(x) = C(x) G(x) G(x) x9 + x8 + x7 + x5 + x3 |x3 + x + 1 |--------9 7 6 x + x +x |x6 + x5 + 1 ----------------------/ x8 + x6 + x5 + x3 x8 + x6 + x5 -----------------------/ / / x3 x3 + x + 1 ----------/ x+1 (Adunarea i scderea n modulo 2 sunt echivalente) R(x) = x + 1

Se obine polinomul T(x) = M'(x) R(x) T(x) = x9 + x8 + x7 + x5 + x3 + x + 1


Coeficienii acestui polinom reprezint mesajul ce se va transmite:

Exemplul 7 tiind c mesajul recepionat T': 1010101011 a fost transmis dup codificarea prin polinomul de generare G(x) = x3 + x + 1, s se verifice corectitudinea lui. Rezolvare. Mesajului recepionat T' i se asociaz polinomul T'(x) = x9 + x7 + + x5 + x3 + x + 1. Aplicnd criteriul de detecie a erorilor, obinem:T (x) T(x) E(x) E(x) = = C(x) G(x) G(x) G(x)

x9 + x7 + x5 + x3 + x + 1

x9 + x7 + x6 ---------------------------------------/ / x6 + x5 + x3 + x + 1 x6 + x4 + x3 -----------------------------/ x5 + x4 + x + 1 x5 + x3 + x2 -------------------------/ x4 + x3 + x2 + x + 1 x4 + x2 + x --------------------/ x3 + 1 x3 + x + 1 ----------------/ / x / Aadar, mesajul recepionat este eronat deoarece E(x) 0.

| x3 + x + 1 |-------------------| x6 + x3 + x2 + x + 1

03. Elemente de Teoria Transmisiei Informatiei

Documents

Transcript of 03. Elemente de Teoria Transmisiei Informatiei