Prelegerea 3

Coduri liniare - II

3.1 Capacităţi de detectare şi corectare de erori

După cum am văzut până acum, un cod liniar este un spaţiu liniar, codul dual este
complementul său ortogonal etc. Teoria codurilor este interesată ı̂nsă ı̂n depistarea
unor coduri cu proprietăţi deosebite ı̂n detectarea şi corectarea erorilor. Aceste
proprietăţi sunt legate ı̂n special de distanţa minimă a codului. Vom prezenta pentru
ı̂nceput câteva rezultate legate de diverse margini relativ la distanţă, numărul de
simboluri de control, informaţie etc.
Teorema 3.1 Un cod liniar An,k ⊂ Zqn are distanţa minimă d dacă şi numai dacă
poate detecta orice combinaţie de maxim d − 1 erori.
Demonstraţie: Dacă se transmite un cuvânt a ∈ An,k şi apar t(t < d) erori, se va
recepţiona cuvântul a + e ∈ Zqn cu w(e) = t.
Deoarece d(a, a + e) = t, rezultă a + e 6∈ An,k , deci se detectează eroare.
Reciproca este evidentă. 2
Teorema 3.2 Un cod liniar An,k ⊂ Zqn areh
distanţa
i
minimă d dacă şi numai dacă
poate corecta orice combinaţie de maxim d−1
2
erori.
Demonstraţie: Să presupunem prin absurd că d ≤ 2t şi vom arăta că există erori
- tip de pondere t (numite şi pachete de t erori) care nu pot fi corectate de codul
An,k . Această contradicţie
h i va duce la concluzia d ≥ 2t + 1, adică An,k poate corecta
d−1
orice pachet de t ≤ 2 erori.
Fie a, b ∈h An,ki cu d(a, b) = d şi i1 , i2 , . . . , id toţi indicii ı̂n care a diferă de b.
d+1
Alegând t = 2 , avem d ≤ 2t (t astfel ales este minim).
Să presupunem că se trimite a şi se recepţionează cuvântul a0 = (a01 , a02 , . . . , a0n )
unde 
 ai = bi dacă i 6= i1 , i2 , . . . , id ,

0
ai = ai dacă i = i1 , i3 , . . . ,


bi dacă i = i 2 , i4 , . . .
" # " #
0 d+1 d
Atunci, evident d(a, a ) = = t şi d(a0 , b) = ≤ t = d(a0 , a). Aceasta va
2 2
duce la decodificarea lui a ı̂n b - incorect.

25
26 PRELEGEREA 3. CODURI LINIARE - II

Să presupunem acum d ≥ 2t + 1. Atunci codul An,k poate corecta orice pachet
de t erori. Pentru a arăta aceasta, să presupunem că se trimite un cuvânt - cod
a şi se primeşte un cuvânt a0 cu d(a, a0 ) ≤ t. Pentru orice cuvânt cod b (deci cu
d(a, b) ≥ d ≥ 2t + 1) avem, conform inegalităţii triunghiului:

d(a, a0 ) + d(a0 , b) ≥ d(a, b) ≥ 2t + 1.

deci, d(a0 , b) ≥ 2t + 1 − d(a, a0 ) ≥ 2t + 1 − t = t + 1 > d(a, a0 ).

Deci, cu o decodificare cea mai probabilă, a0 se va decodifica ı̂n a. 2

Teorema 3.3 Distanţa minimă a unui (n, k) - cod liniar verifică relaţia

d ≤ n − k + 1.

Demonstraţie: Vom separa demonstraţia ı̂n două părţi:

A: Fie An,k un cod sistematic. Atunci primele k simboluri din orice cuvânt - cod
pot fi alese arbitrar. Fie v ∈ An,k cuvântul de forma v = 100 . . . 0vk+1 vk+2 . . . vn .
Evident, 0 < w(v) ≤ n − k + 1. Cum d este cea mai mică pondere a unui cuvânt -
cod nenul, rezultă inegalitatea cerută.
B: Fie An,k un cod liniar arbitrar şi A0n,k codul liniar sistematic echivalent. Se ob-
servă că cele două coduri au aceeaşi parametri n, k, d. Folosind acum A, inegalitatea
se obţine din nou. 2

