Aurelian Claudiu VOLF [610156]

Aurelian Claudiu VOLF
Coduri

Universitatea „Al. I Cuza” Ia și
2011

Cuprins
Cuprins ………………………………………………………………………………………………………… ……… 2
Prefață………………………………………………………………………………………………………………. … 3
Unele nota ții …………………………………………………………………………………………………………. 5
I. Coduri corectoare de erori…………………………………………………………………………………. 6
II. Coduri liniare………………………………………………………………………………………………. … 14
III. Corpuri finite……………………………………………………………………………………………… … 26
IV. Coduri liniare: codare și decodare …………………………………………………………………. 37
V. Construc ții de coduri noi din coduri existente………………………………………………….. 44
VI. Coduri ciclice ………………………………………………………………………………………………. .. 49
VII. Aplica ții: pachete de erori, Compact Disc, CRC ……………………………………………. 55
Index ………………………………………………………………………………………………………….. ……… 65
Bibliografie……………………………………………………………………………………………………. …… 68

3 Prefață
“Error correction is one of the most advanced areas in
the entire field of digital audio. It is purely because of
error-correction techniques that reliable digital
recordings can be made, despite the frequent
occurrence of tape dropouts .” [ Digital Audio
Technology , Edited by Jan Maes and Marc Vercammen,
Focal Press 2001]

Codurile corectoare de erori (pe scurt, codurile) corecteaz ă sau detecteaz ă erori care apar
inevitabil la transmiterea unui mesaj pe un canal cu zgomot. Aceast ă detectare/corectare se
realizează prin introducerea de redundan ță în mesaj (adic ă în loc de a transmite mesajul
original, un mesaj mai lung este transmis, în speran ța că simbolurile ad ăugate vor ajuta la
detecția/corectarea erorilor). Orice comunicare digital ă, orice stocare de date folose ște o
formă de coduri corectoare de erori. Compact di scurile, discurile dure, memoriile interne ale
calculatoarelor, memoriile flash, DVD-urile etc sînt protejat e împotriva alter ării accidentale a
datelor folosind astfel de coduri. Se poate spune c ă aceste dispozitive, și multe altele, nu ar
putea func ționa fără coduri corectoare de erori.
Deci, codurile ajut ă la corectarea de erori, dar nu ofer ă confiden țialitate. Confiden țialitatea
se realizeaz ă de către criptografie .
Multe monografii de teoria codurilor au mai mu lt de 700 de pagini. Acest curs introductiv,
din motive de spa țiu, nu include multe teme care sînt foarte importante. Totu și, avem
convingerea c ă după parcurgerea acestui curs, cititorul va fi familiarizat cu ideile principale,
cu metodele, aplica țiile, limitările și problemele teoriei codurilor. Acest domeniu este în plin ă
evoluție și multe rezultate sau metode apar an de an. De aceea, acest curs trebuie v ăzut mai
mult ca o invita ție la lecturi ulterioare și cercetare în arii mai restrînse care sînt de interes
pentru cititor.
Sperăm că acest curs va dezv ălui măcar o parte din uimitoarea cantitate de inventivitate și
de frumuse țe matematic ă din spatele multor lucruri pe care le consider ăm normale: retragerea
de bani de la un ATM, trimiterea unui email, ascultarea unui CD, o convorbire pe telefonul
mobil. Toate aceste tehnologii nu ar fi posibile f ără teoria codurilo r, criptografie, și
matematica din spatele lor.
Cititorul român trebuie avertizat c ă practic toat ă literatura din domeniul teoriei codurilor
este în englez ă. Multe din no țiunile folosite sînt de dat ă foarte recent ă și unele nu au avut timp

4

să fie incluse în literatura româneasc ă, oricum foarte restrîns ă. De aceea, este necesar ă
familiarizarea cu terminologia englez ă, echivalentele române ști ale multor denumiri nefiind
încă standardizate.

5
Unele nota ții
– | A | desemneaz ă cardinalul mul țimii A (numărul elementelor lui A, dacă A este finită).
– x := y înseamnă „x este egal prin defini ție cu y” (unde y este deja definit) sau „notăm pe
y cu x”.
– † marcheaz ă sfîrșitul sau absen ța unei demonstra ții.
– bxc este cel mai mare întreg care este mai mic sau egal cu num ărul real x (partea
întreagă a lui x)
– ⌈x⌉ = min { n ∈ Z | x ≤ n} este cel mai mic întreg mai mare sau egal decît num ărul real
x.
– M(k, n, F ) este mul țimea matricelor de tip k×n peste inelul F.
– AT este transpusa matricei A.
– N este mulțimea numerelor naturale: 0, 1, 2, …
– Irr(x, K) este polinomul minimal al elementului algebric x peste corpul K.
– Z este mulțimea numerelor întregi : 0, 1, 2, − 1, − 2, …
– Zn = {0[, 1[, …, n − 1[ } este inelul claselor de resturi modulo n, cu adunarea și înmulțirea
mod n.
– S(X) = {σ : X → X | σ este bijectiv ă} este mul țimea permut ărilor mulțimii X. Este grup
cu compunerea func țiilor.
– Sn este grupul permut ărilor mulțimii {1, 2, …, n}. Are n! = 1·2·…· n elemente.
– u||v este concatenarea șirurilor u și v.
– k
nnC
k⎛⎞=⎜⎟⎝⎠ = combinări de n luate cîte k = !
!( )!n
kn k −

6
I. Coduri corectoare de erori
Fie A o mulțime finită, numită alfabet , ale cărei elemente le numim simboluri . Prin
„informație digital ă” (sau mesaj peste A ) înțelegem un șir de simboluri (elemente) din
alfabetul A. Astfel, orice fraz ă dintr-o limb ă dată este un mesaj (informa ție digitală). Orice șir
de litere, chiar f ără sens, este mesaj. De exemplu, 011110101100 este un șir de simboluri din
alfabetul {0,1} (în acest caz, simbolurile se numesc biți). Acest mesaj este un mesaj binar ,
căci alfabetul are dou ă simboluri. Un alfabet cu q simboluri se nume ște alfabet q-ar.
Transmiterea unei informații digitale1 între dou ă puncte diferite în spațiu (de exemplu o
transmisie de date pe o linie telefonic ă) sau în timp (stocarea pe un suport material cum ar fi
un compact disc, pentru o citire ulterioar ă), este supus ă erorilor cauzate de o varietate de
factori: zgomot pe linia telefonic ă, deteriorarea suportu lui fizic al informa ției etc. Se impune
găsirea unui procedeu prin care mesajul s ă poată ajunge în form ă corectă la receptor (sau
receptorul s ă poată detecta eventualele erori și să ceară retransmisia mesajului).
Fixăm un alfabet A cu q simboluri (alfabet q-ar).
Ideea care st ă la baza teoriei codurilor bloc corectoare de erori este următoarea: se fixeaz ă
k, n ∈ N*, cu k < n. Se împarte mesajul original în „blocuri” (numite „ cuvinte ”) de k
simboluri. Fiec ărui cuvînt2 de lungime k i se asociaz ă un cuvînt mai lung, de lungime n, după
o lege prestabilit ă; cele n − k simboluri „în plus” sînt puse pentru detectarea și eventual
corectarea erorilor ce pot ap ărea în transmisie. Pe canal se transmite cuvîntul de n simboluri,
la recepție urmînd ca, prin ana lizarea cuvîntului recep ționat, să se decidă dacă au apărut erori
(sau să se reconstituie cu vîntul transmis).
1 Exemplu. Fie A = {0, 1} (alfabet binar ). O idee simpl ă și nu prea eficient ă de codare
pentru corectarea erorilor este de a transmite fiecare bit de 3 ori, urmînd ca decodarea s ă se
facă după „regula majorit ății”. Mai precis, lu ăm k = 1, n = 3 și stabilim urm ătorul procedeu de

1 Transmiterea de sunete, imagini, texte etc. ca un șir de 0 și 1 pare azi evident ă, dar în anii 1940 a fost o idee
revoluționară și îi aparține lui Claude Shannon (1916-2001), matematician american, unul din fondatorii teoriei
informației (articolul A mathematical theory of communication, 1948).
2 Prin cuvînt de lungime k se înțelege un k-uplu de simboluri din A (un element din Ak).

7
codare: 0 este codat ca 0 00, iar 1 ca 111. Astfel, dac ă mesajul original este 0101, el va fi codat
ca 000111000111. S ă presupunem c ă acest mesaj este afectat de erori pe canal, încît la
recepție se prime ște 001111000011. La decodare, fiecare grup de 3 bi ți este tratat individual:
de exemplu grupul 001 este decodat în 0 (se presupune c ă 001 provine din 000 în care unul
din 0 a devenit 1), 011 este decodat în 1 etc. Acest procedeu de co rectare a erorilor func țio-
nează atît timp cît nu apare mai mult de o eroare la fiecare grup de trei simbolur i transmise.
Acest cod se nume ște codul (binar) de repeti ție de lungime 3.
Modelăm o situa ție de tipul descris, astfel: transmițătorul trimite un mesaj către receptor
pe un canal de transmisie . Mesajul este un șir finit de simboluri din alfabetul A. Orice șir de
simboluri poate fi mesaj3. Presupunem c ă o eroare cauzează receptarea altui simbol decît cel
transmis (dar nu „pierderea” simbolului în ti mpul transmisiei). Posibilitatea de apari ție de
erori pe canal este modelat ă de o funcție de tranzi ție P : A × A → [0, 1], cu semnifica ția că
∀x, y ∈ A, P(y, x) reprezint ă probabilitatea ca la tr ansmiterea simbolulului x, la recepție să fie
primit simbolul y.
Unul din cele mai r ăspîndite modele pentru un canal de transmisie este canalul q-ar
simetric de probabilitate p :
– A are q elemente (este un „ alfabet q -ar”);
– funcția de tranzi ție P are proprietatea c ă P(y, x) = p, ∀y, x ∈ A cu y ≠ x. Altfel spus,
probabilitatea de apari ție a unei erori (simbolul primit difer ă de cel trimis) este ( q − 1)p,
indiferent de simbolul transmis (de unde și denumirea de canal simetric ) și indiferent de locul
simbolului în mesaj (canal „fără memorie” ). Deci, probabilitatea ca un simbol transmis x să
fie recepționat corect este P(x, x) = 1 − (q − 1)p. Se presupune c ă 0 ≤ p < 1/2(q − 1) (altfel
este mai probabil s ă se recep ționeze un simbol eronat decît cel corect!). Dac ă q = 2, se
vorbește de un canal binar .
Spunem c ă un canal este canal qSC(p) dacă este un canal q-ar simetric, f ără memorie, de
probabilitate p.
Formalizăm ideea de codare bloc de mai sus: se fixeaz ă k, n ∈ N, cu k ≤ n; se dă o funcție
injectivă E : Ak → An care codează fiecare a = a1…ak ∈ A k într-un cuvînt cod c = c1…cn ∈ A n.
(Un element oarecare din A n, (x1, …, xn), (unde xi ∈ A,∀i) îl scriem mai simplu x1…xn.)
Mulțimea C := E(Ak) = {E(a1…ak) | a1…ak ∈ Ak} a tuturor cuvintelor cod se nume ște cod
(în cazul nostru, cod de tip [n, k] peste A). Observ ăm că |C| = q k. Dacă mesajul a1…ak este o
parte a cuvîntului cod c1…cn = E(a1…ak) (de obicei c1…cn = a1…ak p1…pn − k, unde p1…pn − k

3 Desigur, acest lucru e fals dac ă se transmit numai mesaje din limba român ă, de exemplu. Îns ă această
presupunere e valabil ă dacă se efecueaz ă în prealabil o compresie fără pierderi a mesajului, lucru curent în
practica transmisiei de date (de exemplu compresiile zip, ra r, lha etc). Acest procedeu, formalizat de Huffman, se
bazează pe o analiz ă statistică a mesajului și codarea simbolurilor cele mai probabile în șiruri scurte și a celor
mai puțin probabile în șiruri mai lungi.

8

se numesc simboluri de paritate sau simboluri redundante ), codarea ( și codul C) se nume ște
sistematic( ă).
Pentru func ționarea codului trebuie dat ă și o funcție de decodare D : An → C, care asociaz ă
oricărui cuvînt x din An cuvîntul cel mai probabil transmis D(x) ∈ C. Evident, D(c) = c,
∀c ∈ C. O codare sistematic ă are avantajul c ă mesajul original este recuperat prin simpla
eliminare a simbolurilor redundante.
Este utilă și o accepție mai largă a noțiunii de cod:
2 Definiție. Fie n ∈ N. Un cod (bloc) de lungime n peste alfabetul A este o submul țime C a
lui An. Elementele lui C se numesc cuvinte cod . Dacă |A| = q, C se numește cod q-ar .
Un cod bloc de tip [ n, k] transform ă orice bloc de k simboluri într-un cuvînt cod de
lungime mai mare n, ceea ce va permite (se sper ă) detecția sau corec ția erorilor. Îns ă acest
procedeu mărește lungimea mesajelor transmise (ceea ce nu este de dorit). Pentru a m ăsura
eficiența unui cod din acest punct de vedere, se define ște rata de transmisie a unui cod C de
tip [n, k] ca fiind R(C) := k/n. Rata măsoară proporția de simboluri care poart ă informație
(restul sînt simboluri redundante , care folosesc la detec ție sau corectare de erori). Dac ă C este
doar o submul țime a lui An, ca în Def. 2, rata e definită ca R(C) := log q|C|/n (de ce?).
Observați că pentru un cod de tip [ n, k]q, cele dou ă definiții coincid. Rata codului de repeti ție
de lungime 3 este 1/3.
3 Exemplu. Codul binar de paritate P de lungime 9 este construit astfel: fiec ărui mesaj de
8 biți i se adaug ă un bit de paritate astfel încît în cuvîntul de 9 bi ți care rezult ă să conțină un
număr par de bi ți egali cu 1. Aceasta revine la a spune c ă suma (în Z2) a celor 9 bi ți este 0.
Deci, P = {x1… x8x9 ∈ Z29 | x1 + … + x9 = 0}. Cite cuvinte are P? Care e rata sa?
Posibilitatea unui cod C de a corecta erori se bazeaz ă în întregime pe ideea c ă, dacă un
cuvînt cod c ∈ C este afectat pe canalul de transmisie de (un num ăr mic de) erori, cuvîntul
receptat c
t ≠ c nu este cuvînt cod (nu apar ține lui C), dar este „suficient de apropiat” de c încît
să putem reconstitui c din ct. Acest lucru este posibil doar dac ă ct nu este el însu și un alt
cuvînt cod sau nu e „mai ap ropiat” de alt cuvînt cod c' !
Aceste idei se pot formula riguros.
4 Definiție. Fie A o mulțime nevid ă. Distanța Hamming 4 pe An se define ște astfel:
∀ x = (x1, …, xn), y = (y1, …, yn), d(x, y) := |{i | 1 ≤ i ≤ n, xi ≠ yi}|.
Deci, distan ța între dou ă cuvinte este numărul de locuri în care cuvintele difer ă.

4 În onoarea lui Richard Hamming (1915-1998), matematician american, fondator, al ături de Shannon, al
teoriei informa ției (articolul Error detecting and error correcting codes , 1950).

9
5 Propozi ție. Distanța Hamming d : An × An → R este o distan ță (o metrică) pe An, adică:
a) ∀x, y ∈ An, avem d (x, y) = d(y, x) ≥ 0 ;
b) ∀x, y ∈ An, avem: d (x, y) = 0 ⇔ x = y;
c) ∀x, y, z ∈ An, avem: d (x, y) ≤ d(x, z) + d(z, y).
Demonstra ție. c) Pentru orice x = (x1, …, xn), y = (y1, …, yn) ∈ An, fie C(x, y) := {i |xi = yi}.
Arătăm că d(x, y) ≤ d(x, z) + d(z, y), ∀x, y, z ∈ An. Cum d(x, y) = n − |C(x, y)|, inegalitatea
devine: n ≥ |C(x, z)| + |C(z, y)| − |C(x, y)|. Evident, avem C(x, z) ∪ C(z, y) ⊆ {1,… , n}, deci
|C(x, z) ∪ C(z, y)| ≤ n, adică |C(x, z)| + |C(z, y)| − |C(x, z)∩C(z, y)| ≤ n. Însă C(x, z)∩C(z, y) ⊆
C(x, y), deci n ≥ |C(x, z)| + |C(z, y)| − |C(x, z)∩C(z, y)| ≥ |C(x, z)| + |C(z, y)| − |C(x,y)|. †
Pentru x ∈ An și r > 0, sfera (bila) de rază r centrată în x este mulțimea cuvintelor care sînt
la distanță cel mult r față de x:
Br(x) := {y ∈ An | d(x, y) ≤ r}.
Pentru x ∈ An, unde | A| = q, și 1 ≤ i ≤ n, există exact ()i i
nqC 1−cuvinte aflate la distan ță
exact i de x. Deci orice dou ă sfere de raz ă r au același "volum" (num ăr de elemente):
6 Propozi ție. Fie |A| = q. Numărul de elemente al unei sfere de raz ă r din An este
| Br| = |Br(x)| = ()∑
=−r
ii i
nqC
01. †
7 Definiție. Distanța minimă a unui cod C ⊆ An este:
d(C) := min { d(x, y) | x, y ∈ C, x ≠ y}.
Distanța minimă d(C) este un parameteru foarte important al codului. Orice dou ă cuvinte
cod distincte ale lui C diferă în cel puțin d(C) poziții, și există măcar o pereche de cuvinte cod
la distanță exact d(C).
Capacitatea de corectare a codului C este:
e(C) := [(d(C) − 1)/2].
Să presupunem c ă la transmiterea unui cuvînt cod c ∈ C apar erori, iar y este cuvîntul
recepționat. Trebuie s ă găsim c cunoscînd doar pe y. Pentru orice y ∈ An și c ∈ C, fie
prob( y|c) probabilitatea ca y să fie recep ționat cînd c este trimis. La recep ționarea lui y ∈ A n,
trebuie să găsim un cuvînt cod m(y) ∈ C astfel încît prob( y|m(y)) să fie maxim ă:
prob( y|m(y)) = max { prob( y|c) | c ∈ C}.
Un algoritm care realizeaz ă acest lucru se nume ște algoritm de maximă verosimilitate
(maximum likelihood algorithm). In cazul canalului qSC(p):
prob ( y|c) = pd(y,c)(1 − p)n − d(y,c) = (1 − p)n (),
1dy cp
p⎛⎞
⎜⎟−⎝⎠și 0 < p < 1
2, deci 11p
p<−
Astfel, prob( y|c) e maxim ⇔ d(y, c) este minim. Aceasta arat ă că algoritmul de maxim ă
verosimilitate e echivalent cu:

10

Algoritmul de distan ță minimă. Pentru orice y ∈ An, algoritmul produce un cuvînt cod
w(y) ∈ C care este cel mai apropiat de y
d(y, w(y)) = min { d(y, c) | c ∈ C}.
Este important de știut cînd un astfel de algoritm func ționează. Rezultatul urm ător justific ă
denumirea “capacitate de corectare” dat ă lui e(C) = b(d(C) − 1)/2c:
8 Teorem ă. Fie C ⊆ An un cod cu d(C) = d și e(C) = e = b(d(C) − 1)/2c. Atunci:
a) Orice dou ă sfere centrate în cuvinte cod distincte și de rază e sînt disjuncte.
b) Dacă la transmiterea unui cuvînt cod c ∈ C, x ∈ An este recep ționat și au apărut ε
erori, unde ε ≤ e, atunci c este unicul cuvînt cod din C cel mai apropiat de x (algoritmul de
distanță minimă decodeaz ă corect pe x în c)
c) Dacă d este impar, (deci d = 2e + 1), atunci exist ă cuvinte cod u, v ∈ C și x ∈ An astfel
încît d (u, x) = e + 1, d(v, x) = e. Deci exist ă o situație cînd un cuvînt u este afectat de e + 1
erori și nu este decodat corect de algoritmul de distan ță minimă.
Demonstra ție. a) Presupunem c ă există u, v ∈ C și x ∈ An astfel încît x ∈ Be(u)∩Be(v).
Atunci d(u, v) ≤ d(u, x) + d(x, v) ≤ e + e < d, contradic ție.
b) Avem d(c, x) = ε ≤ e, so x ∈ Be(c). Pentru orice alt u ∈ C, x ∉ Be(u), deci d(x, u) > e.
c) Exercițiu. †
Dacă x ∈ An este recep ționat și δ = min{ d(x, c) | c ∈ C} > e, mai multe cuvinte cod pot fi la
distanță δ de x. Aceasta înseamn ă că o decodare corect ă nu e posibil ă. Chiar dac ă există un
unic c ∈ C la distanță δ, decodarea lui x în c poate fi incorect ă, ca în c) mai sus.
9 Observa ție. Utilizarea unui cod C de lungime n, distanță minimă d și capacitate de
corectare e se poate face în dou ă moduri distincte:
– modul „corectare de erori”: se presupune c ă orice bloc de n simboluri c este afectat de cel
mult e erori. Dac ă cuvîntul recep ționat este ct, ct poate fi decodat în mod univoc în c. De aici
provine și denumirea de capacitate de corectare a lui C ce se dă lui e.
– modul „detectare de erori”: se presupune c ă la transmiterea oric ărui bloc de n simboluri
apar cel mult d − 1 erori. Atunci niciun cuvînt cod c nu poate fi transformat pe parcursul
transmiterii în alt cuvînt cod c'. Astfel, dac ă receptorul prime ște un cuvînt ct care nu este
cuvînt cod, semnaleaz ă „eroare” ( și cere eventual retransmiterea cuvîntului). De aceea, d − 1
se numește capacitatea de detec ție a codului C.
În unele cazuri o combina ție a acestor moduri este posibil ă (un exemplu remarcabil este
schema de corectare/detec ție de erori folosit ă la Compact Disc).
10 Defini ție. Un cod q-ar tip [n, k] cu distan ța minimă d este numit cod tip [ n, k, d]q sau
[n, k, d ]q-cod. Adesea indicele q este omis.

11
Ștersături. Am definit o eroare ca o situa ție cînd un simbol transmis e recep ționat ca un
simbol diferit (adic ă receptorul nu știe apriori c ă o eroare a avut loc, ori unde e plasat ă
eroarea). Un alt model pentru canalul de transmisie include ștersături (erasures ): simbolul
recepționat nu este citibil. O ștersătură poate fi interpretat ă ca o eroare a c ărei poziție e
cunoscută. Ștersăturile sînt mai u șor de corectat (c ăci sînt deja detectate ). Putem modela
această situație permițînd ca în cuvintele receptate s ă poata ap ărea și un nou simbol * (care
notează o ștersătură); desigur, * nu apar ține alfabetului A. Notăm deci A* = A ∪ {*}. Pentru
orice c = c1…cn ∈ C transmis, fie x = x1…xn ∈ A*n cuvîntul recep ționat. Fie S = {i | xi = *}
mulțimea pozi țiilor lui x unde sînt ștersături și fie xS ∈ An − |S| cuvîntul x din care elimin ăm
toate ștersăturile. Algoritmul de distan ță minimă, în acest caz, va c ăuta un cuvînt cod c' ∈ C
astfel încît
d(xS, c'S) = min { d(xS, yS) | y ∈ C}.
Rezultatul urm ător generalizeaz ă Teorema 8 pentru cazul cînd apar ștersături și erori
simultan:
11 Teorem ă. Fie C ⊆ An un cod de distan ță minimă d. Presupunem c ă c ∈ C este
transmis, x ∈ A*n este recep ționat și au apărut ε erori și δ ștersături, unde 2ε + δ < d. Atunci c
este unicul cuvînt cod din C cu proprietatea c ă d(xS, cS) = min { d(xS, yS) | y ∈ C}. Așadar,
algoritmul de distan ță minimă decodeaz ă corect pe x în c.
Demonstra ție. Folosim nota țiile de mai sus. S = {i | xi = *} are δ elemente. Avem
d(xS, cS) = ε. Fie y ∈ C, y ≠ c, și să presupunem prin reducere la absurd c ă d(xS, yS) ≤ ε.
Atunci:
d(yS, cS) ≤ d(yS, xS) + d(xS, cS) ≤ 2ε.
Aceasta implic ă d(y, x) = 2ε + δ < d, contradic ție. †
Teorema lui Shannon asupra capacit ății unui canal. Fixăm un canal qSC(p). Pentru un
cod q-ar C dat și un cuvînt cod x ∈ C, Px(C) este definit ca probabilitatea ca, la transmiterea
lui x pe canal, cuvîntul receptat s ă nu fie decodat corect de algoritmul de distan ță minimă.
Definim probabilitatea de eroare (sau așteptarea de eroare , error expectation) P(C) a lui C ca
media acestor probabilit ăți individuale: P(C) = 1()x
xCCP C−
∈∑ . P(C) este o m ăsură important ă
a calității codului: sînt interesante codurile C pentru care P(C) este foarte mic ă. P(C) depinde
și de canal (adică de probabilitatea de tranzi ție p), nu numai de codul C.
Pentru a enun ța teorema fundamental ă a lui Shannon asupra capacit ății unui canal qSC(p),
definim Hq : [0, (q − 1)/q] → R, funcția de entropie q-ară:
H q(p) = − plog q( p/(q − 1)) − (1 − p)log q(1 − p), ∀ p ∈ (0, ( q − 1)/q]
și punem Hq(0) = 0 prin continuitate. Func ția de capacitate q-ară Cq este definit ă pe [0, 1 /q]
astfel:

12

Cq(p) = 1 − Hq((q − 1)p), ∀ p ∈ [0, 1/q].
În cazul q = 2, o interpretare a H2( p) este urm ătoarea: pentru un simbol transmis s, H2( p)
este incertitudinea ca simbolul recep ționat s' să fie chiar s (echivalent, C2( p) = 1 − H2( p) este
cantitatea de informa ție pe care s' o poartă despre s). Deși extrem de interesante și instructive,
nu insistăm asupra acestor aspecte, deorece țin mai mult de teoria informa ției decît de codare
și necesită incursiuni în teoria probabilit ății. Cq( p) se nume ște capacitatea canalului qSC(p).
12 Teorem ă (Shannon) Fie un canal qSC (p). Atunci, pentru orice R cu R < Cq( p), există
un șir de coduri (Cm)m ≥ 1, de tip [nm, km], cu rată Rm = km /nm > R, astfel încît P (Cm) → 0 cînd
m → ∞.
Pentru orice R > Cq( p), nu exist ă șiruri de coduri cu rate ≥ R și probabilit ăți de eroare
care tind la zero .
Teorema lui Shannon spune în esen ță că dacă rata R de transmisie e mai mic ă decît
capacitatea C q(p) a canalului, atunci exist ă coduri de rat ă R cu probabilitate de eroare
arbitrar de mic ă.
Demonstra ția nu este constructiv ă, adică nu furnizeaz ă explicit un șir de coduri cu
proprietățile din enun ț. De aceea, unul din scopurile teoriei codurilor este de a g ăsi coduri sau
familii de coduri care au rata cît mai apropiat ă de capacitatea canalului și probabilitatea de
eroare cît mai mic ă.
Vom prezenta numai aspecte din teoria codurilor bloc corectoare de erori și unele aplica ții,
ignorînd o clas ă de coduri corectoare de erori numite coduri convoluționale . Un codor
convoluțional tip [ n, k] divide mesajul de intrar e în blocuri de lungime k și le codeaz ă ca
blocuri de lungime n. Dar codarea unui bloc depinde nu nu mai de ultimul bloc mesaj (ca la
codurile bloc corectoa re de erori), ci și de m blocuri de informa ție precedente.

Exerciții
1. Dați exemplu de cod binar de lungime 3 cu 4 cuvinte cod. De ce nu exist ă niciun cod binar
de lungime 4 cu 18 cuvinte cod?
2. De ce este funcția de codare presupus ă injectivă?
3. De ce rata unui cod este definit ă ca log q|C|/n?
4. Fie codul binar C = {01101 , 00011 , 10110 , 11000}. Determina ți distanța sa minim ă și rata.
Folosind algoritmul de distan ță minimă, decodați următoarele cuvinte recep ționate: a) 00000;
b) 01111; c) 10110; d) 10011; e) 11011.

13
5. Fie codul de repeti ție Cn de lungime n peste un alfabet q-ar A, Cn := {c…c ∈ A n| c ∈ A}.
Estimați rata Rn și așteptarea de eroare P(Cn) pentru un canal qSC(p). Satisface șirul ( Cn)n ≥ 1
teorema lui Shannon?
6. Fie n ≥ 2. Fie C un cod binar de lungime n și distanță minimă n. Cîte cuvinte are C? Cîte
astfel de coduri exist ă? Tratați și cazul q-ar.

14

II. Coduri liniare

Dezvoltarea teoriei codurilor bloc corectoare de erori, precum și găsirea unor algoritmi
eficienți de codare și decodare, sînt mult u șurate pentru acele coduri C care au o anumit ă
structură. O astfel de situa ție este cea în care alfabetul este un corp finit F (cu q elemente,
unde q este o putere a unui num ăr prim), iar codul C ⊆ F n este subspațiu liniar în F n. Deși
aceste condi ții limiteaz ă drastic clasa codurilor pe care le studiem, aceast ă clasă este suficient
de largă pentru a furniza coduri importante și eficiente, folosite pe scar ă largă în practic ă. În
continuare presupunem c ă cititorul este familiarizat cu no țiuni și rezultate elementare de
Algebră Liniară: spațiu liniar, dependen ță liniară, sistem de generatori, baze, dimensiune,
produsul scalar standard în F-spațiul liniar F n. În acest capitol not ăm cu F un corp fixat.
Corpul cu q elemente este notat Fq. Cititorul care nu este familiarizat cu corpurile finite poate
presupune c ă F este corpul cu dou ă elemente F2 = Z2 = {0, 1} (inelul de clase de resturi
modulo 2).
Reamintim cîteva lucruri de baz ă privind spa țiile liniare. Fie F un corp comutativ.
Elementele lui F mai sînt numite în acest context scalari . O mulțime nevid ă V (ale cărei
elemente le numim vectori ) se nume ște spațiu liniar (sau vectorial ) peste F dacă:
– este definit ă o adunare a vectorilor din V, adică o funcție
+ : V × V→ V, (u, v) 6 u + v, ∀u, v ∈ V;
– este definit ă o înmulțire a vectorilor din V cu scalari din F:
· : F × V→ V, (λ, v) 6 λv ∈ V, ∀λ ∈ F, ∀v ∈ V;
– aceste opera ții satisfac condi țiile următoare:
(V, +) este un grup abelian , adică:
a) Adunarea e asociativ ă: (x + y) + z = x + (y + z), ∀x, y, z ∈ V.
b) Adunarea e comutativ ă: x + y = y + x, ∀x, y ∈ V.
c) Există un vector 0 ∈ V astfel încît x + 0 = 0 + x = x, ∀x ∈ V.
d) Pentru orice x ∈ V există (− x) ∈ V astfel încît x + (− x) = (− x) + x = 0.
Adunarea vectorilor și înmulțirea cu scalari satisfac în plus propriet ățile următoare, pentru
orice λ ∈ F și x, y ∈ V:
e) λ(x + y) = λx + λy
f) (λμ)x = λ(μx)

15
g) 1x = x, unde 1 noteaz ă elementul unitate al lui F.
Am notat cu 0 atît vectorul 0 ( ∈ V), cît și scalarul 0 ( ∈ F). Cititorul nu trebuie s ă le
confunde. În loc de „spa țiu liniar peste F”, se spune adesea „ F-spațiu liniar”
1 Exemplu. a) Mulțimea F n = {(x1, …, xn) | xi ∈ F, 1 ≤ i ≤ n} este un F-spațiu liniar.
Adunarea și înmulțirea cu scalari se definesc „pe componente”:
(x1, …, xn) + (y1, …, yn) := (x1 + y1, …, xn + yn),
λ(x1, …, xn) := (λx1, …, λxn),
pentru orice ( x1, …, xn), (y1, …, yn) ∈ F n, ∀λ ∈ F.
Verificarea faptului c ă V este într-adev ăr un spațiu linar este imediat ă. Vectorul 0 este
0 := (0, …, 0). Pentru orice ( x1, …, xn) ∈ F n, avem − (x1, …, xn) := (− x1, …, − xn).
Exemplul acesta este fundamental (în sensul c ă orice F-spațiu liniar finit dimensional este
izomorf cu un unic F n).
b) Mulțimea polinoamelor cu coeficien ți în F, F[X], este un F-spațiu liniar. Care sînt
operațiile?
2 Definiție. O submul țime nevid ă C a unui F-spațiu liniar V este un subspațiu liniar al lui
V dacă C este el însu și un F-spațiu liniar cu adunarea vectorilor și înmulțirea cu scalari
definite pe V. Mai precis, C este o mul țime de vectori din V astfel încît C este parte stabil ă la
adunarea vectorilor din V și la înmul țirea extern ă cu scalari din F:
∀u, v ∈ C, ∀α ∈ F, are loc: u + v ∈ C și αv ∈ C.
Scriem C ≤ FV dacă C este un subspa țiu al F- spațiului liniar V (sau mai simplu C ≤ V dacă
nu există pericol de confuzie).
3 Exemple. a) Codul din exemplul I. 1 este C = {000, 111} și este subspa țiu al Z2-spațiului
liniar Z23 (verificați!).
b) Pentru orice k ∈ N*, mulțimea polinoamelor de grad < k din F[X] este un subspa țiu liniar
în F[X] (verifica ți!).
4 Observa ție. Condiția ca C să fie parte stabil ă la înmul țirea cu scalari este redundant ă
pentru cazul corpului cu dou ă elemente Z2. De ce? Mai pute ți da exemple de corpuri pentru
care se întîmpl ă același fenomen?
5 Definiție. Fie F V, n ≥ 1 și v1, …, vn ∈ V. Orice vector de forma
λ1v1 + … + λnvn,
unde λ1, …, λn ∈ F, se nume ște combinație liniară a vectorilor v1, …, vn. Scalarii λ1, …, λn se
numesc coeficienții acestei combina ții liniare, iar num ărul natural n se nume ște lungimea
combinației liniare. Convenim c ă vectorul 0 este singura combina ție liniară de o mulțime vidă
de vectori .
Dacă C este un subspa țiu în V, atunci orice combina ție liniară de vectori din C este în C.

16

Pentru orice submul țime S a lui V, cel mai mic (în sensul incluziunii) subspa țiu al lui V
care include S se numne ște subspațiul generat de S și este notat < S >. Se pooate ar ăta ușor că
< S > este mulțimea tuturor combina țiilor liniare de vectori din S:
< S > = {λ1v1 + … + λnvn | n ∈ N*, λ1, …, λn ∈ F, v 1, …, vn ∈ S}.
Dacă < S > = V, S se numește un sistem de generatori pentru V.
O mulțime B = {v1, …, vn} de vectori se nume ște liniar independent ă dacă orice
combinație liniară de v1, …, vn care este egal ă cu 0 are to ți coeficien ții egali cu 0:
∀ λ1, …, λn ∈ F, dacă λ1v1 + … + λnvn = 0, atunci λ1 = … = λn = 0.
O submul țime B a lui V se nume ște bază a lui V dacă B este linear independent ă și
< B > = V. Dacă B = {v1, …, vn} e finită, condiția este echivalent ă cu: orice vector din V poate
fi scris în mod unic drept o combina ție liniară de { v1, …, vn}:
∀v ∈ V, ∃! (λ1, …, λn) ∈ F n astfel încît v = λ1v1 + … + λnvn .
6 Exemplu. O bază pentru F n este { e1, …, en}, unde e1 = (1, 0, …, 0), e2 = (0, 1, …, 0), …,
en = (0, 0, …, 1) ( baza canonic ă). Există multe alte baze în F n (dacă n > 1 sau | F| > 2).
7 Teorem ă. Orice F-spațiu liniar V are o baz ă. Mai mult, orice dou ă baze ale lui V au
același cardinal (acela și număr de elemente). Acest num ăr este numit dimensiunea lui FV și
se notează dim FV (sau dim V). †
8 Definiție. Fie U, V spații liniare peste corpul F. O func ție ϕ : U → V se nume ște
F-liniară (sau F-morfism de spa ții liniare) dacă :
ϕ(x + y) = ϕ(x) + ϕ(y), ∀x, y ∈ U;
ϕ(λx) = λϕ(x), ∀x ∈ U, ∀λ ∈ F.
Astfel, ϕ este liniar ă dacă și numai dac ă pastrează combinațiile liniare:
ϕ(λ1v1 + … + λnvn) = λ1 ϕ (v1) + … + λnϕ(vn), ∀λ1, …, λn ∈ F, ∀v1, …, vn ∈ U
Un morfism bijectiv de spații linare se nume ște izomorfism . Dacă există un izomorfism
între spațiile liniare U și V, spunem c ă U și V sînt izomorfe și scriem U ≅ V.
9 Observa ție. Dacă V este un spa țiu liniar de dimensiune n peste Fși B = {v1, …, vn} este o
bază pentru V, atunci func ția ϕ : F n → V, ϕ(λ1, …, λn) = λ1v1 + … + λnvn ∀(λ1, …, λn) ∈ F n,
este un izomorfism (demonstra ți!). Deci, toate F-spa țiile liniare cu aceea și dimensiune n sînt
izomorfe .
10 Defini ție. Fie F un corp finit cu q elemente. Se nume ște cod liniar de lungime n peste F
orice subspa țiu liniar C al lui F n.
Cu alte cuvinte, C este o mul țime de cuvinte de lungime n în care simbolurile sînt elemente
din F, închisă la adunarea (pe componente) din F n și la înmul țirea cu scalari din F.
Dimensiunea codului liniar C este dimensiunea lui C ca spațiu liniar peste F. Dacă C este
cod de lungime n, dim C = k și distanța minimă a lui C este d, spunem c ă C este cod liniar de

17
tip [n, k, d]q (sau cod liniar q-ar de tip [n, k, d]); n, k, d se numesc parametrii codului C.
Observați că această notație este în acord cu cea de la I.10: C este F-spațiu liniar de
dimensiune k, deci C ≅ F k și C are q k cuvinte cod.
La un cod liniar C de tip [ n, k, d ], cuvintele cod au lungime n; numărul de simboluri care
poartă informație este k. Restul de n − k simboluri sînt folosite pentru corectare/detec ție de
erori. Rata codului este R = k/n.
11 Exemplu. Codul de repeti ție de lungime 3 peste F2 în exemplul I.1 este C = {000, 111},
care este un subspa țiu în F23 de dimensiune 1 (de ce?). Distan ța minimă a lui C este 3, deci C
este un cod binar tip [3, 1, 3]. Astf el, capacitatea de corectare a lui C este e(C) = 1.
Pentru un cod C dat, determinarea distan ței minime este foarte important ă. A priori, pentru
aceasta ar trebui s ă consider ăm toate distan țele d(x, y) cu x, y ∈ C distincte, adic ă
|C|·(|C| − 1)/2 distanțe, ceea ce este practic inabordabi l (de exemplu, un cod Reed-Solomon
folosit în CD-uri are 25628 ≈ 2.69·1067 cuvinte cod). La coduri liniare , avem deja o sarcin ă
ușurată:
12 Propozi ție. Fie F un corp finit. Atunci distan ța Hamming pe F n este invariant ă la
translații: d(x, y) = d(x + z, y + z), ∀x, y, z ∈ F n. În particular, d (x, y) = d(x − y, 0) și deci
distanța minimă a unui cod liniar C ≤ F n este:
d (C) = min{ d(x, 0) | x ∈ C, x ≠ 0}. †
Ponderea (Hamming ) wt( x) a unui cuvînt (vector) x = x1…xn ∈ F n se define ște ca num ărul
coordonatelor sale nenule (echivalent, wt( x) = d(x, 0))5. Deci:
13 Corolar. Distanța minimă a unui cod liniar este ponderea minim ă nenulă a cuvintelor
cod. †
Așadar, în locul calculului tuturor celor |C|·(|C| − 1)/2 distanțe, codurile liniare cer „doar”
|C| − 1 calcule de ponderi în scopul afl ării distanței minime. În multe ca zuri acest calcul este
tot prea lung, dar exist ă alternative mai rapide (Teorema 19 de mai jos).
Cum putem preciza în mod concret un cod liniar? Exist ă două moduri naturale de a da un
subspațiu liniar C (un cod liniar) de dimensiune k în F n:
– se dă o bază a lui C (adică se dau k vectori liniar independen ți în C )
– se descrie C ca mulțimea solu țiilor unui sistem omogen de n − k ecuații liniar
independente .
14 Defini ție. Fie C ≤ F n un cod liniar de dimensiune k ≤ n peste corpul F. O matrice
generatoare a lui C este o matrice G ∈ M(k, n, F ) ale cărei linii (văzute ca vectori în F n)

5 Notația wt vine de la weight (greutate, pondere).

18

formează o bază în C (deci liniile lui G sînt liniar independente, adic ă rang G = k). Deci, o
matrice G este matrice generatoare pentru C dacă și numai dac ă G este o matrice k × n cu
liniile liniar independente, iar subspa țiul generat de liniile lui A este C.
O matrice de paritate6 a lui C este o matrice H = (hij) ∈ M(n − k, n, F ) astfel încît,
∀x = (x1, …, xn) ∈ F n:
x ∈ C ⇔ hi1x1 + … + hinxn = 0, 1 ≤ i ≤ n − k.
Deci, pentru ca H să fie o matrice de paritate pentru codul C de dimensiune k, trebuie ca
rang H = n − k și să aibă loc: x ∈ C ⇔ HxT = 0 ∈ M(n − k, 1, F).
15 Observa ție. Denumirea de matrice de paritate (parity-check matrix ) provine din cazul
particular al codului binar urm ător: se fixeaz ă k ∈ N* și orice vector x1…xk ∈ F2k este codat ca
x1…xkxk + 1, unde xk + 1 este astfel încît x1 + … + xk + xk + 1 = 0 (în F2). Codul este a șadar
C = {x1…xkxk + 1 ∈ F2k + 1 | x1 + … + xk + xk + 1 = 0}. Orice cuvînt cod are un num ăr par de bi ți
egali cu 1 și de aceea bitul xk + 1 este numit bit de paritate . Verificarea faptului c ă un cuvînt x
este cuvînt cod revine la a ve rifica „paritatea” cuvîntului, adic ă un tip particular de sistem
liniar omogen pe care îl satisfac coordonatele lui x. Acesta se nume ște codul (binar) de
paritate și este liniar, de tip [ k + 1, k, 2] (demonstra ți!). Ce rat ă de transmisie are?
16 Defini ție. Definim produsul scalar standard pe F n:
∀x = (x1, …, xn), y = (y1, …, yn) ∈ F n , 〈x, y〉 = x1y1 + … + xnyn ∈ F.
Dacă S ⊆ F n, fie S⊥ := {y ∈ F n | 〈x, y〉 = 0, ∀x ∈ S} ortogonalul lui S (doi vectori x, y ∈ F n
se numesc ortogonali sau perpendiculari dacă 〈x, y〉 = 0).
Așadar: H ∈ M(n − k, n, F ) este matrice de paritate pentru C ≤ F n ⇔ the liniile lui H sînt
liniar independente și C este mul țimea vectorilor din F nortogonali pe toate liniile lui H .
Produsul scalar standard e o formă biliniar ă simetric ă pe F n, adică este o
funcție 〈·, ·〉: F n×F n → F care satisface propriet ățile:
〈x, y〉 = 〈y, x〉
〈x, y + z〉 = 〈x, y〉 + 〈x, z〉; 〈x + y, z〉 = 〈x, z〉 + 〈y, z〉
〈αx, y〉 = α〈x, y〉
pentru orice x, y ∈ F n, α ∈ F. Demonstra ți!
17 Propozi ție. Fie S ⊆ F n. Atunci:
a) S ⊥ este un subspa țiu în E , numit subspațiul ortogonal pe S;
b) S ⊆ S ⊥ ⊥;
c) ∀T ⊆ E cu S ⊆ T, are loc T ⊥ ⊆ S ⊥;
d) Dacă U ≤ E, atunci U ⊥ = S ⊥, pentru orice sistem de generatori S al lui U.

6 Se mai folose ște terminologia "matrice de control".

19
Demonstra ție. a), c) Verificare direct ă, cu defini ția.
b) Fie x ∈ S. Atunci 〈x, y〉 = 0, ∀y ∈ S ⊥, deci x este în ortogonalul lui S ⊥.
d) Fie S = {v1, …, vk}. Deoarece S ⊆ U, avem U ⊥ ⊆ S ⊥. Orice x ∈ U este o combina ție
liniară de vi': x = λ1v1 + … + λkvk, pentru ni ște λ1, …, λk ∈ F. Pentru orice y ∈ S ⊥,
〈x, y〉 = 〈λ1v1 + … + λkvk, y〉 = λ1〈v1, y〉 + … + λk 〈vk, y〉 = 0,
ceea ce arat ă că y ∈ U ⊥. †
18 Teorem ă. Fie C un cod liniar de tip [n, k, d] peste corpul F. Atunci:
a) C ⊥ este un cod liniar de dimensiune n − k (numit codul dual lui C ).
b) (C ⊥)⊥ = C.
c) Dacă G este o matrice generatoare a lui C, atunci G este o matrice de paritate pentru
C ⊥. Dacă H este matrice de paritate pentru C, at unci H este matrice generatoare pentru C ⊥.†
Demonstra ție. a) Fie G ∈ M(k, n, F) o matrice generatoare pentru C. Atunci x ∈ C ⊥ ⇔ x
este ortogonal pe liniile lui G (căci aceste linii genereaz ă C). Deci C ⊥ este spațiul soluțiilor
sistemului liniar omogen de matrice G, care este de dimensiune n − rang G = n − k.
b), c) Exerci țiu. †
Deoarece un spa țiu liniar poate avea multe baze, un cod liniar poate avea multe matrice
generatoare și multe matrice de paritate. Observa ți că, spre deosebire de spa țiile liniare reale
(cum este Rn), un vector nenul în F n poate fi ortogonal pe el însu și (de ex. (1, 1) în F22), deci
este posibil ca C și C ⊥ să aibă intersecție nenulă. Dacă C = C ⊥, C se numește autodual .
Distanța minimă a unui cod liniar poate fi citit ă de pe matricea sa de paritate:
19 Teorem ă. Fie C un cod liniar peste F și H ∈ M(n − k, n, F) o matrice de paritate
pentru C. Atunci distan ța minimă d a lui C este
d = min{ δ | există δ coloane în H care sînt liniar dependente} =
= 1 + max{ ε ∈ N | orice ε coloane din H sînt liniar independente} .
Demonstra ție. Fie Hi ∈ F n − k coloana i a lui H, 1 ≤ i ≤ n. Avem ( x1, …, xn) ∈ C dacă și
numai dac ă x1H1 + … + xnHn = 0. Fie d' = min{ δ | există δ coloane în H, liniar dependente}.
Fie ( x1, …, xn) ∈ C, de pondere minim ă d. Atunci coloanele Hi pentru care xi ≠ 0 (în num ăr
de d) sînt liniar dependente, deci d' ≤ d. Reciproc, fie o mul țime de d' coloane { Hi}i ∈ J, liniar
dependent ă. Atunci exist ă (x1, …, xn) ∈ F n cu x1H1 + … + xnHn = 0 și xi ≠ 0 ⇒ i ∈ J. Deci
x = (x1, …, xn) ∈ C și d ≤ wt(x) ≤ d'. †
Construim o clas ă important ă de coduri de distan ță minimă 3, pe baza acestui rezultat.

20

20 Defini ție. (Coduri Hamming7) Fie F = Fq și r ∈ N* fixat. Definim codul Hamming
q-ar de redundan ță r, Hq, r, astfel:
Construim o matrice de paritate H care să aibă orice 2 coloane liniar independente, dar
există 3 liniar dependente (deci distan ța minimă a codului va fi 3). Pentru aceasta, alegem cîte
un vector nenul din fiecare subspa țiu de dimensiune 1 din F r și construim matricea H ce are
drept coloane ace ști vectori (într-o ordine arbitrar ă). Matricea H este prin defini ție matricea de
paritate H a codului Hq, r.
Un alt mod de a exprima ideea de mai sus este: pe F r \ {0} definim o rela ție de
echivalen ță:
∀x, y ∈ F r scriem x ∼ y ⇔ ∃α ∈ F * astfel încît y = α·x.
Din fiecare clas ă de echivalen ță alegem cîte un vector. Ace ști vectori sînt coloanele
matricei de paritate H.
Cîte coloane are H ? Se observ ă că clasele de echivalen ță de mai sus au fiecare cîte q − 1
elemente (clasa de echivalen ță a lui x ∈ F r \ {0} este { α·x | α ∈ F*}). Cum reuniunea lor
(disjunctă) este F r \ {0}, avem q r − 1 = n(q − 1), unde n este num ărul claselor de echivalen ță.
Deci H are n = (q r − 1)/(q − 1) coloane și r linii.
Pentru ca H ∈ M(r, n, K) să fie matrice de paritate, trebuie ca rang H = r. Există într-adev ăr
r coloane liniar independente în H, de exemplu (multipli scalari de) (1, 0, …, 0)T, (0, 1, …,
0)T, …, (0, 0, …, 1)T.
Există 3 coloane liniar dependent e (de ce?), deci distan ța minimă a lui Hq,r este 3, din
Teorema II.19.
Deci Hq,r este un cod liniar de tip [( q r − 1)/(q − 1), ( q r − 1)/(q − 1) − r, 3] q .
21 Observa ție. Construc ția de mai sus nu determin ă în mod unic matricea de paritate H.
De exemplu, pentru dou ă ordonări diferite ale coloanelor se ob țin două matrice de paritate H,
H' distincte și deci coduri Hamming corespunz ătoare distincte C , C'. Însă aceste coduri sînt
echivalente pîn ă la o permutare , în sensul c ă ∃σ ∈ Sn (grupul permut ărilor mulțimii {1, 2, …,
n}) astfel încît:
∀x1…xn ∈ F n, avem x1… xn ∈ C ⇔ xσ(1)… xσ(n) ∈ C'.
Dacă în matricea de paritate H a codului Hamming C se înlocuie ște coloana i (fie aceasta
Pi) cu coloana αPi, unde α ∈ F*, atunci se ob ține o matrice H', de paritate pentru un cod C'
astfel încît avem x1…xi…xn ∈ C ⇔ x1…(α − 1xi)…xn ∈ C.
Această situație sugereaz ă definirea unui alt tip de echivalen ță: două coduri C, C' de
lungime n peste corpul F se numesc diagonal echivalente dacă ∃ (α1, …, αn) ∈ (F*)n astfel
încît ∀(x1,…, xn) ∈ F n, avem ( x1,…, xn) ∈ C ⇔ (α1×1,…, αnxn) ∈ C'. Două coduri C, C' care

7 Familia de coduri descris ă a fost descoperit ă independent în 1949 de Marcel Golay și în 1950 de Richard
Hamming.

21
sînt echivalente (diagonal sau pîn ă la o permutare) au în esen ță „aceleași” propriet ăți: de
exemplu, C este liniar ⇔ C' este liniar.
Reuniunea celor dou ă relații de echivalen ță pentru coduri de lungime n peste F se numește
echivalen ță monomial ă.
Se poate demonstra c ă codurile C și C' sînt monomial echivalente dac ă și numai dac ă
există σ ∈ Sn și (α1, …, αn) ∈ (F*)n astfel încît:
∀x1…xn ∈ F n: (x1,…, xn) ∈ C ⇔ (α1xσ(1),…, αnxσ(n)) ∈ C'
Deci, codul Hamming H q, r este unic determinat pîn ă la o echivalen ță monomial ă.
Enunțați cît mai multe propriet ăți ale unui cod care se conserv ă prin echivalen țele definite
aici. Puteți defini și alte tipuri de echivalen țe?
22 Exemplu. (codul binar Hamming [7, 4, 3]) Pentru q = 2 și r = 3, avem n = 7. Cum
F = F2, corpul cu dou ă elemente, coloanele lui H sînt unic determinate pîn ă la o ordonare
(orice subspa țiu de dimensiune 1 are un uni c vector nenul). Alegem s ă ordonăm coloanele
lexicografic (adic ă scriem “vertical” toate numerele nenule de 3 cifre în baza 2, în ordine
crescătoare). Deci H este:
H =
⎥⎥⎥
⎦⎤
⎢⎢⎢
⎣⎡
111100011001101010101

Acest cod are o importan ță istorică deosebită: A fost primul cod corector de erori folosit în
computere (coduri detectoare de erori mai fuseser ă folosite înainte). O matrice de paritate a
codului binar Hamming [7, 4, 3] este imprimat ă pe medalia “Richard W. Hamming” a IEEE8.
Să descriem o modalitate practic ă de codare și de decodare pe ntru acest cod H2, 3. Întrucît
este un cod tip [7, 4], fiecare mesaj de 4 bi ți este codat pe un cuvînt cod de 7 bi ți.
Coordonatele unui cuvînt cod d = d1 … d7 ∈ H2, 3 satisfac ecua ția Pd T = 0, adică

8 Matricea de pe medalie nu este cea aleas ă de noi. Ce leg ătură este între codurile respective?

22

d1 + d3 + d5 + d7 = 0
d 2 + d3 + d6 + d7 = 0 (*)
d4 + d5 + d6 + d7 = 0
Alegem bi ții d1, d2, d4 să fie „de control”, iar bi ții mesajului original sînt plasa ți în pozițiile
3, 5, 6, 7. Bi ții d1, d2, d4 se obțin din ecua țiile de mai sus, adic ă d1 = d3 + d5 + d7 etc.9
La recepția unui cuvînt de 7 bi ți r = r1 … r7, se verific ă dacă r este cuvînt cod (adic ă dacă
r1, …, r7 satisfac ecua țiile (*)). Altfel spus, se calculeaz ă (c1, c2, c3) = H(r1, …, r7)T. Dacă
(c1, c2, c3) = (0, 0, 0), atunci nu au avut loc erori. Dac ă (c1, c2, c3) ≠ (0, 0, 0), atunci eroarea
(presupus ă a fi singura) e plasat ă în bitul a c ărui poziție este dat ă de numărul binar c3c2c1 (și
deci poate fi corectat ă!). Demonstra ția acestei „scamatorii” e propus ă ca exerci țiu.
Acest cod este mai eficient decît codul binar de repeti ție de lungime 3. Rata sa este 4/7, o
îmbunătățire substan țială față de 1/3. Dar poate corect a maximum o eroare la 7 bi ți, în timp ce
codul de repeti ție corecteaz ă o eroare la 3 bi ți.
23 Exerci țiu. Presupunem folosim codul H2, 3 și că s-a recep ționat cuvîntul 110100.
Decideți dacă au avut erori și corectați.
24 Teorem ă (inegalitatea Hamming) . Fie C un cod q-ar (nu neap ărat liniar) de lungime n
cu capacitate de corectare e. Atunci
()∑
=−e
ii i
nqC C
01≤ qn.
Demonstra ție. Sînt q n elemente în An și |C| cuvinte cod în C. Sferele de raz ă e centrate în
cuvintele cod sînt disjuncte dou ă cîte dou ă, deci |C|·|B(x, e)| ≤ q n. Înlocuind | B(x, e)| cu
volumul sferei se ob ține rezultatul. 6. †
Pentru orice cod C (nu neap ărat liniar) de capacitate de corectare e, sferele centrate în
cuvintele cod de raz ă e sînt disjuncte; dac ă reuniunea lor este întreg F n, atunci codul se
numește (e-)perfect . Echivalent, un cod este perfect dac ă are loc egalitate în inegalitatea
Hamming.
25 Exerci țiu. Orice cod e-perfect are distan ță minimă 2e + 1.
Codurile Hamming sînt 1- perfecte (verificați!). Altfel spus, orice cuvînt din F n se găsește
la distanță ≤ 1 de exact un cuvînt cod. Acest fenomen are aplica ții oarecum surprinz ătoare.
26 Aplicație. Jocul Pronosport constă în ghicirea rezultatelor a 13 partide de fotbal.
Rezultatul unei partide este un element al mul țimii {x, 1, 2} (x = egalitate; 1 = cîștigă gazdele;
2 = cîștigă oaspeții). Jucătorii completeaz ă variante ; numim variant ă orice 13-uplu ( s1,…, s13),

9 De ce s-a ales astfel pozi ția biților de control?

23
cu si ∈ {x, 1, 2}. Pentru a cî știga cu siguran ță premiul I (13 rezultate exacte), este necesar ă a
priori completarea a 313 variante. Se pune întrebarea: care este num ărul minim de variante ce
trebuie completate pentru a cî știga cu siguran ță premiul II (12 rezultate exacte )?
Reformul ăm problema în termen ii teoriei codurilor: Fie F = F3, corpul cu 3 elemente. S ă se
găsească o submul țime (un cod ) S ⊆ F13 (cît mai „mic ă”), astfel încît orice cuvînt din F13 să
se găsească la distan ță cel mult 1 de un cuvînt din S . Altfel spus, s ă se găsească un cod
1-perfect de lungime 13 peste F3.
Răspunsul este dat de codul Hamming cu q = 3 și r = 3: avem n = (33 − 1)/2 = 13, deci este
un cod tip [13, 10, 3] 3. Numărul de cuvinte cod (de „variante”) este 310 = 59049.
27 Exerci țiu. Scrieți o matrice de paritate pent ru codul Hamming de mai sus.
28 Teorem ă. (inegalitatea Single ton, Singleton Bound) Fie C un cod de lungime n și
distanță minimă d peste un alfabet A cu q simboluri. Atunci |C| ≤ q n − d + 1. Dacă C este liniar,
atunci d ≤ n − k + 1.
Demonstra ție. Pentru ( x1, …, xn − d + 1) ∈ An − d + 1 fixat, exist ă cel mult un cuvînt cod în C
ale cărui coordonate de pe primele n − d + 1 locuri sînt ( x1, …, xn − d + 1) (dacă ar exista dou ă
astfel de cuvinte în C, distanța dintre ele ar fi < d). Deci |C| ≤ |A| n − d + 1 = q n − d + 1. Dacă C
este liniar, atunci |C| = q k. †
Codurile liniare pentru care d = n − k + 1 se numesc coduri MDS (Maximum Distance
Separable ) și sînt „cele mai bune” dintr-un anumit punct de vedere (distan ța minimă a codului
este maxim posibil ă dacă dimensiunea și lungimea codului sînt fixate).
Rezultatele de mai sus limiteaza num ărul cuvintelor cod, pentru o lungime și o distan ță
minimă date. Iată și rezultate care afirm ă că, pentru o distan ță minimă dată, există coduri care
conțin măcar un num ăr garantat de cuvinte.
29 Teorem ă (Inegalitatea Gilber t, Gilbert Bound) Fie q, n ∈ N și d ≤ n. Atunci exist ă
coduri q-are (neliniare) C de lungime n și distanță minimă d astfel încît:
|C| ≥
()1
01n
di
iq
nq
i−
=⎛⎞− ⎜⎟⎝⎠∑.
Demonstra ție. Dintre codurile q-are de lungime n și distanță minimă d alegem codul C cu
un număr maxim de cuvinte. Presupunem c ă pentru C inegalitatea de mai sus este fals ă.
Atunci reuniunea sferelor de raz ă d − 1 centrate în cuvintele din C este strict inclus ă în F n,
deoarece:
() ()1
1
01di n
d
i xCnB xC q q
i−
−
= ∈⎛⎞≤ −< ⎜⎟⎝⎠∑ ∪ ,

24

Deci, exist ă v ∈ F n cu d(v, C) = min{ d(v, x) | x ∈ C} ≥ d. Atunci C ∪{v} are mai multe
cuvinte decît C și are distan ța minimă d, contradic ție. †
Versiunea liniar ă a rezultatului de mai sus este:
30 Teorem ă (Inegalitatea Varshamov, Varshamov Bound) Există un cod liniar q-ar C tip
[n, k] cu distanța minimă cel puțin d astfel încît
|C| = q n − k > ()2
011di
inq
i−
=⎛⎞−− ⎜⎟⎝⎠∑ .
Demonstra ție. Arătăm că există o matrice H tip ( n−k) × n peste F astfel încît orice d − 1
coloane ale lui H sînt liniar independente. Construim coloanele c1, …, cn ale lui H astfel:
Fie c1 orice vector nenul din F n − k. Fie c2 ∈ F n − k \ < c1 >.
Pentru orice 2 ≤ j ≤ n, fie cj orice vector care nu se poate scrie ca o combina ție liniară de
d − 2 (sau mai pu țini) vectori dintre c1, …, cj − 1. Există un astfel de vector?
O combina ție liniară de i vectori ( i ≤ d − 2) aleși dintre c1, …, cj − 1 este determinat ă dacă
alegem i indici din j − 1 și atașăm fiecărui indice un coeficient nenul din F. Aceasta se poate
face în ()11i jq
i−⎛⎞− ⎜⎟⎝⎠ moduri. Deci exist ă cel mult ()2
011di
ijq
i−
=−⎛⎞− ⎜⎟⎝⎠∑ astfel de vectori.
Deoarece
() ()22
001 111ddii nk
iij nqq q
ii−−
−
==−⎛⎞ ⎛⎞ −−≤ −< ⎜⎟ ⎜⎟⎝⎠ ⎝⎠∑∑ ,
vectorul cj poate fi g ăsit, pentru orice j ≤ n.
Fie C subspațiul ortogonal pe liniile lui H. Atunci C are dimensiune cel pu țin k (liniile lui
H pot să nu fie liniar independente, adic ă rang H < n − k). Deoarece un cuvînt din C de
pondere < d corespunde unei combina ții liniare nule de mai pu țin decît d coloane ale lui H,
ponderea minim ă a cuvintelor nenule din C este cel pu țin d. Dacă vrem un cod de dimensiune
exact k, alegem orice subspa țiu al lui C de dimensiune k. †
Versiunile "asimptotice" (nu aprofund ăm acest aspect) ale acestor inegalit ăți coincid, și de
aceea se vorbe ște de “inegalitatea Gilbert-Varshamov”.
Exerciții
1. (Algoritm de decodare pentru codu ri binare Hamming) Folosim nota țiile din Exemplul 22.
Fie e = e1… e7 = r − d vectorul eroare și fie h1, …, h7 coloanele lui H.
a) Dem că H(r1, …, r7)T = H(e1, …, e7)T = e1h1 + … + e7h7
b) Dacă are loc exact o eroare, atunci wt( e) = 1. Fie ei ≠ 0 . Atunci ( c1, c2, c3)T = hi.
c) Folosind faptul c ă hi este num ărul i scris în baza 2, corecta ți eroarea.

25
d) Generaliza ți algoritmul pentru orice cod binar Hamming H2, r.
2. Fie F un corp cu q elemente, n ∈ N și m < q n. Cîte coduri de lungime n peste F cu m
cuvinte exist ă? Cîte din acestea sînt liniare? ( Ind. Dacă m nu este de forma q k, nu exist ă
subspații liniare cu m elemente în F n. Dacă m = q k, trebuie g ăsit numărul subspa țiilor liniare
de dimensiune k din F n.)
3. Scrieți o matrice de paritate pentru codul din Aplica ția 26.
4. (Coduri de repeti ție) Consider ăm următorul procedeu de codare : pentru a coda cuvinte
oarecare de lungime k (peste alfabetul binar {0, 1} = F) se repet ă fiecare bit de r ori; astfel,
orice cuvînt x1…xk este codat ca x1…x1x2…x2…xk…xk (fiecare xi apare de r ori). Se ob ține un
cod de lungime kr.
a) Arătați că acest cod este liniar, de dimensiune k.
b) Arătați că distanța sa minim ă este r.
c) Folosim codul de repeti ție de tip [3,1]. Dac ă se prime ște mesajul 000101111100, unde
au apărut erori? Corecta ți-le.
d) Care este rata de tran smisie a codului de repeti ție tip [ kr, k]?
5. Scrieți toate cuvintele codului Hamming H2, 2, Care este rata sa de transmisie?
6. Scrieți toate cuvintele codului binar Hamming tip [7, 4, 3]. Care es te rata sa de transmisie?
7. Calculați numărul de cuvinte și rata de transmisie ale codului Hamming Hq, r (în general) și
pentru q = 2, r ≤ 5.
8. Fie C un cod liniar de tip [ n, k, d ] peste F, corp cu q elemente.
a) Arătați că: ori toate cuvintele din C încep cu 0, ori exact 1 /q din cuvinte încep cu 0. ( Ind.
Fie D := {x1…xn ∈ F n | x1 = 0}, subspa țiu liniar în F n. Aplicați formula pentru dim( C + D)).
b) Demonstra ți că suma ponderilor tuturor cuvintelor lui C este cel mult n(q − 1)q k − 1.
c) Demonstra ți că d ≤ ()
111
−−−
kk
qq qn. (Ind. Distanța minimă este mai mic ă decit media
ponderilor cuvintelor nenule.)
d) (Inegalitatea Plotkin) Demonstra ți că, dacă qq
nd 1−> , atunci
nqqddC1−−≤ .
9. Arătați că un cod liniar C peste Fq care are aceia și parametri ca un cod Hamming trebuie s ă
fie un cod Hamming. ( Ind. Deoarece d(C) = 3, o matrice de paritate a lui C trebuie s ă aibă
orice două coloane liniar independente.)

26 III. Corpuri finite
Corpurile finite au dep ășit de mult stadiul de curiozitate matematic ă. Corpurile finite sînt
esențiale în tehnologiile legate de tr ansmisia, stocarea, secretizarea și prelucrarea informa ției
digitale. Codurile liniare corectoare de erori se bazeaz ă pe corpuri finite, iar unele din cele
mai puternice scheme criptografice moderne au la baz ă logaritmul discret într-un corp finit.
Clasificarea corpurilor finite este simpl ă: pentru orice num ăr q, putere a unui prim, exist ă
un unic (pîn ă la izomorfism) corp finit cu q elemente, notat Fq. Acestea sînt toate corpurile
finite (pîn ă la izomorfism). În plus, grupul ( Fq*, ·) este ciclic. Vom demonstra în continuare
aceste fapte. Reamintim cîteva no țiuni fundamenale de algebr ă.
Se numește inel un triplet ( R, +, ·) format dintr-o mul țime nevid ă R și două operații interne
pe R,
+ : R × R → R, (x, y) 6 x + y, ∀x, y ∈ R (numită adunare ),
· : R × R → R, (x, y) 6 x·y, ∀x, y ∈ R (numită înmulțire),
care satisfac urm ătoarele condi ții:
1) (R, +) este grup comutativ (abelian ), adică
a)∀x, y, z ∈ R, (x + y) + z = x + (y + z) (asociativitatea adun ării);
b) ∃0 ∈ R astfel încît, ∀x ∈ R, x + 0 = 0 + x = x (există element neutru 0 pentru adunare );
c) ∀x ∈ R, ∃ −x ∈ R astfel încît x + (−x) = (−x) + x = 0 (orice element x are un opus −x);
d) ∀x, y ∈ R, x + y = y + x (comutativitatea adunării);
2) Înmulțirea este asociativ ă și distributiv ă față de adunare , adică
∀x, y, z ∈ R, (xy)z = x(yz) (asociativitatea înmul țirii);
∀x, y, z ∈ R, x(y + z) = xy + xz (distributivitatea la stînga a înmul țirii față de adunare );
∀x, y, z ∈ R, (y + z)x = yx + zx (distributivitatea la dreapta a înmul țirii față de adunare ).
Toate inelele R pe care le consider ăm sînt inele unitare : există 1 ∈ R astfel încît
x1 = 1x = x, ∀x ∈ R. Dacă înmulțirea este comutativ ă, (∀x, y ∈ R, xy = yx) R se numește inel
comutativ .
Un corp F este un inel unitar (cu 1 ≠ 0) în care orice element nenul are un invers fa ță de
înmulțire: ∀x ∈ F\{0} : = F*, ∃x−1 ∈ F* astfel încît xx−1 = x−1x = 1. Orice corp are m ăcar două
elemente: 0 și 1. Un corp în care înmul țirea este comutativ ă se numește corp comutativ (numit
uneori cîmp ). În acest curs, „corp” înseamn ă „corp comutativ”.

