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

International Symposium on Wireless Communication Systems

On the Design of LDPC-Based Error-Reducing Codes

Dawit Simegn, Kirill Andreev, Pavel S. Rybin, Alexey Frolov

Published Jul 14, 2024• 2 citations
Publisher

Abstract

In this paper, we continue our investigation into the error-reducing properties of superposition codes started in Andreev, et al. (2023), where the focus was on Sparse Regression Codes (SPARCs) with Gaussian signals. However, despite their high performance, SPARCs are known to have noticeable limitations in their application due to their high decoding complexity. This prompted us to propose a Low-Density Parity Check (LDPC)-based superposition scheme with low-complexity Soft Successive Interference Cancellation (SIC) decoding. In this paper, we focus on such a scheme and perform a detailed analysis of it. We have developed a low-complexity quantized density evolution (DE) procedure for the proposed scheme under the SIC decoder to estimate the output bit error rate. It is shown that the obtained DE procedure quite accurately predicts the behavior of the considered LDPC-based superposition scheme. The procedure predicts not only the waterfall region, but also the error-floor region, which we assume to be caused by interference of component LDPC codes. This helps us to obtain highly optimized constructions of proto-graphs of LDPC code components and significantly improve the bit error rate performance of the whole construction. In addition, for the proposed scheme we have analyzed the output error count distribution, which is crucial for concatenated code constructions, where usually error-reducing codes are used as inner code. All numerical results and analysis are presented at the end of the paper.

DOI
10.1109/iswcs61526.2024.10639052

Related papers

Improving the Error Floor Performance of LDCP Codes with Better Codes and Better Decoders

Dung Viet Nguyen

Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.

•Jan 1, 2012•1 citation

Neural Network-Based Iterative Decoding, Code Design, and Erasure Correction of Low-Density Parity-Check Codes

Xin Wei Xiao

Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems for the past three decades due to their capacity-approaching error correction capability under the Belief Propagation (BP) decoding algorithms. In this dissertation, we investigate three topics related to efficient and effective decoding algorithms and the code design of LDPC codes. In the first part of this dissertation, we propose a methodology with the help of artificial intelligence to design Finite Alphabet Iterative Decoders (FAID) for LDPC codes, which are not only of great theoretical but also practical importance. This model-driven neural network (NN) framework unfolds the decoding iterations, introduces quantized neural networks (QNN) to model the FAIDs, and proposes a new cost function, namely, bit error rate (BER), to address the inefficiency in discrete-output channel scenarios. The low precision activations in the QNN and quantization in the cost functions cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We design and leverage straight-through estimators as surrogate gradients to tackle this issue and provide a joint training scheme. These QNN-aided FAIDs, are capable of surpassing the floating-point BP algorithms, with much lower complexity and faster convergence. The QNN-aided approach is general, as it can be applied to both continuous and discrete-output channels. In the second part of this dissertation, we propose a new code construction of LDPC codes based on the conventional parity-check matrices of Reed-Solomon (RS) codes. We investigate the girth and cycle structure and introduce an efficient searching algorithm to reduce short cycles in their Tanner graphs and to construct LDPC codes with a girth of at least eight. We use masking to further reduce the number of short cycles and to adjust the column and row weights of the parity-check matrices of the constructed codes for performance improvement. Our designs are systematic and flexible, which balance the requirements of good waterfall performance and low error-floor while maintaining a structure that facilitates implementation. In the third part of this dissertation, we investigate binary quasi-cyclic (QC) LDPC codes and their capability to correct phased bursts of erasures. We prove that the peeling algorithm when applied to such parity-check matrices of column weight two can correct all erasures that can be corrected by a maximum likelihood (ML) decoder. We show that by modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. For the Additive White Gaussian Noise (AWGN) channel, we design QC LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel. Our analysis of QC-LDPC codes with parity-check matrices of column weight two is rather comprehensive as we determine, for all such codes, their dimensions, minimum Hamming distances, and their capabilities to correct phased bursts.

•Jan 1, 2021•0 citations

Error Floors of LDPC Codes and Related Topics

Brian K. Butler

Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</

•Jan 1, 2013•1 citation

Error Floors of LDPC Codes and Related Topics - eScholarship

