iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/3-540-46541-3_1
Codes and Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Codes and Graphs

  • Conference paper
  • First Online:
STACS 2000 (STACS 2000)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1770))

Included in the following conference series:

Abstract

In this paper, I will give a brief introduction to the theory of low-density parity-check codes, and their decoding. I will emphasize the case of correcting erasures as it is still the best understood and most accessible case. At the end of the paper, I will also describe more recent developments.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. N. Alon and M. Luby. A linear time erasure-resilient code with nearly optimal recovery. IEEE Trans. Inform. Theory, 42:1732–1736, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  2. S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45:70–122, 1998.

    Article  MATH  MathSciNet  Google Scholar 

  3. E.R. Berlekamp, R.J. McEliece, and H.C.A. vanTilborg. On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory, 24:384–386, 1978.

    Article  MATH  Google Scholar 

  4. C. Berroux, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting coding and decoding. In Proceedings of ICC’93, pages 1064–1070, 1993.

    Google Scholar 

  5. P. Elias. Coding for two noisy channels. In Information Theory, Third London Symposium, pages 61–76, 1955.

    Google Scholar 

  6. R. G. Gallager. Low Density Parity-Check Codes. MIT Press, Cambridge, MA, 1963.

    Google Scholar 

  7. M. Luby, M. Mitzenmacher, and M.A. Shokrollahi. Analysis of random processes via and-or tree evaluation. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 364–373, 1998.

    Google Scholar 

  8. M. Luby, M. Mitzenmacher, M.A. Shokrollahi, and D. Spielman. Analysis of low density codes and improved designs using irregular graphs. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 249–258, 1998.

    Google Scholar 

  9. M. Luby, M. Mitzenmacher, M.A. Shokrollahi, and D. Spielman. Improved low-density parity-check codes using irregular graphs and belief propagation. In Proceedings 1998 IEEE International Symposium on Information Theory, page 117, 1998.

    Google Scholar 

  10. M. Luby, M. Mitzenmacher, M.A. Shokrollahi, D. Spielman, and V. Stemann. Practical loss-resilient codes. In Proceedings of the 29th annual ACM Symposium on Theory of Computing, pages 150–159, 1997.

    Google Scholar 

  11. D.J.C. MacKay. Good error-correcting codes based on very sparse matrices. IEEE Trans. Inform. Theory, 45:399–431, 1999.

    Article  MATH  MathSciNet  Google Scholar 

  12. G. A. Margulis. Explicit constructions of graphs without short cycles and low density codes. Combinatorica, 2:71–78, 1982.

    Article  MATH  MathSciNet  Google Scholar 

  13. T. Richardson, M.A. Shokrollahi, and R. Urbanke. Design of provably good low-density parity check codes. IEEE Trans. Inform. Theory (submitted), 1999.

    Google Scholar 

  14. T. Richardson and R. Urbanke. The capacity of low-density parity check codes under message-passing decoding. IEEE Trans. Inform. Theory (submitted), 1998.

    Google Scholar 

  15. C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379–423, 623–656, 1948.

    MathSciNet  Google Scholar 

  16. M.A. Shokrollahi. New sequences of linear time erasure codes approaching the channel capacity. To appear in the Proceedings of AAECC’13, 1999.

    Google Scholar 

  17. M. Sipser and D. Spielman. Expander codes. IEEE Trans. Inform. Theory, 42:1710–1722, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  18. D. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42:1723–1731, 1996.

    Article  MATH  MathSciNet  Google Scholar 

  19. M. R. Tanner. A recursive approach to low complexity codes. IEEE Trans. Inform. Theory, 27:533–547, 1981.

    Article  MATH  MathSciNet  Google Scholar 

  20. V. V. Zyablov. An estimate of the complexity of constructing binary linear cascade codes. Probl. Inform. Transm., 7:3–10, 1971.

    Google Scholar 

  21. V. V. Zyablov and M. S. Pinsker. Estimation of error-correction complexity of Gallager low-density codes. Probl. Inform. Transm., 11:18–28, 1976.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Bell Laboratories, Room 2C-353, 700 Mountain Ave, Murray Hill, NJ, 07974, USA

    M. Amin Shokrollahi

Authors
  1. M. Amin Shokrollahi
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Faculty of Computer Science, Dept. of Theoretical Computer Science, Universität Dresden, 01062, Dresden, Germany

    Horst Reichel

  2. Université de Lille, LIFL - UPRESA 8022, CNRS, Bât. M3 - UFR IEEA, 59655, Villeneuve d’ASCQ Cedex, France

    Sophie Tison

Rights and permissions

Reprints and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Shokrollahi, M.A. (2000). Codes and Graphs. In: Reichel, H., Tison, S. (eds) STACS 2000. STACS 2000. Lecture Notes in Computer Science, vol 1770. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46541-3_1

Download citation

  • DOI: https://doi.org/10.1007/3-540-46541-3_1

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-67141-1

  • Online ISBN: 978-3-540-46541-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation