On the Parity-Check Density and Achievable Rates of LDPC Codes

Gil Wiechman, Igal Sason

Published 2005-05-30, updated 2005-07-04Version 2

The paper introduces new bounds on the asymptotic density of parity-check matrices and the achievable rates under ML decoding of binary linear block codes transmitted over memoryless binary-input output-symmetric channels. The lower bounds on the parity-check density are expressed in terms of the gap between the channel capacity and the rate of the codes for which reliable communication is achievable, and are valid for every sequence of binary linear block codes. The bounds address the question, previously considered by Sason and Urbanke, of how sparse can parity-check matrices of binary linear block codes be as a function of the gap to capacity. The new upper bounds on the achievable rates of binary linear block codes tighten previously reported bounds by Burshtein et al., and therefore enable to obtain tighter upper bounds on the thresholds of sequences of binary linear block codes under ML decoding. The bounds are applied to low-density parity-check (LDPC) codes, and the improvement in their tightness is exemplified numerically.