The equivalent condition for GRL codes to be MDS, AMDS or self-dual

Résumé Technique : Conditions d'Équivalence pour que les Codes GRL soient Non-GRS MDS, AMDS ou Auto-duaux

Énoncé du Problème
Les codes Maximum Distance Separable (MDS) et Almost MDS (AMDS), ainsi que les codes auto-duaux, possèdent des propriétés algébriques significatives et sont largement appliqués dans les systèmes de communication, le stockage de données, le codage quantique et la cryptographie. Bien que les codes de Reed-Solomon (RS) soient une classe bien connue de codes MDS, la construction de codes qui ne sont pas équivalents aux codes RS (non-RS) demeure un domaine de recherche critique pour élargir la diversité des familles de codes disponibles. Des travaux antérieurs par Roth et Lempel [20], puis par Wu et al. [21] et [22], ont construit des classes spécifiques de codes MDS non-RS en augmentant la matrice génératrice des codes RS avec deux ou trois colonnes supplémentaires. Cet article répond à la nécessité de généraliser davantage ces constructions et d'établir des conditions algébriques précises sous lesquelles ces codes généralisés (et leurs duaux) présentent des propriétés MDS, AMDS ou auto-duales sans être équivalents aux codes RS.

Méthodologie
Les auteurs introduisent une classe de codes Generalized Roth-Lempel (GRL), notée $GRL_k(\alpha, v, A_{l \times l})$, définie sur un corps fini $F_q$. Cette construction généralise les modèles précédents en remplaçant les matrices d'augmentation spécifiques utilisées dans [21] et [22] par une matrice arbitraire inversible $A_{l \times l} \in GL_l(F_q)$. Plus précisément, l'article se concentre sur le cas où $l=3$, noté $GRL_k(\alpha, v, A_{3 \times 3})$.

La méthodologie emploie les approches techniques suivantes :

1. Analyse de la Matrice Génératrice : Les auteurs définissent la matrice génératrice $G_4$ pour le code $GRL_k(\alpha, v, A_{3 \times 3})$, qui consiste en une structure de type Vandermonde standard augmentée de trois colonnes dérivées de la matrice $A_{3 \times 3}$.
2. Vérification Non-RS : Pour prouver que les codes sont non-RS, les auteurs utilisent le Lemme 5 (une caractérisation des codes RS via les entrées de la matrice génératrice) et démontrent que la structure spécifique des colonnes augmentées empêche le code de satisfaire les conditions nécessaires à l'équivalence RS lorsque $k > 3$.
3. Conditions MDS et AMDS : En utilisant le Lemme 6 (qui stipule qu'un code $[n, k]$ est MDS si et seulement si toute $k$ colonnes de sa matrice génératrice sont linéairement indépendantes), les auteurs analysent les déterminants de toutes les sous-matrices $k \times k$ possibles formées par la matrice génératrice. Cela implique une analyse de cas approfondie concernant l'inclusion des colonnes augmentées ($u_1, u_2, u_3$) dans les sous-matrices.
4. Construction de la Matrice de Contrôle de Parité : Pour l'analyse de l'auto-dualité, les auteurs dérivent une matrice de contrôle de parité explicite $H_5$ pour le code GRL. Ils utilisent le Lemme 4 (propriétés des sommes de puissances d'éléments de corps pondérées par des différences inverses) pour vérifier la condition d'orthogonalité $G H^T = 0$.
5. Critères d'Auto-dualité : La condition pour l'auto-dualité ($C = C^\perp$) est établie en exigeant que la matrice génératrice et la matrice de contrôle de parité engendrent le même espace, ce qui conduit à des contraintes spécifiques sur le vecteur $v$ et la matrice $A_{3 \times 3}$.

Contributions Clés et Résultats

1. Propriété Non-RS : Le Théorème 7 établit que pour $k > 3$, le code $GRL_k(\alpha, v, A_{3 \times 3})$ est strictement non-GRS (Generalized Reed-Solomon), quel que soit le choix des paramètres, à condition que $A_{3 \times 3} \in GL_3(F_q)$.

2. Conditions d'Équivalence pour MDS Non-RS : Le Théorème 8 fournit les conditions nécessaires et suffisantes pour que $GRL_k(\alpha, v, A_{3 \times 3})$ soit MDS. Ces conditions sont exprimées sous forme d'inégalités impliquant des sommes de produits des points d'évaluation $\alpha_i$ et des entrées de $A_{3 \times 3}$. Plus précisément, pour tout sous-ensemble de taille $k-1$ ou $k-2$, certaines expressions polynomiales impliquant les entrées de la matrice ne doivent pas s'annuler.

   • Le Corollaire 10 et l'Exemple 11 illustrent ces conditions avec une forme de matrice spécifique et un exemple concret sur $F_{11}$, produisant un code $[8, 4, 5]$.

3. Conditions d'Équivalence pour les Duaux AMDS : Le Théorème 12 détermine les conditions sous lesquelles le code dual $GRL_k^\perp(\alpha, v, A_{3 \times 3})$ est AMDS. Cela nécessite que toute $k-1$ colonnes de la matrice génératrice soient linéairement indépendantes, tandis qu'au moins un ensemble de $k$ colonnes est dépendant. Le théorème liste six cas spécifiques impliquant les entrées de $A_{3 \times 3}$ et les sommes de $\alpha_i$.

   • Le Corollaire 13 et l'Exemple 14 fournissent une instanciation spécifique sur $F_7$, résultant en un code $[8, 4, 4]$.

4. Matrice de Contrôle de Parité et Auto-dualité : Le Théorème 16 construit la matrice de contrôle de parité $H_5$ pour le code GRL. S'appuyant sur cela, le Théorème 17 fournit la condition d'équivalence pour que le code soit auto-dual non-RS. Les conditions exigent :

   • $n + 3 = 2k$ (contrainte de dimension).
   • Le vecteur $v$ doit être proportionnel au vecteur des différences inverses $u$ (c'est-à-dire $v_i = \lambda u_i$).
   • La matrice $A_{3 \times 3}$ doit satisfaire une relation quadratique spécifique impliquant les sommes de $\alpha_i$ et $\alpha_i^2$.
   • Les Exemples 18 et 19 démontrent la construction de tels codes auto-duaux sur $F_{13}$ et $F_{19}$, respectivement. Notamment, l'Exemple 19 souligne que des codes GRL auto-duaux peuvent être construits pour $q \equiv 3 \pmod 4$, un cas où les constructions auto-duales précédentes dans [22] étaient limitées.

Signification
L'article affirme généraliser les résultats trouvés dans [21] et [22] en remplaçant les matrices d'augmentation spécifiques par une matrice inversible générale $A_{3 \times 3}$. La principale signification réside dans la fourniture d'un cadre unifié pour déterminer quand ces codes généralisés possèdent des propriétés de distance optimales (MDS/AMDS) ou l'auto-dualité. Les auteurs notent explicitement que leurs résultats récupèrent les théorèmes de [21] comme cas particuliers. De plus, la construction de codes auto-duaux pour $q \equiv 3 \pmod 4$ (Exemple 19) étend l'applicabilité de tels codes au-delà des contraintes de la littérature précédente. L'article conclut que ces conditions d'équivalence permettent la construction systématique de codes non-RS possédant des propriétés désirables pour les applications en communications et en cryptographie.