Vés al contingut

Cos finit

De la Viquipèdia, l'enciclopèdia lliure
Joseph Wedderburn demostrà l'última conjectura sobre els cossos finits el 1905

En matemàtiques i més precisament en la branca de la teoria de Galois, un cos finit, anomenat també cos de Galois és un cos el cardinal del qual és finit (té un nombre finit d'elements). Tret d'isomorfismes, tot cos finit queda completament determinat pel seu cardinal que és sempre de la forma pn, una potència d'un nombre primer. Aquest nombre primer no és altre que la seva característica (el nombre més petit de vegades que s'ha de sumar l'element neutre de la multiplicació per a obtenir l'element neutre de la suma) i el cos es presenta com l'única extensió finita del cos primitiu Z/p de dimensió n.

Les aplicacions són essencialment la teoria de nombres algebraics on els cossos finits apareixen com una estructura essencial per a la geometria aritmètica. Aquesta branca ha permès, entre altres coses, demostrar l'últim teorema de Fermat. Els cossos finits s'utilitzen sovint en criptografia i en teoria dels codis, per exemple, per determinar codis correctors eficaços.

Observació sobre la terminologia: quan l'àlgebra abstracta va començar a ésser desenvolupada, la definició de cos normalment no incloïa la commutativitat de la multiplicació, així el que avui s'anomena cos fa un temps hauria estat anomenat cos commutatiu o domini racional. Avui en dia però, un cos és sempre commutatiu. Una estructura que satisfaci totes les propietats d'un cos llevat de la commutativitat, s'anomena avui anell de divisió encara que cos no commutatiu és encara força usat. Altres llengües han mantingut aquesta antiga notació. Així per exemple, en italià i francès, els anells de divisió se'ls anomena corpo i corps. En canvi, en anglès, alemany i espanyol, field, Körper (d'aquí ve que denoti normalment un cos) i cuerpo signifiquen cos. Cal remarcar que en francès no hi ha una paraula concreta per designar un cos, amb la qual cosa s'ha d'usar la forma corps commutatif.[1] En italià existeix també la forma campo que es tradueix exactament per la nostra noció de cos. En el cas dels cossos finits, aquesta observació, de fet, té poca importància, ja que, segons el teorema de Wedderburn, tot cos finit és commutatiu. Aquest resultat es demostra amb l'ajuda dels polinomis ciclotòmics.

Història

[modifica]

Teoria

[modifica]
Ferdinand Georg Frobenius

La teoria general dels cossos apareix de manera inicial durant la segona meitat del segle xix. Richard Dedekind (1831-1916) inventa el terme alemany de Körper,[2] terme que encara es fa servir avui, la traducció catalana del qual és cos. Una primera definició és a l'obra de Heinrich Weber (1842-1913).[3] La definició axiomàtica moderna és deguda a Ernst Steinitz (1871-1928) i data de 1910.

Els treballs de Frobenius (1849-1917) marquen el començament de la utilització dels cossos finits no primers. Semblen necessaris per a la resolució de qüestions[4] sobre la teoria de les representacions d'un grup finit. L'endomorfisme de Frobenius permet aplicar la teoria de Galois a aquestes estructures. La teoria es mostra eficaç en el cas commutatiu. L'existència, el cardinal i l'estructura dels cossos finits queden determinats ràpidament. Això fa que es vegi que els termes cos de Galois i cos finit són de fet sinònims.

L'estudi sistemàtic dels cossos finits comença amb el segle xx, amb els treballs de Leonard Dickson (1874-1954) i després de Joseph Wedderburn (1882-1948). Dickson publicà[5] la primera classificació dels cossos finits commutatius, on s'explicita l'estructura de l'anell dels polinomis associat. La qüestió del cas no commutatiu era en aquells moments l'objecte d'una conjectura: no existeix cap cos finit no commutatiu. Wedderburn es queda a la Universitat de Chicago el 1904 i treballa en estreta col·laboració amb Dickson. A la seva tornada, l'any següent, demostra la conjectura que esdevé el teorema de Wedderburn, anomenat així en el seu honor.

Des d'aquesta època, la teoria pròpiament dita ja no comporta cap problema obert. En canvi, les aplicacions, tant teòriques com pràctiques, abunden durant tot el segle xx.

Aplicacions teòriques

[modifica]

