On theHardness ofApproximating Stopping and Trapping Setsin LDPC Codes

Olgica Milenković

Published Jan 1, 2007• 0 citations

Abstract

We provethatapproximating thesizeofthe smallest trapping setinTannergraphsoflinear block codes, andmorerestrictively, LDPC codes, isNP-hard. Theprooftechniques relyonreductions fromthreeNP- hardproblems, thesetcover, minimumthree-dimensional matching, andtheminimumHammingdistance problem. Theramifications ofourfindings arethatmethodsused forestimating theheight oftheerror-floor oflongLDPC codes, centered aroundtrapping setenumeration, cannot provide accurate worst-case performance predictions. I.INTRODUCTION Inthepastdecade, thesearch forefficient andnear- optimal decoding algorithms forlinear block codes cul- minated withtherediscovery andgeneralization ofthe notion ofsparse codesanditerative message passing algorithms. Iterative decoders canapproach theShannon limit ofreliable communication withpolynomial time complexity, provided thattheyoperate onlong, low- density parity-check (LDPC)codes. Thisisachieved by using graphical representations ofcodes, termed Tanner graphs, that contain asmall numberofedges. Onsuch graphs, probabilistic inference oftheformofiterative message passing isknowntohavelinear complexity. Theperformance oflinear blockcodesunderiter- ative decoding, andtheperformance ofLDPC codes inparticular, depends onthestructural properties of their underlying Tannergraphs. Foreachchannel- decoder pair, there exist vertex configurations inthe codegraph onwhichagiven iterative decoder fails. Forsomefrequently encountered Discrete Memoryless Channels (DMCs), suchconfigurations areknownas near-codewords (9), trapping andstopping sets(3), (12), pseudocodewords (7), orinstantons (13). Itisknownthat maximum-likelihood (ML)decoders fail whentransmission errors areconfined toTanner graph configurations corresponding tocodewords, while iterative decoders usually fail tomakecorrect decisions on(strictly) larger setsofconfigurations. Forexample, iterative edge-removal (ER)decoders forcoding overthe

Related papers

Short-length Low-density Parity-check Codes: Construction and Decoding Algorithms

Cornelius T. Healy

Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.

Jul 1, 20144 citations

Controlling the Error Floors of the Low-Density Parity-Check Codes

Shuai Zhang

The goal of error control coding is to encode information in such a way, that in the event that errors occur during transmission over a noisy communication channel or during storage in an unreliable memory, the receiver can correct the errors and recover the original transmitted information. Low-density parity-check (LDPC) codes are a kind of high performance linear block code, which are already used in many recent communication systems. Information rates guaranteed by these codes approach the theoretical Shannon capacity limit. In addition, LDPC codes are now widely used in practice and included in many communication standards. Therefore study of these codes is very important and practical approaches to their design and decoding techniques are of great interest. There exist very good decoding algorithms for LDPC codes with respect to different channel models. However, LDPC codes suffer from the infamous error floor problem at high signal-to-noise ratios. This problem is attributed to the trapping sets by Richardson. It is shown that the dominant trapping sets of regular LDPC codes, so called absorption sets, undergo a two-phase dynamic behavior in the iterative message-passing decoding algorithm. We present a linear dynamic model for the iteration behavior of these sets. It can be seen that they undergo an initial geometric growth phase which stabilizes in a final bit-flipping behavior where the algorithm reaches a fixed point. Our analysis is shown to lead to very accurate numerical calculations of the error floor bit error rates down to error rates that are inaccessible by simulation. The topologies of the dominant absorption sets of two example codes, the IEEE 802.3an [2048,1723] regular (6,32) LDPC code and the Tanner [155,64,20] regular (3,5) LDPC code, are identified and tabulated by using topological features in combination with search algorithms, respectively. To make our analysis more complete, we provide more solid evidence showing that trapping sets are equivalent to absorption sets. In other words, we argue that absorption sets characterize all failure mechanisms. Some insights from our linear analysis can be borrowed to approach this problem. Another insight that this formula provides to us is the means to reduce the error floor, which is another important part of what we hoped to achieve by developing the formula in the first place. By allowing the log-likelihood ratios (LLRs) utilized by the message-passing decoding to grow bigger in precision length, the absorption sets as a trouble-causing structure will be successfully corrected. Therefore, the absorption sets, generically born with the code design, will no longer threaten the error correcting performance as long as the messages have enough room and time to grow. This translates to greater LLR clipping thresholds and more iterations, both of which are preset at the decoder. However, the actual settings are dependent on how much the subgraph of the dominant absorption set resembles that of a non-zero minimum-weight codeword, therefore the settings are empirical. In general more likeness in their topologies, the more effort it costs to correct the absorption set.