27
O submul țime E a unui corp F este numit ă subcorp al lui F dacă este parte stabil ă la
înmulțire, adunare și la inversarea elementelor nenule. Astfel, E este corp cu opera țiile induse.
Se demonstreaz ă ușor că E este subcorp în F dacă și numai dac ă: ∀x, y ∈ E, cu y ≠ 0, avem
x − y ∈ E și xy − 1 ∈ E.
Mulțimea numerelor întregi Z este un inel comutativ, dar nu este corp (2 nu e inversabil în
Z). Mulțimea numerelor ra ționale Q este corp și este subcorp al lui R. Aceste corpuri sînt
infinite. Sîntem interesa ți în corpuri finite .
O funcție ϕ : E → F, unde E și F sînt inele, se nume ște morfism de inele dacă păstrează
operațiile: ϕ(x + y) = ϕ(x) + ϕ(y), ϕ(xy) = ϕ(x)ϕ(y), ∀x, y ∈ E și ϕ(1) = 1. Dacă E și F sînt
corpuri, spunem c ă ϕ este morfism de corpuri. Orice morfism de corpuri e injectiv
(demonstra ți!).
Construcția corpurilor finite se bazeaz ă pe conceptul important de inel factor , care în
esență este o generalizare a construc ției inelului Zn al întregilor modulo n. Schițăm ideile
acestor construc ții.
Fie n un num ăr întreg fixat (numit modul ). Spunem c ă numerele întregi a și b sînt
congruente modulo n dacă n divide a − b. Scriem aceasta sub forma a ≡ b (mod n). Se
demonstreaz ă imediat c ă relația „ ≡ (mod n)” de congruen ță modulo n este o rela ție de
echivalen ță pe Z. Pentru orice a ∈ Z, se noteaz ă cu a[ clasa lui a în raport cu rela ția de
congruență modulo n. Avem deci a[ = {b ∈ Z | a ≡ b (mod n)}. Mulțimea factor Z/≡
(mod n) (adică {a[ | a ∈ Z}) se noteaz ă cu Zn și se nume ște mulțimea claselor de resturi
modulo n .
Denumirea de clase de resturi este motivat ă de faptul c ă că două numere întregi a și b sînt
congruente modulo n dacă și numai dac ă dau acela și rest la împ ărțirea cu n.
Pe Zn se pot defini dou ă operații (numite adunarea , respectiv înmulțirea modulo n ), în
raport cu care Zn devine inel comutativ și unitar . Pentru orice a [, b [ ∈ Zn (cu a, b ∈ Z),
definim:
a[ + b[ := a + b[ ; a[ · b[ := a · b[
Demonstrarea corectitudinii defini țiilor de mai sus (adic ă independen ța de alegerea
reprezentan ților) și a axiomelor inelului este propus ă cititorului.
Vom aplica ideea construc ției de mai sus într-o situa ție mai general ă. În acest scop,
observăm că putem defini rela ția de congruen ță modulo n pe Z și în felul urm ător: Notăm
nZ := {nk | k ∈ Z}. Avem atunci, ∀a, b ∈ Z:
a ≡ b (mod n) ⇔ a − b ∈ nZ.
Se vede imediat c ă a[ = {a + nk | k ∈ Z}, motiv pentru care a[ se mai noteaz ă cu a + nZ.
Deci, 0[ = nZ, 1[ = 1 + nZ etc.
Mulțimea nZ este ideal în Z, în sensul c ă este parte stabil ă la adunare și, ∀x ∈ Z, ∀a ∈ nZ,
rezultă că xa ∈ nZ (nZ este parte stabil ă la înmulțirea cu orice element din Z).

28

Mai general, dac ă R este inel (presupus pentru simplitate comutativ și unitar ), o
submulțime nevid ă I a sa se nume ște ideal în R (fapt notat I ≤ R) dacă satisface condi țiile:
– ∀a, b ∈ I, rezultă a + b ∈ I;
– ∀a ∈ I, ∀r ∈ R, rezultă ra ∈ I.
Se observ ă imediat c ă orice ideal I al lui R este subgrup al grupului aditiv
(R, +) (demonstra ți!) și deci 0 ∈ I. Idealul I se numește propriu dacă I ≠ R.
Propoziția următoare arat ă că ideea de construc ție a lui Zn pornind de la Z și un ideal al s ău
(de forma nZ) se generalizeaz ă cuvînt cu cuvînt la cazul unui inel R și al unui ideal I al său.
Demonstra ția constă în verificarea direct ă a propriet ăților enunțate și o lăsăm cititorului ( și
poate fi g ăsită în orice carte introductiv ă de algebr ă „modernă”).
1 Propozi ție. Fie R un inel comutativ unitar și I un ideal al s ău.
a) Relația (de congruență modulo I), definită prin:
a ≡ b (mod I) ⇔ a − b ∈ I
este o rela ție de echivalen ță pe I. Notînd cu a[ = {b ∈ R | a ≡ b (mod I)} (numită clasa lui a
modulo I), are loc a[ = {a + x | x ∈ I} (a[ se mai noteaz ă a + I din acest motiv ).
b) Operațiile pe mul țimea factor R /I := {a[ | a ∈ R}, date de:
a[ + b[ := a + b[ și a[·b[ ≡ a·b[, ∀a, b ∈ R,
sînt corect definite și înzestreaz ă pe R/I cu o structur ă de inel comutativ unitar (numit inelul
factor al lui R în raport cu I).
c) Aplicația π : R → R/I, π(r) = r[ = r + I, ∀r ∈ R, este un morfism surjectiv de inele (numit
surjecția canonic ă a inelului factor R/I). †
În termeni mai pu țin riguroși, trecerea de la inelul R la inelul factor R/I „duce toate
elementele din I în zero” sau „anuleaz ă elementele lui I”. Cu nota țiile de mai sus, inelul factor
Z/nZ este exact Zn. Multe afirma ții referitoare la idealul I în R s e t r a d u c p r i n a f i r m a ții
referitoare la idealul 0 în R/I, idee aplicat ă adesea în ra ționamente.
2 Teorem ă. (teorema fundamental ă de izomorfism pentru inele) Fie R, S inele comutative
și ϕ : R → S un morfism de inel e. Atunci nucleul lui ϕ, Kerϕ = {r ∈ R | ϕ(r) = 0} este un
ideal al lui R și există un izomorfism canonic
ImKerRϕϕ≅
r + kerϕ 6 ϕ(r), ∀r ∈ R. †
Propoziția următoare dă cele mai simple exemple de corpuri finite, care sînt blocurile de
bază pentru orice corp finit.
3 Teorem ă. Fie n ∈ N*. Atunci inelul Zn este corp dac ă și numai dac ă n este prim.

29
Demonstra ție. Presupunem c ă n e prim. Cum Zn este inel, e suficient s ă arătăm că orice
element nenul din Zn este inversabil. Fie a ∈ Z astfel încît a [ ≠ 0[ în Zn. Aceasta înseamn ă
că (a, n) = 1. Un rezultat cunoscut afirm ă că în acest caz exist ă u, v ∈ Z astfel încît ua + vn =
(a, n) = 1. Trecînd la clase modulo n, obținem u [·a[ = 1[, căci n [ = 0[. Reciproc, presupunem c ă
Zn este corp și totuși n nu este prim. Atunci n = ab, cu 1 < a, b < n, deci în Zn avem a[b [ = n;[
= 0[, imposibil, c ăci a[ și b [sînt nenule. Contradic ția arată că n trebuie să fie prim. †
4 Definiție. Fie K, L corpuri. Dac ă σ : K → L este un morfism de corpuri (cu necesitate
injectiv), atunci tripletul ( K, L, σ) se nume ște o extindere a lui K. În acest caz, pentru orice
element a ∈ K, obișnuim să identificăm σ(a) ∈ L cu a ∈ K. Astfel, dac ă a ∈ K și x ∈ L, vom
scrie a·x în loc de σ(a)·x etc. Prin aceast ă identificare, K este subcorp al lui L și scriem, prin
abuz, „extinderea K ⊆ L” în loc de „extinderea ( K, L, σ)”.
Rezultatul urm ător conține o construc ție de corpuri extrem de important ă. Toate corpurile
finite sînt construite în acest mod.
5 Propozi ție. Fie K un corp și f ∈ K[X] un polinom ireductibil de grad cel pu țin 2 (deci f
nu are rădăcini în K ). Fie ( f ) = {gf | g ∈ K[X]} idealul generat de f.
a) Inelul factor L := K[X]/( f ) este un corp10 (extindere a lui K) și f are o r ădăcină în L,
anume X + ( f ), clasa lui X mod f.
b) Există o extindere E a lui K astfel încît f are toate r ădăcinile în E (f se descompune în
factori liniari în E [X]).
Demonstra ție. a) Fie g[ ≠ 0[ un element nenul în L, unde g ∈ K[X]. Aceasta înseamn ă că f
nu divide g; cum f este ireductibil, avem ( f, g) = 1. Atunci exist ă u, v ∈ K[X] astfel încît
1 = uf + vg . Trecînd la clase modulo f, 1[ = uf + vg[ = vg[. Deci g[ are un invers, anume v[ ∈ L.
Rădăcina lui f în L este X [. Într-adev ăr, fie f = a0 + a1X + … + anX n; atunci:
f (X [) = a01[ + a1X;[ + … + an X[ n = a0 + a1X + … + anX n [ = f [ = 0[.
b) Se folose ște o induc ție după grad f. †
Observați că se consider ă K drept subcorp în K[X]/( f ) via aplica ția canonic ă
ϕ : K → K[X]/( f ), ϕ(a) = a[ (clasa lui a modulo ( f )), ∀a ∈ K, care este un morfism de
corpuri.
Avem nevoie de unele defini ții și rezultate fundamentale din teor ia extinderilor de corpuri.
6 Definiție. Fie K ⊆ L o extindere și x ∈ L. Spunem c ă x este algebric peste K dacă există
un polinom nenul f ∈ K[X] astfel încît f (x) = 0. Altfel spus, x este algebric peste K dacă și
numai dac ă morfismul de evaluare evx : K[X] → L, evx( f ) = f(x) ∀f ∈ K[X], nu este injectiv.

10 Rezultatul și demonstra ția sînt asem ănătoare cu faptul c ă Zn este corp dac ă și numai dac ă n este prim.
Aceasta nu e întîmpl ător: atît Z cît și K[X] sînt "inele principale".

30

De exemplu, în extinderea Q ⊆ R, elementul 2 este algebric peste Q, căci este rădăcină a
lui X 2 − 2 ∈ Q[X].
7 Teoremă. Fie K ⊆ L o extindere de corpuri și x ∈ L, algebric peste K. Fie f un polinom
unitar cu coeficien ți în K. Urm ătoarele afirma ții sînt echivalente:
a) f (x) = 0 și grad f = min{grad g | g ∈ K[X], g(x) = 0, g ≠ 0}.
b)f (x) = 0 și f este ireductibil .
c) f (x) = 0 și, oricare ar fi g ∈ K[X] cu g(x) = 0, rezultă că f |g.
Demonstra ție. a)⇒b) Dacă f ar fi reductibil, atunci f = gh, cu g, h ∈ K[X], 1≤ deg h, deg g
< deg f. Cum g(x)h(x) = f (x) = 0, x este o rădăcină a lui g sau h, ale căror grade sînt mai mici
decît grad f, contradic ție cu defini ția lui f.
b)⇒c) Fie 0 ≠ g ∈K[X] astfel încît g(x) = 0. Cum f(x) = 0, rezult ă că d(x) = 0, unde
d = GCD( f, g), deci grad d > 0. Însă d |f și f este ireductibil, deci d = f, i.e. f |g.
c)⇒a) Fie g ∈ K[X] cu g(x) = 0, g ≠ 0. Din ipotez ă, f |g, deci deg f ≤ deg g. †
8 Definiție. Fie K ⊆ L o extindere de corpuri și fie x ∈ L algebric peste K. Polinomul
minimal al lui x peste K (notat Irr( x, K)) este polinomul monic din K[X] care satisface una din
condițiile echivalente de mai sus. De exemplu, Irr( 2, Q) = X 2 – 2 deoarece X 2 – 2 ∈ Q[X]
este monic, ireductibil în Q[X] și are rădăcină pe 2.
9 Definiție. Fie K ⊆ L o extindere de corpuri. Atunci L are o structur ă canonică de K-spațiu
vectorial: înmul țirea unui „scalar” din K cu un „vector” din L este înmul țirea din L.
Dimensiunea lui L văzut ca spa țiu vectorial peste K se numește gradul extinderii K ⊆ L și se
notează [L : K]. O extindere se nume ște extindere finit ă dacă gradul său este finit.
De exemplu, în extinderea R ⊆ C, elementul i ∈ C este algebric peste R, deoarece este
rădăcina polinomului X 2 + 1 ∈ R[X]. Gradul extinderii este [ C : R] = 2, deoarece {1, i} este o
bază a R-spațiului liniar C.
Fie extinderea K ⊆ L și x ∈ L. Sînt de prim ă importan ță următoarele no țiuni:
– subinelul lui L generat11 de K și {x}, notat K[x]. Are loc (demonstra ți):
K [x] = {a0 + a1 x + … + an x n | n ∈ N, ai ∈ K, 0 ≤ i ≤ n} = Im evx,
unde evx : K → L este morfismul de evaluare în x.
– subcorpul lui L generat de K și {x}, notat K(x). Are loc:
K(x) = {αβ −1 | α, β ∈ K[x], β ≠ 0}.
De exemplu, subcorpul lui C generat de Q și 2 e s t e Q(2) = Q[2] = {a + b2 | a,
b ∈ Q} (demonstra ți!). Se observ ă că nu este nevoie s ă luăm toate expresiile polinomiale (de

11 Subinelul lui L generat de o submul țime S a lui L este definit ca intersec ția tuturor subinelelor lui L care
includ S. La fel se define ște subcorpul generat de S.

31
orice grad) în 2 , cu coeficien ți în Q, ca în caracterizarea (S), ci doar cele de grad mai mic
decît 2 = grad Irr( 2, Q). De asemenea, are loc și Q(2) = Q[2 ]. Lucrul acesta nu este
întîmplător și este caracteristic elementelor algebrice :
10 Teorem ă (de caracterizare a elementelor algebrice). Fie K ⊆ L o extindere de corpuri și
x ∈ L. Următoarele afirma ții sînt echivalente:
a) x este algebric peste K. b) K
[x] este corp.
c) K[x] = K(x).
d) Extinderea K ⊆ K(x) este finită.
Dacă x este algebric peste K și f = Irr(x, K), grad f = n, atunci K [X]/( f ) ≅ K(x). În
particular, [K(x) : K] = n și o bază a K-spațiului liniar K (x) este {1, x, …, xn − 1}.
Demonstra ție. a)⇒b) Fie f = Irr(x,K) ∈ K[X] și evx : K[X] → L morfismul de evaluare în x.
Avem Ker evx = f. Din teorema de izomor fism pentru inele, K[X]/( f ) ≅ Im evx = K[x]. Cum f
este ireductibil în K[X], idealul ( f ) este maximal și K[X]/( f ) este corp. Atunci K[x], izomorf
cu K[X]/( f ), este și el corp.
b)⇔c) Evident.
c)⇒a) Presupunem c ă x ≠ 0 și fie x−1 = a0 + a1x + … + anx n ∈ K[x] inversul lui x.
Înmulțind cu x, obținem a0x + a1x 2 + … + anx n+1 − 1 = 0, adică x este rădăcina unui polinom
nenul cu coeficien ți în K.
d)⇒a) Familia infinit ă {x i | i ∈ N} de elemente ale K-spațiului vectorial finit dimensional
K(x) este liniar dependent ă. Deci, exist ă o relație de dependen ță liniară de forma a0·1 + a1x +
… + anx n = 0, cu n ∈ N și a0, a1, …, an ∈ K, nu toți nuli, adic ă x este algebric peste K.
a)⇒d) Avem K-izomorfismul de corpuri K[X]/( f ) ≅ K(x). Acesta este și un izomorfism de
K-spații vectoriale. Fie n = grad f. Demonstr ăm că în K-spațiul vectorial K[X]/( f ), clasele
elementelor 1, X, …, X n − 1 sînt elementele unei baze. Dac ă a01[ + a1X [ + … + an − 1 X n −1[ = 0[,
cu a0, a1, …, an − 1 ∈ K, atunci g = a0 + a1X + … + an − 1X n −1 ∈ ( f ), adică f |g. Cum grad f = n,
rezultă că g = 0, adică a0, a1, …, an − 1 sînt nule. Pe de alt ă parte, folosind teorema împ ărțirii
cu rest, orice clas ă modulo f a unui polinom h ∈ K[X] are un reprezentant de grad mai mic
decît n. Aceasta înseamn ă că h[ este combina ție liniară cu coeficien ți în K de 1[, X [, …, X n −1[ .
Izomorfismul K[X]/( f ) ≅ K(x) duce X + ( f ) în x, deci baza { 1[, X [, …, X n −1[ } este dus ă în
baza { 1, x, …, x n − 1} în K[x]. †
11 Defini ție. Fie K un corp și x un element algebric peste K. Gradul extinderii K ⊆ K[x]
(egal cu grad Irr( x, K)) se nume ște gradul elementului x peste K .
Caracteristica char R a unui inel ( R, +, ·) cu unitate e este definit ă ca fiind 0 (dac ă ne ≠ 0,
∀n ∈ N*) sau cel mai mic num ăr natural n ≠ 0 astfel încît ne = 0 în R. Deci,
char Z = char Q = 0; char Zn = n. Caracteristica unui corp F este 0 sau un num ăr prim p.
(demonstra ți!).

32

12 Lemă. (endomorfismul Frobenius) Fie R un inel comutativ de caracteristic ă p > 0.
Atunci aplica ția ϕ : R → R, ϕ(x) = x p, ∀x ∈ R, este un morfism de corpuri (numit
endomorfismul lui Frobenius12 al lui R ). Dacă R este finit, atunci ϕ este bijectiv (este un
automorfism al lui R ). Notînd q = pn, atunci ϕ n = ϕ ◦…◦ϕ (de n ori ) este morfism, iar ϕ n-
(x) = xq, ∀x ∈ R.
Demonstra ție. Fie x, y ∈ R. Este clar c ă ϕ(xy) = ϕ(x)ϕ(y). Corpul R fiind comutativ, are
loc formula binomului lui Newton:
ϕ(x + y) = (x + y) p =∑
≤≤−
piiipi
p yxC
0= x p + y p,
ultima egalitate avînd loc pentru c ă p divide coeficien ții binomiali i
pC dacă 1 ≤ i < p (de ce?).
Morfismul de corpuri ϕ : R → R este injectiv, deci bijectiv dac ă R este finit.
Avem ( ϕ ◦ϕ)(x) = ϕ(xp) = (ϕ(x))p = 2px și, prin induc ție, ϕ n(x) = npx, ∀x ∈ R, ∀n ∈ N. †
Endomorfismul Frobenius este aplica ția identitate în cazul corpului Zp (din mica teorem ă a
lui Fermat, x p = x, ∀x ∈ Zp).
Vom da un criteriu pentru a decide dac ă un polinom are r ădăcini multiple, folosind
noțiunea de derivată formală a unui polinom.
13 Defini ție. Fie R un inel comutativ unitar și f = a0 + a1X + … + anX n ∈ R[X]. Numim
derivată (formală) a polinomului f polinomul
df := a1 + 2a2 X + … + nan X n −1.
Se mai folose ște notația df = f ' sau d f = f (1).
Un calcul direct arat ă că derivata formal ă are propriet ățile uzuale ale derivatei cunoscute
din Analiz ă:
( f + g)' = f ' + g', (af )' = af ', ( fg)' = f 'g + fg', ∀a ∈ R, ∀f, g ∈ R[X].
Compunerea morfismului d cu el însu și de n ori ( n ∈ N*) se noteaz ă dn; dn : R[X] → R[X].
Avem deci dn = d◦dn−1, ∀n ∈ N*, cu conven ția că d0 = id. Mai not ăm dnf = f (n), ∀f ∈ R[X].
14 Propozi ție. Fie F un corp, f ∈ F[X] un polinom de grad n > 0 și α ∈ F.
a) Există și sînt unice elementele b 0, …, bn ∈ F astfel încît ()∑
≤≤− =
nii
iXb f
0α.
b) Dacă α este rădăcină multiplă de ordin m (m ∈ N*) a polinomului f, atunci f (i)(α) = 0,
pentru orice i ∈ {0, …, m − 1}.
c) Dacă f (α) = f '(α) = 0, atunci α este rădăcină multiplă a lui f (de multiplicitate cel pu țin
2).
Demonstra ție. a) Prin induc ție după grad f. Dacă f = a0 + a1X, atunci f = a0+ a1α +
a1(X − α). Dacă grad f = n > 1, aplicînd teorema împ ărțirii cu rest, ob ținem f = (X − α)g + b0,

12 Ferdinand Georg Frobenius (1849-1917 ), matematician german.

33
cu b0 ∈ F și g ∈ F[X], grad g = n − 1. Scriind pe g sub forma dat ă de ipoteza de induc ție și
înlocuind în rela ția precedent ă, se obține rezultatul.
Unicitatea scrierii este echivalent ă cu F-liniara independen ță a mulțimii de polinoame
{(X − α)i | i ∈ N} în F[X], ușor de demonstrat.
b) Din rela ția dedusă la punctul a), rezult ă că (X − α)m | f dacă și numai dac ă b0, b1,…, bm−1
sînt nuli. Pe de alt ă parte, se demonstreaz ă ușor că f (i)(α) = i!bi, ∀i ∈ {0, …, n}. De aici
rezultă că f (i)(α) = 0, ∀i ∈ {0, …, m − 1}.
c) Din cele demonstrate pîn ă acum, ob ținem că f (α) = b0 = 0 și f '(α) = b1 = 0. Deci
(X − α)2 | f. †
În cazul polinoamelor cu coeficien ți într-un corp K, un element α dintr-o extindere E a lui
K este rădăcină multiplă a polinomului f dacă și numai dac ă este simultan r ădăcină a
polinomului și a derivatei sale, adic ă (X − α)| f și (X − α)| f '. Aceasta implic ă faptul că cmmdc
al lui f și f ' în E[X] este de grad ≥ 1. Însă cmmdc a dou ă polinoame se ob ține cu algoritmul lui
Euclid și nu depinde de corpul considerat : dacă K ⊆ L este o extindere de corpuri, iar f,
g ∈ K[X], atunci ( f, g)K[X] = ( f, g)L[X]. În concluzie:
15 Propozi ție. Fie K un corp și f ∈ K[X]. Atunci f are r ădăcini multiple dac ă și numai
dacă f și f ' nu sînt prime între ele. †
Astfel, se poate decide dac ă un polinom are r ădăcini multiple fără a cunoaște rădăcinile .
Putem acum enun ța și demonstra teorema de existen ță și unicitate pentru corpurile finite.
16 Teorem ă. a) Fie F un corp finit cu q elemente. Atunci există un număr prim p și n ∈ N*
astfel încît |F| = p n.
b) Pentru orice num ăr prim p și n ∈ N*, există un corp finit cu p n elemente.
Demonstra ție. a) Fie e elementul unitate al lui F. Atunci mul țimea multiplilor lui e,
P := {n·e | n ∈ N*}, este o submul țime a lui F și este finit ă. Deci exist ă p ∈ N* astfel încît
p·e = 0. Alegem p să fie minim cu aceast ă proprietate ( p = char F ). Dacă p nu ar fi prim,
atunci p = ab, cu 1 < a, b < p. Cum p·e = (ab)·e = (a·e)·(b·e) = 0, rezultă că a·e = 0 sau b·e = 0,
contradicție cu minimalitatea lui p.
Rămîne că există un unic p prim astfel încît p·e = 0. Deci P = {0, e, 2e, …, ( p − 1)e}.
Observăm că există o bijecție între P și Zp = {0[, 1[, …, p − 1[ } (inelul claselor de resturi
modulo p), dată de i·e 6 i [. Este chiar un izomorfism, dup ă cum se verific ă imediat. Deci P
este corp (fiind izomorf cu corpul Zp), iar F este o extindere a sa.
Interpretăm F ca un spa țiu liniar peste P. Atunci dimensiunea lui F peste P este finit ă, fie
dim PF = n. Deci F ≅ P n (izomorfism de spa ții liniare), adic ă |F| = pn.
b) Presupunem problema rezolvat ă: dacă F este corp finit cu q := p n elemente, grupul
(F*, ·) are q − 1 elemente. Aplicînd teorema lui Lagra nge privind ordinul unui element într-un
grup finit, ob ținem că x q −1 = 1, deci x q = x, ∀x ∈ F. Pe de alt ă parte, din punctul a), F conține

34

un subcorp izomorf cu Zp. Deci F este o extindere a lui Zp, iar X q − X ∈ Zp[X] se descompune
în factori liniari în F[X] (toate elementele din F sînt rădăcini ale lui X q − X).
Argument ăm acum astfel existen ța unui corp cu q = p n elemente: fie corpul Zp și
f = X q − X ∈ Zp[X]. Există o extindere E a lui Zp încît f se descompune în factori liniari în
E[X]. Consider ăm mulțimea F := {x ∈ E | x q = x}. Să demonstr ăm că F este subcorp al lui E
(va fi corpul cu q elemente c ăutat). Fie x, y ∈ F. Atunci ( xy)q = xqyq = xy, deci xy ∈ F. Avem
și (x + y)q = xq + yq (q = pn, deci x 6 xq este o putere a endomorf ismului Frobenius), deci
x + y ∈ F. Dacă x ≠ 0, atunci (x−1)q = (xq)−1 = x−1, deci x−1 ∈ F. Elementele lui F sînt exact
rădăcinile polinomului f, iar acestea sînt în num ăr de exact q. Într-adev ăr, un polinom de grad
q are cel mult q rădăcini; pe de alt ă parte, f nu are r ădăcini multiple, dup ă cum se vede
folosind criteriul cu derivata formal ă: f' = qXq − 1 − 1 = − 1, deci ( f, f') = 1. †
Grupul multiplicativ al unui corp finit este ciclic , proprietate pe care nu o demonstr ăm, dar
care are multe aplica ții:
17 Teorem ă. Fie F un corp finit cu q elemente. Atunci grupul (F*, ·) este ciclic: exist ă
α ∈ F* astfel încît F* = {α i |1 ≤ i ≤ q − 1}. Un astfel de element α se nume ște element
primitiv al lui F. †
18 Teorem ă. Orice dou ă corpuri finite care au acela și cardinal sînt izomorfe.
Demonstra ție. Fie F, E corpuri finite cu q = pn elemente (cu p prim) și α ∈ F un element
primitiv. Atunci f = Xq − X ∈ Zp[X] are rădăcina α în F. Pe de alt ă parte, f este produs de
polinoame ireductibile în Zp[X]; deci exist ă un (unic) factor ireductibil g al lui f astfel încît
g(α) = 0. Atunci grad g = [Zp(α) : Zp] = [F : Zp] = n. Fie β o rădăcină a lui g în E (g are toate
rădăcinile în E), atunci [ Zp[β] : Zp] = grad g = n = [E : Zp], deci Zp[β] = E. Avem acum
izomorfismele: F = Zp[α] ≅ Zp[X]/(g) ≅ Zp[β] = E. †
Corpul finit cu p n elemente (unic pîn ă la izomorfism) se noteaz ă cu GF (p n) (Galois
Field = corp Galois)13 sau Fpn .
Din existen ța unui corp finit F cu pn elemente rezult ă că există polinoame ireductibile de
grad n cu coeficien ți în Zp: de exemplu, polinomul minimal peste Zp al unui element primitiv
al lui F. Construc ția concret ă a corpului cu pn elemente este dat ă de:
19 Propozi ție. Pentru orice n ∈ N*, există măcar un polinom ireductibil de grad n în
Fp[X]; pentru orice astfel de polinom f, Fp[X]/( f ) este un corp cu p n elemente. †
Problema construc ției efective a unui corp cu pn elemente se reduce la c ăutarea unui
polinom ireductibil g de grad n în Zp[X]. Corpul c ăutat va fi inelul factor Zp[X]/(g).

13 Structura corpurilor finite a fost determinat ă de Galois în 1830.

35
20 Exemplu: Corpul cu 4 elemente . Fie Z2 = F2 = {0, 1} corpul cu dou ă elemente
(omitem c ăciula pentru a nota clasele modulo 2. Deci, 1 + 1 = 0). Căutăm un polinom
ireductibil de grad 2 in Z2[X]. Polinomul
g = X 2 + X + 1
nu are rădăcini în Z2 (g(0) = 1, g(1) = 1) și are grad 2, deci este ireductibil. A șadar corpul cu 4
elemente este:
F4 = []
()[] {}2
2 () |Xhg h Xg=+ ∈FF ,
unde h + (g) notează clasa lui h modulo g. Din teorema împ ărțirii cu rest, ∀h ∈ F2[X] se scrie
ca h = gq + r, unde q, r ∈ F2[X] și deg r < 2 = deg g. Trecînd la clase modulo g:
h + (g) = gq + r + (g) = r + (g), deoarece clasa lui g este 0. Un polinom oarecare de grad < 2 e
de forma r = a + bX, a, b ∈ F2. Identific ăm a ∈ F2 with a + (g) ∈ F4 și notăm X + (g) cu α.
Obținem că elementele lui F4 sînt de forma
a + bX + (g) = a + bα, cu a, b ∈ F2
F4 = Z2[X]/(g) = {a + bα | a, b ∈ Z2} = {0, 1, α, 1 + α}, unde α 2 = α + 1.
Cum X 2 + X + 1 + (g) = 0 + (g) , rezultă că α satisface α 2 + α + 1 = 0, adică α 2 = α + 1.
Rezumînd:
F4 = { a + bα | a, b ∈ F2} = {0, 1, α, 1 + α}, unde α 2 = α + 1.
De exemplu, α(1 + α) = α 2 + α = α + 1 + α = 1
α + (1 + α) = 1
Am folosit c ă α 2 = α + 1 și α + α = 0. Un element primitiv din F4 este α.

Exerciții
1. (Caracteristic a unui inel) Fie K un inel și e elementul s ău unitate. Dac ă există k ∈ N* astfel
încît ke = 0, atunci definim car K = min{ k ∈ N* | ke = 0}. În caz contrar, punem car K = 0.
a) Demonstra ți că, dacă K este integru, atunci car K = 0 sau un num ăr prim.
b) Dacă K este corp de caracteristic ă p > 0, atunci K are un unic subcorp izomorf cu Zp.
c) Dacă K este corp de caracteristic ă 0, atunci K are un unic subcorp izomorf cu Q.

36

2. Fie ( G, ·) un grup finit. Definim exponentul lui G, exp( G) := cmmmc{ord a |
a ∈ G} = min{ n | xn = 1, ∀x ∈ G}.14 Să se arate c ă:
a) Dacă a, b ∈ G, ab = ba și (ord a, ord b) = 1, atunci ord ab = (ord a)·(ord b).
b) Pentru orice a, b ∈ G cu ab = ba, există c ∈ G cu ord c = [ord a, ord b].
c) Dacă G este abelian, exist ă un element al lui G care are ordinul egal cu exp( G).
3. Dacă R este inel comutativ integru, iar G este un subgrup finit al lui ( U(R), ·), atunci G este
ciclic.
4. Dacă F este un corp cu p n elemente, iar K este un subcorp al s ău, atunci exist ă m|n astfel
încît | K| = p m. Reciproc, pentru orice divizor m al lui n există un unic subcorp al lui F cu
p m =: r elemente, anume K = {x ∈ F| x r = x}.
5. Fie F un corp finit și m ∈ N*. Demonstra ți că există un polinom ireductibil de grad m în
F[X].
6. Construiți corpuri finite cu 4, 8, 16, 25, 9 și 27 elemente. Pentru fiecare din ele g ăsiți cîte
un element primitiv.
7. (Numărul polinoamelor ireductibile de grad m cu coeficien ți într-un corp finit ) Fie F ⊆ L o
extindere de grad m de corpuri finite, unde F are q elemente. Pentru orice d ∈ N*, notăm
Pq, d = {f ∈ F[X] | grad f = d, f ireductibil și unitar}.
a) Demonstra ți că () ∏∏ ∏∈ ∈= − =−mdP f Lq
dqmf X X X
, αα .
b) Notăm cu Rf = {α ∈ L | f(α) = 0}, ∀f ∈ F[X]. Arătați că ∪{Rf | f ∈ Pq, d, d|m} = L
(reuniune disjunct ă).
c) Demonstra ți că qm = ∑d|m |Pq, d|·d.
d) Calcula ți P2, m și P3, m, 1 ≤ m ≤ 6.
8. Scrieți un algoritm eficient de calcul al lui br, unde b este un element dintr-un inel sau
monoid pentru care se cunoa ște un algoritm de înmul țire a două elemente oarecare, iar r este
un număr natural. (Ind. Folosi ți ridicări la pătrat repetate și pe înmul țiri cu b, cînd e cazul.
Exemplu: pentru a calcula a = b22, scriem mai întîi 22 10 în baza 2, 22 = 10110 2 și calculăm
succesiv a = b, b2 = a*a, b5 = (a*a)*b, b10 = a*a, b21 = (a*a)*b. Vezi tabel:

Pasul 0 1 2 3 4
Cifra binar ă a lui r 1 0 1 1 0
Valoarea lui a b b2 = a*ab5 = (a*a)*b b11 = (a*a)*b b22 = a*a

14 Din teorema lui Lagrange, exp( G) divide cardinalul lui G.

37
IV. Coduri liniare: codare și decodare
Un cod este inutilizabil f ără algoritmi eficien ți de codare și decodare. Descriem cîteva
principii generale de codare și decodare pentru coduri liniare. Fix ăm un corp finit F cu q
elemente și presupunem c ă toate spa țiiile liniare sînt peste F.
Dacă un cod C tip [n, k] peste F are o matrice generatoare G, liniile sale g1,…, gk formează
o bază în C. Codul C poate coda cuvinte mesaj de lungime k în cuvinte cod de lungime n
astfel: un mesaj de forma m1… mk ∈ F k este codat ca m1g1 + … + mkgk. În formă matricial ă,
m = m1… mk este codat ca mG ∈ F n. Desigur, forma matricei generatoare ar trebui aleas ă
astfel încît procedura de codare s ă fie cît mai economic ă. O astfel de form ă este forma
standard, care duce la o codare sistematic ă.
1 Definiție. O matrice generatoare G a unui cod liniar C tip [ n, k] peste F este în formă
standard 15 dacă G = (Ik | A), unde Ik este matricea identitate k × k și A este o matrice
k × (n − k) peste F:
G = 11 12 1
21 22 2
12 ,10 0
01 0
00 1nk
nk
kk k n kaa a
aa a
aa a−
−
−⎡⎤
⎢⎥
⎢⎥⎢⎥
⎢⎥⎢⎥⎣⎦……
……%… … … ………

Dacă G e s t e î n f o r m ă standard, ca mai sus, cuvîntul mesaj m1… mk este codat ca
mG = m1… mkc1… cn − k, adică simbolurile de control c 1… cn − k sînt adăugate la cuvîntul
mesaj m1… mk pentru a forma cuvîntul cod. Desigur,
ci = m1a1i + … + mkaki, 1 ≤ i ≤ n − k.
În acest caz, {1, 2, …, k} este mul țimea de coordonate care poart ă simbolurile de
informație. Orice cuvînt cod e perfect determinat de primele sale k coordonate. Aceasta
înseamnă că proiecția pe primele k coordonate π : C → F k, π(x1… xn) = (x1… xk), este o
bijecție liniară (un izomorfism). Mai general:
2 Definiție. Fie C un cod liniar [ n, k, d ]. O mulțime S ⊆ {1, 2, …, n} de coordonate se
numește mulțime de informa ție (information set) dacă proiecția pe coordonatele din S,

15 Uneori o matrice este declarat ă în formă standard dac ă G = (A | Ik ).

38

πS : C → F |S|, πS(x1… xn) = (xi)i ∈ S este un izomorfism. A șadar, orice mul țime de informa ție
are k elemente (deoarece C și F |S| sînt izomorfe, au aceea și dimensiune).
Observăm că: S este o mul țime de informa ție ⇔ |S| = k și ∀x ∈ C, πS(x) = 0 ∈ F |S| implică
x = 0 (singurul cuvînt cod care e 0 pe S este cuvîntul 0).
3 Propozi ție. Fie G o matrice generatoare a lui C și H o matrice de paritate a lui C.
Următoarele afirma ții sînt echivalente:
a) S ⊆ {1, 2, …, n} este o mul țime de informa ție.
b) Coloanele lui G corespunz ătoare coordonatelor din S sî nt liniar independente.
c) Coloanele lui H corespunz ătoare coordonatelor din {1, 2,…, n} \ S sînt liniar
independente.
Demonstra ție. Fie g1, …, gk liniile lui G și H1, …, Hn coloanele lui H. Coloanele lui G
correspunz ătoare coordonatelor din S formează o matrice R tip k × k.
“a)⇒b)” Fie r1,…, rk liniile lui R. O relație de dependen ță liniară α1r1 + … + αkrk = 0
correspunde unui cuvînt cod nenul x = α1g1 + … + αkgk cu πS(x) = 0, contradic ție .Astfel,
rang R = k și coloanele lui R sînt independente.
“b)⇒a)” Avem rang R = k, deci liniile lui R sînt independente. Un cuvînt cod nenul
x = α1g1 + … + αkgk cu πS(x) = 0 conduce la o rela ție de dependen ță liniară
α1r1 + … + αkrk = 0, contradic ție.
“a)⇒c)” Pentru simplitate, presupunem c ă S = {1, 2, …, k}. Dacă, prin absurd, coloanele
Hk + 1, …, Hn nu sînt liniar independente, exist ă αk + 1, …, αn ∈ F, nu toți zero, astfel încît
αk + 1Hk + 1 + … + αnHn = 0. Atunci 0…0 αk + 1…αn ∈ C (căci x1… xn ∈ C dacă și numai dac ă
x1H1 + … + xnHn = 0), contradic ție.
Restul implica țiilor sînt propuse ca exerci țiu. †
4 Propozi ție. Fie C un cod tip [n, k, d ] și fie S ⊆ {1, 2, …, n}.
a) Dacă |S| ≥ n − d + 1, atunci S include o mul țime de informa ție.
b) C este cod MDS ⇔ orice mul țime de k coordonate este mul țime de informa ție.
Demonstra ție. a) Fie G o matrice generatoare a lui C și fie GS matricea format ă din
coloanele lui G care corespund coordonatelor din S. Presupunem c ă S nu include o mul țime de
informație. Aceasta înseamn ă că orice k coloane din GS sînt liniar dependente, deci
rang GS < k. Deci liniile lui GS sînt dependente, și aceasta produce un cuvînt cod nenul x care
este zero pe S (cf. demonstra ția precedent ă). Dar atunci wt( x) ≤ n − |S| ≤ d − 1, contradic ție.
b) “⇒”Avem : C este MDS ⇔ d = n − k + 1. Deci, dac ă S are k elemente, k ≥ n − d + 1 și
aplicăm a).
“⇐” Presupunem c ă d < n − k + 1. Fie 0 ≠ x ∈ C cu wt( x) = d < n − k + 1. Atunci
S = {i | xi = 0} are n − d > k − 1 element și S nu este mul țime de informa ție, contradic ție. †
Nu orice cod liniar are o matrice generatoare în form ă standard, dar este echivalent cu un
cod care are. În ceea ce urmeaz ă schițăm o demonstra ție a acestui fapt.

39
5 Definiție. Spunem c ă o matrice peste F este în formă eșalon pe linii (REF, row echelon
form ) dacă:
– toate liniile nenule (i.e. cu cel pu țin un element nenul) sînt deasupra oric ărei linii formate
doar din zerouri;
– primul (de la stînga) coeficient nenul (numit pivot ) al unei linii nenule este întotdeauna
strict mai la dreapta pivotului de pe linia de deasupra.
Dacă în plus fiecare pivot este 1 și este unicul element nenul de pe coloana sa, spunem c ă
matricea este in forma eșalon redus ă pe linii (reduced row echelon form, RREF).
Spre exemplu, fie matricele:
A = 1202
0010
0001⎡⎤
⎢⎥
⎢⎥
⎢⎥⎣⎦; B = 1200
0010
0001⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
A este în REF, B este în RREF. Mai mult, B și A sînt echivalente (B se obține din A prin
înlocuirea liniei 1 cu linia 1 + (− 2)·linia 3). Observ ăm că o matrice k × n de rang k în RREF
conține coloanele matricei identitate I k.
Dacă A ∈ M(k, n, F ) și 1 ≤ i, j ≤ k , 1 ≤ j ≤ k, a ∈ F*, definim transform ările elementare de
tip I, II, III asupra liniilor lui A :
Tip I: se adun ă la linia i linia j înmulțită cu a.
Tip II: se permut ă linia i cu linia j.
Tip III: se înmul țește linia i cu a.
6 Exercițiu. Demonstra ți că orice transformare elementar ă asupra liniilor lui A produce o
matrice A' cu proprietatea c ă subspațiul generat de liniile lui A' este egal cu subspa țiul generat
de liniile lui A.
Un rezultat cunoscut de Algebr ă liniară afirmă că, pentru orice matrice A ∈ M(k, n, F),
există un șir finit de transform ări elementare asupra liniilor lui A, care transform ă matricea
A într-o matrice A' în RREF și care are subspa țiul generat de linii egal cu cel generat de
liniile lui A. Mai mult, matricea A' cu aceste propriet ăți este unic ă (și se nume ște forma
eșalon redus ă pe linii a lui A).
Rezultatul de mai sus înseamn ă că, plecînd de la o matric e generatoare oarecare G a unui
cod liniar C, obținem (prin transform ări elementare pe liniile lui A) o matrice generatoare G1 a
lui C, care este în RREF; G1 conține coloanele matricei identitate (dar nu neap ărat în ordinea
necesară încît G1 să fie în form ă standard). O permutare adecvat ă a coloanelor furnizeaz ă o
matrice G' (în formă standard). Matricea G' este matrice generatoare a unui cod C', care este
echivalent pîna la o permutare cu C. Rezumînd:
7 Propozi ție. Orice cod liniar este echivalent pîn ă la o permutare cu un cod care are o
matrice generatoare în form ă standard. †

40

O matrice generatoare în form ă standard furnizeaz ă imediat o matrice de paritate:
8 Propozi ție. Fie C un cod liniar [n, k, d ] astfel încît G = (Ik | A) este o matrice
generatoare a lui C în form ă standard. Atunci H := (− AT | In − k) este o matrice de paritate a
lui C (adică o matrice generatoare pentru C⊥).
Demonstra ție. Un calcul direct arat ă că orice linie a lui H este ortogonal ă cu orice linie a
lui G. Deci subspa țiul generat de liniile lui H este inclus în C⊥. Deoarece rang H = n − k (H
conține In − k ca submatrice) și dim C⊥ = n − k, H este matrice generatoare pentru C⊥. †
Pentru a descrie algoritmi de decodare pentru coduri liniare avem nevoie de no țiunea de
coset al unui subspa țiu liniar. Construc ția e similar ă cu cea de la inelul factor.
9 Definiție. Fie U un subspa țiu al spațiului liniar V. Relația pe V, definită de:
x ≡ y(mod U) ⇔ x − y ∈ U
este o rela ție de echivalen ță (relația de congruen ță modulo U). Clasa de echivalen ță a
elementului v ∈ V se numește cosetul lui U determinat de v. Se vede u șor că acest coset este:
v + U = {v + u | u ∈ U}.
Astfel, cosetul lui U determinat de v se obține adunînd v la fiecare vector al lui U, și are
același număr de elemente ca U. Mulțimea tuturor coseturilor lui U se numește spațiul liniar
factor V/U; acesta e spa țiu liniar dac ă definim opera țiile astfel: pentru orice v, w ∈ V:
(v + U ) + (w + U) = v + w + U
λ(v + U) = λv + U.
Verificarea axiomelor este imediat ă. Au loc urm ătoarele rezultate clasice de Algebr ă
liniară:
10 Teorem ă. Fie |F| un corp cu q elemente și U ≤ FV. Atunci orice baz ă a lui U poate fi
completat ă pînă la o bază a lui V. Dac ă {u1, …, uk} este o baz ă a lui U și {u1, …, uk, uk + 1, …,
un} este o baz ă a lui V, atunci {uk + 1 + U, …, u n + U} este o baz ă a lui V /U. În particular,
dim( V/U) = dim( V) − dim( U) = numărul de coseturi distincte ale lui U. A șadar, exist ă qn − k
coseturi ale lui U și fiecare coset are q k elemente. †
11 Teorem ă. Fie U și V F-spa ții liniare finit dimensionale și fie ϕ : U → V o aplica ție
liniară. Atunci:
a) Nucleul lui ϕ, Ker ϕ := {u ∈ U | ϕ(u) = 0} este subspa țiu liniar al lui U.
b) (Teorema fundamental ă de izomorfism) Exist ă un izomorfism canonic:
ImKerUϕϕ≅ , u + Kerϕ 6 ϕ(u), ∀u ∈ U.
c) dim( U) = dim(Im ϕ) + dim(Ker ϕ). †
Ne întoarcem la problema decod ării. Fie w cuvîntul cod original transmis și fie x cuvîntul
recepționat. Atunci x = w + ε, unde ε este cuvîntul eroare (ε este un cuvînt din F n). Deci x și ε

