Decoding Codes on Graphs: Probabilistic Decoding

Iterative decoding is a widely used technique in modern communications systems. The Low Density Parity Check (LDPC) codes of Gallager were the earliest codes for which iterative decoding techniques were defined. These codes along with a simple iterative decoding algorithm were introduced in the first part of this article. Here we describe a probabilistic iterative decoding scheme, also proposed by Gallager, and show how many modern iterative decoding algorithms are derived from his basic scheme.