Els cossos finits es fan servir, especialment, en aritmètica. Contribueixen per exemple al fonament de l'aritmètica modular. Varen permetre a Gauss (1777-1865) demostrar[6] la llei de reciprocitat quadràtica. L'estructura de cos intervé sobretot en la resolució d'equacions diofàntiques (vegeu l'apartat equació diofàntica). El petit teorema de Fermat n'és un exemple arquetípic.

Artin (1898-1962) utilitza el fet que un context natural de les lleis de reciprocitat és el dels cossos finits. És una de les eines que li permeten resoldre el novè problema de Hilbert. Inicia l'anàlisi de l'equivalent de la Funció zeta de Riemann sobre els cossos finits. La geometria aritmètica es generalitza sobre estructures finites. Aquest enfocament és particularment actiu durant la segona meitat del segle xx. André Weil (1906-1998) generalitza el pas a les corbes algebraiques i Pierre Deligne (nascut el 1944), a les varietats algebraiques. Les conjectures de Weil sobre les varietats sobre cossos finits, enunciades el 1940 per André Weil, formen part dels problemes importants d'aquesta època. Demostrades el 1974, obren la via a la demostració del teorema de Taniyama-Shimura per part d'Andrew Wiles, que té per conseqüència l'últim teorema de Fermat.

Aplicacions pràctiques

[modifica]
Voyager 2 utilitza el codi Reed-Solomon basat en la teoria dels cossos finits per a les comunicacions.

Després de la Segona Guerra mundial i per a les necessitats de la societat, Claude Shannon (1916-2001) formalitza la teoria de la informació com una branca de les matemàtiques,[7] formulant les problemàtiques de la seguretat i de la fiabilitat.[8]

La criptografia es recolza en la possibilitat de generar ràpidament nombres primers grans. La confidencialitat d'un missatge s'assegura per la incapacitat actual per descompondre enters, és a dir d'efectuar un algorisme que permeti descompondre un nombre en factors primers en un temps raonable. Una investigació activa intenta crear nous algorismes que vagin en aquest sentit. Així, Michael Rabin (nascut el 1931) publicà[9] un test de primalitat basant-se en les propietats del grup multiplicatiu dels cossos primers.

La fiabilitat tracta de la capacitat per transmetre sense error un missatge malgrat alteracions en la comunicació. La teoria dels codis correctors tracta les tècniques per aconseguir-ho. El 1950, Richard Hamming (1915-1998) treballa per als laboratoris Bell amb Shannon sobre aquest tema. Fa servir[10] els espais vectorials de dimensió finita sobre cossos finits per formalitzar un marc operacional de la teoria i trobar els primers exemples de codis correctors òptims. Aquest enfocament dona a llum la teoria dels codis lineals.

El 1960, dos matemàtics, R. C. Bose, D. K. Ray-Chaudhuri, demostren[11] que ideals de l'anell dels polinomis sobre els cossos finits de característica dos resulten particularment adequats per aquesta finalitat. La teoria és generalitzada[12] pel matemàtic A. Hocquenghem i dona a llum la família de codis BCH. Els altres dos fundadors de la teoria, I. Reed i G. Solomon enriqueixen el mètode[13] i creen codis en condicions de resistir grans alteracions, els codis de Reed-Solomon. Les aplicacions més conegudes són probablement el sistema de comunicació de certes sondes de la NASA com la Voyager o els discs compactes. Durant els anys de la dècada del 1970 els resultats d'aritmètica avançats sobre les corbes el·líptiques dels cossos finits, troben la seva aplicació,[14] per exemple, amb els codis de Goppa.

La teoria dels codis correctors ara es considera com una branca de la dels cossos finits.

Exemples

[modifica]

El cos més petit

[modifica]

El cos finit més petit no trivial, notat (, +, .) o més simplement F₂ té dos elements diferents, és a dir l'element neutre per a l'addició 0 i l'element neutre per a la multiplicació 1. Heus aquí la definició dels operacions «+» i «.» sobre aquest cos:

+ 0 1
0 0 1
1 1 0
. 0 1
0 0 0
1 0 1

Cos primers i extensions

[modifica]

Com que Z és un anell euclidià principal, tot ideal I s'escriu de manera única sota la forma I = n.Z on n s'anomena el generador positiu de I. Per definició, és el nombre natural més petit no nul que no pertany a I. Només les estructures quocients obtingudes a partir de Z són doncs els anells commutatius unitaris Z/n.Z.

Aquests anells donen els primers exemples de cossos finits:

  • L'anell Z/nZ és un cos si i només si n és un nombre primer.

