Cod liniar

Prelegerea 2

Coduri liniare

2.1 Matrice generatoare

Definitia 2.1 Fie q un numar prim si n N un numar natural nenul. Se numestecod liniar orice subspatiu liniar al lui Znq .Un subspatiu k-dimensional al lui Znq se numeste (n, k)- cod liniar peste alfabetulZq.

Sa notam n general cu An,k (An,k Znq ) un (n, k) - cod liniar. Elementele sale senumesc cuvinte-cod.

Fie n, k N, k < n. O codificare este o aplicatie injectiva : Zkq Znq , iarAn,k = (Z

kq ). Elementele lui Z

kq se numesc mesaje de informatie.

Deci, x Zkq este un mesaj de informatie scris cu caractere din alfabetul Zq.Daca transmitem succesiunea x de semnale printr-un canal de comunicatie, mesajuleste supus diverselor perturbari de canal care-l modifica. Ideea teoriei coduriloreste urmatoarea: n loc de a transmite elementele lui Zkq , sa lungim mesajulinformational scufundand (prin intermediul aplicatiei ) Zkq ntr-un spatiu liniarZnq (n > k) astfel ncat cele n k pozitii noi - numite pozitii de control - sa asigureredondanta necesara refacerii mesajului de informatie initial.

Astfel, cu pretul lungirii mesajului, se castiga protectia fata de (anumite tipuride) erori.

Observatii:

Din definitie rezulta ca un cod liniar de lungime n este un set A de cuvinte(secvente, siruri, vectori) de lungime n cu proprietatile:

a,b A = a+ b A; a A, t Zq = ta A.

Orice cod - liniar contine cuvantul cod nul 0 = (0, 0, . . . , 0). |Zq| = r = |An,k| = rk

An,k fiind un spatiu liniar k-dimensional, admite o baza formata din k vectori cu nelemente. Fie

e1, e2, . . . , en

13

14 PRELEGEREA 2. CODURI LINIARE

o astfel de baza. Atunci orice cuvant cod v An,k are forma

v =ki=1

uiei

unde (u1, u2, . . . , uk) Zkq este unic determinat.Cu alte cuvinte, k simboluri de informatie u1, . . . , uk Zq determina n mod

unic un cuvant - cod v An,k prin relatia de sus, si reciproc. Operatia de codificare face aceasta asociere biunivoca:

u = (u1, . . . , uk) Zkq v =ki=1

uiei An,k

Fiecare vector - cod ntr-un cod liniar va avea deci k simboluri de informatie; celelalten k simboluri se numesc simboluri de control.Definitia 2.2 Fie An,k un cod liniar cu baza e1, . . . , ek. Matricea

Gn,k =

e1e2. . .ek

se numeste matricea generatoare a codului.

Deci operatia de codificare este definita prin matricea generatoare:

u Zkq , (u) = uG.Exemplul 2.1 Matricea

G =

(1 0 0 1 10 1 0 0 1

)genereaza un (5, 2)-cod liniar peste Z2. Rangul ei este 2 (primele doua coloaneformeaza matricea unitate), deci cele doua linii ale lui G sunt cuvinte - cod liniarindependente.

Multimea mesajelor de de informatie este Z22 = {00, 01, 10, 11}. Inmultind fiecaremesaj cu matricea G se obtine spatiul liniar al cuvintelor - cod

A4,2 = {00000, 01001, 10011, 11010}.Functia de codificare este:

00 00000, 01 01001, 10 10011, 11 11010.Un cod liniar poate fi generat de mai multe baze posibile. Deci se pot construimai multe matrici generatoare pentru un (n, k)-cod liniar. Ele se pot transformauna n alta prin operatiile liniare obisnuite, definite pentru liniile unei matrici. Prinschimbarea matricii generatoare nu se schimba spatiul liniar al cuvintelor - cod, cinumai modalitatea de codificare (functia ). Cum prin termenul cod se ntelege deobicei spatiul liniar An,k, rezulta ca doua matrici diferite care se deduc una din altaprin operatii pe linii, reprezinta acelasi cod.

2.1. MATRICE GENERATOARE 15

Exemplul 2.2 Reluand Exemplul 2.1, prin adunarea liniei doi la prima linie seobtine matricea

G =

(1 1 0 1 00 1 0 0 1

)

Ea genereaza acelasi spatiu liniar A5,2, dar codificarea difera:

