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

Résumé Technique : Construction de codes cycliques à grande distance minimale à partir de fonctions de puissance sur des corps finis de caractéristique impaire

Énoncé du problème
Les codes cycliques dont les dimensions dépassent la moitié de la longueur du code ($k > v/2$) et dont les distances minimales sont supérieures à la racine carrée de la longueur du code ($d > \sqrt{v}$) sont hautement désirables pour des applications exigeant une grande efficacité de transmission et une correction d'erreurs robuste, telles que les systèmes de communication, la cryptographie post-quantique et le radar. Bien que des progrès significatifs aient été réalisés pour la construction de codes binaires (caractéristique 2), la construction de codes cycliques non binaires utilisant des fonctions de puissance avec une uniformité différentielle connue sur des corps finis de caractéristique impaire a reçu comparativement moins d'attention. Cet article comble la lacune dans la construction de familles infinies de codes $q$-aires (où $q$ est une puissance d'un nombre premier impair) qui atteignent des paramètres favorables, ciblant spécifiquement des dimensions $k > (q^m - 1)/2$ et des distances minimales $d > \sqrt{q^m - 1}$.

Méthodologie
Les auteurs emploient l'approche de la séquence de trace pour construire des codes cycliques. La méthodologie comprend les étapes suivantes :

1. Définition de la séquence : Pour un corps fini $\mathbb{F}_{q^m}$ donné et un élément primitif $\alpha$, une séquence $s_\infty = (s_t)_{t \ge 0}$ est définie via la fonction de trace : $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, où $F(x)$ est une fonction de puissance sélectionnée sur $\mathbb{F}_{q^m}$.
2. Détermination du polynôme générateur : Le code cyclique $C_F$ est généré par le polynôme minimal $M_s(x)$ de la séquence $s_\infty$. La dimension du code est déterminée par l'espace linéaire ($L_s$) de la séquence, ce qui correspond au nombre de coefficients non nuls dans l'expansion de la trace de la séquence.
3. Sélection de la fonction de puissance : L'article sélectionne des monômes spécifiques $F(x) = x^d$ avec une uniformité différentielle connue sur $\mathbb{F}_{q^m}$ (où $q$ est impair). Les critères de sélection dépendent de la parité de $m$ et de la structure spécifique de l'exposant $d$.
4. Analyse algébrique :
   • Espace linéaire : Les auteurs utilisent les développements $q$-adiques, le théorème de Lucas et les propriétés des cosets cyclotomiques pour développer la fonction de trace et identifier les termes non nuls. Cela permet le calcul exact de l'espace linéaire $L_s$ et la construction du polynôme générateur $M_s(x)$.
   • Bornes de distance minimale : Les bornes inférieures sur la distance minimale $d$ sont établies en utilisant la borne BCH et la borne de Hartmann-Tzeng. Cela implique l'identification d'entiers consécutifs ou d'ensembles spécifiques au sein de l'ensemble définissant (les racines du polynôme générateur).
   • Distances exactes : Pour des cas spécifiques, les auteurs construisent des mots explicites de poids spécifiques pour déterminer la distance minimale exacte, reliant souvent les codes construits à des codes BCH primitifs connus.

Contributions clés et résultats
L'article présente plusieurs familles infinies de codes cycliques $q$-aires de longueur $v = q^m - 1$ avec des dimensions dépassant $v/2$. Les constructions et résultats spécifiques sont catégorisés par les fonctions de puissance utilisées :

1. Codes ternaires à partir de $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ impair) :

   • Construits sur $\mathbb{F}_{3^m}$.
   • L'espace linéaire est $3m + N_3(m)$, produisant une dimension $3^m - 1 - 3m - N_3(m)$.
   • La distance minimale $d$ satisfait $3 \le d \le 8$.
   • Exemple : Pour $m=5$, un code $[242, 226, 5]$ est obtenu, ce qui est presque optimal.

