Abstract
Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a √1 - λ′ (0)ρp′(1) fraction of codes with λ′(0)ρ ′(1) < 1, and in particular for almost all codes with smallest variable degree > 2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability ε, showing in particular that for codes with lowest variable degree 2, if ε is below a certain threshold, the asymptotic average block error probability is 1 - √1 - λ′(0)ρp′(1)ε.
Original language | English (US) |
---|---|
Pages (from-to) | 929-953 |
Number of pages | 25 |
Journal | IEEE Transactions on Information Theory |
Volume | 51 |
Issue number | 3 |
DOIs | |
State | Published - Mar 2005 |
Externally published | Yes |
Keywords
- Binary erasure channel (BEC)
- Block error probability
- Growth rate
- Low-density parity-check (LDPC) codes
- Minimum distance
- Stopping set
ASJC Scopus subject areas
- Information Systems
- Computer Science Applications
- Library and Information Sciences