00 00000, 01 01001, 10 11010, 11 10011

Exemplul 2.3 Matricea

G =

1 1 0 0 0 00 0 2 2 0 01 1 1 1 1 1

genereaza un (6, 3)-cod liniar peste Z3. Aducand matricea la forma canonica, seobtine

G =

1 1 0 0 0 00 0 1 1 0 00 0 0 0 1 1

Toate cele 33 = 27 cuvinte ale acestui cod au urmatoarea proprietate: fiecare simboleste scris de doua ori. Din acest motiv, codul este numit cod cu repetitie.

Cea mai convenabila regula de codificare consta n scrierea simbolurilor de informatiesi suplimentarea lor cu n k simboluri de control. Aceasta corespunde matriciigeneratoare (unice)

G = (I|B)unde I este matricea unitate de ordin k, iar B este o matrice cu k linii si n kcoloane.

Definitia 2.3 Un cod liniar este numit sistematic daca admite o matrice genera-toare de forma G = (I|B) unde I este matricea unitate.

Definitia 2.4 Doua coduri liniare A si A de aceeasi lungime n se numesc echiva-lente daca pi Sn astfel ncat

v1v2 . . . vn A vpi(1)vpi(2) . . . vpi(n) A(s-a notat cu Sn multimea permutarilor de n elemente).

Exemplul 2.4 Codul din Exemplul 2.1 este un cod sistematic. Din codificare seobserva ca mesajul de informatie se afla n cuvantul - cod pe primele doua pozitii.

Codul cu repetitie din Exemplul 2.3 nu este sistematic. Totusi, folosind per-mutarea (1, 4, 6, 2, 5, 3) (se permuta simbolurile doi cu patru si trei cu sase) se ajungela un cod sistematic generat de matricea

G =

1 0 0 1 0 00 1 0 0 0 10 0 1 0 1 0


Teorema 2.1 Orice cod liniar este echivalent cu un cod liniar sistematic.

Demonstratie: Matricea generatoare G a unui (n, k) - cod liniar A are rangul k; deciea are k coloane liniar independente.

1. Sa presupunem ca primele k coloane ale lui G sunt liniar independente. DeciG = (X|Y ) unde Y este o matrice kk inversabila. Exista atunci o succesiunede operatii de linii care transforma X n matricea unitate. Aceeasi succesiunede operatii efectuate acum pentru toata matricea G va conduce la matriceaG = (I|Y ). Deoarece si G este matrice generatoare pentru codul A, rezultaca acesta este sistematic.

2. Fie (p1, p2, . . . , pn) permutarea care aduce coloanele liniar independente alematricii G pe primele k pozitii. Se obtine n acest fel o noua matrice G. FieA codul liniar obtinut prin codificarea cu matricea generatoare G. Atunci Asi A sunt echivalente, iar A este sistematic, conform cazului anterior. 2

2.2 Matrice de control

Definitia 2.5 Fie An,k un cod liniar generat de matricea G = Gk,n. Se numestematrice de control o matrice H = Hnk,n cu proprietatea GHT = 0.

Observatii:

Din definitie rezulta ca matricea de control H a unui cod liniar A are urma-toarea proprietate:

v A vHT = 0Lasam ca exercitiu demonstrarea acestei echivalente.

Prin transpunere, relatia de sus se poate scrie si HGT = 0. Aceasta nseamnaca si H este matricea generatoare a unui (n, nk) - cod liniar peste corpul Zq,cod pentru care G este matrice de control. Cele doua coduri astfel definite senumesc coduri duale. Cuvintele - cod din cele doua coduri duale sunt ortogo-nale (produsul lor scalar este zero). Intr-adevar, daca A si B sunt doua coduriduale generate de matricile G respectiv H, iar x A,y B sunt cuvinte -cod arbitrare, exista u,v cu x = uG,y = vH. In plus, xHT = 0,yGT = 0.

Atunci, xyT = uGyT = u(yGT )T = u0T = 0.

Exemplul 2.5 (7, 4) - codul liniar binar cu matricea generatoare

G =

1 0 0 0 0 1 10 1 0 0 1 0 10 0 1 0 1 1 00 0 0 1 1 1 1

are drept matrice de control

2.2. MATRICE DE CONTROL 17

H =

0 0 0 1 1 1 10 1 1 0 0 1 11 0 1 0 1 0 1

