Near-Shannon-limit quasi-cyclic low-density parity-check codes

This letter presents two classes of quasi-cyclic low-density parity-check codes that perform close to the Shannon limit.     

Simple reconfigurable low-density parity-check codes

Low-density parity-check codes (LDPCC) have been recently investigated as a possible solution for high data rate applications, for both space and terrestrial wireless communications. A main issue is the research of low complexity encoding and decoding schemes. In this letter we present a class of reconfigurable LDPCC characterized by low encoding and decoding complexity: we call them generalized irregular repeat-accumulate (GeIRA) codes.     

Rate-compatible puncturing of low-density parity-check codes

In this correspondence, we consider puncturing of low-density parity-check (LDPC) codes for additive white Gaussian noise (AWGN) channels. We show that good puncturing patterns exist and that the puncturing can be performed in a rate-compatible fashion. Furthermore, rate-compatible puncturing results in a small loss of performance with respect to threshold, namely, the punctured code is good (in terms of threshold) across a range of rates when compared with the optimal codes for each rate. This allows one to implement a single "mother" encoder and decoder that is good across a wide range of rates.     

Graph-theoretic construction of low-density parity-check codes

This article presents a graph-theoretic method for constructing low-density parity-check (LDPC) codes from connected graphs without the requirement of large girth. This method is based on finding a set of paths in a connected graph, which satisfies the constraint that any two paths in the set are either disjoint or cross each other at one and only one vertex. Two trellis-based algorithms for finding these paths are devised. Good LDPC codes of practical lengths are constructed and they perform well with iterative decoding.     

Bootstrap decoding of low-density parity-check codes

An initial bootstrap step for the decoding of low-density parity-check (LDPC) codes is proposed. Decoding is initiated by first erasing a number of less reliable bits. New values and reliabilities are then assigned to erasure bits by passing messages from nonerasure bits through the reliable check equations. The bootstrap step is applied to the weighted bit-flipping algorithm to decode a number of LDPC codes. Large improvements in both performance and complexity are observed.     

Decoding low-density parity-check codes with probabilisticscheduling

We present a new message-passing schedule for the decoding of low-density parity-check (LDPC) codes. This approach, designated “probabilistic schedule”, takes into account the structure of the Tanner graph (TG) of the code. We show by simulation that the new schedule offers a much better performance/complexity trade-off. This work also suggests that scheduling plays an important role in iterative decoding and that a schedule that matches the structure of the TG is desirable     

Efficient encoding of low-density parity-check codes

Low-density parity-check (LDPC) codes can be considered serious competitors to turbo codes in terms of performance and complexity and they are based on a similar philosophy: constrained random code ensembles and iterative decoding algorithms. We consider the encoding problem for LDPC codes. More generally we consider the encoding problem for codes specified by sparse parity-check matrices. We show how to exploit the sparseness of the parity-check matrix to obtain efficient encoders. For the (3,6)-regular LDPC code, for example, the complexity of encoding is essentially quadratic in the block length. However, we show that the associated coefficient can be made quite small, so that encoding codes even of length n≃100000 is still quite practical. More importantly, we show that “optimized” codes actually admit linear time encoding     

Improved low-density parity-check codes using irregular graphs

We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance     

Efficient encoding of quasi-cyclic low-density parity-check codes

Quasi-cyclic (QC) low-density parity-check (LDPC) codes form an important subclass of LDPC codes. These codes have encoding advantage over other types of LDPC codes. This paper addresses the issue of efficient encoding of QC-LDPC codes. Two methods are presented to find the generator matrices of QC-LDPC codes in systematic-circulant (SC) form from their parity-check matrices, given in circulant form. Based on the SC form of the generator matrix of a QC-LDPC code, various types of encoding circuits using simple shift registers are devised. It is shown that the encoding complexity of a QC-LDPC code is linearly proportional to the number of parity bits of the code for serial encoding, and to the length of the code for high-speed parallel encoding.     

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.     

Soft-bit decoding of regular low-density parity-check codes

