Name
Abstract | ||
|---|---|---|
We design low-density parity-check (LDPC) codes that perform at rates extremely close to the Shannon capacity. The codes are built from highly irregular bipartite graphs with carefully chosen degree patterns on both sides. Our theoretical analysis of the codes is based on the work of Richardson and Urbanke (see ibid., vol.47, no.2, p.599-618, 2000). Assuming that the underlying communication channel is symmetric, we prove that the probability densities at the message nodes of the graph possess a certain symmetry. Using this symmetry property we then show that, under the assumption of no cycles, the message densities always converge as the number of iterations tends to infinity. Furthermore, we prove a stability condition which implies an upper bound on the fraction of errors that a belief-propagation decoder can correct when applied to a code induced from a bipartite graph with a given degree distribution. Our codes are found by optimizing the degree structure of the underlying graphs. We develop several strategies to perform this optimization. We also present some simulation results for the codes found which show that the performance of the codes is very close to the asymptotic theoretical bounds |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1109/18.910578 | IEEE Transactions on Information Theory |
Keywords | Field | DocType |
AWGN channels,channel capacity,decoding,error detection codes,optimisation,probability,stability,Shannon capacity,additive white Gaussian noise channel,asymptotic theoretical bounds,belief-propagation decoder,binary-input AWGN channel,bipartite graph,capacity-approaching irregular codes,code design,decoding,degree distribution,degree structure optimisation,irregular bipartite graphs,low-density parity-check codes,message densities,message nodes,probability densities,simulation results,stability condition,symmetric communication channel,symmetry property,upper bound | Factor graph,Discrete mathematics,Concatenated error correction code,Combinatorics,Low-density parity-check code,Turbo code,Block code,Expander code,Linear code,Tanner graph,Mathematics | Journal |
Volume | Issue | ISSN |
47 | 2 | 0018-9448 |
Citations | PageRank | References |
1357 | 138.76 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. J. Richardson | 1 | 5111 | 510.18 |
| Shokrollahi, M.A. | 2 | 1357 | 138.76 |
| Rüdiger L. Urbanke | 3 | 2741 | 279.71 |