Codici Segreti e Sovrapposizioni Proibite: Un Tuffo nella Teoria dell’Informazione

Ciao a tutti! Oggi voglio portarvi con me in un viaggio affascinante nel mondo dei codici, ma non quelli che aprono casseforti (beh, non direttamente!). Parleremo di codici a blocchi e di una proprietà molto particolare: le sovrapposizioni ristrette. Sembra complicato? Forse un po’, ma vi assicuro che è un campo pieno di sfide intriganti e applicazioni sorprendenti, dalla sincronizzazione dei dati fino all’archiviazione su DNA!

Ma Cosa Sono Queste Sovrapposizioni?

Immaginate di avere delle “parole” (che chiamiamo codeword) fatte di simboli presi da un alfabeto (ad esempio, 0 e 1, oppure A, T, C, G). Ora, pensate a prendere l’inizio di una parola (un prefisso) e la fine di un’altra parola, magari la stessa (un suffisso). Una sovrapposizione (o “overlap” in inglese) si verifica quando un prefisso di una certa lunghezza `t` di una codeword è identico a un suffisso della stessa lunghezza `t` di un’altra codeword (o anche della stessa).

Perché dovremmo preoccuparci di queste sovrapposizioni? Beh, in certi contesti, come nella trasmissione di dati, le sovrapposizioni possono creare ambiguità o problemi, specialmente se ci sono errori come cancellazioni o inserzioni di simboli. Se riusciamo a costruire codici dove certe sovrapposizioni sono *proibite*, possiamo rendere i nostri sistemi di comunicazione o archiviazione più robusti.

Ecco dove entrano in gioco i codici di cui parliamo oggi: i codici `(t1, t2)`-overlap-free. In questi codici, vietiamo tutte le sovrapposizioni la cui lunghezza `t` cade in un intervallo specifico, cioè `t1 ≤ t ≤ t2`. Questo significa che nessun prefisso di lunghezza `t` (con `t` nell’intervallo proibito) di una codeword può essere uguale a un suffisso della stessa lunghezza di qualsiasi altra codeword nel nostro insieme.

Un Po’ di Storia e Tipi Speciali

L’idea di studiare le sovrapposizioni non è nuova. Già negli anni ’60, il matematico Levenshtein si accorse di qualcosa di simile studiando linguaggi decodificabili univocamente. Più tardi, la proibizione totale delle sovrapposizioni (il caso `(1, n-1)`, dove `n` è la lunghezza della codeword) si rivelò utile per la sincronizzazione di frame.

Negli anni, sono state studiate diverse varianti:

• Codici non sovrapponibili (Non-overlapping codes): Vietano tutte le sovrapposizioni tranne quelle banali (lunghezza 0 o lunghezza `n`). Corrispondono ai nostri `(1, n-1)`-overlap-free.
• Codici T-shift synchronization: Legati ai `(n-T, n-1)`-overlap-free.
• Codici κ-weakly mutually uncorrelated: Sono i `(κ, n-1)`-overlap-free, motivati dall’archiviazione dati su DNA.
• Codici `(1, k)`-overlap-free: Studiati più di recente, utili quando le cancellazioni sono più frequenti delle inserzioni.

Addirittura, si è pensato a codici che combinano più proprietà, come essere simultaneamente `(1, k)`- e `(n-k, n-1)`-overlap-free, per ottenere il meglio dei due mondi nella rilevazione di errori.

Quanto Grandi Possono Essere Questi Codici? I Limiti Superiori

Una domanda fondamentale che ci poniamo noi ricercatori è: dato un alfabeto di `q` simboli e una lunghezza `n` per le codeword, quanti codeword possiamo inserire al massimo in un codice `(t1, t2)`-overlap-free? Trovare questo numero massimo, che chiamiamo `S_{t1}^{t2}(q, n)`, è una bella sfida.

Nel mio lavoro, insieme ad altri, abbiamo cercato di stabilire dei limiti superiori (upper bounds). Questi limiti ci dicono: “Non puoi avere più di tot codeword, non importa quanto tu sia bravo a costruirle!”. Abbiamo trovato un limite generale per i codici `(t1, t2)`-overlap-free. L’idea, un po’ semplificata, deriva dal contare quante “finestre” di codeword possono scorrere su una sequenza più lunga senza creare sovrapposizioni proibite.

Per il caso specifico dei codici `(1, k)`-overlap-free, specialmente quando `k` è abbastanza grande (cioè `k ≥ n/2`), siamo riusciti a trovare limiti superiori più stringenti. Qui entra in gioco un concetto affascinante: le parole primitive. Si scopre che, in questi casi, tutte le codeword e anche le loro versioni “ruotate” (shift ciclici) devono essere primitive (cioè non ripetizioni di una sequenza più corta) e distinte tra loro. Questo ci dà un modo per contare e limitare il numero massimo di codeword possibili, usando strumenti matematici come la funzione di Möbius.

Un’osservazione interessante è che per certi tipi di codici, come i `(t1, t2)`-overlap-free con `t2 < n/2`, il problema di trovare la dimensione massima per una lunghezza `n` grande può essere ricondotto a un problema simile ma con lunghezza `2*t2`. Questo semplifica un po' le cose!