Teorema 3.4 În orice cod liniar An,k peste Zq avem

nq k−1 (q − 1)
d≤ (marginea Plotkin)
qk − 1

Demonstraţie: Să considerăm elementele din An,k aşezate ca linii ale unui tablou. Se
obţine un tablou cu q k linii şi n coloane. Fiecare componentă nenulă din Zq apare
pe fiecare coloană ı̂n q k−1 linii. Atunci, suma ponderilor tuturor cuvintelor - cod
este egală cu nq k−1 (q − 1) deoarece fiecare componentă nenulă apare de q k−1 ori ı̂n
fiecare coloană şi avem q − 1 componente nenule distribuite pe n coloane.
Distanţa minimă a codului nu poate să depăşească ponderea medie a cuvintelor
codului, adică
nq k−1 (q − 1)
d≤
qk − 1
deoarece ı̂n An,k sunt q k − 1 cuvinte nenule. 2

Teorema 3.5 Fie An,k un cod liniar peste Zq care corectează orice combinaţie de
maxim t erori. Într-un asemenea cod sunt necesare cel puţin

n − k ≥ logq [1 + Cn1 (q − 1) + Cn2 (q − 1)2 + . . . + Cnt (q − 1)t ]

poziţii de control (marginea Hamming).

3.1. CAPACITĂŢI DE DETECTARE ŞI CORECTARE DE ERORI 27

Demonstraţie: Pentru ca An,k să corecteze orice combinaţie de cel mult t erori, este
necesar ca fiecare astfel de eroare - tip să fie reprezentată ı̂n tabloul standard, deci
să fie caracterizată printr-un sindrom distinct. Sunt q n−k sindromuri distincte, deci
acesta este numărul maxim de erori care pot fi corectate de cod. Din cele q n−k
sindromuri, 1 trebuie să fie pentru 0 erori, Cn1 (q − 1) - pentru erori - tip simple
(cuvinte e cu o singură componentă nenulă), Cn2 (q − 1)2 pentru erori duble etc.
Deci, este necesar ca

q n−k ≥ 1 + Cn1 (q − 1) + Cn2 (q − 1)2 + . . . + Cnt (q − 1)t .

Apoi se logaritmează. 2

Teorema 3.6 Dacă

1 2
n − k ≥ logq [1 + Cn−1 (q − 1) + Cn−1 (q − 1)2 + . . . + Cn−1
d−2
(q − 1)d−2 ]

atunci există un cod liniar An,k peste Zq cu distanţa minimă d (marginea Varşamov
- Gilbert).

Demonstraţie: Pentru ca să existe un cod liniar An,k peste Zq cu distanţa minimă d
este suficient (Teorema 2.4) ca orice coloană din matricea de control Hn−k,n să nu
fie combinaţie liniară a altor d − 2 coloane, ı̂n acest fel ne-existând nici o combinaţie
liniară ı̂ntre d − 1 coloane ale lui H. Această condiţie este echivalentă cu

q n−k − 1 ≥ Cn−1
1 2
(q − 1) + Cn−1 (q − 1)2 + . . . + Cn−1
d−2
(q − 1)d−2 .

Aici, q n−k − 1 reprezintă numărul total de coloane distincte nenule care pot apare
ı̂n matricea H. Semnificaţia termenilor din membrul drept este evidentă; astfel, de
2
exemplu Cn−1 (q − 1)2 reprezintă numărul combinaţiilor liniare cu coeficienţi nenuli
a două din cele n − 1 coloane etc.
Apoi se logaritmează. 2
Fie En,k un cod liniar peste Zq pentru care d ≥ 2t + 1 (deci cu capacitatea de a
corecta orice combinaţie de maxim t erori). Reamintim că ı̂n prelegerea precedentă
am definit pentru orice x ∈ An,k sfera centrată ı̂n x prin

