Near-capacity coding in multicarrier modulation systems

We apply irregular low-density parity-check (LDPC) codes to the design of multilevel coded quadrature amplitude modulation (QAM) schemes for application in discrete multitone systems in frequency-selective channels. A combined Gray/Ungerboeck scheme is used to label each QAM constellation. The Gray-labeled bits are protected using an irregular LDPC code with iterative soft-decision decoding, while other bits are protected using a high-rate Reed-Solomon code with hard-decision decoding (or are left uncoded). The rate of the LDPC code is selected by analyzing the capacity of the channel seen by the Gray-labeled bits and is made adaptive by selective concatenation with an inner repetition code. Using a practical bit-loading algorithm, we apply this coding scheme to an ensemble of frequency-selective channels with Gaussian noise. Over a large number of channel realizations, this coding scheme provides an average effective coding gain of more than 7.5 dB at a bit-error rate of 10/sup -7/ and a block length of approximately 10/sup 5/ b. This represents a gap of approximately 2.3 dB from the Shannon limit of the additive white Gaussian noise channel, which could be closed to within 0.8-1.2 dB using constellation shaping.     

Power- and bandwidth-efficient communications using LDPC codes

We apply low-density parity-check (LDPC) codes to a bandwidth-efficient modulation scheme using multilevel coding, multistage decoding, and trellis-based signal shaping. Performance results based on density evolution and simulations are presented. Using irregular LDPC component codes of block length 10/sup 5/ and a 64-quadrature amplitude modulation signal constellation operating at 2 bits/dimension, a bit-error rate of 10/sup -5/ is achieved at an E/sub b//N/sub 0/ of 6.55 dB. At this value of E/sub b//N/sub 0/, the Shannon channel capacity, computed assuming equally likely signaling, is below 2 bits/dimension.     

High-rate punctured convolutional self-doubly orthogonal codes for iterative threshold decoding

The puncturing technique allows obtaining high-rate convolutional codes from low-rate convolutional codes used as mother codes. This technique has been successfully applied to generate good high-rate convolutional codes which are suitable for Viterbi and sequential decoding. In this paper, we investigate the puncturing technique for convolutional self-doubly orthogonal codes (CSO/sup 2/C) which are decoded using an iterative threshold-decoding algorithm. Based on an analysis of iterative threshold decoding of the rate-R=b/(b+1) punctured systematic CSO/sup 2/C, the required properties of the rate-R=1/2 systematic convolutional codes (SCCs) used as mother codes are derived. From this analysis, it is shown that there is no need for the punctured mother codes to respect all the required conditions, in order to maintain the double orthogonality at the second iteration step of the iterative threshold-decoding algorithm. The results of the search for the appropriate rate-R=1/2 SCCs used as mother codes to yield a large number of punctured codes of rates 2/3/spl les/R/spl les/6/7 are presented, and some of their error performances evaluated.     

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).     

Low-density parity-check codes for space-time wireless transmission

Irregular low-density parity-check (LDPC) codes have shown exceptionally good performance for single antenna systems over a wide class of channels. In this paper, we investigate their application to multiple antenna systems in flat Rayleigh fading channels. For small transmit arrays, we focus mainly on space-time coding with 2/sup p/-ary LDPC codes, where p equals the number of encoded bits transmitted by the transmit antenna array during each signaling interval. For large transmit arrays, we study a layered space-time architecture using binary LDPC codes as component codes of each layer: We show through simulation that, when applied to multiple antenna systems with high diversity order, LDPC codes of quasi-regular construction are able to achieve higher coding gain and/or diversity gain than previously proposed space-time trellis codes, space-time turbo codes, and convolutional codes in a number of fading conditions. Extending the work of density evolution with Gaussian approximation, we study 2/sup p/-ary LDPC codes on multiple antenna fading channels, and search for the optimum 2/sup p/-ary quasi-regular codes in quasi-static fading. We also show that on fast fading channels, 2/sup p/-ary irregular LDPC codes, though designed for static channels, have superior performance to nonbinary quasiregular codes and binary irregular codes specifically designed for fast fading channels.     