En efecte, aquesta proposició és una conseqüència directa de la identitat de Bézout. Suposem n primer, llavors si a és un enter primer amb n, és a dir que el màxim comú divisor entre a i n és 1 (altrament dit, a i n són coprimers), existeixen dos enters b i c tals que:

La qual cosa significa que la classe d'a és invertible i la seva inversa és la classe de b (fixeu-vos que tots els múltiples de n formen la classe del 0).

Recíprocament, si n no és pas primer, existeixen dos enters a i b diferents de n i d'1 tals que el seu producte és igual a n. La classe d'a així com la classe de b són dels divisors de zero, la qual cosa no pot ser en un cos.

Una qüestió important serà la de l'estructura del grup multiplicatiu dels cossos finits. Aquí:

  • Si p és primer, llavors el grup dels invertibles Z/p.Z* és un grup cíclic d'ordre p - 1.

Es veurà a més que aquests exemples són de fet els únics exemples de cossos finits de cardinal un nombre primer, i també que tot cos finit es pot obtenir per extensió algebraica a partir d'un d'aquests cossos. Si p és un nombre primer, Fp designa el cos Z/p.Z.

Existeixen polinomis irreductibles P[X] de Fp [X] tals que el quocient Fp [X]/(P[X]) de l'anell dels polinomis Fp [X] per l'ideal principal engendrat per tal polinomi irreductible P(X) sigui un cos finit (commutatiu). Conté estrictament el cos primer d'ordre p, si el polinomi no és de grau 1. Aquest cos no és altre que un cos de ruptura del polinomi: la classe de X subministra a una arrel de P.

