The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation
Open accessAbstract
We investigate spatially coupled code ensembles. For transmission over the binary erasure channel, it was recently shown that spatial coupling increases the belief propagation threshold of the ensemble to essentially the maximum a priori threshold of the underlying component ensemble. This explains why convolutional LDPC ensembles, originally introduced by Felström and Zigangirov, perform so well over this channel. We show that the equivalent result holds true for transmission over general binary-input memoryless output-symmetric channels. More precisely, given a desired error probability and a gap to capacity, we can construct a spatially coupled ensemble that fulfills these constraints universally on this class of channels under belief propagation decoding. In fact, most codes in this ensemble have this property. The quantifier universal refers to the single ensemble/code that is good for all channels but we assume that the channel is known at the receiver. The key technical result is a proof that, under belief-propagation decoding, spatially coupled ensembles achieve essentially the area threshold of the underlying uncoupled ensemble. We conclude by discussing some interesting open problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Mathematical Theory of Communication
Shannon, C. E. (1948) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1948.tb01338.x · Cited by 88,486
Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
Viterbi, A. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1054010 · Cited by 6,759
Near Shannon limit error-correcting coding and decoding: Turbo-codes. 1
Berrou, C., Glavieux, A., & Thitimajshima, P. (2002) · Proceedings of ICC '93 - IEEE International Conference on Communications · doi:10.1109/icc.1993.397441 · Cited by 6,738
Factor graphs and the sum-product algorithm
Kschischang, F. R., Frey, B. J., & Loeliger, H.-A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910572 · Cited by 6,486 · cited 1×
“who introduced the notion of factor graphs [39].”
BackgroundError Detecting and Error Correcting Codes
Hamming, R. W. (1950) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1950.tb00463.x · Cited by 5,377
Arikan, E. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2021379 · Cited by 4,476
Low-Density Parity-Check Codes
Gallager, R. G. (1963) · The MIT Press eBooks · doi:10.7551/mitpress/4347.001.0001 · Cited by 4,401
Channel coding with multilevel/phase signals
Ungerboeck, G. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056454 · Cited by 3,751
Good error-correcting codes based on very sparse matrices
MacKay, D. J. C. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.748992 · Cited by 3,684
Villani, C. (2009) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-540-71050-9 · Cited by 3,669
Polynomial Codes Over Certain Finite Fields
Reed, I. S., & Solomon, G. (1960) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0108018 · Cited by 3,662
ERROR DETECTING AND ERROR CORRECTING CODES
Chauhan, N., Yadav, P., & Kumari, P. (2014) · Cited by 3,270
The capacity of low-density parity-check codes under message-passing decoding
Richardson, T. J., & Urbanke, R. L. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910577 · Cited by 3,065
Self-citationNear Shannon limit performance of low density paritycheck codes
MacKay, D. J. C., & Neal, R. M. (1997) · Electronics Letters · doi:10.1049/el:19970362 · Cited by 2,678
Bollobás, B. (2001) · doi:10.1017/cbo9780511814068 · Cited by 2,639
Richardson, T., & Urbanke, R. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511791338 · Cited by 2,271
Self-citationShift-register synthesis and BCH decoding
Massey, J. (1969) · IEEE Transactions on Information Theory · doi:10.1109/tit.1969.1054260 · Cited by 2,186
Near Shannon limit performance of low density paritycheck codes
MacKay, D. J. C., & Neal, R. M. (1996) · Electronics Letters · doi:10.1049/el:19961141 · Cited by 1,923
The Efficiency Analysis of Choices Involving Risk
Hanoch, G., & Levy, H. (1969) · The Review of Economic Studies · doi:10.2307/2296431 · Cited by 1,411
On a class of error correcting binary group codes
Bose, R. C., & Ray-Chaudhuri, D. K. (1960) · Information and Control · doi:10.1016/s0019-9958(60)90287-4 · Cited by 1,367
Efficient erasure correcting codes
Luby, M. G., Mitzenmacher, M., Shokrollahi, M. A., & Spielman, D. A. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910575 · Cited by 1,180
Improved decoding of Reed-Solomon and algebraic-geometry codes
Guruswami, V., & Sudan, M. (1999) · IEEE Transactions on Information Theory · doi:10.1109/18.782097 · Cited by 998
Sipser, M., & Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556667 · Cited by 931
Codes and Decoding on General Graphs
Wiberg, N. (1996) · Cited by 869
Trellis-coded modulation with redundant signal sets Part I: Introduction
Ungerboeck, G. (1987) · IEEE Communications Magazine · doi:10.1109/mcom.1987.1093542 · Cited by 802
Extrinsic information transfer functions: model and erasure channel properties
Ashikhmin, A., Kramer, G., & ten Brink, S. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.836693 · Cited by 756
Achieving<tex>$ 1over 2log (1+ hboxSNR)$</tex>on the AWGN Channel With Lattice Encoding and Decoding
Erez, U., & Zamir, R. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834787 · Cited by 732
Trellis-coded modulation with redundant signal sets Part II: State of the art
Ungerboeck, G. (1987) · IEEE Communications Magazine · doi:10.1109/mcom.1987.1093541 · Cited by 692
Algebraic soft-decision decoding of reed-solomon codes
Koetter, R., & Vardy, A. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2003.819332 · Cited by 607
Coding theorems for 'turbo-like' codes
Divsalar, D. (1998) · Medical Entomology and Zoology · Cited by 524
Calculation of the Wasserstein Distance Between Probability Distributions on the Line
Vallender, S. S. (1974) · Theory of Probability & Its Applications · doi:10.1137/1118101 · Cited by 483
Good codes based on very sparse matrices
MacKay, D. J. C., & Neal, R. M. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-60693-9_13 · Cited by 451
Golay, M. J. E. (1949) · Cited by 422
Channel coding: The road to channel capacity
Costello, D. J., & Forney, G. D. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2007.895188 · Cited by 408
Gray, R. M. (2011) · Entropy and Information Theory · doi:10.1007/978-1-4419-7970-4_14 · Cited by 392
Linear-time encodable and decodable error-correcting codes
Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556668 · Cited by 350
Statistical physics-based reconstruction in compressed sensing
Krząkała, F., Mézard, M., Sausset, F., Sun, Y., & Zdeborová, L. (2012) · HAL · Cited by 267
Windowed Decoding of Protograph-Based LDPC Convolutional Codes Over Erasure Channels
Iyengar, A. R., Papaleo, M., Siegel, P. H., Wolf, J. K., Vanelli-Coralli, A., & Corazza, G. E. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2177439 · Cited by 214
Statistical-Physics-Based Reconstruction in Compressed Sensing
Krzakala, F., Mézard, M., Sausset, F., Sun, Y. F., & Zdeborová, L. (2012) · Physical Review X · doi:10.1103/physrevx.2.021005 · Cited by 182
1Windowed Decoding of Protograph-based LDPC Convolutional Codes over Erasure Channels
Iyengar, A. R., Papaleo, M., Siegel, P. H., Wolf, J. K., Fellow, L., Vanelli-coralli, R., & Corazza, G. E. (2012) · Cited by 168
Deriving Good LDPC Convolutional Codes from LDPC Block Codes
Pusane, A. E., Smarandache, R., Vontobel, P. O., & Costello, D. J. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2095211 · Cited by 130
Maxwell Construction: The Hidden Bridge Between Iterative and Maximuma PosterioriDecoding
Méasson, C., Andrea Montanari, A., & Urbanke, R. L. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.2006466 · Cited by 127
Self-citationLattice codes can achieve capacity on the AWGN channel
Urbanke, R. L., & Rimoldi, B. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.651040 · Cited by 119
Self-citationProtograph based LDPC codes with minimum distance linearly growing with block size
Divsalar, D., Jones, C., Dolinar, S. J., & Thorpe, J. (2005) · Globecom · doi:10.1109/glocom.2005.1577834 · Cited by 115
Expander graph arguments for message-passing algorithms
Burshtein, D., & Miller, G. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.910588 · Cited by 101
Extremes of Information Combining
Sutskover, I., Shamai, S. S., & Ziv, J. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.844077 · Cited by 90
An analysis of the block error probability performance of iterative decoding
Lentmaier, M., Truhachev, D. V., Zigangirov, K. S., & Costello, D. J. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.856942 · Cited by 79
Windowed erasure decoding of LDPC Convolutional Codes
Papaleo, M., Iyengar, A. R., Siegel, P. H., Wolf, J. K., & Corazza, G. E. (2010) · IEEE Information Theory Workshop (ITW) · doi:10.1109/itwksps.2010.5503166 · Cited by 56
A Phenomenological Study on Threshold Improvement via Spatial Coupling
Takeuchi, K., Tanaka, T., & Kawabata, T. (2012) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e95.a.974 · Cited by 28
Metadata
- Authors
- Kudekar, S., Richardson, T., & Urbanke, R. L.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2013-12
- Volume
- 59
- Issue
- 12
- Pages
- 7761-7813
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2179644698
- Cited by
- 360
- References
- 49
- FWCI
- 48.90
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.