Coduri bloc liniare

CODURI BLOC LINIARE

La scurt timp dupa aparitia teoremei canalelor cu perturbatii (teorema a II-a a lui Shannon), au fost inventate primele coduri pentru protectie la erori : codurile bloc liniare. Principalele etape in istoria evolutiei acestor coduri au fost :1950 -R.Hamming si M.Golay au propus codurile liniare sistematice, 1957-1960 -D.Slepian a dat o teorie unitara a codurilor liniare ; dupa 1960, literatura de specialitate a cunoscut numeroase lucrari care au aprofundat studiul codurilor liniare si au propus o serie de coduri concrete.

Din clasa larga a codurilor bloc liniare ne vom ocupa doar de codurile binare, deci cu simboluri in cimpul Galois GF(2) ;teoria pentru codurile binare poate fi cu usurinta generalizata pentru coduri nebinare , deci pentru [An-72].

1 DEFINIREA SI DESCRIEREA MATRICEALA A CODURILOR BLOC LINIARE

Asa cum am aratat in 3, in cazul codurilor bloc, informatia unei surse binare se imparte in blocuri de m biti notate cu i (bloc informational) ; la cele m simboluri informationale se adauga simbolurile redundante ( de control ) in numar de k, dupa o anumita lege de codare formind un cuvint de cod (v) de lungime n, in care

n=m+k (30)

Numarul mesajelor codificabile, deci si al cuvintelor de cod, pentru o asemenea structura este :

Din multimea codurilor bloc un interes deosebit in aplicatii practice prezinta structurile liniare.

Se numeste cod bloc liniar (n,m) codul de lungime n pentru care cele 2^m cuvinte de cod formeaza un subspatiu vectorial m-dimensional (C) al spatiului n-dimensional V_n format de multimea cuvintelor de cod ce pot fi formate cu n biti, deci cu coeficienti in GF(2). Denumirea de cod liniar provine de la faptul ca simbolurile de control se determina ca o combinatie liniara a simbolurilor de informatie.

Un cod bloc este liniar daca si numai daca suma modulo-2 a doua cuvinte de cod este tot un cuvint de cod (vezi proprietatile spatiilor vectoriale -Anexa A.8).

