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

Birkhäuser Basel eBooks

LDPC Codes: An Introduction

Amin Shokrollahi

Published Jan 1, 2004• 144 citations
Publisher

Abstract

LDPC codes are one of the hottest topics in coding theory today. Originally invented in the early 1960’s, they have experienced an amazing comeback in the last few years. Unlike many other classes of codes, LDPC codes are already equipped with very fast (probabilistic) encoding and decoding algorithms. The question is that of the design of the codes such that these algorithms can recover the original codeword in the face of large amounts of noise. New analytic and combinatorial tools make it possible to solve the design problem. This makes LDPC codes not only attractive from a theoretical point of view, but also perfect for practical applications. In this note I will give a brief overview of the origins of LDPC codes and the methods used for their analysis and design.

DOI
10.1007/978-3-0348-7865-4_5

Related papers

Capacity-Approaching Low-Density Parity-Check Codes

Pierre J. Garrigues

The class of low-density parity-check (LDPC) codes was introduced by Gallager in his thesis in 1961 [2]. Until the invention of turbo codes, they were largely neglected, but received a lot of interest lately, due to the possibility of designing LDPC codes within 0.0045 dB of the Shannon limit. We review in this project techniques used to analyze the performance of LDPC codes under a message-passing decoding algorithm, namely belief propagation (BP) [4][5]. This analysis gives us the tools to design good LDPC codes. We will first take the simpler example of transmission over the class of binary erasure channels (BEC). We will then see how it is possible to extend the results for the BEC to the much more general class of symmetric channels.

•Jan 1, 2005•0 citations

Low-Density Parity-Check Codes

Low Density Parity Check(LDPC) codes is one of the high topics of the channel coding theory and has been paid more and more attention.This paper begins with a brief review of channel coding theories.Then the iterative decoding algorithm of LDPC codes,so-called as Sum-Product algorithm or Belief Propagation algorithm,is represented in detail.And the construction of LDPC codes by means of random bipartite graph and algebraic constructions,and the performance analysis by Density Evolution theory,Gaussian Approximation method and Extrinsic Information Transfer(EXIT) charts etc.,are respectively discussed.Finally,the latest study results of LDPC codes are presented and some open questions about LDPC codes are provided.

Kluwer Academic Publishers eBooks•Dec 21, 2005•9 citations

A Universal Theory of Decoding and Pseudocodewords

Nathan Axvig, Deanna Dreher, Katherine Morrison +3 more

The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)

•Jan 1, 2008•2 citations

Comprehensive Algorithmic Review and Analysis of LDPC Codes

Waheed Ullah, Abid Yahya

Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel

Indonesian Journal of Electrical Engineering and Computer Science•Oct 1, 2015•8 citations

Comprehensive Algorithmic Review and Analysis of LDPC Codes

Waheed Ullah, Abid Yahya

Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel

TELKOMNIKA Indonesian Journal of Electrical Engineering•Oct 1, 2015•10 citations

A REVIEW OF CONSTRUCTION METHODS FOR REGULAR LDPC CODES

Nisha Sarwade

Low-Density parity-check (LDPC) codes are one of the most powerful error correcting codes available today. Their Shannon capacity approaching performance and lower decoding complexity have made them the best choice for many wired and wireless applications. This paper gives an overview about LDPC codes and compares the Gallager’s method, Reed-Solomon based algebraic method and the Progressive edge growth (PEG) combinatorial method for the construction of regular LDPC codes.

