Failures and Error Floors of Iterative Decoders

This chapter presents a study of graph substructures and corresponding error patterns involved in decoding failures on various channels under different iterative message passing and linear programming decoding algorithms. The intriguing structural dependence among these subgraphs, called trapping sets, suggests a comprehensive framework for studying the error floor performance of LDPC codes, as well as for designing codes with guaranteed error floor performance on the binary symmetric channel, additive white Gaussian noise channel and other channels. The problem treated in this chapter is one of the major challenges in modern coding theory. The topological relationship among trapping sets advances our fundamental understanding of the relationship between graphical code representations and the performance of iterative decoding algorithms on several core channel models. In particular, it serves as a foundation for elucidating the relationship between various decoding algorithms and lead to the design of LDPC codes with a superior performance in the error floor region.