Per exemple, per a p=2, el polinomi 1+X+X² és irreductible en F₂ [X] (és l'únic polinomi irreductible de grau 2). L'extensió corresponent és un cos notat F₄. Aquest cos té exactament 4 elements que són 0, 1, i les dues arrels x i x+1 de 1+X+X². Les seves lleis additiva i multiplicativa venen donades tal com segueix:

+ 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
. 0 1 x x+1
0 0 0 0 0
1 0 1 x x+1
x 0 x x+1 1
x+1 0 x+1 1 x

Per a p > 2, la funció polinòmica quadrat, que a x li associa el seu quadrat x² no és injectiva, ja que fa correspondre als elements diferents 1 i -1 l'element 1. Com que el seu conjunt de sortida és igual al seu conjunt d'arribada i és de cardinal finit, la funció no és tampoc suprajectiva. Per tant, existeix almenys un element a tal que el polinomi P[X] igual X² - a no és descomponible. L'extensió associada a aquest polinomi és de grau 2 i subministra un cos que conté n = p² elements notat Fn. Aquest cos és independent de a.

Extensions de cossos finits

[modifica]

El teorema de Wedderburn diu que tot cos finit és commutatiu, és doncs una extensió finita d'un cos primer. Es demostra primer que tot cos finit és de cardinal la potència d'un nombre primer, després que existeix un isomorfisme agafant un únic cos finit de tal cardinal donat.

Característica i cardinal

[modifica]

Sigui K un cos finit i p la seva característica, és a dir l'enter més petit tal que l'addició d'1 iterada p vegades sigui igual a 0. Tal nombre existeix, ja que si no, el grup additiu engendrat per 1 seria de cardinal infinit i K no conté pas un subconjunt infinit. A més, p és un nombre primer. En efecte, si a i b són enters tals que a⋅b = p, llavors el producte de a per b és nul en K, la qual cosa demostra que o bé a o bé b és un múltiple de p, ja que no existeix en divisors de 0 en un cos. L'únic homomorfisme d'anells unitaris de Z en K induït una injecció de Z/p. Z en K la seva imatge és el subcos de K format pels elements del subgrup additiu engendrat per 1. És un subcos de K que conté p elements i és isomorf a Z/pZ, també notat Fp.

El cos K hereta doncs d'una estructura d'espai vectorial sobre Fp. La seva dimensió és per força finita, sigui n aquesta dimensió, llavors el seu cardinal és pn. En resum:

  • El cardinal d'un cos finit és una potència d'un nombre primer que n'és la seva característica. Més exactament, tot cos finit és una extensió finita d'un cos primer Fp..

Automorfisme de Frobenius

[modifica]

Sigui K un cos finit de característica p, de cardinal = pk. Llavors, es pot demostrar la fórmula següent:

L'aplicació que, a x, li associa xp de K en ell mateix és un endomorfisme bijectiu, anomenat endomorfisme de Frobenius i notat aquí Frob. Aquest automorfisme és important en l'estudi dels cossos finits. Es pot enunciar el teorema següent que es demostra a l'article principal :

  • Tot cos finit és perfecte, és a dir que les seves extensions algebraiques són separables

Aquest fet té una conseqüència important, pel teorema de l'element primitiu, que afirma que tota extensió finita i separable és simple és a dir engendrada per un únic element:

  • Tota extensió de cossos finits és simple.

L'estudi de l'automorfisme de Frobenius permet també determinar els polinomis irreductibles sobre el cos finit K:

  • Els polinomis irreductibles de K de grau n són els divisors primers de grau n del polinomi següent i són doncs tots els ciclotòmics:

Existència d'un cos finit de cardinal pn

[modifica]

Sigui n un enter estrictament positiu, q l'enter igual a pn i L el cos de descomposició del polinomi P[X] = Xq - X sobre el cos Fp. El conjunt dels elements invariants per l'automorfisme Frobn és una extensió K de Fp. K és exactament el conjunt de les arrels de P[X]. Ara bé P[X] és descomponible sobre K, és a més separable, ja que és primer amb el seu polinomi derivada igual a 1 (aquesta propietat es demostra en el paràgraf Cas dels polinomis de l'article Extensió separable). K conté doncs tantes arrels com el seu grau, és a dir pn.

Grup multiplicatiu i conseqüències

[modifica]

Sigui K un cos finit de cardinal q = pn. Llavors, el grup multiplicatiu d'aquest cos és de cardinal q - 1; sigui e el seu exponent, e és un divisor de q - 1. Llavors resulta que el polinomi Xe - 1 amb coeficients a K, posseeix q - 1 arrels diferents i és de grau e, això implica que e és més gran o igual que q - 1, com que e ha de ser al mateix temps un divisor de q -1 només pot ser e = q -1. L'exponent del grup multiplicatiu és igual al seu ordre, i com que en un grup finit commutatiu l'exponent és sempre l'ordre d'un element del grup, en resulta que:

  • El grup multiplicatiu d'un cos finit és cíclic.

En conseqüència, tot cos de cardinal q és un cos de descomposició del polinomi Xq - X sobre Fp. Dos cossos de descomposició qualsevulla d'aquest tipus són isomorfs, perquè si es fixa una clausura algebraica de Fp, llavors:

  • Existeix un i un només un cos de cardinal q, notat Fq, contingut a la clausura algebraica fixada.

Propietats de Galois

[modifica]

Una conseqüència del paràgraf precedent és que el polinomi mínim ψq-1[X] d'un element primitiu és de grau n, i el cos Fq de cardinal q és isomorf al cos de ruptura Fp[X]/ψq-1[X]. Ara bé, aquest polinomi és divisor del polinomi Xq-1-1, que es descompon en Fq. Així:

  • L'extensió Fq/Fp és cos de descomposició del polinomi cyclotomic ψq-1[X]. És una extensió de Galois.

I més precisament, l'endomorfisme de Frobenius Frob és un automorfisme del cos Fq' que deixa el seu subcos primer invariant, és doncs un element del grup de Galois. Considerant llavors un element x primitiu en Fq, es veu que:

i per primitivitat, n és la potència més petita de Frob que deixa x fix. Frob és doncs un element d'ordre com a mínim n del grup de Galois, que és d'ordre el grau n de l'extensió:

  • L'endomorfisme de Frobenius és un generador del grup de Galois Gal (Fq/Fp), que és en particular cíclic d'ordre n.

El teorema fonamental de la teoria de Galois permet la determinació dels subcossos d'un cos finit. Els subgrups del grup de Galois són els grups cíclics d'ordre un divisor de n, en conseqüència:

  • Existeixen exactament tants subcossos com divisors d de n per a una extensió de cardinal pn. Els subcossos K tenen per a cardinal pn, són extensions de Galois, i el grup Gal (K/K' ) és un grup cíclic d'ordre n/d.

Clausura algebraica

[modifica]

Es coneixen pel que precedeix totes les extensions finites, i per tant, per reunió, totes les extensions algebraiques dels cossos finits. Tota clausura algebraica de es pot veure com la composició dels \mathbb .

Des del punt de vista de la teoria de Galois, la família dels grups , per a n variant, forma doncs el que es diu un sistema projectiu, és a dir que el grup de Galois absolut és el límit projectiu dels grups ; és, per tant, el complement profinit Que és així un grup procíclic: un generador natural és altre cop l'endomorfisme de Frobenius, que pot ser vist com la dada de la família compatible dels endomorfismes de Frobenius de les extensions finites.

Aquesta descripció completa de les extensions algebraiques dels cossos finits és un element important que intervé en la teoria dels cossos de classes per als cossos de nombres i els cossos de nombres p-adics, ja que els seus cossos residuals són cossos finits.

Polinomi irreductible

[modifica]

Extensió normal i polinomi ciclotòmic

[modifica]
Il·lustració gràfica del grup multiplicatiu de F

Sigui p un nombre primer n un enter estrictament positiu i K un cos de cardinal q = pn.

El paràgraf precedent mostra que tot element de K és arrel del polinomi Xq - X. A Excepció de l'element nul, tot element és arrel de la unitat. Aquesta propietat s'il·lustra a la figura de la dreta, els tres elements no nuls de F₄ són les tres arrels de la unitat. Aquesta observació porta a la proposició següent:

  • Tot element de K* és arrel de la unitat i tot polinomi irreductible diferent de X és ciclotòmic.

Si φ designa la funció Fi d'Euler llavors existeixen exactament φ(q - 1) elements primitius a K. Cada element primitiu posseeix un polinomi mínim amb coeficients en Fp de grau n igual a la dimensió de K considerat com espai vectorial sobre Fp.

  • Existeixen exactament φ(q - 1) elements primitius a K, que corresponen a φ(q - 1)/n polinomis sobre Fp. Tanmateix, hi pot haver altres polinomis irreductibles d'igual grau: en F9, es té x8 - 1 = (x - 1)(x + 1)(x² + 1)(x² + x +2)(x² + 2x + 2) mod 3, tot i que és irreductible, no és el polinomi mínim de cap dels 4 elements primitius.

Aquesta propietat s'associa a una definició important en la teoria dels cossos finits:

  • Dos elements de K s'anomenen conjugats si i només si posseeixen el mateix polinomi irreductible. La relació de conjugació és una classe d'equivalència. Cada classe posseeix com a cardinal el grau del polinomi irreductible associat.

Dues propietats suplementàries indiquen la relació entre els polinomis cyclotomiques i el seu grau en el cas de la característica p. (Es demostren a l'article principal).

  • Un polinomi cyclotomic d'índex q - 1 sobre Fp és de grau l'ordre multiplicatiu de p modul q - 1.
  • El producte dels polinomis irreductibles de grau n és la imatge del polinomi cyclotomic d'índex q - 1 amb coeficients a Z pel morfisme canònic de Z[X] en Fp[X].

Característica dos

[modifica]

Existeixen exactament dos polinomis unitaris de grau u i el segon és el polinomi cyclotomique d'índex u:

Existeix exactament un polinomi de grau dos irreductible, és primitiu, és el polinomi cyclotomic d'índex tres. Es descompon en F₄. El polinomi cyclotomique d'índex 3 a Z és:

Existeixen exactament dos polinomis de grau tres irreductibles, ja que el cos conté sis elements fora del seu únic subcos. El grup multiplicatiu conté set elements, per tant sis són generadors. Existeixen doncs dos polinomis primitius són els dos polinomis cyclotomics d'índex set, descompost en F₈:

El seu producte és la imatge del polinomi cyclotomic amb coeficients a Z:

El cos F16 conté dos subcossos F₄ i F₂. En conseqüència, existeixen exactament tres polinomis irreductibles de grau quatre. El grup multiplicatiu F16* conté vuit generadors, ja que la funció Fi d'Euler aplicada a quinze és igual a vuit, existeixen doncs dos polinomis d'arrels els elements primitius. El polinomi restant és aquell que correspon al polinomi cyclotomic d'índex cinc. Existeixen doncs dos polinomis cyclotomiques d'índex quinze i un polinomi cyclotomic d'índex cinc.

A més, el producte dels dos polinomis cyclotomics d'índex 15 és la imatge del polinomi cyclotomic amb coeficients a Z:

Característica tres

[modifica]

Existeixen tres polinomis unitaris de grau u, el segon és el polinomi ciclotòmic d'índex u i el tercer d'índex dos.

L'extensió d'ordre nou conté sis elements fora del cos primer, és de dimensió dos, existeixen doncs exactament tres polinomis irreductibles. El grup multiplicatiu és d'ordre vuit i conté quatre elements generadors, dos dels polinomis són doncs cyclotomics d'ordre vuit, l'últim és cyclotomic d'ordre quatre.

L'extensió d'ordre vint-i-set conté un únic subcos, el cos primer. Existeixen doncs vint-i-quatre elements fora de tot subcos i vuit polinomis irreductibles de grau tres. El grup multiplicatiu conté vint-i-sis elements i dotze generadors i existeixen quatre polinomis cyclotomics d'índex vint-i-sis i quatre d'índex tretze.

També es verifica que:

Aplicacions

[modifica]

Equacions diofàntiques

[modifica]
Richard Dedekind

Una equació diofàntica és una equació amb coeficients sencers on les solucions que es busquen són senceres. Pierre de Fermat (1601, 1665) treballà a bastament sobre equacions d'aquesta naturalesa.

El petit teorema de Fermat estableix que si p és primer, llavors tot enter elevat a la potència p és congruent mòdul p amb aquest enter. En el context dels cossos finits, això indica que els punts fixos de l'automorfisme de Frobenius són els elements del cos primer, o que el grup multiplicatiu d'aquest últim és cíclic d'ordre p - 1.

Fermat es fixa que només per als nombres primers que són suma de dos quadrats, la divisió per quatre dona u de residu. Es fixa en efecte que:

En una carta escrita a Marin Mersenne, datada del 25 de desembre de 1640 proposa l'equació següent a ² + b ² = p amb p primer.

Richard Dedekind (1831-1916) proposa una demostració[15] la primera part de la qual consisteix a estudiar l'equació sobre el cos Fp. Fa servir les propietats del grup multiplicatiu i les dels polinomis amb coeficients en un cos. L'equació esdevé a ² + b ² = 0. Si b és igual a 0 llavors a també i la solució és trivial. En el cas contrari. És possible dividir entre b, ja que l'estructura subjacent és la d'un cos, l'equació esdevé llavors X ² + 1 = 0. Multiplicant el polinomi precedent per X ² - 1 = 0, obté l'equació següent: X 4 - 1 = 0. Les propietats del grup multiplicatiu donen una condició necessària i suficient sobre p: ha de ser congruent amb u mòdul quatre. La part final de la demostració no utilitza els cossos finits, es dona a l'article principal.

Aquest mètode, que consisteix a reduir l'equació al cos primer és freqüent. El cos disposa d'una estructura més forta i de nombrosos teoremes per a treure'n conclusions.

Codi corrector

[modifica]

Els codis correctors sorgeixen d'un problema molt concret vinculat a la transmissió de dades. En certs casos, una transmissió de dades es fa utilitzant un canal de comunicació que no és completament fiable. En altres paraules, les dades, quan circulen sobre aquesta via, són susceptible de ser alterades. L'objectiu d'un codi corrector és l'aportació d'una redundància de la informació de tal manera que l'error pugui ser detectat i fins i tot corregit.

Un missatge és una successió finita de caràcters, que en el cas d'un codi lineal es consideren com a elements d'un cos finit. Un missatge m apareix com un element d'un espai vectorial E sobre un cos finit de dimensió k. L'aportació de la redundància és el resultat d'una aplicació lineal injectiva φ de E en un espai F anomenat codi i de dimensió n superior a k. La paraula del codi que es transmet és l'element φ(m). L'interès de transmetre φ(m) en lloc de m s'il·lustra a la figura següent:

Il·lustració d'un codi no corrector i d'un codi corrector

Si es transmet el missatge m, i si la transmissió l'altera, llavors el missatge rebut és erroni (com s'il·lusta a la figura de l'esquerra) i el receptor no disposa de cap mitjà per localitzar o corregir l'error. Si l'aplicació φ(m) s'escull adequadament, cada punt del codi difereix dels altres punts del codi per almenys dues coordenades. Aquesta situació s'il·lustra sobre la figura de la dreta. Els punts del codi es representen en verd, la modificació d'una coordenada se simbolitza per un segment de la quadrícula. Fixeu-vos que en la figura els punts del codi difereixen tots entre ells en almenys d = 3 coordenades. Si, per exemple, l'alteració es refereix a una única coordenada, la transmissió correspon a un punt vermell. Llavors el receptor pot corregir l'error, ja que no existeix més que un únic punt del codi (en verd) a una distància d'1 del missatge rebut.

Il·lustració d'un codi perfecte

L'aplicació que, en dos punts de F, associa el nombre de coordenades diferents és una distància en el sentit matemàtic, anomenada distància de Hamming. Si la distància de Hamming mínima entre dos punts del codi és igual a d, llavors el codi està en condicions de corregir t alteracions on t és el major enter estrictament més petit que d/2. Sobre la figura de damunt, fixeu-vos en els punts negres. Corresponen a redundàncies inútils. Són en efecte a una distància de dos dels punts del codi, ara bé tal distància no és tractable en el cas de la figura.

El conjunt dels punts corregibles ve donat per la reunió de totes les boles de centre un punt del codi i de radi t. La configuració ideal és aquella on aquestes boles formen una partició de F. Llavors no existeix cap redundància inútil. Aquesta situació s'il·lustra per la figura de la dreta. Els punts del codi es representen en verd, la distància mínima d igual a 5. Les boles de centre els punts del codi i de radi 2 formen una partició de F. Els punts a distància 1 del codi es representen en blau, aquells a distància 2 en vermell. Tot missatge que contingui com a màxim dues alteracions pot ser corregit. Tot codi d'aquest tipus s'anomena perfecte.

La teoria dels cossos finits permet construir codis perfectes. L'espai F està proveït de l'estructura d'anell Fd[X]/P[X] on P[X] = Xn - 1 amb n = d a - 1 i a és un enter estrictament positiu. F correspon al conjunt dels polinomis que prenen valors diferents sobre el cos Fn+1. Si φ(E) és l'ideal engendrat pel polinomi G[X] a coeficients en Fd tenint per a arrels, 2..., d-1, llavors el codi és de distància mínima de. G[X] és el producte de polinomis cyclotomics. El codi BCH o el codi de Reed-Solomon utilitza aquesta tècnica per a construir codis perfectes. Si k és l'enter tal que n - k és igual al grau de G[X], llavors l'aplicació φ associa amb el missatge M[X] el polinomi M[X].Xk - R[X] on R[X] és el residu de la divisió euclidiana de M[X].Xk per G[X]. Els detalls i demostracions es donen a l'article codi cíclic.

Referències

[modifica]
  1. N. Bourbaki Algèbre commutative. Chapitre 5 Hermann 1964
  2. Richard Dedekind, Lechbuch des Algebra 1871.
  3. Heinrich Weber, Lechbuch der Algebra 1895.
  4. Ferdinand Georg Frobenius, Sur le caractère du groupe, Académie de Berlin, 1896.
  5. Leonard Dickson, Linear Groups With an Exposition of the Galois Field Theory, 1901.
  6. Carl Friedrich Gauss, Disquisitiones Arithmeticae, 1801.
  7. Claude Shannon A mathematical theory of communication Bell System Technical Journal, vol. 27, pp. 379-423 i 623-656, juliol i octubre del 1948.
  8. Claude Shannon Communication Theory of Secrecy Systems Bell System Technical Journal, Vol 28, pp. 656-715, Oct 1949
  9. Michael Rabin, Probabilistic Algorithm for Testing Primality J. Number Th. 12, 128-138, 1980
  10. Richard Hamming Error-detecting and error-correcting codes Bell Syst. Tech. J. 29 pp 147 à 160 1950
  11. R. C. Bose and D. K. Ray-Chaudhuri On a class of error-. correcting. binary group codes Inform. Control, vol. 3, pp. 68-79, Mars 1960
  12. A. Hocquenghem Codes correcteurs d'erreurs Chiffre 1959
  13. I. Reed G. Solomon Polynomial codes over certain finite fields J. Soc. Indus. Appl Math Vol 8 n° 2 pp 300 à 304 1960
  14. V.D. Goppa Codes associated with divisors Problems of Information Transmission, 12(1):22--27, 1977
  15. Richard Dedekind Supplément XI des Leçons en théorie des nombres de Dirichlet 1894

Notes

[modifica]
  • N. Bourbaki Algèbre commutative. Chapitre 5 Hermann 1964
  • Samuel, Pierre. Théorie algébrique des nombres. 
  • Serre, Jean-Pierre. Cours d'arithmétique (en francès). 
  • G. Heuzé Sur les corps finis Mathématiques et Sciences Humaines 1974
  • A. Warusfel Structures algébriques finies Hachette Université 1971

Enllaços externs

[modifica]