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

IEEE International Conference on Communication Systems (ICCS)

Extended optimum decoding for LDPC codes based on exhaustive tree search algorithm

Li Yang, Martin Tomlinson, Marcel Ambroze, Jing Cai

Published Nov 1, 2010• 1 citation
Publisher

Abstract

A maximum-likelihood decoding algorithm inspired by information set decoding is realised for LDPC codes or linear block codes with sparse parity-check matrices of moderate codeword lengths over the AWGN channel. The extension involves an exhaustive branch and bound tree-search based algorithm for finding all small Euclidean distance error vectors. It provides an approach of searching on the bounded n-bit positions, which involves 2kcombinatorial dual codes based on the corresponding parity-check matrix, to achieve the near-optimum decoding output with attainable computational complexity. Soft decision decoding results are presented for some well-known LDPC codes demonstrating near-optimum maximum-likelihood performance.

DOI
10.1109/iccs.2010.5685891

Related papers

An Exhaustive Tree Search for Stopping Sets of LDPC Codes

Martin Tomlinson, Cen Jung Tjhai, Marcel Ambroze +2 more

The indicative performance of an LDPC code may be determined from exhaustive analysis of the low-weight spectral terms of the code’s stopping sets which by definition includes the low-weight codewords. In a landmark paper, Rosnes and Ytrehus showed that exhaustive, low-weight stopping set analysis of codes whose parity-check matrix is sparse can be carried out using a bounded tree search over the length of the code. For an (n, k) code, the potential total search space is of size $$2^n$$ but a good choice of bound dramatically reduces this search space to a practical size. Indeed, the choice of bound is critical to the success of the algorithm. It is shown in this chapter that an improved algorithm can be obtained if the bounded tree search is applied to a set of k information bits since the potential total search space is reduced to size $$2^k$$ . Since such a restriction will only find codewords and not all stopping sets, a class of bits is defined as unsolved parity bits, and these are also searched as appended bits in order to find all low-weight stopping sets. Weight spectrum and stopping set results are presented for commonly used WiMax LDPC codes in addition to some other well known LDPC codes.

Signals and communication technology•Jan 1, 2017•0 citations

Exhausting Error-Prone Patterns in LDPC Codes

Chih-Chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

It is proved in this work that exhaustively determining bad patterns in arbitrary, finite low-density parity-check (LDPC) codes, including stopping sets for binary erasure channels (BECs) and trapping sets (also known as near-codewords) for general memoryless symmetric channels, is an NP-complete problem, and efficient algorithms are provided for codes of practical short lengths n~=500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size <=13 and the trapping sets of size <=11 can be efficiently exhaustively determined for the first time, and the resulting exhaustive list is of great importance for code analysis and finite code optimization. The featured tree-based narrowing search distinguishes this algorithm from existing ones for which inexhaustive methods are employed. One important byproduct is a pair of upper bounds on the bit-error rate (BER) & frame-error rate (FER) iterative decoding performance of arbitrary codes over BECs that can be evaluated for any value of the erasure probability, including both the waterfall and the error floor regions. The tightness of these upper bounds and the exhaustion capability of the proposed algorithm are proved when combining an optimal leaf-finding module with the tree-based search. These upper bounds also provide a worst-case-performance guarantee which is crucial to optimizing LDPC codes for extremely low error rate applications, e.g., optical/satellite communications. Extensive numerical experiments are conducted that include both randomly and algebraically constructed LDPC codes, the results of which demonstrate the superior efficiency of the exhaustion algorithm and its significant value for finite length code optimization.

arXiv:cs/0609046•Sep 11, 2006•41 citations

Multitree decoding and multitree-aided LDPC decoding

Maja Ostojic, Hans‐Andrea Loeliger

New decoding algorithms for linear codes are proposed. The first part of the paper considers decoding general binary linear codes by searching multiple trees, which is shown to achieve near maximum-likelihood performance for short block lengths. The second part of the paper considers decoding low-density parity check (ldpc) codes by means of repeated decoding attempts by standard sum-product message passing. Each decoding attempt starts from modified channel output, where some of the bits are clamped to a fixed value. The values of the fixed bits are obtained from multitree search.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•2 citations

Finding the Exhaustive List of Small Fully Absorbing Sets and Designing the Corresponding Low Error-Floor Decoder

Gyu Bum Kyung, Chih-Chun Wang

