Analysis of low density codes and improved designs using irregular graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Analysis of low density codes and improved designs using irregular graphs

Full text

Pdf (1.27 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 249 - 258

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

M. Luby	International Computer Science Institute, Berkeley, CA
M. Mitzenmacher	Digital Equipment Corporation, Systems Research Center, Palo Alto, CA
A. Shokrollah	International Computer Science, Institute Berkeley, and Institut für Informatik der Universitüt Bonn, Germany
D. Spielman	Department of Mathematics, M.I.T.

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 103, Citation Count: 10

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276756 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. Berrou, A Glavieux, and P. Thitimajshima, "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes", Proceedings of lEEE International Communications Conference, 1993.
	2	J.-F. Cheng and R. J. MeEliece, "Some High-Rate Near Capacity Codecs for the Gaussian Channel", 34th Allerton Conference on Communications, Control and Computing.
	3	D. Divsalar and F. Pollara, "On the Design of Turbo Codes", JPL TDA Progress Report 42-123.
	4	G.D. Forney, Jr. 'q'he Forwaxd-Baekward Algorithm", Proceedings of the $4th Allerton Conference on Communications, Control and Computing, 1996, pp. 432- 446.
	5	B. 3. Frey and E tL Ksehisehang, "Probability Propagation and Iterafive Decoding", Proceedings of the $4th Allerton Conference on Communications, Control and Computing, 1996.
	6	R. G. Gallager, Low-Density Parity-Check Codes, MiT Press, 1963.
	7	Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi , Daniel A. Spielman , Volker Stemann, Practical loss-resilient codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.150-159, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258573]
	8	Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi, Analysis of random processes via And-Or tree evaluation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.364-373, January 25-27, 1998, San Francisco, California, United States
	9	M. Luby, M. Mitzenmaeher, M. A. Shokrollahi, and D. A. Spielman, "Improved Low Density Parity Cheek Codes Using irregular Graphs and Belief Propagation", submitted to the 1998 International Symposium on Information Theory.
	10	D. J. C. MacKay, R, J. McEliece, and J.-F. Cheng, "Turbo Coding as an Instance of Pearl's 'Belief Propagation' Algorithm", to appear in IEEE Journal on Selected Areas in Communication.
	11	D.J.C. MacKay and R. M. Neal, "Good Error Correcting Codes Based on Very Sparse Matrices", available from http ://wol.ra.phy. cam. ae..uk/mackay.
	12	D.J.C. MacKay and R. M. Neal, "Near Shannon Limit Performance of Low Density Parity Cheek Codes", to appear in Electronic Letters.
	13	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	14	Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	15	M. Sipser, D. A. Spielman, "Expander Codes", IEEE Transactions on Information Theory, 42(6), November 1996, pp. 1710-1722.
	16	D. A. Spielman, "Linear Time Eneodable and Decodable Error-Correcting Codes", IEEE Transactions on Information Theory, 42(6), November 1996, pp. 1723- 1731.
	17	N. Wiberg, "Codes and decoding on general graphs" Ph.D. dissertation, Dept. Elec. Eng, U. LinkSping, Sweeden, April 1996.

CITED BY 10

	Andrei Z. Broder , Robert Krauthgamer , Michael Mitzenmacher, Improved classification via connectivity information, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.576-585, January 09-11, 2000, San Francisco, California, United States
	Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi, Analysis of random processes via And-Or tree evaluation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.364-373, January 25-27, 1998, San Francisco, California, United States
	John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishan Gummadi , Sean Rhea , Hakim Weatherspoon , Westley Weimer , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, ACM SIGPLAN Notices, v.35 n.11, p.190-201, Nov. 2000
	John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, ACM SIGARCH Computer Architecture News, v.28 n.5, p.190-201, Dec. 2000
	Amin Shokrollahi, An introduction to low-density parity-check codes, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
	Frank Kienle , Norbert Wehn, Design methodology for IRA codes, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.459-462, January 27-30, 2004, Yokohama, Japan
	Ben Lu , Xiaodong Wang , Mohammad Madihian, Physical-layer air interface solutions for broadband high-speed wireless cellular systems, Wireless Networks, v.13 n.1, p.5-26, January 2007
	Phillip A. Regalia, Iterative decoding of concatenated codes: a tutorial, EURASIP Journal on Applied Signal Processing, v.2005 n.1, p.762-774, 1 January 2005
	Hanno Lefmann, Sparse Parity-Check Matrices over ${GF(q)}$, Combinatorics, Probability and Computing, v.14 n.1, p.147-169, January 2005
	Changhao Zhai , Chengxin Xu , Xin Zhang , Yafeng Wang, Research on stopping criterion for irregular LDPC codes decoding, Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, June 21-24, 2009, Leipzig, Germany