Near-Optimum Coding for q-ary Symmetric Channel with Application to Space Communications

Questa Tesi aspira a mostrare un codice a livello di pacchetto, che abbia performance molto vicine a quello ottimo, per progetti di comunicazioni Satellitari. L’altro scopo di questa Tesi è quello di capire se rimane ancora molto più difficile maneggiare direttamente gli errori piuttosto che le erasures. Le applicazioni per comunicazioni satellitari ora come ora usano tutte packet erasure coding per codificare e decodificare l’informazione. La struttura dell’erasure decoding è molto semplice, perché abbiamo solamente bisogno di un Cyclic Redundancy Check (CRC) per realizzarla. Il problema nasce quando abbiamo pacchetti di dimensioni medie o piccole (per esempio più piccole di 100 bits) perché in queste situazioni il costo del CRC risulta essere troppo dispendioso. La soluzione la possiamo trovare utilizzando il Vector Symbol Decoding (VSD) per raggiungere le stesse performance degli erasure codes, ma senza la necessità di usare il CRC. Per prima cosa viene fatta una breve introduzione su come è nata e su come si è evoluta la codifica a livello di pacchetto. In seguito è stato introdotto il canale q-ary Symmetric Channel (qSC), con sia la derivazione della sua capacità che quella del suo Random Coding Bound (RCB). VSD è stato poi proposto con la speranza di superare in prestazioni il Verification Based Decoding (VBD) su il canale qSC. Infine, le effettive performance del VSD sono state stimate via simulazioni numeriche. I possibili miglioramenti delle performance, per quanto riguarda il VBD sono state discusse, come anche le possibili applicazioni future. Inoltre abbiamo anche risposto alla domande se è ancora così tanto più difficile maneggiare gli errori piuttosto che le erasure.

Architettura di supporto al peer-to-peer gaming basata su network coding

La popolarita` dei giochi online e` in crescita, ma allo stesso tempo le architetture proposte dagli sviluppatori e le connessioni di cui sono dotati gli utenti sembrano restare non adeguate a questo. Nella tesi si descrive un'architettura peer-to-peer che riesce ad effettuare una riduzione nella perdita dei pacchetti grazie al meccanismo del Network Coding senza effetti collaterali per la latenza.

A Multilevel Gradient Method for Optimization Problems

I problemi di ottimizzazione di dimensione finita di larga scala spesso derivano dalla discretizzazione di problemi di dimensione infinita. È perciò possibile descrivere il problema di ottimizzazione su più livelli discreti. Lavorando su un livello più basso di quello del problema considerato, si possono calcolare soluzioni approssimate che saranno poi punti di partenza per il problema di ottimizzazione al livello più fine. I metodi multilivello, già ampiamente presenti in letteratura a partire dagli anni Novanta, sfruttano tale caratteristica dei problemi di ottimizzazione per migliorare le prestazioni dei metodi di ottimizzazione standard. L’obiettivo di questa tesi è quello di implementare una variante multilivello del metodo del gradiente (MGM) e di testarlo su due diversi campi: la risoluzione delle Equazioni alle Derivate Parziali la ricostruzione di immagini. In questo elaborato viene illustrata la teoria dello schema multilivello e presentato l’algoritmo di MGM utilizzato nei nostri esperimenti. Sono poi discusse le modalità di utilizzo di MGM per i due problemi sopra presentati. Per il problema PDE, i risultati ottenuti mostrano un ottimo comportamento di MGM rispetto alla implementazione classica ad un livello. I risultati ottenuti per il problema di ricostruzione di immagini, al contrario delle PDEs, evidenziano come MGM sia efficace solo in determinate condizioni.