L4 - Platforma

Lucrarea nr. 4. Coduri grup Hamming extins (8,4,4) 1. Obiectivul lucrarii Aceasta lucrare studiaza procesul de codare, respectiv decodare, cu ajutorul codului Hamming grup H(8,4), punând în evidenta modalitatea de corectie a unei erori sau de detectie a doua erori.

2. Introducere teoretica Unul din codurile grup cele mai cunoscute este codul Hamming H(n,k ) corector de o eroare, la care coloana h j a matricei de control H este reprezentarea binara a numarului j , daca eroarea este singulara. Codul Hamming are urmatorii parametrii: • lungime: n = 2m-1; • numar simboluri de informatie: k = 2m -m-1; • numar simboluri de control: m = n - k; • distanta minima: d min= 3; • numar erori corectabile: t = 1. Codul Hamming este singurul cod grup perfect corector de o eroare. Acest cod este nesistematic, respectiv pozitiile de control sunt 21 , 22 , …,2m-1, corespunzând unor vectori coloana din matricea de control H cu o singura pozitie diferita de 0, ceea ce usureaza determinarea simbolurilor de control din relatia: HvT = 0. Daca, pe lânga corectia unei erori, trebuie sa se asigure si detectia erorilor duble, se transforma codul Hamming corector de o eroare (Single -Error Correcting: SEC) într-un cod Hamming corector de o eroare si detector de erori duble (Single-Error Correcting and Double-Error Detecting: SEC-DED). Distanta minima a unui cod care corecteaza t erori si simultan detecteaza l erori ( l > t), trebuie sa fie cel putin l + t + 1: d min ≥ t + l + 1 . Deci, t = 1, l = 2 ⇒ d min ≥ 1 + 2 + 1 = 4 . Asadar, distanta minima a codului trebuie crescuta cu o unitate. Aceasta se poate realiza în doua moduri: utilizând un cod Hamming extins sau un cod Hamming prescurtat. Pentru a obtine un cod Hamming extins se bordeaza matricea de control H a codului Hamming initial cu o coloana de "0" la stânga si cu o linie de "1" în partea inferioara:

[

]

0 H h0 h1 h2 h3 h4 h5 h6 h7  H = =  = h0 h1 h2 h3 h4 h5 h6 h7 . 1 1   1 1 1 1 1 1 1 1  Matricea de control H va avea m = m+1 linii si n = n+1 coloane, de unde rezulta C(n+1,k). Deci lungimea cuvântului de cod va creste cu o unitate, care corespunde introducerii unui bit de control suplimentar, pe prima pozitie din stânga. Exemplu: codul C(7,4). Structura unui cuvânt de cod va fi acum:

v = [c0 c1 c2 i3

c4

i5 i6 i7 ] ,

iar relatia matriceala de codare pentru codul extins C(8,4): H ⋅vT = 0

45

va conduce la urmatoarele ec uatii de codare:

0 0  0  1

0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1

c 0  c   1 1 c2   c4 = i5 + i6 + i7    c = i + i + i 1  i3   2 3 6 7 ⋅ = 0⇒  1 c4  .  c1 = i3 + i5 + i7     c0 = c1 + c2 + i3 + c4 + i5 + i6 + i7 = i3 + i5 + i6 1  i5   i6     i7 

Se observa ca bitul de control suplimentar c0 este suma modulo 2 a tuturor celorlalti biti din cuvântul de cod. De aceea el se numeste simbol de control al paritatii, sau, pe scurt, bit de paritate. Se poate arata us or ca acest bit de paritate creste distanta minima a codului cu o unitate. Exemplu: i = [i3

i5

i6

i = [i3

i5

i6

c4 = 0  w( v ) = 3 c2 = 1 i7 ] = [0 1 0 1] ⇒  ⇒ v = [1 0 1 0 0 1 0 1];   w( v ) = 4 c1 = 0 c0 = 1 . c4 = 0 c = 0 w( v ) = 4   2 i7 ] = [1 1 0 1] ⇒  ⇒ v = [0 1 0 1 0 1 0 1];   w( v ) = 4  c1 = 1 c0 = 0

