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

Technische Zusammenfassung: Konstruktion von zyklischen Codes mit großer minimaler Distanz aus Potenzfunktionen über endlichen Körpern mit ungerader Charakteristik

Problemstellung
Zyklische Codes mit Dimensionen, die die halbe Codelänge überschreiten ($k > v/2$), und minimalen Distanzen, die größer als die Quadratwurzel der Codelänge sind ($d > \sqrt{v}$), sind für Anwendungen, die eine hohe Übertragungseffizienz und starke Fehlerkorrektur erfordern – wie etwa Kommunikationssysteme, Post-Quanten-Kryptographie und Radar – äußerst wünschenswert. Während signifikante Fortschritte bei der Konstruktion binärer Codes (Charakteristik 2) erzielt wurden, hat die Konstruktion nicht-binärer zyklischer Codes unter Verwendung von Potenzfunktionen mit bekannter differentieller Uniformität über endlichen Körpern mit ungerader Charakteristik vergleichsweise weniger Aufmerksamkeit erhalten. Diese Arbeit adressiert die Lücke bei der Konstruktion unendlicher Familien von $q$-ären zyklischen Codes (wobei $q$ eine Potenz einer ungeraden Primzahl ist), die vorteilhafte Parameter erzielen, insbesondere mit dem Ziel, Dimensionen $k > (q^m - 1)/2$ und minimale Distanzen $d > \sqrt{q^m - 1}$ zu erreichen.

Methodik
Die Autoren verwenden den Spurfolgen-Ansatz (trace sequence approach), um zyklische Codes zu konstruieren. Die Methodik umfasst die folgenden Schritte:

1. Definition der Sequenz: Für einen gegebenen endlichen Körper $\mathbb{F}_{q^m}$ und ein primitives Element $\alpha$ wird eine Sequenz $s_\infty = (s_t)_{t \ge 0}$ mittels der Spurfunktion definiert: $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, wobei $F(x)$ eine ausgewählte Potenzfunktion über $\mathbb{F}_{q^m}$ ist.
2. Bestimmung des Erzeugenden Polynoms: Der zyklische Code $C_F$ wird durch das minimale Polynom $M_s(x)$ der Sequenz $s_\infty$ erzeugt. Die Dimension des Codes wird durch den linearen Span ($L_s$) der Sequenz bestimmt, was der Anzahl der Nicht-Null-Koeffizienten in der Spur-Expansion der Sequenz entspricht.
3. Auswahl der Potenzfunktion: Das Papier wählt spezifische Monomiale $F(x) = x^d$ mit bekannter differentieller Uniformität über $\mathbb{F}_{q^m}$ (wobei $q$ ungerade ist). Die Auswahlkriterien hängen von der Parität von $m$ und der spezifischen Struktur des Exponenten $d$ ab.
4. Algebraische Analyse:
   • Linearer Span: Die Autoren nutzen $q$-adische Expansionen, den Satz von Lucas und Eigenschaften von zyklotomischen Kosets, um die Spurfunktion zu expandieren und die Nicht-Null-Terme zu identifizieren. Dies ermöglicht die exakte Berechnung des linearen Spans $L_s$ und die Konstruktion des Erzeugenden Polynoms $M_s(x)$.
   • Untere Schranken für die minimale Distanz: Die unteren Schranken für die minimale Distanz $d$ werden mittels der BCH-Schranke und der Hartmann-Tzeng-Schranke etabliert. Dies beinhaltet das Identifizieren aufeinanderfolgender Ganzzahlen oder spezifischer Mengen innerhalb der definierenden Menge (die Nullstellen des Erzeugenden Polynoms).
   • Exakte Distanzen: Für spezifische Fälle konstruieren die Autoren explizite Codewörter spezifischer Gewichte, um die exakte minimale Distanz zu bestimmen, wobei sie die konstruierten Codes häufig mit bekannten primitiven BCH-Codes in Beziehung setzen.

Wesentliche Beiträge und Ergebnisse
Das Paper präsentiert mehrere unendliche Familien von $q$-ären zyklischen Codes der Länge $v = q^m - 1$ mit Dimensionen, die $v/2$ überschreiten. Die spezifischen Konstruktionen und Ergebnisse sind nach den verwendeten Potenzfunktionen kategorisiert:

1. Ternäre Codes aus $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ ungerade):

   • Konstruiert über $\mathbb{F}_{3^m}$.
   • Der lineare Span ist $3m + N_3(m)$, was eine Dimension von $3^m - 1 - 3m - N_3(m)$ ergibt.
   • Die minimale Distanz $d$ erfüllt $3 \le d \le 8$.
   • Beispiel: Für $m=5$ wird ein $[242, 226, 5]$ Code erhalten, der nahezu optimal ist.