41
sînt în acela și coset al lui C, anume x + C. Pentru a g ăsi w, e suficient s ă găsim ε. Algoritmul
de distanță minimă, pentru x dat, caut ă acel w ∈ C care este cel mai aproape de x. Deoarece
ε = x − w, aceasta înseamn ă că ε este cuvîntul de pondere minim ă în cosetul x + C.
Sîntem condu și la defini ția următoare. Pentru orice coset D al lui V, un vector ε din D se
numește un lider al cosetului D dacă ponderea sa este cea mai mic ă printre ponderile
cuvintelor din D: wt( ε) = min{wt( x) | x ∈ D}. Un coset poate avea mai mul ți lideri (de aceea și
pondere, desigur).
Astfel, receptorul caut ă liderul ε al cosetului ce con ține x și decodeaz ă x în x − ε. Putem
enunța următorul algoritm:
Pentru un cod dat C, se calculeaz ă (înaintea oric ărei transmisii) coseturile lui C cu liderii
respectivi și se aranjeaz ă într-un tablou (numit tablou Slepian , sau tablou standard ). În
practică, prima linie a tabloului const ă în cuvintele lui C, cu 0 în prima pozi ție. Dacă j − 1 linii
au fost deja scrise, dintre cuvintele care nu sî nt deja scrise se alege un cuvînt de pondere
minima ej; acesta e declarat lider al cosetului, și este scris ca primul element al liniei j. Pe
locul i al liniei j scriem ej adunat cu elementul de pe locul i din prima linie. Astfel am ob ținut
linia j, care este cosetul ej + C. Continuăm procedura pîna epuiz ăm toate cuvintele din F n. Se
obține un tablou cu q n − k linii (fiecare linie este coset al lui C și are q k elemente).
La recepția lui x, se caută cosetul care con ține x, și fie ε liderul acestui coset. Se decodeaz ă
x în x − ε (adică exact cuvîntul din prima linie care e deasupra lui x).
12 Observa ție. Fie C un cod [n, k, d ], cu capacitate de corectare e. Atunci:
a) Orice lider de coset de pondere ≤ e este unic . Deci, dac ă nu au loc mai mult de e erori
(i.e. vectorul de eroare are pondere ≤ e), algoritmul de mai sus decodeaz ă corect cuvîntul
receptat. Demonstra ție: presupunem c ă u și v au ponderi ≤ e și sînt în acela și coset. Atunci
wt(u − v) ≤ wt(u) + wt(v) ≤ 2e < d și u − v ∈ C. Aceasta implic ă u − v = 0, căci distan ța
minimă a lui C este d.
b) Dacă d este par (
d = 2e + 2), atunci există un coset care are doi lideri distinc ți de
pondere e + 1. Deci, exist ă un cuvînt cod c și un vector eroare ε de pondere e + 1 astfel încît
c + ε aparține unui coset cu cel pu țin doi lideri (adic ă c + ε nu poate fi unic decodat). Acest
fapt e normal, c ăci e + 1 erori dep ășesc capacitatea de corectare a lui C. Lăsăm demonstra ția
cititorului.
Decodarea cu sindroame. Algoritmul de decodare prezentat cere stocarea în memorie a
tuturor cuvintelor din Fn, ceea ce poate fi costisitor sau chiar imposibil pentru n mare. O
variantă a algoritmului de mai sus folose ște următorul concept:
13 Defini ție. Fie C un cod liniar tip [ n, k, d ] peste F, H o matrice de paritate pentru C și
x ∈ F n. Vectorul sH(x) = HxT ∈ F n − k se numește sindromul lui x.

42

Observăm că sH : F n → F n − k, sH(x) = HxT, ∀x ∈ F n, este o func ție liniară.
Două cuvinte sînt în acela și coset al lui C dac ă și numai dac ă au acela și sindrom: x ∈ C
⇔ sH(x) = 0. Deci, ∀u, v ∈ F n: u − v ∈ C⇔ sH(u) = sH(v).
Astfel, putem enun ța următorul algoritm (de decodare cu sindroame ):
Înaintea oric ărei transmisii se alc ătuiește o list ă care con ține sindroamele tuturor
coseturilor lui C pe o coloan ă și liderii coseturilor respective pe urm ătoarea coloan ă.
La recepția unui cuvînt x, se calculeaz ă sH(x). Dacă sH(x) = 0, atunci x ∈ C, adică nu au
avut loc erori.
Dacă sH(x) ≠ 0, receptorul caut ă liderul e care are acela și sindrom cu x (sH(e) = sH(x)). Apoi
x este decodat în x − e ∈ C.
Exerciții
1. Demonstra ți că dualul unui cod liniar MDS este tot MDS. ( Ind.: folosiți Prop. 4)
2. Demonstra ți că un cod binar MDS de lungime n este unul din urm ătoarele: codul de
repetiție tip [ n, 1, n], codul de paritate tip [ n, n − 1, 2], sau tot F2n, de tip [ n, n, 1]. (Ind:
considera ți o matrice generatoare și folosiți Prop. 4)
3. Există un cod binar tip [4, 2, 3]? ( Ind: încercați să construiți o matrice de paritate.)
4. Fie C codul liniar binar cu matrice de paritate
H = 110100
101010
011001⎛⎞
⎜⎟
⎜⎟⎜⎟⎝⎠
a) Găsiți o matrice generatoare a lui C și scrieți toate cuvintele cod din C.
b) Decoda ți : 110110; 011011; 101010.
5. (a) Arătați că orice cuvînt cod al unui c od binar autodual are pondere par ă.
(b) Arătați că orice cuvînt cod al unui cod ternar autodual are pondere multiplu de 3.
(c) Construi ți un cod autodual peste F5 astfel încît m ăcar unul din cuvintele cod nu are
pondere multiplu de 5.
(d) Fie x, y be cuvinte cod într-un cod autodual binar. Dac ă ponderile lui x și y sînt
divizibile cu 4, atunci ponderea lui x + y este multiplu de 4.
6. Fie C cod binar autodual tip [ n, k, d ].
(i) Demonstra ți că (1, 1, . . . , 1) ∈ C.
(ii) Demonstra ți că: fie toate cuvintele lui C au pondere multiplu de 4, fie exact jum ătate
din cuvintele lui C au pondere multiplu de 4.

43
(iii) Fie n = 6. Determina ți d.
7. Scrieți o matrice de paritate pentru un cod bina r autodual de lungime 10.

44

