Shortest LCD embeddings of binary, ternary and quaternary linear codes

Énoncé du problème
Les codes linéaires à dual complémentaire (codes LCD) constituent un domaine de recherche important en théorie des codes et en cryptographie, notamment en raison de leur résistance aux attaques par canaux auxiliaires et par injection de fautes. Bien qu'il soit connu que tout code linéaire sur $\mathbb{F}_q$ ($q \ge 4$) est équivalent à un code LCD, et que des résultats similaires existent pour $\mathbb{F}_{q^2}$, les bornes pour les distances minimales des codes LCD sur $\mathbb{F}_2$, $\mathbb{F}_3$ et les codes LCD hermitiens sur $\mathbb{F}_4$ demeurent inconnues pour de nombreuses longueurs et dimensions. Un défi central en théorie des codes consiste à déterminer la plus grande distance minimale pour une longueur et une dimension données. Cet article traite du problème spécifique de l'incorporation de codes linéaires arbitraires dans des codes LCD, en visant l'incorporation la plus « courte » (augmentation minimale de la longueur) et en utilisant cette méthode pour construire de nouveaux codes LCD optimales en distance.

Méthodologie
Les auteurs introduisent une approche systématique pour incorporer un code linéaire donné $C$ dans un code LCD $\tilde{C}$ en ajoutant le nombre minimum de colonnes à sa matrice génératrice. La méthodologie procède comme suit :

1. Fondement théorique : L'article établit que le nombre minimum de colonnes ($m$) requis pour incorporer un code $[n, k]$ dans un code LCD est exactement égal à la dimension $\ell$ du noyau (hull) de $C$ (où $\text{Hull}(C) = C \cap C^\perp$). Par conséquent, la longueur de l'incorporation LCD la plus courte est $n + \ell$.
2. Caractérisation structurelle : Les auteurs caractérisent la matrice génératrice d'une incorporation LCD la plus courte. Si $G$ est une matrice génératrice de $C$ décomposée en une partie générant le noyau, $G(\text{Hull}(C))$, et une partie restante $A$, alors une incorporation LCD la plus courte est générée par une matrice de la forme :
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   où $D$ est une matrice inversible de taille $\ell \times \ell$ et $C$ est une matrice arbitraire de taille $(k-\ell) \times \ell$. L'article prouve qu'ajouter une matrice inversible aux lignes correspondant au noyau et une matrice arbitraire aux lignes restantes produit toujours une incorporation LCD la plus courte.
3. Stratégie de construction : Les auteurs appliquent cette méthode d'incorporation à des codes linéaires connus étant optimaux en distance (spécifiquement des codes ternaires et quaternaires) qui ne sont pas eux-mêmes LCD. En calculant la dimension du noyau de ces codes existants et en ajoutant les colonnes nécessaires selon la structure dérivée, ils génèrent de nouveaux codes LCD.

Contributions clés et résultats
L'article fournit à la fois des bornes théoriques et des constructions concrètes :

• Résultats théoriques :

  • Prouve que la longueur de l'incorporation LCD la plus courte d'un code $[n, k]$ avec une dimension de noyau $\ell$ est $n + \ell$.
  • Caractérise toutes les formes possibles de matrices génératrices pour ces incorporations les plus courtes, montrant qu'elles sont équivalentes à l'ajout d'une matrice inversible aux lignes générant le noyau.
  • Démontre que la longueur de l'incorporation LCD la plus courte d'un code $C$ est identique à celle de son noyau, $\text{Hull}(C)$.

• Nouvelles constructions de codes :
  En utilisant la méthode d'incorporation LCD la plus courte sur des codes linéaires existants, les auteurs ont construit plusieurs nouveaux codes LCD avec des paramètres qui améliorent les distances minimales connues :

  • Codes LCD ternaires :
    • $[23, 4, 14]$ : Améliore la distance minimale connue de 13 à 14.
    • $[23, 5, 12]$ : Améliore la distance minimale connue de 11 à 12.
    • $[24, 6, 12]$ : Améliore la distance minimale connue de 11 à 12.
    • $[25, 5, 14]$ : Améliore la distance minimale connue de 13 à 14.
  • Code LCD Hermitien quaternaire :
    • $[21, 10, 8]$ : Améliore la distance minimale connue de 7 à 8.

Les auteurs notent que pour les nouveaux paramètres $[23, 4, 14]$ et $[23, 5, 12]$, ils ont trouvé respectivement 226 et 38 codes inéquivalents. Ces codes sont optimaux en distance et inéquivalents à ceux figurant actuellement dans la base de données BKLC (Best Known Linear Codes).

Signification
L'article affirme que la méthode d'incorporation LCD la plus courte est un outil utile pour trouver des codes LCD optimaux en distance sur divers corps. En déterminant le nombre précis de colonnes nécessaires et en caractérisant leur structure, la méthode offre une voie constructive pour améliorer la distance minimale des codes linéaires connus lors de leur conversion en codes LCD. Les résultats démontrent que cette approche permet de générer avec succès de nouveaux codes dont les distances minimales sont supérieures de un par rapport aux codes précédemment connus pour des paramètres ternaires et quaternaires spécifiques.

Limites et directions futures
Les auteurs reconnaissent une limite dans leur approche : puisque l'espace de recherche pour les matrices inversibles et arbitraires ajoutées est excessivement large, il est difficile de garantir la découverte de l'incorporation spécifique qui produit la distance minimale absolue la plus grande pour un code donné. Ils suggèrent que les recherches futures devraient se concentrer sur le développement de méthodes permettant de sélectionner les matrices ajoutées de manière plus stratégique afin de maximiser la distance minimale résultante, ou de déterminer si les matrices ajoutées peuvent être davantage restreintes par équivalence afin de réduire l'espace de recherche.