St (x) = {y ∈ Zqn |d(x, y) ≤ t}.

Mai introducem şi suprafaţa (scoarţa) acestei sfere, definită:

At (x) = {y ∈ Zqn |d(x, y) = t}.

Vom nota numărul de elemente ale fiecăreia din cele două mulţimi prin
St = |St (x)|, At = |At (x)|
(valorile sunt aceleaşi pentru orice x ∈ Zqn ).
Au loc relaţiile evidente:
t
X
A t ≤ St , St = Ai .
i=0
28 PRELEGEREA 3. CODURI LINIARE - II

Deoarece sferele de rază t centrate ı̂n cuvintele codului An,k sunt disjuncte, avem
q k St ≤ q n .
Aici, q k reprezintă numărul de cuvinte - cod, iar q n - numărul total de cuvinte
din Zqn .
Din această relaţie se obţine imediat

n − k ≥ logq St ,

cunoscută sub numele de inegalitatea volumului. Ea mai poate fi găsită şi sub forma

k 1
≤ 1 − logq St .
n n
k
Raportul se numeşte rata de informaţie şi dă o măsură a cantităţii de informaţie
n
pe care o poartă un cuvânt - cod. O rată de informaţie mică (mai multe simboluri
de control) asigură o securitate mai mare a transmiterii datelor. În schimb, condiţii
practice de eficienţă cer o rată de informaţie cât mai mare (mai multă informaţie
pe unitatea de mesaj). Aceasta este una din solicitările contradictorii ale teoriei
codurilor.

3.2 Modificări ale codurilor liniare

Adesea este imposibil să se utilizeze un cod bun deoarece el nu satisface anumite
restricţii tehnice, cum ar fi lungimea sau rata de informaţie. De aceea este practic
să se facă anumite modificări asupra codurilor, care să nu afecteze proprietătile
principale de detectare şi corectare de erori.

Definiţia 3.1 Numim extensie a unui (n, k) - cod liniar A peste Zq , (n + 1, k) -

codul liniar A∗ obţinut din A prin adăugarea la fiecare cuvânt cod a1 a2 . . . an a unui
n+1
X
simbol nou an+1 cu proprietatea ai = 0 (mod q).
i=1

Observaţii:

• În cazul binar, noul caracter an+1 poartă numele bit de paritate.
Dacă H este matricea de control a codului An,k , atunci codul extins A∗n+1,k are
matricea de control
 
0
 .. 
 H . 
H∗ = 



 0 
1 1 ... 1 1 1
n
X
De fapt, ultima linie reprezintă ecuaţia xi = 1.
i=1
3.2. MODIFICĂRI ALE CODURILOR LINIARE 29

• Dacă un cod liniar binar A are o distanţă minimă impară d, atunci codul
extins are distanţa minimă d + 1. Într-adevăr, fie a = a1 a2 . . . an ∈ A cu
n
X
w(a) = d. Cum d este impar, rezultă ai = 1 (ı̂n Z2 ), deci an+1 = 1.
i=1
Cuvântul a0 = a1 a2 . . . an 1 ∈ A∗ , w(a0 ) = d + 1 şi nu se poate construi un alt
cuvânt - cod ı̂n A∗ de pondere mai mică.

Definiţia 3.2 Fie A un cod liniar de lungime n peste Zq .

1. ”Relaxarea” lui A este un cod liniar A de lungime n − 1 obţinut prin ştergerea
ultimului simbol din cuvintele lui A;

2. ”Completarea” lui A este un cod definit A∗ = A∪(A+1) (unde 1 este cuvântul

cu toate elementele 1, iar suma se face modulo q);

3. ”Expurgarea” lui A este codul A0 = {a ∈ A|w(a) ≡ 0 mod 2}.

Observaţii:
• Relaxarea este operaţia inversă extensiei.

• Prin completarea şi expurgarea codurilor liniare se obţin coduri liniare numai
ı̂n cazul binar. În celelalte cazuri, noile mulţimi rezultate nu sunt spaţii liniare.