V. Construc ții de coduri noi din coduri existente
Descriem cîteva construc ții care produc noi coduri porn ind de la coduri cunoscute.
Construcțiile ce urmeaz ă arată că există coduri liniare cu parametri ce se afla în anumite rela ții
cu cei ai unui cod dat C. Adesea aceste coduri sînt mai "rele" decît C, dar au interes teoretic.
Detaliile de demonstra ție care lipsesc sînt l ăsate cititorului.
Fie C un cod liniar tip [ n, k, d ] peste F.
I. Lungire (lengthening). Fie C' = {(x1, …, xn, 0) | ( x1, …, xn) ∈ C}. Atunci C' este un cod
liniar tip [ n + 1, k, d ] (se spune c ă e obținut prin lungirea lui C). Prin induc ție, se vede c ă:
Pentru orice r ∈ N, există un cod liniar tip [n + r, k, d ].
II. Găurire (Puncturing) . Fixăm o coordonat ă i ∈ {1, …, n}. Ștergem coordonata i din
toate cuvintele cod ale lui C, și obținem un cod C' ⊆ F n − 1.
Pentru simplitate, presupunem c ă i = 1. Fie π : C → C', π(x1…xn) = x2…xn. E clar că π este
aplicație liniară surjectiv ă. Din teorema fundamental ă de izomorfism ( IV.11) , C/Kerπ ≅ C'.
Avem dou ă cazuri:
– Ker π = 0 (adică C izomorf cu C'). Atunci C' este cod tip [ n − 1, k]. Avem d(C') = d − 1
dacă există un cuvînt în C de pondere minim ă d care e nenul pe coordonata i. Altfel, d(C') = d.
– Ker π ≠ 0. Atunci Ker π = { x1…xn ∈ C | x2…xn = 0} = { α0…0 ∈ C | α ∈ F}. Ker π ≠ 0
înseamnă că d = 1 și dim Ker π = 1, deci dim C' = k − 1.
Deci: Dacă d > 1, atunci exist ă un cod [n − 1, k, d − 1]. Prin induc ție, pentru orice r < d, există
un cod [n − r, k, d − r].
Mai general, dac ă S ⊆ {1, …, n} este o mul țime de coordonate, prin ștergerea acestor
coordonate din cuvintele lui C, se obține un cod C
S (codul C găurit pe S). Are parametrii
[n − |S|, k', d' ], unde k' ≥ k − |S|, d' ≥ d − |S|.
III. Subcod. Există un cod tip [n, k − 1, d].
Intr-adevăr, fie x ∈ C de pondere d; formăm o bază a lui C cu primul vector x. Codul
generat de primii k − 1 vectori ai aceste baze are dimensiune k − 1 și distanță minimă d. Prin
inducție obținem: pentru orice r < k, există un cod tip [n, k − r, d].

45
IV. Există un cod tip [n, k, d − 1].
Pentru a demonstra aceasta, lungim C și formăm un cod [ n + 1, k, d ]; apoi aplic ăm o
găurire și obținem un cod [ n, k, d − 1]. Prin induc ție, pentru orice r < d, există un cod tip
[n, k, d − r].
V. Există un cod tip [n − 1, k − 1, d].
Dacă k = n, atunci C = F n, deci d = 1. Atunci F n − 1 este de tip [ n − 1, k − 1, d]. Presupunem
că k < n. Permutăm coordonatele lui C pentru a ob ține un cod liniar car e are o matrice de
paritate de forma H = (In − k | A). Ștergînd ultima coloan ă a lui H obținem o matrice H'. Rangul
lui H' este n − k căci are primele n − k coloane liniar independente. Deci H' este matrice de
paritate pentru un cod C' de lungime n − 1 și dimensiune n − 1 − (n − k) = k − 1. Cum orice
d − 1 coloane ale lui H sînt independente, acela și lucru se întîmpl ă pentru H', deci
d(C') = d' ≥ d. Dacă d' > d, applicăm IV și obținem un cod tip [ n − 1, k − 1, d. Prin induc ție,
pentru orice r < k, există un cod tip [n − r, k − r, d].
VI. Extinderea unui cod.
Fie C ⎯ = {(x1, …, xn, p) ∈ F n + 1| (x1, …, xn) ∈ C, x1 + …+ xn + p = 0} (numit codul extins al
lui C ). Astfel, fiec ărui cuvînt cod i se adaug ă un "simbol de paritate p" (în cazul unui cod
binar, este numit bit de paritate ). Atunci C ⎯ este un cod liniar [ n + 1, k]. Distanța sa este d sau
d + 1 (Exercițiu: discutați cazul binar!).
VII. Scurtare. Fie S ⊆ {1, …, n} o mulțime de coordonate. Fie
C(S) = {x1…xn ∈ C | xi = 0, ∀i ∈ S}
Prin găurirea lui C(S) pe S obținem un cod CS (codul C scurtat pe S ). Altfel spus: lu ăm
toate cuvintele cod din C care sînt 0 pe S, ștergem coordonatele din S și declarăm mulțimea de
cuvinte ob ținută ca noul cod.
Prin scurtarea unui cod MDS se ob ține tot un cod MDS (rezultat utilizat în practic ă):
14. Propozi ție. Fie C un cod tip [n, k, n − k + 1] (cod MDS). Atunci codul C scurtat pe
orice coordonat ă este un cod tip [n − 1, k − 1, n − k + 1] (tot un cod MDS). Prin induc ție,
scurtarea lui C pe orice r < k coordonate produce un cod MDS tip [n − r, k − r, d].
Demonstra ție. Presupunemc ă scurtăm C pe coordonata 1. Ob ținem
C1 = {x2…xn ∈ F n − 1 | 0x2…xn ∈ C}.
C1 este izomorf cu { x1…xn ∈ C | x1 = 0}, nucleul aplica ției π : C → F, π(x1… xn) = x1. Avem
că π nu este identic 0. într-adev ăr, dacă π = 0, atunci toate cuvintele din C sînt 0 pe
coordonata 1; deci C găurit pe coordonata 1 este un cod [ n − 1, k, d ], ceea ce contrazice
inegalitatea Singleton.
Deci π ≠ 0 și π este surjectiv ă. Avem dim C = dim Ker π + dim Im π, deci k = dim C1 + 1 ⇔
dim C1 = k − 1. Astfel, C1 este un cod tip [ n − 1, k − 1, d(C1)]. Inegalitatea Singleton spune c ă

46

d(C1) ≤ (n − 1) − (k − 1) + 1 = n − k + 1. Fie 0 ≠ x2… xn ∈ C1, deci 0 x2…xn ∈ C. Atunci
wt(x2…xn) = wt(0 x2…xn) ≥ n − k + 1. Așadar d(C1) ≥ n − k + 1. †
VIII Suma direct ă. Suma direct ă a două coduri este acela și lucru ca suma direct ă
(externă) a două spații liniare:
15. Propozi ție. Fie C 1 și C2 coduri liniare tip [n1, k1, d1] (resp. [n2, k2, d2]) peste F. Atunci
C1⊕C2 := {(c1, c2) ∈12nnF+| c1 ∈ C1, c2 ∈ C2}
este un cod liniar tip [n1 + n2, k1 + k2, min( d1, d2)] (numit suma direct ă a codurilor C1 și C2).
Dacă G1 și G2 sînt matrice generatoare, atunci1
20
0G
G⎡ ⎤
⎢ ⎥⎣ ⎦ este matrice generatoare pentru
C1⊕C2.
Demonstra ție. Fie
1 1{, , }k ee… ,
2 1{, , }k f f… baze în C1 (resp. C2). Se vede u șor că
12 11{( ,0), ,( ,0),(0 , ), ,(0 , )}kk eef f…… este bază în C1⊕C2. Cuvintele nenule de pondere minim ă
sînt de forma ( c1, 0) sau (0, c2), unde c1 și c2 sînt nenule de pondere minim ă. Deci ponderea
minimă este min( d1, d2). †
IX Construc ția (u, u + v) (“bar product”) Această construcție poate produce coduri
interesante și practice.
16. Propozi ție. Fie C 1 și C 2 coduri liniare tip [n, k1, d1] (resp. [n, k2, d2]) de aceeași
lungime peste F. Atunci
C1|C2 := {(u, u + v) ∈ F 2n | u ∈ C1, v ∈ C2}
este un cod liniar tip [2n, k1 + k2, min(2 d1, d2)]. Dacă G1 și G 2 sînt matrice generatoare,
atunci 11
2 0GG
G⎡⎤
⎢⎥⎣⎦ este o matrice generatoare pentru C 1|C2.
Demonstra ție. Fie
1 1{, , }k ee… ,
2 1{, , }k f f… baze în C1 (resp. C2). Atunci:
11 2 11 1{ ( , ) ,, (,) , ( 0 , ) ,, ( 0 , ) }kk k ee e e f f……
este o baz ă în C1|C2. Aceasta implic ă dim ( C1|C2) = k1 + k2 și afirmația despre matricea
generatoare .
Fie c = (u, u + v) un cuvînt nenul în C1|C2, u ∈ C1, v ∈ C2. Avem dou ă cazuri:
I. v = 0 Atunci u ≠ 0, deci wt( c) = 2wt( u) ≥ 2d1 ≥ min(2 d1, d2).
II. v ≠ 0 Atunci
wt(u, u + v) = wt(u) + wt(u + v) ≥ wt(u) + wt(v) − wt(u) = wt(v) ≥ d2 ≥ min(2 d1, d2)
(Am folosit faptul c ă wt(v + u) ≥ wt(v) − wt(u), ∀v, u ∈ F n. Demonstra ți!)
Deci, d(C1|C2) ≥ min(2 d1, d2). Pentru inegalitatea opus ă, observăm că dacă u ∈ C1 are
pondere d1, atunci ( u, u) ∈ C1|C2 și wt( u, u) = 2d1; dacă v ∈ C2 are pondere d2, atunci
(0, v) ∈ C1|C2 și wt(0 , v) = d2. †

47
Fie 1 vectorul din F2n cu toate componentele egale cu 1. Acest vector genereaz ă codul de
repetiție de lungime n, cod binar de tip [ n, 1, n], pe care îl not ăm tot cu 1; acest cod are doi
vectori: (0, …, 0) and (1, …, 1) = 1.
17 Corolar. Fie C un cod binar tip [n, k, d]. Atunci
C|1 := {(u, u) ∈ F22n | u ∈ C}∪{(u, u + 1) ∈ F22n | u ∈ C}
este un cod liniar tip [2n, k + 1, min(2 d, n)]. Dacă G ∈ M(k, n, F2) este o matrice generatoare
a lui C, atunci 0GG⎡⎤
⎢⎥⎣⎦ 1 ∈ M(k + 1, 2n, F2) este o matrice generatoare a lui C| 1. †
Ca o aplica ție, descriem o familie important ă de coduri care poate fi construit ă recursiv
folosind metodele de mai sus:
18 Defini ție. Codurile Reed-Muller binare de ordinul 1, R(1, m) (m ≥ 1) sînt definite astfel:
R(1, 1) : = F22; pentru orice m ≥ 1, R(1, m + 1) := R(1, m)|1.
19 Propozi ție. Pentru orice m ∈ N*, R(1, m) este un cod binar tip [2m , m + 1, 2m − 1]. Mai
mult, orice cuvînt cod nenul are pondere 2m − 1, cu excep ția cuvîntului 1 (de pondere 2m ).
Demonstra ție. R(1, 1) este cod binar tip [2 , 2, 1]. Demonstr ăm afirma țiile prin induc ție
după m. Presupunem c ă R(1, m) este cod tip [2m , m + 1, 2m − 1]. Din Corolarul 17, R(1, m + 1)
este cod tip [2·2m , m + 2, min(2m , 2m)], ca în enun ț. Fie 0 ≠ c ∈ R(1, m + 1). Dacă c = (u, u),
cu u ∈ R(1, m), atunci wt( u, u) = 2wt( u) = 2·2m − 1 dacă u ≠ 1 (sau 2·2m dacă u = 1). Dacă
c = (u, u + 1), u ∈ R(1, m), u ≠ 1, atunci wt( u + 1) = 2m − wt(u) = 2m − 1(observați că adunînd 1
la u biții care erau 1 devin 0 și invers), deci wt( u, u + 1) = 2m. Dacă c = (1, 1 + 1) = (0, 1),
atunci wt( c) = 2m. †
Codul Reed-Muller R(1, 5) a fost folosit pentru comunica ții din spa țiul cosmic în 1972,
cînd sonda Mariner a transmis fotografii cu Marte.
Construcția (u, u + v) poate fi folosit ă pentru a defini recursiv codurile Reed-Muller binare
de ordin r:
20 Defini ție. Pentru r ∈ N și orice m ≥ r, definim codul binar Reed-Muller de ordin r,
R(r, m):
a) R(0, m) este codul binar de repeti ție de lungime 2m. Este un cod tip [2m, 1, 2m].
b) R(r, r) este întreg spa țiul 2
2rF (codul binar tip [2r, 2r, 1]2).
c) Pentru orice r > 0 și r + 1 ≤ m, R(r, m) := R(r, m − 1)|R(r − 1, m − 1).
Fie G(r, m) o matrice generatoare a lui R(r, m). Din defini țiile de mai sus rezult ă că putem
pune:
G(0, m) = [ ] 11 1… ; G(m, m ) =
2mI
Corolarul 17 permite să scriem:

48

G(r, m) = (, 1 ) (, 1 )
0( 1 , 1 )Grm Grm
Gr m−− ⎡ ⎤
⎢ ⎥− − ⎣ ⎦
Se pot demonstra urm ătoarele fapte despre coduri le Reed-Muller folosind aceast ă definiție:
21 Teorem ă. Fie r ∈ N și m ≥ r. Atunci :
a) R(r, m) ⊆ R(s, m) if r ≤ s ≤ m.
b) dim R(r, m) = () () ()01mm m
r++… .
c) d(R(r, m)) = 2m − r.
d) R(m, m ) ⊥ = 0; for any r < m, R(r, m) ⊥ = R(m − r − 1, m). †
Alte construc ții importante ( întrețesere și concatenare ) se vot descrie în capitolul de
Aplicații.

Exerciții
1. Demonstra ți că prin scurtarea unui cod tip [n, k, d ] pe o coordonat ă se obține un cod tip
[n − 1, k', d' ], unde k − 1 ≤ k' ≤ k și d' ≥ d.
2. Presupunem c ă G este o matrice generatoare în form ă standard pentru codul tip [ n, k, d ] C.
Scrieți o matrice generatoare pentru C scurtat pe prima coordonat ă.
3. Fie C codul binar cu matricea generatoare
11110
0101100111⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥ ⎣ ⎦
Scrieți o matrice generatoare pentru C scurtat pe coordonata 2.
4. Scrieți toate cuvintele codului R(1, m), pentru m = 3, 4, 5.
5. Presupunem c ă există un cod liniar tip [ n, k, d ] peste F. Rezultă că există un cod liniar tip
[n + 1, k + 1, d] ? Dar un cod liniar tip [ n + 1, k, d + 1]?

49 VI. Coduri ciclice
Clasa codurilor ciclice este ob ținută prin impunerea unei structuri suplimentare codurilor
liniare. Aceasta permite o descriere mai precis ă, o construc ție mai ușoară și compact ă și
algoritmi rapizi de codare și decodare. Fix ăm un corp finit F cu q elemente.
1 Definiție. Un cod liniar peste F se nume ște ciclic dacă, pentru orice
c = (c0, c1,…, cn − 1) ∈ C, rezultă că permutarea ciclic ă la dreapta a lui c, adică
(cn − 1, c0, …, cn − 2) este tot în C.
Codurile ciclice au o structur ă algebrică suplimentar ă:
2 Teorem ă. Fie C un cod liniar peste F și fie R n inelul factor F [X]/(X n − 1). Fie x clasa lui
X modulo (X n − 1) și fie submul țimea lui R n:
I C := {c0 + c1x + … + cn − 1x n − 1|(c0, c1,…, cn − 1) ∈ C}.
Atunci: C este ciclic dac ă și numai dac ă IC este un ideal în R.
Demonstra ție. Fie C cod ciclic. IC este clar parte stabil ă la adunare în Rn. Fie
(c0, c1,…, cn − 1) ∈ C. Atunci avem în Rn:
x(c0 + c1x + … + cn − 1x n − 1) = c0x + c1x2 + … + cn − 1x n = cn − 1 + c0x + … + cn − 2x n − 1 ∈ IC
Am folosit c ă în Rn x n = 1. Pentru orice u = b0 + b1x + … + bmx m ∈ Rn și v ∈ IC, uv este o
combinație liniară de elemente de forma xt(c0 + c1x + … + cn − 1x n − 1), care sînt în IC (se
folosește o induc ție, cazul t = 1 a fost demonstrat).
Dacă IC este ideal, atunci, ∀(c0, c1,…, cn − 1) ∈ C, avem x(c0 + c1x + … + cn − 1x n − 1)
= cn − 1 + c0x + … + cn − 2x n − 1 ∈ IC, deci ( cn − 1, c0, …, cn − 2) ∈ C. †
Demonstra ția de mai sus arat ă că este util s ă vedem cuvintele unui cod ci clic de lungime n
peste F ca polinoame mod( X n − 1); astfel, vom identifica cuvîntul ( c0, c1,…, cn − 1) ∈ C cu
c0 + c1x + … + cn − 1x n − 1 din Rn = F[X]/(X n − 1).
Studiul codurilor ci clice de lungime n peste F este așadar echivalent cu st udiul idealelor lui
Rn.
3 Lemă. a) Fie R inel și I un ideal în R. Atunci orice ideal al inelului factor R /I se poate
scrie unic sub forma J /I = {j + I | j ∈ J}, unde J este un ideal al lui R care include I. Mai
precis, aplica ția J 6 J/I este o bijec ție care păstrează incluziunile între mul țimea idealelor
lui R care includ I și mulțimea idealelor lui R /I.

50
b) Idealele lui F [X] sînt de forma (g) = {gh | h ∈ F[X]}, cu g ∈ F[X]. Pentru un ideal nenul
I al lui F [X], avem I = (g), dacă g este un polinom nenul din I de grad minim. Un astfel de
polinom g este numit generator al lui I.
Demonstra ție. a) Dacă B este ideal în R/I, atunci IB := {r ∈ R | r + I ∈ B} este ideal în R și
B = IB/I (demonstra ți!).
b) Fie I un ideal nenul în F[X] și fie g ∈ I un polinom monic al c ărui grad e cel mai mic
printre gradele polinoamelor nenule din I. Dacă f ∈ I, atunci f = gq + r, unde q, r ∈ K[X],
deg r < deg g (sau r = 0). Cum r = f − gq și I is an ideal, avem r ∈ I; deg r < deg g implică
r = 0. Deci f = gq ∈ (g), ∀f ∈ I. †
4 Teorem ă. Pentru orice ideal I al lui R n = F[X]/(X n − 1), există un unic polinom monic
g ∈ F[X] astfel încît g| (X n − 1) și I = (g)/(X n − 1) = {hg mod( X n − 1) | h ∈ F[X]}.
Demonstra ție. Lema de mai sus spune c ă I = J/(X n − 1), pentru un ideal al lui F[X] care
include ( X n − 1). Dar J este de forma ( g), unde ( g) ⊇ (X n − 1), i.e. g|(X n − 1). †
Conchidem c ă un cod ciclic C este unic determinat de generatorul monic g din
demonstra ția de mai sus, numit polinomul generator al codului C. Deci, polinomul monic
g ∈ F[X] este polinomul generator al codului C de lungime n dacă și numai dac ă g|(X n − 1) și
C = {hg mod( X n − 1) | h ∈ F[X]}.
(Identificăm cuvintele din C cu polinoamele mod ( X n − 1)!)
5 Propozi ție. Fie C cod ciclic de lungime n și fie g polinomul s ău generator. Atunci orice
cuvînt din C poate fi unic scris sub forma hg, cu h ∈ F[X], deg h < deg g :
C = {hg mod( X n − 1) | h ∈ F[X], deg h < deg g}
În particular, dimensiunea lui C este k = n − deg g.
Demonstra ție. Deoarece g|(X n − 1), există d ∈ F[X] astfel încît X n − 1 = gd. Fie h ∈ F[X]
oarecare. Teorema împ ărțirri cu rest implic ă h = dq + r, pentru q, r ∈ F[X], deg r < deg g.
Deci (egalit ățile sînt mod( X n − 1)):
hg = (dq + r)g = gdq + rg = (X n − 1)q + rg = rg mod( X n − 1). †

Fie C un cod ciclic [ n, k, d ] și fie g polinomul s ău generator. Propozi ția de mai sus spune
că o bază pentru C este g, xg, …, xk − 1g. Presupunem c ă g = a0 + a1 X + … + an X n − k. Așadar,
o matrice generatoare a lui C este:
01
01
0100 0
00 0
00nk
nk
nkaa a
aa a
aa a−
−
−⎡⎤
⎢⎥
⎢⎥
⎢⎥⎢⎥⎢⎥⎣⎦……
……
# # ## ## ##
…… … ∈ M(k, n, F)
Presupunem de acum înainte c ă (q, n) = 1.

51
Această presupunere e necesar ă deoarece avem nevoie de o extindere a lui Fq în care
X n − 1 se descompune în factori liniari distincți (adică X n − 1 nu are r ădăcini multiple; din
criteriul cu derivata formal ă, aceasta echivaleaz ă cu ( X n − 1, nX n − 1) = 1⇔ nX n − 1 ≠ 0 ⇔
(q, n) = 1). Dacă o astfel de extindere F există, F are qm elemente. Cum r ădăcinile lui X n − 1
formează un subgrup de ordin n și F* are ordin qm − 1, din teorema lui Lagrange rezult ă
n | qm − 1. Fie ω un generator al lui F* (un element primitiv al lui F ); atunci α = () n qm1−ω are
ordin n in F* (este o rădăcină primitivă de ordinul n a unit ății în F ) și avem:
()∏−
=− =−1
01n
ii nX X α
Deoarece generatorul g divide X n − 1, rezultă că:
g = ()i
iIXα
∈−∏ , pentru o submul țime I ⊆ {0, 1,… , n − 1}.
Mulțimea I se numește mulțimea de defini ție a lui C (în raport cu α). Nu orice submul țime
a lui {0, 1,… , n − 1} este mul țime de defini ție pentru un cod ciclic, deoarece g trebuie să aibă
coeficienți în Fq. Avem nevoie de urm ătorul rezultat din teoria Galois.
6 Propoziție. Fie F ⊆ E o extindere de corpuri finite, |F| = q, |E| = q m. Atunci
F = {x ∈ E | x q = x}. Fie ϕ : E → E, ϕ(x) = x q. Extindem ϕ la ψ : E[X] → E[X],
ψ(a0 + a1 X + … + an X n) = ϕ(a0) + ϕ(a1) X + … + ϕ(an )X n
Atunci ψ este un morfism de inele și f ∈ F[X] dacă și numai dac ă ψ( f ) = f.
Demonstra ție. Faptul că F = {x ∈ E | x q = x} e demonstrat la Teorema III.16 .b). Cum ϕ
este automorfism (este o putere a automorf ismului Frobenius), un calcul direct arat ă căψ este
automorfism. Avem ψ(a0 + a1 X + … + an X n) = a0 + a1 X + … + an X n ⇔ ϕ(a0) = a0,
…, ϕ(an ) = an ⇔ a0, …, an ∈ F ⇔ a0 + a1 X + … + an X n ∈ F[X]. †

Aplicînd acest rezultat la g = ( )i
iIXα
∈−∏ , avem: g ∈ F[X] ⇔ g = ψ(g) = ()iq
iIXα
∈−∏ .
Deci:
7 Propoziție. Mulțimea I ⊆ {0, 1,… , n − 1} este mulțime de defini ție pentru un anumit cod
ciclic C dac ă și numai dac ă are proprietatea c ă, pentru orice i ∈ I , avem iq (mod n) este tot
în I. †
Se observ ă că g factorizeaz ă într-un produs de polinoame ireductibile di stincte peste Fq,
alese dintre factorii lui X n − 1. Un astfel de polinom ire ductibil este de fapt polinomul
minimal mi al lui α i pentru un i, 0 ≤ i < n, și trebuie s ă aibă și rădăcinile obținute aplicînd
automorfismul z 6 z q, adică α i, α iq, α iq2, … . În concluzie, g este produs de polinoame
minimale distincte mi.

