Descodificación por localización y el algoritmo de Berlekamp-Massey-Sakata

Ponente(s): Juan Jacobo Simón Pinero, José Joaquín Bernal Buitrago

El algoritmo de Berlekamp-Massey-Sakata (aBMS) es una generalización a dos variables del algoritmo de Berlekamp-Massey que consiste en, dada una sucesión periódica en un cuerpo finito, encontrar la fórmula de recurrencia y el polinomio que la generan. En el caso de dos variables, consiste en encontrar una base de Groebner para determinar el sistema de recurrencias lineales. Existen muchos métodos de descodificación basados en este algoritmo; entre otros, la descodificación por localizador que se aplica en códigos abelianos y algebraico-geométricos. En esta plática, vamos a mostrar un panorama sobre su funcionamiento y comentaremos algunas de nuestras aportaciones en un trabajo conjunto con José Joaquín Bernal. Entre otras, cabe mencionar la siguiente: para una tabla de orden (o bien, doblemente periódica) $r_1\times r_2$, obtenida por una fórmula polinomial (por síndromes) que tiene $t\leq \min\{\lfloor\frac{r_1}{2}\rfloor, \lfloor\frac{r_2}{2}\rfloor\}$ términos, existe un conjunto mínimo de índices sobre el que basta ejecutar el algoritmo para obtener la base de Groebner, garantizando que el proceso terminará en, a lo más, $\frac{t^2+7t}{2}-1$ pasos.