care la randul ei este matricea generatoare a unui (7, 3) - cod liniar binar.

Se verifica imediat relatia

GHT =

0 0 00 0 00 0 00 0 0

Un cod care coincide cu codul sau dual se numeste cod auto - dual.

Teorema 2.2 Un cod sistematic cu matricea generatoare G = (I|B) admite camatrice de control H = (BT |I).Demonstratie: Cele doua matrici unitate din scrierea lui G si H sunt de ordin krespectiv n k. Efectuand calculele, se obtine:

GHT = (I|B) B

I

= IB +BI = B +B = 02

Corolarul 2.1 Matricea de control a unui (n, k)-cod liniar are rangul n k.Teorema de sus permite un algoritm de calcul extrem de simplu al matricii de control,atunci cand se cunoaste matricea generatoare. Sa aratam aceasta pe un exemplu:

Exemplul 2.6 Plecand de la matricea generatoare construita n Exemplul 2.4, sepoate construi matricea de control (calculele se fac n Z3):

H =

1 0 0 1 0 00 0 1 0 1 00 1 0 0 0 1

= 2 0 0 1 0 00 0 2 0 1 0

0 2 0 0 0 1

.Aplicand acum permutarea inversa coloanelor lui H, se ajunge la matricea de con-trol a codului definit n Exemplul 2.3:

H =

2 1 0 0 0 00 0 0 0 1 20 0 1 2 0 0

Relatia xHT = 0 pe care o verifica orice cuvant - cod x An,k permite sa definimun cod si sub forma unui sistem de ecuatii. Astfel, An,k este un cod peste Zq dacasi numai daca elementele sale sunt solutii ale sistemului liniar xHT = 0.

Exemplul 2.7 Codul cu matricea de control H =

(1 1 0 1 01 1 1 1 1

)este definit ca multimea solutiilor binare (x1, x2, x3, x4, x5) ale sistemului

x1 + x2 + x4 = 0, x1 + x2 + x3 + x4 + x5 = 0


2.3 Sindrom

Fie codul liniar An,k Znq peste Zq, cu matricea de control H si a Znq . Se numestesindrom al vectorului a vectorul z cu n k componente obtinut prin relatia

zT = HaT ,

sau - echivalent - z = aHT .Observatie: z = 0 a An,k.Daca se transmite printr-un canal de comunicatie un cuvant a An,k pentru

care sindromul corespunzator verifica relatia z = aHT 6= 0, nseamna ca s-a detectatfaptul ca n timpul transmisiei au aparut erori.

Teorema 2.3 In Z2, sindromul receptionat este egal cu suma coloanelor din ma-tricea de control corespunzatoare pozitiilor perturbate.

Demonstratie: Fie a = (a1, a2, . . . , an) An,k cuvantul-cod transmis. Fara a res-trange generalitatea, sa presupunem ca au intervenit trei erori, pe pozitiile i, j, k,fiind receptionat vectorul

a = (a1, . . . , ai1, ai, ai+1, . . . , aj1, aj, aj+1, . . . , ak1, a

k, ak+1, . . . , an)

unde ai 6= ai, aj 6= aj, ak 6= ak. Avem0 = aHT = a1(h1) + . . .+ ai(hi) + . . .+ aj(hj) + . . .+ ak(hk) + . . .+ an(hn)pentru ca a An,k, iar (h1), . . . , (hn) sunt coloanele matricii H.Avem, de asemeneaaHT = a1(h1) + . . .+ ai(hi) + . . .+ a

j(hj) + . . .+ a

k(hk) + . . .+ an(hn)

Prin adunarea acestor doua egalitati se obtine:z = aHT = aHT +aHT = (0)+ . . .+(0)+ (hi)+ . . .+(hj)+ . . .+(hk)+ (0)+

. . .+ (0) = (hi) + (hj) + (hk). 2

2.4 Pondere, distanta Hamming

Pentru orice cuvant x Znq , se numeste pondere numarul w(x) de componentenenule. Evident, 0 w(x) n.

Pentru doua cuvinte x,y Znq , se numeste distanta Hamming ntre ele, numarul

d(x,y) = w(x y).

Ca o remarca, deoarece x y Znq , rezulta ca distanta Hamming dintre douacuvinte este ponderea unui cuvant din Znq .