În cazul cuvintelor de cod care initial aveau ponderea w(v) = dmin = 3, bitul de paritate este 1, deci w(v) = 4. În cazul cuvintelor de cod care initial aveau ponderea w(v) = d min+1 = 4, bitul de paritate este 0, deci w(v) = 4. Asadar, distanta minima a codului Hamming extins este dmin= 4. În general, prin adaugarea bitului de paritate, ponderea cuvintelor de cod care initial aveau un numar impar de "1" creste cu o unitate, iar ponderea cuvintelor de cod care initial aveau un numar par de "1" ramâne neschimbata. La decodare, corectorul calculat va avea acum 4 pozitii:

 s3  s  s T T s = H r = H e =  2 =   .  s1  s0     s0  Daca a aparut un numar impar de erori, atunci corectorul s va consta din suma modulo 2 a unui numar impar de coloane din matricea H, de tipul: h  hi =  i  , 1

46

deci pe ultima pozitie a corectorului se va afla bitul s0 = 1. Daca a aparut un numar par de erori, atunci corectorul s va consta din suma modulo 2 a unui numar par de coloane din matricea H, de acelasi tip: h  hi =  i  , 1 deci pe ultima pozitie a corectorului se va afla bitul s0 = 0. Simbolul s0 va fi, prin urmare, un indice de recunoastere a prezentei erorilor duble, care va împiedica o falsa corectie. În aceasta situatie, decodarea se va efectua conform urmatoarelor reguli: • daca s = 0 si s0 = 0, decizia va fi : nu au aparut erori (r = v); • daca s ≠ 0 si s0 = 1, decizia va fi: a aparut o eroare corectabila; • daca s ≠ 0 si s0 = 0, decizia va fi: au aparut doua erori necorectabile; • daca s = 0 si s0 = 1, decizia va fi: a fost eronat bitul de paritate. Exemplu: C(7,4) ⇒ C(8,4). Fie

v = [0 1 0 1 0 1 0 1] . 0  0  0 1 0  1  1 0 T r = [0 1 0 1 0 0 0 1] ⇒ s = H r = h1 + h3 + h 7 =   +   +   =   ⇒ s0 = 1 1  1  1 1         1  1  1 1 ⇒a aparut o eroare corectabila pe pozitia data de: 1  s = 0  = h5 ⇒ i = 5 ⇒ e = [0 0 0 0 0 1 0 0 ]   1 

⇒ v* = r + e = [0 1 0 1 0 0 0 1] + [0 0 0 0 0 1 0 0] = = [0 1 0 1 0 1 0 1] = v

0  1 1 0  1 1 T r = [0 1 0 0 0 0 0 1] ⇒ s = H r = h1 + h7 =   +   =   1  1 0      1  1 0 s0 = 0 ⇒

⇒au aparut doua erori necorectabile, dar detectabile. Pentru a obtine un cod Hamming sistematic s-au permutat coloanele matricei de control H, obtinîndu-se matricea H : 0 0 H = 0 1 

1 0 0 1 0 1 1 0 1 0 1 1 1 0  0 0 1 0 1 1 1 . 1 1 1 1 1 1 1 

47

Din relatia:

 c1 = i0 + i2 + i3 c = i + i + i T  Hv =0 ⇒  2 0 1 2,  c3 = i1 + i2 + i3  c4 = i0 + i1 + i3 se obtin ecuatiile de codare pentru forma sistematica.

3. Descrierea evolutiei programului Programul de simulare a codului Hamming SEC-DED poate fi apelat sub numele "hamming.exe". Dupa lansarea în executie, pe ecran va apare urmatorul meniu: • Introducere teoretica • Codare • Transmisie • Decodare • eXit. Aceste etape pot fi selectate cu ajutorul tastelor " I", "C","T ","D" si "X". Pentru vizualizarea introducerii teoretice se apasa tasta I. Parcurgerea în totalitate a introducerii se face prin apasarea oricarei taste, pentru pagina urmatoare. În etapa de codare se ajunge apasând tasta C. În acest moment apar pe ecran, în afara de meniu, alte doua cadre: "evolutia datelor în lantul de transmisiune" (1) si "datele initiale" (2). În cadrul (1) va fi afisata, pe parcursul derularii programului, modificarea datelor ce sunt transmise. În cadrul (2) vor fi introdusi de la tastatura cei patru biti de informatie, respectiv I0 I1 I2 I3. Daca se vor introduce alte simboluri decât cele binare, pe ecran va apare mesajul: "comanda eronata". Dupa introducerea celor patru biti de informatie ceruti, pe ecran va fi afisata schema de codare pentru C(8,4). La intrarea acestei scheme se vor afla înscrisi cei patru biti introdusi de la tastatura. Acesti biti vor intra în schema prin apasarea de 4 ori a oricarei taste. Se observa ca pe timpul introducerii bitilor de informatie, comutatorul K este pe pozitia 1, bitii fiind afisati si la iesirea schemei.