A novel representation, using soft-bit messages, of the belief propagation (BP) decoding algorithm for low-density parity-check codes is derived as an alternative to the log-likelihood-ratio (LLR)-based BP and min-sum decoding algorithms. A simple approximation is also presented. Simulation results demonstrate the functionality of the soft-bit decoding algorithm. Floating-point soft-bit and LLR BP decoding show equivalent performance; the approximation incurs 0.5-dB loss, comparable to min-sum performance loss over BP. Fixed-point results show similar performance to LLR BP decoding; the approximation converges to floating-point results with one less bit of precision.     

On maximum-length linear congruential-sequences-based low-density parity-check codes

This letter extends a low-density parity-check code construction using maximum-length linear congruential sequences by Prabhakar and Narayanan. The corresponding bipartite graphs of their construction were guaranteed to have a girth larger than four by a sufficient condition. However, their sufficient condition was limited to regular codes and data-node degree equal to three. The extension in this letter allows arbitrary data-node degrees and is applicable to irregular codes. Further, simpler sufficient conditions are derived and larger girths are addressed.     

On generalized low-density parity-check codes based on Hammingcomponent codes

In this paper we investigate a generalization of Gallager's (1963) low-density (LD) parity-check codes, where as component codes single error correcting Hamming codes are used instead of single error detecting parity-check codes. It is proved that there exist such generalized low-density (GLD) codes for which the minimum distance is growing linearly with the block length, and a lower bound of the minimum distance is given. We also study iterative decoding of GLD codes for the communication over an additive white Gaussian noise channel. The performance in terms of the bit error rate, obtained by computer simulations, is presented for GLD codes of different lengths     

Reliability-based coded modulation with low-density parity-check codes

In this letter, we consider the interleaver design in bit-interleaved coded modulation (BICM) with low-density parity-check (LDPC) codes. The design paradigm is to provide more coding protection through iterative decoding to bits that are less protected by modulation (and are thus less reliable at the output of the demodulator). The design is carried out by an ad hoc search algorithm over the column permutations of the parity-check matrix. Our simulations show that the proposed reliability-based coded modulation scheme can improve the error-rate performance of conventional BICM schemes based on regular LDPC codes by a few tenths of a decibel, with no added complexity.     

The renaissance of Gallager's low-density parity-check codes

LDPC codes were invented in 1960 by R. Gallager. They were largely ignored until the discovery of turbo codes in 1993. Since then, LDPC codes have experienced a renaissance and are now one of the most intensely studied areas in coding. In this article we review the basic structure of LDPC codes and the iterative algorithms that are used to decode them. We also briefly consider the state of the art of LDPC design.     

Verification-based decoding for packet-based low-density parity-check codes

We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units. Verification-based decoding requires only linear time for both encoding and decoding and succeeds with high probability under random errors. We describe how to utilize code scrambling to extend our results to channels with errors controlled by an oblivious adversary.     

Replica horizontal-shuffled iterative decoding of low-density parity-check codes

For practical considerations, it is essential to accelerate the convergence speed of the decoding algorithm used in an iterative decoding system. In this paper, replica versions of horizontal-shuffled decoding algorithms for low-density parity-check (LDPC) codes are proposed to improve the convergence speed of the original versions. The extrinsic information transfer (EXIT) chart technique is extended to the proposed algorithms to predict their convergence behavior. Both EXIT chart analysis and numerical results show that replica plain horizontal-shuffled (RPHS) decoding converges much faster than both plain horizontal-shuffled (PHS) decoding and the standard belief-propagation (BP) decoding. Furthermore, it is also revealed that replica group horizontal-shuffled (RGHS) decoding can increase the parallelism of RPHS decoding as well as preserve its high convergence speed if an equivalence condition is satisfied, and is thus suitable for hardware implementation.     

Density evolution for low-density parity-check codes underMax-Log-MAP decoding

A density evolution procedure for low-density parity-check (LDPC) codes under Max-Log-MAP decoding is presented. Using this technique, the precise convergence threshold for LDPC code could be easily derived     

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.     

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.