Transmisiuni de date Seminar 4

1

CODURI HAMMING GRUP

Unul din codurile cele mai cunoscute este codul Hamming C(n, k), corector de o eroare, la care coloana hi, a matricii de control H, este reprezentarea în binar a numărului i, dacă eroarea este singulară.

• Lungimea codului este ; n = m + k o k – numărul de simboluri de informaţie o m – numărul simbolurilor de control o n lungimea fiecărui cuvânt

• Cuvântul de cod este de forma , unde ci reprezintă cuvintele de control, iar ii reprezintă biţii de informaţie. Mulţimea cuvintelor de cod (cuvinte cu sens), care trebuie să satisfacă anumite condiţii:

o numărul de cuvinte cu sens va trebui să fie mai mare sau egal cu numărul mesajelor ce urmează a fi transmise , cu k < n

o submulţimea V se alege astfel încât să formeze un subgrup în raport cu grupul tuturor cuvintelor posibile

• 2i reprezintă poziţia simbolurilor de control cu • H matricea de control , unde hi reprezintă în cod binar

numărul coloanei respective • Relaţia de codare este de forma • un cuvânt de cod eronat, cu ei eroare

• . Dacă si = 0 ⇒

• , m = n – k ⇒ n = m + k, 2m reprezintă numărul de corectori

distincţi, iar reprezintă numărul total al cuvintelor eroare, în cazul în care

se doreşte corecţia a „e” erori • distanţa minimă este 3 • numărul de erori ce pot fi corectate este 1 Acest cod pe lângă faptul că poate corecta o eroare singulara, mai poate detecta şi

erori duble. În acest fel codul se transformă într-un cod corector de o eroare şi detector de erori duble. Distanţa minimă a unui cod ce corectează t erori şi detectează p erori (p > t) trebuie să fie cel puţin p + t + 1. Pentru t = 1 şi p = 2 ⇒ dmin = 1 + 2 + 1 = 4. În concluzie distanţa minimă a codului trebuie crescută cu o unitate, acest lucru realizându-se în două moduri: fie utilizând un cod Hamming extins, fie un cod Hamming prescurtat.

Transmisiuni de date Seminar 4

2

Pentru a obţine un cod Hamming extins se bordează matricea de control H a codului Hamming iniţial cu o coloană de „0” la stânga şi cu o linie de „1” în partea inferioară.

Matricea de control a avea linii şi coloane, de unde rezultă C(n+1,k). Astfel lungimea cuvântului de cod va creşte cu o unitate, care corespunde introducerii unui bit de control suplimentar, pe prima poziţie din stânga.

Exemplu Codul C(7, 4) Structura unui cuvânt de cod va fi de forma:

Astfel rezultă codul extins C(8, 4) cu relaţia de codare de forma

Bitul c0 este suma modulo 2 a tuturor celorlalţi biţi din cuvântul de cod, numindu-se bit de control al parităţii sau bit de paritate.

Distanţa minimă a codului Hamming extins este 4. Prin adăugarea bitului de paritate, ponderea cuvintelor care iniţial aveau un număr par de „1” rămâne neschimbată, iar cea a cuvintelor cu număr impar de „1” va creşte cu o unitate.

Problemă Fie N = 16 simboluri ce se transmit pe un canal cu perturbaţii utilizând un cod

Hamming grup corector de o eroare. Să se calculeze: a) k – numărul simbolurilor de informaţie

m – numărul simbolurilor de control n – lungimea fiecărui cuvânt de cod

b) H – matricea de control şi cuvintele de cod c) Să se reprezinte schema codorului şi a decodorului d) Expresia corectorului când se eronează c4. Rezolvare

a) N = 16

Transmisiuni de date Seminar 4

3

c1 c2 i3 c4 i5 i6 i7

S1

+

S2

+

S3

+

c1

c2

c4

out

RD1

b)

Pentru a se determina cuvintele de cod trebuie determinaţi biţii de control pe poziţiile 2i cu 20 = 1 21 = 2 22 = 4 Biţii de control vor apare pe poziţiile 1, 2 şi 4.

Codarea se realizează cu formula

c) Codorul este format dintr-un registru de deplasare cu 7 celule.

Transmisiuni de date Seminar 4

4

Decodorul este format dintr-un registru de deplasare şi un descifrator zecimal.

d)

Transmisiuni de date Seminar 4

5

Lucrarea de laborator

Corectorul de erori În cazul codului C(8, 4), vom avea 4 poziţii:

r – reprezintă secvenţa care apare eronat Dacă vor apare un număr impar de erori, atunci corectorul va consta din suma

modulo 2 a unui număr impar de coloane din matricea , iar pe ultima poziţie a corectorului se va afla s0 = 1.

Dacă vor apare un număr par de erori , atunci corectorul va consta din suma modulo 2 a unui număr par de coloane din matricea , iar pe ultima poziţie a corectorului se va afla s0 = 0.

Simbolul s0 va împiedica o corecţie eronată, detectând erorile duble. Decodarea se va realiza după următoarele reguli:

• dacă s = 0 şi s0 = 0 nu au apărut erori • dacă s ≠ 0 şi s0 = 1 apare o eroare corectabilă • dacă s ≠ 0 şi s0 = 0 apar două erori necorectabile • dacă s = 0 şi s0 = 1 bitul de paritate este eronat. Exemplu C(7, 4) sau C(8, 4)

Cazul fără erori

s = 0

s0 = 0

Transmisiuni de date Seminar 4

6

Detectarea şi corectarea unei erori Fie secvenţa

Detectarea de erori duble Fie secvenţa

s ≠ 0

s0 = 1

s ≠ 0

s0 = 0