A Note on Low Density Parity Check Codes for Erasures and Errors
Michael Mitzenmacher · 1998
We analyze low density parity check codes that correct both errors and erasures using a simple decoding scheme. Our framework unifies previous analyses for low density parity check codes and erasure codes. The result is a general class of codes that corrects both errors and erasures, with corresponding simple linear time encoding and decoding algorithms and provable performance guarantees. We also describe how these codes can be applied to yield a new fast algorithm for the setting of of Gaussian noise, and leave several open questions regarding the construction of these codes and the associated decoding algorithms. 1 Introduction Simple linear time erasure codes with nearly optimal correction properties were introduced and analyzed in [2, 3]. The analysis of these codes are based on the analysis of a simple stochastic process on an irregular random bipartite graph. In [4], a similar analysis was used to develop and prove bounds on the behavior of irregular low density parity check co...