Fig. 1. Schema de codare a codului Hamming SEC-DED.

48

La apasarea celei de a cincea taste, comutatorul K va trece pe pozitia 2 si bitii de control C0 C1 C2 C 3 vor fi calculati si afisati. Acestia vor fi trecuti la iesirea codorului prin apasarea succesiva a înca patru taste. Dupa ce s-a terminat codarea, la iesirea schemei se afla cuvântul de cod v = C0 C1 C2 C 3 I0 I 1 I2 I3 transmis. Acest cuvânt va fi înscris, dupa apasarea unei noi taste, în cadrul (1). Pentru a trece la etapa transmisie se apasa tasta T. Pe ecran va aparea un nou cadru: "erori de transmisie" (3), unde va fi introdus de la tastatura cuvântul eroare. Dupa introducerea celui de-al 8-lea bit al cuvântului eroare, pe ecran va fi afisata schema bloc a lantului de transmisiune, care la intrare va avea cuvântul de cod v = C 0 C1 C2 C3 I0 I 1 I2 I3 , cuvânt de cod care va fi adunat modulo 2 cu cuvântul eroare e, iar la iesirea acesteia va fi înscris cuvântul receptionat r. Prin apasarea unei noi taste se observa ca în cadrul (1) a fost înscris cuvântul receptionat r.

Fig. 2. Schema bloc a lantului de transmisiune pentru codul Hamming SEC-SED.

Pentru a urmari etapa de decodare se apasa tasta D, iar pe ecran va fi afisa ta schema de decodare pentru C(8,4). La intrarea schemei vor fi înscrisi bitii receptionati, care se introduc în schema prin apasarea succesiva a 8 taste. În cazul în care cuvântul a fost transmis cu o eroare, la iesirea schemei va fi afisat cuvântul de cod corectat, iar daca transmisia s-a facut cu doua erori nu va putea fi afisat cuvântul corect (codul detecteaza doua erori si corecteaza doar una), dar se va aprinde becul din stânga schemei indicând prezenta a doua erori. Prin apasarea unei noi taste, pe ecran va aparea înca un cadru (4) unde va fi afisat sindromul s si pozitia bitului eronat (la transmisia cu un bit eronat) sau apare mesajul: "transmisie cu doi biti eronati", iar în cadrul (1) va fi înscris cuvântul de cod corectat (atunci când este posibil). Pentru iesirea din program se apasa tasta X.

49

Fig. 3. Schema de decodare a codului Hamming SEC -DED.

4. Desfasurarea lucrarii 4.1. Se studiaza introducerea teoretica. 4.2. Se introduc de la tastatura (si se noteaza) bitii de informatie I0 I1 I2 I3 si se urmareste calculul bitilor de control C0 C1 C 2 C3 pe schema de codare, facându-se comparatia valorilor de pe ecran cu cele calculate cu ajutorul relatiilor din introducerea teoretica. 4.3. Se introduce de la tastatura (si se noteaza) cuvântul eroare e si se urmareste pe schema canalului de transmisiune calculul cuvântului receptionat afisat, calculat cu relatia: r = v⊕e . 4.4. Se urmareste pe schema de decodare modul de corectie a unei erori sau de detectie a doua erori si se compara decizia decodorului cu valoarea sindromului. 4.5. Se repeta punctele 4.2, 4.3 si 4.4 pentru un cuvânt eroare cu un bit eronat (de informatie sau de control), pentru un cuvânt eroare cu doi biti eronati si pentru un cuvânt de cod fara eroare.

5. Întrebari 5.1. Ce se întelege prin cod perfect? 5.2. Ce este un cod sistematic? Dar nesistematic? 5.3. Ce semnificatie au coloanele h j ale matricei de control H? 5.4. Cum se obtine matricea de control extinsa H din matricea de control initiala H? 5.5. Cum se numeste bitul de control suplimentar introdus de codul Hamming extins? 5.6. Cât este distanta minima a codului Hamming C(7,4)? Dar a codului extins C(8,4)? 5.7. Care este relatia de calcul a corectorului pentru C(7,4)? Dar pentru C(8,4)? 5.8. Care este semnificatia termenilor din compunerea corectorilor s si s? 5.9. Cum actioneaza codul Hamming SEC-DED daca apar mai mult de doua erori?

50