Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-6bf8c574d5-j5c6p Total loading time: 0 Render date: 2025-03-11T17:30:53.255Z Has data issue: false hasContentIssue false

11 - Finite-Geometry LDPC Codes

Published online by Cambridge University Press:  06 March 2025

William E. Ryan ,
Shu Lin  and
Stephen G. Wilson
William E. Ryan
Affiliation:
Zeta Associates
Shu Lin
Affiliation:
University of California, Davis
Stephen G. Wilson
Affiliation:
University of Virginia
Get access

Summary

Channel coding lies at the heart of digital communication and data storage. Fully updated to include current innovations in the field, including a new chapter on polar codes, this detailed introduction describes the core theory of channel coding, decoding algorithms, implementation details, and performance analyses. This edition includes over 50 new end-of-chapter problems to challenge students and numerous new figures and examples throughout.

The authors emphasize a practical approach and clearly present information on modern channel codes, including polar, turbo, and low-density parity-check (LDPC) codes, as well as detailed coverage of BCH codes, Reed–Solomon codes, convolutional codes, finite geometry codes, and product codes for error correction, providing a one-stop resource for both classical and modern coding techniques.

Assuming no prior knowledge in the field of channel coding, the opening chapters begin with basic theory to introduce newcomers to the subject. Later chapters then begin with classical codes, continue with modern codes, and extend to advanced topics such as code ensemble performance analyses and algebraic LDPC code design.

  • 300 varied and stimulating end-of-chapter problems test and enhance learning, making this an essential resource for students and practitioners alike.

  • Provides a one-stop resource for both classical and modern coding techniques.

  • Starts with the basic theory before moving on to advanced topics, making it perfect for newcomers to the field of channel coding.

  • 180 worked examples guide students through the practical application of the theory.

