L5 - Platforma

Lucrarea 5.a. Coduri ciclice binare H(7,4,3) peste GF(2). 1. Obiectivul lucrarii Lucrarea se ocupa cu studiul codurilor Hamming ciclice corectoare de o eroare/detectoare de doua erori, codate si decodate prin circuite de divizare si registre de deplasare cu reactie.

2. Introducere teoretica Codurile ciclice sunt coduri bloc în care cele n simboluri care formeaza un cuvânt sunt considerate ca fiind coeficientii binari ai unui polinom v(x) de grad n-1. Codurile ciclice au proprietatea ca daca v(x) este un cuvânt cu sens, atunci orice permutare ciclica a simbolurilor sale este un cuvânt cu sens. De asemenea, cuvintele de cod sunt privite ca elemente ale unei algebre lineare (+,x) modulo p(x) = xn + 1. Cuvintele cu sens (în numar de 2k) sunt elemente ale idealului generat de polinomul ireductibil si primitiv g(x) (numit polinom generator, divizor al polinomului p(x)) de grad m: v(x) = i(x)g(x), iar cuvintele fara sens (în numar de 2n – 2 k) alcatuiesc cele 2m clase de resturi modulo p(x). Relatiile matriceale deduse în cazul codurilor grup ramân valabile, codurile ciclice facând parte, de asemenea, din categoria codurilor lineare. Codarea este operatia de determinare a polinomului simbolurilor de control c(x) în functie de polinomul simbolurilor de informatie i(x). Simbolurile de control introduc o redundanta care faciliteaza detectia si corectia erorilor. Acestea pot fi calculate pe baza polinomului generator g(x), din relatia: c(x ) = rest

x m i(x) , g (x)

sau pe baza polinomului de control h(x) de grad k , din relatia v(x)h(x) = 0 modp(x), în ambele cazuri rezultând un cuvânt de cod de forma: v(x ) = x mi(x ) + rest

x m i(x) . g (x)

Polinomul de control poate fi determinat din polinomul modulo si polinomul generator cu relatia: h( x ) =

p ( x) . g (x )

Cu ajutorul coeficientilor polinomului de control, matricea H poate fi scrisa astfel: 0  0 H= .  hk

0

...

0

0 .

... hk . .

hk −1 ... h0

51

hk

... h1

hk −1 ... h0 . . . 0

... 0

h0   0. .  0

Codul Hamming ciclic este un cod perfect (n = 2 m-1), corector de o eroare (d min = 3) si sistematic, adica are proprietatea ca simbolurile de informatie sunt delimitate de simbolurile de control si sunt plasate succesiv la sfârsitul cuvântului de cod. Decodarea este operatia inversa codarii si consta în gasirea unei corespondente între cuvântul eronat receptionat v’(x) si erorile introduse de canal e(x): v’(x) = v(x) + e(x). Decodarea se face pe baza valorii corectorului s(x) s ( x) = rest

v ' ( x) e( x ) , = rest g( x ) g ( x)

care se obtine prin însumarea simbolurilor de control receptionate cu simbolurile de control obtinute prin recodarea simbolurilor de informatie receptionate: s (x) = c ' (x ) + rest

x mi ' ( x) . g( x)

Codurile ciclice cu distanta minima 3 pot fi utilizate fie pentru corectia erorilor singulare, fie pentru detectia erorilor duble. În ambele cazuri, se prelucreaza valoarea corectorului, folosindu-se diverse circuite pentru efectuarea codarii si a decodar ii. 2.1. Codarea prin circuite de divizare Codorul este format dintr-un circuit de divizare cu celule binare de memorare pe 1 bit si sumatoare modulo 2 interioare. Circuitul de divizare are conexiunile buclei de reactie realizate conform coeficientilor polinomului generator g(x). Schema bloc este prezentata în figura 1.

Fig. 1. Codor cu circuit de divizare prin g(x).

Pe durata primelor k perioade de tact, comutatorul K este în pozitia 1, astfel încât cei k biti de informatie de la intrare se regasesc în cuvântul de la iesire. Celulele codorului vor contine dupa k perioade de tact simbolurile de control. Dupa terminarea introducerii simbolurilor de informatie, comutatorul K este trecut în pozitia 2 si continutul celulelor este evacuat, completându-se ultimii m biti din cuvântul de cod, care reprezinta simbolurile de control. 2.2. Decodare cu circuite de divizare 2.2.1. Detectia erorilor Decodorul cu detectia erorilor este eficient pentru detectia pachetelor de erori de lungime maxima m. Schema bloc este prezentata în figura 2.

52

Fig. 2. Decodor cu circuit de divizare pentru detectia erorilor.

Dupa n perioade de tact, în circuitul de divizare se va afla restul împartirii polinomului cuvântului receptionat la polinomul genera tor g(x). Daca acest rest este 0, la iesirea portii SAU-NU va fi “1”, deci cuvântul receptionat nu este eronat. Iesirea portii SAU-NU se pozitioneaza pe “0” când în cuvântul receptionat s-au introdus erori, indiferent de pozitia acestora. 2.2.2. Corectia erorilor Decodorul cu corectia erorilor este format dintr-un registru de deplasare în inel de lungime n, 3 porti logice SI, un circuit de divizare cu m celule si un multiplexor. Schema bloc este prezentata în figura 3.

