Matematic a si Informatic a Aplicate n Inginerie [626309]

Universitatea POLITEHNICA DIN BUCURES TI
Facultatea DE S TIINT  E APLICATE
Matematic a  si Informatic a Aplicate ^ n Inginerie
Proiect de Diplom a
Coordonator  stiint ic,
Lect.dr. Mona DOROFTEI
Absolvent: [anonimizat]-Vasilic a MUNTEANU
Bucure sti
2017

Universitatea POLITEHNICA DIN BUCURES TI
Facultatea DE S TIINT  E APLICATE
Matematic a  si Informatic a Aplicate ^ n Inginerie
Aprobat
Decan:
Prof. dr. Emil PETRESCU
Circuite Secvent iale Liniare  si
Coduri Detectoare  si
Corectoare de Erori
Coordonator  stiint ic,
Lect.dr. Mona DOROFTEI
Absolvent: [anonimizat]-Vasilic a MUNTEANU
Bucure sti
2017

Adrian-Vasilic a MUNTEANU
Cuprins
1 Introducere 2
2 C^ ampuri Galois 4
2.1 C^ ampuri Galois de baz a . . . . . . . . . . . . . . . . . . 4
2.2 Extensia c^ ampului Galois, GF(pm) . . . . . . . . . . . . 8
2.3 C^ ampul Galois, GF(22) . . . . . . . . . . . . . . . . . . . 8
2.4 C^ ampul Galois, GF(23) . . . . . . . . . . . . . . . . . . . 9
1

Adrian-Vasilic a MUNTEANU
1 Introducere
Nevoia de a comunica este necesitatea int ei umane de a schimba
informat ii cu semenii s ai. Indispensabil a ^ n desf a surarea oric arei ac-
tivit at i, ea a existat dintotdeauna, iar transmisia informat iei a ap arut
ca un r aspuns la aceast a nevoie, prezent^ and un interes continuu ^ n dome-
niul cercet arii aplicative.
Lucrul
exibil  si abil cu informat ia, at^ at din punct de vedere al
prelucr arii c^ at  si al stoc arii  si transmiterii acesteia ^ ntr-un timp c^ at mai
scurt, este indispensabil ^ n dezvoltarea tehnologic a a dispozitivelor  si
echipamentelor de calcul. Informat ia este util a doar dac a este corect a
 si transmis a oportun. Asupra canalului de transmisie act ioneaz a perma-
nent perturbat ii care afecteaz a corectitudinea informat iei.
Codurile corectoare de erori corecteaz a sau detecteaz a erorile ce apar
^ n urma perturbat iilor asupra canalelor care nu pot asigura transmiterea
perfect a a unui mesaj. Procedeul de detectare/corectare se realizeaz a
prin modicarea mesajului original. Astfel, mesajului original ^ i sunt
ad agate simboluri care ajut a la detectarea  si corectarea erorilor.
Codurile sunt folosite ^ n domenii precum criptograa, compresia de
date sau ret elele de internet  si sunt cercetate intens de diferite discipline
 stiint ice cu scopul dezvolt arii unor metode eciente  si abile de trans-
misie a datelor. Compact discurile, discurile dure, memoriile interne ale
calculatoarelor, memoriile
ash, DVD-urile etc. sunt protejate ^ mpotriva
alter arii accidentale a datelor prin folosirea unor astfel de coduri, f ar a de
care aceste dispozitive,  si multe altele, nu ar putea funct iona.
Bazele teoriei cod arii au fost puse de c atre matematicianul Claude
Shannon care  si-a propus s a studieze din punct de vedere matematic
problemele ce apar la transmiterea informat iilor cu ajutorul semnalelor
^ n sistemele comunicat iilor electrice. El considera c a o comunicat ie sigur a
va  realizabil a cu ajutorul cod arii canalului prin ad augarea de informat ie
redundant a mesajelor transmise.
^In lucrarea sa initulat a "A Mathematical Theory of Communication",
publicat a ^ n 1948, Shannon a demonstrat c a o comunicat ie sigur a este
posibil a printr-un canal oric^ at de zgomotos dac a este ^ ndeplinit a condit ia
ca rata de transmisie s a e mai mic a dec^ at capacitatea canalului. De si
lucrarea sa are o important  a fundamental a, Shannon nu a propus nicio
solut ie explicit a de codare a canalului pentru implement ari practice.
La put in timp dup a publicarea lucr arii lui Shannon, au fost inventate
codurile bloc liniare. ^In 1950, Richard Hamming propune unul dintre
2

