On the equivalence between additive and linear codes

1. Il Problema

Il campo dei codici correttori di errore ha visto un rinnovato interesse per i codici additivi, specialmente nel contesto dei codici quantistici binari e dei codici quaternari. Sebbene i codici additivi abbiano dimostrato di poter superare le prestazioni dei codici lineari tradizionali (in termini di distanza minima per dati parametri di lunghezza e dimensione), rimane una sfida fondamentale distinguere tra:

1. Codici additivi strettamente additivi (che non sono equivalenti a nessun codice lineare).
2. Codici additivi che sono in realtà equivalenti a codici lineari, ma presentati in una forma non lineare.

La letteratura recente (es. [14], [18]) ha proposto numerosi nuovi codici additivi quaternari con parametri superiori ai limiti noti per i codici lineari. Tuttavia, manca un metodo deterministico ed efficiente per verificare se questi nuovi codici siano effettivamente "nuovi" (strettamente additivi) o se siano semplicemente codici lineari trasformati. Le tecniche esistenti si basano principalmente su metodi geometrici complessi (come pseudo-archi e spread di Desargues), che non sono sempre applicabili o computazionalmente efficienti per tutti i casi.

2. Metodologia

Gli autori sviluppano un framework puramente algebrico basato sulla matrice generatrice del codice, evitando tecniche geometriche. La metodologia si articola nei seguenti punti:

• Rappresentazione e Isomorfismo:

  • Si considera un codice additivo $C$ su $\mathbb{F}_{q^2}$ (in particolare $q=2$, quindi $\mathbb{F}_4$).
  • Si utilizza una mappa $\phi$ che trasforma vettori in $\mathbb{F}_{q^2}^n$ in vettori in $\mathbb{F}_q^{2n}$, permettendo di trattare il codice come un sottospazio lineare su $\mathbb{F}_q$.
  • Si introduce la rappresentazione regolare del campo $\mathbb{F}_{q^2}$ tramite matrici $2 \times 2$ (gruppo di Singer). L'elemento primitivo $\omega$ è mappato in una matrice $M_\omega$.

• Criterio di Equivalenza (Teorema 3.1):

  • Un codice additivo $C$ è equivalente a un codice lineare su $\mathbb{F}_{q^2}$ se e solo se esiste una matrice invertibile $R \in GL_k(\mathbb{F}_q)$ e una matrice diagonale a blocchi $A$ tale che:
    $$RG = G(AM_\omega A^{-1})$$
    dove $G$ è la matrice generatrice del codice additivo.

• Condizioni Necessarie (Teoremi 3.2 e 3.3):

  • Teorema 3.2: Se $C$ è equivalente a un codice lineare, deve esistere una matrice $R$ nello spazio vettoriale delle matrici che preservano i sottospazi delle colonne di $G$, tale che $R$ non abbia autovalori in $\mathbb{F}_q$. Se una colonna di blocchi di $G$ ha rango 1, il codice è non equivalente a un codice lineare.
  • Teorema 3.3 (Test di Nullità): Gli autori costruiscono un sistema lineare omogeneo $S\mathbf{x} = 0$ derivato dall'equazione matriciale sopra. Se la nullità (dimensione dello spazio nullo) della matrice $S$ è dispari, allora il codice è strettamente additivo (non equivalente a nessun codice lineare).

• Algoritmo Deterministico (Algorithm 1):

  1. Controllo del Rango: Verifica se i blocchi di colonne della matrice generatrice hanno rango 1 (se sì, non è lineare).
  2. Test di Nullità: Costruisce la matrice $S$ e calcola la sua nullità. Se è dispari, il codice è strettamente additivo.
  3. Ricerca nello Spazio Nullo: Se la nullità è pari, si cerca esplicitamente una soluzione $R$ che soddisfi le condizioni di equivalenza.

3. Contributi Chiave

1. Nuovo Criterio Algebrico: Introduzione di un test deterministico basato esclusivamente sulla matrice generatrice, che sostituisce o integra le complesse verifiche geometriche.
2. Caratterizzazione Teorica: Dimostrazione che la parità della nullità di una matrice specifica $S$ è un indicatore sufficiente per la non-equivalenza lineare (Teorema 3.3).
3. Verifica Computazionale: Applicazione del test a codici quaternari riportati in letteratura recente, fornendo prove definitive sulla loro natura.
4. Scoperta di Equivalenze: Identificazione di un codice additivo complementare duale (ACD) che, pur non essendo lineare nella sua forma originale, è equivalente a un codice lineare Hermitiano LCD, migliorando i limiti noti.

4. Risultati Sperimentali

Gli autori hanno applicato il loro algoritmo (implementato in MAGMA) a diverse famiglie di codici:

• Codici Quaternari da [14] (Tabella II):

  • Sono stati verificati diversi codici additivi con parametri che superano i limiti dei codici lineari.
  • Risultato: Tutti i codici verificati (es. parametri [47, 35, 7], [56, 11, 30], [63, 5, 45], ecc.) hanno una nullità(S) dispari (solitamente 1).
  • Conclusione: Questi codici sono strettamente additivi e non equivalenti a nessun codice lineare.

• Codici ACD (Additive Complementary Dual) da [14] (Tabella IV):

  • Sono stati esaminati codici ACD con distanze minime superiori ai limiti noti per i codici Hermitiani LCD.
  • Caso [22, 10, 9]: La nullità(S) è pari (2). Un calcolo diretto ha mostrato l'esistenza di una trasformazione che rende il codice equivalente a un codice lineare Hermitiano LCD su $\mathbb{F}_4$. Questo migliora il record noto in [2, Tabella 6].
  • Altri casi (Linee 5, 6, 10): Hanno mostrato nullità(S) = 1, confermando che sono strettamente additivi.

• Codici ACD da [18] (Costruzione di Plotkin):

  • Dei 10 codici elencati, 5 sono stati scartati immediatamente tramite il controllo del rango (Teorema 3.2), mentre gli altri 5 sono stati confermati come strettamente additivi tramite il calcolo della nullità (Teorema 3.3).

5. Significato e Impatto

Questo lavoro risolve un problema aperto nella teoria dei codici fornendo uno strumento pratico e computazionalmente efficiente per classificare i codici additivi.

• Conferma di Nuovi Codici: Dimostra che molti dei codici additivi più recenti e promettenti sono genuinamente nuovi (strettamente additivi) e non possono essere ridotti a codici lineari, giustificando così il loro studio come entità distinte.
• Miglioramento dei Limiti: Identificando l'equivalenza tra un codice ACD additivo e un codice lineare Hermitiano LCD, gli autori hanno migliorato i parametri conosciuti per i codici lineari, un risultato controintuitivo dato che l'obiettivo era spesso trovare codici non lineari.
• Metodologia Unificata: L'approccio algebrico proposto è generale e può essere applicato a qualsiasi codice additivo, offrendo una via alternativa e spesso più semplice rispetto alle tecniche geometriche tradizionali.

In sintesi, il paper fornisce sia la teoria necessaria per distinguere le classi di codici, sia la prova empirica che i codici additivi offrono un terreno fertile per la scoperta di nuovi parametri ottimali, sia per i codici strettamente additivi che per quelli equivalenti a codici lineari con parametri migliorati.