The equivalent condition for GRL codes to be MDS, AMDS or self-dual

Sintesi Tecnica: Condizioni Equivalenti per Codici GRL per essere Non-GRS MDS, AMDS o Auto-duali

Definizione del Problema
I codici Maximum Distance Separable (MDS) e Almost MDS (AMDS), insieme ai codici auto-duali, possiedono significative proprietà algebriche e sono ampiamente applicati nei sistemi di comunicazione, nell'archiviazione dei dati, nella codifica quantistica e nella crittografia. Mentre i codici di Reed-Solomon (RS) sono una classe nota di codici MDS, la costruzione di codici che non siano equivalenti ai codici RS (non-RS) rimane un'area di ricerca critica per espandere la diversità delle famiglie di codici disponibili. Lavori precedenti da parte di Roth e Lempel [20], e successivamente da parte di Wu et al. [21] e [22], hanno costruito classi specifiche di codici MDS non-RS mediante l'aumento della matrice generatrice dei codici RS con due o tre colonne aggiuntive. Questo articolo affronta la necessità di generalizzare ulteriormente queste costruzioni e di stabilire precise condizioni algebriche sotto le quali questi codici generalizzati (e i loro duali) esibiscono proprietà MDS, AMDS o auto-duali senza essere equivalenti ai codici RS.

Metodologia
Gli autori introducono una classe di codici Generalized Roth-Lempel (GRL), denotata come $GRL_k(\alpha, v, A_{l \times l})$, definita su un campo finito $F_q$. Questa costruzione generalizza i modelli precedenti sostituendo le specifiche matrici di aumento utilizzate in [21] e [22] con una matrice arbitraria invertibile $A_{l \times l} \in GL_l(F_q)$. Nello specifico, il documento si concentra sul caso in cui $l=3$, denotato come $GRL_k(\alpha, v, A_{3 \times 3})$.

La metodologia impiega i seguenti approcci tecnici:

1. Analisi della Matrice Generatrice: Gli autori definiscono la matrice generatrice $G_4$ per il codice $GRL_k(\alpha, v, A_{3 \times 3})$, che consiste in una struttura di tipo Vandermonde standard aumentata da tre colonne derivate dalla matrice $A_{3 \times 3}$.
2. Verifica Non-RS: Per dimostrare che i codici sono non-RS, gli autori utilizzano il Lemma 5 (una caratterizzazione dei codici RS tramite le voci della matrice generatrice) e dimostrano che la specifica struttura delle colonne aumentate impedisce al codice di soddisfare le condizioni necessarie per l'equivalenza RS quando $k > 3$.
3. Condizioni MDS e AMDS: Utilizzando il Lemma 6 (che afferma che un codice $[n, k]$ è MDS se e solo se ogni $k$ colonne della sua matrice generatrice sono linearmente indipendenti), gli autori analizzano i determinanti di tutte le possibili sottomatrici $k \times k$ formate dalla matrice generatrice. Ciò comporta un'estesa analisi dei casi riguardante l'inclusione delle colonne aumentate ($u_1, u_2, u_3$) nelle sottomatrici.
4. Costruzione della Matrice di Controllo di Parità: Per l'analisi dell'auto-dualità, gli autori derivano una matrice di controllo di parità esplicita $H_5$ per il codice GRL. Utilizzano il Lemma 4 (proprietà delle somme di potenze di elementi di un campo pesate per differenze inverse) per verificare la condizione di ortogonalità $G H^T = 0$.
5. Criteri di Auto-dualità: La condizione per l'auto-dualità ($C = C^\perp$) è stabilita richiedendo che la matrice generatrice e la matrice di controllo di parità spanino lo stesso spazio, portando a vincoli specifici sul vettore $v$ e sulla matrice $A_{3 \times 3}$.

Contributi Chiave e Risultati

1. Proprietà Non-RS: Il Teorema 7 stabilisce che per $k > 3$, il codice $GRL_k(\alpha, v, A_{3 \times 3})$ è strettamente non-GRS (Generalized Reed-Solomon), indipendentemente dalla scelta dei parametri, a condizione che $A_{3 \times 3} \in GL_3(F_q)$.

2. Condizioni Equivalenti per MDS Non-RS: Il Teorema 8 fornisce condizioni necessarie e sufficienti affinché $GRL_k(\alpha, v, A_{3 \times 3})$ sia MDS. Queste condizioni sono espresse come disuguaglianze che coinvolgono somme di prodotti dei punti di valutazione $\alpha_i$ e le voci di $A_{3 \times 3}$. Nello specifico, per ogni sottoinsieme di dimensione $k-1$ o $k-2$, determinate espressioni polinomiali che coinvolgono le voci della matrice non devono annullarsi.

   • Il Corollario 10 e l'Esempio 11 illustrano queste condizioni con una forma di matrice specifica e un esempio concreto su $F_{11}$, producendo un codice $[8, 4, 5]$.

3. Condizioni Equivalenti per Duali AMDS: Il Teorema 12 determina le condizioni sotto le quali il codice duale $GRL_k^\perp(\alpha, v, A_{3 \times 3})$ è AMDS. Ciò richiede che ogni $k-1$ colonne della matrice generatrice siano linearmente indipendenti, mentre almeno un set di $k$ colonne sia dipendente. Il teorema elenca sei casi specifici che coinvolgono le voci di $A_{3 \times 3}$ e le somme di $\alpha_i$.

   • Il Corollario 13 e l'Esempio 14 forniscono un'istanza specifica su $F_7$, risultando in un codice $[8, 4, 4]$.

4. Matrice di Controllo di Parità e Auto-dualità: Il Teorema 16 costruisce la matrice di controllo di parità $H_5$ per il codice GRL. Partendo da ciò, il Teorema 17 fornisce la condizione equivalente affinché il codice sia auto-duale non-RS. Le condizioni richiedono:

   • $n + 3 = 2k$ (vincolo di dimensione).
   • Il vettore $v$ deve essere proporzionale al vettore delle differenze inverse $u$ (ovvero, $v_i = \lambda u_i$).
   • La matrice $A_{3 \times 3}$ deve soddisfare una specifica relazione quadratica che coinvolge le somme di $\alpha_i$ e $\alpha_i^2$.
   • Gli Esempi 18 e 19 dimostrano la costruzione di tali codici auto-duali su $F_{13}$ e $F_{19}$, rispettivamente. In particolare, l'Esempio 19 evidenzia che i codici GRL auto-duali possono essere costruiti per $q \equiv 3 \pmod 4$, un caso in cui le precedenti costruzioni di codici auto-duali in [22] erano limitate.

Significatività
Il documento sostiene di generalizzare i risultati trovati in [21] e [22] sostituendo le specifiche matrici di aumento con una matrice invertibile generale $A_{3 \times 3}$. La principale significatività risiede nel fornire un quadro unificato per determinare quando questi codici generalizzati possiedono proprietà di distanza ottimali (MDS/AMDS) o l'auto-dualità. Gli autori notano esplicitamente che i loro risultati recuperano i teoremi in [21] come casi speciali. Inoltre, la costruzione di codici auto-duali per $q \equiv 3 \pmod 4$ (Esempio 19) estende l'applicabilità di tali codici oltre i vincoli della letteratura precedente. Il documento conclude che queste condizioni equivalenti permettono la costruzione sistematica di codici non-RS con proprietà desiderabili per applicazioni nelle comunicazioni e nella crittografia.