Adrian-Vasilic a MUNTEANU
primele coduri corectoare de erori. Codul implementat de c atre Hamming
este capabil de corectarea unei singure erori, performant  a considerat a
prea sc azut a pentru aplicat ii practice.
Un moment important pentru aplicat iile practice este descoperirea, ^ n
1959, a familiei de coduri bloc binare corectoare de multiple erori, coduri
numite BCH (Bose-Chaudhuri-Hocquenghem). Dup a 1960, literatura de
specialitate a cunoscut numeroase articole care au aprofundat studiul
codurilor liniare  si au propus o serie de coduri concrete.
3

Adrian-Vasilic a MUNTEANU
2 C^ ampuri Galois
Proiectarea de coduri cu dimensiune nit a, deci cu un num ar limitat
de elemente ^ n alfabet, impune denirea unor c^ ampuri numerice nite,
cu operat ii interne de adunare  si multiplicare.
2.1 C^ ampuri Galois de baz a
Se nume ste c^ amp de baz a sau c^ amp Galois, inelul claselor de resturi
modulo m, unde m=p sipeste un num ar prim. C^ ampurile Galois se
noteaz a cu GF(p).
GF(p) ={0,1, . . . , p −1}
De exemplu, pentru p= 2, obt inem c^ ampul GF(2) cu dou a ele-
mente, {0,1}. Regulile de adunare  si ^ nmult ire pentru GF(2) sunt date
^ n urm atoarele tabele:
Tabelul 2.1. Adunare modulo 2
+0 1
00 1
11 0
Tabelul 2.2. ^Inmult ire modulo 2
×0 1
00 0
10 1
Observ am c a oric arui element din GF(2) ^ i corespunde:
a+a≡0(mod 2);
a2≡a(mod 2) .
C^ and p= 3, avem c^ ampul GF(3) cu elementele {0,1,2}, ^ n care
adunarea  si ^ nmult irea se execut a astfel:
Tabelul 2.3. Adunare modulo 3
+0 1 2
00 1 2
11 2 0
22 0 1
4

Adrian-Vasilic a MUNTEANU
Tabelul 2.4. ^Inmult ire modulo 3
×0 1 2
00 0 0
10 1 2
21 2 1
Se observ a c a pentru orice element din GF(3),
a+a+a≡0(mod 3);
3a≡0(mod 3) .
Mai avem c a,
Tabelul 2.5.
a0 1 2
a20 1 1
a30 1 2
Prin urmare, dac a a̸≡0 (mod 3) atunci pentru orice element din
GF(3) avem:
a2≡1(mod 3);
a3≡a(mod 3);
a4≡a2(mod 3);
a5≡a(mod 3);
. . . . . . . . . .
^In cazul p= 5, obt inem c^ ampul GF(5), ale c arui elemente sunt
{0,1,2,3,4}.^InGF(5) adunarea  si ^ nmult irea elementelor se efectueaz a
conform tabelelor urm atoare:
Tabelul 2.6. Adunare modulo 5
+0 1 2 3 4
00 1 2 3 4
11 2 3 4 0
22 3 4 0 1
33 4 0 1 2
44 0 1 2 3
5

Adrian-Vasilic a MUNTEANU
Tabelul 2.7. ^Inmult ire modulo 5
×0 1 2 3 4
00 0 0 0 0
10 1 2 3 4
20 2 4 1 3
30 3 1 4 2
40 4 3 2 1
Pentru orice element din GF(5) avem:
a+a+a+a+a≡0(mod 5);
5a≡0(mod 5) .
De asemenea, avem c a pentru orice a̸≡0(mod 5) din c^ ampul GF(5),
Tabelul 2.8.
×0 1 2 3 4
a0 1 2 3 4
a20 1 4 4 1
a30 1 3 2 4
a40 1 1 1 1
a50 1 2 3 4
adic a oric arui element a̸≡0(mod 5) din GF(5) ^ i corespunde:
a4≡1(mod 5);
a5≡a(mod 5) .
Observ am c a ^ n GF(5) elementele nenule ale c^ ampului sunt generate
de 21,22,23,24 si de 31,32,33,34, adic a pentru orice a̸= 0 exist a x, y
astfel ^ nc^ at:
2x≡a(mod 5);
3y≡a(mod 5) .
Dac a eeste cel mai mic num ar pozitiv astfel ^ nc^ at
ae≡1(mod p),
atunci spunem c a elementul a̸= 0 apart ine exponentului epentru mod-
ululpsau c a eeste indicele lui a.
Se poate ar ata c a orice indice eeste un divizor al lui p−1.
6

