Construction of MRD Codes Based on Circular-Shift Operations

Titel: Konstruktion von MRD-Codes basierend auf zirkulären Verschiebungsoperationen

Autoren: Zhe Zhai, Sheng Jin, Qifu Tyler Sun, Zongpeng Li

---

1. Problemstellung

Maximum Rank Distance (MRD) Codes sind eine wichtige Klasse von fehlerkorrigierenden Codes mit Anwendungen in der Kryptographie, verteilten Speichersystemen und Subspace-Codes. Die bekanntesten Konstruktionen von MRD-Codes, wie die Gabidulin-Codes und die verallgemeinerten "Twisted Gabidulin"-Codes, basieren auf der Arithmetik über Erweiterungskörpern $\mathbb{F}_{q^N}$.

Das Hauptproblem bei diesen herkömmlichen Konstruktionen ist die hohe Implementierungskomplexität, insbesondere wenn der Parameter $N$ (die Dimension des Codes über dem Grundkörper) groß wird.

• Die Operationen erfordern die Arithmetik in $\mathbb{F}_{q^N}$, was bei wachsendem $N$ rechenintensiv wird.
• Die effiziente Auswahl einer Basis für die Transformation von Vektoren über $\mathbb{F}_{q^N}$ in Matrizen über $\mathbb{F}_q$ ist oft unzureichend untersucht.
• Dies führt zu einer unflexiblen Parameterauswahl und erschwert die praktische Anwendung.

2. Methodik

Die Autoren schlagen eine neue Konstruktion von MRD-Codes vor, die ausschließlich auf zirkulären Verschiebungsoperationen (circular-shift operations) über dem Grundkörper $\mathbb{F}_q$ basiert und die Arithmetik über Erweiterungskörpern vermeidet.

Kernkonzepte der Konstruktion:

• Parameter: Sei $q$ eine Primzahl, $L$ eine positive ganze Zahl mit $\text{ggT}(q, L) = 1$.
  • $m_L$: Die multiplikative Ordnung von $q$ modulo $L$ (d.h. $q^{m_L} \equiv 1 \pmod L$).
  • $J$: Die Eulersche Phi-Funktion $\phi(L)$ (Anzahl der zu $L$ teilerfremden Zahlen kleiner als $L$).
• Struktur: Der Code ist ein $(J \times n, q^{Jk}, d)$ MRD-Code mit $n \le m_L \le J$.
• Konstruktionsformel: Ein Codewort $C$ wird durch folgende Operation erzeugt:
  $$C = \{ \Delta(m(I_k \otimes P) \Psi_{k \times n} (I_n \otimes Q)) : m \in \mathbb{F}_q^{Jk} \}$$
  Dabei sind:
  • $\Psi_{k \times n}$: Eine Blockmatrix, deren Blöcke zirkulante Permutationsmatrizen $C_L^l$ über $\mathbb{F}_q$ sind.
  • $P, Q$: Matrizen über $\mathbb{F}_q$, die speziell konstruiert werden (z.B. basierend auf Vandermonde-Matrizen und Wurzeln der Einheitswurzel), um die MRD-Eigenschaft zu garantieren.
  • $\Delta$: Eine Abbildung, die einen Vektor in eine Matrix umwandelt.
• Vermeidung von Erweiterungskörpern: Alle Berechnungen (Addition, Multiplikation, zirkuläre Verschiebung) finden direkt in $\mathbb{F}_q$ statt.

3. Wichtige Beiträge