This work provides an efficient exhaustive search algorithm for finding all small fully absorbing sets (FASs) of any arbitrary low-density parity-check (LDPC) code. The proposed algorithm is based on the branch-&-bound principle for solving NP-complete problems. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised with new node selection and tree-trimming mechanisms. The resulting algorithm is capable of finding all FASs of size <; 7 for LDPC codes of length <; 1000. When limiting the FASs of interest to those with the number of violated parity-check nodes <; 3, the proposed algorithm is capable of finding all such FASs of size <; 14 for LDPC codes of lengths <; 1000. The resulting exhaustive list of small FASs is then used to devise a new efficient post-processing low-error floor LDPC decoder. The numerical results show that by exploiting the exhaustive list of small FASs, the proposed post-processing decoder can significantly lower the error-floor performance of a given LDPC code. For various example codes of length <; 3000, the proposed post-processing decoder lowers the error floor by a couple of orders of magnitude when compared to the standard belief propagation decoder and by an order of magnitude when compared to other existing low error-floor decoders.

IEEE Transactions on Communications•Jun 1, 2012•42 citations

Exhaustive search for small fully absorbing sets and the corresponding low error-floor decoder

Gyu Bum Kyung, Chih-Chun Wang

This work provides an exhaustive search algorithm for finding small fully absorbing sets (FASs) of arbitrary low-density parity-check (LDPC) codes. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised. New node selection and the tree-trimming mechanisms are designed to further enhance the efficiency of the algorithm. The proposed algorithm is capable of finding all FASs of size ≤ 11 with no larger than 2 induced odd-degree check nodes for LDPC codes of length ≤ 1000. The resulting exhaustive list of small FASs is then used to devise a new post-processing decoder. Numerical results show that by taking advantage of the exhaustive list of small FASs, the proposed decoder significantly lowers the error floor for codes of practical lengths and outperforms the state-of-the-art low-error-floor decoders.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•24 citations

A decoding algorithm for LDPC codes over erasure channels with sporadic errors

Gianluigi Liva, Enrico Paolini, Balázs Matuz +1 more