Jan 1, 20130 citations

Analysis of failures of decoders for LDPC codes

Shashi Kiran Chilappagari

Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.

Jan 1, 20080 citations

On the Hardness of Approximating Stopping and Trapping Sets

Andrew McGregor, Olgica Milenković

We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes, based on stopping and trapping set enumeration, cannot provide accurate worst-case performance predictions for most codes.

IEEE Transactions on Information TheoryMar 24, 201061 citations

Analysis of LDPC convolutional codes derived from LDPC block codes

Alí Emre Pusane

LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message passing decoding. In this dissertation, we present several methods of deriving families of time-varying and time-invariant LDPC convolutional codes from LDPC block codes. We demonstrate that the derived LDPC convolutional codes significantly outperform the underlying LDPC block codes, and we investigate the reasons for these 'convolutional gains'. It is well known that cycles in the Tanner graph representation of a sparse code affect the iterative decoding algorithm, with short cycles generally pushing its performance further away from optimum. Hence it is common practice to design codes that do not contain short cycles, so as to obtain independent messages in at least the initial iterations of the decoding process. We show that the derived LDPC convolutional codes have better graph-cycle properties than their block code counterparts. In particular, we show that the unwrapping process that is used to derive LDPC convolutional codes from LDPC block codes can 'break' some cycles of the underlying LDPC block code, but cannot create any shorter cycles. We prove that any cycle in an LDPC convolutional code always maps to a cycle of the same or smaller length in the underlying LDPC block code. Minimum distance is an important code design parameter when the channel quality is high, since codewords that are minimum distance apart are the most likely to cause errors with ML or near-ML decoding. In this case, the minimum distance determines the so-called error floor behavior in the performance curve corresponding to high channel signal-to-noise ratios. Thus studying the minimum distance properties of a code family gives insight into its error floor behavior. We use asymptotic methods to calculate a lower bound on the free distance of several ensembles of asymptotically good LDPC convolutional codes derived from protograph-based LDPC block codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of the corresponding LDPC block codes. Message-passing iterative decoders for LDPC block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood decoding union bound. We address the pseudo-codeword problem from the convolutional code perspective. In particular, we show that the minimum pseudo-weight of an LDPC convolutional code is at least as large as the minimum pseudo-weight of an underlying LDPC block code. This result, which parallels a well-known relationship between the minimum Hamming weight of convolutional codes and the minimum Hamming weight of their quasi-cyclic counterparts, is due to the fact that every pseudo-codeword in the LDPC convolutional code induces a pseudo-codeword in the LDPC block code with pseudo-weight no larger than that of the convolutional pseudo-codeword. More generally, we demonstrate a difference in the weight spectra of LDPC block and convolutional codes that leads to improved performance at low-to-moderate signal-to-noise ratios for the convolutional codes, a conclusion supported by simulation results.

Sep 15, 20221 citation

Trapping set analysis of protograph-based LDPC convolutional codes

David G. M. Mitchell, Alí Emre Pusane, Daniel J. Costello

It has been suggested that ¿near-codewords¿ may be a significant factor affecting decoding failures of LDPC codes over the AWGN channel. A near-codeword is a sequence that satisfies almost all of the check equations. These near-codewords can be associated with so-called `trapping sets' that exist in the Tanner graph of a code. In this paper, we analyse the trapping sets of protograph-based LDPC convolutional codes. LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message-passing decoding. Further, it has been shown that some ensembles of LDPC convolutional codes are asymptotically good, in the sense that the average free distance grows linearly with constraint length. Here, asymptotic methods are used to calculate a lower bound on the trapping set growth rates for two ensembles of asymptotically good protograph-based LDPC convolutional codes. This can be used to predict where the error floor will occur for these codes under iterative message-passing decoding.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 200915 citations