🔢 mathematics

On the equivalence between additive and linear codes

Die Arbeit stellt einen deterministischen Test vor, um additive Codes von linearen Codes zu unterscheiden, und wendet diesen an, um sowohl die strikte Additivität bestimmter quaternärer Codes zu verifizieren als auch die Äquivalenz eines bekannten additiven komplementären Dualcodes zu einem linearen hermitischen LCD-Code nachzuweisen, was die besten bekannten Schranken für letztere verbessert.

Ursprüngliche Autoren: Kanat Abdukhalikov, Duy Ho

Veröffentlicht 2026-03-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kanat Abdukhalikov, Duy Ho

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die große Suche: Sind diese Codes wirklich neu oder nur verkleidet?

Stellen Sie sich vor, Sie sind ein Architekt, der neue, extrem stabile Brücken baut. In der Welt der Datenübertragung (Kommunikationstechnik) sind diese „Brücken" Codes. Sie sorgen dafür, dass Ihre Nachrichten (z. B. WhatsApp-Nachrichten oder Satellitendaten) auch dann noch verständlich ankommen, wenn sie unterwegs durch Störungen „zerkratzt" werden.

Es gibt zwei Hauptarten von Bauplänen für diese Brücken:

Lineare Codes: Diese folgen strengen, einfachen mathematischen Regeln (wie ein gerades Gitter). Sie sind gut verstanden und leicht zu bauen.
Additive Codes: Diese sind flexibler und folgen etwas komplexeren Regeln. Man hat kürzlich entdeckt, dass einige dieser „Additiven" Brücken noch stabiler sein können als die besten „Linearen".

Das Problem:
Manchmal sieht eine neue, additive Brücke auf den ersten Blick fantastisch aus und scheint besser zu sein als alles, was man vorher kannte. Aber ist sie wirklich etwas Neues? Oder ist sie nur eine alte, lineare Brücke, die man einfach nur umgebaut, umgedreht oder neu bemalt hat?

Bisher war es sehr schwer, das herauszufinden. Man musste oft komplizierte geometrische Tricks anwenden, um zu sehen, ob die Brücke im Kern linear ist oder nicht.

Die Lösung: Der neue „Fingerabdruck-Test"

Die Autoren dieses Papiers haben eine neue Methode entwickelt, um diese Frage schnell und sicher zu beantworten. Sie nennen es einen deterministischen Test.

Stellen Sie sich vor, Sie haben einen Bauplan (einen Generator-Matrix). Früher musste man den Plan stundenlang studieren, um zu raten, ob er linear ist. Die Autoren sagen: „Nein, wir brauchen nur einen einzigen, klaren Test."

Wie funktioniert der Test? (Die Analogie)

Stellen Sie sich den Code als ein riesiges Puzzle vor, das aus vielen kleinen Kacheln besteht.

Der Test prüft die Kacheln: Der Autor schaut sich an, wie diese Kacheln angeordnet sind.
Der „Spiegel"-Effekt: Ein linearer Code hat eine besondere Eigenschaft: Wenn man ihn in einen bestimmten mathematischen Spiegel hält (eine Operation namens Multiplikation mit einer speziellen Zahl), bleibt er in sich selbst erhalten. Er dreht sich nicht wild umher, sondern passt perfekt zurück in sein eigenes Muster.
Der Additive Code: Ein echt additiver Code (der nicht linear ist) würde in diesem Spiegel zerfallen oder sich völlig anders verhalten. Er passt nicht zurück.

Die Autoren haben eine Formel (eine große Matrix, nennen wir sie Matrix S) entwickelt, die diesen Spiegel-Test für den gesamten Code durchführt.

Die zwei einfachen Regeln des Tests

Der Test läuft in zwei Schritten ab, die wie ein Sicherheitscheck funktionieren:

Der „Einzel-Kachel"-Check:
Schaut man sich die Kacheln an, gibt es eine, die so einfach ist, dass sie nur eine einzige Richtung hat (mathematisch: Rang 1)?
- Ja: Dann ist der Code nicht linear. Er ist ein echtes, neues Unikat. (Wie ein Puzzle, bei dem ein Teil nur aus einem einzigen Strich besteht – das passt nicht in das strenge Gitter).
Der „Zahl-Check" (Die Nullen):
Wenn alle Kacheln komplex sind, zählt man die „freien Räume" in der großen Formel (die sogenannte Nullität).
- Ist diese Zahl ungerade (1, 3, 5...)? Dann ist der Code nicht linear. Er ist strikt additiv.
- Ist die Zahl gerade? Dann könnte er linear sein. Man muss noch genauer hinschauen.

Was haben die Forscher herausgefunden?

Mit diesem neuen, schnellen Test haben sie einige berühmte Beispiele aus der Literatur überprüft:

Die „Super-Brücken" sind echt: Viele der neuen Codes, die kürzlich als „besser als linear" gepriesen wurden (insbesondere aus einer Arbeit von Guan et al.), haben den Test bestanden. Sie sind wirklich neu. Sie sind nicht nur verkleidete lineare Codes. Das ist eine große Entdeckung, denn es bedeutet, wir haben völlig neue Werkzeuge für stabilere Datenübertragung.
Die Überraschung: Es gab einen Code, der als „additiv" galt, aber der Test zeigte: Aha! Der ist eigentlich linear!
- Dieser Code war ein „Additiver Komplementärer Dual" (ACD) Code. Der Test zeigte, dass man ihn so umdrehen und umgestalten kann, dass er zu einem sehr guten „Linearen Hermitian LCD Code" wird.
- Warum ist das wichtig? Weil lineare Codes oft einfacher zu handhaben sind. Indem sie zeigten, dass dieser Code eigentlich linear ist, haben sie die Bestwerte für diese Art von linearen Codes verbessert. Es ist, als würden sie sagen: „Wir dachten, das ist ein neuer, komplizierter Motor, aber eigentlich ist es ein bewährter, hochleistungsfähiger Motor, den wir nur falsch eingebaut hatten."

Fazit für den Alltag

Diese Arbeit ist wie ein neuer Metall-Detektor für Mathematiker.