Type
Chapter
Information
Channel Codes
Classical and Modern
 , pp. 511 - 578
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Kou, Y., Lin, S., and Fossorier, M., “Low density parity check codes based on finite geometries: A rediscovery,” Proceedings of the IEEE International Symposium on Information Theory, Sorrento, June 25–30, 2000, p. 200.Google Scholar
Kou, Y., Lin, S., and Fossorier, M., “Construction of low density parity check codes: A geometric approach,” Proceedings of the 2nd International Symposium on Turbo Codes and Related Topics, Brest, September 2000, pp. 137–140.Google Scholar
Kou, Y., Lin, S., and Fossorier, M., “Low density parity-check codes: Construction based on finite geometries,” Proceedings of IEEE Globecom, San Francisco, CA, November–December, 2000, pp. 825–829.Google Scholar
Kou, Y., Lin, S., and Fossorier, M., “Low-density parity-check codes based on finite geometries: A rediscovery and new results,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 2711–2736, November 2001.CrossRefGoogle Scholar
Kou, Y., Xu, J., Tang, H., Lin, S., and Abdel-Ghaffar, K., “On circulant low density parity check codes,” Proceedings of the IEEE International Symposium on Information Theory, Lausanne, June–July 2002, p. 200.CrossRefGoogle Scholar
Lin, S., Tang, H., and Kou, Y., “On a class of finite geometry low density parity check codes,” Proceedings of the IEEE International Symposium on Information Theory, Washington, DC, June 2001, p. 24.Google Scholar
Lin, S., Tang, H., Kou, Y., and Abdel-Ghaffar, K., “Codes on finite geometries,” Proceedings of the IEEE Information Theory Workshop, Cairns, Australia, September 2–7, 2001, pp. 14–16.Google Scholar
Tang, H., Codes on Finite Geometries, PhD thesis, University of California, Davis, CA, 2002.Google Scholar
Tang, H., Kou, Y., Xu, J., Lin, S., and Abdel-Ghaffar, K., “Codes on finite geometries: Old, new, majority-logic and iterative decoding,” Proceedings of the 6th International Symposium on Communication Theory and Applications, Ambleside, UK, July 2001, pp. 381–386.Google Scholar
Tang, H., Xu, J., Kou, Y., Lin, S., and Abdel-Ghaffar, K., “On algebraic construction of Gallager low density parity-check codes,” Proceedings of the IEEE International Symposium on Information Theory, Lausanne, June–July, 2002, p. 482.CrossRefGoogle Scholar
Tang, H., Xu, J., Kou, Y., Lin, S., and Abdel-Ghaffar, K., “On algebraic construction of Gallager and circulant low density parity check codes,” IEEE Transactions on Information Theory, vol. 50, no. 6, pp. 1269–1279, June 2004.CrossRefGoogle Scholar
Tang, H., Xu, J., Lin, S., and Abdel-Ghaffar, K., “Codes on finite geometries,” IEEE Transactions on Information Theory, vol. 51, no. 2, pp. 572–596, 2005.Google Scholar
Tai, Y. Y., Lan, L., Zeng, L.-Q., Lin, S., and Abdel Ghaffar, K., “Algebraic construction of quasi-cyclic LDPC codes for AWGN and erasure channels,” IEEE Transactions on Communications, vol. 54, no. 10, pp. 1765–1774, October 2006.CrossRefGoogle Scholar
Vontobel, P. O. and Koetter, R., “Graph-cover decoding and finite-length analysis of message-passing iterative decoding of LDPC codes,” unpublished work at https://arxiv.org/pdf/cs/0512078.Google Scholar
Xu, J., Chen, L., Djurdjevic, I., Lin, S., and Abdel-Ghaffar, K., “Construction of regular and irregular LDPC codes: Geometry decomposition and masking,” IEEE Transactions on Information Theory, vol. 53, no. 1, pp. 121–134, January 2007.CrossRefGoogle Scholar
Zeng, L.-Q., Lan, L., Tai, Y. Y., Zhou, B., Lin, S., and K. Abdel-Ghaffar, “Construction of nonbinary quasi-cyclic LDPC codes: A finite geometry approach,” IEEE Transactions on Communications, vol. 56, no. 3, pp. 378–387, March 2008.CrossRefGoogle Scholar
Zhang, J. and Fossorier, M. P. C., “A modified weighted bit-flipping decoding for low-density parity-check codes,” IEEE Communication Letters, vol. 8, pp. 165–167, March 2004.CrossRefGoogle Scholar
Zhou, B., Kang, J.-Y., Tai, Y. Y., Lin, S., and Ding, Z., “High performance non-binary quasi-cyclic LDPC codes on Euclidean geometries,” IEEE Transactions on Communications, vol. 57. no. 5, pp. 1298–1311, May 2009.CrossRefGoogle Scholar
Rudolph, L. D., Geometric Configuration and Majority Logic Decodable Codes, MEE thesis, University of Oklahoma, Norman, OK, 1964.Google Scholar
Rudolph, L. D., “A class of majority logic decodable codes,” IEEE Transactions on Information Theory, vol. 13. pp. 305–307, April 1967.Google Scholar
Weldon, E. J., Jr., “Euclidean geometry cyclic codes,” Proceedings of the Symposium on Combinatorial Mathematics, University of North Carolina, Chapel Hill, NC, April 1967.Google Scholar
Kasami, T., Lin, S., and Peterson, W. W., “Polynomial codes,” IEEE Transactions on Information Theory, vol. 14, no. 6, pp. 807–814, November 1968.CrossRefGoogle Scholar
Lin, S. and Costello, D. J., Jr., Error Control Coding: Fundamentals and Applications, 2nd ed., Upper Saddle River, NJ, Prentice-Hall, 2004.Google Scholar
Peterson, W. W. and Weldon, E. J., Error-Correcting Codes, 2nd ed., Cambridge, MA, MIT Press, 1972.Google Scholar
Berlekamp, E. R., Algebraic Coding Theory, New York, McGraw-Hill, 1968. (Revised edition, Laguna Hills, NY, Aegean Park Press, 1984).Google Scholar
Richardson, T., Shokrollahi, A., and Urbanke, R., “Design of capacity approaching irregular codes,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 619–637, February 2001.CrossRefGoogle Scholar
Chen, L., Xu, J., Djurdjevic, I., and Lin, S., “Near Shannon limit quasi-cyclic low-density parity-check codes,” IEEE Transactions on Communications, vol. 52, no. 7, pp. 1038–1042, July 2004.Google Scholar
Huang, Q., Diao, Q., Lin, S., and Abdel-Ghaffar, K., “Cyclic and quasi-cyclic LDPC codes on constrained parity-check matrices and their trapping sets,” IEEE Transactions on Information Theory, vol. 58, no. 5, pp. 2648–2671, May 2012.CrossRefGoogle Scholar
Goethals, J. M. and Delsarte, P., “On a class of majority-logic decodable codes,” IEEE Transactions on Information Theory, vol. 14, no. 2, pp. 182–189, March 1968.CrossRefGoogle Scholar
Smith, K. J. C., Majority Decodable Codes Derived from Finite Geometries, Institute of Statistics Memo Series No. 561, University of North Carolina, Chapel Hill, NC, 1967.Google ScholarPubMed
Weldon, E. J., Jr., “New generalization of the Reed–Muller codes, part II: Non-primitive codes,” IEEE Transactions on Information Theory, vol. 14, no. 2, pp. 199–205, March 1968.CrossRefGoogle Scholar
Gallager, R. G., “Low-density parity-check codes,” IRE Transactions on Information Theory, vol. IT-8, no. 1, pp. 21–28, January 1962.CrossRefGoogle Scholar
Kasami, T. and Lin, S., “On majority-logic decoding for duals of primitive polynomial codes,” IEEE Transactions on Information Theory, vol. 17, no. 3, pp. 322–331, May 1971.CrossRefGoogle Scholar
Massey, J. L., “Shift-register synthesis and BCH decoding,” IEEE Transactions on Information Theory, vol. IT-15, no. 1, pp. 122–127, January 1969.CrossRefGoogle Scholar
Chen, J. and Fossorier, M. P. C., “Near optimum universal belief propagation based decoding of low-density parity check codes,” IEEE Transactions on Communications, vol. 50, no. 3, pp. 406–614, March 2002.CrossRefGoogle Scholar
Jiang, M., Zhao, C., Shi, Z., and Chen, Y., “An improvement on the modified weighted bit-flipping decoding algorithm for LDPC codes,” IEEE Communications Letters, vol. 9, no. 7, pp. 814–816, September 2005.Google Scholar
Liu, Z. and Pados, D. A., “A decoding algorithm for finite-geometry LDPC codes,” IEEE Transactions on Communications, vol. 53, no. 3, pp. 415–421, March 2005.CrossRefGoogle Scholar
Shan, M., Zhao, C., and Jian, M., “An improved weighted bit-flipping algorithm for decoding LDPC codes,” IEE Proceedings Communications, vol. 152, pp. 1350–2425, 2005.CrossRefGoogle Scholar
Bose, R. C., “Strongly regular graphs, partial geometries and partially balanced designs,” Pacific Journal of Mathematics, vol. 13, no. 2, pp. 389–419, April 1963.CrossRefGoogle Scholar
van Lint, J. H., “Partial geometries,” Proceedings of the International Congress of Mathematicians, Warszawa, August 16–24, 1983, pp. 1579–1589.Google Scholar
Cameron, P. J. and van Lint, J. H., Designs, Graphs, Codes, and their Links, Cambridge, Cambridge University Press, 1991.CrossRefGoogle Scholar
Batten, L. M., Combinatorics of Finite Geometries, 2nd ed., Cambridge, Cambridge University Press, 1997.CrossRefGoogle Scholar
Kamischke, E. J., Benson’s Theorem for Partial Geometries, MSc thesis, Michigan Technological University, 2013.Google Scholar
Johnson, S. J. and Weller, S. R., “Codes for iterative decoding from partial geometries,” IEEE Transactions on Communications, vol. 52, no. 2, pp. 236–243, February 2004.Google Scholar
Diao, Q., Tai, Y. Y., Lin, S., and Abdel-Ghaffar, K., “LDPC codes on partial geometries: Construction, trapping sets structure, and puncturing,” IEEE Transactions on Information Theory, vol. 59, no. 12, pp. 7898–7914, September 2013.Google Scholar
Lin, S. and Li, J., Fundamentals of Classical and Modern Error-Correcting Codes, Cambridge, Cambridge University Press, 2022.Google Scholar
Lin, S., Diao, Q., and Blake, I. F., “Error floors and finite geometries,” Proceedings of the International Symposium, Germany, August 18–22, 2014.Google Scholar
Diao, Q., Li, J., Lin, S., and Blake, I. F., “New classes of partial geometries and their associated LDPC codes,” IEEE Transactions on Information, vol. 62, no. 6, pp. 2947–2965.Google Scholar
Li, J., Liu, K., Lin, S., and K. Abdel-Ghaffar, “Construction of partial geometries and LDPC codes based on Reed–Solomon codes,” Proceedings of the International Symposium on Information Theory, July 7–12, 2019, Paris.Google Scholar
Lin, S., “On the number of information symbols in polynomial codes,” IEEE Transactions on Information Theory, vol. 18, no. 6, pp. 785–794, November 1972.CrossRefGoogle Scholar
Miladinovic, N. and Fossorier, M. P., “Improved bit-flipping decoding of low-density parity-check codes,” IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1594–1606, April 2005.Google Scholar
Mobini, N., Banihashemi, A. H., and Hemati, S., “A differential binary-passing LDPC decoder,” Proceedings of IEEE Globecom, Washington, DC, November 2007, pp. 1561–1565.Google Scholar
Richardson, T. J., “Error floors of LDPC codes,” Proceedings of the 41st Allerton Conference on Communications, Control and Computing, Monticello, IL, October 2003, pp. 1426–1435.Google Scholar
Weldon, E. J., Jr., “Some results on majority-logic decoding,” in Mann, H. (ed.), Error-Correcting Codes, New York, Wiley, 1968.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×