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

Riepilogo Tecnico: Costruzione di Codici Ciclici con Grande Distanza Minima da Funzioni di Potenza su Campi Finiti a Caratteristica Dispari

Enunciato del Problema
I codici ciclici con dimensioni che superano la metà della lunghezza del codice ($k > v/2$) e distanze minime superiori alla radice quadrata della lunghezza del codice ($d > \sqrt{v}$) sono altamente desiderabili per applicazioni che richiedono un'elevata efficienza di trasmissione e una forte correzione degli errori, come i sistemi di comunicazione, la crittografia post-quantistica e il radar. Mentre sono stati fatti progressi significativi nella costruzione di codici ciclici su campi binari (caratteristica 2), la costruzione di codici ciclici non binari utilizzando funzioni di potenza con uniformità differenziale nota su campi a caratteristica dispari ha ricevuto un'attenzione comparativamente minore. Questo articolo affronta la lacuna nella costruzione di famiglie infinite di codici $q$-ari (dove $q$ è una potenza di un primo dispari) che raggiungono parametri favorevoli, mirando specificamente a dimensioni $k > (q^m - 1)/2$ e distanze minime $d > \sqrt{q^m - 1}$.

Metodologia
Gli autori utilizzano l'approccio della sequenza di traccia per costruire codici ciclici. La metodologia prevede i seguenti passaggi:

1. Definizione della Sequenza: Per un dato campo finito $\mathbb{F}_{q^m}$ e un elemento primitivo $\alpha$, una sequenza $s_\infty = (s_t)_{t \ge 0}$ è definita tramite la funzione di traccia: $s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$, dove $F(x)$ è una funzione di potenza selezionata su $\mathbb{F}_{q^m}$.
2. Determinazione del Polinomio Generatore: Il codice ciclico $C_F$ è generato dal polinomio minimo $M_s(x)$ della sequenza $s_\infty$. La dimensione del codice è determinata dall'estensione lineare ($L_s$) della sequenza, che corrisponde al numero di coefficienti non nulli nell'espansione della traccia.
3. Selezione della Funzione di Potenza: L'articolo seleziona specifici monomi $F(x) = x^d$ con uniforme differenziale nota su $\mathbb{F}_{q^m}$ (dove $q$ è dispari). I criteri di selezione dipendono dalla parità di $m$ e dalla struttura specifica dell'esponente $d$.
4. Analisi Algebrica:
   • Estensione Lineare: Gli autori utilizzano espansioni $q$-adiche, il Teorema di Lucas e le proprietà dei cosetti ciclotomici per espandere la funzione di traccia e identificare i termini non nulli. Ciò consente il calcolo esatto dell'estensione lineare $L_s$ e la costruzione del polinomio generatore $M_s(x)$.
   • Limiti della Distanza Minima: I limiti inferiori sulla distanza minima $d$ sono stabiliti utilizzando il limite BCH e il limite di Hartmann-Tzeng. Ciò comporta l'identificazione di interi consecutivi o specifici insiemi all'interno dell'insieme definente (le radici del polinomio generatore).
   • Distanze Esatte: Per casi specifici, gli autori costruiscono parole codificate esplicite di pesi specifici per determinare la distanza minima esatta, spesso collegando i codici costruiti a noti codici BCH primitivi.

Contributi Chiave e Risultati
L'articolo presenta diverse famiglie infinite di codici $q$-ari di lunghezza $v = q^m - 1$ con dimensioni che superano $v/2$. Le specifiche costruzioni e i risultati sono categorizzati in base alle funzioni di potenza utilizzate:

1. Codici Ternari da $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ dispari):

   • Costruiti su $\mathbb{F}_{3^m}$.
   • L'estensione lineare è $3m + N_3(m)$, fornendo una dimensione $3^m - 1 - 3m - N_3(m)$.
   • La distanza minima $d$ soddisfa $3 \le d \le 8$.
   • Esempio: Per $m=5$, si ottiene un codice $[242, 226, 5]$, che è quasi ottimale.

