Parity-check density versus performance of binary linear block codes over memoryless symmetric channels
We derive lower bounds on the density of parity-check matrices of binary linear codes which are used over memoryless binary-input output-symmetric (MBIOS) channels. The bounds are expressed in terms of the gap between the rate of these codes for which reliable communications is achievable and the channel capacity; they are valid for every sequence of binary linear block codes if there exists a decoding algorithm under Which the average bit-error probability vanishes. For every MBIOS channel, we construct a sequence of ensembles of regular low-density parity-check (LDPC) codes, so that an upper bound on the asymptotic density of their parity-check matrices scales similarly to the lower bound. The tightness of the lower bound is demonstrated for the binary erasure channel by analyzing a sequence of ensembles of right-regular LDPC codes which was introduced by Shokrollahi, and which is known to achieve the capacity of this channel. Under iterative message-passing decoding, we show that this sequence of ensembles is asymptotically optimal (in a sense to be defined in this paper), strengthening a result of Shokrollahi. Finally, We derive lower bounds' on the bit-error probability and on the gap to capacity for binary. linear block codes Which are represented by bipartite graphs,and study their performance limitations over MBIOS channels, the latter bounds provide a quantitative measure for the number of cycles of bipartite graphs which represent good error-correction codes.
block codes linear codes channel capacity low-density parity-check (ldpc) codes bipartite graph cycles in a graph error probability iterative decoding maximum-likelihood (ml) decoding memoryless channels sparse matrices