Construction of cyclic codes with large minimum distance from power functions over odd characteristic finite fields

Resumen Técnico: Construcción de Códigos Cíclicos con Gran Distancia Mínima a partir de Funciones de Potencia sobre Campos Finitos de Característica Impar

Planteamiento del Problema
Los códigos cíclicos con dimensiones que exceden la mitad de la longitud del código ($k > v/2$) y distancias mínimas superiores a la raíz cuadrada de la longitud del código ($d > \sqrt{v}$) son altamente deseables para aplicaciones que requieren una alta eficiencia de transmisión y una fuerte corrección de errores, tales como sistemas de comunicación, criptografía post-cuántica y radar. Si bien se ha logrado un progreso significativo en la construcción de códigos sobre campos binarios (característica 2), la construcción de códigos cíclicos no binarios utilizando funciones de potencia con uniformidad diferencial conocida sobre campos de característica impar ha recibido comparativamente menos atención. Este artículo aborda la brecha en la construcción de familias infinitas de códigos $q$-arios (donde $q$ es una potencia de un primo impar) que logran parámetros favorables, específicamente apuntando a dimensiones $k > (q^m - 1)/2$ y distancias mínimas $d > \sqrt{q^m - 1}$.

Metodología
Los autores emplean el enfoque de secuencia de traza para construir códigos cíclicos. La metodología involucra los siguientes pasos:

1. Definición de la Secuencia: Para un campo finito dado $\mathbb{F}_{q^m}$ y un elemento primitivo $\alpha$, se define una secuencia $s_\infty = (s_t)_{t \ge 0}$ mediante la función de traza: $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, donde $F(x)$ es una función de potencia seleccionada sobre $\mathbb{F}_{q^m}$.
2. Determinación del Polinomio Generador: El código cíclico $C_F$ es generado por el polinomio mínimo $M_s(x)$ de la secuencia $s_\infty$. La dimensión del código está determinada por la extensión lineal ($L_s$) de la secuencia, la cual corresponde al número de coeficientes no nulos en la expansión de la traza de la secuencia.
3. Selección de la Función de Potencia: El artículo selecciona monomios específicos $F(x) = x^d$ con uniformidad diferencial conocida sobre $\mathbb{F}_{q^m}$ (donde $q$ es impar). Los criterios de selección dependen de la paridad de $m$ y la estructura específica del exponente $d$.
4. Análisis Algebraico:
   • Extensión Lineal: Los autores utilizan expansiones $q$-ádicas, el Teorema de Lucas y propiedades de los cosets ciclotómicos para expandir la función de traza e identificar los términos no nulos. Esto permite el cálculo exacto de la extensión lineal $L_s$ y la construcción del polinomio generador $M_s(x)$.
   • Límites de la Distancia Mínima: Los límites inferiores de la distancia mínima $d$ se establecen utilizando la cota BCH y la cota de Hartmann-Tzeng. Esto implica identificar enteros consecutivos o conjuntos específicos dentro del conjunto definitorio (las raíces del polinomio generador).
   • Distancias Exactas: Para casos específicos, los autores construyen palabras de código explícitas de pesos específicos para determinar la distancia mínima exacta, relacionando frecuentemente los códigos construidos con códigos BCH primitivos conocidos.

Contribuciones Clave y Resultados
El artículo presenta varias familias infinitas de códigos $q$-arios de longitud $v = q^m - 1$ con dimensiones que exceden $v/2$. Las construcciones y resultados específicos se categorizan según las funciones de potencia utilizadas:

1. Códigos Ternarios de $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ impar):

   • Construidos sobre $\mathbb{F}_{3^m}$.
   • La extensión lineal es $3m + N_3(m)$, resultando en una dimensión de $3^m - 1 - 3m - N_3(m)$.
   • La distancia mínima $d$ satisface $3 \le d \le 8$.
   • Ejemplo: Para $m=5$, se obtiene un código $[242, 226, 5]$, el cual es casi óptimo.