2. Codes $p$-aires à partir de $x^{p^{m/2} + 2}$ ($m$ pair, $p$ impair) :

   • Construits sur $\mathbb{F}_{p^m}$.
   • L'espace linéaire dépend de $p$ et $m$ (par exemple, $N_p(m) + 5m/2$ pour $p=3$).
   • Des bornes de distance minimale sont établies : $d \ge 3$ (pour $p=3$), $d \ge 5$ (pour $p \ge 5, p \nmid m$), et $d \ge 4$ (pour $p \ge 5, p \mid m$).
   • Les distances exactes sont déterminées pour des cas spécifiques (par exemple, $d=5$ pour $p=5, p \nmid m$).

3. Codes à partir de $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$ impair) :

   • Cette construction traite un cas spécifique où l'exposant est une somme de série géométrique.
   • L'article dérive une formule générale pour l'espace linéaire impliquant des sommes de termes $N_p(k)$.
   • Signification : Cette construction résout partiellement le Problème Ouvert 5.31 posé par Ding [35], qui concernait la dimension et le polynôme générateur des codes cycliques pour $t = (m+1)/2$ avec $m$ impair.
   • Des bornes inférieures sur $d$ sont fournies, allant de 2 à $2^{t-2} + 2$ selon $q$ et $t$.

4. Codes ternaires à partir de $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ impair) :

   • Utilise un monôme qui est une fonction de type Perfect Nonlinear (PN) ou 4-uniforme selon $m$.
   • L'espace linéaire est calculé comme $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$.
   • Des bornes de distance minimale sont établies, avec $d \ge 8$ sous des conditions de divisibilité spécifiques.

5. Codes $p$-aires à partir de $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$) :

   • Généralise les résultats binaires précédents au cas de la caractéristique impaire.
   • L'espace linéaire est dérivé en utilisant les développements $p$-adiques et des définitions d'ensembles spécifiques ($\hat{\Gamma}(t)$).
   • Les bornes inférieures de la distance minimale sont montrées comme étant significativement meilleures que la racine carrée de la longueur du code dans de nombreux cas (par exemple, $d \ge p^h + 2$).
   • Les distances exactes sont déterminées pour les cas où $h \mid m$, montrant que le code est équivalent à un code BCH primitif à sens étroit avec une distance conçue de $p^h + 1$.

6. Codes à partir de $x^{2 \cdot p^{m/2} - 1}$ et $x^{p^{2h} - p^h + 1}$ :

   • Ces sections traitent respectivement des cas $m$ pair et $m$ impair avec des exposants spécifiques.
   • Les auteurs dérivent des expressions complexes pour l'espace linéaire et les polynômes minimaux.
   • Le Théorème 11 et le Théorème 13 démontrent que les bornes inférieures de la distance minimale pour ces familles sont souvent nettement supérieures à la borne de la racine carrée ($\sqrt{v}$).

Signification et affirmations
L'article affirme étendre le cadre binaire de Ding et Zhou [14] à un cadre non binaire. La principale signification réside dans :

• Amélioration des paramètres : Les codes construits atteignent des dimensions $k > (q^m - 1)/2$ et des distances minimales $d > \sqrt{q^m - 1}$, équilibrant efficacement le taux du code et la capacité de correction d'erreurs.
• Résolution de problèmes ouverts : Le travail résout partiellement le Problème Ouvert 5.31 de Ding [35] concernant le code cyclique ternaire défini par $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ avec $m$ impair.
• Optimalité : Plusieurs codes construits (et leurs duals) sont identifiés comme optimaux ou presque optimaux par rapport à la base de données des meilleurs codes linéaires connus [47].
• Avancement théorique : L'article fournit des formules explicites pour l'espace linéaire et les polynômes générateurs pour des familles infinies de codes, en utilisant des outils de théorie des nombres avancés (cosets cyclotomiques, développements $p$-adiques, théorème de Lucas) pour gérer les complexités des corps de caractéristique impaire.

Les auteurs concluent que ces constructions fournissent une source riche de codes adaptés à des applications exigeantes et suggèrent qu'une exploration plus approfondie des fonctions de puissance sur les corps de caractéristique impaire pourrait engendrer des familles plus optimales. Ils notent également le potentiel de ces codes pour la construction de codes correcteurs d'erreurs quantiques via la construction CSS.