Brian K. Butler

Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</

•Sep 11, 2013•0 citations

Turbo product decoding of cubic tensor codes

Sarah Khalifeh, Ken R. Duffy, Muriel Médard

Long, powerful soft detection forward error correction codes are typically constructed by concatenation of shorter component codes that are decoded through iterative Soft-Input Soft-Output (SISO) procedures. The current gold-standard is Low Density Parity Check (LDPC) codes, which are built from weak single parity check component codes that are capable of producing accurate SO. Due to the recent development of SISO decoders that produce highly accurate SO with codes that have multiple redundant bits, square product code constructions that can avail of more powerful component codes have been shown to be competitive with the LDPC codes in the 5G New Radio standard in terms of decoding performance while requiring fewer iterations to converge. Motivated by applications that require more powerful low-rate codes, in the present paper we explore the possibility of extending this design space by considering the construction and decoding of cubic tensor codes.

arXiv:2412.14017•Conference on Information Sciences and Systems•Mar 19, 2025•2 citations

On the Serial Concatenation of LDPC Codes

Fedor I. Ivanov, Aleksey Kuvshinov

Concatenated codes are effectively used in different approaches of error-correcting theory. We suggest new concatenated code construction that is composed of outer LDPC code and a particular designed inner LDPC code. Special optimization procedure was developed to obtain inner code with specific error-correcting characteristics. We apply the decoder of woven codes to this construction, while reducing the complexity of decoding procedure compared to a classic decoder of LDPC code. Furthermore, we improve the performance of our scheme with puncturing the code symbols. The resulting concatenated construction outperforms low-rate LDPC from the 5G standard. Besides this, we demonstrate the performance of code with a special parity-check matrix consisting of parity-check matrices of inner and outer codes from our suggested construction.

