Linear Time Encoding of LDPC Codes

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ?label-and-decide.? We prove that the ?label-and-decide? method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ?label-decide-recompute.? Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than 4 ·M ·((k?- 1), where M is the number of independent rows in the parity-check matrix and k? represents the mean row weight of the parity-check matrix.     

On the stopping distance and the stopping redundancy of codes

It is now well known that the performance of a linear code /spl Copf/ under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for /spl Copf/. Several recent papers refer to this parameter as the stopping distance s of /spl Copf/. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for /spl Copf/ depends on the corresponding choice of a parity-check matrix. It is easy to see that s /spl les/ d, where d is the minimum Hamming distance of /spl Copf/, and we show that it is always possible to choose a parity-check matrix for /spl Copf/ (with sufficiently many dependent rows) such that s=d. We thus introduce a new parameter, the stopping redundancy of /spl Copf/, defined as the minimum number of rows in a parity- check matrix H for /spl Copf/ such that the corresponding stopping distance s(H) attains its largest possible value, namely, s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 34 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes.     

Eliminating small stopping sets in irregular low-density parity-check codes

We present a novel scheme to eliminate small stopping sets in irregular low-density parity-check (LDPC) codes. By adding several new check nodes and having their edges connected to small stopping sets in the original code, the improved code decreases the number of small stopping sets efficiently. Simulation results show that the proposed scheme decreases the frame error rate (FER) significantly in the error floor region, whereas having almost the same rate as the original code.     

Stopping set distribution of LDPC code ensembles

Stopping sets determine the performance of low-density parity-check (LDPC) codes under iterative decoding over erasure channels. We derive several results on the asymptotic behavior of stopping sets in Tanner-graph ensembles, including the following. An expression for the normalized average stopping set distribution, yielding, in particular, a critical fraction of the block length above which codes have exponentially many stopping sets of that size. A relation between the degree distribution and the likely size of the smallest nonempty stopping set, showing that for a /spl radic/1-/spl lambda/'(0)/spl rho/'(1) fraction of codes with /spl lambda/'(0)/spl rho/'(1)<1, and in particular for almost all codes with smallest variable degree >2, the smallest nonempty stopping set is linear in the block length. Bounds on the average block error probability as a function of the erasure probability /spl epsi/, showing in particular that for codes with lowest variable degree 2, if /spl epsi/ is below a certain threshold, the asymptotic average block error probability is 1-/spl radic/1-/spl lambda/'(0)/spl rho/'(1)/spl epsi/.     

Construction of Near-Optimum Burst Erasure Correcting Low-Density Parity-Check Codes

In this paper, a simple and effective tool for the design of low-density parity-check (LDPC) codes for iterative correction of bursts of erasures is presented. The design method consists of starting from the parity-check matrix of an LDPC code and developing an optimized parity-check matrix, with the same performance over the memoryless erasure channel, and suitable also for the iterative correction of single erasure bursts. The parity-check matrix optimization is performed by an algorithm called pivot searching and swapping (PSS) algorithm. It executes permutations of carefully chosen columns of the parity-check matrix, after a local analysis of particular variable nodes called stopping set pivots. This algorithm can be in principle applied to any LDPC code. If the input parity-check matrix is designed to achieve a good performance over the memoryless erasure channel, then the code obtained after the application of the algorithm provides a good joint correction of independent erasures and single erasure bursts. Numerical results are provided in order to show the algorithm effectiveness when applied to different categories of LDPC codes.     

Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-size turbo stopping set which is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garello et al. in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.     

Permutation Decoding and the Stopping Redundancy Hierarchy of Cyclic and Extended Cyclic Codes

We introduce the notion of the stopping redundancy hierarchy of a linear block code as a measure of the tradeoff between performance and complexity of iterative decoding for the binary erasure channel. We derive lower and upper bounds for the stopping redundancy hierarchy via LovÁsz's Local Lemma (LLL) and Bonferroni-type inequalities, and specialize them for codes with cyclic parity-check matrices. Based on the observed properties of parity-check matrices with good stopping redundancy characteristics, we develop a novel decoding technique, termed automorphism group decoding, that combines iterative message passing and permutation decoding. We also present bounds on the smallest number of permutations of an automorphism group decoder needed to correct any set of erasures up to a prescribed size. Simulation results demonstrate that for a large number of algebraic codes, the performance of the new decoding method is close to that of maximum-likelihood (ML) decoding.      

LDPC Codes Based on Latin Squares: Cycle Structure, Stopping Set, and Trapping Set Analysis

It is well known that certain combinatorial structures in the Tanner graph of a low-density parity-check (LDPC) code exhibit a strong influence on its performance under iterative decoding. These structures include cycles, stopping/trapping sets, and parameters such as the diameter of the code. In general, it is very hard to find a complete characterization of such configurations in an arbitrary code, and even harder to understand the intricate relationships that exist between these entities. It is, therefore, of interest to identify a simple setting in which all the described combinatorial structures can be enumerated and studied within a joint framework. One such setting is developed in this paper, for the purpose of analyzing the distribution of short cycles and the structure of stopping and trapping sets in Tanner graphs of LDPC codes based on idempotent and symmetric Latin squares. The parity-check matrices of LDPC codes based on Latin squares have a special form that allows for connecting combinatorial parameters of the codes with the number of certain subrectangles in the Latin squares. Subrectangles of interest can be easily identified, and in certain instances, completely enumerated. This study can be extended in several different directions, one of which is concerned with modifying the code design process in order to eliminate or reduce the number of configurations bearing a negative influence on the performance of the code. Another application of the results includes determining to which extent a configuration governs the behavior of the bit-error rate curve in the waterfall and error-floor regions     

On the Stopping Redundancy of Reed&#8211;Muller Codes

The stopping redundancy of the code is an important parameter which arises from analyzing the performance of a linear code under iterative decoding on a binary erasure channel. In this paper, we will consider the stopping redundancy of Reed-Muller codes and related codes. Let R(lscr,m) be the Reed-Muller code of length 2^m and order lscr. Schwartz and Vardy gave a recursive construction of parity-check matrices for the Reed-Muller codes, and asked whether the number of rows in those parity-check matrices is the stopping redundancy of the codes. We prove that the stopping redundancy of R(m-2,m), which is also the extended Hamming code of length 2^m, is 2m-1 and thus show that the recursive bound is tight in this case. We prove that the stopping redundancy of the simplex code equals its redundancy. Several constructions of codes for which the stopping redundancy equals the redundancy are discussed. We prove an upper bound on the stopping redundancy of R(1,m). This bound is better than the known recursive bound and thus gives a negative answer to the question of Schwartz and Vardy     

Quasi-cyclic LDPC codes for fast encoding

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.     

Finding All Small Error-Prone Substructures in LDPC Codes

It is proven in this work that it is NP-complete to exhaustively enumerate small error-prone substructures in arbitrary, finite-length low-density parity-check (LDPC) codes. Two error-prone patterns of interest include stopping sets for binary erasure channels (BECs) and trapping sets for general memoryless symmetric channels. Despite the provable hardness of the problem, this work provides an exhaustive enumeration algorithm that is computationally affordable when applied to codes of practical short lengths n ap 500. By exploiting the sparse connectivity of LDPC codes, the stopping sets of size les 13 and the trapping sets of size les11 can be exhaustively enumerated. The central theorem behind the proposed algorithm is a new provably tight upper bound on the error rates of iterative decoding over BECs. Based on a tree-pruning technique, this upper bound can be iteratively sharpened until its asymptotic order equals that of the error floor. This feature distinguishes the proposed algorithm from existing non-exhaustive ones that correspond to finding lower bounds of the error floor. The upper bound also provides a worst case performance guarantee that is crucial to optimizing LDPC codes when the target error rate is beyond the reach of Monte Carlo simulation. Numerical experiments on both randomly and algebraically constructed LDPC codes demonstrate the efficiency of the search algorithm and its significant value for finite-length code optimization.     

Flexible construction of irregular partitioned permutation LDPC codes with low, error floors

Irregular partitioned permutation (IPP) low-density parity-check (LDPC) codes have been recently introduced to facilitate hardware implementation of belief propagation (BP) decoders. In this letter, we present a new method to construct IPP LDPC codes with great flexibility in the selection of code parameters. Meanwhile, small stopping sets are avoided in the code construction, thus good error floor performance can be achieved.     

On the Asymptotic Weight and Stopping Set Distribution of Regular LDPC Ensembles

In this correspondence, we estimate the variance of weight and stopping set distribution of regular low-density parity-check (LDPC) ensembles. Using this estimate and the second moment method we obtain bounds on the probability that a randomly chosen code from regular LDPC ensemble has its weight distribution and stopping set distribution close to respective ensemble averages. We are able to show that a large fraction of total number of codes have their weight and stopping set distribution close to the average     

High-rate girth-eight low-density parity-check codes on rectangular integer lattices

This letter introduces a combinatorial construction of girth-eight high-rate low-density parity-check codes based on integer lattices. The parity-check matrix of a code is defined as a point-line incidence matrix of a 1-configuration based on a rectangular integer lattice, and the girth-eight property is achieved by a judicious selection of sets of parallel lines included in a configuration. A class of codes with a wide range of lengths and column weights is obtained. The resulting matrix of parity checks is an array of circulant matrices.     

Burst Erasure Correcting LDPC Codes

In this paper low-density parity-check (LDPC) codes are designed for burst erasure channels. Firstly, lower bounds for the maximum length erasure burst that can always be corrected with message-passing decoding are derived as a function of the parity-check matrix properties. We then show how paritycheck matrices for burst erasure correcting LDPC codes can be constructed using superposition, where the burst erasure correcting performance of the resulting codes is derived as a property of the stopping set size of the base matrices and the choice of permutation matrices for the superposition. This result is then used to design both single burst erasure correcting LDPC codes which are also resilient to the presence of random erasures in the received bits and LDPC codes which can correct multiple erasure bursts in the same codeword.     

围长至少为8的QC-LDPC码的新构造:一种显式框架

 构造围长较大的校验矩阵,是提高二进制和多进制QC-LDPC码译码性能的一种有效手段.本文提出一种不需要借助于任何计算机搜索步骤,能够直接构造出围长至少为8的QC-LDPC码的显式构造框架.该框架所构造的QC-LDPC码不仅满足围长至少为8的条件,而且还具有循环置换矩阵(CPM)尺寸可以连续变化的优点.该框架可以分为两个步骤:第一步是在无穷大CPM尺寸条件下利用确定性方法构造一个围长至少为8的校验矩阵;第二步是根据本文新发现的一个围长性质,从该校验矩阵的移位矩阵直接精确地计算出CPM尺寸连续变化的紧致下界.     

Asymptotic Spectra of Trapping Sets in Regular and Irregular LDPC Code Ensembles

We evaluate the asymptotic normalized average distributions of a class of combinatorial configurations in random, regular and irregular, binary low-density parity-check (LDPC) code ensembles. Among the configurations considered are trapping and stopping sets. These sets represent subsets of variable nodes in the Tanner graph of a code that play an important role in determining the height and point of onset of the error-floor in its performance curve. The techniques used for deriving the spectra include large deviations theory and statistical methods for enumerating binary matrices with prescribed row and column sums. These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, that are known to characterize other important properties of soft-decision decoders of linear block codes     

Shortened Array Codes of Large Girth

One approach to designing structured low-density parity-check (LDPC) codes with large girth is to shorten codes with small girth in such a manner that the deleted columns of the parity-check matrix contain all the variables involved in short cycles. This approach is especially effective if the parity-check matrix of a code is a matrix composed of blocks of circulant permutation matrices, as is the case for the class of codes known as array codes. We show how to shorten array codes by deleting certain columns of their parity-check matrices so as to increase their girth. The shortening approach is based on the observation that for array codes, and in fact for a slightly more general class of LDPC codes, the cycles in the corresponding Tanner graph are governed by certain homogeneous linear equations with integer coefficients. Consequently, we can selectively eliminate cycles from an array code by only retaining those columns from the parity-check matrix of the original code that are indexed by integer sequences that do not contain solutions to the equations governing those cycles. We provide Ramsey-theoretic estimates for the maximum number of columns that can be retained from the original parity-check matrix with the property that the sequence of their indices avoid solutions to various types of cycle-governing equations. This translates to estimates of the rate penalty incurred in shortening a code to eliminate cycles. Simulation results show that for the codes considered, shortening them to increase the girth can lead to significant gains in signal-to-noise ratio (SNR) in the case of communication over an additive white Gaussian noise (AWGN) channel     

Memory Access Optimized Implementation of Cyclic and Quasi-Cyclic LDPC Codes on a GPGPU

Software based decoding of low-density parity-check (LDPC) codes frequently takes very long time, thus the general purpose graphics processing units (GPGPUs) that support massively parallel processing can be very useful for speeding up the simulation. In LDPC decoding, the parity-check matrix H needs to be accessed at every node updating process, and the size of the matrix is often larger than that of GPU on-chip memory especially when the code length is long or the weight is high. In this work, the parity-check matrix of cyclic or quasi-cyclic (QC) LDPC codes is greatly compressed by exploiting the periodic property of the matrix. Also, vacant elements are eliminated from the sparse message arrays to utilize the coalesced access of global memory supported by GPGPUs. Regular projective geometry (PG) and irregular QC LDPC codes are used for sum-product algorithm based decoding with the GTX-285 NVIDIA graphics processing unit (GPU), and considerable speed-up results are obtained.     

Quasi-Cyclic Low-Density Parity-Check Codes for Space-Time Bit-Interleaved Coded Modulation

In this letter, it is shown that the diversity order of space-time bit-interleaved coded modulation (ST-BICM) system is determined by the number of submatrices having linearly independent column vectors in a parity-check matrix of quasicyclic low-density parity-check (QC-LDPC) code. It is also proved that this diversity order can be derived from the base matrix of QC-LDPC code, which can make it easy to design QC-LDPC codes suitable for ST-BICM systems. Finally, the simulation results are provided to confirm the analytical results.