New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance

1. Il Problema

I codici ciclici binari sono fondamentali sia per le loro applicazioni pratiche che per la loro importanza teorica. Un problema centrale nella teoria dei codici è la costruzione di famiglie infinite di codici ciclici con lunghezza $n = 2^m - 1$ e dimensione $k$ vicina a $n/2$ (specificamente $k \approx (n \pm 1)/2$) che possiedano contemporaneamente:

• Una distanza minima ($d$) elevata.
• Una distanza duale ($d^\perp$) elevata.

Storicamente, esiste un compromesso (trade-off) tra questi due parametri: all'aumentare della distanza minima $d$ di un codice ciclico, la distanza minima del suo codice duale $d^\perp$ tende a diminuire. La maggior parte delle costruzioni esistenti ottiene un miglioramento di uno dei due parametri a scapito dell'altro. L'obiettivo di questo lavoro è superare questo limite, costruendo codici in cui il prodotto $d \cdot d^\perp$ sia asintoticamente grande (vicino a $n$ o addirittura $2n$), superando i limiti noti come il "square-root bound" ($\sqrt{n}$).

2. Metodologia

Gli autori utilizzano un approccio basato sulla teoria degli anelli polinomiali e sulle proprietà delle classi ciclotomiche (2-cyclotomic cosets) modulo $n = 2^m - 1$.

• Definizione dell'insieme di definizione (Defining Set): Un codice ciclico è determinato da un insieme di radici del suo polinomio generatore, che corrisponde a un sottoinsieme $Z \subseteq \mathbb{Z}_n$. La dimensione del codice è $k = n - |Z|$.
• Simmetria e Rotazione: Viene sfruttata la proprietà che un sottoinsieme $Z$ è un insieme di definizione per un codice ciclico se e solo se è invariante sotto l'azione della moltiplicazione per 2 modulo $n$ (o equivalentemente, sotto la rotazione ciclica della rappresentazione binaria degli indici).
• Costruzione tramite Partizioni: Gli autori definiscono insiemi specifici di vettori binari basati sul loro peso di Hamming ($wt(x)$) e sulla loro struttura simmetrica (es. vettori che sono invarianti o complementari sotto rotazione di $t$ posizioni, dove $m=2t$).
• Stima della Distanza: La distanza minima $d$ e quella duale $d^\perp$ sono stimate utilizzando il limite di BCH (BCH bound), che garantisce che se l'insieme di definizione contiene una sequenza consecutiva di interi (o le loro classi ciclotomiche), la distanza minima è almeno la lunghezza di tale sequenza più uno.

3. Contributi Chiave e Risultati

Il lavoro presenta nuove costruzioni di codici ciclici binari distinte in base alla parità di $m$ e alla sua fattorizzazione.

A. Caso: $m$ è pari

Quando $m = 2t$, gli autori costruiscono due famiglie di codici con parametri $[2^m - 1, 2^{m-1} \pm 1, d]$.

• Risultato: Ottenuti codici con $d \ge 2^{m/2} - 1$ e $d^\perp \ge 2^{m/2}$.
• Significato: Entrambi i parametri (distanza e distanza duale) sono significativamente migliori rispetto alle costruzioni precedenti (es. [26]), superando il limite quadratico e raggiungendo un prodotto $d \cdot d^\perp \approx n$.

B. Caso: $m$ è il prodotto di due primi distinti ($m = p_1 p_2$)

Questa sezione affronta il caso in cui $m$ non è primo, ma un prodotto di due primi ($p_1, p_2$).

• Risultato: Vengono costruiti codici con dimensione $k = 2^{m-1}$ e una distanza minima $d$ che supera notevolmente il limite $\frac{n}{\log_2 n}$.
• Specifiche:
  • Se $p_2 > p_1 \ge 3$: $d \ge \lfloor \frac{2^{p_1 p_2}-1}{p_1 p_2} \rfloor + \dots$ (una somma di termini che cresce rapidamente).
  • Se $p_1 = 2$: $d \ge \frac{2^{2p_2-4}}{2^{p_2}} + \dots$
• Significato: La distanza minima ottenuta è molto più grande del limite della radice quadrata e anche superiore a $\frac{n}{\log_2 n}$, mantenendo al contempo una buona distanza duale.

C. Caso: $m$ è dispari

Vengono presentate due nuove famiglie di codici con parametri $[2^m - 1, 2^{m-1}, d]$.

1. Famiglia 1: $d \ge 2^{(m+1)/2} - 1$ e $d^\perp \ge 2^{(m+1)/2}$.
   • Questi parametri sono uguali o migliori rispetto ai codici di Reed-Muller tagliati (punctured Reed-Muller codes).
2. Famiglia 2: $d \ge 2^{(m+3)/2} - 15$ e $d^\perp \ge 2^{(m-1)/2}$.
   • Rispetto alla costruzione precedente [28] (che aveva $d \ge 3 \cdot 2^{(m-1)/2} - 1$), questa nuova famiglia offre una distanza minima maggiore mantenendo la stessa distanza duale.

• Risultato Asintotico: Per entrambe le famiglie, il prodotto $d \cdot d^\perp$ tende asintoticamente a $2n$.

4. Significato e Impatto

• Superamento dei Limiti Esistenti: Il lavoro dimostra che è possibile costruire codici ciclici in cui sia la distanza minima che quella duale sono elevate, sfidando l'idea che un aumento di $d$ richieda necessariamente una drastica riduzione di $d^\perp$.
• Record di Parametri: Per codici di lunghezza $n = 2^m - 1$ e dimensione $k \approx n/2$, queste costruzioni raggiungono o superano i limiti noti, ad eccezione dei codici di Reed-Muller tagliati, che rimangono un punto di riferimento. In particolare, per $m$ dispari, il prodotto $d \cdot d^\perp \approx 2n$ è un risultato eccezionale, poiché la maggior parte delle costruzioni note si ferma a $d \cdot d^\perp \approx n$.
• Problema Aperto: Gli autori propongono un problema aperto: esiste una famiglia infinita di codici ciclici binari con dimensione vicina a $n/2$ tale che $\limsup_{n \to \infty} \frac{d \cdot d^\perp}{n} > 2$? Attualmente, i risultati di questo paper e dei codici di Reed-Muller suggeriscono che il limite inferiore per questo rapporto è almeno 2.

Conclusione

Questo articolo fornisce una serie di nuove costruzioni teoriche che migliorano sostanzialmente i parametri noti per i codici ciclici binari. Attraverso un'attenta analisi delle classi ciclotomiche e della struttura degli insiemi di definizione, gli autori riescono a bilanciare efficacemente distanza minima e distanza duale, offrendo codici con prestazioni superiori per applicazioni che richiedono alta affidabilità e capacità di correzione degli errori in entrambe le direzioni (codice e duale).