l4 - platforma

8/14/2019 L4 - platforma

1/6

45

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), punnd n evidenta modalitatea de corectie a unei erori sau de detectiea doua erori.

2. Introducere teoretica

Unul din codurile grup cele mai cunoscute este codul Hamming H(n,k) corector de oeroare, la care coloana hj a matricei de controlHeste reprezentarea binara a numaruluij , dacaeroarea 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: dmin= 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, corespunznd unor vectoricoloana din matricea de control H cu o singura pozitie diferita de 0, ceea ce usureazadeterminarea simbolurilor de control din relatia:

HvT = 0.

Daca, pe lnga corectia unei erori, trebuie sa se asigure si detectia erorilor duble, setransforma codul Hamming corector de o eroare (Single-ErrorCorrecting:SEC) ntr-un codHamming corector de o eroare si detector de erori duble (Single-Error Correcting and

Double-ErrorDetecting:SEC-DED).Distanta minima a unui cod care corecteaza terori si simultan detecteaza l erori ( l > t),trebuie sa fie cel putin l + t + 1: 1min ++ ltd . Deci, t = 1, l = 2 4121min =++ d .Asadar, distanta minima a codului trebuie crescuta cu o unitate. Aceasta se poate realiza ndoua moduri: utiliznd un cod Hamming extins sau un cod Hamming prescurtat.

Pentru a obtine un cod Hamming extins se bordeaza matricea de control Ha coduluiHamming initial cu o coloana de "0" la stnga si cu o linie de "1" n partea inferioara:

[ ]7654321076543210 11111111110

hhhhhhhhhhhhhhhhH

H =

=

= .

Matricea de control H va avea m = m+1 linii si n = n+1 coloane, de unde rezultaC(n+1,k). Deci lungimea cuvntului de cod va creste cu o unitate, care corespundeintroducerii unui bit de control suplimentar, pe prima pozitie din stnga.

Exemplu:codul C(7,4). Structura unui cuvnt de cod va fi acum:

[ ]76543210 iiicicccv = ,

iar relatia matriceala de codare pentru codul extins C(8,4):

0= TvH


2/6

46

va conduce la urmatoarele ecuatii de codare:

++=++++++=

++=++=

++=

=

65376543210

7531

7632

7654

7

6

5

4

3

2

1

0

0

11111111

1010101011001100

11110000

iiiiiiciccc

iiic

iiic

iiic

i

i

i

c

i

c

c

c

.

Se observa ca bitul de control suplimentar c0 este suma modulo 2 a tuturor celorlaltibiti din cuvntul de cod. De aceea el se numeste simbol de control al paritatii, sau, pe scurt,bit de paritate. Se poate arata usor ca acest bit de paritate creste distanta minima a codului cuo unitate.

Exemplu:

[ ] [ ] [ ]

[ ] [ ] [ ]

=

==

=

=

=

=

==

=

==

=

=

=

=

==

