In this talk we will try to give an overview of the current state of knowledge (and lack thereof) of iterative decoding systems. We will speak primarily about LDPCCs and Turbo codes. We will start by showing that virtually all known iterative decoding systems exhibit a threshold phenomenon which characterizes their asymptotic performance. Thresholds may be determined via a process we call density evolution which describes the distributions of extrinsic information produced by each iteration of decoding. In the case of belief propagation density evolution exhibits several special properties. In particular, densites which arise this way satisfy a certain symmetry condition which we call the consistency condition. Further the sequence of densities produced satisfy various monotonicity properties implying in particular that the evolution always converges to a fixed point.

In the case of LDPCCs we have a fast algorithm for computing density evolution which has enabled us to optimize degree sequences yielding codes which perform extremely close to Shannon capacity. We will also describe a method for building efficient encoders for these codes. Many of the best degree sequences admit linear time encoding.

In the case of Turbo codes we do not have a similar fast algorithm but, here, certain ergodicity results show that one can trade-off space for time and thresholds can be reliably computed via Monte-Carlo methods.

[The optimization of LDPCC degree sequences is joint work with Amin Shokrollahi]

Material used during the talk