A Hardware Generator for Factor Graph Applications

Simple item page
dc.contributor.authorDemma, James Danielen
dc.contributor.committeechairAthanas, Peter M.en
dc.contributor.committeememberSchaumont, Patrick R.en
dc.contributor.committeememberMcGwier, Robert W.en
dc.contributor.departmentElectrical and Computer Engineeringen
dc.date.accessioned2014-06-09T08:00:42Zen
dc.date.available2014-06-09T08:00:42Zen
dc.date.issued2014-06-08en
dc.description.abstractA Factor Graph (FG -- http://en.wikipedia.org/wiki/Factor_graph) is a structure used to find solutions to problems that can be represented as a Probabilistic Graphical Model (PGM). They consist of interconnected variable nodes and factor nodes, which iteratively compute and pass messages to each other. FGs can be applied to solve decoding of forward error correcting codes, Markov chains and Markov Random Fields, Kalman Filtering, Fourier Transforms, and even some games such as Sudoku. In this paper, a framework is presented for rapid prototyping of hardware implementations of FG-based applications. The FG developer specifies aspects of the application, such as graphical structure, factor computation, and message passing algorithm, and the framework returns a design. A system of Python scripts and Verilog Hardware Description Language templates together are used to generate the HDL source code for the application. The generated designs are vendor/platform agnostic, but currently target the Xilinx Virtex-6-based ML605. The framework has so far been primarily applied to construct Low Density Parity Check (LDPC) decoders. The characteristics of a large basket of generated LDPC decoders, including contemporary 802.11n decoders, have been examined as a verification of the system and as a demonstration of its capabilities. As a further demonstration, the framework has been applied to construct a Sudoku solver.en
dc.description.degreeMaster of Scienceen
dc.format.mediumETDen
dc.identifier.othervt_gsexam:3174en
dc.identifier.urihttp://hdl.handle.net/10919/48599en
dc.publisherVirginia Techen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectFactor Graphen
dc.subjectProbabilistic Graphical Modelen
dc.subjectDigital Designen
dc.subjectSum-Producten
dc.subjectMin-Sumen
dc.subjectBelief Propagationen
dc.subjectHardware Generatoren
dc.titleA Hardware Generator for Factor Graph Applicationsen
dc.typeThesisen
thesis.degree.disciplineComputer Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.levelmastersen
thesis.degree.nameMaster of Scienceen

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Demma_JD_T_2014.pdf
Size:
1.53 MB
Format:
Adobe Portable Document Format
Download

Collections

Masters Theses