Fig. 3. Decodor cu circuit de divizare pentru corectia erorilor.

Registrul de deplasare are rolul de a înmagazina cei n biti receptionati, necesari pentru efectuarea corectiei. MUX-ul este "deschis" pe perioada primelor n tacte si registrul se comporta ca un registru de deplasare de la stânga la dreapta. Dupa primele n tacte, celulele de divizare contin simbolurile corespunzatoare corectorului cuvântului receptionat. Pe perioada urmatoarelor n perioade de tact se obtine cuvântul decodat astfel: bitul de iesire se calculeaza prin însumarea modulo 2 între bitul corespunzator ca pozitie din cuvântul receptionat (bit înmagazinat în celula cea mai putin semnificativa din registru) si un bit care are valoarea “1” numai atunci când bitul corespunzator ca pozitie din cuvântul receptionat

53

este eronat. Deci momentul când bitul eronat a ajuns în celula cea mai putin semnificativa din registru este identificat cu ajutorul unui detector al starii circuitului de divizare. Când starea acestuia coincide cu ultima coloana din matricea de control H a codului, bitul de corectie devine “1”, iar iesirea se obtine prin complementarea bitului eronat. În ultimele n perioade de tact, MUX-ul permite înscrierea în celula cea mai semnificativa din registru a iesirii, deci continutul registrului este rotit de la dreapta la stânga în inel. Decodorul poate corecta o eroare indiferent de pozitia acesteia. 2.3. Codor cu registru de deplasare cu reactie Codorul este format dintr-un registru de deplasare cu reactie cu m celule, conexiunile de reactie fiind realizate conform coeficientilor polinomului generator. Schema bloc este prezentata în figura 4. Starea initiala a registrului este nula, astfel încât în toate celulele se afla înmagazinat simbolul “0”. Pe perioada primelor k perioade de tact, comutatorul K este în pozitia “1” si se introduc simbolurile de informatie, care în acelasi timp apar si la iesire.

Fig. 4. Codor cu registru de deplasare cu reactie.

Comutatorul K este apoi trecut în pozitia 2, astfel încât la intrarea în registru se obtine dupa fiecare deplasare simbolul “0”. Dupa m astfel de deplasari, registrul este adus în starea initiala nula. La fiecare tact registrul este evacuat, calculându-se în continuare ultimii m biti din cuvânt, bitii de control. 2.4. Decodor cu registru de deplasare cu reactie Decodorul este format dintr-un registru de memorare, doua decodoare identice cu registre de deplasare cu reactie care functioneaza în tandem, o poarta SAU si 4 porti SI. Schema bloc este prezentata în figura 5. Initial comutatorul K este în pozitia 1 si în primele n perioade de tact cuvântul receptionat este pe de o parte înmagazinat în registrul de memorare, iar pe de alta parte este încarcat simultan în decodorul DC1. La sfârsitul celor n perioade de tact, decodorul DC1 contine corectorul corespunzator cuvântului receptionat. Pe durata urmatoarelor n perioade de tact, comutatorul este trecut în pozitia 2 si iesirea se obtine însumând modulo 2 bitul din celula cea mai putin semnificativa a registrului de memorare cu un bit care va avea valoarea “1” numai atunci când bitul corespunzator ca pozitie din cuvântul receptionat este eronat. Deci momentul în care bitul eronat a ajuns în 54

celula cea mai putin semnificativa din registrul de memorare este identificat cu ajutorul unui detector al starii registrului de deplasare cu reactie din DC1. Când starea acestuia coincide cu ultima coloana din matricea de control H a codului, bitul de corectie devine “1”, iar iesirea se obtine prin complementarea bitului eronat.

Fig. 5. Decodor cu registru de deplasare cu reactie pentru corectia erorilor.

Decodorul DC2 executa acelasi ciclu de n + n perioade de tact, dar în opozitie fata de DC1: când DC1 calculeaza corectorul cuvântului receptionat care tocmai in tra în registrul de memorare, DC2 efectueaza operatia de corectie asupra cuvântului receptionat anterior, care iese din registrul de memorare, si viceversa. În felul acesta, operatia de decodare decurge în flux continuu asupra cuvintelor receptionate de pe canal. Decodorul poate corecta o eroare indiferent de pozitia acesteia.

3. Descrierea evolutiei programului Programul se lanseaza în executie tastând “hamm.exe”. Meniul principal prezinta urmatoarele optiuni: • • •

C - Codor -decodor Hamming ciclic, T - Teorie cod Hamming ciclic, X - eXit.

În optiunea C apare un submeniu în care utilizatorul alege tipul structurii fizice de implementare a schemelor codorului si decodorului: • •

