Coduri corectoare de erori (1) [608235]

Coduri corectoare de erori (1)
-pe lângă fiecare bloc de date trimis se include suficientă
informație 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 apărut 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 ( comunicație fără fir ) – coduri corectoare de
erori;

Coduri corectoare de erori (2)
n – cuvânt de cod de n biți ( n-bit codeword );
n = m + r;
m – biți de date ( mesaj )
r – biți redundanți sau de control
10001001 OR EXCLUSIV
10110001
00111000
distanță Hamming
Obs. Numărul de poziții binare în care două cuvinte de cod diferă
– distanță Hemming ; dacă două cuvinte de cod sunt despărțite de
o distanță Hemming d, sunt necesare d erori de un singur bit
pentru a-l converti pe unul în celălat.

Coduri corectoare de erori ( 3)
-pentru a detecta d erori este nevoie de un cod cu distanța d+1,
deoarece cu un asemenea cod nu exist ă nici o modalitate ca d
erori de un singur bit s ă poată modifica un cuv ânt de cod corect
într-un alt cuvânt de cod corect ;
-pentru a corecta d erori este nevoie de un cod cu distanța 2d+1,
deoarece în acest mod cuvintele de cod corecte sunt atât de
distanțate, încât, chiar cu d modificări, cuvântul de cod originar
este totuși mai apropiat decât alte cuvinte de cod și va fi unic
determinat ;