52
Unul din cele mai importante exemple de coduri ciclice (foarte folosit în practic ă) este
următorul:
8 Definiție. Fie Fq \ {0} = {1, α, …, α q − 2} unde α este un element primitiv al lui Fq (deci
α este de ordin q − 1 în Fq*) și 1 ≤ k ≤ q − 1. Codul Reed-Solomon RS(k, q) este codul urm ător
de lungime n = q − 1:
RS (k, q) := {( f (1), …, f (α q − 2)) ∈ Fqq − 1 | f ∈ Fq[X], deg f ≤ k − 1}
Deoarece { f | f ∈ Fq[X], deg f ≤ k − 1} =: Lk − 1 este un subspa țiu liniar al lui Fq[X] de
dimensiune k, RS(k, q) poate fi v ăzut ca imaginea func ției de evaluare ev : Lk − 1 → Fqq − 1,
ev( f ) = ( f (1), …, f (α q − 2)). Deci RS(k, q) este subspa țiu liniar, c ăci ev este liniar ă.
Dimensiunea este k, deoarece ev este injectiv ă: orice f ∈ Lk − 1 cu ev( f ) = (0, …, 0) are
q − 1 > deg f rădăcini și trebuie s ă fie 0).
Dacă wt( f (1), …, f (α q − 2)) < n − k + 1, atunci num ărul de coordonate i cu f (α i) = 0 este
mai mare decît n − (n − k + 1) = k − 1. Deci f are mai multe r ădăcini decît gradul, i.e f = 0.
Astfel, ponderea minim ă a cuvintelor lui RS(k, q) este d = n − k + 1, adică este un cod MDS .
Orice cod Reed-Solomon este ciclic. Într-adev ăr, o bază a subspa țiului k-dimensional
RS(k, q) este { ev(X j) | 0 ≤ j ≤ k − 1}, unde ev(X j) = ((α j)0,…, ( α j)q − 2). Permutînd ciclic la
dreapta acest cuvînt cod ob ținem (( α j)q − 2, (α j)0,…, ( α j)q − 3) = α −jev(X j), care apar ține
RS(k, q) (vezi și exercițiul 1).
De fapt, codurile Reed-Solomon sînt o subclas ă a unei clase de coduri ciclice cunoscute
drept coduri BCH (descoperite de c ătre R.C. Bose și D.K. Ray-Chaudhuri în 1960 și
independent de A. Hocquenghem in 1959).
9 Definiție. Fie n ≥ 2 și t ∈ N*. Fie α o rădăcină primitivă de ordin n a unității într-o
extindere mqFa lui Fq și fie I mulțimea de defini ție a unui cod ciclic code C ⊆ Fqn. Codul C se
numește cod BCH de distan ță din design t dacă I conține t − 1 numere consecutive (modulo
n). Dacă {1, …, t − 1} ⊆ I, atunci C se numește cod BCH în sens restrîns . Dacă n = qm − 1,
atunci C este numit primitiv .
Echivalent spus, un cod BCH este un cod ciclic cu generator egal cu cel mai mic multiplu
comun al polinoamelor minimale ale α j, α j + 1, …, α j + t − 2 pentru un j ≥ 0.
Așadar, RS(k, q) este cod BCH primitiv în sens restrîns, de lungime q − 1 (deci m = 1 și
n = q − 1 în defini ția de mai sus). Generatorul s ău este g = (X − 1)…( X − α q − k − 2).
Denumirea de cod BCH de distan ță din design t este justificat ă:
10 Teorem ă (inegalitatea BCH , BCH bound ) Distanța minimă d a unui cod BCH cu
distanță din design t este cel pu țin t.

53
Demonstra ție. Fie j, j + 1, …, j + t − 2 în mul țimea de defini ție a lui C și fie
c = 1d is
i s scx=∑ un cuvînt cod nenul în C de pondere d (unde ijc≠ 0, ∀j). Presupunem prin
absurd că d < δ. Deoarece c(α i) = 0, ∀j ≤ i ≤ j + t − 2, avem Ac = 0, unde
12
12
12(1 ) (1 ) (1 )
(1 ) (1 ) (1 )d
d
dij ij i j
ij ij i j
ij d ij d i j dAαα α
αα α
αα α+ ++
+− +− +−⎡⎤
⎢⎥
⎢⎥=⎢⎥
⎢⎥
⎢⎥⎣⎦…
…
…… … …
…, c = 1
2
di
i
ic
c
c⎡⎤
⎢⎥
⎢⎥
⎢⎥
⎢⎥
⎢⎥⎣⎦#
Dar det A ≠ 0 (este un determinant Vandermonde), deci c = 0, contradic ție. †
Există multe coduri ciclice cu distan ța minimă mai mare decît cea garantat ă de inegalitatea
BCH. O cale de a îmbun ătăți estimarea distan ței pentru un cod ciclic este s ă observăm că
mulțimea de defini ție I a codului ciclic C depinde de alegerea r ădăcinii primitive de ordin n a
unității α din F. Orice alt ă rădăcină primitivă de ordin n a unității β este de forma β = α a, cu
(a, n) = 1. Fie b ∈ N astfel încît ab = 1 (mod n); atunci () 1babα β = = . Mulțimea de defini ție
a lui C relativă la β este J = {bi (mod n) | i ∈ I} := bI. Se poate întîmpla ca bI să aibă mai
multe elemente consecutive decît I. Deci, cînd estim ăm cu inegalitatea BCH distan ța minimă
a unui cod ciclic de mul țime de defini ție I, un multiplicator (un num ăr întreg b prim cu n)
poate fi aplicat lui I.
11 Exemplu. Construim un cod ciclic binar C de lungime 31 a c ărui mulțime de defini ție
conține 0 și 3. Deci q = 2 și n = 31. Cel mai mic m astfel încît 31| 2m − 1 este 5 și o rădăcină
primitivă de ordin 31 a unit ății, α, din F32, este de fapt un element primitiv al F32. Mulțimea
de defini ție a lui C trebuie s ă conțină 3, 3·2 = 6, 6·2 = 12, 12·2 = 24, 24·2 = 48 = 17,
17·2 = 34 = 3 (calcule mod 31). Deci mul țimea de defini ție este I = {0, 3, 6, 12, 24, 17}, care
furnizează d(C) ≥ 2. Cum apar multipli de 3 consecutivi, alegem multiplicatorul s ă fie
21 = 3−1 (mod 31); ob ținem 21 I = {0, 1, 2, 4, 8, 16 }, care d ă d(C) ≥ 4. Cît este dim C?
Exerciții
1. Fie C cod liniar și fie { u1, …, uk} o bază în C. Demonstra ți că C este ciclic dac ă și numai
dacă permutările ciclice la dreapta ale oric ărui ui sînt cuvinte cod în C.
2. Fie g ∈ F[X] polinomul generator al unui cod ciclic de lungime n astfel încît ( X − 1) ? g.
Demonstra ți că codul C' = {(c0, …, cn − 1) ∈ F n | (c0,…, cn − 1) ∈ C, c0 + … + cn − 1 = 0} este
ciclic și are polinom generator ( X − 1)g. Ce se întîmpl ă dacă (X − 1) | g?
3. Fie C cod binar ciclic și g polinomul generator. Demonstra ți că toate cuvintele lui C au
pondere par ă dacă și numai dac ă g este divizibil cu X − 1.

54
4. Fie g = 1 + X 2 + X 5 ∈ F2[X]. Demonstra ți că g generează un cod ciclic C de tip [31 , 26, 3].
Demonstra ți că mulțimea cuvintelor de pondere par ă ale lui C este codul din exemplul 11.
Scrieți polinomul generator.
5. Fie C cod liniar ciclic. Demonstra ți că C⊥ este ciclic.
6. Fie g = a0 + a1 X + … + amX m polinomul generato r al codului ciclic C, de lungime n.
Definim reciprocul lui g prin gR := am + am − 1 X + … + a0 X n. Fie h ∈ F[X] astfel încît
gh = X n − 1. Demonstra ți că hR genereaz ă codul dual C⊥. ( Ind. Scrieți
g = g0 + g1 X + … + gn − 1X
n − 1 și h = h0 + h1 X + … + hn − 1X
n − 1, cu gn − 1 și hn − 1 posibil 0.
Calculați gh mod ( X n − 1) și compara ți coeficien ții. Conchide ți că hR (ca vector în Fn) este
ortogonal pe ( g0, g1, …, gn − 1) și toate permut ările sale ciclice).

55
VII. Aplica ții: pachete de erori, Compact Disc, CRC

Ipoteza că erorile de comunicare apar la întîmplare (ca la canalul qSC) nu este îndeplinit ă
în toate aplica țiile practice: exist ă canale la care erorile tind s ă apară una lîngă alta ( pachete
de erori , burst errors ). Această situație este des întîlnit ă la stocarea pe band ă sau medii optice
(CD, DVD), comunica ții radio etc.
Ca întotdeauna, F este un corp finit fixat.
1 Definiție. Un pachet de erori de lungime b , pe scurt b-pachet de erori (burst of length b,
b-burst ) este un vector u în F n
ale cărui coordonate nenule se g ăsesc pe b poziții consecutive,
din care prima și ultima sînt nenule. Codul C ⊆ F n se numește corector de b-pachete de erori
dacă nu există cuvinte cod distincte c1, c2 ∈ C și pachete de erori u1, u2 de lungimi cel mult b
astfel încît c1 + u1 = c2 + u2. Pentru un cod liniar C, aceasta e echivalent cu:
Pentru orice pachet de erori u de lungime ≤ b, cosetul u + C nu conține alt pachet de erori
de lungime ≤ b.
Avertizare: pot ap ărea confuzii între lungimea unui pachet de erori u definită ca mai sus
(care este b) și lungimea lui u văzut ca vector în F n (care e, desigur, n).
2 Teoremă. Fie C un cod liniar corector de b-pachete de erori tip [n, k, d ]. Atunci:
a) C nu conține pachete de erori de lungime ≤ 2b.
b) (Inegalitatea Reiger, Reiger Bound) n − k ≥ 2b.
Demonstra ție. a) Presupunem c ă c ∈ C este un pachet de erori de lungime ≤ 2b ale cărui
componente nenule sînt în pozi țiile de la i pînă la i + t (cu t ≤ 2b − 1): c = 0…0 ci…ci + t 0…0,
unde cj ∈ F, c i ≠ 0, ci + t ≠ 0. Fie u = 0…ci…ci + b − 10…0, v = 0…0 ci + b…ci + t0…0; deci
c = u + v. Atunci 0 + v = c + (− u), cu 0, c ∈ C și −u, v pachete de erori de lungime ≤ b,
contradicție.
b) Afirmăm că C conține pachete de erori de lungime ≤ n − k + 1. (Din prima parte, aceasta
va implica n − k + 1 > 2b ⇔ n − k ≥ 2b.) Să demonstr ăm afirmația. Fie H o matrice de paritate
a lui C și fie h1, …, hn coloanele sale. Avem hi ∈ Fn − k, deci h1, …, hn − k + 1 sînt linear
dependente: exist ă c1, …, cn − k + 1 ∈ F, nu toți zero, astfel încît c1h1 + … + cn − k + 1hn − k + 1 = 0.
Atunci c1…cn − k + 10…0 ∈ C, care este pachet de erori de lungime ≤ n − k + 1. †

56
Tehnicile de concatenare și întrețesere sînt folosite la proiectarea de coduri cu capacit ăți
bune de corectare de pachete de erori.
Dacă informația vine în cuvinte de m simboluri binare, acestea pot fi v ăzute ca elemente
ale corpului cu 2m elemente. Folosind un cod Reed-Solomon cu q = 2m, un pachet de b erori în
simbolurile binare de vine un pachet de b/m erori în cuvintele cod, care poate fi corectat dac ă
b/m < e (capacitatea de corectare a codul ui). Aceasta este un exemplu de concatenare .
3 Definiție (Concatenarea a dou ă coduri, Concatenation of two codes ). Fie A un cod
liniar [ n, k, d ] peste Fq. Atunci A este Fq-spațiu liniar de dimensiune k; deoarece corpul cu
Q := qk elemente este tot Fq-spațiu liniar de dimensiune k, există un Fq-izomorfism
ϕ : FQ → A. Fie B un cod liniar [ N, K, D ] peste FQ. Un cuvînt oarecare al lui B este de forma
b = (b1, …, bN), bi ∈ FQ. Dacă înlocuim fiecare bi cu imaginile lor în A prin ϕ (care sînt
cuvinte de lungime n peste Fq), obținem un cuvînt de lungime Nn peste Fq. Toate cuvintele
obținute astfel formeaz ă un nou cod C. Formal:
C = {(ϕ(b1), …, ϕ(bN)) ∈ Nn
qF | (b1, …, bN) ∈ B}
Codul C se nume ște cod concatenat , cu A codul interior (the inner code ) și B codul
exterior (the outer code ). A se observa c ă C depinde și de alegerea Fq-izomorfismului
ϕ : FQ → A.
4 Teorem ă. a) C este cod liniar peste Fq, de lungime Nn, dimensiune Kk și distanță
minimă cel puțin Dd.
b) Păstrăm notațiile din defini ția de mai sus și punem A = Fqn (cod tip [n, n, 1] peste Fq).
Atunci codul concatenat C cu cod interior A și cod exterior B poate corecta pachete de erori
de lungime ≤ (e − 1)n + 1, unde e = b(D − 1)/2c, capacitatea de corectare a lui B .
Demonstra ție. a) Lema urm ătoare spune c ă B este un Fq-spațiu liniar de dimensiune Kk.
Definim aplica ția Fq-linară Φ : N
QF→ Nn
qF, Φ(b1, …, bN) = (ϕ(b1), …, ϕ(bN)), pentru orice
(b1, …, bN) ∈ N
QF. Acesta este un Fq-izomorfism. Deoarece C este imaginea lui B prin
izomorfismul Φ, dim C = dim B = Kk (ca Fq-spații liniare).
Orice cuvînt nenul din C este de forma ( ϕ(b1), …, ϕ(bN)), unde ( b1, …, bN) este un cuvînt
nenul din B; deci are cel pu țin D componente nenule . Deoarece orice ϕ(bi) care e nenul are
pondere cel pu țin d, wt(ϕ(b1), …, ϕ(bN)) = wt(ϕ(b1)) + … + wt(ϕ(bN)) ≥ Dd.
b) Fie u ∈Nn
qF un pachet de erori de lungime ≤ an + 1. Atunci u coresponde prin Φ−1 unui
vector v ∈ N
QF. O examinare rapid ă arată că v este pachet de erori de lungime ≤ a + 1. Deci,
dacă punem a = e − 1, atunci v este pachet de erori de lungime ≤ e și poate fi corectat de B. †
5 Lemă. Fie F ⊆ E o extindere de corpuri, dim FE = k. Dacă V este un E-spa țiu vectorial
de dimensiune N, atunci E este un F-spa țiu vectorial de dimensiune kN.

57
Demonstra ție. Fie v1, …, vN o E-bază a lui V și fie e1, …, ek o F-bază a lui E. Atunci
{eivj | 1 ≤ i ≤ k, 1 ≤ j ≤ N} este o F-bază a lui V. †
6 Definiție (Întrețesere, Interleaving ). Fie C un cod liniar [ n, k, d ] peste F care poate
corecta pachete de erori de lungime ≤ b. Definim codul tip [ nt, kt ] I(C, t) (numit C între țesut
la adînimea t, C interleaved to depth t) astfel: pentru orice cij ∈ F, (1 ≤ i ≤ t, 1 ≤ j ≤ n):
c11c21…ct1c12c22…ct2……c 1nc2n…ctn ∈ I(C, t) ⇔ c11c12…c1n ∈ C, c21c22…c2n ∈ C, …,
ct1ct2…ctn ∈ C.
Așadar, pentru a ob ține un cuvînt cod de lungime nt în I(C, t), se aleg t cuvinte cod c1, c2,
…, ct ∈ C, ci = ci1ci2…cin și se formeaz ă matricea ale c ărei linii sînt cele t cuvinte:
11 12 1
21 22 2
12n
n
tt t ncc c
cc c
cc c⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦…
…
#
…
Dacă scriem simbolurile din ma trice citind pe coloane ob ținem un cuvînt cod din I(C, t).
Întrețeserea la adîncime t multiplic ă de t ori capacitatea de corec ție de pachete de erori:
7 Teorem ă. Dacă C este un cod liniar [n, k, d ], corector de b-pache te de erori, atunci
I(C, t) este cod tip [nt, kt, d ], corector de bt-pachete de erori.
Demonstra ție. Un pachet de erori de lungime bt sau mai mic ă
c11c21…ct1c12c22…ct2……c 1nc2n…ctn este distribuit în pachete de erori de lungime cel mult b în
cele t linii ale matricei de mai sus. †

Codarea pentru compact disc
Schema de codare petru Compact Disc audio folose ște două coduri Reed-Sol omon scurtate
și două forme de între țesere. Din Prop. V.14 , știm că scurtarea unui cod tip [ n, k, n − k + 1]
(cod MDS) pe r coordonate produce un cod MDS tip [n − r, k − r, n − k + 1].
Exercițiu. Construi ți un cod Reed–Solomon de lungime 255 și distanță minimă 5 peste
corpul cu 256 elemente. Explica ți cum se ob țin două coduri Reed–Solomon scurtate: C2 de tip
[32, 28, 5] și C1 de tip [28, 24, 5].
Descriem acum (urmînd în linii mari [7]) schema de codare și decodare folosit ă pentru
compact disc audio (CD audio), pentru a da o idee asupra dificult ăților ce apar în
implement ările concrete ale codurilor corectoare de erori.
Descriere general ă. Un CD este un disc gros de 1,2 mm, din policarbonat, cu diametrul de
120 mm. Un strat sub țire de aluminiu (sau, mai rar, aur) este aplicat pe suprafa ță, ceea ce o
face reflectorizant ă. Metalul este protejat de un film de lac. Discul con ține o pista spiral ă de
aproximativ 5 km (care începe dinspre centru), care e scanat ă optic de un laser cu AlGaAs de
lungime de und ă 780 nm (infraro șu apropiat), la o vitez ă liniară constantă de aprox. 1,2 m/s.

58
Pe pistă sînt indent ări (numite pit-uri ) și zone plate intre pit-uri, numite lands . Lățimea unui
pit este de aprox. 500 nm, adîncimea de 100 nm; lungimea variaz ă între 850 nm și 3500 nm.
Pasul spiralei este 1,6 µm. Laserul este reflectat cu intensit ăți diferite de pit-uri și land-uri din
cauza interferen ței. Prin m ăsurarea schimb ărilor de intensitate cu o fotodiod ă, datele pot fi
citite de pe disc. Pit-urile sît mai apropiate de fa ța etichetat ă a discului, ceea ce face ca
defectele și impuritățile de pe fa ța care este scanat ă optic să fie neclare (nefocusate) în timpul
citirii. Deci este mai probabil ă deteriorarea CD-urilor prin partea etichetat ă a discului.
Informația conținută de pit-uri și land-uri este afectat ă de erori provenind de la particule de
praf pe disc, bule de aer în înveli șul de plastic, amprente, zgîrietu ri etc. Aceste erori sînt cel
mai adesea pachete de erori și sînt corectate cu un sistem de codare și decodare foarte eficient.
Codarea. Semnalul audio este e șantionat prin m ăsurare de 44,100 ori pe secund ă. Fiecare
eșantion este tradus într-un num ăr pe 16 bi ți (deci amplitudinea semnalului va fi aproximat ă
cu unul din cele 216 = 65536 nivele posibile); deoarece sunetul este stereo, sînt dou ă
eșantioane simultane (unul pentru fiecare canal). Astfel, o e șantionare produce 4 octe ți (bytes)
(un octet /byte este un cuvînt de 8 bi ți, adică un element al 8
2F). Pentru fiecare secund ă de
sunet se genereaz ă așadar 44 100 · 4 = 176 400 octe ți.
Pentru a coda octe ții se folosesc dou ă coduri Reed–Solomon scurtate, C1 și C2, și două
forme de între țesere. Aceast ă schemă se nume ște CIRC (cross-interleaved Reed–Solomon
code, cod Reed-Solomon între țesut-încruci șat). Scopul între țeserii încruci șate, care este o
variantă de întrețesere, este s ă "spargă" pachetele lungi de erori.
Șase eșantioane de 4 octe ți fiecare sînt grupate pentru a forma un cadru (frame) . Un cadru
are deci 24 octe ți:
L1R1L2R2… L 6R6 ,
unde L i semnifică cei doi octeți corespunz ători canalului stîng din e șantionul i al cadrului, iar
Ri sînt cei doi octe ți correspunz ători de la canalul drept.
Octeții sînt rearanja ți astfel: e șantioanele impare (L 1R1, L 3R3, L 5R5) se grupeaz ă cu
eșantioanele pare L" 2R"2 L" 4R"4 L" 6R"6 luate cu dou ă cadre mai tîrziu , în ordinea urm ătoare:
L1L3L5R1R3R5L"2L"4L"6 R" 2R"4R"6
Se obține un cuvînt mesaj de 24 octe ți. Eșantioanele care erau ini țial consecutive în timp
sînt acum la dou ă cadre distan ță. Aceasta va u șura „disimularea erorilor” (vezi partea de
decodare).
Identificăm octeții cu elemente ale corpului F256 cu 28 = 256 elemente . Un codor sistematic
pentru codul Reed Solomon scurtat tip [28, 24, 5] 256 C1 (vezi Exercițiu mai sus) codeaz ă
mesajul de 24 octe ți într-un cuvînt de 28 octe ți, care e format din mesajul original la care se
adaugă 4 octeți "de paritate" nota ți P1 și P2 (P 1 și P2 au cîte doi octeți, ca și L i). Formăm
cuvîntul cod de 28 octe ți prin plasarea P 1 și P2 la mijloc:
L1L3L5R1R3R5P1P2L"2L"4L"6 R" 2R"4R"6

59
Cuvintele cod de 28 octe ți din C1 sînt între țesute la o adîncime de 28 folosind o "întîrziere"
de 4 cadre ( 4-frame delay interleaving ). Mai precis, fie c1, …, cn, … cuvintele cod din C1 în
ordinea în care au fost generate, și fie ci = ci1…ci28 ∈ 28
256F. Formăm următoarea matrice M cu
28 linii și un număr suficient de coloane ca s ă conțină toate cadrele:

1 c1,1 c2,1 c3,1 c4,1 c5,1 c6,1 c7,1 c8,1 c9,1 c10,1 c11,1 c12,1 c13,1 … c109,1 …
2 0 0 0 0 c1,2 c2,2 c3,2 c4,2 c5,2 c6,2 c7,2 c8,2 c9,2 … c105,2 …
3 0 0 0 0 0 0 0 0 c1,3 c2,3 c3,3 c4,3 c5,3 … c101,3 …
4 0 0 0 0 0 0 0 0 0 0 0 0 c1,4 … c97,4 …
… …
28 0 0 0 0 0 0 0 0 0 0 0 0 0 … c1,28 …
Matricea M obținută prin între țesere cu întîrziere de 4 cadre ( 4-frame delay interleaving )
Linia i (foarte lung ă) se obține prin plasarea octe ților i ai cuvintelor cod c1, …, cn, …, în
această ordine; apoi se translateaz ă la dreapta linia 2 cu 4 pozi ții, linia 3 cu 8 pozi ții, …, linia
28 cu 27·4 = 108 pozi ții; se completeaz ă cu zerouri unde e necesar. Cuvîntul cod ci poate fi
citit din aceast ă matrice prin parcurgerea în diagonal ă cu panta -1 /4 începînd din pozi ția i a
liniei 1.
Am obținut pînă acum o matrice M ale cărei coloane sînt elemente din 28
256F. Folosim acum
codul Reed–Solomon scurtat C2, tip [32, 28, 5] 256, pentru a coda ace ști vectori de lungime 28
în cuvinte cod de lungime 32. Aceste cuvinte cod sînt iar ăși întrețesute: simbolurile de pe
poziții impare de la un cuvînt sînt gr upate cu simbolurile de pe pozi ții pare ale cuvîntului
următor; se ob ține un șir de segmente de 32 octe ți. Aceast ă întrețesere mai împr ăștie
eventualele pachetele de erori care mai exist ă. La sfîrșitul fiecărui astfel de segment este
adăugat un al 33lea octet (de control și display). Astfel, fiecare cadru de 6 e șantioane a produs
în final 33 octe ți. O schem ă detaliată a codării folosind C1 și C2 poate fi g ăsită în [17].
Fiecare octet ob ținut trebuie acum impr imat pe disc. O tranzi ție land-pit sau pit-land
semnifică un 1, în timp ce un pit sau land semnific ă un șir de 0. Lungimea pit-ului (land-ului)
determină numărul de 0-uri, dup ă regula că fiecare bit corespunde la 300 nm. De exemplu, un
pit de lungime 1500 nm urmat de un land de lungime 900 nm corespunde șirului 10000100:
pit-ul de 1500 nm semnific ă 1500/300 = 5 biți, din care primul e 1, adic ă 10000; landul de
900 nm semnific ă 100.
Din motive tehnice, fiecare land sau pit trebuie s ă fie între 900 și 3300 nm, adic ă fiecare
pereche de 1 trebuie s ă fie separat ă de cel pu țin două 0-uri și cel mult zece 0-uri. Cel mai scurt
pt (land) reprezint ă 3 biți (100), și cel mai lung 11 bi ți (10000000000). Deci, cei 256 octe ți
posibili trebuie converti ți în șiruri de bi ți care satisfac aceast ă condiție. Se poate ar ăta că cea
mai mică lungime l, astfel încît exist ă cel puțin 256 cuvinte bi nare de lungime l cu
proprietatea c ă fiecare 1 este separat de cel pu țin două 0-uri și cel mult zece 0-uri, este 14. De
fapt, sînt 267 cuvinte de lungime 14 cu aceast ă proprietate; 11 din acestea nu sînt folosite.

