February 2005 
PROGRESS| How to reduce failures in data transmission? Maths give the answer


The mathematical concept of semigroup is present in many daily life processes. One of them is the data transmission through geometric codes, where they help to explain how data is transmitted and, if errors occur, how they are corrected. In this article, Maria Bras-Amoros, of the Department of Computer Science, analyses the role of semigroups in the study of these problems.

Article: Bras-Amoros, M. "Acute semigroups, the order bound on the minimum distance, and the Feng-Rao improvements". IEEE Transactions on Information Theory, 50 (6): 1282-1289; 2004.

Els semigrups són un objecte matemàtic que trobem en la vida de cada dia. L'exemple més quotidià és el dels caixers automàtics. Qui més qui menys tothom s'ha trobat davant d'un caixer automàtic amb la intenció de treure 30 euros i s'ha quedat amb les ganes. La senzilla explicació era que la màquina només dispensava bitllets de 20 i de 50.
Així, les úniques quantitats que ens deixaria treure aquest caixer (a part de 0), serien:



Això és un exemple de semigrup. Més formalment es defineix un semigrup com un conjunt infinit de números (enters i més grans o iguals que 0) de manera que contenen el zero i que sempre que sumem dues quantitats del conjunt n'obtenim una altra que també cau dins del conjunt. Altres exemples de semigrups serien {0, 25, 26, 27, 28, …}
o {0,4,5,8,9,10,12,13,14,15,16,…}.

Tot i la senzillesa de la definició de semigrup, el seu estudi és molt complex. Alguns dels problemes clàssics són:

-Trobar quants enters cauen fora del semigrup (llacunes).
-Trobar quin és el primer enter a partir del qual tots els següents pertanyen al semigrup (conductor).
-Comptar quants semigrups hi ha amb un número determinat de llacunes.
-Comptar quants semigrups hi ha amb un conductor determinat.
-Trobar un conjunt finit minimal dins del semigrup tal que tots els elements del semigrup es puguin expressar com a sumes repetides dels elements d'aquest conjunt finit.

A part de la subjectiva "bellesa matemàtica" dels semigrups, podem trobar-hi moltes aplicacions en diferents camps. Els treballs referenciats tracten les aplicacions que els semigrups tenen en l'anàlisi dels codis de canal. Aquests codis s'utilitzen per poder detectar i corregir els errors que es poden produir en la trasmissió d'informació a través de canals defectuosos que distorsionin la informació que s'envia. Per exemple, els errors que produeix l'atmosfera en transmetre les fotos del satèl·lit Meteosat fins la Terra, o els errors deguts a les diferents interferències produïdes en una comunicació per telèfon mòbil, o els possibles errors en la lectura d'un CD.



El funcionament d'aquests codis consisteix en l'enviament, junt amb la informació original, d'una mica de redundància de manera que a partir de tot el que es rep poguem deduir el que realment s'ha transmès. L'exemple més simple seria afegir, per cada bit que s'envia, dues còpies iguals del mateix. Així si el bit original o alguna de les còpies es rep malament, podem corregir-lo a partir dels altres dos. Observem que en afegir redundància, d'una banda hi guanyem perquè millora la qualitat de la informació rebuda, però de l'altra hi perdem perquè hi ha un augment del cost d'enviament. En l'exemple de repetir bits, el cost es multiplica per tres.

Per controlar la capacitat de corregir errors, així com el cost d'enviar la informació codificada, es definieixen uns paràmetres relacionats amb el codi, quantificant el que anomenem capacitat correctora i dimensió. Per una família de codis molt important, els anomenats codis geomètrics, aquests paràmetres es poden controlar a partir de semigrups. En els treballs presentats es dedueixen certes propietats d'aquests codis i s'aprofundeix en l'estudi i la classificació de semigrups.

References:

Maria Bras-Amoros. Acute Semigroups, the Order Bound on the Minimum Distance and the Feng-Rao Improvements. IEEE Transactions on Information Theory. Vol 50, no. 6, pp. 1282-1289 (Juny 2004).

---. Improvements to Evaluation Codes and New Characterizations of Arf Semigroups. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. Lecture Notes in Computer Science, vol. 2643, Marc Fossorier, Tom Hoholdt, Alain Poli, pp. 204-215, ISSN: 0302-9743 (Maig 2003).

---. Addition behavior of a numerical semigroup. In the workshop "Algebraic Geometry and Information Theory" (AGCT-9), Centre International de Rencontres Mathématiques (CIRM). Luminy, France, Maig 2003.

---. Patterns on numerical semigroups. In Actas de los Encuentro de Álgebra Computacional y Aplicaciones. Santander, L. González-Vega and T. Recio, 53--58. Universidad de Cantabria, ISSN: 84-688-6988-04 (Juliol 2004).

Maria Bras-Amoros
Departament of Computer Studies
Universitat Autònoma de Barcelona

 

Universitat Autònoma de Barcelona
Àrea de Comunicació i de Promoció
Edifici A
08193 Bellaterra
(Cerdanyola del Vallès)
Tel.: +34 93 581 33 01
premsa.ciencia@uab.es
www.uab.es www.uab.es