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 Symposium on Information Theory (ISIT)

Computing the minimum distances of linear codes by the error impulse method

Claude Berrou, Sandrine Vaton

Published Jun 25, 2003• 41 citations
Publisher

Abstract

A new method for computing minimum distances is proposed and justified. Unlike classical techniques that rely on the exhaustive or partial enumeration of codewords with weights lower than or equal to the minimum distance, this new method is based on the ability of the soft-in decoder, when it exists, to overcome error impulse input patterns.

DOI
10.1109/isit.2002.1023277

Related papers

Computing the minimum distance of linear codes by the error impulse method

Claude Berrou, Sandrine Vaton, Michel Jézéquel +1 more

A new method for computing the minimum distances of linear error-correcting codes is proposed and justified. Unlike classical techniques that rely on exhaustive or partial enumeration of codewords, this new method is based on the ability of the Soft-In decoder to overcome Error Impulse input patterns. It is shown that the maximum magnitude of the Error Impulse that can be corrected by the decoder is directly related to the minimum distance. This leads to a very fast algorithm to obtain minimum distances of any linear code whatever the block size and the code rate considered. In particular, the method can be advantageously worked out for turbo-like concatenated codes.

Globecom•Mar 22, 2004•72 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

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

F. Daneshgaran, Massimiliano Laddomada, M. Mondin

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.

European Transactions on Telecommunications•Jan 1, 2006•20 citations

A new approach to the general minimum distance decoding problem: The zero-neighbors algorithm

Lev B. Levitin, Carlos R. P. Hartmann

Minimum distance decoding (MDD) for a general error-correcting linear code is a hard computational problem that recently has been shown to beNP-hard. The complexity of known decoding algorithms is determined by\min (2^{k},2^{n-k}), wherenis the code length andkis the number of information digits. Two new algorithms are suggested that reduce substantially the complexity of MDD. The algorithms use a new concept of zero neighbors--a special set of codewords. Only these codewords (which can be computed in advance) should be stored and used in the decoding procedure. The number of zero neighbors is shown to be very small compared with\min (2^{k},2^{n-k})forn \gg 1and a wide range of code ratesR = k/n. For example, forR \approx 0.5this number grows approximately as a square root of the number of codewords.

IEEE Transactions on Information Theory•May 1, 1985•34 citations

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

Hard- and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes (Corresp.)

Martin Bossert, F. Hergert

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.

IEEE Transactions on Information Theory•Sep 1, 1986•38 citations
A new method for computing minimum distances is proposed and justified. Unlike classical techniques that rely on the exhaustive or partial enumeration of codewords with weights lower than or equal to the minimum distance, this new method is based on the ability of the soft-in decoder, when it exists, to overcome error impulse input patterns.
A new method for computing the minimum distances of linear error-correcting codes is proposed and justified. Unlike classical techniques that rely on exhaustive or partial enumeration of codewords, this new method is based on the ability of the Soft-In decoder to overcome Error Impulse input patterns. It is shown that the maximum magnitude of the Error Impulse that can be corrected by the decoder is directly related to the minimum distance. This leads to a very fast algorithm to obtain minimum distances of any linear code whatever the block size and the code rate considered. In particular, the method can be advantageously worked out for turbo-like concatenated codes.
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.
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.
Minimum distance decoding (MDD) for a general error-correcting linear code is a hard computational problem that recently has been shown to beNP-hard. The complexity of known decoding algorithms is determined by\min (2^{k},2^{n-k}), wherenis the code length andkis the number of information digits. Two new algorithms are suggested that reduce substantially the complexity of MDD. The algorithms use a new concept of zero neighbors--a special set of codewords. Only these codewords (which can be computed in advance) should be stored and used in the decoding procedure. The number of zero neighbors is shown to be very small compared with\min (2^{k},2^{n-k})forn \gg 1and a wide range of code ratesR = k/n. For example, forR \approx 0.5this number grows approximately as a square root of the number of codewords.
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.