4)(

4)(;10101010

0

1

0

0

1011

4)(

3)(;10100101

1

0

1

0

1010

0

1

2

4

7653

0

1

2

4

7653

vw

vwv

c

c

c

c

iiiii

vw

vwv

c

c

c

c

iiiii

.

n cazul cuvintelor de cod care initial aveau ponderea w(v) = dmin= 3, bitul de paritateeste 1, deci w(v) = 4.n cazul cuvintelor de cod care initial aveau ponderea w(v) = dmin+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"ramne neschimbata.

La decodare, corectorul calculat va avea acum 4 pozitii:

=

===0

0

1

2

3

s

s

s

s

s

s

eHrHsTT

.

Daca a aparut un numar impar de erori, atunci corectorul s va consta din suma modulo2 a unui numar impar de coloane din matricea H, de tipul:

=

1i

i

hh ,


3/6

47

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:

=

1i

i

hh ,

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 0s si s0 = 1, decizia va fi: a aparut o eroare corectabila; daca 0s 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

[ ]10101010=v .

[ ] 1

1

1

0

1

1

1

1

0

1

1

1

0

1

1

0

0

10001010 0731 =

=

+

+

=++=== shhhrHsrT

a aparut o eroare corectabila pe pozitia data de:

[ ]

[ ] [ ]

[ ]

[ ]

=

=

+

=+===

==

=+=+=

===

=

0

0

0

1

1

1

1

1

1

1

1

0

0

10000010

10101010

0010000010001010

001000005

1

0

1

0

71

*

5

s

hhrHsr

v

erv

eihs

T

au aparut doua erori necorectabile, dar detectabile.

Pentru a obtine un cod Hamming sistematic s-au permutat coloanele matricei decontrolH, obtinndu-se matriceaH :

=

11111111

11101000

01110100

11010010

H.


4/6

48

Din relatia:

++=

++=

++=

++=

=

3104

3213

2102

3201

0

iiic

iiic

iiic

iiic

vHT ,

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 apasnd 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 sunttransmise. n cadrul (2) vor fi introdusi de la tastatura cei patru biti de informatie, respectiv I 0I1 I2 I3. Daca se vor introduce alte simboluri dect cele binare, pe ecran va apare mesajul:"comanda eronata".

Dupa introducerea celor patru biti de informatie ceruti, pe ecran va fi afisata schemade codare pentru C(8,4). La intrarea acestei scheme se vor afla nscrisi cei patru biti introduside la tastatura. Acesti biti vor intra n schema prin apasarea de 4 ori a oricarei taste. Seobserva ca pe timpul introducerii bitilor de informatie, comutatorul K este pe pozitia 1, bitiifiind afisati si la iesirea schemei.

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


5/6

49

La apasarea celei de a cincea taste, comutatorul K va trece pe pozitia 2 si bitii decontrol C0 C1 C2 C3 vor fi calculati si afisati. Acestia vor fi trecuti la iesirea codorului prinapasarea succesiva a nca patru taste.

Dupa ce s-a terminat codarea, la iesirea schemei se afla cuvntul de cod

v = C0 C1 C2 C3 I0 I1 I2 I3

transmis. Acest cuvnt 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 cuvntul eroare.

Dupa introducerea celui de-al 8-lea bit al cuvntului eroare, pe ecran va fi afisataschema bloc a lantului de transmisiune, care la intrare va avea cuvntul de cod

v = C0 C1 C2 C3 I0 I1 I2 I3,

cuvnt de cod care va fi adunat modulo 2 cu cuvntul eroare e, iar la iesirea acesteia va fi nscris cuvntul receptionat r. Prin apasarea unei noi taste se observa ca n cadrul (1) a fostnscris cuvntul 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 afisata schema de

decodare pentru C(8,4). La intrarea schemei vor fi nscrisi bitii receptionati, care se introducn schema prin apasarea succesiva a 8 taste.

n cazul n care cuvntul a fost transmis cu o eroare, la iesirea schemei va fi afisatcuvntul de cod corectat, iar daca transmisia s-a facut cu doua erori nu va putea fi afisatcuvntul corect (codul detecteaza doua erori si corecteaza doar una), dar se va aprinde beculdin stnga schemei indicnd prezenta a doua erori.

Prin apasarea unei noi taste, pe ecran va aparea nca un cadru (4) unde va fi afisatsindromul 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 cuvntul de cod corectat (atunci

cnd este posibil).Pentru iesirea din program se apasa tasta X.


6/6

50

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 C2 C3 pe schema de codare, facndu-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) cuvntul eroare e si se urmareste pe

schema canalului de transmisiune calculul cuvntului receptionat afisat, calculat cu relatia:evr = .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 cuvnt eroare cu un bit eronat (de

informatie sau de control), pentru un cuvnt eroare cu doi biti eronati si pentru un cuvnt decod 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 hj ale matricei de controlH?5.4. Cum se obtine matricea de control extinsa Hdin matricea de control initialaH?5.5. Cum se numeste bitul de control suplimentar introdus de codul Hamming extins?5.6. Ct 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?

l4 - platforma

Documents