Coduri corectoare de erori (1)pe lng fiecare bloc de date trimis se include suficient informaie redundant pentru ca receptorul s poat deduce care a fost caracterul transmis coduri corectoare de erori ( corectare de erori n avans forward error correction );

se include suficient redundan pentru a permite receptorului s constate c a aprut o eroare, dar nu care este eroarea, i s cear o retransmisie coduri detectoare de erori;

pe canale cu siguran mare - cod detector de erori i retransmiterea blocului n care s-au detectat erori;

pe canale nesigure ( comunicaie fr fir ) coduri corectoare de erori;

Coduri corectoare de erori (2)n cuvnt de cod de n bii ( n-bit codeword );n = m + r; m bii de date ( mesaj )r bii redundani sau de control

10001001 OR EXCLUSIV1011000100111000 distan Hamming

Obs. Numrul de poziii binare n care dou cuvinte de cod difer distan Hemming; dac dou cuvinte de cod sunt desprite de o distan Hemming d, sunt necesare d erori de un singur bit pentru a-l converti pe unul n cellat.

Coduri corectoare de erori (3)

pentru a detecta d erori este nevoie de un cod cu distana d+1, deoarece cu un asemenea cod nu exist nici o modalitate ca d erori de un singur bit s poat modifica un cuvnt de cod corect ntr-un alt cuvnt de cod corect;

pentru a corecta d erori este nevoie de un cod cu distana 2d+1, deoarece n acest mod cuvintele de cod corecte sunt att de distanate, nct, chiar cu d modificri, cuvntul de cod originar este totui mai apropiat dect alte cuvinte de cod i va fi unic determinat;

Coduri corectoare de erori (4)

Exemple:

Cod detector de erori: adugarea la date a unui bit de paritate un cod cu un singur bit de paritate are distana 2, deoarece orice eroare pe un singur bit produce un cuvnt de cod cu paritatea greit ( poate fi folosit pentru detectarea erorilor singulare );

Cod corector de erori: fie un cod cu patru cuvinte de cod corecte:0000000000, 0000011111, 1111100000 i 1111111111; codul are distana 5 i poate corecta erori duble; dac sosete cuvntul de cod 0000000111, cel ce recepioneaz tie c originalul trebuie s fi fost 0000011111; dac totui o eroare tripl modific 0000000000 n 0000000111, eroarea nu va fi corectat corespunztor;

Coduri corectoare de erori (5)Proiectarea unui cod cu m bii de mesaj i r bii de control pentru corectarea tuturor erorilor singulare ( 1 ):

pentru fiecare din cele 2m mesaje corecte exist n cuvinte de cod eronate, aflate la distana 1 de el; acestea sunt formate prin inversarea sistematic a fiecruia dintre cei n bii din cuvntul de cod de n bii format din el; astfel, fiecare din cele 2m mesaje corecte necesit n+1 abloane asociate;

cum numrul total de abloane este 2n, trebuie s avem (n+1)2m

Coduri corectoare de erori (6)Proiectarea unui cod cu m bii de mesaj i r bii de control pentru corectarea tuturor erorilor singulare ( 2 ):

atingerea limitei inferioare amintite ( Hamming ): biii cuvntului de cod sunt numerotai consecutiv, ncepnd cu bitul 1 de la marginea din stnga, bitul 2 imediat la dreapta sa .a.m.d. Biii care sunt puteri ale lui 2 ( 1, 2, 4, 8 etc.) sunt bii de control; restul ( 3, 5, 6, 7, 9 etc. ) sunt completai cu cei m bii de date; fiecare bit de control foreaz ca paritatea unui grup de bii, inclusiv el nsui, s fie par ( sau impar );

-un bit poate fi inclus n mai multe calcule de paritate; pentru a se vedea la care bii de control contribuie bitul de date din poziia k, se rescrie k ca o sum de puteri ale lui 2 ( ex: 11=1+2+8 ); un bit este verificat de acei bii de control care apar n dezvoltarea sa ( ex: bitul 11 este verificat de biii 1, 2 i 8 );

Coduri corectoare de erori (7)Proiectarea unui cod cu m bii de mesaj i r bii de control pentru corectarea tuturor erorilor singulare ( 3 ):

cnd sosete un cuvnt de cod, receptorul iniializeaz un contor la 0; acesta examineaz apoi fiecare bit de control k ( k=1, 2, 4, 8) pentru a vedea dac are paritatea corect; dac nu, adaug k la contor;

dac, dup ce au fost examinai toi biii de control, contorul este 0 ( adic dac toi biii au fost coreci ), cuvntul de cod este acceptat ca valid;

dac valoarea contorului este nenul, ea reprezint numrul bitului incorect ( ex: dac biii de control 1, 2 i 8 sunt eronai, atunci bitul inversat este 11, deoarece este singurul verificat de biii 1, 2 i 8 );