Propoziţia 3.1 Prin completarea unui cod liniar binar An,k se obţine un cod liniar
binar An,k+1 cu un număr dublu de cuvinte - cod.

Demonstraţie: Completarea unui cod binar ı̂nseamnă adăugarea la cuvintele - cod

ale lui A a tuturor cuvintelor obţinute prin complementare (schimbarea lui 0 ı̂n 1 şi
a lui 1 ı̂n 0).
Fie Gk,n matricea generatoare a codului An,k . Se verifică uşor că matricea
 
G
 
G0 =  
1 1 ... 1 1

generează An,k ∪ (1 + An,k ). Acest cod are k + 1 poziţii de informaţie şi lungime
n. Fiecare din cele două submulţimi are un număr egal de elemente. 2

Propoziţia 3.2 Orice cod liniar binar are sau toate cuvintele - cod de pondere pară,
sau numărul cuvintelor - cod de pondere pară este egal cu al celor de pondere impară.

Demonstraţie: Fie A un cod liniar binar cu un cuvânt v1 de pondere impară. Să

presupunem că v1 , v2 , . . . , vr sunt toate cuvintele lui A; atunci A = A + v1 . Pentru
orice cuvânt - cod vi de pondere pară (impară), v1 + vi are pondere impară (pară).
Pentru aceasta, să presupunem că w(v1 ) = 2p + 1, w(vi ) = 2q iar vi şi v1 au 1 pe
r poziţii comune. Atunci w(vi + v1 ) = w(vi ) + w(v1 ) − 2r (pentru că 1 + 1 = 0)
= 2p + 1 + 2q − 2r = 2s + 1. Similar dacă vi are pondere impară.
Deci adunarea cu v1 defineşte o corespondenţă biunivocă ı̂ntre cuvintele - cod
de pondere pară şi cele de pondere impară, ceea ce completează demonstraţia. 2
30 PRELEGEREA 3. CODURI LINIARE - II

Corolarul 3.1 Expurgarea unui cod liniar binar A este tot A sau un cod liniar
având ca elemente jumătate din elementele lui A.
Matricea generatoare Gexp a lui Aexp se poate obţine din matricea G a lui A astfel:
dacă toate liniile lui G sunt vectori de pondere pară cele două coduri coincid. Altfel,
fie G = [e1 , e2 , . . . , er , er+1 , . . . , ek ]T ı̂n care - fără a micşora generalitatea, putem
presupune că primele r au pondere impară, iar celelalte k − r au pondere pară.
Atunci Gexp = [0, e2 + e1 , . . . , er + e1 , er+1 . . . , ek ]T .
Exemplul 3.1 Să construim codul A4,2 peste Z3 de matrice generatoare
à !
1 0 0 1
G= .
0 1 1 1
Ea codifică cele 9 elemente din Z32 ı̂n
A4,2 = {0000, 0111, 0222, 1001, 1112, 1220, 2002, 2110, 2221}.
Codul liniar relaxat A3,2 = {000, 011, 022, 100, 111, 122, 200, 211, 222} este generat
de matricea à !
1 0 0
Grel = .
0 1 1
Construcţia a fost posibilă deoarece prin eliminarea ultimei coloane, liniile rămase
sunt tot liniar independente. Dacă acest lucru nu este realizabil, se caută k cuvinte
- cod ı̂n An,k cu proprietatea că după eliminarea ultimei componente, ele sunt liniar
independente. Acestea formează liniile noii matrici generatoare.
Codul completat este
0000 0111 0222 1001 1112 1220 2002 2110 2221
1111 1222 1000 2112 2220 2001 0110 0221 0002
De remarcat că el nu este un spaţiu liniar (nu este ı̂nchis la adunarea din Z3 ).
Codul expurgat are cinci elemente: {0000, 1001, 1112, 2002, 2221}. Nici acesta
nu este cod liniar.
Exemplul 3.2 Să reluăm matricea generatoare din Exemplul 3.1, dar pentru un
cod liniar peste Z2 . Codul generat de G este A4,2 = {0000, 0111, 1001, 1110}.
Toate codurile modificate sunt ı̂n acest caz coduri liniare. Astfel
• Codul relaxat Arel = {000, 011, 100, 111} este generat de aceeaşi matrice Grel
din Exemplul 3.1.
• Codul completat Acom = {0000, 0111, 1001, 1110, 1111, 1000, 0110, 0001} este
un cod liniar generat de matricea
 