Definitia 2.6 Se numeste distanta (Hamming) a codului liniar An,k Znq peste Zqcea mai mica distanta (Hamming) dintre elementele codului An,k, adica

d = minx,yAn,k,x6=y

d(x,y)

2.5. DETECTARE SI CORECTARE DE ERORI 19

Folosind proprietatea anterioara si faptul ca 0 An,k, rezulta cad = min

xAn,k,x6=0w(x).

Se poate verifica imediat ca d este o distanta cu ajutorul careia Znq se poate structuraca spatiu metric.

Teorema 2.4 Fie H matricea de control a unui cod liniar An,k. Codul are distantaminima d daca si numai daca orice combinatie liniara de d 1 coloane ale lui Heste liniar independenta si exista cel putin o combinatie liniara de d coloane liniardependente.

Demonstratie: Pentru orice cuvant a, cu w(a) = s, aHT este o combinatie liniarade s coloane ale lui H. Cum exista un cuvant - cod de pondere minima egala cudistanta d a codului, rezulta ca avem cel putin o combinatie de d coloane liniardependente ale lui H. O combinatie de mai putin de d coloane liniar dependente arconduce la contradictie. 2

Definitia 2.7 Pentru r > 0 si x Znq , definim sfera de raza r si centru x caSr(x) = {y|d(x,y) r}

Teorema 2.5 Fie An,k Znq un cod liniar peste Zq cu distanta Hamming d. Dacar =

[d 12

], atunci

x,y An,k,x 6= y, Sr(x) Sr(y) = .Demonstratie: Presupunem prin absurd ca exista z Znq , z Sr(x) Sr(y).Atunci d(x, z) r, d(y, z) r deci, conform inegalitatii triunghiului, d(x,y) d(x, z) + d(y, z) 2r = 2

[d12

]< d, ceea ce contrazice afirmatia ca d este distanta

codului An,k. 2Evident, n fiecare astfel de sfera exista un singur cuvant - cod: cel aflat n

centru.

Definitia 2.8 Un cod liniar An,k Znq de distanta d peste Zq este perfect daca

Znq =

xAn,kSr(x)

unde r =[d12

].

2.5 Detectare si corectare de erori

Fie An,k Znq un cod liniar peste Zq, de distanta d si t =[d12

]. Sa presupunem ca

s-a receptionat cuvantul z Znq ; va exista cel mult un cuvant x An,k astfel ncatz St(x) (n cazul codurilor perfecte, acest cuvant exista totdeauna).

In cazul (ideal) cand z = x, cuvantul a fost transmis fara erori (sau cu erorinedetectabile).


Daca z 6= x, atunci mesajul a fost perturbat (si avem o detectare de erori);n ipoteza ca numarul de erori aparute este minim si exista un x An,k astfel cad(x, z) t, atunci z provine din cuvantul - cod x - si se va transforma n acestaprin corectarea corespunzatoare a erorilor.

In celelalte cazuri, z sau nu se poate corecta, sau se corecteaza gresit, n altcuvant cod.

Aceasta ultima situatie nu apare la codurile perfecte.Metoda de detectare si corectare a erorilor descrisa mai sus se numeste decodi-

ficarea cea mai probabila. Pentru marea majoritate a codurilor liniare aceasta estesingura metoda utilizata.

Pentru orice cuvant e Znq formam multimeaVe = e+ A = {e+ v|v A}

Ve este multimea cuvintelor w = e+ v care pot fi receptionate la transmitereacuvantului cod v, atunci cand a actionat un vector - eroare e. e va fi numit eroare- tip.

In particular, A = 0+ A = V0.

Propozitia 2.1 Pentru orice a Ve, Va = Ve.Demonstratie: Din a Ve, rezulta ca exista x A cu a = e+ x. Deoarece x+A = A(evident, A fiind subspatiu liniar), avem Va = a+ A = e+ x+ A = e+ A = Ve. 2

Vom utiliza aceasta propozitie pentru definirea unei tehnici de decodificare.Daca vrem sa detectam o anumita eroare - tip e care modifica cuvintele din A

n cuvintele subspatiului Ve, atunci vor fi mai usor de depistat cuvintele din Ve cuponderea minima.

Pentru fiecare Ve se alege un cuvant numit reprezentantul lui Ve; acesta este unelement cu cea mai mica pondere din Ve.

Se construieste urmatorul tablou (numit tablou standard):