An efficient decoding algorithm for low-density parity-check (LDPC) codes on erasure channels with sporadic errors (i.e., binary error-and-erasure channels with error probability much smaller than the erasure probability) is proposed and its performance analyzed. A general single-error multiple-erasure (SEME) decoding algorithm is first described, which may be in principle used with any binary linear block code. The algorithm is optimum whenever the non-erased part of the received word is affected by at most one error, and is capable of performing error detection of multiple errors. An upper bound on the average block error probability under SEME decoding is derived for the linear random code ensemble. The bound is tight and easy to implement. The algorithm is then adapted to LDPC codes, resulting in a simple modification to a previously proposed efficient maximum likelihood LDPC erasure decoder which exploits the parity-check matrix sparseness. Numerical results reveal that LDPC codes under efficient SEME decoding can closely approach the average performance of random codes.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2010•11 citations
A maximum-likelihood decoding algorithm inspired by information set decoding is realised for LDPC codes or linear block codes with sparse parity-check matrices of moderate codeword lengths over the AWGN channel. The extension involves an exhaustive branch and bound tree-search based algorithm for finding all small Euclidean distance error vectors. It provides an approach of searching on the bounded n-bit positions, which involves 2kcombinatorial dual codes based on the corresponding parity-check matrix, to achieve the near-optimum decoding output with attainable computational complexity. Soft decision decoding results are presented for some well-known LDPC codes demonstrating near-optimum maximum-likelihood performance.
The indicative performance of an LDPC code may be determined from exhaustive analysis of the low-weight spectral terms of the code’s stopping sets which by definition includes the low-weight codewords. In a landmark paper, Rosnes and Ytrehus showed that exhaustive, low-weight stopping set analysis of codes whose parity-check matrix is sparse can be carried out using a bounded tree search over the length of the code. For an (n, k) code, the potential total search space is of size 2n2^n2n but a good choice of bound dramatically reduces this search space to a practical size. Indeed, the choice of bound is critical to the success of the algorithm. It is shown in this chapter that an improved algorithm can be obtained if the bounded tree search is applied to a set of k information bits since the potential total search space is reduced to size 2k2^k2k . Since such a restriction will only find codewords and not all stopping sets, a class of bits is defined as unsolved parity bits, and these are also searched as appended bits in order to find all low-weight stopping sets. Weight spectrum and stopping set results are presented for commonly used WiMax LDPC codes in addition to some other well known LDPC codes.
It is proved in this work that exhaustively determining bad patterns in arbitrary, finite low-density parity-check (LDPC) codes, including stopping sets for binary erasure channels (BECs) and trapping sets (also known as near-codewords) for general memoryless symmetric channels, is an NP-complete problem, and efficient algorithms are provided for codes of practical short lengths n~=500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size <=13 and the trapping sets of size <=11 can be efficiently exhaustively determined for the first time, and the resulting exhaustive list is of great importance for code analysis and finite code optimization. The featured tree-based narrowing search distinguishes this algorithm from existing ones for which inexhaustive methods are employed. One important byproduct is a pair of upper bounds on the bit-error rate (BER) & frame-error rate (FER) iterative decoding performance of arbitrary codes over BECs that can be evaluated for any value of the erasure probability, including both the waterfall and the error floor regions. The tightness of these upper bounds and the exhaustion capability of the proposed algorithm are proved when combining an optimal leaf-finding module with the tree-based search. These upper bounds also provide a worst-case-performance guarantee which is crucial to optimizing LDPC codes for extremely low error rate applications, e.g., optical/satellite communications. Extensive numerical experiments are conducted that include both randomly and algebraically constructed LDPC codes, the results of which demonstrate the superior efficiency of the exhaustion algorithm and its significant value for finite length code optimization.
New decoding algorithms for linear codes are proposed. The first part of the paper considers decoding general binary linear codes by searching multiple trees, which is shown to achieve near maximum-likelihood performance for short block lengths. The second part of the paper considers decoding low-density parity check (ldpc) codes by means of repeated decoding attempts by standard sum-product message passing. Each decoding attempt starts from modified channel output, where some of the bits are clamped to a fixed value. The values of the fixed bits are obtained from multitree search.
This work provides an efficient exhaustive search algorithm for finding all small fully absorbing sets (FASs) of any arbitrary low-density parity-check (LDPC) code. The proposed algorithm is based on the branch-&-bound principle for solving NP-complete problems. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised with new node selection and tree-trimming mechanisms. The resulting algorithm is capable of finding all FASs of size <; 7 for LDPC codes of length <; 1000. When limiting the FASs of interest to those with the number of violated parity-check nodes <; 3, the proposed algorithm is capable of finding all such FASs of size <; 14 for LDPC codes of lengths <; 1000. The resulting exhaustive list of small FASs is then used to devise a new efficient post-processing low-error floor LDPC decoder. The numerical results show that by exploiting the exhaustive list of small FASs, the proposed post-processing decoder can significantly lower the error-floor performance of a given LDPC code. For various example codes of length <; 3000, the proposed post-processing decoder lowers the error floor by a couple of orders of magnitude when compared to the standard belief propagation decoder and by an order of magnitude when compared to other existing low error-floor decoders.
This work provides an exhaustive search algorithm for finding small fully absorbing sets (FASs) of arbitrary low-density parity-check (LDPC) codes. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised. New node selection and the tree-trimming mechanisms are designed to further enhance the efficiency of the algorithm. The proposed algorithm is capable of finding all FASs of size ≤ 11 with no larger than 2 induced odd-degree check nodes for LDPC codes of length ≤ 1000. The resulting exhaustive list of small FASs is then used to devise a new post-processing decoder. Numerical results show that by taking advantage of the exhaustive list of small FASs, the proposed decoder significantly lowers the error floor for codes of practical lengths and outperforms the state-of-the-art low-error-floor decoders.
An efficient decoding algorithm for low-density parity-check (LDPC) codes on erasure channels with sporadic errors (i.e., binary error-and-erasure channels with error probability much smaller than the erasure probability) is proposed and its performance analyzed. A general single-error multiple-erasure (SEME) decoding algorithm is first described, which may be in principle used with any binary linear block code. The algorithm is optimum whenever the non-erased part of the received word is affected by at most one error, and is capable of performing error detection of multiple errors. An upper bound on the average block error probability under SEME decoding is derived for the linear random code ensemble. The bound is tight and easy to implement. The algorithm is then adapted to LDPC codes, resulting in a simple modification to a previously proposed efficient maximum likelihood LDPC erasure decoder which exploits the parity-check matrix sparseness. Numerical results reveal that LDPC codes under efficient SEME decoding can closely approach the average performance of random codes.