1 0 0 1
Gcom = 
 0 1 1 1 .
1 1 1 1

• Codul expurgat Aexp = {0000, 1001} este un cod liniar generat de matricea
à !
1 0 0 1
Gex = .
0 0 0 0
3.3. DETECTAREA ŞI CORECTAREA SIMULTANĂ A ERORILOR 31

3.3 Detectarea şi corectarea simultană a erorilor

Să ı̂ncepem cu un exemplu.

Exemplul 3.3 Fie (7, 4) - codul liniar binar cu matricea de control

 
0 0 0 1 1 1 1
 
H =  0 1 1 0 0 1 1 .
1 0 1 0 1 0 1

El are distanţa minimă d = 3, deci poate detecta 2 erori şi poate corecta o eroare
(Teoremele 3.1,3.2). Totuşi, codul nu poate realiza acest lucru simultan.
Mai precis, atunci când codul este utilizat pentru corectare de erori, erorile du-
ble scapă nedetectate. Astfel, dacă se trimite 0000000 şi se recepţionează 1010000,
sindromul este 010. Tabloul standard conduce la corectarea celui de-al doilea bit, şi
decodifică (incorect) ı̂n cuvântul - cod 111000.

Uneori ı̂nsă, se solicită ı̂n mod explicit un cod capabil să detecteze şi să corecteze
erori ı̂n acelaşi timp.

Definiţia 3.3 Un cod A de lungime n corectează t erori şi detectează s erori simul-
tan dacă orice cuvânt - cod v are următoarea proprietate:

∀w ∈ Zqn [d(w, v) ≤ s =⇒ ∀a ∈ A \ {v}, d(w, a) > t].

În această situaţie, detectarea şi corectarea simultană a erorilor se realizează astfel:
la recepţionarea unui cuvânt w ∈ Zqn se caută cel mai apropiat cuvânt - cod v (ı̂n
sensul distanţei Hamming). Dacă d(w, v) ≤ t atunci cuvântul se corectează ı̂n v;
altfel, se anunţă că cel puţin s simboluri sunt modificate.
Justificarea acestui procedeu rezultă imediat din definiţie.

Teorema 3.7 Un cod corectează t erori şi detectează s erori simultan dacă şi numai
dacă
d ≥ t + s + 1.

Demonstraţie: A: Să presupunem d ≥ s + t + 1. Fie v un cuvânt - cod şi w ∈ Zqn

cu d(v, w) ≤ s. Pentru orice cuvânt - cod v0 (v0 6= v) avem d(v, v0 ) ≥ d ≥ t + s + 1.
Folosind inegalitatea triunghiului,

d(v, w) + d(w, v0 ) ≥ d(v, v0 ) ≥ s + t + 1,

se deduce

d(w, v0 ) ≥ t + s + 1 − d(v, w) ≥ t + s + 1 − s = t + 1.

Deci, condiţia din definiţie este ı̂ndeplinită.

B: Să presupunem prin absurd d < t + s + 1. Fie v, v0 două cuvinte - cod cu
d(v, v0 ) = d ≤ t + s. Construim cuvântul w din v ı̂nlocuind primele s simboluri
ı̂n care acesta diferă de v0 , cu valorile lor din v0 . Atunci d(v, w) = s şi d(v0 , w) =
d − s ≤ t + s − s = t, ceea ce contrazice condiţia din definiţie. 2
32 PRELEGEREA 3. CODURI LINIARE - II

