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

Technische Samenvatting: Constructie van Cyclische Codes met een Grote Minimale Afstand vanuit Vermogensfuncties over Eindige Velden met een Oneven Karakteristiek

Probleemstelling
Cyclische codes met dimensies die de helft van de codelengte overstijgen ($k > v/2$) en minimale afstanden die groter zijn dan de vierkantswortel van de codelengte ($d > \sqrt{v}$) zijn zeer wenselijk voor toepassingen die een hoge transmissie-efficiëntie en sterke foutcorrectie vereisen, zoals communicatiesystemen, post-kwantum cryptografie en radar. Hoewel er aanzienlijke vooruitgang is geboekt bij het construeren van binaire codes (karakteristiek 2), heeft de constructie van niet-binaire cyclische codes met behulp van vermogensfuncties met bekende differentiële uniformiteit over eindige velden met een oneven karakteristiek relatief minder aandacht gekregen. Dit artikel adresseert de kloof in het construeren van oneindige families van $q$-aire cyclische codes (waarbij $q$ een macht is van een oneven priemgetal) die gunstige parameters bereiken, specifiek gericht op dimensies $k > (q^m - 1)/2$ en minimale afstanden $d > \sqrt{q^m - 1}$.

Methodologie
De auteurs maken gebruik van de trace-sequentie benadering om cyclische codes te construeren. De methodologie omvat de volgende stappen:

1. Sequentie Definitie: Voor een gegeven eindig veld $\mathbb{F}_{q^m}$ en een primitief element $\alpha$, wordt een sequentie $s_\infty = (s_t)_{t \ge 0}$ gedefinieerd via de trace-functie: $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, waarbij $F(x)$ een geselecteerde vermogensfunctie over $\mathbb{F}_{q^m}$ is.
2. Bepaling van het Genererende Polinoom: De cyclische code $C_F$ wordt gegenereerd door het minimale polynoom $M_s(x)$ van de sequentie $s_\infty$. De dimensie van de code wordt bepaald door de lineaire span ($L_s$) van de sequentie, wat overeenkomt met het aantal niet-nul coëfficiënten in de trace-expansie van de sequentie.
3. Selectie van de Vermogensfunctie: Het artikel selecteert specifieke monomialen $F(x) = x^d$ met bekende differentiële uniformiteit over $\mathbb{F}_{q^m}$ (waarbij $q$ oneven is). De selectiecriteria hangen af van de pariteit van $m$ en de specifieke structuur van de exponent $d$.
4. Algebraïsche Analyse:
   • Lineaire Span: De auteurs maken gebruik van $q$-adische expansies, de Stelling van Lucas en eigenschappen van cyclotomische coseten om de trace-functie te expanderen en de niet-nul termen te identificeren. Dit maakt de exacte berekening van de lineaire span $L_s$ en de constructie van het genererende polynoom $M_s(x)$ mogelijk.
   • Minimale Afstand Grenzen: De ondergrenzen op de minimale afstand $d$ worden vastgesteld met behulp van de BCH-bound en de Hartmann-Tzeng bound. Dit houdt het identificeren van opeenvolgende gehele getallen of specifieke verzamelingen binnen de definiërende verzameling (de wortels van het genererende polynoom) in.
   • Exacte Afstanden: Voor specifieke gevallen construeren de auteurs expliciete codewoorden van specifieke gewichten om de exacte minimale afstand te bepalen, wat vaak gerelateerd is aan de geconstrueerde bekende primitieve BCH-codes.

Belangrijkste Bijdragen en Resultaten
Het artikel presenteert verschillende oneindige families van $q$-aire cyclische codes van lengte $v = q^m - 1$ met dimensies die $v/2$ overstijgen. De specifieke constructies en resultaten worden gecategoriseerd op basis van de gebruikte vermogensfuncties:

1. Ternaire Codes uit $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ oneven):

   • Geconstrueerd over $\mathbb{F}_{3^m}$.
   • De lineaire span is $3m + N_3(m)$, wat een dimensie oplevert van $3^m - 1 - 3m - N_3(m)$.
   • De minimale afstand $d$ voldoet aan $3 \le d \le 8$.
   • Voorbeeld: Voor $m=5$ wordt een $[242, 226, 5]$ code verkregen, die bijna optimaal is.