Adrian-Vasilic a MUNTEANU
Numim indicatorul lui Euler al num arului ^ ntreg m, num arul natural
egal cu num arul elementelor dintr-un sistem redus de resturi modulo m.
Indicatorul lui Euler se noteaz a cu φ(m). Pentru numerele m=p,p
num ar prim, nu exist a sistem redus de resturi mod p.^In acest caz,
φ(p) =p−1.
Pentru c^ ampul GF(p) avem p−1 numere ace apart in exponentului
p−1, adic a cele φ(p−1) puteri ale acestor numere,
a, a2, . . . , aφ(p1),
au resturi diferite  si anume 1 ,2, . . . , p −1 ^ nscrise ^ ntr-o ordine anume.
Aceste numere ase numesc elemente primitive sau r ad acini primitive ale
c^ ampului.
Pentru orice num ar ria
at ^ ntre 1  si p−1 exist a un exponent x
cuprins ^ ntre 1  si p−1, astfel ^ nc^ at
ax≡ri(mod p),
unde a este element primitiv, iar xeste indicele lui ri^ n raport cu baza
a.
G asirea unei r ad acini primitive se realizeaz a prin ^ ncerc ari. De ex-
emplu, pentru p= 13 se poate g asi cea mai mic a r ad acin a primitiv a
astfel:
φ(13) = 12 = φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12).
Aleg^ and ca baz a pe a= 2, obt inem:
i 1 2 3 4 5 6 7 8 9 10 11 12
a≡2i(mod p)2 4 8 3 6 12 11 9 5 10 7 1
Prin urmare, cea mai mic a r ad acin a primitiv a pentru modulul p= 13
estea= 2.
Pentru numerele prime mai mici dec^ at 100, se g asesc^ n tabelul urm ator
cele mai mici r ad acini primitive:
Tabelul 2.9. R ad acini primitive
a p
23 5 11 13 19 29 37 53 59 61 67 83
37 5 11 13 19 29 37 53 59 61 67 83
523 47 73 97
641
771
7

Adrian-Vasilic a MUNTEANU
2.2 Extensia c^ ampului Galois, GF(pm)
FieFun c^ amp  si p(x) un polinom cu coecient i din F. Dac a p(x)
este ireductibil ^ n c^ ampul F, atunci clasele de resturi de polinoame peste
Fmod p(x) formeaz a un c^ amp. Dac a p(x) este polinom ireductibil de
grad m, c^ ampul format din polinoamele mod p(x) se nume ste extensia
c^ ampului de ordin mpeste F.
C^ ampul Galois, GF(pm), format din pmelemente sau pm−1 elemente
nenule, reprezint a c^ ampul polinoamelor mod p(x) ^ n care p(x) este poli-
nom ireductibil de grad mpeste GF(p). De asemenea, c^ ampul GF(pm)
este  si spat iu vectorial peste GF(p). Deci putem spune c a exist a un
c^ amp Galois GF(q) cu qelemente pentru orice num ar q=pm, unde
peste num ar prim. Astfel de c^ ampuri Galois, formate din clase de res-
turi de polinoame modulo p(x), cu p(x) polinom ireductibil peste c^ ampul
coecient ilor lui GF(pm), se numesc c^ ampuri de caracteristic a p, pentru
orice num ar m.
^InGF(pm), ca  si^ n cazul c^ ampurlor de baz a, exist a αelement primitiv
de ordin p−1 astfel ^ nc^ at ecare element al c^ ampului poate  construit
ca putere a lui α.
2.3 C^ ampul Galois, GF(22)
^Imp art ind un polinom cu coecient i din GF(2) la p(x) =x2+x+ 1
obt inem restul modulo 2,
R=a1x+a0(mod 2) .
Coecient ii a0 sia1pot lua doar valorile 0  si 1 deci, clasele de resturi
de polinoame sunt constituite din polinoamele,
{0},{1},{x},{x+ 1}.
Aceste 4 polinoame formeaz a elementele c ampului GF(22).^In acest
c^ amp, suma a dou a elemente este denit a ^ n tabelul urm ator:
Tabelul 2.10. Adunare ^ n GF(22)
+ 0 1 x x + 1
0 0 1 x x + 1
1 1 0 x+ 1 x
x x x + 1 0 1
x+ 1 x+ 1 x 1 0
8