•Jan 1, 2012•7 citations
LDPC codes are one of the hottest topics in coding theory today. Originally invented in the early 1960’s, they have experienced an amazing comeback in the last few years. Unlike many other classes of codes, LDPC codes are already equipped with very fast (probabilistic) encoding and decoding algorithms. The question is that of the design of the codes such that these algorithms can recover the original codeword in the face of large amounts of noise. New analytic and combinatorial tools make it possible to solve the design problem. This makes LDPC codes not only attractive from a theoretical point of view, but also perfect for practical applications. In this note I will give a brief overview of the origins of LDPC codes and the methods used for their analysis and design.
The class of low-density parity-check (LDPC) codes was introduced by Gallager in his thesis in 1961 [2]. Until the invention of turbo codes, they were largely neglected, but received a lot of interest lately, due to the possibility of designing LDPC codes within 0.0045 dB of the Shannon limit. We review in this project techniques used to analyze the performance of LDPC codes under a message-passing decoding algorithm, namely belief propagation (BP) [4][5]. This analysis gives us the tools to design good LDPC codes. We will first take the simpler example of transmission over the class of binary erasure channels (BEC). We will then see how it is possible to extend the results for the BEC to the much more general class of symmetric channels.
Low Density Parity Check(LDPC) codes is one of the high topics of the channel coding theory and has been paid more and more attention.This paper begins with a brief review of channel coding theories.Then the iterative decoding algorithm of LDPC codes,so-called as Sum-Product algorithm or Belief Propagation algorithm,is represented in detail.And the construction of LDPC codes by means of random bipartite graph and algebraic constructions,and the performance analysis by Density Evolution theory,Gaussian Approximation method and Extrinsic Information Transfer(EXIT) charts etc.,are respectively discussed.Finally,the latest study results of LDPC codes are presented and some open questions about LDPC codes are provided.
The discovery of turbo codes [5] and the subsequent rediscovery of low-density parity-check (LDPC) codes [9, 18] represent a major milestone in the field of coding theory. These two classes of codes can achieve realistic bit error rates, between 10−5 and 10−12, with signalto- noise ratios that are only slightly above the minimum possible for a given channel and code rate established by Shannon’s original capacity theorems. In this sense, these codes are said to be near-capacity-achieving codes and are sometimes considered to have solved (in the engineering sense, at least) the coding problem for the additive white Gaussian noise (AWGN) channel and its derivative channels. Perhaps the most important commonality between turbo and low-density parity-check codes is that they both utilize iterative message-passing decoding algorithms. For turbo codes, one uses the so-called turbo decoding algorithm, and for LDPC codes, both the sumproduct (SP) and the min-sum (MS) algorithms are used. The success of the various iterative message-passing algorithms is sometimes said to have ushered in a new era of “modern” coding theory in which the design emphasis has shifted from optimizing some code property, such as minimum distance, to optimizing the corresponding decoding structure of the code, such as the degree profile [24, 25], with respect to the behavior of a message-passing decoder. As successful as these codes and decoders have been in terms of application, there are several major questions that must be answered before a complete understanding of them can be achieved. The theoretical research in the area of capacity-achieving codes is focused on two main themes. The first theme is whether different types of capacity-achieving codes have common encoder and structural properties. In [17], it was claimed that turbo codes could be viewed as LDPC codes, but the relationship was not made explicit. More recently, P´erez, his student Jiang, and others [11, 16] developed a construction for the parity-check matrices of arbitrary turbo codes that clearly connects the components of the turbo encoder to the resulting structure of the parity-check matrix. From a more abstract perspective, turbo codes and low-density parity-check codes are examples of codes with long block lengths that exhibit the random structure inherent in Shannon’s original theorems. The second and more active research theme is the determination of the behavior of iterative message-passing decoding and the relationships between the various decoding algorithms. The dominant problem in this area is to understand the non-codeword decoder errors that occur in computer simulations of LDPC codes with iterative message-passing decoders. Motivated by empirical observations of the non-codeword outputs of LDPC decoders, the notion of stopping sets was first introduced by Forney, et al. [8] in 2001. Two years later, a formal definition of stopping sets was given by Changyan, et al. [6]. They demonstrated that the bit and block error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix. (Here, a stopping set S is a subset of the set of variable nodes such that all neighboring check nodes of S are connected to S at least twice.)
Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel
Due to the increasing popularity of LDPC codes and its demand for future applications, first time in this paper, LDPC coding techniques have been systematically summarized and analyzed. The paper gives the comprehensive review of LDPC encoder, decoder and its architecture for simulation and implementation. The paper is specially intended for giving an insight of the algorithmic overview of the LDPC encoder, decoder and its architecture for research and practical purposes. The original belief propagation algorithm (BPA) , logarithmic model of BPA , and the other simplified form of the logarithmic sum product algorithms (SPA) has been elaborated and analyzed for medium and short length codes under AWGN channel