Coduri corectoare de erori (8)Caractere ASCII pe 7 bii codificate prin cuvinte de cod pe 11 bii, utliznd codul Hamming

Coduri corectoare de erori (9)informaia este regsit n biii de pe poziiile 3, 5, 6, 7, 9, 10 i 11;codurile Hamming pot corecta doar erori singulare;artificiu pentru a permite codurilor Hamming s corecteze erorile n rafal:

o secven de k cuvinte de cod consecutive este aranjat ca o matrice, avnd cte un cuvnt de cod pe fiecare linie; n mod normal, datele sunt transmise linie cu linie, de la stnga la dreapta; pentru a corecta erorile n rafal, datele vor trebui transmise pe coloane, ncepnd cu coloana cea mai din stnga; cnd au fost trimii toi cei k bii, este transmis a doua coloan i aa mai departe ( figura din slide-ul anterior ); atunci cnd un cadru ajunge la receptor , matricea este reconstruit, coloan cu coloan;

dac a aprut o eroare n rafal, de lungime k, va fi afectat cel mult un bit din fiecare dintre cele k cuvinte de cod, dar codul Hamming poate corecta o eroare pe cuvnt de cod, astfel c ntregul bloc poate fi refcut;

metoda utilizeaz kr bii de control pentru a face blocuri de km bii de date imune la erorile n rafal de lungime k sau mai mic.

Coduri corectoare de erori (1)

dac unui bloc i se adaug un singur bit de paritate i blocul e puternic deformat de o eroare n rafal lung, probabilitatea ca eroarea s fie detectat este de numai 0.5; ansele pot fi mbuntite dac fiecare bloc transmis este privit ca o matrice dreptunghiular de n bii lime i k bii nlime ; pentru fiecare coloan e calculat un bit de paritate, care este adugat ntr-o nou linie de la sfritul matricei. Matricea este apoi transmis linie cu linie; la sosirea blocului, receptorul verific toi biii de paritate; dac oricare idn ei e greit, va cere o retransmisie a blocului;

dac este nevoie, sunt cerute retransmisii succesive, pn cnd ntregul bloc este recepionat fr erori de paritate;

Coduri corectoare de erori (2)metoda anterioar poate detecta o singur rafal de lungime n, cu numai un bit pe coloana modificat;

o rafal de lungime n+1 va trece nedetectat dac primul i ultimul bit sunt inversai, iar toi ceilali bii sunt coreci ( o eroare n rafal nu nseamn c toi biii sunt greii, ci c cel puin primul i ultimul sunt greii );

dac blocul e puternic deformat de o rafal lung sau de rafale scurte multiple, probabilitatea ca oricare din cele n coloane s aib, accidental, paritatea corect este 0.5, deci probabilitatea ca un bloc eronat s fie acceptat atunci cnd nu ar trebui este 2-n;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (1)bazate pe tratarea irurilor de bii ca reprezenatri de polinoame cu coeficieni 0 i 1;

un cadru de k bii e vzut ca o list de coeficieni pentru un polinom cu k termeni, de la xk-1 la x0 polinom de gradul k-1;

bitul cel mai semnificativ e coeficientul lui xk-1;

ex: 110001 reprezint polinomul x5 + x4 + x0 ( coeficienii sunt 1, 1, 0, 0, 0 i 1 );

aritmetica polinomial este de tip modulo 2;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (2)nu exist transport la adunare i nici mprumut la scdere ( adunrile i scderile sunt identice cu SAU EXCLUSIV );

ex: 10011011001100111111000001010101 +11001010 +11001101 -10100110 -10101111 01010001 11111110 01010110 11111010

scderea este realizat modulo 2;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (3)emitorul i receptorul se pun de acord n avans asupra unui polinom generator G(x);

bitul cel mai semnificativ i cel mai puin semnificativ trebuie s fie 1;

pentru a calcula suma de control pentru un cadru cu m bii, corespunztor polinomului M(x), cadrul trebuie s fie mai lung dect polinomul generator;

se adaug o sum de control la sfritul cadrului, astfel nct polinomul reprezentat de cadrul cu sum de control s fie divizibil prin G(x);

cnd receptorul preia cadrul cu suma de control, ncearc s-l mpart la G(x); dac se obine un rest, nseamn c a avut loc o eroare de transmisie;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (4)Algoritmul pentru calculul sumei de control:

fie r gradul lui G(x); se adaug r bii la captul mai puin semnificativ al cadrului, aa nct acesta va conine acum n+r bii i va corespunde polinomului xrM(x);

se mparte irul de bii ce corespund lui G(x) ntr-un ir de bii corespunznd lui xrM(x), utiliznd mprirea modulo 2;