Exemplul 3.4 Să considerăm (8, 4) - codul liniar binar generat de matricea
 
1 0 0 0 1 1 1 0
 0 1 0 0 1 1 0 1 
 
G= .
 0 0 1 0 1 0 1 1 
0 0 0 1 0 1 1 1

El are distanţa minimă d = 4, deci - conform Teoremei 3.2 poate corecta maxim
o eroare, iar conform Teoremei 3.7 poate corecta o eroare şi detecta simultan două
erori.
Astfel recepţionarea cuvântului 11110010 conduce la corectarea sa ı̂n 10110010
(deoarece d(11110010, 10110010) = 1 şi 10110010 este cuvânt - cod).
În schimb recepţionarea cuvântului 00001111 anunţă că au apărut cel puţin două
erori. În această situaţie, nu mai puţin de patru cuvinte - cod (00010111, 00101011,
01001101, 10001110) sunt situate la distanţa 2 de cuvântul primit.

Exemplul 3.5 Codul binar cu repetiţie de lungime 7 (care are 2 elemente) poate
realiza una din condiţiile:

• Corectează 3 erori;

• Detectează 6 erori;

• Corectează 2 erori şi detectează 4 erori simultan.

3.4 Probabilitatea nedetectării erorilor

Să ne punem următoarea problemă: care este probabilitatea ca la transmiterea unui
cuvânt - cod a să fie recepţionat alt cuvânt - cod b (b 6= a). Altfel spus, care este
probabilitatea ca o eroare să scape nedetectată ?
Notând cu e = b − a, o eroare este nedetectată dacă şi numai dacă e este un
cuvânt - cod nenul.
Vom considera un canal de transmisie binar simetric, adică un canal ı̂n care
singurele simboluri transmise sunt 0 şi 1, iar probabilitatea p (0 ≤ p ≤ 1) ca la
transmiterea lui 0 să fie recepţionat 1 este egală cu probabilitatea ca la transmiterea
lui 1 să se recepţioneze 0. Într-un astfel de canal, dacă w(e) = i (adică au fost
perturbate la transmisie i caractere), probabilitatea de apariţie a erorii - tip e este
pi q n−i , unde q = 1 − p. Notând cu Ai numărul cuvintelor - cod cu ponderea i, prob-
abilitatea Pned a unei erori nedetectabile este suma probabilităţilor pi q n−i , fiecare
termen apărând de Ai ori pentru i = 1, 2, . . . , n. Formal,
n
X
Pned = Ai pi q n−i
i=1

n
X
Cum A1 = A2 = . . . = Ad−1 = 0, suma se reduce la Pned = pi q n−i .
i=d
3.5. IDENTITATEA MACWILLIAMS 33

Exemplul 3.6 Să considerăm un cod care are un cuvânt de pondere 0, câte şapte
cuvinte de pondere 3 şi 4 şi un cuvânt de pondere 7. Atunci
Pned = 7p3 q 4 + 7p4 q 3 + p7
Dacă folosim acest cod ı̂ntr-un canal binar simetric cu eroare de probabilitate
p = 0.01, avem
Pned = 7(0.01)3 (0.99)4 + 7(0.01)4 (0.99)3 + (0.01)7 ≈ 7 × 10−6
deci - ı̂n medie - apar cam şapte erori nedetectabile la un milion de cuvinte
transmise.

Definiţia 3.4 Polinomul de variabilă x ∈ [0, 1] definit

n
X
P (x) = A i xi
i=0

unde Ai este numărul de cuvinte din An,k de pondere i, se numeşte ”numărătorul

de ponderi” al codului An,k .

Exemplul 3.7 Codul definit ı̂n Exemplul 3.2 are numărătorul de ponderi
P (x) = 1 + x2 + 2x3

Propoziţia 3.3 Fie An,k un cod liniar binar cu numărător de ponderi P (x). Proba-
bilitatea apariţiei unei erori nedetectabile la folosirea codului An,k ı̂ntr-un canal binar
simetric este " Ã ! #
n p
Pned = q P −1 .
q