Früher musste man raten, ob ein neuer Code etwas Besonderes ist.
Jetzt können sie mit einem schnellen, klaren Test (dem „Fingerabdruck") sofort sagen: „Nein, das ist nur eine alte lineare Brücke in neuem Gewand" ODER „Ja, das ist ein völlig neuer, additiver Code, den wir noch nie gesehen haben."

Das hilft Ingenieuren und Wissenschaftlern, die besten Werkzeuge für die Zukunft der Kommunikation (wie 6G oder Quantencomputer) schneller zu finden, ohne Zeit mit Codes zu verschwenden, die eigentlich gar nicht neu sind.

Titel: Zur Äquivalenz zwischen additiven und linearen Codes

Autoren: Kanat Abdukhalikov und Duy Ho (UAE University)

1. Problemstellung

Additive Codes über dem Körper $\mathbb{F}_{q^2}$ (insbesondere über $\mathbb{F}_4$ ) haben in der Forschung an Bedeutung gewonnen, da sie oft bessere Parameter (insbesondere minimale Distanzen) aufweisen als ihre linearen Gegenstücke. Ein zentrales, aber bisher ungelöstes Problem besteht darin, rigoros zu unterscheiden, ob ein neu konstruierter additiver Code strikt additiv ist (d.h. nicht äquivalent zu einem linearen Code über $\mathbb{F}_{q^2}$ ) oder ob er lediglich eine andere Darstellung eines linearen Codes darstellt.

Bisherige Methoden zur Unterscheidung basierten primär auf geometrischen Techniken (z.B. Pseudo-Arcs und Desargues-Verteilungen), die oft komplex und nicht allgemein anwendbar sind. Die Autoren adressieren die Frage, wie man algorithmisch und deterministisch feststellen kann, ob ein additiver Code äquivalent zu einem linearen Code ist, ohne auf geometrische Konstruktionen zurückgreifen zu müssen.

2. Methodik und Algebraischer Rahmen

Die Autoren entwickeln einen rein algebraischen Test, der ausschließlich die Generator-Matrix $G$ des additiven Codes benötigt. Der Ansatz stützt sich auf folgende Konzepte:

Darstellung: Ein additiver Code $C \subseteq \mathbb{F}_{q^2}^n$ der Dimension $k$ über $\mathbb{F}_q$ wird durch eine Matrix $G \in \mathbb{F}_q^{k \times 2n}$ dargestellt, die die Abbildung $\phi: \mathbb{F}_{q^2}^n \to \mathbb{F}_q^{2n}$ nutzt.
Äquivalenzdefinition: Zwei Codes sind monomial äquivalent, wenn sie durch eine Permutation der Koordinaten und Multiplikation mit invertierbaren $2 \times 2$ -Matrizen (über $\mathbb{F}_q$ ) ineinander überführt werden können.
Regular Representation (Reguläre Darstellung): Die Multiplikation mit einem primitiven Element $\omega \in \mathbb{F}_{q^2}$ wird durch eine $2 \times 2$ -Begleitmatrix $M_\omega$ dargestellt. Ein Code ist genau dann linear über $\mathbb{F}_{q^2}$ , wenn er unter dieser Multiplikation abgeschlossen ist.

Der Kern des Tests (Theorem 3.1):
Ein additiver Code $C$ mit Generatormatrix $G$ ist genau dann äquivalent zu einem linearen Code über $\mathbb{F}_{q^2}$ , wenn es eine invertierbare Matrix $R \in GL_k(\mathbb{F}_q)$ und eine Block-Diagonalmatrix $A = \text{diag}(A_1, \dots, A_n)$ gibt, sodass gilt:
$RG = G(A M_\omega A^{-1})$
Dies führt zu einem System linearer Gleichungen für die unbekannten Matrizen $R$ und $A_i$ .

Algorithmus 1 (Der Äquivalenztest):

Rang-Check: Die Matrix $G$ $G$ wird in $n$ $n$ Blöcke $G_i$ $G_{i}$ der Größe $k \times 2$ $k \times 2$ zerlegt.
- Falls ein Block $G_i$ den Rang 1 hat, ist der Code nicht äquivalent zu einem linearen Code (Theorem 3.2).
Nullitäts-Test: Es wird eine große Matrix $S$ $S$ konstruiert, deren Kern (Nullraum) die Lösungen für $R$ $R$ und die Transformationsmatrizen $T_i$ $T_{i}$ beschreibt.
- Falls die Nullität (Dimension des Nullraums) von $S$ ungerade ist, ist der Code strikt additiv (Theorem 3.3).
- Begründung: Wenn der Code linear wäre, müsste der Raum der Lösungen $R$ eine Struktur haben, die eine gerade Dimension impliziert (da er isomorph zu $\mathbb{F}_{q^2}$ ist).
Suche im Nullraum: Falls die Nullität gerade ist, wird im Nullraum nach einer spezifischen Matrix $R$ gesucht, die keine Eigenwerte in $\mathbb{F}_q$ besitzt.

3. Wichtige Beiträge

Deterministischer Algebraischer Test: Einführung eines effizienten Algorithmus, der nur die Generator-Matrix benötigt und keine geometrischen Konstruktionen erfordert.
Charakterisierung der Äquivalenz: Beweis, dass die Existenz einer bestimmten Matrix $R$ (die die Struktur von $\mathbb{F}_{q^2}$ widerspiegelt) notwendig und hinreichend für die Äquivalenz zu einem linearen Code ist.
Notwendige Bedingung (Theorem 3.3): Die Erkenntnis, dass eine ungerade Nullität der Hilfsmatrix $S$ ausreicht, um strikte Additivität nachzuweisen.
Anwendung auf ACD-Codes: Untersuchung von Additive Complementary Dual (ACD) Codes und deren Beziehung zu Linear Complementary Dual (LCD) Codes im hermitischen Sinne.

4. Ergebnisse und Anwendungen

Die Autoren wandten ihren Test auf bekannte quaternäre additive Codes an (berechnet mit dem System MAGMA):

Verifizierung strikter Additivität:
- Alle in [14, Tabelle II] aufgeführten quaternären additiven Codes (z.B. mit Parametern wie $[47, 35, 7]_2^2$ , $[63, 5, 45]_2^2$ ) wurden als strikt additiv bestätigt.
- Alle zehn in [18, Tabelle 2] vorgestellten ACD-Codes (konstruiert via Plotkin-Summe) wurden ebenfalls als strikt additiv identifiziert.
- Bei vielen dieser Codes konnte dies bereits durch den Rang-Check (Theorem 3.2) oder die ungerade Nullität (Theorem 3.3) bewiesen werden.
Entdeckung einer Äquivalenz (Verbesserung von Schranken):
- Ein spezifischer ACD-Code aus [14, Tabelle IV] mit Parametern $[22, 10, 9]_2^2$ wurde untersucht.
- Der Test zeigte, dass dieser Code äquivalent zu einem linearen hermitischen LCD-Code über $\mathbb{F}_4$ ist.
- Bedeutung: Dies verbessert die besten bekannten Schranken für lineare hermitische LCD-Codes dieser Parameter, da der Code ursprünglich als additiv und potenziell "besser" als lineare Codes galt, sich aber als lineare Struktur entpuppte, die nun in die Tabellen für lineare Codes aufgenommen werden kann.

5. Bedeutung und Fazit

Die Arbeit liefert ein essentielles Werkzeug für die Codierungstheorie, um die Natur neu konstruierter Codes zu klassifizieren.

Sie klärt die oft unklare Situation, ob ein Code mit überlegenen Parametern tatsächlich eine neue Klasse (strikt additiv) darstellt oder nur eine Transformation eines bekannten linearen Codes ist.
Der vorgestellte Test ist effizient, deterministisch und leicht implementierbar.
Die Ergebnisse bestätigen, dass viele der kürzlich als "besser als linear" gepriesenen Codes tatsächlich strikt additiv sind, während gleichzeitig gezeigt wird, dass einige additive Konstruktionen (wie der $[22, 10, 9]$ -Code) wertvolle lineare LCD-Codes liefern, die die aktuellen Bestwerte übertreffen.

Dies trägt maßgeblich dazu bei, die Grenzen zwischen additiven und linearen Codes präziser zu definieren und die Klassifikation optimaler Codes zu verfeinern.