2. $p$-äre Codes aus $x^{p^{m/2} + 2}$ ($m$ gerade, $p$ ungerade):

   • Konstruiert über $\mathbb{F}_{p^m}$.
   • Der lineare Span hängt von $p$ und $m$ ab (z. B. $N_p(m) + 5m/2$ für $p=3$).
   • Untere Schranken für die minimale Distanz sind etabliert: $d \ge 3$ (für $p=3$), $d \ge 5$ (für $p \ge 5, p \nmid m$) und $d \ge 4$ (für $p \ge 5, p \mid m$).
   • Exakte Distanzen werden für spezifische Fälle bestimmt (z. B. $d=5$ für $p=5, p \nmid m$).

3. Codes aus $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$ ungerade):

   • Diese Konstruktion adressiert einen spezifischen Fall, in dem der Exponent eine geometrische Reihensumme ist.
   • Das Paper leitet eine allgemeine Formel für den linearen Span her, die Summen von $N_p(k)$-Termen beinhaltet.
   • Bedeutung: Diese Konstruktion löst teilweise das Open Problem 5.31 von Ding [35], welches sich mit der Dimension und dem Erzeugenden Polynom zyklischer Codes für $t = (m+1)/2$ mit $m$ ungerade befasste.
   • Untere Schranken für $d$ werden bereitgestellt, die je nach $q$ und $t$ von 2 bis $2^{t-2} + 2$ reichen.

4. Ternäre Codes aus $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ ungerade):

   • Verwendet ein Monomial, das je nach $m$ eine perfekte nichtlineare (PN) Funktion oder eine 4-uniforme Funktion ist.
   • Der lineare Span wird als $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$ berechnet.
   • Untere Schranken für die minimale Distanz werden etabliert, wobei $d \ge 8$ unter spezifischen Teilbarkeitsbedingungen gilt.

5. $p$-äre Codes aus $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$):

   • Generalisiert vorherige binäre Ergebnisse auf die ungerade Charakteristik.
   • Der lineare Span wird mittels $p$-adischer Expansionen und spezifischer Mengen-Definitionen ($\hat{\Gamma}(t)$) abgeleitet.
   • Die unteren Schranken für die minimale Distanz sind in vielen Fällen signifikant besser als die Quadratwurzel der Codelänge (z. B. $d \ge p^h + 2$).
   • Exakte Distanzen werden für Fälle bestimmt, in denen $h \mid m$ gilt, was zeigt, dass der Code äquivalent zu einem eng gefassten primitiven BCH-Code mit der designten Distanz $p^h + 1$ ist.

6. Codes aus $x^{2 \cdot p^{m/2} - 1}$ und $x^{p^{2h} - p^h + 1}$:

   • Diese Abschnitte behandeln die Fälle für gerades und ungerades $m$ mit spezifischen Exponenten.
   • Die Autoren leiten komplexe Ausdrücke für den linearen Span und die minimalen Polynome ab.
   • Theorem 11 und Theorem 13 zeigen, dass die unteren Schranken für die minimale Distanz dieser Familien oft deutlich über der Quadratwurzel-Schranke ($\sqrt{v}$) liegen.

Bedeutung und Behauptungen
Das Paper behauptet, den binären Rahmen von Ding und Zhou [14] auf eine nicht-binäre Umgebung zu erweitern. Die primäre Bedeutung liegt in:

• Verbesserung der Parameter: Die konstruierten Codes erreichen Dimensionen $k > (q^m - 1)/2$ und minimale Distanzen $d > \sqrt{q^m - 1}$, wodurch Coderate und Fehlerkorrekturkapazität effektiv ausbalanciert werden.
• Lösung offener Probleme: Die Arbeit löst teilweise das Open Problem 5.31 von Ding [35] bezüglich des ternären zyklischen Codes, der durch $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ mit $m$ ungerade definiert ist.
• Optimalität: Mehrere der konstruierten Codes (und deren Duals) werden im Vergleich zur Datenbank der besten bekannten linearen Codes [47] als optimal oder nahezu optimal identifiziert.
• Theoretischer Fortschritt: Das Paper liefert explizite Formeln für den linearen Span und die Erzeugenden Polynome für unendliche Familien von Codes unter Verwendung fortgeschrittener zahlentheoretischer Werkzeuge (zyklotomische Kosets, $p$-adische Expansionen, Satz von Lucas), um die Komplexitäten von Körpern mit ungerader Charakteristik zu handhaben.

Die Autoren kommen zu dem Schluss, dass diese Konstruktionen eine reiche Quelle für Codes darstellen, die für anspruchsvolle Anwendungen geeignet sind, und schlagen vor, dass die weitere Untersuchung von Potenzfunktionen über Feldern mit ungerader Charakteristik weitere optimale Familien hervorbringen könnte. Sie merken zudem das Potenzial dieser Codes an, zur Konstruktion von Quanten-Fehlerkorrektur-Codes via der CSS-Konstruktion verwendet zu werden.