The Experts below are selected from a list of 2553 Experts worldwide ranked by ideXlab platform
David Declercq - One of the best experts on this subject based on the ideXlab platform.
-
Generalized Belief Propagation to break trapping sets in LDPC codes
2014Co-Authors: Jean-christophe Sibel, Sylvain Reynal, David DeclercqAbstract:In this paper, we focus on the Generalized Belief Propagation (GBP) algorithm to solve trapping sets in Low-Density Parity-Check (LDPC) codes. Trapping sets are topological structures in Tanner Graphs of LDPC codes that are not correctly decoded by Belief Propagation (BP), leading to exhibit an error-floor in the bit-error rate. Stemming from statistical physics of spin glasses, GBP consists in passing messages between groups of Tanner Graph nodes. Provided a well-suited grouping, this algorithm proves to be a powerful decoder as it may lower harmful topological effects of the Tanner Graph. We then propose to use GBP to break trapping sets and create a new decoder to outperform BP and to defeat error-floor.
-
A novel region Graph construction based on trapping sets for the Generalized Belief Propagation
2012Co-Authors: Jean-christophe Sibel, Sylvain Reynal, David DeclercqAbstract:The Belief Propagation (BP) is an inference algorithm used to estimate marginal probability distributions for any Markov Random Field (MRF). In the realm of Low-Density Parity-Check (LDPC) codes that can be represented by MRF called Tanner Graphs, the BP is used as a decoding algorithm to estimate the states of bits sent through a noisy channel. Known to be optimal when the Tanner Graph is a tree, the BP suffers from suboptimality when the Tanner Graph has a loop-like topology. Furthermore, combinations of loops, namely the trapping sets, are particularly harmful for the decoding. To circumvent this problem were proposed other algorithms, like the Generalized Belief Propagation (GBP) that comes from statistical physics. This algorithm allows to absorb topological structures inside new nodes called regions. An advantage is that the resulting Graph, the region Graph, is not unique then according to its construction this region Graph is a media for the GBP that can provide more accurate estimates than the BP. In this paper, we propose novel constructions of the region Graph for the famous Tanner code of length N = 155 by making use of the trapping sets as basis for the regions.
-
Fountain Coding via Multiplicatively Repeated Non-Binary LDPC Codes
IEEE Transactions on Communications, 2012Co-Authors: Kenta Kasai, David Declercq, Kohichi SakaniwaAbstract:We study fountain codes transmitted over the binary-input symmetric-output channel. For channels with small capacity, receivers in fountain coding systems needs to collects many channel outputs to recover information bits. Since a collected channel output yields a check node in the decoding Tanner Graph, the channel with small ca- pacity leads to large decoding complexity. In this paper, we introduce a novel fountain coding scheme with non-binary LDPC codes. The decoding complexity of the proposed fountain code does not depend on the channel. Numerical experiments show that the proposed codes exhibit better performance than conventional fountain codes, especially for moderate number of information bits.
-
Experimental results about the dynamics of the Generalized Belief Propagation used on LDPC codes
2012Co-Authors: Jean-christophe Sibel, Sylvain Reynal, David DeclercqAbstract:In the context of channel coding, the Generalized Belief Propagation (GBP) is an iterative algorithm used to recover the transmission bits sent through a noisy channel. To ensure a reliable transmission, we apply a map on the bits, that is called a code. This code induces artificial correlations between the bits to send, and it can be modeled by a Graph whose nodes are the bits and the edges are the correlations. This Graph, called Tanner Graph, is used for most of the decoding algorithms like Belief Propagation or Gallager-B. The GBP is based on a non unic transformation of the Tanner Graph into a so called region-Graph. A clear advantage of the GBP over the other algorithms is the freedom in the construction of this Graph. In this article, we explain a particular construction for specific Graph topologies that involves relevant performance of the GBP. Moreover, we investigate the behavior of the GBP considered as a dynamic system in order to understand the way it evolves in terms of the time and in terms of the noise power of the channel. To this end we make use of classical measures and we introduce a new measure called the hyperspheres method that enables to know the size of the attractors.
-
ICCS - A novel region Graph construction based on trapping sets for the Generalized Belief Propagation
2012 IEEE International Conference on Communication Systems (ICCS), 2012Co-Authors: Jean-christophe Sibel, Sylvain Reynal, David DeclercqAbstract:The Belief Propagation (BP) is an inference algorithm used to estimate marginal probability distributions for any Markov Random Field (MRF). In the realm of Low-Density Parity-Check (LDPC) codes that can be represented by MRF called Tanner Graphs, the BP is used as a decoding algorithm to estimate the states of bits sent through a noisy channel. Known to be optimal when the Tanner Graph is a tree, the BP suffers from suboptimality when the Tanner Graph has a loop-like topology. Furthermore, combinations of loops, namely the trapping sets, are particularly harmful for the decoding. To circumvent this problem were proposed other algorithms, like the Generalized Belief Propagation (GBP) that comes from statistical physics. This algorithm allows to absorb topological structures inside new nodes called regions. An advantage is that the resulting Graph, the region Graph, is not unique then according to its construction this region Graph is a media for the GBP that can provide more accurate estimates than the BP. In this paper, we propose novel constructions of the region Graph for the famous Tanner code of length N = 155 by making use of the trapping sets as basis for the regions.
Eirik Rosnes - One of the best experts on this subject based on the ideXlab platform.
-
iterative soft decoding of binary linear codes using a generalized Tanner Graph
Information Theory Workshop, 2011Co-Authors: Eirik RosnesAbstract:In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner Graph. A generalized Tanner Graph is constructed from the code's Tanner Graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner Graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.
-
ITW - Iterative soft decoding of binary linear codes using a generalized Tanner Graph
2011 IEEE Information Theory Workshop, 2011Co-Authors: Eirik RosnesAbstract:In this work, we consider iterative soft-decision decoding of binary linear codes using a generalized Tanner Graph. A generalized Tanner Graph is constructed from the code's Tanner Graph representation under the objective of mitigating the effect of small cycles. Then, iterative decoding is applied to the generalized Tanner Graph using trellis-based soft-input soft-output decoding in the generalized check nodes. When combined with the stochastic shifting algorithm of Jiang and Narayanan (IEEE Commun. Letters, 2004), the proposed decoding method provides both improved error rate performance and reduced average decoding complexity, without increasing the worst-case decoding complexity.
-
Random Edge-Local Complementation With Applications to Iterative Decoding of HDPC Codes
2010Co-Authors: Joakim Grahl Knudsen, Eirik Rosnes, Lars Eirik Danielsen, Matthew G. Parker, Constanza RieraAbstract:This paper describes the application of edge-local complementation (ELC), defined for a simple bipartite Graph, to a Tanner Graph associated with a binary linear code, C. From a code perspective, various properties of ELC are described and discussed, mainly the special case of isomorphic ELC operations and the relationship to the automorphism group of the code, Aut(C), as well as the generalization of ELC to weight-bounding ELC (WB-ELC) operations under which the number of edges remains upper-bounded. The main motivation is the use of ELC to improve iterative soft-input soft-output decoding of high-density parity-check (HDPC) codes using the sum-product algorithm (SPA). By updating the edges of the Tanner Graph using ELC additional diversity is achieved, while maintaining control on the weight of the Tanner Graph (which also influences the number of short cycles) via WB-ELC. One motivation of ELC-based SPA decoding is the locality argument; that diversity is achieved by local Graph action, and so is well-suited to the local actions that constitute the SPA and allows a parallel implementation. Further applications of WB-ELC are described, including a heuristic to search for a systematic parity-check matrix (i.e., a Tanner Graph) of reduced weight – a problem which has not received much focus in the literature. Extensive simulation data is shown for a range of HDPC codes, both in terms of matrix weight reduction, and error-rate performance of a proposed SPA-WBELC iterative decoding algorithm. A gain is reported over SPA decoding, and over a state-of-the-art algorithm to decode HDPC codes using permutations from Aut(C).
-
ISIT - Iterative decoding on multiple Tanner Graphs using random edge local complementation
2009 IEEE International Symposium on Information Theory, 2009Co-Authors: Joakim Grahl Knudsen, Lars Eirik Danielsen, Matthew G. Parker, Constanza Riera, Eirik RosnesAbstract:In this paper, we propose to enhance the performance of the sum-product algorithm (SPA) by interleaving SPA iterations with a random local Graph update rule. This rule is known as edge local complementation (ELC), and has the effect of modifying the Tanner Graph while preserving the code. We have previously shown how the ELC operation can be used to implement an iterative permutation group decoder (SPA-PD)-one of the most successful iterative soft-decision decoding strategies at small blocklengths. In this work, we exploit the fact that ELC can also give structurally distinct parity-check matrices for the same code. Our aim is to describe a simple iterative decoder, running SPA-PD on distinct structures, based entirely on random usage of the ELC operation. This is called SPA-ELC, and we focus on small blocklength codes with strong algebraic structure. In particular, we look at the extended Golay code and two extended quadratic residue codes. Both error rate performance and average decoding complexity, measured by the average total number of messages required in the decoding, significantly outperform those of the standard SPA, and compares well with SPA-PD. However, in contrast to SPA-PD, which requires a global action on the Tanner Graph, we obtain a performance improvement via local action alone. Such localized algorithms are of mathematical interest in their own right, but are also suited to parallel/distributed realizations.
-
Code design and performance analysis using a 2-level generalized Tanner Graph on the binary erasure channel
2008 International Symposium on Information Theory and Its Applications, 2008Co-Authors: Eirik RosnesAbstract:In this work, we consider code design and performance analysis using a 2-level generalized Tanner Graph on the binary erasure channel. The 2-level generalized Tanner Graph is composed of traditional variables nodes on the left side and generalized check nodes on the right side. The generalized check nodes are (dc, dc - 2), dc ges 3, binary linear codes. Iterative decoding is applied to the 2-level generalized Tanner Graph using maximum a posteriori (MAP) erasure correction in the generalized check nodes. With MAP erasure correction, each check node decoder removes as much erasures as possible, even if it cannot resolve all erasures. Code design is done using density evolution, and we will show that the proposed scheme achieves both a better design rate and lower decoding complexity compared to the traditional scheme with only single parity-check nodes.
Bane Vasic - One of the best experts on this subject based on the ideXlab platform.
-
girth of the Tanner Graph and error correction capability of ldpc codes
Allerton Conference on Communication Control and Computing, 2008Co-Authors: Shashi Kiran Chilappagari, Bane Vasic, Dung Viet Nguyen, Michael W MarcellinAbstract:We investigate the relation between the girth and the guaranteed error correction capability of gamma-left regular LDPC codes. For column-weight-three codes, we give upper and lower bounds on the number of errors correctable by the Gallager A algorithm. For higher column weight codes, we find the number of variable nodes which are guaranteed to expand by a factor of at least 3gamma/4, hence giving a lower bound on the guaranteed correction capability under the bit flipping (serial and parallel) algorithms. We also establish upper bounds by studying the sizes of smallest possible trapping sets.
-
designing ldpc codes without small trapping sets by using Tanner Graph covers
International Symposium on Information Theory, 2007Co-Authors: M Ivkovic, Shashi Kiran Chilappagari, Bane VasicAbstract:We present a method for lowering the error floor of low-density parity check (LDPC) codes. It is based on Tanner Graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel model/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. We illustrate the method by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm.
-
ISIT - Designing LDPC Codes without small trapping sets by using Tanner Graph Covers
2007 IEEE International Symposium on Information Theory, 2007Co-Authors: M Ivkovic, Shashi Kiran Chilappagari, Bane VasicAbstract:We present a method for lowering the error floor of low-density parity check (LDPC) codes. It is based on Tanner Graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel model/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. We illustrate the method by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm.
K.m. Krishnan - One of the best experts on this subject based on the ideXlab platform.
-
Computing the Stopping Distance of a Tanner Graph Is NP-Hard
IEEE Transactions on Information Theory, 2007Co-Authors: K.m. Krishnan, P. ShankarAbstract:Two decision problems related to the computation f stopping sets in Tanner Graphs are shown to be NP-complete. It follows as a consequence that there exists no polynomial time algorithm for computing the stopping distance of a Tanner Graph unless P = NP.
-
FSTTCS - Hardness of approximation results for the problem of finding the stopping distance in Tanner Graphs
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006Co-Authors: K.m. Krishnan, L. Sunil ChandranAbstract:Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner Graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner Graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner Graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P=NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of $2^{(\log n)^{1-\epsilon}}$ for any e> 0 unless NP⊆DTIME(npoly(logn)).
-
Hardness of approximation results for the problem of finding the stopping distance in Tanner Graphs
Lecture Notes in Computer Science, 2006Co-Authors: K.m. Krishnan, L. Sunil ChandranAbstract:Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures introduced by the channel. The stopping distance of a Tanner Graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner Graph T when data is transmitted across a binary erasure channel using the code C. We show that the problem of finding the stopping distance of a Tanner Graph is hard to approximate within any positive constant approximation ratio in polynomial time unless P = NP. It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2 (log n)1-e for any ∈ > 0 unless NP C DTIME(n poly(log n)) ).
-
Hardness of Approximation Results for the Problem of Finding the Stopping Distance in
2006Co-Authors: Tanner Graphs, K.m. Krishnan, Sunil ChandranAbstract:Tanner Graph representation of linear block codes is widely used by iterative decoding algorithms for recovering data transmitted across a noisy communication channel from errors and erasures intro- duced by the channel. The stopping distance of a Tanner Graph T for a binary linear block code C determines the number of erasures correctable using iterative decoding on the Tanner Graph T when data is transmitted across a binary erasure channel using the code C. We show that the prob- lem of finding the stopping distance of a Tanner Graph is hard to approx- imate within any positive constant approximation ratio in polynomial time unless P = NP . It is also shown as a consequence that there can be no approximation algorithm for the problem achieving an approximation ratio of 2 (log n) 1−� for any �> 0 unless NP ⊆ DT IME (n poly(log n) ).
-
On the Complexity of finding stopping set size in Tanner Graphs
2006 40th Annual Conference on Information Sciences and Systems, 2006Co-Authors: K.m. Krishnan, P. ShankarAbstract:The problem of determining whether a Tanner Graph for a linear block code has a stopping set of a given size is shown to be NP-complete.
Evangelos S. Eleftheriou - One of the best experts on this subject based on the ideXlab platform.
-
binary representation of cycle Tanner Graph gf 2 sup b codes
International Conference on Communications, 2004Co-Authors: Yu X Hu, Evangelos S. EleftheriouAbstract:We derive the average symbol and Hamming weight spectrum functions of the random ensemble of regular low-density parity-check (LDPC) codes over GF(2/sup b/) when used with the binary-input noisy channel. This work confirms theoretically that the near-Shannon-limit performance of Gallager's binary LDPC codes can be significantly enhanced by moving to fields of higher order. We construct a family of error-correcting codes based on the binary representation of GF(2/sup b/) codes defined on a cycle Tanner Graph that appears to be "good" for both optimum and iterative decoding over the binary-input noisy channel. In particular, we report a short-block-length (1008 bits), rate-1/2 progressive-edge-growth-based cycle Tanner-Graph code over GF(2/sup b/) with a block-error rate <10/sup -4/ at E/sub b//N/sub 0/=1.89 dB, which appears to exhibit the best iterative-decoding performance at this short block length known to date.
-
ICC - Binary representation of cycle Tanner-Graph GF(2/sup b/) codes
2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577), 2004Co-Authors: Evangelos S. EleftheriouAbstract:We derive the average symbol and Hamming weight spectrum functions of the random ensemble of regular low-density parity-check (LDPC) codes over GF(2/sup b/) when used with the binary-input noisy channel. This work confirms theoretically that the near-Shannon-limit performance of Gallager's binary LDPC codes can be significantly enhanced by moving to fields of higher order. We construct a family of error-correcting codes based on the binary representation of GF(2/sup b/) codes defined on a cycle Tanner Graph that appears to be "good" for both optimum and iterative decoding over the binary-input noisy channel. In particular, we report a short-block-length (1008 bits), rate-1/2 progressive-edge-growth-based cycle Tanner-Graph code over GF(2/sup b/) with a block-error rate
-
Cycle Tanner-Graph codes over GF(2/sup b/)
IEEE International Symposium on Information Theory 2003. Proceedings., 2003Co-Authors: Evangelos S. EleftheriouAbstract:The average Hamming weight spectrum function of the random ensemble of regular low-density parity-check (LDPC) codes over GF(2/sup b/) when used with binary-input channels is derived. This work confirms theoretically that the near-Shannon-limit performance of Gallager's binary LDPC codes can be significantly enhanced by moving to fields of higher order. We construct a family of error-correcting codes based on the binary representation of GF(2/sup b/) codes defined on a cycle Tanner Graph, that appears to be good for both optimum decoding and iterative decoding over binary-input channels.
