ETD

Archivio digitale delle tesi discusse presso l'Università di Pisa

Tesi etd-09072015-120442


Tipo di tesi
Tesi di laurea magistrale
Autore
PORCU, FRANCESCO
URN
etd-09072015-120442
Titolo
Application of Belief Propagation Algorithms on Factor Graphs: from Sudoku solving to LDPC decoding
Dipartimento
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA INFORMATICA
Relatori
relatore Prof. Luise, Marco
Parole chiave
  • scheduling
  • Binary Erasure Channel
  • message passing
  • LDPC
  • Belief Propagation
  • Factor Graphs
  • sum-product
  • Low Density Parity-check Code
Data inizio appello
25/09/2015
Consultabilità
Completa
Riassunto
Durante lo svolgimento della mia tesi, ho applicato l'algoritmo di Belief Propagation (detto anche "sum-product" algorithm), solitamente usato sulle reti, per testarne la possibilità di utilizzo in diversi ambiti di applicazione. Gli ambiti che ho verificato sono:

1) risoluzione del famoso gioco Sudoku, associando il puzzle a un Factor Graph su cui applicare l'algoritmo;sono stati applicati un algoritmo creato dal matematica T.K. Moon e un algoritmo da me creato basandomi sulle regole matematiche di base usate per la risoluzione del sudoku. successivamente ho aggiunto delle regole di scheduling di propagazione dei messaggi per aumentarne le prestazioni.
2) nella seconda parte ho applicato l'algoritmo per il decoding di Low Density Parity-check Codes su Binary Erasure Channel usando le modifiche e i miglioramenti trovati nella prima parte.

la fine della mia tesi prevedeva il confronto qualitativo delle due parti per vedere se l'algoritmo fosse adatto ai due aspetti trattati.
File