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

European Transactions on Telecommunications

An algorithm for the computation of the minimum distance of LDPC codes

F. Daneshgaran, Massimiliano Laddomada, M. Mondin

Published Jan 1, 2006• 20 citations
Publisher

Abstract

Abstract The evaluation of the minimum distance of low‐density parity‐check (LDPC) codes remains an open problem due to the rather large dimension of the parity check matrix H associated with any practical code. In this article, we propose an effective modification of the error impulse (EI) technique for computation of the minimum distance of the LDPC codes. The EI method is successfully applied to sub‐optimum decoding algorithms such as the iterative MAP decoding algorithm for turbo codes. We present novel modifications and extensions of this method to the sub‐optimum iterative sum‐product algorithm for LDPC codes. The performance of LDPC codes may be limited by pseudo‐codewords. There are, however, cases when the LDPC decoder behaves as a maximum‐likelihood (ML) decoder. This is specially so for randomly constructed LDPC codes operating at medium to high SNR values. In such cases, estimation of the minimum distance d m using the error‐impulse method can be useful to assess asymptotic performance. In short, apart from theoretical interest in achievable d m , the technique is useful in checking whether an LDPC code is poor by virtue of having a low d m . But, if a code has a high d m , simulations would still be needed to assess real performance. Copyright © 2006 AEIT.

DOI
10.1002/ett.1091

Related papers

An algorithm for the estimation of the minimum distance of LDPC codes

F. Daneshgaran, Massimiliano Laddomada, M. Mondin

The evaluation of the minimum distance of low-density parity-check (LDPC) codes remains an open problem due to the rather large dimension of the parity check matrix H associated with any practical code. In this article, we propose an effective modification of the error impulse (EI) technique for estimation of the minimum distance of the LDPCs. The EI method is successfully applied to suboptimum decoding algorithms such as the iterative MAP decoding algorithm for turbo codes. We present novel modifications and extensions of this method to the suboptimum iterative sum-product algorithm for LDPCs. Simulation results validate the functionality of the proposed technique. Simulations focus on a particular class of LDPC codes, but our approach is general and applies to any LDPC code.

IEEE Wireless Communications and Networking Conference•Apr 25, 2005•5 citations

On the computation of the minimum distance of low-density parity-check codes

Xiao-Yu Hu, M.P.C. Fossorier, Evangelos S. Eleftheriou

Low-density parity-check (LDPC) codes in their broader-sense definition are linear codes whose parity-check matrices have fewer 1s than 0s. Finding their minimum distance is therefore in general an NP-hard problem. We propose a randomized algorithm called nearest nonzero codeword search (NNCS) approach to tackle this problem for iteratively decodable LDPC codes. The principle of the NNCS approach is to search codewords locally around the all-zero codeword perturbed by minimal noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum-Hamming- weight codeword whose Hamming weight is equal to the minimum distance of the linear code. This approach has its roots in Berrou et al.'s error-impulse method and a form of Fossorier's list decoding for LDPC codes.

International Conference on Communications•Jan 1, 2004•156 citations

Computing the Minimum Distance of Nonbinary LDPC Codes

Lei Liu, Jie Huang, Wuyang Zhou +1 more

Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.

IEEE Transactions on Communications•Jul 1, 2012•8 citations

Techniques for the decoding of low density parity check codes: efficient simulation, algorithm improvement and implementation

Babak Daneshrad, Enver Çavuş

After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.

•Jan 1, 2007•2 citations

A probabilistic computation method for the weight distribution of low-density parity-check codes

Masanori Hirotomo, Masami Mohri, Masakatu Morii

