吳家麟臺灣大學：資訊工程學研究所潘廷建Pan, Ting-JianTing-JianPan2007-11-262018-07-052007-11-262018-07-052004http://ntur.lib.ntu.edu.tw//handle/246246/53960因子圖(Factor Graphs)能提供一個一致且有效率的圖形觀點，可用來處理在通訊、訊號處理、和人工智慧領域上，各式各樣有名的編碼和圖形化模型，像低密度同位元檢查碼(Low-Density Parity-Check Codes)、隱藏式馬可夫模型(Hidden Markov Models)、貝氏網路(Bayesian Networks)、馬可夫隨機場模型(Markov Random Fields)、和某些傅立葉轉換(Fourier Transforms)。由於因子圖可如此廣泛地被應用，此圖形上的編解碼演算法設計變成很重要的一件事。這篇論文主要目的就是回顧現有的因子圖演算法：和積演算法(Sum-Product Algorithms)，然後提供一個兼具效率、快速且具彈性的和積演算法來解決一般情形或某些特殊情形的邊際函式問題。Factor graphs provide a unified and efficient graphical perspective for various well-known graphical models as we see in communication, signal processing, and artificial intelligence communities, such as LDPC codes, hidden Markov models, Bayesian networks, Markov random fields, and certain Fourier transforms. Due to the wide applications of factor graphs, the design of the coding algorithm on a factor graph is very important. The main aim of this paper is to review the current coding algorithm on a factor graph, the sum-product algorithm, and to provide an efficient, fast, and flexible sum-product algorithm for solving both general situations and some constrained situations of marginalization problems.Abstract 2 中文摘要 3 TABLE OF CONTENTS 4 LIST OF TABLES 5 LIST OF FIGURES 6 Chapter 1 Introduction 8 Chapter 2 Factor Graphs 11 2.1. Definition of Factor Graphs 11 2.2. Modeling Systems with Factor Graphs 13 2.2.1. Modeling Systems with a Single Factor Graph 13 2.2.2. Modeling Systems with a Joint Factor Graph 19 Chapter 3 Coding on Factor Graphs: The Sum-Product Algorithm 23 3.1. Concepts of the Sum-Product Algorithm 23 3.2. Definitions of the Sum-Product Algorithm 27 3.2.1. The Architecture of the Sum-Product Algorithm 27 3.2.2. Message-Passing Schedules 29 3.2.3. Sum-Product Update Rules 32 3.3. Complexity Analysis of Sum-Product Update Rules 35 Chapter 4 A Novel Sum-Product Algorithm 37 4.1. The Proposed Message-Passing Schedules 37 4.2. Fast Sum-Product Update Rules 44 4.3. The Combined Solution: A Novel Sum-Product Algorithm 50 Chapter 5 A Novel Sum-Product Algorithm with Constraints 52 5.1. Constraints of Partial Marginalization Problems 52 5.2. Constraints of Limited Processors 56 Chapter 6 Conclusions 61 Appendix A Proof of Theorem 1 63 Appendix B Proof of Lemma 1 65 Acknowledgements 67 Reference 67370431 bytesapplication/pdfen-US隱藏式馬可夫模型和積演算法傅立葉轉換低密度同位元檢查碼馬可夫隨機場模型貝氏網路因子圖Fourier TransformFactor GraphHidden Markov ModelLow-Density Parity-Check CodeBayesian NetworkSum-Product AlgorithmMarkov Random Fieldthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53960/1/ntu-93-R91922055-1.pdf