se scade restul ( care are ntotdeauna r sau mai puini bii ) din irul de bii corespunznd lui xrM(x), utiliznd scderea modulo 2. Rezultatul este cadrul cu sum de control ce va fi transmis. Polinomul su va fi T(x).

Obs. T(x) este divizibil (modulo 2) cu G(x).

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (5)

Calculul sumei de control n cod polinomial pentru cadrul 1101011011 i G(x) = x4+x+1

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (6)-apariia unei erori de transmisie: n loc s soseacs irul de biipentru T(x), ajunge T(x) + E(x); fiecare bit din E(x) corespunde unui bit care a fost inversat; dac n E(x) exist k bii 1, aceasta nseamn c au aprut k erori de un singur bit;

-o singur eroare n rafal este caracterizat de un 1 iniial, un amestec de 0 i 1 i un 1 final, toi ceilali bii fiind 0;

-la recepia cadrului cu sum de control, receptorul l mparte prin G(x); nseamn c se va calcula [T(x) + E(x)] / G(x); T(x) / G(x) este 0, aa nct rezultatul calculului este E(x) / G(x); acele erori care se ntmpl s corespund unor polinoame care l au ca factor pe G(x) vor scpa; toate celelalte vor fi detectate;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (7)-dac a aprut o eroare pe un singur bit, E(x)=xi, unde i determin care bit este eronat; dac G(x) conine doi sau mai muli termeni, nu poate fi divizor al lui E(x), aa nct toate erorile pe un singur bit vor fi detectate;

-dac au aprut dou erori izolate pe un singur bit, atunci E(x)=xi + xj, unde i>j; dac presupunem c G(x) nu este divizibil prin x, o condiie suficient pentru detectarea erorilor duble este ca G(x) s nu se divid prin xk+1 pentru orice k pn la valoarea maxim i-j ( adic pn la lungimea maxim a cadrului );

-sunt cunoscute polinoame simple, de grad mic, care asigur protecie cadrelor de lungime mare ( ex: x15+x14+1 nu se va divide cu xk+1 pentru nici o valoare a lui k mai mic de 32768 );

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (8)

-dac exist un numr impar de bii eronai, E(x) conine un numr impar de termeni ( adic x5+x2+1, dar nu x2+1 );

-n sistemul modulo 2 nu exist nici un polinom cu numr impar de termeni care s l aib pe x+1 ca factor; fcndu-l pe x+1 factor al lui G(x), se vor putea depista toate erorile constituite dintr-un numr impar de bii inversai;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (9)Nici un polinom cu numr impar de termeni nu este divizibil cu x+1.

Demonstraie:

presupunem c E(x) are un numr impar de termeni i este divizibil cu x+1; se factorizeaz n (x+1)Q(x);

se evalueaz E(1)=(1+1)Q(1); deoarece 1+1=0(modulo 2), E(1) trebuie s fie 0;

dac E(x) are un numr impar de termeni, substituind fiecare x cu 1, rezultatul obinut va fi ntotdeauna 1; rezult c nici un polinom cu numr impar de termeni nu este divizibil cu x+1;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (10)-un cod polinomial cu r bii de control va detecta toate erorile n rafal de lungime r;

-o eroare n rafal de lungime k poate fi reprezentat de xj(xk-1+..+1), unde i determin ct de departe este localizat rafala fa de captul din dreapta al cadrului recepionat;

-dac G(x) conine termenul x0, atunci nu l va avea ca factor pe xj, aa c dac gradul expresiei dintre paranteze este mai mic dect gradul lui G(x), restul nu poate fi niciodat 0;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (11)

-dac lungimea rafalei este r+1, restul mpririi cu G(x) va fi zero dac i numai dac rafala este identic cu G(x);

-prin definiia rafalei, primul i ultimul bit trebuie s fie 1, astfel c potrivirea depinde de cei r-1 bii intermediari;

-dac toate combinaiile sunt privite ca egal posibile, atunci probabilitatea ca un cadru incorect s fie acceptat ca valid este 1/2r-1;

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (12)

Polinomul folosit n IEEE 802:

x32 + x26 + x23 + x22 + x16 + x12 + x11 + + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1

Coduri corectoare de erori -coduri polinomiale ( coduri cu redundan ciclic ) (13)

-n practic, pentru calcularea i verificarea sumei de control se utilizeaz un simplu registru de deplasare ( circuitul este folosit n aproape toate reelele locale, i uneori i n cazul liniilor punct-la-punct );

-analize recente au artat c presupunerea conform creia cadrele pentru care se calculeaz suma de control conin bii aleatori este incorect; ca o consecin, n unele circumstane, erorile nedetectate sunt mult mai obinuite dect s-a crezut anterior;