Adrian-Vasilic a MUNTEANU
^Inmult irea elementelor c^ ampului GF(22) se realizeaz a astfel:
Tabelul 2.11. ^Inmult ire ^ n GF(22)
× 0 1 x x + 1
0 0 0 0 0
1 0 1 x x + 1
x 0 x x + 1 1
x+ 1 0x+ 1 1 x
Elementele, 0 ,1, x, x + 1, ^ mpreun a cu legile de adunare  si ^ nmult ire
denite anterior, formeaz a c^ ampul Galois GF(22). Se observ a c a GF(2)
este inclus ^ n c^ ampul GF(22) a sadar, putem spune c a GF(22) este o
extensie a c^ ampului GF(2).
Not^ and un element din GF(22) cu α, avem:
Tabelul 2.12.
α0 1 x x + 1
α20 1 x+ 1 x
α30 1 1 1
α40 1 x x + 1
Deci, pentru orice element α̸= 0 din c^ ampul GF(22),
α3= 1;
α4=α.
Cum pentru α=x, α2=x+ 1  si conform legilor de adunare din
GF(22),x+1+ x+1 = 0, rezult a c a α=xeste o r ad acin a a polinomului
p(x).
p(α) =α2+α+ 1 = x+ 1 + x+ 1 = 0 .
2.4 C^ ampul Galois, GF(23)
Restul modulo 2 obt inut prin ^ mp art irea unui polinom cu coecient i
dinGF(2) la p(x) =x3+x+ 1 este:
R=a2x2+a1x+a0(mod 2) ,
unde a0,a1 sia2pot lua doar valorile 0  si 1 deci, clasele de resturi de
polinoame sunt constituite din polinoamele:
{0},{1},{x},{x+ 1},{x2},{x2+ 1},{x2+x},{x2+x+ 1}.
9

Adrian-Vasilic a MUNTEANU
^InGF(23) legile de adunare  si ^ nmult ire sunt:
Tabelul 2.13. Adunare ^ n GF(23)
+ 0 1 x x+ 1 x2x2+x x2+x+ 1 x2+ 1
0 0 1 x x+ 1 x2x2+x x2+x+ 1 x2+ 1
1 1 0 x+ 1 x x2+ 1 x2+x+ 1 x2+x x2
x x x+ 1 0 1 x2+x x2x2+ 1 x2+x+ 1
x+ 1 x+ 1 x 1 0 x2+x+ 1 x2+ 1 x2x2+x
x2x2x2+ 1 x2+x x2+x+ 1 0 x x+ 1 1
x2+x x2+x x2+x+ 1 x2x2+ 1 x 0 1 x+ 1
x2+x+ 1 x2+x+ 1 x2+x x2+ 1 x2x+ 1 1 0 x
x2+ 1 x2+ 1 x2x2+x+ 1 x2+x 1 x+ 1 x 0
Tabelul 2.14. ^Inmult ire ^ n GF(23)
+ 0 1 x x+ 1 x2x2+x x2+x+ 1 x2+ 1
0 0 0 0 0 0 0 0 0
1 0 1 x x+ 1 x2x2+x x2+x+ 1 x2+ 1
x 0x x2x2+x x+ 1 x2+x+ 1 x2+ 1 1
x+ 1 0x+ 1 x2+x x2+ 1 x2+x+ 1 1 x x2
x20x2x+ 1 x2+x+ 1 x2+x x2+ 1 1 x
x2+x 0x2+x x2+x+ 1 1 x2+ 1 x x2x+ 1
x2+x+ 1 0x2+x+ 1 x2+ 1 x 1 x2x+ 1 x2+x
x2+ 1 0x2+ 1 1 x2x x+ 1 x2+x x2+x+ 1
Polinoamele, 0 ,1, x, x + 1, x2, x2+x, x2+x+ 1, x2+ 1, ^ mpreun a cu
legile de adunare  si ^ nmult ire denite ^ n tabelele de mai sus, formeaz a
c^ ampul Galois GF(23).
10