Aula 8 (Facultad de Matemáticas), 13.00 h.
En esta charla exploraremos el nexo de unión que existe entre la estructura
algebraica de un código lineal y el proceso de descodificación completa. El
método de descodificación completa es un problema NP-completo, incluso si
consentimos el pre-procesamiento de los datos. Abordaremos este problema con
distintas técnicas algebraicas.
La Teoría de Códigos correctores busca la forma de transmitir información
de manera fiable y eficiente a través de canales afectados de ruido y que, por
lo tanto, pueden distorsionar la información. En la vida cotidiana utilizamos
los códigos correctores de forma frecuente. Los ejemplos más comunes son el
código de barras, el ISBN que nos facilitan la identificación de libros y
revistas, los códigos ASCII utilizado en ordenadores; o los códigos correctores
que se emplean en cualquier dispositivo que nos permita almacenar o transmitir
información, como los CD, los DVD, los chips que aparecen en nuestras tarjetas
de crédito, en el carnet de conducir, en el DNI, etc.
El proceso de descodificación (en el que se intenta recuperar el mensaje
original) es la parte más importante y delicada del proceso de comunicación con
códigos. La descodificación completa consiste en crear un sistema que asigne,
para cualquier palabra recibida en la que se han cometido errores, la palabra
del código más cercana.
Una de las principales aplicaciones de nuestro problema es definir el
conjunto de palabras de soporte minimal de un código lineal, lo que está
relacionado con la descripción de algoritmos de descodificación por gradiente
(de gran relevancia en la esteganografía, disciplina que estudia los métodos de
encubrir mensajes) y con esquemas o protocolos para compartir secretos en
criptografía.
El fundamento matemático se basa en introducir un ideal binomial asociado a
cualquier código lineal de forma que los binomios de la base de Gröbner de
dicho ideal respecto de un orden graduado inducen un conjunto de prueba o
test-set que nos proporciona un método de descodificación completo.
Para el caso binario muchos de estos resultados ya se conocían. Sin
embargo, presentaremos extensiones de los algoritmos conocidos con los que
podemos calcular, sin aumento del coste computacional, parámetros adicionales
del código como el conjunto de palabras líderes, su distribución de pesos o el
radio de recubrimiento y de Newton. La complejidad, próxima a la óptima, puede
ser mejorada con diversas técnicas. Por ejemplo, podemos hacer uso de la teoría
de descomposición de matroides representables para dividir nuestros algoritmos
en sub-algoritmos independientes autorizando la paralelización de los mismos.
Para el caso de códigos lineales arbitrarios los algoritmos que presentaremos
son novedosos.
Irene Márque Corbella nacida en Tenerife, se licenció en Matemáticas por la Universidad de La
Laguna en 2008. En el curso 2008-2009, gracias a una beca internacional de la
Fundación la Caixa para estudios de post-grado, realizó un máster profesional
en la especialidad de criptografía, protocolos y redes en la Universidad
Diderot - París VII. Tras obtener una Beca Nacional FPI y la realización del
Programa de doctorado en la Universidad de Valladolid, en el Departamento de
Álgebra, Geometría y Topología, actualmente está trabajando en su tesis
doctoral bajo la dirección de los profesores Antonio Campillo López y Edgar
Martínez-Moro. Forma parte del grupo SINGACOM y del Instituto Universitario de
Matemáticas de la Universidad de Valladolid (ImUVa).
0 comentarios:
Publicar un comentario