2. Códigos $p$-arios de $x^{p^{m/2} + 2}$ ($m$ par, $p$ impar):

   • Construidos sobre $\mathbb{F}_{p^m}$.
   • La extensión lineal depende de $p$ y $m$ (por ejemplo, $N_p(m) + 5m/2$ para $p=3$).
   • Se establecen límites de distancia mínima: $d \ge 3$ (para $p=3$), $d \ge 5$ (para $p \ge 5, p \nmid m$), y $d \ge 4$ (para $p \ge 5, p \mid m$).
   • Se determinan distancias exactas para casos específicos (por ejemplo, $d=5$ para $p=5, p \nmid m$).

3. Códigos de $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$ impar):

   • Esta construcción aborda un caso específico donde el exponente es la suma de una serie geométrica.
   • El artículo deriva una fórmula general para la extensión lineal que involucra sumas de términos $N_p(k)$.
   • Significado: Esta construcción resuelve parcialmente el Problema Abierto 5.31 planteado por Ding [35], el cual concernía a la dimensión y el polinomio generador de códigos cíclicos para $t = (m+1)/2$ con $m$ impar.
   • Se proporcionan límites inferiores para $d$, que oscilan entre 2 y $2^{t-2} + 2$ dependiendo de $q$ y $t$.

4. Códigos Ternarios de $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ impar):

   • Utiliza un monomio que es una función Perfectamente No Lineal (PN) o 4-uniform dependiendo de $m$.
   • La extensión lineal se calcula como $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$.
   • Se establecen límites de distancia mínima, con $d \ge 8$ bajo condiciones específicas de divisibilidad.

5. Códigos $p$-arios de $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$):

   • Generaliza resultados binarios previos a la caracteristica impar.
   • La extensión lineal se deriva utilizando expansiones $p$-ádicas y definiciones de conjuntos específicos ($\hat{\Gamma}(t)$).
   • Se muestra que los límites inferiores de la distancia mínima son significativamente mejores que la raíz cuadrada de la longitud del código en muchos casos (por ejemplo, $d \ge p^h + 2$).
   • Se determinan distancias exactas para casos donde $h \mid m$, mostrando que el código es equivalente a un código BCH primitivo de sentido estrecho con distancia diseñada $p^h + 1$.

6. Códigos de $x^{2 \cdot p^{m/2} - 1}$ y $x^{p^{2h} - p^h + 1}$:

   • Estas secciones manejan $m$ par e impar respectivamente con exponentes específicos.
   • Los autores derivan expresiones complejas para la extensión lineal y los polinomios mínimos.
   • El Teorema 11 y el Teorema 13 demuestran que los límites inferiores de la distancia mínima para estas familias son a menudo significativamente superiores al límite de la raíz cuadrada ($\sqrt{v}$).

Significado y Reivindicaciones
El artículo afirma extender el marco binario de Ding y Zhou [14] a un entorno no binario. La principal significación radica en:

• Mejora de Parámetros: Los códigos construidos logran dimensiones $k > (q^m - 1)/2$ y distancias mínimas $d > \sqrt{q^m - 1}$, equilibrando eficazmente la tasa del código y la capacidad de corrección de errores.
• Resolución de Problemas Abiertos: El trabajo resuelve parcialmente el Problema Abierto 5.31 de Ding [35] referente al código cíclico ternario definido por $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ con $m$ impar.
• Optimalidad: Varios de los códigos construidos (y sus duales) se identifican como óptimos o casi óptimos al compararlos con la Base de Datos de los mejores códigos lineales conocidos [47].
• Avance Teórico: El artículo proporciona fórmulas explícitas para la extensión lineal y los polinomios generadores para familias infinitas de códigos, utilizando herramientas avanzadas de teoría de números (cosets ciclotómicos, expansiones $p$-ádicas, Teorema de Lucas) para manejar las complejidades de los campos de característica impar.

Los autores concluyen que estas construcciones proporcionan una fuente rica de códigos adecuados para aplicaciones exigentes y sugieren que la exploración adicional de las funciones de potencia sobre campos de característica impar podría producir familias más óptimas. También señalan el potencial de estos códigos para ser utilizados en la construcción de códigos de corrección de errores cuánticos mediante la construcción CSS.