Capacity Achieving Codes with Bounded Complexity

Speaker: Dr Henry Pfister , LTHC


Error-correcting codes which employ iterative decoding algorithms are now considered state of the art in communications. There is now a large collection of code families which achieve a small gap to capacity with feasible decoding complexity. Examples are low-density parity-check (LDPC) codes, irregular repeat-accumulate (IRA) codes, and Raptor codes. For each of these code families, one can construct code sequences which provably achieve capacity on the binary erasure channel (BEC). In each case, however, the decoding complexity becomes unbounded as the gap to capacity vanishes. This talk will focus on recently constructed code families whose complexity remains bounded as the gap to capacity vanishes. Assuming only basic knowledge of LDPC codes, three closely related ensembles will be described: IRA codes, accumulate-repeat-accumulate (ARA) codes, and accumulate-LDPC (ALDPC) codes. Using the duality between these ensembles and simplified approach to density evolution, we will construct a variety of codes which achieve capacity with bounded complexity. This is joint work with Igal Sason and Ruediger Urbanke.