C - Circuite de divizare, R - Registre de deplasare cu reactie, 55

• X - eXit. Înaintea efectuarii operatiei de codare, trebuie ales polinomul generator g(x) dintr-un set de 4 polinoame ireductibile si primitive de grad 3 si 4 (divizori ai lui x 7 + 1, respectiv x15 + 1 ), cu coeficienti binari: 1. 1 + x + x 3 , 2. 1 + x 2 + x 3 , 3. 1 + x + x 4 , 4. 1 + x 3 + x 4 . În optiunea de codare, se introduc coeficientii binari ai polinomului simbolurilor de informatie i(x), iar apoi este descrisa secvential operatia de codare pe schema si pe tabelul evolutiei starilor, care este completat prin apasarea tastei T (Tact). Momentul în care toti bitii de informatie au fost încarcati în circuitul de codare, precum si momentul în care operatia de codare a luat sfârsit, sunt marcate prin semnale sonore. Daca în continuare se doreste efectuare operatiei de decodare, trebuie aleasa varianta de lucru: • D - Detectia erorilor, • C - Corectia erorilor. De fiecare data se cere introducerea simbolurilor cuvântului eroare, care afecteaza cuvântul cu sens obtinut în urma operatiei de codare. Functionarea decodorului este prezentata pas cu pas, pe schema si/sau pe tabelul evolutiei starilor, similar optiunii de codare. În cazul variantei cu detectia erorilor se obtine valoarea corectorului, iar în cazul variantei cu corectia erorilor se obtine cuvântul de cod refacut la decodor. Programul este protejat împotriva introducerii datelor nespecifice.

4. Desfasurarea lucrarii 4.1. Codarea si decodarea cu circuite de divizare. 4.1.1. Luând polinomul generator g(x) = 1 + x + x3 se stabilesc simbolurile de control pentru doua polinoame de informatie, notându-se tabelul evolutiei starilor celulelor circuitului de divizare. 4.1.2. Se compara valorile obtinute cu rezultatele teoretice. 4.1.3. Se decodeaza cuvântul obtinut la punctul 4.1.1 folosind decodorul cu circuit de divizare pentru detectia erorilor. Se noteaza tabelul evolutiei starilor celulelor circuitului de divizare. 4.1.4. Se decodeaza cuvântul obtinut la punctul 4.1.1 folosind decodorul cu circuit de divizare pentru corectia erorilor. Se noteaza tabelul evolutiei starilor celulelor circuitului de divizare. 4.1.5. Se repeta punctele 4.1.3, 4.1.4 pentru o eroare, doua erori si trei erori, indiferent de pozitia acestora. 4.1.6. Se repeta punctele 4.1.1 – 4.1.5 pentru polinomul generator g(x) = 1 + x + x4. 4.2. Codarea si decodarea cu registre de deplasare cu reactie. 4.2.1. Luând polinomul generator g(x) = 1 + x + x3 se stabilesc simbolurile de control pentru doua polinoame de informatie, notându-se tabelul evolutiei starilor celulelor registrului de deplasare cu reactie. 4.2.2. Se compara valorile obtinute cu rezultatele teoretice. 4.2.3. Se decodeaza cuvântul obtinut la punctul 4.2.1. Se noteaza tabelul evolutiei starilor celulelor registrului de deplasare cu reactie. 4.2.4. Se repeta punctul 4.2.3 pentru o eroare, doua erori si trei erori, indiferent de pozitia acestora. 4.2.5. Se repeta punctele 4.2.1, 2.2, 2.3, 2.4 pentru polinomul g( x) = 1 + x + x4.

56

5. Întrebari 5.1. Care este diferenta între codarea realizata prin multiplicare: v(x) = i(x)g(x) si codarea realizata prin diviz are : v( x) = rest

x mi( x) + x mi( x) ? g( x)

5.2. Desi corectorul este s ( x ) = rest

v ' (x ) g ( x)

s ( x) = rest

e(x ) , g ( x)

sau

de ce la decodare calcului acestuia se face numai din vectorul receptionat v'(x)? 5.3. Când corectorul este zero? 5.4. Ce contin celulele codorului cu circuit de divizare dupa k perioade de tact? 5.5. La codorul cu circuit de divizare, de ce intrarea se face prin capatul din dreapta? 5.6. Care este numarul maxim de erori detectate de decodorul cu circuit de divizare pentru detectia erorilor? 5.7. De ce, atunci când comutatorul K este în pozitia 2 la codorul cu registru de deplasare cu reactie, intrarea în registru este “0”? 5.8. Când bitul de corectie generat de detectorul de erori al decodorului cu registru de deplasare cu reactie pentru corectia erorilor este “1”? 5.9. Ce se întâmpla daca, atunci când programul asteapta introducerea mesajului, în loc de un simbol binar “0” sau “1”, se introduce de la tastatura un caracter sau orice alta cifra? 5.10. Cum actioneaza circuitele de corectie atunci când în cuvântul receptionat sunt doua sau mai multe erori?

57