Shortest LCD embeddings of binary, ternary and quaternary linear codes

Problematica
I codici lineari con duali complementari (codici LCD) sono un'area di ricerca significativa nella teoria della codifica, in particolare per la loro resistenza agli attacchi side-channel e agli attacchi di iniezione di guasti. Sebbene sia noto che ogni codice lineare su $\mathbb{F}_q$ ($q \ge 4$) è equivalente a un codice LCD, e risultati simili esistano per $\mathbb{F}_{q^2}$, i limiti per le distanze minime dei codici LCD su $\mathbb{F}_2$, $\mathbb{F}_3$ e per i codici LCD ermitiani su $\mathbb{F}_4$ rimangono sconosciuti per molte lunghezze e dimensioni. Una sfida centrale nella teoria della codifica è determinare la massima distanza minima per una data lunghezza e dimensione. Questo articolo affronta il problema specifico dell'embedding di codici lineari arbitrari in codici LCD, con l'obiettivo di trovare il più breve tale embedding (minimo incremento di lunghezza) e di utilizzare questo metodo per costruire nuovi codici LCD ottimali per distanza.

Metodologia
Gli autori introducono un approccio sistematico per embeddare un dato codice lineare $C$ in un codice LCD $\tilde{C}$ aggiungendo il numero minimo di colonne alla sua matrice generatrice. La metodologia procede come segue:

1. Fondamento Teorico: L'articolo stabilisce che il numero minimo di colonne ($m$) richiesto per embeddare un codice $[n, k]$ $C$ in un codice LCD è esattamente uguale alla dimensione $\ell$ dell'hull di $C$ (dove $\text{Hull}(C) = C \cap C^\perp$). Di conseguenza, la lunghezza del più breve embedding LCD è $n + \ell$.
2. Caratterizzazione Strutturale: Gli autori caratterizzano la matrice generatrice di un embedding LCD più breve. Se $G$ è una matrice generatrice di $C$ decomposta in una parte che genera l'hull, $G(\text{Hull}(C))$, e una parte rimanente $A$, allora un embedding LCD più breve è generato da una matrice della forma:
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   dove $D$ è una matrice $\ell \times \ell$ invertibile e $C$ è una matrice $(k-\ell) \times \ell$ arbitraria. L'articolo prova che l'aggiunta di una matrice invertibile alle righe corrispondenti all'hull e di una matrice arbitraria alle restanti righe produce sempre un embedding LCD più breve.
3. Strategia di Costruzione: Gli autori applicano questo metodo di embedding a codici lineari noti per essere ottimali per distanza (specificamente codici ternari e quaternari) che non sono essi stessi LCD. Calcolando la dimensione dell'hull di questi codici esistenti e aggiungendo le colonne necessarie secondo la struttura derivata, generano nuovi codici LCD.

Contributi Chiave e Risultati
L'articolo fornisce sia limiti teorici che costruzioni concrete:

• Risultati Teorici:

  • Dimostra che la lunghezza del più breve embedding LCD di un codice $[n, k]$ con dimensione dell'hull $\ell$ è $n + \ell$.
  • Caratterizza tutte le possibili forme delle matrici generatrici per questi embedding più brevi, mostrando che sono equivalenti all'aggiunta di una matrice invertibile alle righe che generano l'hull.
  • Dimostra che la lunghezza del più breve embedding LCD di un codice $C$ è identica a quella del suo hull, $\text{Hull}(C)$.

• Nuove Costruzioni di Codici:
  Utilizzando il metodo di embedding LCD più breve su codici lineari esistenti, gli autori hanno costruito diversi nuovi codici LCD con parametri che migliorano le distanze minime note:

  • Codici LCD Ternari:
    • $[23, 4, 14]$: Migliora la distanza minima nota da 13 a 14.
    • $[23, 5, 12]$: Migliora la distanza minima nota da 11 a 12.
    • $[24, 6, 12]$: Migliora la distanza minima nota da 11 a 12.
    • $[25, 5, 14]$: Migliora la distanza minima nota da 13 a 14.
  • Codice LCD Ermitiano Quaternario:
    • $[21, 10, 8]$: Migliora la distanza minima nota da 7 a 8.
      Gli autori notano che per i nuovi parametri $[23, 4, 14]$ e $[23, 5, 12]$, hanno trovato rispettivamente 226 e 38 codici inequivocabili. Questi codici sono ottimali per distanza e inequivocabili rispetto ai codici attualmente presenti nel database BKLC (Best Known Linear Codes).

Significato
L'articolo sostiene che il metodo di embedding LCD più breve è uno strumento utile per trovare codici LCD ottimali per distanza su vari campi. Determinando il numero preciso di colonne necessarie e caratterizzando la loro struttura, il metodo fornisce un percorso costruttivo per migliorare la distanza minima di codici lineari noti quando convertiti in codici LCD. I risultati dimostrano che questo approccio riesce a produrre nuovi codici con distanze minime superiori di un'unità rispetto ai codici precedentemente noti per specifici parametri ternari e quaternari.

Limitazioni e Direzioni Future
Gli autori riconoscono una limitazione nel loro approccio: poiché lo spazio di ricerca per le matrici invertibili e arbitrarie aggiunte è eccessivamente grande, è difficile garantire di trovare l'embedding specifico che produca la massima distanza minima assoluta per un dato codice. Suggeriscono che la ricerca futura dovrebbe concentrarsi sullo sviluppo di metodi per selezionare le matrici aggiunte in modo più strategico per massimizzare la risultante distanza minima o per determinare se le matrici aggiunte possano essere ulteriormente ristrette fino all'equivalenza per ridurre lo spazio di ricerca.