ETD system

Electronic theses and dissertations repository

 

Tesi etd-09072015-120442


Thesis type
Tesi di laurea magistrale
Author
PORCU, FRANCESCO
URN
etd-09072015-120442
Title
Application of Belief Propagation Algorithms on Factor Graphs: from Sudoku solving to LDPC decoding
Struttura
INGEGNERIA DELL'INFORMAZIONE
Corso di studi
INGEGNERIA INFORMATICA
Supervisors
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 analitico
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