Turbo Decoding as an Instance of Pearl's "Belief Propagation" Algorithm

By Robert J. McEliece, David John Cameron MacKay, Jung-Fu (Thomas) Cheng. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Kernel Belief Propagation (2011, methodology): “Belief propagation is an inference algorithm for graphical models that has been widely and successfully applied in a great variety of domains, including vision (Sudderth et al., 2003), protein folding (Yanover & Weiss, 2002), and turbo decoding (McEliece et al., 1998).”
Loopy Belief Propagation for Approximate Inference: An Empirical Study (1999, background): “These theo rems, which may have nothing directly to do with coding or decoding will show that in some sense belief propagation "converges with high probability to a near-optimum value" of the desired belief on a class of loopy DAGs [10].”
Collective Classification in Network Data (2008, methodology): “This led to the development of the approximate inference algorithm that we, in this report, refer to as loopy belief propagation (LBP) (also known as sum product algorithm) [31, 40, 32].”
Information Theory, Inference, and Learning Algorithms (2004, background): “See (Wiberg, 1996; Frey, 1998; McEliece et al., 1998) for further discussion of the sum–product algorithm.”
Generalized approximate message passing for estimation with random linear mixing (2010, background): “ons of the two algorithms, max-sum GAMP and sum-product GAMP, respectively. In communications and signal processing, BP is best known for its connections to iterative decoding in turbo and LDPC codes [24]–[26]. However, while turbo and LDPC codes typically involve computations over ﬁnite ﬁelds, BP h”
Factor graphs and the sum-product algorithm (2001, methodology): “Bayesian networks and belief propagation with applications in coding theory were MacKay and Neal [21]; more recently, [19], [24] develop a view of the “turbo decoding” algorithm [5] as an instance of probability propagation in a Bayesian network model of a code.”
Using linear programming to Decode Binary linear codes (2005, background): “842696 on the belief-propagation algorithm [11], where messages are iteratively sent across a factor graph modeling the structure of the code.”
Fault Identification Via Nonparametric Belief Propagation (2009, background): “When the variables xi take on only a finite number of values, the messages may be represented as vectors; the resulting algorithm has proven effective in many coding applications including low-density parity check (LDPC) codes [42].”
Channel coding: The road to channel capacity (2006, methodology): “nternal communication (message-passing); • Symbol edges are used for external communication (I/O). Connections shortly began to be made to a variety of related work in various other ﬁelds, notably in [130], [131], [129], [127]. In addition to the Viterbi and BCJR algorithms for decoding trellis code”
Adaptive computation and machine learning (1998, result): “An important conjecture, supported both by emprirical evidence and results in coding theory, is that the simple message-passing algorithm of [416] yields reasonably good approximations in the multiply connected case (see [385] for details).”
Belief Propagation, Dykstra's Algorithm, and Iterated Information Projections (2010, background): “The seminal practical confirmation occurred with the advent of turbo codes [3], [4] which breached previous barriers in approaching the Shannon limit of reliable communications over a noisy channel.”
Hyperparameter Learning for Graph Based Semi-supervised Learning Algorithms (2006, methodology): “Markov Chain Monto Carlo (Neal, 1993; Mackay), (loopy/generalized) belief propagation (Yedidia et al., 2005; Murphy et al., 1999; McEliece et al., 1998), expectation propagation (Minka, 2001a; Minka, 2001b), variational methods (Wainwright & Jordan, 2005; Wainwright & Jordan, 2003; Jordan et al.”
Residual Splash for Optimally Parallelizing Belief Propagation (2009, methodology): “Nonetheless, BP on “loopy” graphs (often referred to as Loopy BP ) is used extensively with great success as an approximate inference algorithm [McEliece et al., 1998, Sun et al., 2003, Yedidia et al., 2003, Yanover and Weiss, 2002, Yanover et al., 2007].”