1. Pe prima linie se scriu cuvintele - cod, ncepand cu 0 (reprezentantul luiA = V0);

2. Pe prima coloana se scriu reprezentantii 0, e1, e2, . . .;

3. Pe linia cu reprezentantul ei, sub cuvantul cod xj se scrie cuvantulei + xj( mod q).

Exemplul 2.8 Fie matricea generatoare G =

(1 0 0 10 1 1 1

)peste Z2. Ea va cod-

ifica Z22 = {00, 01, 10, 11} n A4,2 = {0000, 1001, 0111, 1110}.Calculul multimilor Ve conduce la

V0000 = V1001 = V0111 = V1110V1000 = V0001 = V0110 = V1111V0100 = V1101 = V0011 = V1010V0010 = V1011 = V0101 = V1100

2.5. DETECTARE SI CORECTARE DE ERORI 21

Alegem ca reprezentanti pe 0000, 1000 (se poate si 0001), 0100, 0010. Tabloulstandard va fi:

0000 1001 0111 11101000 0001 1111 01100100 1101 0011 10100010 1011 0101 1100

Pentru receptie, acest tablou este ca un dictionar care se utilizeaza astfel: cu-vantul primit se decodifica n cuvantul - cod din capul coloanei pe care se afla.

De exemplu, daca se receptioneaza 1101, el se va decodifica n 1001.Evident, cuvintele de pe prima coloana se decodifica n ele nsele (ele nu au fost

perturbate de nici o eroare).

Pentru orice cod liniar, un dictionar complet de tipul celui de mai sus constituie ceamai simpla metoda de decodificare.

Problema apare atunci cand ntr-o multime Ve sunt mai multe cuvinte de pondereminima. Atunci tabela va decodifica corect numai eroarea - tip aleasa ca reprezen-tant.

Astfel, revenind la Exemplul 2.8, cuvantul receptionat 1111 se decodifica n 0111(considerand ca a fost alterat primul caracter).

Daca se ia nsa drept reprezentant pe linia a doua 0001 n loc de 1000, a doualinie din tabloul standard este

0001 1000 0110 1111

Atunci, 1111 se decodifica n 1110 (considernd ultimul caracter ca fiind cel alteratde canalul de transmisie). Care este cuvantul - cod corect transmis ? Acest lucru nupoate fi decis. Singurul lucru care poate fi facut este sa se aleaga drept reprezentantierorile - tip cele mai probabile.

Pentru un (n, k) - cod peste Zq, un dictionar complet consta din toate cele qn

cuvinte posibile, lucru destul de dificil deoarece n practica codurile sunt destul delungi (de exemplu n = 100, k = 80). De aceea este utilizata o alta maniera de lucrucare reduce mult marimea tabloului de lucru.

FieH matricea de control a unui (n, k) - cod liniar A; putem considera (Corolarul2.1) ca liniile lui H sunt vectori liniar independenti.

Teorema 2.6 Pentru orice e Znq , toate cuvintele din Ve au acelasi sindrom.

Demonstratie: Fie v A arbitrar si w = e+ v. AvemwHT = (e+ v)HT = eHT + vHT = eHT + 0 = eHT .

Deci toate cuvintele din Ve au sindromul egal cu sindromul lui e. 2

Invers, pentru fiecare sindrom - deci pentru fiecare cuvant s de lungime nk, sepoate determina un vector - eroare e avand sindromul s. Mai mult, s va fi ales astfelncat sa aiba pondere minima (conform decodificarii cele mai probabile). Pentru


aceasta, se rezolva sistemul de ecuatii liniare HeT = sT , care are solutie, deoareceliniile luiH sunt liniar independente. Din multimea solutiilor alegem una de pondereminima, cu ajutorul careia construim multimea Ve a tuturor cuvintelor de sindroms.

Pe baza celor de mai sus, se poate folosi urmatoarea procedura de decodificare:

1. La receptionarea unui cuvant w, se calculeaza sindromul s:

sT = HwT .

2. Se afla eroarea - tip e cu sindromul s.

3. Se considera cuvantul - cod corect ca fiind v = w e.

In acest fel, nu mai este necesar sa se retina tot tabloul standard; este suficientsa se stie reprezentantii subspatiilor Ve si sindromurile corespunzatoare.

Exemplul 2.9 Reluand codul definit n Exemplul 2.8, el are ca matrice de control