Costruire Questi Codici: L’Arte della Creazione

Bello sapere i limiti, ma come si costruiscono *effettivamente* questi codici? Qui entra in gioco la creatività matematica! Ci sono vari metodi, spesso basati su un’idea elegante proposta originariamente per i codici non sovrapponibili.

L’idea base (che abbiamo generalizzato) è partire da una divisione dell’alfabeto Σ in due insiemi, `L1` e `R1`. Poi, ricorsivamente, si definiscono nuovi insiemi `Li` e `Ri` combinando quelli precedenti (`Li` contiene certe concatenazioni `Lj * Rk` dove `j+k=i`, e `Ri` le altre). Le codeword finali sono poi costruite concatenando un elemento da un `Li` con uno da un `R(n-i)`. La magia sta nel fatto che, se si scelgono bene queste partizioni, le sovrapposizioni “cattive” vengono automaticamente evitate grazie alle proprietà intrinseche di questi insiemi `L` e `R`.

Nel nostro lavoro, abbiamo adattato e ampliato queste idee:

• Costruzione 2: Per i codici `(1, k)`-overlap-free (con `k ≥ n/2`). Qui concateniamo parole speciali `Li Rj` (dove `i+j > k`) con sequenze di `L` a sinistra e `R` a destra fino a raggiungere la lunghezza `n`.
• Costruzione 3: Per i codici `(k, n-1)`-overlap-free (weakly mutually uncorrelated). Abbiamo migliorato una costruzione esistente mostrando che spesso si possono aggiungere più codeword di quanto si pensasse inizialmente.
• Costruzione 4 e 5: Per i codici generici `(t1, t2)`-overlap-free. Una si basa sull’aggiungere simboli a codici `(1, t2)`-overlap-free, l’altra è un’espansione più sofisticata simile alla Costruzione 3.
• Costruzione 6: Per i codici che sono *simultaneamente* `(1, k)`- e `(n-k, n-1)`-overlap-free (per `n > 2k`). Combina idee dai codici non sovrapponibili e dalla nostra Costruzione 2.

Un aspetto importante è capire quando un codice costruito è massimale (cioè non si può aggiungere nessun’altra codeword senza violare le regole) o addirittura massimo (cioè ha il numero più alto possibile di codeword). Abbiamo anche approfondito questo, caratterizzando i codici `(1, k)`-overlap-free massimali ottenibili dalla nostra Costruzione 2.

E Quanto Grandi *Riusciamo* a Farli? I Limiti Inferiori

Le costruzioni non servono solo a creare codici utilizzabili, ma anche a darci dei limiti inferiori (lower bounds) sulla dimensione massima `S_{t1}^{t2}(q, n)`. Ogni codice che riusciamo a costruire ci dice: “La dimensione massima è *almeno* questa!”.

Usando le nostre costruzioni, abbiamo derivato nuove formule per i limiti inferiori. Ad esempio, per i codici `(1, k)`-overlap-free, abbiamo trovato un limite inferiore che dipende da `q`, `n`, `k` e da una scelta ottimale di come partizionare l’alfabeto iniziale. Questo limite si rivela particolarmente interessante:

• Per `k=2`, coincide con il valore esatto già noto!
• Quando `q` (la dimensione dell’alfabeto) è grande rispetto a `k`, il nostro limite inferiore è abbastanza vicino al limite superiore che avevamo trovato, differendo solo per un fattore costante. Questo è un ottimo risultato, significa che abbiamo quasi “intrappolato” il valore vero!
• Quando `q` è piccolo, il divario tra limite inferiore e superiore può essere ancora grande, lasciando spazio per future ricerche.

Abbiamo derivato limiti inferiori anche per i codici `(t1, t2)`-overlap-free generici e per quelli simultaneamente `(1, k)`- e `(n-k, n-1)`-overlap-free.

Confronto e Prospettive Future

Quindi, a che punto siamo? Abbiamo fatto passi avanti nel capire questi codici con sovrapposizioni ristrette. Abbiamo nuovi limiti superiori e inferiori, e metodi concreti per costruirli. Per i codici `(1, k)`, specialmente con alfabeti grandi, la nostra comprensione è piuttosto buona, con limiti inferiore e superiore relativamente vicini.

Per i codici `(t1, t2)` più generali, invece, il divario tra ciò che sappiamo essere il massimo possibile (limite superiore) e ciò che sappiamo costruire (limite inferiore) è ancora significativo. C’è ancora molto lavoro da fare per trovare limiti più stringenti o costruzioni migliori!

Altre direzioni future? Potremmo cercare di implementare algoritmi efficienti basati sulle nostre costruzioni per trovare codici massimi per valori specifici di `q`, `n`, `k`. Oppure, studiare se le idee usate per codici a lunghezza variabile o bidimensionali non sovrapponibili possono essere estese a queste nuove classi di codici con restrizioni più generali sulle sovrapposizioni. È un campo ancora pieno di domande aperte e potenziali scoperte!

Spero che questo piccolo tour nel mondo dei codici con sovrapposizioni ristrette vi abbia incuriosito. È un esempio di come la matematica pura possa avere implicazioni concrete e portare a soluzioni eleganti per problemi tecnologici complessi.

Fonte: Springer