Coduri corectoare de erori (4)
Exemple:
Cod detector de erori : adăugarea la date a unui bit de paritate – un cod
cu un singur bit de paritate are distanța 2, deoarece orice eroare pe un
singur bit produce un cuvânt de cod cu paritatea greșită ( 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 distan ța
5 și poate corecta erori duble ; dacă sosește cuvântul de cod 0000000111,
cel ce recepționează știe că originalul trebuie să fi fost 0000011111 ; dacă
totuși o eroare triplă modifică 0000000000 în 0000000111, eroarea nu va
fi corectată corespunzător ;

Coduri corectoare de erori ( 5)
Proiectarea unui cod cu m biți de mesaj și r biți de control pentru
corectarea tuturor erorilor singulare ( 1 ):
-pentru fiecare din cele 2m mesaje corecte exist ă n cuvinte d e cod
eronate, aflate la distanța 1 de el ; acestea sunt formate prin inversarea
sistematică a fiecăruia dintre cei n biți din cuvântul de cod de n biți format
din el; astfel, fiecare din cele 2m mesaje corecte necesită n+1 șabloane
asociate;
-cum numărul total de șabloane este 2n, trebuie să avem (n+1)2m<=2n;
utilizând n=m+r, această condiție devine (m+r+1)<=2r; dându-se m,
acesta impune o limită inferioară asupra numărului de biți de control
necesari pentru a corecta erorile singulare ;m2

Coduri corectoare de erori (6)
Proiectarea unui cod cu m biți de mesaj și r biți de control pentru
corectarea tuturor erorilor singulare ( 2 ):
-atingerea limitei inferioare amintite ( Hamming ) : biții cuvântului de cod
sunt numerotați consecutiv, începând cu bitul 1 de la marginea din
stânga, bitul 2 imediat la dreapta sa ș.a.m.d. Biții care sunt puteri ale lui 2
( 1, 2, 4, 8 etc.) sunt biți de control ; restul ( 3, 5, 6, 7, 9 etc. ) sunt
completați cu cei m biți de date ; fiecare bit de control forțează ca
paritatea unui grup de biți, inclusiv el însuși, să fie pară ( sau impară ) ;
-un bit poate fi inclus în mai multe calcule de paritate ; pentru a se vedea
la care biți de control contribuie bitul de date din poziția k, se rescrie k ca
o sumă de puteri ale lui 2 ( ex : 11=1+2+8 ); un bit este verificat de acei
biți de control care apar în dezvoltarea sa ( ex : bitul 11 este verificat de
biții 1, 2 și 8 ) ;

Coduri corectoare de erori (7)
Proiectarea unui cod cu m biți de mesaj și r biți de control pentru
corectarea tuturor erorilor singulare ( 3 ):
-când sosește un cuvânt de cod, receptorul inițializează 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 examinați toți biții de control, contorul este 0
( adică dacă toți biții au fost corecți ), cuvântul de cod este acceptat ca
valid;
-dacă valoarea contorului este nenulă, ea reprezintă numărul bitului
incorect ( ex : dacă biții de control 1, 2 și 8 sunt eronați, atunci bitul
inversat este 11, deoarece este singurul verificat de biții 1, 2 și 8 ) ;

Coduri corectoare de erori (8)
Caractere ASCII pe 7 bi ți codificate prin cuvinte
de cod pe 11 biți, utlizând codul Hamming

Coduri corectoare de erori ( 9)
-informația este regăsită în biții de pe pozițiile 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, având
câte un cuvânt de cod pe fiecare linie ; în mod normal, datele sunt transmise linie
cu linie, de la stânga la dreapta ; pentru a corecta erorile în rafală, datele vor trebui
transmise pe coloane, începând cu coloana cea mai din stânga ; când au fost
trimiși toți cei k biți, este transmisă a doua coloană și așa mai departe
( figura din slide-ul anterior ) ; atunci când un cadru ajunge la receptor , matricea
este reconstruită, coloană cu coloană ;
-dacă a apărut 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
cuvânt de cod, astfel că întregul bloc poate fi refăcut ;
-metoda utilizează kr biți de control pentru a face blocuri de km biți 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
îmbunătățite dacă fiecare bloc transmis este privit ca o matrice
dreptunghiulară de n biți lățime și k biți înălțime ; pentru fiecare
coloană e calculat un bit de paritate, care este adăugat într-o nouă
linie de la sfârșitul matricei. Matricea este apoi transmisă linie cu
linie; la sosirea blocului, receptorul verifică toți biții de paritate ;
dacă oricare idn ei e greșit, va cere o retransmisie a blocului ;
-dacă este nevoie , sunt cerute retransmisii succesive, până când
întregul bloc este recepționat fără erori de paritate ;

Coduri corectoare de erori (2)
-metoda anterioa ră 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 inversați, iar toți ceilalți biți sunt corecți ( o eroare în
rafală nu înseamnă că toți biții sunt greșiți, ci că cel puțin primul și
ultimul sunt greșiți ) ;
-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 când nu ar trebui est e 2-n;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (1)
-bazate pe tratarea șirurilor de biți ca reprezenatări de polinoame
cu coeficienți 0 și 1 ;
-un cadru de k biți e văzut ca o list ă de coeficienți 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 ( coeficienții sunt 1,
1, 0, 0, 0 și 1 ) ;
-aritmetica polinomial ă este de tip modulo 2;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (2)
-nu există transport la adunare și nic i împrumut la scădere
( adunările și scăderile sunt identice cu SAU EXCLUSIV ) ;
-ex: 10011011 00110011 11110000 01010101
+11001010 +11001101 -10100110 -10101111
01010001 11111110 01010110 11111010
-scăderea este realizată modulo 2 ;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (3)
-emițătorul și receptorul se pun de acord în avans asupra unui polinom
generator G(x) ;
-bitul cel mai semnificativ și cel mai puțin semnificativ trebuie să fie 1 ;
-pentru a calcula suma de control pentru un cadru cu m biți,
corespunzător polinomului M(x), cadrul trebuie să fie mai lung decât
polinomul generator ;
-se adaugă o sumă de control la sfârșitul cadrului, astfel încât polinomul
reprezentat de cadrul cu sumă de control să fie divizibil prin G(x);
-când receptorul preia cadrul cu suma de control, încearcă să-l împartă la
G(x); dacă se obține un rest, înseamnă că a avut loc o eroare de
transmisie ;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (4)
Algoritmul pentru calculul sumei de control:
1. fie r gradul lui G(x); se adaugă r biți la capătul mai puțin
semnificativ al cadrului, așa încât acesta va conține acum n+r
biți și va corespunde polinomului xrM(x);
2.se împarte șirul de biți ce corespund lui G(x) într-un șir de biți
corespunzând lui xrM(x), utilizând împărțirea modulo 2 ;
3.se scade restul ( care are întotdeauna r sau mai puțini biți ) din
șirul de biți corespunzând lui xrM(x), utilizând scăderea modulo
2. Rezultatul este cadrul cu sumă de control ce va fi transmis.
Polinomul său va fi T(x).
Obs. T(x) este divizibil (modulo 2) cu G(x).

Coduri corectoare de erori –
coduri polinomial e ( 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 polinomial e ( coduri cu redundanță ciclică ) (6)
-apariția unei erori de transmisie : în loc să soseacsă șirul de biți
pentru 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 biți 1, aceast a înseamnă
că au apărut k erori de un singur bit ;
-o singură eroare în rafală este caracterizată de un 1 inițial, un
amestec de 0 și 1 și un 1 final, toți ceilalți biți fiind 0 ;
-la recepția 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, așa încât rezultatul calculului este E(x) / G(x) ; acele erori care se
întâmplă să corespundă unor polinoame care îl au ca factor pe G(x)
vor scăpa; toate celelalte vor fi detectate ;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (7)
-dacă a apărut o eroare pe un singur bit, E(x)=xi, unde i determină
care bit este eronat ; dacă G(x) conține doi sau mai mulți termeni, nu
poate fi divizor al lui E(x), așa încât toate erorile pe un singur bit vor
fi detectate ;
-dacă au apărut 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
condiție suficientă pentru detectarea erorilor duble este ca G(x) să
nu se dividă prin xk+1 pentru orice k până la valoarea maximă i-j
( adică până la lungimea maximă a cadrului ) ;
-sunt cunoscute polinoame simple, de grad mic, care asigur ă
protecție 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 polinomial e ( coduri cu redundanță ciclică ) (8)
-dacă există un număr impar de biți eronați, E(x) conține un număr
impar de termeni ( adică x5+x2+1, dar nu x2+1 );
-în sistemul modulo 2 nu există nici un polinom cu număr impar de
termeni care să îl aibă pe x+1 ca factor; făcându-l pe x+1 factor al
lui
G(x), se vor putea depista toate erorile constituite dintr-un număr
impar de biți inversați ;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (9)
Nici un polinom cu număr impar de termeni nu este divizibil cu x+1.
Demonstra ție:
-presupunem c ă E(x) are un număr 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 număr impar de termeni, substituind fiecare x
cu 1, rezultatul obținut va fi întotdeauna 1; rezultă că nici un
polinom cu număr impar de termeni nu este divizibil cu x+1;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (10)
-un cod polinomial cu r biți 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ă cât de departe este localizată rafala față de capătul
din dreapta al cadrului recepționat ;
-dacă G(x) conține termenul x0, atunci nu îl va avea ca factor pe xj,
așa că dacă gradul expresiei dintre paranteze este mai mic decât
gradul lui G(x), restul nu poate fi niciodată 0;

Coduri corectoare de erori –
coduri polinomial e ( coduri cu redundanță ciclică ) (11)
-dacă lungimea rafalei este r+1, restul împărțirii cu G(x) va fi zero
dacă și numai dacă rafala este identică cu G(x);
-prin definiția rafalei, primul și ultimul bit trebuie să fie 1, astfel că
potrivirea depinde de cei r-1 biți intermediari ;
-dacă toate combinațiile 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 polinomial e ( 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 polinomial e ( 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 rețelele locale, și uneori și în cazul liniilor punct-la-
punct );
-analize recente au arătat că presupunerea conform căreia cadrele
pentru care se calculează suma de control conțin biți aleatori este
incorectă; ca o consecință, în unele circumstanțe, erorile nedetectate
sunt mult mai obișnuite decât s-a crezut anterior ;