60
Această conversie de la octe ți la cuvinte de lungime 14 se nume ște EFM ( eight-to-fourteen
modulation, modula ție opt la paisprezece ), și se realizeaz ă folosind un tabel de conversie. Mai
este o problem ă: două cuvinte succesive de 14 bi ți pot să nu satisfac ă condiția de separare de
mai sus. Din acest motiv, trei bi ți suplimentari ( merge bits , biți de fuzionare ) sînt adăugați la
sfîrșitul fiecărui cuvînt de 14-bi ți pentru a ob ține șiruri care satisfac condi ția. De exemplu,
șirurile 10010000000100 și 00000000010001, scrise succesiv, ar produce un șir de 11 zerouri;
dacă adăugăm 001 dup ă primul șir, obținem 1001000000010000100000000010001, care
satisface condi ția.
Astfel, cadrul ini țial de 6 eșantioane corespunde la 33 octe ți; fiecare octet e convertit în 17
biți. La fiecare ace ști 33·17 bi ți, se adaug ă 24 biți plus trei bi ți de fuzionare; astfel, fiecare
cadru de 6 e șantioane produce 588 bi ți.
Decodarea și corectarea de erori. Mai întîi se elimin ă biții de sincronizare, control și
display și de fuzionare. Se realizeaz ă apoi conversia din formatul EFM în octe ți folosind o
tabelă; acum informa ția este un șir de octe ți. Apoi se rearanjeaz ă octeții în ordinea normal ă.
Șirul e împ ărțit în segmente de 32 octe ți. Fiecare din aceste segmente de 32 octe ți conține
octeții de pe pozi ții impare dintr-un cuvînt cod (cu posibile erori) și octeții de pe pozi țiile pare
ale următorului cuvînt cod. Octe ții sînt regrupa ți în pozi țiile inițiale și sînt furniza ți
decodorului pentru C2. Dacă un pachet scurt de erori a ap ărut pe disc, pachetul poate fi divizat
în pachete mai mici prin aceast ă regrupare.
Decodarea cu C 2. Deoarece C2 este cod tip [32, 28, 5] peste F256, poate corecta dou ă erori
la nivel de octe ți. Totuși, este folosit doar pentru a corecta o eroare și pentru a detecta
prezența de erori multiple . Dacă s-a produs o singur ă eroare, C2 poate corecta eroarea prin
căutarea unui cuvînt c od în sfera de raz ă 1 centrată în cuvîntul recep ționat. Dac ă găsește unul,
eroarea este corectat ă; dacă nu, înseamn ă că două sau trei erori au avut loc și C2 a detectat
aceste erori (dar nu va fi folosit pentru corectarea lor).
E important s ă estimăm probabilitatea ca C2 să nu detecteze 4 sau ma i multe erori cînd e
folosit să corecteze 1 eroare. O astfel de situa ție apare dac ă erorile se produc la un cuvînt cod
încît vectorul ce rezult ă se află într-o sfer ă de rază 1 centrată în alt cuvînt cod. Presupunînd c ă
toți vectorii sînt la fel de probabili, probabilitatea ca aceast ă situație să apară este aproximativ
egală cu raportul dintre num ărul de vectori din sferele de raz ă 1 centrate în cuvinte cod și
numărul total de vectori din 32
256F:
[ ]28
6
32 4256 1 32(256 1) 81611.9 10256 256− ⋅+ −=≈ ⋅
Pe de alt ă parte, dac ă am utiliza C2 la capacitatea maxim ă de corectare de erori (toate
erorile duble), probabilitatea de e șec în detectarea a trei sau mai multe erori este raportul
dintre num ărul de vectori din sferele de raz ă 2 centrate în cuvinte cod și numărul total de
vectori din 32
256F:

61
28 2
32 432256 1 32(256 1) (256 1)2 322605610.0756256 256⎡⎤ ⎛⎞⋅+ −+ −⎢⎥ ⎜⎟⎝⎠ ⎣⎦=≈

Această probabilitate de e șec (cam de 4000 ori mai mare d ecît precedenta) este motivul
pentru care C2 nu este folosit la capacitatea maxim ă de corectare.
Decodare cu C 1. Dacă decodorul pentru C2 găsește cel mult o eroare într-un șir de 32
octeți, eroarea eventual ă este corectat ă și mesajul de 28 octe ți este extras și trimis mai departe.
Dacă C2 detecteaz ă cel puțin două erori, trimite un cuvînt de 28 octe ți cu toate componentele
marcate ca " ștersături". Aceste blocuri de 28 octe ți corespund coloanelor matricei M, cu
posibile ștersături. Diagonalele de pant ă −1/4 sînt transmise ca vectori de 28 octe ți
decoderului pentru C1. Se observ ă că blocurile de 28 octe ți cu ștersături sînt împr ăștiate prin
acest proces la blocuri diferite ale codului exterior C2.
O schemă de decodare folose ște C1 doar la corectarea ștersăturilor. Din teorema I. 11 , C1
poate corecta pîn ă la patru ștersături. Datorit ă întrețeserii, un bloc de 28 octe ți marcat ca
ștersătură (de codul interior) co respunde la 28 blocuri (c u cîte un singur octet ștersătură) din
codul exterior. Între țeserea cu întîrziere de 4 cadre, combinat ă cu capacitatea de corectare a 4
ștersături a lui C1, permit corectarea unui pachet de erori care afecteaz ă 16 șiruri consecutive
de 588 bi ți fiecare. Un astfel de pachet de erori ocup ă aproximativ 2.8 mm în lungul pistei
discului.
O altă schemă de decodare folose ște C1 la corectarea unei erori (care a sc ăpat eventual
detectării lui C2) și a două ștersături. (cf. Teorema I. 11 )
Interpolare și disimularea erorilor. Eșantioanele care nu pot fi corectate de schema de mai
sus și sînt detectate ca erori sînt marcate ca ștersături. Deoarece e șantioanele consecutive sînt
separate de dou ă cadre înainte de coda re, la finalul decod ării, cînd aceste e șantioane sînt
readuse în ordinea ini țială, este probabil ca e șantioanele vecine s ă fie corecte sau s ă fi fost
corectate. În acest caz, e șantionul marcat " șters" este aproximat prin interpolare liniar ă
folosind e șantioanele vecine. Testele au ar ătat că acest proces este practic indedectabil la
audiție. Dacă eșantioanele vecine nu sînt corecte, se folose ște “muting”. Cu 32 e șantioane
înaintea pachetului de erori, e șantioanele corecte sînt treptat mic șorate pîna la apari ția
pachetului de erori, care e înlocuit de e șantioane de valoare zero, iar urm ătoarele 32
eșantioane corecte sînt treptat readuse la valoarea real ă.

Detecție de erori cu CRC (Cyclic Redundancy Check)
Matricea generatoare a unui cod ciclic code dat ă la VI.5 nu este în form ă standard, deci
codarea corespunz ătoare nu e sistematic ă. Descriem acum o codare sistematic ă pentru coduri
ciclice, carea are importante aplica ții. Codurile binare ciclice sînt potri vite pentru detec ția de

62
erori, iar implementarea circuitelor de codare și de detec ție de erori este eficient ă (folosind
linear feedback shift registers ).
Fie C un cod ciclic tip [ n, k, d ] peste corpul F cu q elemente, g polinomul s ău generator,
deg g = n − k. Deoarece dim C = k, polinomul mesaj este de grad cel mult k − 1. Folosind
teorema împ ărțirii cu rest, putem scrie
X n − km = gq + r, cu q, r ∈ F[X], deg r < n − k or r = 0.
Astfel, X n − km − r = gq ∈ C. Dacă codăm m ca c = X n − km − r, aceasta este o codare
sistematic ă, deoarece coeficien ții lui m apar drept coeficien ții lui X n − k, X n − k + 1, …, X n − 1 în
c. Practic, la cuvîntul mesaj (coeficien ții lui m) se adaug ă la sfîrșit simbolurile de control
(coeficien ții lui − r).
În aplicații, mesajul m este binar și nu are lungimea fixat ă k; biții de control sînt ad ăugați
la mesaje de lungime ≤ k. Acești biți de sînt cunoscu ți sub numele de CRC ( Cyclic
Redundancy Check , Verificare Redundant ă Ciclică) și se folosesc pentru detectarea erorilor .
Verificarea de eroa re se realizeaz ă prin testarea dac ă cuvîntul recep ționat (văzut ca polinom)
este divizibil cu g. O eroare poate trece nedetectat ă dacă și numai dac ă un vector eroare e (un
polinom de grad mai mic ca n) este adunat cuvîntului cod c de mai sus și c + e este divizibil
cu g. Deoarece g | c, aceasta are loc dac ă și numai dac ă g|e.
8 Propozi ție. Un cod ciclic C tip [n, k, d ] de generator g poate detecta toate pachetele de
erori de lungime ≤ n − k.
Demonstra ție. Fie r un pachet de erori de lungime ≤ n − k și să presupunem prin reducere
la absurd c ă r nu este detectat de C, adică g|r. Fie j cel mai mare num ăr natural astfel încît
X j | r. Cum r este pachet de erori de lungime ≤ n − k, aceasta înseamn ă că r = X js, cu
deg s < n − k. Dar g divide Xn − 1, deci g nu este divizibil prin X, adică (X j, g) = 1. Cum
g | X js, rezultă că g | s, is imposibil c ăci deg g > deg s. †
Rezultatul urm ător estimeaz ă proporția de pachet de erori (mai lungi decit n − k) care nu
sînt detectate de C:
9 Teorem ă. Din totalul de pachete de erori de lungime b > n − k, propor ția celor care nu
sînt detectate de un cod ciclic C tip [n, k, d ] de generator g este: q −(n − k − 1)/(q − 1) (dacă
b = n − k + 1) , respectiv q −(n − k ) (dacă b > n − k + 1).
Demonstra ție. Fie r un pachet de erori de lungime b care începe în simbolul i: r = X is,
unde deg s = b − 1. Numărăm cîte asemenea polinoame s există: sînt q − 1 posibilit ăți pentru
primul coeficient (orice element nenul al lui F), q − 1 pentru ultimul, și q posibilități pentru
coeficienții dintre ace știa, deci avem ( q − 1)2qb − 2 polinoame s.
Eroarea r nu este detectat ă dacă și numai dac ă g|s, adică s = gh, pentru un h ∈ K[X].
Deoarece deg g = n − k, avem deg h = b − 1 − (n − k). Dacă b − 1 = n − k, atunci h e o
constantă nenulă (q − 1 posibilit ăți). Astfel, raportul dintre num ărul de pachete nedetectate și
numărul total de pachete este ( q − 1)/((q − 1)2qb − 2) = q −(n − k − 1)/(q − 1).

63
Dacă b − 1 > n − k, sînt q − 1 alegeri posibile pentru primul coeficient al lui h, q − 1 alegeri
pentru ultimul coeficient și cîte q alegeri pentru fiecare ceficient intermediar. În total rezult ă
to (q − 1)2qb − 1 − (n − k) − 1 polinoame h. Raportul în acest caz este deci q −(n − k ). †
Această teoremă afirmă că probabilitatea de e șec în detectarea de erori este propor țională
cu q −(n − k ) (independent ă de lungimea codului sau de cît de zgomotos e canalul). Deci,
probabilitatea de apari ție de eroari nedete ctate e determinat ă de n − k, numărul de simboluri
de control.
10 Exerci țiu. Fie g ∈ Fq[X] un polinom ireductibil de grad m. Atunci:
a) g| X n − 1, unde n = qm − 1 (Ind: g are toate r ădăcinile în corpul cu q m elemente).
b) Dacă g este polinomul minimal peste Fq al unui element primitiv al corpului cu q m
elemente (un astfel de g se nume ște polinom primitiv ), atunci g este de grad m și numărul
natural min { n ∈ N | g divide X n − 1} (numit ordinul lui g) este qm − 1.
c) Dacă α este o rădăcină a lui g într-o extindere E a lui Fq, atunci ordinul lui g este ordinul
lui α (în sens de ordin al lui α în grupul multiplicativ E*). Dacă g are ordin qm − 1, atunci g
este primitiv.
d) Pentru orice polinom h ∈ Fq[X] astfel încît ( X, h) = 1, există n astfel încît g divide X n − 1
(cel mai mic num ăr natural n cu aceast ă proprietate se nume ște iarăși ordinul lui h).
Presupunem de acum înainte c ă F este corpul cu 2 elemente F2 (cazul binar ). Din Prop. 8
deducem că orice cod C ciclic tip [ n, k, d ] cu k < n detectează o eroare . Consider ăm o eroare
dublă, în pozi țiile i > j, deci polinomul eroare este e = X i + X j = X j(X i − j + 1). Cum
(X j, g) = 1, e nu este detectat ⇔ g|e ⇔ X i − j + 1 e divizibil cu g. Dacă lungimea mesajului e
mai mică decît ordinul lui g (care este 2m − 1 dacă g este primitiv), atunci X i − j + 1 nu poate fi
divizibilă cu g, deci orice eroare dubl ă este detectat ă.
Polinoamele generatoare g folosite de obicei în practic ă pentru CRC sînt de forma ( X + 1) h
unde h este un polinom primitiv binar de grad m − 1. Aceast ă alegere are la baz ă faptul că un
cod binar ciclic cu polinomul generator g divizibil cu X − 1 are toate cuvintele cod de pondere
pară (demonstra ți!). Aceasta asigur ă detectarea tuturor vector ilor eroare care au pondere
impară (și că distanța minimă a codului este cel pu țin 4). Deci orice cod de acest tip are
distanța minimă cel puțin 4, detecteaz ă orice pachete de erori de lungime ≤ m, iar
probabilitatea de e șec in detectarea de erori în mesaje complet aleatoare este 2 − m.
Polinomul "CRC-5-USB" este X 5 + X 2 + 1. Acest polinom e folosit în standardul USB
pentru a proteja "pachete token" de 11 bi ți.
Polinoame CRC standard pentru m = 16:
CRC-16 : g = X16 + X15 + X2 + 1
CRC-CCITT : g = X16 + X12 + X5 + 1,
Pentru m = 32, polinomul CRC sta ndard IEEE 802.3 este
g = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5 + X 4 + X 2 + X + 1

64
Aceste polinoame ( și altele folosite în variate sta ndarde) adesea nu sînt cea mai bun ă
alegere. Mai mul ți autori au contribuit la efectuarea unei c ăutări exhaustive în spa țiul
polinoamelor binare de grad pîn ă la 32, găsind exemple de polinoame care se comport ă mai
bine (au distan ță minimă mai mare pentru o lungime de mesaj dat ă) decît polinoamele în uz în
anumite protocoale. Vezi [4], [8].

Exerciții
1. Construi ți un polinom generator și o matrice de paritate pe ntru un cod binar BCH care
corecteaz ă două erori, de lungime 15.
2. Arătați că distanța minimă a unui cod binar BCH în sens restrîns este impar ă.
3. Găsiți o matrice generatoare a unui cod RS tip [10, 6] peste Z11 și calculați distanța sa
minimă.
4. a) Folosind polinomul CRC-5-USB g ăsiți CRC pentru 10110011101.
b) Presupunem c ă 1011 0011 101 00001 este un cuvînt de lungime 11 concatenat cu CRC-
ul său în raport cu polinomul CRC-5 USB. Verifica ți dacă sînt erori.

65

Index

A
alfabet, 6
alfabet q-ar, 6
algebric (element), 29 algoritm de maxim ă verosimilitate, 9
algoritmul de distan ță minimă, 10
așteptarea de eroare, 11
B
bază a unui spa țiu liniar, 16
baza canonic ă a lui Fn, 16
binar, 6 bit, 6 bit de paritate., 18 byte, 58
C
canal de transmisie, 7
canal fără memorie, 7
canal q-ar simetric de probabilitate p, 7
canal qSC(p), 7
canal simetric, 7 capacitatea de corectare a unui cod, 9 capacitatea de detec ție a unui cod, 10
capacitatea unui canal, 12 caracteristica unui inel, 31 cîmp, 26 CIRC, 58 clase de resturi modulo n., 27
cod, 8
Hamming, 20
cod [ n, k, d], 10
cod BCH, 52 cod bloc corector de erori, 6 cod ciclic, 49 cod liniar, 16 cod liniar de tip [ n, k, d]
q, 17
cod MDS, 23 cod perfect, 22 cod q-ar, 8
cod Reed-Solomon, 52 cod sistematic, 8 cod tip [n, k], 7
codare, 7 codul de paritate, 18 codul exterior, 56 codul extins, 45 codul interior, 56 coduri diagonal echivalente, 20 coduri echivalente pîn ă la o permutare, 20
codurile Reed-Muller binare de ordin r, 47
Codurile Reed-Muller bina re de ordinul 1, 47
coeficienții unei combina ții liniare, 15
combinație liniară, 15
Compact Disc, 57 concatenarea a dou ă coduri, 56
congruență modulo n, 27

66
construcția (u, u + v), 46
corector de b-pachete de erori, 55
corp, 26
comutativ, 26
coset, 40 CRC, 62 cuvînt, 6 cuvînt cod, 8 Cyclic Redundancy Check, 62
D
decodare, 8
derivată formală, 32
dimensiunea unui cod liniar, 16 dimensiunea unui spa țiu liniar, 16
distanța Hamming, 8
distanța minimă a unui cod, 9
dualul unui cod, 19
E
echivalen ță monomial ă, 21
element primitiv, 34 endomorfismul lui Frobenius, 32 exponentul unui grup, 36 extindere de corpuri, 29
F
F-liniară (funcție), 16
F-morfism de spa ții liniare, 16
formă biliniară simetrică, 18
formă eșalon pe linii, 39
forma eșalon redus ă pe linii, 39
formă standard a matricei generatoare, 37
funcția de entropie, 11
G
găurire, 44
grad al unui element, 31 gradul unei extinderi, 30
I
ideal, 28
inegalitatea BCH, 52 inegalitatea Gilbert, 23 inegalitatea Reiger, 55 inegalitatea Singleton, 23 inegalitatea Varshamov, 24 inel, 26
comutativ, 26 unitar, 26
inel factor, 28 întrețesere, 57
Irr(x, K), 30
izomorfism, 16
L
lider al unui coset, 41
lungime a unui cuvînt, 6 lungimea
unei combina ții liniare, 15
lungimea unui cod, 8 lungire, 44
M
matrice de control, 18
matrice de paritate, 18 matrice generatoare, 17 mesaj, 6 morfism de inele, 27 mulțime de informa ție, 37
mulțime liniar independent ă, 16
mulțimea de defini ție, 51
O
octet, 58
ortogonalul, 18

67
P
pachet de erori de lungime b, 55
parametrii (unui cod), 17 permutarea ciclic ă la dreapta, 49
pivot, 39 polinomul generator al unui cod ciclic, 50
polinomul minimal, 30 pondere a unui cuvînt, 17 produs scalar, 18
R
rădăcină primitivă de ordinul n a unității, 51
rata unui cod, 8 rata unui cod liniar, 17 REF, 39 Reiger Bound, 55 RREF, 39
S
scurtare, 45
sfera de raz ă r, 9 simbol, 6
simboluri de paritate, 8 sindrom, 41 sistem de generatori, 16 spații izomorfe, 16
spațiu liniar, 14
spațiu liniar factor, 40
spațiu vectorial, 14
ștersătură, 11
subcorp, 27 subspațiu generat, 16
subspațiu liniar, 15
subspațiul ortogonal, 18
suma direct ă, 46
T
tablou Slepian, 41
tablou standard, 41 teorema fundamental ă de izomorfism pentru inele, 28
Teorema lui Shannon, 12 transform ări elementare, 39

68
Bibliografie

1. Bertsekas, D.P, Gallager, R.G, Data networks , Prentice Hall, 1987.
2. Castagnoli, G., Braeuer, S. & Herrman, M., Optimization of Cyclic Redundancy-Check
Codes with 24 and 32 Parity Bits , IEEE Trans. on Communications, Vol. 41, No. 6, June
1993.
3. CD-Recordable FAQ , http://www.cdrfaq.org/
4. Fujiwara, T., Kasami, T., Kitai, A. & Lin, S., "On the undetected error probability for
shortened Hamming codes", IEEE Trans. on Communications, vol. 33, no. 6, 1985, pp.570-
573.
5. Gherghe, C., Popescu, D., Criptografie. Coduri. Algoritmi, Editura Universit ății din
București, 2005
6. Hall, J.I, Notes on Coding Theory ,
http://www.mth.msu.edu/~jhall/classes/codenotes/coding-notes.html
7. Huffman, W., Pless, V., Fundamentals of Error-Correcting Codes , Cambridge University
Press 2003.
8. Koopman, Philip, 32-Bit Cyclic Redu ndancy Codes for Internet Applications . The
International Conference on Dependable Systems and Networks: 459–468 (July 2002),
http://www.ece.cmu.edu/~koopman/networks/dsn02/dsn02_koopman.pdf
9. Lidl, R. and Niederreiter, H., Introduction to Finite Fiel ds and their Applications ,
Cambridge University Press, 1994.
10. R. Lidl and H. Niederreiter, Finite Fields , Addison-Wesley, 1983.
11. Ling, S., Xing, C., Coding Theory. A First Course, Cambridge University Press, 2004.
12. MacWilliams, F. J., and Sloane, N. J. A., The Theory of Error-Correcting Codes, vol. 1 and
2, North Holland, 1977.
13. Moreira, J. C., Farrell, P.G, Essentials of Error-Control Coding , John Wiley & Sons Ltd,
2006.
14. Shannon, C.E., A Mathematical Theory of Communication , Bell Systems Technical Journal
27, 623-656 (1948).
15. Shannon, C.E., Communications in th e presence of noise , Proceedings of the IEEE, 37, 10-
21 (1949).

69
16. Shannon, C.E., Communication Theory of Secrecy Systems , (initially “A Mathematical
Theory of Cryptography”, Memorandum MM 45 -110-02, Sept. 1, 1945, Bell Laboratories,
confidential report), declassified in Bell System Technical Journal , vol. 28( 4), page 656–
715, 1949. (http://netlab.cs.ucl a.edu/wiki/files/shannon1949.pdf)
17. Standard ECMA-130, Data Interchange on Read-only 120 mm Optical Data Disks (CD-
ROM) 2nd edition (June 1996),
http://www.ecma-international.org/p ublications/standards/Ecma-130.htm
18. van Tilborg, H.C.A., Finite Fields and Error Correcting Codes , in Handbook of Algebra,
vol I, Elsevier Science 1996, p. 397-422.