H =

(0 1 1 01 1 0 1

)Calculand sindromurile reprezentantilor, se ajunge la tabloul:

Sindrom Reprezentant00 000001 100010 001011 0100

care reprezinta o reducere cu 50% a datelor stocate.La receptionarea cuvantului 1101, i se calculeaza sindromul

(0 1 1 01 1 0 1

)1101

=(11

)

Repezentantul sindromului 11 este 0100. Efectuand operatia

1101 0100 = 1101 + 0100 = 1001(n Z2 scaderea este de fapt adunare) se ajunge la cuvantul transmis, anume 1001.

Exemplul 2.10 Sa consideram codul liniar peste Z3 definit de matricea de control

H =

(1 0 2 1 00 1 2 1 2

)

Sindromurile sunt cuvinte de lungime 2 peste Z3, deci n total noua cuvinte.Lista sindromurilor si a reprezentantilor este:

2.6. EXERCITII 23Sindrom Reprezentant00 0000010 1000001 0100022 0010011 0001002 0000120 2000012 1000121 20002

De remarcat ca un tablou standard pentru acest cod are dimensiunea 9 27 sicontine 243 cuvinte; volumul de date s-a redus deci cu 92%.

Sa presupunem ca s-a trimis cuvantul cod 21122 si s-a receptionat 11122.Sindromul este

(1 0 2 1 00 1 2 1 2

)

11122

=(20

)

deci e = 20000; decodificarea este

v = w e = 11122 20000 = 21122.

Decodificarea a fost corecta deoarece eroarea - tip aparuta a fost una din celeselectate prin reprezentanti.

2.6 Exercitii

2.1 Sa se construiasca coduri liniare care sa transforme cuvantul (a1, a2, . . . , an) Znq n:

1. (a1, a1, a1, a2, a2, a2, . . . , an, an, an);

2. (a1, b1, a2, b2, . . . , an, bn) unde b1 = a1, b+ 2 = a1 + a2, bn = a1 + . . .+ an;

3. (a1, 2an, 3a2, 4an1, . . .).

2.2 Un cod liniar peste Z5 are urmatoarea matrice generatoare:

G =

1 2 3 1 22 2 4 1 01 1 2 2 1

Sa se afle matricea de control.

2.3 Aceeasi problema pentru Z7.


2.4 Determinati daca urmatorul cod liniar binar este sistematic sau nu:

G =

1 1 0 0 0 00 0 1 1 1 10 0 0 0 1 1

Daca nu, gasiti un cod sistematic echivalent.

2.5 Gasiti matricea generatoare a unui cod liniar binar care are matricea de control:

H =

1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 0 1 0 0 0 1

2.6 Se da matricea de control

H =

1 1 0 1 0 11 1 0 0 1 01 0 1 1 0 0

a unui cod liniar binar.

Sa se decodifice mesajele 110110, 010100.

2.7 Descrieti dualul (6, 3) - codului binar descris de ecuatiile:

x1 = x4, x2 = x5, x3 = x6.

2.8 Fie A un cod liniar binar obtinut din toate sumele posibile ale cuvintelor101011, 011101, 011010.

1. Aflati o matrice de control a codului.

2. Aflati un tablou standard si decodificati 111011.

2.9 Demonstrati ca codul liniar binar descris de ecuatiile

x3 = x1 + x2, x4 = x1, x5 = x1 + x2

corecteaza o eroare. Construiti tabloul standard.

2.10 Construiti o tabela de sindromuri de decodificare pentru:

1. Codul cu repetitie de lungime 7;

2. Codul din Exercitiul 2.7;

3. Codul peste Z3 cu matricea generatoare:

G =

1 0 0 2 20 1 0 0 10 0 1 1 0

2.11 Fie un cod liniar An,k Znq si tabela de sindromuri de decodificare cores-punzatoare. Definim o operatie de decodificare : Znq An,k cu proprietatea:v An,k,e reprezentant din tabela, (v + e) = v. ( corecteaza erorile - tip dintabela de decodificare). Sa se arate ca atunci nu corecteaza nici o alta eroare - tip:daca e nu este un reprezentant din tabela, atunci exista v An,k cu (v + e) 6= v.

(Altfel spus, decodificarea cu sindromuri este optimala).

Cod liniar

Documents

Transcript of Cod liniar