Demonstraţie: Relaţia de definiţie a lui Pned se poate rescrie

n n
à !i
X X p
qn Ai pi q −i = q n Ai .
i=1 i=1 q
Deoarece A0 = 1 (singurul cuvânt - cod de pondere 0 este cuvântul - cod 0, expresia
devine ı̂n continuare  Ã !i  " Ã ! #
X n
n p  n p
Pned = q Ai −1 =q P −1 . 2
i=0 q q

3.5 Identitatea MacWilliams

În acest paragraf vom arăta un rezultat care face posibilă determinarea numără-
torului de ponderi PA⊥ al dualului A⊥ unui cod liniar A, direct din numărătorul de
ponderi PA al codului A.
Propoziţia 3.4 Fie v ∈ Z2n şi A un (n, k) - cod liniar binar. Atunci are loc egali-
tatea (
1 X vw 1 dacă w ∈ A⊥
(−1) =
2k v∈A 0 altfel
34 PRELEGEREA 3. CODURI LINIARE - II

Demonstraţie: Dacă w ∈ A⊥ atunci evident, (−1)vw = (−1)0 = 1 şi suma este egală
cu numărul de cuvinte - cod din A, care este 2k .
Să presupunem acum că w 6∈ A⊥ , deci există un cuvânt - cod v0 ∈ A cu v0 w = 1.
Vom arăta că ı̂n acest caz, numărul cuvintelor - cod ortogonale pe w este egal cu
cel al cuvintelor - cod ne-ortogonale pe w (şi deci suma din formulă este 0).
Fie v1 , v2 , . . . , vr toate cuvintele - cod ortogonale pe w. Facem afirmaţia că
atunci v1 + v0 , v2 + v0 , . . . , vr + v0 sunt toate cuvintele - cod ne-ortogonale pe v0 .
Într-adevăr:
1. ∀i (1 ≤ i ≤ r) (vi + v0 )w = vi w + v0 w = 0 + 1 = 1;

2. Dacă v ∈ A verifică relaţia vw = 1, atunci v − v0 este un cuvânt cod -

ortogonal pe w, deci v − v0 = vi pentru un anumit i. 2

Teorema 3.8 Pentru orice (n, k) - cod liniar binar A are loc relaţia (identitatea
MacWilliams):
µ ¶
(1 + x)n 1−x
PA⊥ (x) = PA .
2k 1+x
Demonstraţie: Să rescriem numărătorul de ponderi sub o formă puţin diferită:
n
X
B(x, y) = Ai xi y n−i .
i=0
à !
n x
Evident, deoarece P (x) = B(x, 1) şi B(x, y) = y P , cele două expresii sunt
y
echivalente.
În notaţia cu polinomul B, identitatea MacWilliams se scrie
1
BA⊥ (x) = BA (y − x, y + x).
2k
Cu ajutorul ponderii cuvintelor - cod, numărătorul de ponderi are forma
n
X X
BA (x, y) = Ai xi y n−i = xw(a) y n−w(a)
i=0 a∈A

Prelucrând membrul drept al identităţii MacWilliams, avem:

X n
XY
BA (y − x, y + x) = (y − x)w(a) (y + x)n−w(a) = [y + (−1)ai x] .
a∈A a∈A i=1

În mod analog, membrul stâng se scrie:

X
BA⊥ (x, y) = xw(a) y n−w(a) .
a∈A⊥

Folosind Propoziţia 3.4, el se poate reformula:

" #
X 1 X
BA⊥ (x, y) = (−1)av xw(a) y n−w(a) .
a∈Z2n 2k v∈A
3.5. IDENTITATEA MACWILLIAMS 35

Expresia din paranteze este 0 pentru toate cuvintele a care nu sunt ı̂n A⊥ . Deci
1 X X
BA⊥ (x, y) = k
(−1)va xw(a) y n−w(a) .
2 v∈A a∈Z k
2

Suma interioară se face după toate secvenţele binare a de lungime n. Vom ordona
această sumă după ponderile lui a: pentru a = 0 sumandul este y n ; pentru cu-
vintele a de pondere 1 avem: [(−1)a1 + (−1)a2 + . . . + (−1)an ]xy n−1 etc; ı̂n final,
pentru ponderea n avem [(−1)a1 + . . . + (−1)an ]xn . Suma tuturor acestor sumanzi
n
X
[(−1)ai1 + . . . + (−1)aik ]xk y n−k se observă uşor că este egală cu
k=0
n
Y
[y + (−1)a1 x][y + (−1)a2 x] . . . [y + (−1)ak x] = [y + (−1)ai x]. Deci
i=1
n
1 XY 1
BA⊥ (x, y) = k [y + (−1)ai x] = k BA (y − x, y + x). 2
2 a∈A i=1 2

Exemplul 3.8 Să considerăm codul din Exemplul 3.2 al cărui numărător de ponderi
a fost dat ı̂n Exemplul 3.7. Pentru codul dual,"numărătorul de ponderi este#
µ ¶ µ ¶ µ ¶
(1 + x)4 1−x (1 + x)4 1−x 2 1−x 3
PA⊥ (x) = PA = 1 + + 2 =
22 1+x 4 1+x 1+x
(1 + x)4 + (1 + x)2 (1 − x)2 + 2(1 + x)(1 − x)3 4 + 4x2 + 4x3
= = = 1 + x2 + x3 .
4 4
Deci cele două coduri au acelaşi numărător de ponderi. Aceasta nu ı̂nseamnă
ı̂nsă că cele două coduri coincid (şi deci codul ar fi auto - dual); a avea acelaşi
numărător de ponderi este doar o condiţie necesară, nu şi suficientă pentru ca un
cod să coincidă cu dualul său.

Exemplul 3.9 Fie codul cu repetiţie de lungime pară n A = {00 . . . 0, 11 . . . 1};

numărătorul lui de ponderi este PA (x) = 1 + xn . Codul dual are numărătorul de
ponderi · µ ¶ ¸
(1 + x)n 1−x n
PA⊥ (x) = 1+ = 1 + Cn2 x2 + Cn4 x4 + . . . + xn .
2 1+x
Rezultă din această formă că dualul codului cu repetiţie este codul liniar al cu-
vintelor de pondere pară.
36 PRELEGEREA 3. CODURI LINIARE - II

3.6 Exerciţii
3.1 În Z2n notăm cu x cuvântul obţinut din x prin permutarea caracterelor 0 şi 1
ı̂ntre ele. Să se arate că pentru orice a, b ∈ Z2n :

1. a + b = a + b;

2. a + b = a + b = a + b;

3. d(a, b) = d(a + b) = w(a + b).

3.2 Descrieţi codurile modificate obţinute din codul liniar binar cu matricea genera-
toare  
1 1 1 0 0
 
G= 0 0 1 1 1 
1 1 1 1 0

3.3 Aceeaşi problemă pentru codul peste Z3 definit prin

 
1 0 0 2 2
 
G =  0 1 0 0 1 .
0 0 1 1 0

3.4 Fie A un (n, k) - cod liniar binar şi A0 (n, k − 1) - codul obţinut din A prin
expurgare. Ce relaţie există ı̂ntre matricile de control ale celor două coduri ?

3.5 Arătaţi cum poate codul binar cu repetiţie de lungime 7 să corecteze două erori
şi să detecteze 4 erori simultan. Câte erori poate detecta dacă corectează o eroare ?

3.6 Fie A (15, 4) - codul liniar binar ı̂n care fiecare coloană i din matricea genera-
toare este scrierea binară a lui i sub forma unui vector cu 4 componente. Să se
determine distanţa minimă, numărătorul de ponderi şi numărătorul de ponderi al
codului dual.

3.7 Fie A un (2k + 1, k) - cod binar astfel ca A⊥ ⊂ A. Descrieţi A⊥ \ A.