IEEE International Symposium on Information Theory (ISIT)

Approximate algorithms for computing the minimum distance of low-density parity-check codes

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

Published Dec 23, 2004• 7 citations

Abstract

We propose a family of randomized approximate algorithms, called nearest nonzero codewords search (NNCS), for computing the minimum distance of low-density parity-check (LDPC) codes, including Gallager-type and finite-geometry-type codes.

DOI: 10.1109/isit.2004.1365512

Related papers

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 CommunicationsJan 1, 2004156 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 CommunicationsJul 1, 20128 citations

Computation of the minimum distance of low-density parity-check codes

Min Xiao

Low-density parity-check (LDPC) codes are a good liner block parity codes. In this paper, the fundamental of LDPC codes are introduced briefly first. Then an algorithm called the minimum-weight codeword searching is discussed, which can be used to compute the minimum distance of LDPC codes. The effectiveness and the practicability of the algorithm are demonstrated by some examples. It is significant for us to analyze and optimize the design of LDPC codes.

Information technology newsletterJan 1, 20050 citations

Chained Gallager codes

Victor Zyablov, Florian Hug, Rolf Johannesson

The ensemble of regular Low-Density Parity-Check (LDPC) codes introduced by Gallager is considered. Using probabilistic arguments a lower bound on the normalized minimum distance is derived. A new code construction, called Chained Gallager codes, is introduced as the combination of two Gallager codes and its error correcting capabilities are studied.

Jan 1, 20091 citation

A lower bound on the minimum distance of chained Gallager codes

Victor Zyablov, Florian Hug, Rolf Johannesson

Based on the combination of two regular Gallager (Low-Density Parity-Check (LDPC)) codes, we will introduce a new code construction, called Chained Gallager codes. Following Gallager’s method we will derive a lower bound on the normalized minimum distance for the ensemble of Chained Gallager codes. Applying this lower bound on the normalized minimum distance to different transmissions schemes with two parallel and independent channels, the error correcting capabilities will be studied, stressing the advantages of Chained Gallager codes.

Jan 1, 20090 citations

1 On the Minimum/Stopping Distance of Array Low-Density Parity-Check Codes

Eirik Rosnes, Marcel Ambroze, Martin Tomlinson +1 more

In this work, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers q and m, where q is an odd prime and m <= q. In the literature, the minimum/stopping distance of these codes (denoted by d(q,m) and h(q,m), respectively) has been thoroughly studied for m <= 5. Both exact results, for small values of q and m, and general (i.e., independent of q) bounds have been established. For m=6, the best known minimum distance upper bound, derived by Mittelholzer (IEEE Int. Symp. Inf. Theory, Jun./Jul. 2002), is d(q,6) <= 32. In this work, we derive an improved upper bound of d(q,6) <= 20 and a new upper bound d(q,7) <= 24 by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of q using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for m <= 7 and low-to-moderate values of q <= 79.

Aug 17, 201625 citations