Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

Low-density parity-check codes

Sarah J. Johnson

Published Nov 19, 2009• 6 citations
Publisher

Abstract

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

DOI
10.1017/cbo9780511809354.003

Related papers

An Introduction to LDPC Codes

Irene Márquez-Corbella, Edgar Martínez-Moro

The focus of this chapter is on low-density parity-check (LDPC) codes and iterative decoding methods. Low density parity check codes were originally introduced by Gallager in his doctoral thesis in 1963 [19]. Gallager discussed several iterative decoding algorithms for these codes that in general have very good error-correcting capabilities. Later, Tanner [32] in 1981 gave a graphical interpretation to these codes as a bi-partite graph whose incidence matrix is the parity check matrix of the LDPC code, and showed how to view the iterative decoding algorithms as message-passing algorithms on these graphs.

Series on coding theory and cryptology•Feb 1, 2013•4 citations

Low-Density Parity-Check Codes

W.E. Ryan, Shu Lin

Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices.

Cambridge University Press eBooks•Sep 17, 2009•6 citations

Low‐Density Parity‐Check Codes

Christian B. Schlegel, Lance C. Pérez

Low-density parity-check (LDPC) codes can rightfully take their stand next to turbo codes as the most powerful and most popular error control codes known. They offer a performance spectacularly close to theoretical limits when decoded using iterative soft decision algorithms. This chapter explores the properties and structure of low-density parity-check codes. It begins with the fundamental construction of regular LDPC codes and their representation as bipartite graphs. The graphical representation of LDPC codes then leads to the notion of irregular LDPC codes, which have been used to improve performance, and to the density evolution analysis technique, which predicts the performance of these codes.

Wiley eBooks•Aug 29, 2015•6 citations

Performance Analysis of LDPC Decoding Techniques

Abdel Halim A. Zikry, Ashraf Yehya Hassan, Wageda I. Shaban +1 more

Low density parity checking codes (LDPC) are one of the most important issues in coding theory at present. LDPC-code are a type of linear-block LDPC-codes. Channel coding might be considered as the finest conversant and most potent components of cellular communications systems, that was employed for transmitting errors corrections imposed by noise, fading and interfering. LDPC-codes are advanced coding gain, i.e., new area in coding. the performances of LDPC-code are similar to the Shannon-limiting, this led to the usage of decoding in several applications in digital communications systems, like DVB-S2 and WLAN802.1..This paper aims to know what is LDPC,what its application and introduce encoding algorithms that gives rise to a linear encoding time and also show that the regular and irregular LDPC performance and also introduce different methods for decoding LDPC. I discuss in detail LDPC decoding algorithm: bit flipping algorithm, as a type from hard decision .belief propagation algorithm, sum product algorithm and minimum sum algorithm as examples from soft decision .I expect that at least some students or researchers involved in researching LDPC codes would find this paper helpful.

International Journal of Recent Technology and Engineering (IJRTE)•Jan 30, 2021•7 citations

Performance Evaluation of LDPC decoding Algorithm for GF (2)

D Patel Jigisha, Patel Ruchita Kumari

Low Density Parity Check (LDPC) codes are one of the block coding techniques that can approach the Shannon’s limit within a fraction of a decibel for high block lengths. In many digital communication systems, these codes have strong competitors of turbo codes for error control. LDPC codes performance depends on the excellent design of parity check matrix and many diverse research methods have been used by different study groups to evaluate the performance. Unlike many other classes of codes, LDPC codes are already equipped with a fast, probabilistic decoding algorithm. This makes LDPC codes not only attractive from a theoretical point of view, but also very suitable for practical applications. This paper throws hard decision and soft decision algorithm of LDPC. The hard decision algorithm contains Bit flipping algorithm and Soft decoding algorithm contains Sum product algorithm which is used to correct burst error. Sum Product algorithm is also called as belief propagation. Bit flipping and Sum Product algorithms are explained and can be implemented for the generated parity check matrix of (1016x508) for LDPC code with code rate 1/2.

Journal of Emerging Technologies and Innovative Research•Nov 1, 2014•0 citations

Düşük yoğunluklu eşlik denetim kodları için kod çözme algoritmalarının karşılaştırılması.

Kolaylı, Mert

Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations; however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.

•Jan 1, 2006•0 citations
Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.
The focus of this chapter is on low-density parity-check (LDPC) codes and iterative decoding methods. Low density parity check codes were originally introduced by Gallager in his doctoral thesis in 1963 [19]. Gallager discussed several iterative decoding algorithms for these codes that in general have very good error-correcting capabilities. Later, Tanner [32] in 1981 gave a graphical interpretation to these codes as a bi-partite graph whose incidence matrix is the parity check matrix of the LDPC code, and showed how to view the iterative decoding algorithms as message-passing algorithms on these graphs.
Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices.
Low-density parity-check (LDPC) codes can rightfully take their stand next to turbo codes as the most powerful and most popular error control codes known. They offer a performance spectacularly close to theoretical limits when decoded using iterative soft decision algorithms. This chapter explores the properties and structure of low-density parity-check codes. It begins with the fundamental construction of regular LDPC codes and their representation as bipartite graphs. The graphical representation of LDPC codes then leads to the notion of irregular LDPC codes, which have been used to improve performance, and to the density evolution analysis technique, which predicts the performance of these codes.
Low density parity checking codes (LDPC) are one of the most important issues in coding theory at present. LDPC-code are a type of linear-block LDPC-codes. Channel coding might be considered as the finest conversant and most potent components of cellular communications systems, that was employed for transmitting errors corrections imposed by noise, fading and interfering. LDPC-codes are advanced coding gain, i.e., new area in coding. the performances of LDPC-code are similar to the Shannon-limiting, this led to the usage of decoding in several applications in digital communications systems, like DVB-S2 and WLAN802.1..This paper aims to know what is LDPC,what its application and introduce encoding algorithms that gives rise to a linear encoding time and also show that the regular and irregular LDPC performance and also introduce different methods for decoding LDPC. I discuss in detail LDPC decoding algorithm: bit flipping algorithm, as a type from hard decision .belief propagation algorithm, sum product algorithm and minimum sum algorithm as examples from soft decision .I expect that at least some students or researchers involved in researching LDPC codes would find this paper helpful.
Low Density Parity Check (LDPC) codes are one of the block coding techniques that can approach the Shannon’s limit within a fraction of a decibel for high block lengths. In many digital communication systems, these codes have strong competitors of turbo codes for error control. LDPC codes performance depends on the excellent design of parity check matrix and many diverse research methods have been used by different study groups to evaluate the performance. Unlike many other classes of codes, LDPC codes are already equipped with a fast, probabilistic decoding algorithm. This makes LDPC codes not only attractive from a theoretical point of view, but also very suitable for practical applications. This paper throws hard decision and soft decision algorithm of LDPC. The hard decision algorithm contains Bit flipping algorithm and Soft decoding algorithm contains Sum product algorithm which is used to correct burst error. Sum Product algorithm is also called as belief propagation. Bit flipping and Sum Product algorithms are explained and can be implemented for the generated parity check matrix of (1016x508) for LDPC code with code rate 1/2.
Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations; however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.