Prin definirea unei asemenea structuri, rezulta ca spatiul vectorial n-dimensional (V_n format din multimea combinatiilor distincte ce pot fi create cu n biti in numar de 2ⁿ, se imparte in doua multimi disjuncte : C multimea cuvintelor de cod avind 2^m elemente si F- multimea cuvintelor false cu 2ⁿ-2^m elemente.

Deoarece codul liniar C(n,m) este un subspatiu m-dimensional al spatiului V_n, intreaga multime a cuvintelor de cod va putea fi generata de combinatiile liniare a m vectori liniar independenti ai lui C. Acesti vectori liniari independenti ai codului, notati cu g_i , pot fi cuprinsi in matricea generatoare a codului G[m x n ] :

G= (32)

unde g_ij , deci sint simboluri binare .

In consecinta , legea de codare va fi data de relatia :

v=iG =i₁g₁+i₂g₂++i_mg_m

Daca se doreste obtinerea unei structuri sistematice :

v^'=[i c] (34.a)

sau

v"=[c I] (34.b)

matricea generatoare G va trebui sa aiba una din cele doua forme canonice :

G'=[I_m P] (32.a)

G"=[P I_m] (32.b)

In acest caz relatia de codare (33), se scrie :

P[k k]

Im

v^'=[i c]= iG'

= . (33.a)

c₁=f₁(i_j) c₂=f₂(i_j) c_k=f_k(i_j)

Din relatia (33.a) se observa ca cele m simboluri informationale se gasesc nemodificate in structura cuvintului de cod v, iar cele k simboluri de control notate cu c_i, sint combinatii liniare ale simbolurilor informationale :

c_i=f_i(i_j) ,

Relatiile (35) sint cunoscute sub denumirea de ecuatii de codare sau de verificare a paritatii (parity-check equations) ; sumele sint sume modulo-2.

Exemplul 3

Fie codul C(5,3) in care legea de codare este :

Vom determina matricea generatoare in structura canonica G', tinind cont de relatiile de codare astfel :

. Din combinatiile liniare ale celor trei vectori liniar independenti ai codului (g_i) , vom obtine celelalte patru cuvinte de cod nenule :

v₄= g₁+g₂ = [ 1 1 0 0 1]

v₅= g₁+g₃ =[ 1 0 1 1 1]

v₆= g₂+g₃ =[ 0 1 1 1 0]

v₇= g₁+g₂+g₃ =[ 1 1 1 0 0]

Din proprietatile spatiilor vectoriale binare (Anexa A.8) se stie ca daca avem un spatiu C de dimensiune m, atunci exista intotdeauna si spatiul nul (ortogonal ) al acestuia () de dimensiune k=n-m astfel incit un cuvint de cod v este ortogonal pe .Vectorii liniar independenti ai spatiului nul , in numar de k, pot fi cuprinsi intr-o matrice H[k x n ] numita matrice de control (de verificare a paritatii) :

H= (36)

unde h_ij , iar h_i , reprezinta coloanele matricei de control.

Ortogonalitatea spatiilor C si implica ortogonalitatea matricilor G si H :

GH^T=HG^T=0

unde T reprezinta transpusa matricei respective.

In cazul unor coduri liniare sistematice si pentru matricea H se impun formele canonice corepondente :

H'=[P^T I_k] (3a)

H"=[I_k P^T] (3b)

Relatia de codare (33) valabila in spatiul C devine in spatiul nul

Hv^T=0

2 DIMENSIONAREA UNUI COD BLOC LINIAR CORECTOR DE ERORI

Dimensionarea unui cod bloc consta in determinarea marimilor m,k si n necesare pentru codificarea unei surse avind M mesaje in vederea corectiei unui numar de t erori.

Numarul simbolurilor de informatie (m) este determinat de numarul mesajelor sursei (M) pentru coduri binare relatia de dimensionare a lui m este :

2^m M

Conditia necesara, insa nu si suficienta pentru construirea unui cod corector de t erori este :

2^k

relatie cunoscuta sub denumirea de margine Hamming .

Conditia suficienta, nu si necesara insa, pentru constructia unui cod corector de t erori este :

2^k

numita margine Varsamov-Gilbert .

Pentru corectia unei singure erori, cele doua margini conduc la aceeasi relatie, care constituie asfel conditia necesara si suficienta pentru constructia unui cod corector de o eroare :

2^k

3 CODURI PERFECTE SI CVASIPERFECTE

Se numesc coduri perfecte (strins impachetate, fara pierderi) codurile care satisfac relatia [An-72] :

Codurile perfecte pot corecta exact t erori, dar nici o configuratie particulara avind un numar mai mare de t erori.

Numarul codurilor perfecte este restrins ; cunoscute pina in prezent sint codurile Hamming cu n=2^k-1, codul binar cu repetare cu n impar si doua coduri Golay [An-72].

Coduri cvasiperfecte sint codurile care corecteaza toate combinatiile de t erori si o parte N combinatii de t+1 erori cu conditia ca (pentru coduri binare ) :

Codurile perfecte si cvasiperfecte asigura o probabilitate maxima a receptiei corecte in cazul transmisiei prin canale simetrice cu erori independente.

4 SINDROMUL ERORII

Fie receptia unui cuvint r, afectat de erori :

r=v+e , (45)

unde v reprezinta cuvintul de cod transmis, iar e este cuvintul eroare ; + este suma modulo-2 si indica erori de tip aditiv.

In cazul reprezentarii matriceale ,e este de forma :

e

unde e_i este "1" daca pe pozitia i apare o eroare si "0" in rest (pentru coduri binare evident).

La receptie se verifica legea de codare :

Hr^T=S

unde S se numeste sindrom (al erorii) si reprezinta o matrice coloana cu k elemente.

Inlocuind pe r cu expresia (45), relatia (47) se rescrie :

S=H(v+e)^T=Hv^T+He^T=He^T

ceea ce indica faptul ca sindromul nu depinde de cuvintul v transmis, ci doar de eroarea de pe canal (e).

Daca S=0 inseamna ca nu exista erori, sau erorile nu sint detectabile. In cazul in care prin eronare v se transforma tot intr-un cuvint de cod, relatia de codare fiind satisfacuta, nu poate fi facuta detectia erorii. Exista un numar de 2^m-1 situatii de erori nedetectabile, corespunzator unor cuvinte de cod, altele decit cel real transmis.

Daca S=0, se face detectia erorii, in cazul unui sistem ARQ cerindu-se retransmitere. Daca se doreste corectia erorii (FEC), atunci, pentru codurile binare, este necesara determinarea pozitiilor eronate din structura lui S. Numarul de sindroame distincte si nenule (sindromul nul corespunde lipsei erorii) este 2^k-1, deci din numarul total de erori posibile 2ⁿ-1 vor putea fi corectate doar 2^k-1.

CAPACITATILE DE DETECTIE ,RESPECTIV CORECTIE SI PROBABILITATEA DE EROARE A UNUI COD BLOC LINIAR

Fie codul bloc liniar C(n,m) detector de erori. Numarul total de erori (N_te este :

N_te= ⁿ

iar numarul erorilor nedetectabile :

N_en= ^m

Capacitatea de detectie, conform relatiei (11) va fi :

. (51)

In mod asemanator, folosind relatia de definitie (12) se poate calcula capacitatea de corectie C_c, cu observatia ca trebuie sa se tina seama daca codul este perfect sau cvasi perfect.

In cazul unui cod C(n,m) detector de erori, utilizat pe un CBS, probabilitatea unei erori nedetectabile (P_n) se calculeaza tinind cont ca eroarea este nedetectabila daca prin eronare se obtine un alt cuvint de cod nenul al lui C. In acest caz avem [Li-83] :

(52)

unde s-a notat cu A_i numarul de cuvinte de cod de pondere i din multimea C. Numerele A₀, A₁,, A_n formeaza distributia ponderilor lui C.

Observatie :

Pentru un cod C(n,m) de distanta de cod d, rezulta ca A₀, A₁,, A_d-1 sint zero.

Teoretic putem calcula distributia ponderilor pentru orice cod liniar (n,m) examinind cele 2^m cuvinte de cod. Totusi pentru n,m de valoare mare, calculul devine practic imposibil, astfel incit exceptind citeva coduri liniare scurte, pentru numeroase coduri cunoscute nu s-a deteminat inca distributia ponderilor, deci nu se cunoaste nici P_n.

Este posibila insa determinarea limitei superioare a probabilitatii unei erori nedetectate [Li-83]:

, (53)

deoarece

Relatia (53) arata ca exista coduri liniare (n,m) pentru care P_n descreste exponetial cu numarul bitilor de control (k).

Observatie :

Desi numarul codurilor bloc liniare este extrem de mare, numai o clasa restrinsa de coduri s-au dovedit a avea P_n satisfacind limita superioara 2^-k (codurile Hamming de ex.).

Un cod bloc C(n,m) corector de t erori, exceptind codurile perfecte, poate corecta numeroase combinatii de t+1 erori si chiar mai multe. Numarul combinatiilor corectabile este 2^k. In cazul transmisiei pe un CBS, probabilitatea de eroare a unui bloc la decodare este limitata superior de [Li-83] :

(54)

P in formula (54) reprezinta probabilitatea de decodare eronata a unui bloc. In cazul codurilor perfecte, relatia (54) se realizeaza la limita. Pentru a determina probabilitatea de eronare a unui bit dupa decodare p_d (BER- bit error rate) se pleaca de la relatia de definitie a p_d :