1. Neue Konstruktion: Einführung einer effizienten MRD-Code-Konstruktion, die auf zirkulären Verschiebungen basiert und keine Arithmetik über $\mathbb{F}_{q^J}$ benötigt.
2. Charakterisierung durch q-lineare Polynome: Die Autoren charakterisieren sowohl die neuen Codes als auch Gabidulin-Codes durch eine Menge von $q$-linearen Polynomen über dem Vektorraum $\mathbb{F}_q^N$ (anstatt über $\mathbb{F}_{q^N}$). Dies ermöglicht einen direkten Vergleich.
3. Unterscheidung und Äquivalenzanalyse:
   • Fall $J \neq m_L$: Unter bestimmten Parametereinstellungen (insbesondere wenn die Exponenten $l_j$ eine bestimmte lineare Struktur haben) wurden die neuen Codes als nicht äquivalent zu beliebigen Gabidulin-Codes oder Twisted Gabidulin-Codes bewiesen.
   • Fall $J = m_L$: Es wurde bewiesen, dass in diesem speziellen Fall jeder konstruierte Code äquivalent zu einem Gabidulin-Code ist. Der Wert dieser Konstruktion liegt jedoch darin, dass sie Gabidulin-Codes rein über $\mathbb{F}_q$ realisiert, was die Implementierung vereinfacht.
4. Verallgemeinerung: Es wurde gezeigt, dass die neuen Codes unter bestimmten Bedingungen äquivalent zu einer Verallgemeinerung von Gabidulin-Codes sind, die durch Summation und Verkettung mehrerer $(m_L \times n, q^{m_L k}, d)$ Gabidulin-Codes entsteht. Diese Verallgemeinerung war in der Literatur bisher nicht untersucht.
5. Komplexitätsanalyse: Eine detaillierte Analyse der Rechenkomplexität für den Fall $q=2$ und primem $L$.

4. Ergebnisse

• Äquivalenz: Die Arbeit liefert einen vollständigen theoretischen Rahmen, der klärt, wann die neuen Codes mit Gabidulin-Codes übereinstimmen und wann sie eine neue, nicht-äquivalente Klasse darstellen.
• Komplexitätsvorteil:
  • Für $q=2$, primem $L$ und $n \le m_L$:
    • Die Generierung eines Codewortes für den vorgeschlagenen Code erfordert $O(nkL)$ XOR-Operationen.
    • Die Generierung eines Codewortes für einen herkömmlichen Gabidulin-Code (basierend auf $\mathbb{F}_{2^{L-1}}$) erfordert $O(nkL^2)$ XOR-Operationen (da Multiplikationen im Erweiterungskörper quadratisch in der Länge skalieren).
  • Dies stellt eine signifikante Reduktion der Rechenkomplexität dar, insbesondere für große Parameter.
• Beispiele: Konkrete Beispiele (z.B. $L=7, q=2$) demonstrieren die Konstruktion und bestätigen die MRD-Eigenschaft sowie die Äquivalenz zu Gabidulin-Codes im Fall $J=m_L$.

5. Bedeutung und Ausblick

• Praktische Relevanz: Die vorgeschlagene Konstruktion macht MRD-Codes für Anwendungen praktikabler, bei denen die Arithmetik über großen Erweiterungskörpern zu teuer oder zu langsam wäre (z.B. in Echtzeit-Netzwerken oder ressourcenbeschränkten Speichersystemen).
• Flexibilität: Da keine Basiswahl für $\mathbb{F}_{q^J}$ erforderlich ist, ist die Parameterauswahl flexibler.
• Theoretischer Fortschritt: Die Arbeit schließt eine Lücke im Verständnis der Beziehung zwischen zirkulären Verschiebungs-codes und klassischen algebraischen Codes. Sie zeigt, dass Gabidulin-Codes auch ohne Erweiterungskörper-Arithmetik effizient implementiert werden können.
• Zukünftige Arbeiten: Die Autoren sehen als offene Fragen die Untersuchung der Beziehung zu Twisted Gabidulin-Codes für $q > 2$ und $\eta \neq 0$ sowie die Entwicklung effizienter Decodieralgorithmen für die neuen Codes.

Zusammenfassend bietet dieses Paper einen effizienten, rein über dem Grundkörper $\mathbb{F}_q$ arbeitenden Weg zur Konstruktion von MRD-Codes, der die Rechenkomplexität drastisch senkt und gleichzeitig tiefgreifende theoretische Einblicke in die Struktur dieser Codes im Vergleich zu Gabidulin-Codes liefert.