Low-density parity-check (LDPC) codes achieve outstanding performance by the sum-product decoder. Its performance approaches the maximum-likelihood (ML) decoding performance at high SNR region. Upper bounds on the error probability of the ML decoded LDPC codes can be computed using the weight distribution. Recently, X.-Y. Hu et al. presented an approximate algorithm for estimating the weight distribution of LDPC codes. However, the weight distribution computed by their method depends on the iterative decoding algorithm, and is not always estimated exactly. In this paper, we propose a probabilistic method for computing the low-part weight distribution of LDPC codes. Using our method, the approximate weight distribution of LDPC codes can be computed with high accuracy

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•30 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
Abstract The evaluation of the minimum distance of low‐density parity‐check (LDPC) codes remains an open problem due to the rather large dimension of the parity check matrix H associated with any practical code. In this article, we propose an effective modification of the error impulse (EI) technique for computation of the minimum distance of the LDPC codes. The EI method is successfully applied to sub‐optimum decoding algorithms such as the iterative MAP decoding algorithm for turbo codes. We present novel modifications and extensions of this method to the sub‐optimum iterative sum‐product algorithm for LDPC codes. The performance of LDPC codes may be limited by pseudo‐codewords. There are, however, cases when the LDPC decoder behaves as a maximum‐likelihood (ML) decoder. This is specially so for randomly constructed LDPC codes operating at medium to high SNR values. In such cases, estimation of the minimum distance d m using the error‐impulse method can be useful to assess asymptotic performance. In short, apart from theoretical interest in achievable d m , the technique is useful in checking whether an LDPC code is poor by virtue of having a low d m . But, if a code has a high d m , simulations would still be needed to assess real performance. Copyright © 2006 AEIT.
The evaluation of the minimum distance of low-density parity-check (LDPC) codes remains an open problem due to the rather large dimension of the parity check matrix H associated with any practical code. In this article, we propose an effective modification of the error impulse (EI) technique for estimation of the minimum distance of the LDPCs. The EI method is successfully applied to suboptimum decoding algorithms such as the iterative MAP decoding algorithm for turbo codes. We present novel modifications and extensions of this method to the suboptimum iterative sum-product algorithm for LDPCs. Simulation results validate the functionality of the proposed technique. Simulations focus on a particular class of LDPC codes, but our approach is general and applies to any LDPC code.
Low-density parity-check (LDPC) codes in their broader-sense definition are linear codes whose parity-check matrices have fewer 1s than 0s. Finding their minimum distance is therefore in general an NP-hard problem. We propose a randomized algorithm called nearest nonzero codeword search (NNCS) approach to tackle this problem for iteratively decodable LDPC codes. The principle of the NNCS approach is to search codewords locally around the all-zero codeword perturbed by minimal noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum-Hamming- weight codeword whose Hamming weight is equal to the minimum distance of the linear code. This approach has its roots in Berrou et al.'s error-impulse method and a form of Fossorier's list decoding for LDPC codes.
Finding the minimum distance of low-density-parity-check (LDPC) codes is an NP-hard problem. Different from all existing works that focus on binary LDPC codes, we in this paper aim to compute the minimum distance of nonbinary LDPC codes, motivated by the fact that operating in a large Galois field provides one important degree of freedom to achieve both good waterfall and error-floor performance. Our method is based on the existing nearest nonzero codeword search (NNCS) method, but several modifications are incorporated for nonbinary LDPC codes, including the modified error impulse pattern, the dithering method, and the nonbinary decoder. Numerical results on the estimated minimum distances show that a code's minimum distance can be increased by careful selection of nonzero elements of the parity check matrix, or by increasing the mean column weight, or by increasing the size of the Galois field. These results support observations that have been made based on simulated performance in the literature. Finally, we provide an upper bound on the minimum distance for nonbinary quasi-cyclic LDPC codes.
After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.
Low-density parity-check (LDPC) codes achieve outstanding performance by the sum-product decoder. Its performance approaches the maximum-likelihood (ML) decoding performance at high SNR region. Upper bounds on the error probability of the ML decoded LDPC codes can be computed using the weight distribution. Recently, X.-Y. Hu et al. presented an approximate algorithm for estimating the weight distribution of LDPC codes. However, the weight distribution computed by their method depends on the iterative decoding algorithm, and is not always estimated exactly. In this paper, we propose a probabilistic method for computing the low-part weight distribution of LDPC codes. Using our method, the approximate weight distribution of LDPC codes can be computed with high accuracy
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.