Legatura de date

Legatura de date

Acest nivel realizeaza o comunicare sigura si eficienta intre doua noduri adiacente (conectate printr-un canal fizic de comunicatie care asigura livrarea bitilor in aceeasi ordine in care au fost transmisi).

Servicii si functii

Serviciul principal este transferul datelor de la nivelul retea al nodului sursa la nivelul retea al nodului destinatar. Categoriile uzuale de servicii sunt urmatoarele:

- neconfirmate si neorientate pe conexiune - utilizate in medii cu rate scazute de erori, recuperarea fiind facuta de nivelele superioare; sunt caracteristice sistemelor in timp real unde datele intarziate sunt mai rele ca datele eronate;

- confirmate si neorientate pe conexiune - fiecare cadru este receptionat individual si confirmat; daca nu se primeste confirmarea intr-un anumit interval de timp se face retransmisia;

- orientate pe conexiune - garanteaza receptia corecta a tuturor cadrelor in succesiunea transmisa; transferul este caracterizat de trei faze distincte:

- stabilirea conexiunii,

- transmisia datelor,

- desfiintarea conexiunii.

Realizarea serviciilor mentionate se bazeaza pe impartirea sirurilor de biti in cadre, carora le sunt atasate informatii de control al corectitudinii transmisiei. In cazul unor erori, corectia se face prin retransmisia cadrului.

Functiile nivelului legatura de date sunt urmatoarele:

- Controlul cadrului

- Transmisia transparenta

- Controlul erorilor

- Controlul fluxului

- Controlul cadrului

Se refera la delimitarea inceputului si sfarsitului cadrelor transmise. Un cadru reprezinta un mesaj (sau pachet) sau o parte a mesajului. Realizarea acestei functii se bazeaza pe utilizarea unor caractere de control (protocolul BSC - Bynary Synchronous Communication, utilizat de IBM), a unei combinatii formate din caractere de control (pentru inceputul mesajului) si dintr-un contor de caractere (DDCMP - Digital Data Communications Message Protocol) sau a unor delimitatori constand din secvente fixe de biti (HDLC - High Level Data Link Control).

- Transmisia transparenta

Asigura transferul datelor binare sau codificate nestandard, care includ coduri corespunzatoare delimitatorilor de cadre sau alte caractere de control.

- Controlul erorilor

Se realizeaza prin urmatoarele mecanisme:

- adaugarea unei informatii de control a cadrului, care permite receptorului sa verifice corectitudinea acestuia;

- utilizarea unor confirmari pentru cadrele receptionate, transmitatorul fiind informat despre succesul sau insuccesul operatiilor sale;

- utilizarea unor ceasuri care permit tratarea situatiilor de pierdere a cadrelor sau confirmarilor;

- utilizarea unor numere de secventa pentru eliminarea duplicatelor si detectarea cadrelor pierdute, permitand totodata refacerea secventei corecte a cadrelor la receptie;

- Controlul fluxului

Evita transmiterea cadrelor cu viteza mai mare decat cea cu care receptorul le poate accepta.

- Gestiunea legaturii

Se refera la stabilirea si desfiintarea conexiunilor, initializarea numaratoarelor, readucerea conexiunilor intr-o stare normala de functionare dupa producerea unor erori.

2. CONTROLUL ERORILOR

Deoarece informatia transmisa printr-un canal de comunicatie este supusa perturbatiilor, sunt necesare masuri de detectie si eventual de corectie a erorilor. O cale este utilizarea unui codificator la transmisie si a unui decodificator la receptie.

Codificatorul transforma o secventa de cifre binare sursa = ( , d[i], d[i+1], ), intr-o alta secventa codificata = ( , a[i], a[i+1], ), care este transmisa prin canalul de comunicatie, ajungand la destinatie in forma (eventual perturbata) receptionata = ( , a'[i], a'[i+1], ). Decodificarea acesteia produce secventa decodificata = , d'[i], d'[i+1], ), coincidenta cu sursa (daca se foloseste un cod corector de erori) sau eventual diferita si insotita de un indicator de eroare (daca se foloseste un cod detector de erori). Corectia in a doua varianta se poate face prin retransmisie.

3. CLASIFICAREA CODURILOR

Uzual, secventele , d[i], d[i+1], ) sunt decupate in blocuri de cate k biti, fiecarui bloc asociindu-se n biti de control. O astfel de codificare se numeste sistematica. Daca bitii de control se deduc din bitii de informatie din blocul curent, codul este BLOC. Daca ei depind si de blocurile anterioare codul este CONVOLUTIONAL sau RECURENT. Aplicatiile de transmitere si prelucrare a datelor folosesc coduri bloc.

4. CODURI CICLICE

Codurile ciclice fac parte din categoria codurilor liniare. O secventa de cod de forma:

unde a_i apartine multimii A, (multimea simbolurilor elementare), reprezinta in teoria codurilor liniare un vector ce apartine unui spatiu vectorial V_n. Intr-o alta formalizare matematica, secventei descrise mai sus i se poate asocia un polinom de gradul n-1 sau mai mic de forma:

In acest polinom variabila are rolul de a fixa pozitia simbolurilor in cadrul secventei de cod si poarta denumirea de nedeterminata x.

Un subspatiu V se numeste ciclic daca orice vector v'_i din V se obtine dintr-un alt vector v_i din V, prin deplasarea ciclica (la stanga sau la dreapta) a componentelor acestuia cu k pozitii, unde 1 < k < n-1.

Un cod ce contine numai secvente dintr-un spatiu ciclic se numeste cod ciclic.

5. ALGORITMI SI SCHEME DE CODIFICARE PENTRU REALIZAREA CODURILOR CICLICE

Consideram un mesaj informational M ce contine un numar oarecare de biti. Acest mesaj este emis de o sursa si urmeaza a fi transmis printr-un canal catre un receptor. Pentru ca receptorul sa posede un criteriu de depistare a erorilor, mesajul M trece inainte de a intra in canal printr-un codificator care stabileste criteriul de verificare, introducand simboluri redundante. Aceasta schema clasica de protectie a informatiei transmise prin canale perturbate cunoaste de la caz la caz forme specifice in functie de modelul matematic ales pentru realizarea codificarii redundante.

In cazul codurilor polinomial ciclice mesajul M se reprezinta mai intai ca un polinom M(x) in nedeterminata x si apoi printr-un algoritm de codificare se transforma intr-un alt polinom T(x), astfel incat T(x) sa fie multiplu al unui polinom dat G(x), denumit polinom de generare. Polinomul G(x) este o constanta a codificarii, prin intermediul careia multimea mesajelor M(x) emise de sursa devine inzestrata cu o proprietate comuna, aceea ca toate elementele sale sunt divizibile prin G(x). Decodificatorul cunoaste polinomul de generare si va putea sa verifice pentru orice mesaj receptionat T'(x), daca acesta mai pastreaza proprietatea de divizibilitate prin G(x). Pe baza acestui test se depisteaza erorile si se valideaza mesajele receptionate.

Sarcina codificatorului intr-o codificare polinomial-ciclica este de a transforma multimea polinoamelor asociate mesajelor emise de sursa M(x) intr-o alta multime de polinoame T(x), care satisface relatia T(x)' este multiplu de G(x)'.

Exista 2 tipuri de algoritmi prin care codificatorul poate realiza transformarea ceruta: algoritmul de inmultire si cel de impartire. Primul consta in inmultirea lui M(x) cu G(x), rezultand T(x) care este evident multiplu de G(x) astfel incat algoritmul se descrie prin relatia simpla:

T(x) = M(x) * G(x), cu mentiunea ca operatiile de inmultire si adunare ale coeficientilor polinoamelor se face modulo 2.

Algoritmul de codificare prin impartire comporta urmatoarele etape:

1. Pornind de la un mesaj ce contine k biti informationali, se asociaza acestuia un polinom

2. Se alege un polinom G(x) de grad r drept polinom generator al codului:

3. Se inmulteste M(x) cu , rezultand un nou polinom M'(x) deplasat cu r pozitii catre stanga si avand in cele r pozitii mai putin semnificative inscrise zerouri

4. Se imparte M'(x) la G(x) rezultand un polinom cat Q(x) si un polinom rest R(x) de grad r-1. Coeficientii polinomului R(x) constituie simbolurile de control aferente mesajului informational reprezentat prin polinomul asociat M(x).

5. Se aduna M'(x) cu R(x) si se obtine un polinom T(x) care contine in zona pozitiilor semnificative cele k simboluri informationale, iar pe pozitiile mai putin semnificative cele r simboluri de control. Acest polinom reprezinta prin coeficientii sai un mesaj codificat redundant, de lungime n, din care r sunt simboluri de control.

Impartirea polinoamelor se efectueaza in algebra obisnuita cu deosebirea ca adunarea si inmultirea coeficientilor se face modulo 2.

Implementarea hard se face folosind registre de deplasare si porti SAU-EXCLUSIV.

Ex: date - 10110

Schema hard va fi urmatoarea:

Se obtine urmatorul tabel:

Initial toate registrele sunt in starea 0, iar la intrarea circuitul se introduce M'(x) bit cu bit. In final se obtine in registre(ultima linie din tabel) valoarea restului.

APLICATIE: Sa se implementeze un algoritm care pentru un mesaj dat determina codificarea polinomial-ciclica a acestuia cu ajutorul unui polinom de generare. Se va folosi algoritmul impartirii.