Improved Capacity Upper Bounds for the Deletion Channel using a Parallelized Blahut-Arimoto Algorithm

1. Il Problema: Il Canale di Cancellazione Binario (BDC)

Il documento affronta il problema fondamentale della determinazione della capacità del canale di cancellazione binario (BDC - Binary Deletion Channel).

• Definizione: Il BDC riceve una stringa di bit $x$ e cancella indipendentemente ogni bit con una probabilità fissa $d$. L'output è una sottosequenza della stringa originale.
• Sfida: A differenza del canale di cancellazione binario (BEC), dove la posizione dei bit cancellati è nota (sostituiti da "?"), nel BDC la sincronizzazione tra mittente e ricevente viene persa. Non si sa quale bit in uscita corrisponda a quale bit in ingresso.
• Stato dell'arte: Sebbene esistano limiti inferiori e superiori per la capacità $C(d)$, questi sono ancora ampi. I limiti superiori attuali sono ottenuti approssimando numericamente la capacità di versioni a "lunghezza finita" del canale ($C_n(d)$) utilizzando l'algoritmo di Blahut-Arimoto (BAA).
• Ostacolo principale: La complessità computazionale e di memoria dell'algoritmo BAA scala male con la lunghezza dell'input $n$. Le implementazioni naive diventano proibitive già per $n$ piccoli (es. $n > 17$). Le implementazioni ottimizzate precedenti (es. Rubinstein e Con, 2023) hanno raggiunto $n=28$, ma si sono scontrate con limiti di memoria e tempo per $n$ superiori.

2. Metodologia e Ottimizzazioni

Gli autori propongono un'implementazione ottimizzata dell'algoritmo Blahut-Arimoto sfruttando la parallelizzazione su GPU (CUDA) e tecniche di enumerazione dinamica.

A. Parallelizzazione GPU dell'Algoritmo BAA

L'algoritmo BAA iterativo richiede il calcolo di distribuzioni di output e funzioni ausiliarie su tutti gli input possibili ($2^n$) e output possibili.

• Strategia: Sfruttare il fatto che i calcoli per diversi input $x$ o diversi output $y$ sono indipendenti.
• Implementazione CUDA:
  • Ogni blocco del kernel CUDA è assegnato a un diverso input $x$.
  • All'interno di ogni blocco, fino a 1024 thread lavorano in parallelo per calcolare le somme parziali necessarie per la funzione ausiliaria $W^{(t)}(x)$, suddividendo l'insieme delle sottosequenze di output.
  • Questo approccio riduce drasticamente il tempo di esecuzione rispetto alle CPU, permettendo di gestire spazi di stati molto più grandi.

B. Enumerazione Efficiente delle Sottosequenze e Supersequenze

Un collo di bottiglia critico è l'enumerazione delle sottosequenze (per il calcolo delle probabilità di transizione) e delle supersequenze (per il calcolo della distribuzione di output).

• Enumerazione delle Sottosequenze (Sez. 4):
  • Invece di iterare su tutti i $\binom{n}{k}$ sottoinsiemi (impossibile per GPU con memoria limitata), gli autori usano un algoritmo di "unranking" basato sulla programmazione dinamica.
  • Vengono pre-calcolate due tabelle: NextPos (posizione della prossima occorrenza di 0 o 1) e Count (numero di sottosequenze di una certa lunghezza rimanenti).
  • Ogni thread può generare la $j$-esima sottosequenza in tempo $O(k)$ senza memorizzare tabelle di ricerca massive, permettendo una distribuzione efficiente del carico di lavoro tra i thread.
• Enumerazione delle Supersequenze (Sez. 5):
  • Per calcolare le probabilità di output, è necessario enumerare le supersequenze di lunghezza $n$ che contengono un dato output di lunghezza $k$.
  • Viene utilizzata una mappatura biunivoca tra indici e sottoinsiemi di bit "non corrispondenti" (non usati per allineare la stringa originale).
  • Anche qui, un algoritmo di unranking permette di generare le supersequenze in tempo lineare $O(n)$ per thread, evitando l'uso di grandi strutture dati in memoria.

C. Ottimizzazione della Memoria

L'implementazione evita di memorizzare l'intera matrice di transizione del canale (che richiederebbe spazio esponenziale). Invece, calcola le probabilità di transizione $P(y|x)$ on-demand utilizzando le tabelle pre-calcolate per canali più piccoli (approccio ricorsivo simile a quello di Rubinstein e Con), ma accelerato dall'architettura parallela.

3. Contributi Chiave

1. Implementazione GPU: Prima implementazione su larga scala dell'algoritmo Blahut-Arimoto per il canale di cancellazione sfruttando la potenza di calcolo parallelo delle GPU.
2. Estensione del limite di $n$: Gli autori sono riusciti a calcolare limiti superiori accurati per lunghezze di input fino a $n = 31$ (in particolare per $k \le 18$ quando $n=31$), superando il precedente record di $n=28$.
3. Nuovi limiti di capacità: Hanno ottenuto limiti superiori migliorati per la capacità $C(d)$ per l'intero intervallo di probabilità di cancellazione $d$.

4. Risultati Principali

• Limiti per $n=29$ e $n=31$: Sono stati calcolati limiti superiori per $C_{n,k}$ (capacità del canale di cancellazione esatto) per tutte le coppie $(n, k)$ con $n \le 29$ e per $n=31, k \le 18$.
• Regime ad alto rumore ($d \to 1$): Combinando i nuovi limiti ottenuti per $d=0.64$ con un risultato asintotico di Rahmati e Duman (2015), gli autori derivano un nuovo limite superiore per l'alta probabilità di cancellazione:
  $$C(d) \le 0.3578(1 - d) \quad \text{per ogni } d \ge 0.64$$
  Questo migliora il limite precedente di Rubinstein e Con ($0.3745(1-d)$ per $d \ge 0.68$).
• Risorse: I calcoli sono stati eseguiti su una GPU RTX 5070 Ti. Per $n=29$, alcune configurazioni hanno richiesto fino a 5 giorni di calcolo (1100 iterazioni).

5. Significato e Impatto

• Avanzamento Teorico: Il lavoro riduce il divario tra i limiti inferiori e superiori noti per la capacità del BDC, fornendo una stima più precisa di quanto sia possibile trasmettere dati in presenza di errori di sincronizzazione.
• Metodologia Computazionale: Dimostra che l'uso di GPU e algoritmi di enumerazione intelligente (unranking) può superare i limiti di memoria e tempo che hanno finora impedito l'analisi esatta di canali di cancellazione per lunghezze maggiori.
• Riproducibilità: Il codice sorgente dell'implementazione è stato reso pubblico su GitHub, permettendo alla comunità di ricerca di verificare i risultati e costruire su questa base per futuri studi.

In sintesi, il paper rappresenta un passo significativo verso la risoluzione del problema aperto della capacità del canale di cancellazione binario, dimostrando come l'ottimizzazione hardware/software possa spingere i confini della teoria dell'informazione computazionale.