International Conference on Advanced Technologies, Systems and Services in Telecommunications (TELSIKS)•Oct 25, 2023•3 citations
In this paper, we continue our investigation into the error-reducing properties of superposition codes started in Andreev, et al. (2023), where the focus was on Sparse Regression Codes (SPARCs) with Gaussian signals. However, despite their high performance, SPARCs are known to have noticeable limitations in their application due to their high decoding complexity. This prompted us to propose a Low-Density Parity Check (LDPC)-based superposition scheme with low-complexity Soft Successive Interference Cancellation (SIC) decoding. In this paper, we focus on such a scheme and perform a detailed analysis of it. We have developed a low-complexity quantized density evolution (DE) procedure for the proposed scheme under the SIC decoder to estimate the output bit error rate. It is shown that the obtained DE procedure quite accurately predicts the behavior of the considered LDPC-based superposition scheme. The procedure predicts not only the waterfall region, but also the error-floor region, which we assume to be caused by interference of component LDPC codes. This helps us to obtain highly optimized constructions of proto-graphs of LDPC code components and significantly improve the bit error rate performance of the whole construction. In addition, for the proposed scheme we have analyzed the output error count distribution, which is crucial for concatenated code constructions, where usually error-reducing codes are used as inner code. All numerical results and analysis are presented at the end of the paper.
Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum-product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four-cycles. A new class of bit flipping algorithms for LDPC codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.
Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems for the past three decades due to their capacity-approaching error correction capability under the Belief Propagation (BP) decoding algorithms. In this dissertation, we investigate three topics related to efficient and effective decoding algorithms and the code design of LDPC codes. In the first part of this dissertation, we propose a methodology with the help of artificial intelligence to design Finite Alphabet Iterative Decoders (FAID) for LDPC codes, which are not only of great theoretical but also practical importance. This model-driven neural network (NN) framework unfolds the decoding iterations, introduces quantized neural networks (QNN) to model the FAIDs, and proposes a new cost function, namely, bit error rate (BER), to address the inefficiency in discrete-output channel scenarios. The low precision activations in the QNN and quantization in the cost functions cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We design and leverage straight-through estimators as surrogate gradients to tackle this issue and provide a joint training scheme. These QNN-aided FAIDs, are capable of surpassing the floating-point BP algorithms, with much lower complexity and faster convergence. The QNN-aided approach is general, as it can be applied to both continuous and discrete-output channels. In the second part of this dissertation, we propose a new code construction of LDPC codes based on the conventional parity-check matrices of Reed-Solomon (RS) codes. We investigate the girth and cycle structure and introduce an efficient searching algorithm to reduce short cycles in their Tanner graphs and to construct LDPC codes with a girth of at least eight. We use masking to further reduce the number of short cycles and to adjust the column and row weights of the parity-check matrices of the constructed codes for performance improvement. Our designs are systematic and flexible, which balance the requirements of good waterfall performance and low error-floor while maintaining a structure that facilitates implementation. In the third part of this dissertation, we investigate binary quasi-cyclic (QC) LDPC codes and their capability to correct phased bursts of erasures. We prove that the peeling algorithm when applied to such parity-check matrices of column weight two can correct all erasures that can be corrected by a maximum likelihood (ML) decoder. We show that by modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. For the Additive White Gaussian Noise (AWGN) channel, we design QC LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel. Our analysis of QC-LDPC codes with parity-check matrices of column weight two is rather comprehensive as we determine, for all such codes, their dimensions, minimum Hamming distances, and their capabilities to correct phased bursts.
Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</
Since their rediscovery in the late 1990s, low-density parity-check (LDPC) codes have rapidly become one the most important classes of error correcting codes. LDPC codes have a graphical description and are generally decoded iteratively. The graph of an iteratively decoded code's error rate performance versus the channel quality is typically divided into two regions. The error floor region appears at higher channel quality and is characterized by a more gradual decrease in error rate as channel quality improves. For iterative decoders the error floor is apparently determined by small structures within the code that are specific to the selected graphical description of the code and subtle details of the decoding algorithm. This thesis addresses several issues of LDPC error floors in the additive white Gaussian noise channel. First, we find the source of several well publicized error floors to be numerical issues within the message-passing decoder. We propose numerical improvements to several decoding formulations which substantially lower error floors. Next, we examine and refine error-floor prediction models. A time-variant linear state-space model is presented and analyzed. Graph theory is applied to analyze the small error-prone structures within the code. While we find our techniques encounter considerable problems in determining the error floors for iterative decoders with unrestricted dynamic range, their predictions are quite accurate when significant range restrictions are present. The final issue of LDPC error floors which we address relates to the minimum distance of quasi-cyclic (QC) LDPC codes. We derive improved minimum distance upper bounds for codes which are punctured and codes which contain a significant number of zeros in their protomatrices. These bound are then applied to a family of protograph-based LDPC codes standardized for use in deep-space communications. In the case of the rate-1/2 code, our upper bounds demonstrate that the previously promulgated ensemble lower bounds do not apply to QC constructions at block lengths beyond 4400 bits. The last part of this dissertation is a fairly separate piece of work on bounding the spectral radius of a large class of nonnegative matrices. We apply these bounds to digraphs and derive several associated equality conditions.</
Long, powerful soft detection forward error correction codes are typically constructed by concatenation of shorter component codes that are decoded through iterative Soft-Input Soft-Output (SISO) procedures. The current gold-standard is Low Density Parity Check (LDPC) codes, which are built from weak single parity check component codes that are capable of producing accurate SO. Due to the recent development of SISO decoders that produce highly accurate SO with codes that have multiple redundant bits, square product code constructions that can avail of more powerful component codes have been shown to be competitive with the LDPC codes in the 5G New Radio standard in terms of decoding performance while requiring fewer iterations to converge. Motivated by applications that require more powerful low-rate codes, in the present paper we explore the possibility of extending this design space by considering the construction and decoding of cubic tensor codes.
Concatenated codes are effectively used in different approaches of error-correcting theory. We suggest new concatenated code construction that is composed of outer LDPC code and a particular designed inner LDPC code. Special optimization procedure was developed to obtain inner code with specific error-correcting characteristics. We apply the decoder of woven codes to this construction, while reducing the complexity of decoding procedure compared to a classic decoder of LDPC code. Furthermore, we improve the performance of our scheme with puncturing the code symbols. The resulting concatenated construction outperforms low-rate LDPC from the 5G standard. Besides this, we demonstrate the performance of code with a special parity-check matrix consisting of parity-check matrices of inner and outer codes from our suggested construction.