Sphere-packing bounds for convolutional codes

We introduce general sphere-packing bounds for convolutional codes. These improve upon the Heller (1968) bound for high-rate convolutional codes. For example, based on the Heller bound, McEliece (1998) suggested that for a rate (n - 1)/n convolutional code of free distance 5 with /spl nu/ memory elements in its minimal encoder it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. A simple corollary of our bounds shows that in this case, n < 2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened. Note that the resulting bounds are also highly useful for codes of limited bit-oriented trellis complexity. Moreover, the results can be used in a constructive way in the sense that they can be used to facilitate efficient computer search for codes.     

A class of irregular LDPC codes with low error floor and low encoding complexity

In this letter, we propose a class of irregular structured low-density parity-check (LDPC) codes with low error floor and low encoding complexity by designing the parity check matrix in a triangular plus dual-diagonal form. The proposed irregular codes clearly lower the error floor and dramatically improve the performance in the waterfall region of error-rate curves. Being characterized by linear encoding complexity, the encoders of the proposed codes attain throughputs over 10 Gbit/s.     

Low-floor decoders for LDPC codes

One of the most significant impediments to the use of LDPC codes in many communication and storage systems is the error-rate floor phenomenon associated with their iterative decoders. The error floor has been attributed to certain subgraphs of an LDPC code?s Tanner graph induced by so-called trapping sets. We show in this paper that once we identify the trapping sets of an LDPC code of interest, a sum-product algorithm (SPA) decoder can be custom-designed to yield floors that are orders of magnitude lower than floors of the the conventional SPA decoder. We present three classes of such decoders: (1) a bi-mode decoder, (2) a bit-pinning decoder which utilizes one or more outer algebraic codes, and (3) three generalized-LDPC decoders. We demonstrate the effectiveness of these decoders for two codes, the rate-1/2 (2640,1320) Margulis code which is notorious for its floors and a rate-0.3 (640,192) quasi-cyclic code which has been devised for this study. Although the paper focuses on these two codes, the decoder design techniques presented are fully generalizable to any LDPC code.     

New covering codes from an ADS-like construction

A covering code construction is presented. Using this construction it is shown that t[52,39]=3, t[36,21]=4, t[58,32]=7, K(32,2)/spl les/62/spl middot/2/sup 18/, and K(62,5)/spl les/31/spl middot/2/sup 37/, where t[n,k] is the minimum covering radius among all binary [n,k] codes and K(n,R) is the minimum cardinality of a binary code of length n and covering radius R. Four new linear codes found by computer search are also given. These include a [23,9]5 code, a [32,8]10 code, a [51,41]2 code, and a [45,20]8 code.     

高码率短码长两边类型LDPC码的设计

高码率LDPC（10w．densityparity-check）码的设计一直是当前纠错编码领域的难点,尤其在短码长情况下。近年被提出的两边类型LDPC（tow—edgetypeLDPC,TET-LDPC）码在高码率情况下具有比传统LDPC码更加优秀的纠错性能。基于对TET—LDPC码结构优势的分析,文中提出一种优化设计方法,该方法通过合理选取TET．LDPC码中删余变量节点的度以及优化校验节点和变量节点的连接关系,进一步提高了该码型的性能。仿真结果显示,在AWGN信道下,文中设计的高码率短码长TET—LDPC码,不仅好于传统LDPC码,而且也好于传统的TET-LDPC码,具有更低的误码平台。     

Explicit construction of families of LDPC codes with no 4-cycles

Low-density parity-check (LDPC) codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl rceil/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction. We also give simulation results for some of our codes.     

Structured IRA Codes: Performance Analysis and Construction