2. Codici $p$-ari da $x^{p^{m/2} + 2}$ ($m$ pari, $p$ dispari):

   • Costruiti su $\mathbb{F}_{p^m}$.
   • L'estensione lineare dipende da $p$ e $m$ (ad esempio, $N_p(m) + 5m/2$ per $p=3$).
   • Sono stabiliti i limiti della distanza minima: $d \ge 3$ (per $p=3$), $d \ge 5$ (per $p \ge 5, p \nmid m$), e $d \ge 4$ (per $p \ge 5, p \mid m$).
   • Le distanze esatte sono determinate per casi specifici (ad esempio, $d=5$ per $p=5, p \nmid m$).

3. Codici da $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$ dispari):

   • Questa costruzione affronta un caso specifico in cui l'esponente è la somma di una serie geometrica.
   • L'articolo deriva una formula generale per l'estensione lineare che coinvolge somme di termini $N_p(k)$.
   • Significato: Questa costruzione risolve parzialmente l'Open Problem 5.31 posto da Ding [35], che riguardava la dimensione e il polinomio generatore per i codici ciclici con $t = (m+1)/2$ con $m$ dispari.
   • Vengono forniti limiti inferiori su $d$, che variano da 2 a $2^{t-2} + 2$ a seconda di $q$ e $t$.

4. Codici Ternari da $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ dispari):

   • Utilizza un monomio che è una funzione Perfettamente Non Lineare (PN) o 4-uniforme a seconda di $m$.
   • L'estensione lineare è calcolata come $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$.
   • Sono stabiliti i limiti della distanza minima, con $d \ge 8$ sotto specifiche condizioni di divisibilità.

5. Codici $p$-ari da $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$):

   • Generalizza i precedenti risultati binari al caso di caratteristica dispari.
   • L'estensione lineare è derivata utilizzando le espansioni $p$-adiche e definizioni di insiemi specifici ($\hat{\Gamma}(t)$).
   • I limiti inferiori della distanza minima sono mostrati essere significativamente migliori della radice quadrata della lunghezza del codice in molti casi (ad esempio, $d \ge p^h + 2$).
   • Le distanze esatte sono determinate per i casi in cui $h \mid m$, mostrando che il codice è equivalente a un codice BCH primitivo a senso stretto con distanza progettata $p^h + 1$.

6. Codici da $x^{2 \cdot p^{m/2} - 1}$ e $x^{p^{2h} - p^h + 1}$:

   • Queste sezioni gestiscono rispettivamente $m$ pari e dispari con esponenti specifici.
   • Gli autori derivano espressioni complesse per l'estensione lineare e i polinomi minimi.
   • Il Teorema 11 e il Teorema 13 dimostrano che i limiti inferiori della distanza minima per queste famiglie sono spesso significativamente superiori al limite della radice quadrata ($\sqrt{v}$).

Significato e Rivendicazioni
L'articolo sostiene di estendere il framework binario di Ding e Zhou [14] a un contesto non binario. Il significato primario risiede nel:

• Miglioramento dei Parametri: I codici costruiti raggiungono dimensioni $k > (q^m - 1)/2$ e distanze minime $d > \sqrt{q^m - 1}$, bilanciando efficacementamente il tasso del codice e la capacità di correzione degli errori.
• Risoluzione di Problemi Aperti: Il lavoro risolve parzialmente l'Open Problem 5.31 di Ding [35] riguardante il codice ciclico ternario definito da $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ con $m$ dispari.
• Ottimalità: Diversi codici costruiti (e i loro duali) sono identificati come ottimali o quasi ottimali rispetto al Database dei migliori codici lineari noti [47].
• Avanzamento Teorico: Il documento fornisce formule esplicite per l'estensione lineare e i polinomi generatori per famiglie infinite di codici, utilizzando strumenti numerici avanzati (cosetti ciclotomici, espansioni $p$-adiche, Teorema di Lucas) per gestire le complessità dei campi a caratteristica dispari.

Gli autori concludono che queste costruzioni forniscono una ricca fonte di codici adatti ad applicazioni esigenti e suggeriscono che un'ulteriore esplorazione delle funzioni di potenza su campi a caratteristica dispari potrebbe portare a famiglie più ottimali. Notano inoltre il potenziale di questi codici per la costruzione di codici di correzione degli errori quantistici tramite la costruzione CSS.