Construction of MRD Codes Based on Circular-Shift Operations

Resumen Técnico: Construcción de Códigos MRD Basados en Desplazamiento Circular

1. Problema y Motivación

Los códigos de distancia de rango máximo (MRD, por sus siglas en inglés) son fundamentales en criptografía, almacenamiento distribuido y códigos de subespacio. La familia más conocida de códigos MRD, los códigos de Gabidulin (y sus variantes "twisted"), se construyen tradicionalmente utilizando aritmética sobre campos de extensión grandes ($\mathbb{F}_{q^N}$).

Limitaciones actuales:

• Complejidad de implementación: A medida que aumenta el parámetro $N$ (tamaño de la matriz o dimensión del campo), la aritmética en $\mathbb{F}_{q^N}$ se vuelve computacionalmente costosa y difícil de implementar en hardware o software eficiente.
• Selección de parámetros: La necesidad de operar en campos grandes limita la flexibilidad en la selección de parámetros para aplicaciones prácticas.
• Transformación de bases: La conversión eficiente de vectores sobre $\mathbb{F}_{q^N}$ a matrices sobre $\mathbb{F}_q$ requiere una selección cuidadosa de bases que no siempre está bien investigada.

El objetivo de este trabajo es superar estas limitaciones proponiendo una construcción de códigos MRD que opere exclusivamente sobre el campo base $\mathbb{F}_q$, evitando la aritmética de campos de extensión.

2. Metodología Propuesta

Los autores introducen una nueva clase de códigos MRD denominados códigos MRD basados en desplazamiento circular. La metodología se basa en las siguientes ideas clave:

• Parámetros Definidos:

  • $q$: Un número primo.
  • $L$: Un entero positivo tal que $\text{mcd}(q, L) = 1$.
  • $m_L$: El orden multiplicativo de $q$ módulo $L$ (es decir, $q^{m_L} \equiv 1 \pmod L$).
  • $J$: La función totiente de Euler de $L$ (número de enteros menores que $L$ y coprimos con $L$).
  • Se asume $n \le m_L \le J$.

• Mecanismo de Construcción:
  En lugar de evaluar polinomios linealizados sobre $\mathbb{F}_{q^J}$, la construcción utiliza matrices de permutación cíclica ($C_L$) y operaciones de desplazamiento circular sobre vectores en $\mathbb{F}_q$.
  El código $C$ se define como:
  $$C = \{ \Delta(m(I_k \otimes P) \Psi_{k \times n} (I_n \otimes Q)) : m \in \mathbb{F}_q^{Jk} \}$$
  Donde:

  • $\Psi_{k \times n}$ es una matriz de bloques compuesta por matrices de permutación cíclica $C_L^{q^s l_i}$.
  • $P$ y $Q$ son matrices diseñadas específicamente sobre $\mathbb{F}_q$ (denominadas $G_L$ y $H_L$) que garantizan la propiedad MRD.
  • $\Delta$ es un mapeo que convierte un vector fila en una matriz $J \times n$.

• Caracterización Polinomial:
  Los autores caracterizan tanto los nuevos códigos como los códigos de Gabidulin utilizando un conjunto de polinomios $q$-linealizados definidos sobre el espacio vectorial de filas $\mathbb{F}_q^N$, en lugar de sobre el campo de extensión $\mathbb{F}_{q^N}$. Esto permite comparar directamente las evaluaciones de los polinomios de ambos tipos de códigos.

3. Contribuciones Clave

1. Construcción Eficiente sin Campos de Extensión:
   Se presenta una construcción de códigos MRD $(J \times n, q^{Jk}, d)$ que opera enteramente sobre $\mathbb{F}_q$. Esto elimina la necesidad de aritmética en $\mathbb{F}_{q^J}$, simplificando drásticamente la implementación.

2. Análisis de Diferencia y Conexión con Códigos de Gabidulin:

   • Caso $J \neq m_L$: Se demuestra que, bajo ciertos parámetros, los códigos propuestos son distintos de cualquier código de Gabidulin o código de Gabidulin "twisted" (retorcido). Esto expande el espacio de códigos MRD conocidos.
   • Caso $J = m_L$: Se prueba que los códigos propuestos coinciden con los códigos de Gabidulin. Sin embargo, la construcción propuesta ofrece una nueva perspectiva: permite construir códigos de Gabidulin usando solo aritmética en $\mathbb{F}_q$, evitando la complejidad de $\mathbb{F}_{q^J}$.

3. Generalización de Códigos de Gabidulin:
   Bajo selecciones específicas de las matrices $P$ y $Q$, se demuestra que los códigos propuestos son equivalentes a una generalización de los códigos de Gabidulin obtenida mediante la suma y concatenación de varios códigos de Gabidulin de menor dimensión $(m_L \times n, q^{m_L k}, d)$. Esta generalización no había sido explorada previamente en la literatura.

4. Análisis de Complejidad Computacional:
   Se realiza un análisis teórico de la complejidad para generar un símbolo de código (codeword) en el caso $q=2$ y $L$ primo:

   • Códigos Propuestos: Requieren $O(nkL)$ operaciones XOR.
   • Códigos de Gabidulin (Construcción Tradicional): Requieren $O(nkL^2)$ operaciones XOR debido a las multiplicaciones en el campo de extensión.

4. Resultados Principales

• Propiedad MRD: Se demuestra teóricamente que la construcción propuesta satisface el límite de Singleton, garantizando que la distancia de rango mínima es $d = n - k + 1$.
• Ejemplos Numéricos: Se proporcionan ejemplos concretos (ej. $q=2, L=7$) que ilustran la construcción de los códigos y verifican que los no nulos tienen rango completo.
• Comparación de Rendimiento:
  • Para generar un código de Gabidulin tradicional, se necesitan multiplicaciones en $\mathbb{F}_{2^{L-1}}$, lo que cuesta $O(L^2)$ operaciones XOR por multiplicación.
  • Los códigos basados en desplazamiento circular solo requieren sumas (XOR) y desplazamientos cíclicos, logrando una complejidad lineal en $L$ en lugar de cuadrática.
  • Resultado: La construcción propuesta es significativamente más eficiente computacionalmente para parámetros grandes.

5. Significado e Impacto

• Eficiencia Práctica: La reducción de la complejidad de $O(nkL^2)$ a $O(nkL)$ hace que los códigos MRD sean viables para aplicaciones de alta velocidad y bajo consumo de energía, como en sistemas de almacenamiento distribuido y redes de codificación lineal.
• Nueva Perspectiva Teórica: Al caracterizar los códigos de Gabidulin a través de polinomios linealizados sobre espacios vectoriales en lugar de campos de extensión, los autores revelan conexiones profundas y nuevas formas de construir estos códigos.
• Flexibilidad de Parámetros: La independencia de campos de extensión grandes permite una selección de parámetros más flexible, superando las restricciones de implementación de los métodos tradicionales.
• Futuro: El trabajo abre la puerta a la investigación de algoritmos de decodificación eficientes para estos nuevos códigos y su aplicación en códigos de subespacio.

En conclusión, este artículo propone una alternativa robusta y eficiente a los códigos MRD tradicionales, logrando la misma capacidad de corrección de errores con una carga computacional significativamente menor al eliminar la dependencia de la aritmética de campos de extensión.