Prerequisites & Notation

Before You Begin

This chapter develops the sum-product algorithm — belief propagation — in detail. The reader must be comfortable with factor graphs (Chapter 17) and the basic idea of local message passing. Familiarity with LDPC codes from Book ITA Chapter 12 is helpful for Section 18.2, and familiarity with the Kalman filter (Chapter 10) helps frame the Gaussian BP section.

Factor graphs and bipartite structure(Review ch17)
Self-check: Can you draw the factor graph of a joint distribution and identify its tree-width?
Trees, cycles, girth, and loopy BP(Review ch17)
Self-check: Can you explain why sum-product is exact on trees?
LDPC codes and parity-check matrices
Self-check: Can you state the syndrome test $\mathbf{H}\mathbf{x} = \mathbf{0}$ ?
Multivariate Gaussian distribution and information form(Review ch07)
Self-check: Can you convert between $(\boldsymbol{\mu}, \boldsymbol{\Sigma})$ and canonical $(\mathbf{h}, \mathbf{J})$ form?
Log-likelihood ratios(Review ch01)
Self-check: Can you write the LLR of a BSC $(p)$ ?

Notation for This Chapter

Symbol	Meaning	Introduced
$\mu_{i \to a}(x_i)$	Message from variable node $i$ to factor node $a$	s01
$\mu_{a \to i}(x_i)$	Message from factor node $a$ to variable node $i$	s01
$b_i(x_i)$	Belief (approximate marginal) at variable node $i$	s01
$\ell_{i}$	Log-likelihood ratio at bit $i$ (LDPC decoding)	s02
$L_{a \to i}, L_{i \to a}$	Log-domain messages (LLRs) on directed edges	s02
$\lambda(x), \rho(x)$	Variable-node and check-node degree distributions (LDPC ensemble)	s02
$\operatorname{sgn}(\cdot)$	Sign function	s02
$\phi(x) = -\log\tanh(\|x\|/2)$	Check-node transform in log-domain BP	s02
$\mathbf{h}_{a \to i}, J_{a \to i}$	Canonical (information-form) message parameters in Gaussian BP	s04
$\epsilon^*$	BP decoding threshold (BEC)	s02

← Ch 17 The Message-Passing Rules