Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques

Abstract

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> and R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> satisfying 0<R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> <R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <1, there exists an ensemble of LDPC codes with the following property. The ensemble can be punctured from rate R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> to R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> resulting in asymptotically good codes for all rates R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> lesRlesR <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> . Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> <R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> <1, the existence of the sequences of punctured LDPC codes that are capacity-achieving for all rates R <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1 </sub> lesRlesR <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels