Shortest LCD embeddings of binary, ternary and quaternary linear codes

Problemstellung
Lineare Codes mit komplementären Duals (LCD-Codes) sind ein bedeutendes Forschungsgebiet in der Kodierungstheorie und Kryptographie, insbesondere aufgrund ihrer Resistenz gegen Seitenkanal- und Fehlereinspritzungsangriffe. Während bekannt ist, dass jeder lineare Code über $\mathbb{F}_q$ ($q \ge 4$) äquivalent zu einem LCD-Code ist, und ähnliche Ergebnisse für $\mathbb{F}_{q^2}$ existieren, bleiben die Schranken für die minimalen Distanzen von LCD-Codes über $\mathbb{F}_2$, $\mathbb{F}_3$ und hermiteschen LCD-Codes über $\mathbb{F}_4$ für viele Längen und Dimensionen unbekannt. Eine zentrale Herausforderung in der Kodierungstheorie besteht darin, die größte minimale Distanz für eine gegebene Länge und Dimension zu bestimmen. Diese Arbeit befasst sich mit der spezifischen Problemstellung, beliebige lineare Codes in LCD-Codes einzubetten, mit dem Ziel, die „kürzeste“ solche Einbettung (minimale Längenzunahme) zu finden und diese Methode zur Konstruktion neuer distanzoptimaler LCD-Codes zu nutzen.

Methodik
Die Autoren führen einen systematischen Ansatz ein, um einen gegebenen linearen Code $C$ in einen LCD-Code $\tilde{C}$ einzubetten, indem sie die minimale Anzahl an Spalten zu seiner Erzeugermatrix hinzufügen. Die Methodik verläuft wie folgt:

1. Theoretische Grundlage: Die Arbeit stellt fest, dass die minimale Anzahl an Spalten ($m$), die erforderlich ist, um einen $[n, k]$ Code $C$ in einen LCD-Code einzubetten, genau der Dimension $\ell$ des Hulls von $C$ entspricht (wobei $\text{Hull}(C) = C \cap C^\perp$). Folglich ist die Länge der kürzesten LCD-Einbettung $n + \ell$.
2. Strukturelle Charakterisierung: Die Autoren charakterisieren die Erzeugermatrix einer kürzesten LCD-Einbettung. Wenn $G$ eine Erzeugermatrix von $C$ ist, die in einen Teil zur Erzeugung des Hulls, $G(\text{Hull}(C))$, und einen verbleibenden Teil $A$ zerlegt wurde, dann wird eine kürzeste LCD-Einbettung durch eine Matrix der Form erzeugt:
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   wobei $D$ eine invertierbare $\ell \times \ell$ Matrix und $C$ eine beliebige $(k-\ell) \times \ell$ Matrix ist. Die Arbeit beweist, dass das Anhängen einer invertierbaren Matrix an die Zeilen, die den Hull entsprechen, und einer beliebigen Matrix an die verbleibenden Zeilen stets eine kürzeste LCD-Einbettung ergibt.
3. Konstruktionsstrategie: Die Autoren wenden diese Einbettungsmethode auf bekannte distanzoptimale lineare Codes (speziell ternäre und quartäre Codes) an, die selbst keine LCD-Codes sind. Durch Berechnung der Hull-Dimension dieser bestehenden Codes und das Anhängen der notwendigen Spalten gemäß der abgeleiteten Struktur generieren sie neue LCD-Codes.

Wesentliche Beiträge und Ergebnisse
Die Arbeit liefert sowohl theoretische Schranken als auch konkrete Konstruktionen:

• Theoretische Ergebnisse:

  • Beweist, dass die Länge der kürzesten LCD-Einbettung eines $[n, k]$ Codes mit Hull-Dimension $\ell$ genau $n + \ell$ ist.
  • Charakterisiert alle möglichen Formen von Erzeugermatrizen für diese kürzesten Einbettungen und zeigt, dass sie äquivalent zum Anhängen einer invertierbaren Matrix an die den Hull erzeugenden Zeilen sind.
  • Demonstriert, dass die Länge der kürzesten LCD-Einbettung eines Codes $C$ identisch mit der seines Hulls, $\text{Hull}(C)$, ist.

• Neue Code-Konstruktionen:
  Durch Anwendung der kürzesten LCD-Einbettungsmethode auf bestehende lineare Codes konstruierten die Autoren mehrere neue LCD-Codes mit Parametern, die die bekannten minimalen Distanzen verbessern:

  • Ternäre LCD-Codes:
    • $[23, 4, 14]$: Verbessert die bekannte minimale Distanz von 13 auf 14.
    • $[23, 5, 12]$: Verbessert die bekannte minimale Distanz von 11 auf 12.
    • $[24, 6, 12]$: Verbessert die bekannte minimale Distanz von 11 auf 12.
    • $[25, 5, 14]$: Verbessert die bekannte minimale Distanz von 13 auf 14.
  • Quartärer hermitischer LCD-Code:
    • $[21, 10, 8]$: Verbessert die bekannte minimale Distanz von 7 auf 8.

Die Autoren merken an, dass sie für die neuen Parameter $[23, 4, 14]$ und $[23, 5, 12]$ jeweils 226 bzw. 38 inäquivalente Codes gefunden haben. Diese Codes sind distanzoptimal und inäquivalent zu den derzeit in der BKLC-Datenbank befindlichen Codes.

Bedeutung
Die Arbeit behauptet, dass die Methode der kürzesten LCD-Einbettung ein nützliches Werkzeug zur Findung distanzoptimaler LCD-Codes über verschiedenen Feldern ist. Durch die Bestimmung der präzisen Anzahl an benötigten Spalten und die Charakterisierung ihrer Struktur bietet die Methode einen konstruktiven Pfad, um die minimale Distanz bekannter linearer Codes bei deren Umwandlung in LCD-Codes zu verbessern. Die Ergebnisse zeigen, dass dieser Ansatz erfolgreich neue Codes mit minimalen Distanzen konstruiert, die um eins größer sind als die der zuvor bekannten ternären und quartären Parameter.

Einschränkungen und zukünftige Richtungen
Die Autoren räumen eine Einschränkung ihres Ansatzes ein: Da der Suchraum für die angehängten invertierbaren und beliebigen Matrizen übermäßig groß ist, ist es schwierig zu garantieren, dass die spezifische Einbettung gefunden wird, die die absolut größte minimale Distanz für einen gegebenen Code liefert. Sie schlagen vor, dass sich die zukünftige Forschung darauf konzentrieren sollte, Methoden zu entwickeln, um die angehängten Matrizen strategischer auszuwählen, um die resultierende minimale Distanz zu maximieren, oder zu bestimmen, ob die angehängten Matrizen bis auf Äquivalenz weiter eingeschränkt werden können, um den Suchraum zu reduzieren.