In this letter, we present design techniques for structured irregular repeat-accumulate (S-IRA) codes with low error-rate floors. These S-IRA codes need not be quasi-cyclic, permitting flexibility in code dimension, length, and rate. We present a simple ensemble estimate of the level of the error-rate floor of finite-length IRA codes on the additive white Gaussian noise channel. This performance estimate provides guidance on the choice of IRA code column weights which yield low floors. We also present two design algorithms for S-IRA codes accompanied by software- and hardware-based performance results which demonstrate their low floors. Lastly, we present two design algorithms for multirate S-IRA code families implementable by a single encoder/decoder     

Fast transform for decoding both errors and erasures of Reed-Solomon codes over GF(2/sup m/) for 8/spl les/m/spl les/10

In this letter, it is shown that a fast, prime-factor discrete Fourier transform (DFT) algorithm can be modified to compute Fourier-like transforms of long sequences of 2/sup m/-1 points over GF(2/sup m/), where 8/spl les/m/spl les/10. Using these transforms, together with the Berlekamp-Massey algorithm, the complexity of the transform-domain decoder for correcting both errors and erasures of the Reed-Solomon codes of block length 2/sup m/-1 over GF(2/sup m/) for 8/spl les/m/spl les/10 is reduced substantially from the previous time-domain decoder. A computer simulation verifies these new results.     

Properties of optimum binary message-passing decoders

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.     

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.     

低差错平底特性的非规则LDPC码的设计

介绍了非规则LDPC码的发展并给出了其优势及缺点，重点论述用ACE算法来构造非规则LDPC码从而降低其差错平底特性。对降低非规则LDPC码的差错平底特性的其它方法提出了展望。     

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.     

Optimal linear identifying codes

Identifying codes can be used to locate malfunctioning processors. We say that a code C of length n is a linear (1,/spl les/l)-identifying code if it is a subspace of F/sub 2//sup n/ and for all X,Y/spl sube/F/sub 2//sup n/ such that |X|, |Y|/spl les/l and X/spl ne/Y, we have /spl cup//sub x/spl isin/X/(B(x)/spl cap/C)/spl ne//spl cup/y/spl isin/Y(B(y)/spl cap/C). Strongly (1,/spl les/l)-identifying codes are a variant of identifying codes. We determine the cardinalities of optimal linear (1,/spl les/l)-identifying and strongly (1,/spl les/l)-identifying codes in Hamming spaces of any dimension for locating any at most l malfunctioning processors.     

Low-Floor Detection/Decoding of LDPC-Coded Partial Response Channels

The error-rate floor phenomenon associated with iterative LDPC decoders has delayed the use of LDPC codes in certain communication and storage systems. Error floors are known to generally be caused by so-called trapping sets which have the effect of confounding the decoder. In this paper, we introduce two techniques that lower the error-rate floors for LDPC-coded partial response (PR) channels which are applicable to magnetic and optical storage. The techniques involve, via external measures, ?pinning? one of the bits in each problematic trapping set and then letting the iterative decoder proceed to correct the rest of the bits. We also extend our earlier work on generalized-LDPC (G-LDPC) decoders for error-floor mitigation on the AWGN channel to partial response channels. Our simulations on PR1 and EPR4 channels demonstrate that the floor for the code chosen for this study, a 0.78(2048,1600) quasicyclic LDPC code, is lowered by orders of magnitude, beyond the reach of simulations. Because simulation in the floor region is so time-consuming, a method for accelerating such simulations is essential for research in this area. In this paper, we present an extension of Richardson?s importance sampling technique for estimating the level of error floors.     

Optimized low-density parity-check codes for partial response channels

We optimize irregular low-density parity-check (LDPC) codes to closely approach the independent and uniformly distributed (i.u.d.) capacities of partial response channels. In our approach, we use the degree sequences optimization method for memoryless channels proposed by Richardson, Shokrollahi, and Urbanke and appropriately modify it for channels with memory. With this optimization algorithm we construct codes whose noise tolerance thresholds are within 0.15 dB of the i.u.d. channel capacities. Our simulation results show that irregular LDPC codes with block lengths 10/sup 6/ bits yield bit error rates 10/sup -6/ at signal-to-noise ratios 0.22 dB away from the channel capacities.