Talk abstract:
Analysis and Design of Iterative Decoding
Systems
Thomas J. Richardson and Ruediger
Urbanke
Bell Laboratories
Lucent Technologies
trj@lucent.com
ruediger@lucent.com
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
Back to Codes, Systems and Graphical Models