Several properties of short LDPC codes

In this paper, we present several properties on minimum distance(d/sub min/) and girth(G/sub min/) in Tanner graphs for low-density parity-check (LDPC) codes with small left degrees. We show that the distance growth of (2, 4) LDPC codes is too slow to achieve the desired performance. We further give a tight upper bound on the maximum possible girth. The numerical results show that codes with large G/sub min/ could outperform the average performance of regular ensembles of the LDPC codes over binary symmetric channels. The same codes perform about 1.5 dB away from the sphere-packing bound on additive white Gaussian noise channels.     

Resolvable 2-designs for regular low-density parity-check codes

This paper extends the class of low-density parity-check (LDPC) codes that can be algebraically constructed. We present regular LDPC codes based on resolvable Steiner 2-designs which have Tanner graphs free of four-cycles. The resulting codes are (3, /spl rho/)-regular or (4, /spl rho/)-regular for any value of /spl rho/ and for a flexible choice of code lengths.     

A lattice-based systematic recursive construction of quasi-cyclic LDPC codes

This paper presents a low-complexity recursive and systematic method to construct good well-structured low-density parity-check (LDPC) codes. The method is based on a recursive application of a partial Kronecker product operation on a given gamma x q, q ges 3 a prime, integer lattice L(gamma x q). The (n - 1)- fold product of L(gamma x q) by itself, denoted Lⁿ(gamma x q), represents a regular quasi-cyclic (QC) LDPC code, denoted (see PDF), of high rate and girth 6. The minimum distance of (see PDF) is equal to that of the core code (see PDF) introduced by L(gamma x q). The support of the minimum weight codewords in (see PDF) are characterized by the support of the same type of codewords in (see PDF). From performance perspective the constructed codes compete with the pseudorandom LDPC codes.     

Design of efficiently encodable moderate-length high-rate irregular LDPC codes