2. $p$-aire Codes uit $x^{p^{m/2} + 2}$ ($m$ even, $p$ oneven):

   • Geconstrueerd over $\mathbb{F}_{p^m}$.
   • De lineaire span hangt af van $p$ en $m$ (bijv. $N_p(m) + 5m/2$ voor $p=3$).
   • Minimale afstand grenzen zijn vastgesteld: $d \ge 3$ (voor $p=3$), $d \ge 5$ (voor $p \ge 5, p \nmid m$), en $d \ge 4$ (voor $p \ge 5, p \mid m$).
   • Exacte afstanden worden bepaald voor specifieke gevallen (bijv. $d=5$ voor $p=5, p \nmid m$).

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

   • Deze constructie behandelt een specifiek geval waarbij de exponent een geometrische reeks som is.
   • Het artikel leidt een algemene formule af voor de lineaire span die de sommen van $N_p(k)$ termen bevat.
   • Significantie: Deze constructie lost gedeeltelijk Open Probleem 5.31 op, geponeerd door Ding [35], dat betrekking had op de dimensie en het genererende polynoom van cyclische codes voor $t = (m+1)/2$ met $m$ oneven.
   • Ondergrenzen op $d$ worden verstrekt, variërend van 2 tot $2^{t-2} + 2$, afhankelijk van $q$ en $t$.

4. Ternaire Codes uit $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ oneven):

   • Maakt gebruik van een monomial die een Perfect Nonlinear (PN) functie of 4-uniform is, afhankelijk van $m$.
   • De lineaire span wordt berekend als $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$.
   • Minimale afstand grenzen worden vastgesteld, met $d \ge 8$ onder specifieke deelbaarheidscondities.

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

   • Generaliseert eerdere binaire resultaten naar een oneven karakteristiek.
   • De lineaire span wordt afgeleid via $p$-adische expansies en specifieke verzamelingsdefinities ($\hat{\Gamma}(t)$).
   • De ondergrenzen op de minimale afstand zijn in veel gevallen aanzienlijk beter dan de vierkantswortel van de codelengte (bijv. $d \ge p^h + 2$).
   • Exacte afstanden worden bepaald voor gevallen waar $h \mid m$, waarbij de code equivalent is aan een narrow-sense primitieve BCH-code met een ontworpen afstand van $p^h + 1$.

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

   • Deze secties behandelen respectievelijk even en oneven $m$ met specifieke exponenten.
   • De auteurs leiden complexe expressies af voor de lineaire span en minimale polynomen.
   • Theorem 11 en Theorem 13 demonstreren dat de ondergrenzen op de minimale afstand voor deze families vaak aanzienlijk superieur zijn aan de vierkantswortel-grens ($\sqrt{v}$).

Significantie en Claims
Het artikel claimt het binaire kader van Ding en Zhou [14] uit te breiden naar een niet-binair setting. De primaire significantie ligt in:

• Verbetering van Parameters: De geconstrueerde codes bereiken dimensies $k > (q^m - 1)/2$ en minimale afstanden $d > \sqrt{q^m - 1}$, waarbij de code-rate en de foutcorrigerende capaciteit effectief worden gebalanceerd.
• Resolutie van Open Problemen: Het werk lost gedeeltelijk Open Probleem 5.31 van Ding [35] op met betrekking tot de ternaire cyclische code gedefinieerd door $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ met $m$ oneven.
• Optimaliteit: Verschillende geconstrueerde codes (en hun dualen) worden geïdentificeerd als optimaal of bijna optimaal wanneer ze worden vergeleken met de Database of best known linear codes [47].
• Theoretische Vooruitgang: Het artikel biedt expliciete formules voor de lineaire span en genererende polynomen voor oneindige families van codes, waarbij geavanceerde getaltheoretische instrumenten (cyclotomische coseten, $p$-adische expansies, de Stelling van Lucas) worden gebruikt om de complexiteit van eindige velden met een oneven karakteristiek te beheersen.

De auteurs concluderen dat deze constructies een rijke bron vormen van codes die geschikt zijn voor veeleisende toepassingen en suggereren dat verdere exploratie van vermogensfuncties over oneven karakteristieke velden meer optimale families kan opleveren. Ze merken ook het potentieel op dat deze codes gebruikt kunnen worden voor het construeren van quantum error-correcting codes via de CSS-constructie.