Belief Propagation Decoding
An introduction to belief propagation, iterative messages, LLRs and convergence in sparse-graph error correction.
Belief propagation is an iterative inference algorithm widely used for decoding sparse-graph codes. In an LDPC decoder, variable nodes and check nodes exchange messages that represent the current evidence about each bit.
Core idea
For binary channels the messages are often represented as log-likelihood ratios (LLRs). Variable-node updates combine channel evidence with incoming check messages. Check-node updates enforce parity constraints and send revised information back. The process repeats until a stopping condition is met or an iteration limit is reached.
Engineering relevance
Belief propagation is exact on trees but only approximate on graphs containing cycles. Practical implementations therefore need to manage correlation, quantisation, saturation, scheduling and non-convergence. Layered schedules can converge faster than flooding in some cases, but they also change memory-access and dependency patterns.
Key points
- LLRs encode both a bit preference and confidence.
- Variable and check updates perform different parts of the inference.
- Cycles cause messages to become statistically dependent.
- Quantisation and scheduling can materially change hardware behaviour.
Continue exploring.
This page explains established concepts and engineering principles. Proprietary JobMettle methods and internal ThinkQuick technology are not disclosed.