This paper presents a new class of irregular low-density parity-check (LDPC) codes of moderate length (10/sup 3//spl les/n/spl les/10/sup 4/) and high rate (R/spl ges/3/4). Codes in this class admit low-complexity encoding and have lower error-rate floors than other irregular LDPC code-design approaches. It is also shown that this class of LDPC codes is equivalent to a class of systematic serial turbo codes and is an extension of irregular repeat-accumulate codes. A code design algorithm based on the combination of density evolution and differential evolution optimization with a modified cost function is presented. Moderate-length, high-rate codes with no error-rate floors down to a bit-error rate of 10/sup -9/ are presented. Although our focus is on moderate-length, high-rate codes, the proposed coding scheme is applicable to irregular LDPC codes with other lengths and rates.     

More results on the weight enumerator of product codes

We consider the product code C/sub p/ of q-ary linear codes with minimum distances d/sub c/ and d/sub r/. The words in C/sub p/ of weight less than d/sub r/d/sub c/+max(d/sub r//spl lceil/(d/sub c//g)/spl rceil/,d/sub c//spl lceil/(d/sub r//q)/spl rceil/) are characterized, and their number is expressed in the number of low-weight words of the constituent codes. For binary product codes, we give an upper bound on the number of words in C/sub p/ of weightless than min(d/sub r/(d/sub c/+/spl lceil/(d/sub c//2)/spl rceil/+1)), d/sub c/(d/sub r/+/spl lceil/(d/sub r//2)/spl rceil/+1) that is met with equality if C/sub c/ and C/sub r/ are (extended) perfect codes.     

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.     

Quantum cyclic and constacyclic codes

Based on classical quaternary constacyclic linear codes, we construct a set of quantum codes with parameters [[(4/sup m/ -1)/3, (4/sup m/ -1)/3 -2(3l + b)m, 4l + b + 2]] where m/spl ges/4, 1/spl les/b/spl les/3, and 12l + 3b < 2 /spl times/ 4/sup /spl lfloor/(m+2)/3/spl rfloor//-1, which are better than the codes in Bierbrauer and Edel (2000).     

Construction of low-density parity-check codes by superposition

This paper presents a superposition method for constructing low-density parity-check (LDPC) codes. Several classes of structured LDPC codes are constructed. Codes in these classes perform well with iterative decoding, and their Tanner graphs have girth at least six.     

Weight distributions of cyclic self-dual codes

We give a 1-level squaring construction for binary repeated-root cyclic codes of length n=2/sup a/b, a/spl ges/1, b odd. This allows us to obtain the weight distributions of all cyclic binary self-dual codes of lengths up to 110, which are not accessible by direct computation. We also use the shadow construction, as a particular method for Type I self-dual codes.     

Improving the Gilbert-Varshamov bound for q-ary codes

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.     

On the stopping distance of finite geometry LDPC codes

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.     

New class of nonlinear systematic error detecting codes

A code C detects error e with probability 1-Q(e),ifQ(e) is a fraction of codewords y such that y, y+e/spl isin/C. We present a class of optimal nonlinear q-ary systematic (n, q/sup k/)-codes (robust codes) minimizing over all (n, q/sup k/)-codes the maximum of Q(e) for nonzero e. We also show that any linear (n, q/sup k/)-code V with n /spl les/2k can be modified into a nonlinear (n, q/sup k/)-code C/sub v/ with simple encoding and decoding procedures, such that the set E={e|Q(e)=1} of undetected errors for C/sub v/ is a (k-r)-dimensional subspace of V (|E|=q/sup k-r/ instead of q/sup k/ for V). For the remaining q/sup n/-q/sup k-r/ nonzero errors, Q(e)/spl les/q/sup -r/for q/spl ges/3 and Q(e)/spl les/ 2/sup -r+1/ for q=2.     

Regular Low-Density Parity-Check codes based on shifted identity matrices

This paper extends the class of Low-Density Parity-Check （LDPC） codes that can be constructed from shifted identity matrices. To construct regular LDPC codes, a new method is proposed. Two simple inequations are adopted to avoid the short cycles in Tanner graph, which makes the girth of Tanner graphs at least 8. Because their parity-check matrices are made up of circulant matrices, the new codes are quasi-cyclic codes. They perform well with iterative decoding.     

Duality and support weight distributions

We show how to compute the support weight distribution A/sub i//sup r/ for r/spl ges/k-d/sub 2//sup /spl perp//+3, where d/sub 2//sup /spl perp// is the second minimum support weight of a code, provided the weight enumerator of the dual code is known.     

TS-LDPC Codes: Turbo-Structured Codes With Large Girth

We consider turbo-structured low-density parity-check (TS-LDPC) codes-structured regular codes whose Tanner graph is composed of two trees connected by an interleaver. TS-LDPC codes with good girth properties are easy to construct: careful design of the interleaver component prevents short cycles of any desired length in its Tanner graph. We present algorithms to construct TS-LDPC codes with arbitrary column weight jges2 and row weight k and arbitrary girth g. We develop a linear complexity encoding algorithm for a type of TS-LDPC codes-encoding friendly TS-LDPC (EFTS-LDPC) codes. Simulation results demonstrate that the bit-error rate (BER) performance at low signal-to-noise ratio (SNR) is competitive with the error performance of random LDPC codes of the same size, with better error floor properties at high SNR     

Dependence of the neodymium random laser threshold on the diameter of the pumped spot

We experimentally studied the dependence of the threshold energy density E/sub th//S in Nd/sub 0.5/La/sub 0.5/Al/sub 3/(BO/sub 3/)/sub 4/ random laser on the diameter of the pumped spot d and found that at d/spl ges/130/spl mu/m, E/sub th//S is proportional to 1/d+const. This functional dependence is different from the one commonly expected in the case of diffusion, /spl prop/1/d/sup 2/+const. However, the obtained experimental dependence does not mean the failure of the diffusion model. Calculating the mean photon's residence time /spl tau//sub res//sup p/ (which photons, making their diffusion-like random walks, spend inside the gain volume) as the function of d and further assuming that E/sub th//S/spl prop/(/spl tau//sup p//sub res/)/sup -1/, we predicted the experimentally obtained functional dependence, /spl prop/1/d+const. The major difference between our model and that of and was in the boundary conditions.     

Low-density parity-check codes based on finite geometries: arediscovery and new results

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding     

Near-optimal depth-constrained codes

This note considers an n-letter alphabet in which the ith letter is accessed with probability p/sub i/. The problem is to design efficient algorithms for constructing near-optimal, depth-constrained Huffman and alphabetic codes. We recast the problem as one of determining a probability vector q/sup */=(q/sup *//sub 1/,...,q/sup *//sub n/) in an appropriate convex set, S, so as to minimize the relative entropy D(p/spl par/q) over all q/spl isin/S. Methods from convex optimization give an explicit solution for q/sup */ in terms of p. We show that the Huffman and alphabetic codes so constructed are within 1 and 2 bits of the corresponding optimal depth-constrained codes.     

A nontrivial lower bound on the Shannon capacities of the complements of odd cycles

This article contains a construction for independent sets in the powers of the complements of odd cycles. In particular, we show that /spl alpha/(C~/sub 2n+3/(2/sup n/))/spl ges/2(2/sup n/)+1. It follows that for n/spl ges/0 we have /spl Theta/(C~/sub 2n+3/)>2, where /spl Theta/(G) denotes the Shannon (1956) capacity of graph G.