Coduri grup

Coduri grup

2.6.1 Principiul decodarii utilizand matricea de control

Procesul de detectie si corectie a erorilor presupune tratarea intr-un anumit mod a semnalului receptionat, astfel incat sa fie corectat efectul perturbatiilor din canalul de transmisie. Putem face considerand o multime Z, numita multimea corectorilor si care contine vectori m dimensionali, capabili sa corecteze sau sa detecteze erorile introduse in canal. Intre multimea cuvintelor receptionate 919f51j , W si multimea corectorilor Z se stabileste o aplicatie definita pe W cu valori in Z astfel incat pentru orice cuvant receptionat sa putem defini un corector Z_i. Avand in vedere caracterul vectorial al campurilor W si Z in care vectorii pot fi reprezentati prin matrici, aplicatia va fi definita ca un produs matricial:

(1.) , unde este transpusa matricei .

Matricea H poarta numele de matrice de control si este alcatuita din m linii si n coloane. Prin definitie:

Avand in vedere scopul introducerii multimii Z, acela de a detecta si corecta erori de transmisie, convenim sa construim in asa fel aceasta multime incat oricand operatia (1.) se efectueaza asupra unui cuvant de cod sa se obtina acelasi corector care are toate componentele nule.

(2.) Aceasta conditie va constitui si relatia de codare. Daca la receptia unui cuvant de cod avem indeplinita relatia (2.) este fara erori si daca rezulta ca in sunt erori. Relatia (1.) serveste deci la DETECTIA ERORILOR.

(3.)

unde E_i este cuvantul eroare. Deci relatia (1.) poate conduce la localizarea erorilor care au afectat cuvantul de cod, daca se decodifica corectorul cu ajutorul relatiei (3.) obtinand cuvantul eroare.

2.6.2 Conditii impuse matricei de control pentru a detecta sau corecta erori

Stabilim conditia pe care trebuie sa o satisfaca matricea de control H, pentru a detecta prezenta erorilor. In acest scop presupunem H compusa din coloane: , iar pe E_i de forma: , in care s-au inclus t componente cu valoare 1. Se constata ca .

Deci pentru a detecta prezenta unui cuvant eroare cu t erori este suficient ca suma a t coloane oarecare din H sa fie nenula.

Stabilim conditia pe care trebuie sa o indeplineasca matricea H pentru a putea corecta cuvinte cu maxim t erori. In acest caz calculam corectorul Z_i pentru doua cuvinte de eroare diferite cu t erori, si obtinem:

si ,

iar conditiile de injectivitate impun ca: sau , adica:

Cu alte cuvinte pentru ca matricea de control sa poata fi folosita la corectia a t erori, este necesar ca suma a oricaror 2t coloane din matrice sa fie diferita de zero. Din cele doua conditii de a corecta respectiv de a detecta erori, rezulta suplimentar ca o matrice de control capabila sa corecteze t erori, este capabila sa detecteze 2t erori. Denumim pondere a unui cuvant de cod, numarul componentelor sale diferite de zero. Fie doua cuvinte de cod v_i si v_j IV. Deoarece V are structura de grup rezulta ca v_i+v_jIV si este si el un cuvant de cod. Pe de alta parte v_i + v_j da un cuvant a carui pondere este egala cu distanta Hamming dintre v_i si v_j. Denumim distanta Hamming a unui cod, cea mai mica distanta Hamming dintre cuvintele codului. Se vede deci ca distanta Hamming a unui cod este egala cu ponderea cea mai mica a cuvintelor de cod exceptand cuvantul nul.

Daca distanta Hamming a codului este 2t+1, atunci exista un cuvant de cod v_r, cu ponderea 2t+1. Pentru acest cuvant: , ceea ce inseamna ca suma a 2t+1 coloane este zero. Daca matricea H poate corecta t erori rezulta ca suma a 2t coloane este diferita de zero si ca exista un cuvant de cod pentru care suma a 2t+1 coloane este nula. Ceea ce inseamna ca un cod capabil sa corecteze t erori are distanta Hamming cel putin 2t+1. Un cod capabil sa detecteze t erori are distanta Hamming 2t+1.

2.6.3 Constructia matricei de control pentru a detecta un numar impar de erori

Ne propunem sa aflam structura unei matrice de control capabile sa detecteze 2t+1 erori. Fie:

in care consideram ca fiecare coloana se termina cu 1, ca atare relatia (1.) devine:

Aceasta suma de coloane va contine in ultima linie un numar impar de "1"-uri a caror suma nu este zero ceea ce inseamna ca se satisface conditia detectarii erorii (1.), indiferent de continutul coloanelor h₁h_n din matricea H, acestea putand fi nule. Fie: . O asemenea matrice are dimensiunea m=1, ceea ce inseamna ca in multimea Z a corectorilor vor fi numai 2 elemente: corectorul Z=0 si Z=1. Primul va indica absenta erorilor in numar impar iar al doilea Z=1 va indica prezenta erorilor in numar impar. Acest procedeu de codare cu implica existenta unui numar par de 1 in cuvintele de cod . Acest tip de codare se numeste codare cu control de paritate.

2.6.4 Constructia matricii de control pentru a detecta doua erori

Am stabilit in paragraful precedent ca adaugarea unui simbol de control la cele n-1 simboluri de informatie poate verifica existenta unui numar impar de erori. Tot asa de bine putem spune ca verifica si existenta unui numar par de erori, in acest caz numarul de "1" -uri din cuvantul receptionat fiind par.

Admitem ca n-1 biti ai cuvantului transmis sunt constituiti astfel incat sa poata corecta o eroare satisfacandu-se conditia pentru cuvantul cu n-1 biti. Daca adaugam inca un bit, cel de al n-lea, obtinem un cuvant de cod care corecteaza o eroare si detecteaza 2 erori. In acest scop construim matricea din matricea H' prin adaugarea unei coloane nule si a unei linii compuse numai din 1. In acest caz conditia de codare devine:

La receptie:

Se constata ca la emisie:; reprezinta conditia pentru un cuvant de cod cu n-1 simboluri.

La receptie: ; reprezinta corectorul acestui cuvant de cod. O eroare in cuvantul receptionat se va detecta si se va corecta prin intermediul corectorului .

Constatam ca la emisie: ceea ce inseamna ca face paritatea canalului de cod.

La receptie: ; care poate sa fie 1 (numarul de erori este impar), sau 0 (numarul de erori este par).

Avem situatia:

, e=0 nu sunt erori;

, e=1 este o eroare corectabila prin

, e=1 este o eroare in pozitia  

, e=0 sunt detectate doua erori