High-performance simple-encoding generator-based systematic irregular LDPC codes and resulted product codes

Low-Density Parity-Check (LDPC) code is one of the most exciting topics among the coding theory community.It is of great importance in both theory and practical communications over noisy channels.The most advantage of LDPC codes is their relatively lower decoding complexity compared with turbo codes,while the disadvantage is its higher encoding complexity.In this paper,a new ap- proach is first proposed to construct high performance irregular systematic LDPC codes based on sparse generator matrix,which can significantly reduce the encoding complexity under the same de- coding complexity as that of regular or irregular LDPC codes defined by traditional sparse parity-check matrix.Then,the proposed generator-based systematic irregular LDPC codes are adopted as con- stituent block codes in rows and columns to design a new kind of product codes family,which also can be interpreted as irregular LDPC codes characterized by graph and thus decoded iteratively.Finally, the performance of the generator-based LDPC codes and the resultant product codes is investigated over an Additive White Gaussian Noise (AWGN) and also compared with the conventional LDPC codes under the same conditions of decoding complexity and channel noise.     

Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes: a finite geometry approach

This paper presents five methods for constructing nonbinary LDPC codes based on finite geometries. These methods result in five classes of nonbinary LDPC codes, one class of cyclic LDPC codes, three classes of quasi-cyclic LDPC codes and one class of structured regular LDPC codes. Experimental results show that constructed codes in these classes decoded with iterative decoding based on belief propagation perform very well over the AWGN channel and they achieve significant coding gains over Reed-Solomon codes of the same lengths and rates with either algebraic hard-decision decoding or Kotter-Vardy algebraic soft-decision decoding at the expense of a larger decoding computational complexity.     

Iterative decoding for partial response (PR), equalized,magneto-optical (MO) data storage channels

Turbo codes and low-density parity check (LDPC) codes with iterative decoding have received significant research attention because of their remarkable near-capacity performance for additive white Gaussian noise (AWGN) channels. Previously, turbo code and LDPC code variants are being investigated as potential candidates for high-density magnetic recording channels suffering from low signal-to-noise ratios (SNR). We address the application of turbo codes and LDPC codes to magneto-optical (MO) recording channels. Our results focus on a variety of practical MO storage channel aspects, including storage density, partial response targets, the type of precoder used, and mark edge jitter. Instead of focusing just on bit error rates (BER), we also study the block error statistics. Our results for MO storage channels indicate that turbo codes of rate 16/17 can achieve coding gains of 3-5 dB over partial response maximum likelihood (PRML) methods for a 10^-4 target BER. Simulations also show that the performance of LDPC codes for MO channels is comparable to that of turbo codes, while requiring less computational complexity. Both LDPC codes and turbo codes with iterative decoding are seen to be robust to mark edge jitter     

Recent Advances in Turbo Code Design and Theory

The discovery of turbo codes and the subsequent rediscovery of low-density parity-check (LDPC) codes represent major milestones in the field of channel coding. Recent advances in the design and theory of turbo codes and their relationship to LDPC codes are discussed. Several new interleaver designs for turbo codes are presented which illustrate the important role that the interleaver plays in these codes. The relationship between turbo codes and LDPC codes is explored via an explicit formulation of the parity-check matrix of a turbo code, and simulation results are given for sum product decoding of a turbo code.     

一种低译码复杂度的Turbo架构LDPC码

针对低密度奇偶校验(LDPC)码较大的译码复杂度和RAM占用,该文提出了一种低译码复杂度的Turbo架构LDPC码并行交织级联Gallager码 (Parallel Interleaved Concatenated Gallager Code,PICGC)。该文给出了PICGC的设计方法和编译码算法,并分析比较了PICGC译码器与LDPC译码器所需的RAM存储量,推导出RAM节省比的上界。理论分析和仿真结果表明,PICGC以纠错性能略微降低为代价,有效地降低译码复杂度和RAM存储量,且译码时延并未增加,是一种有效且易于实现的信道编码方案。     

FPGA implementation of low complexity LDPC iterative decoder

Low-density parity-check (LDPC) codes, proposed by Gallager, emerged as a class of codes which can yield very good performance on the additive white Gaussian noise channel as well as on the binary symmetric channel. LDPC codes have gained lots of importance due to their capacity achieving property and excellent performance in the noisy channel. Belief propagation (BP) algorithm and its approximations, most notably min-sum, are popular iterative decoding algorithms used for LDPC and turbo codes. The trade-off between the hardware complexity and the decoding throughput is a critical factor in the implementation of the practical decoder. This article presents introduction to LDPC codes and its various decoding algorithms followed by realisation of LDPC decoder by using simplified message passing algorithm and partially parallel decoder architecture. Simplified message passing algorithm has been proposed for trade-off between low decoding complexity and decoder performance. It greatly reduces the routing and check node complexity of the decoder. Partially parallel decoder architecture possesses high speed and reduced complexity. The improved design of the decoder possesses a maximum symbol throughput of 92.95 Mbps and a maximum of 18 decoding iterations. The article presents implementation of 9216 bits, rate-1/2, (3, 6) LDPC decoder on Xilinx XC3D3400A device from Spartan-3A DSP family.     

On the application of LDPC codes to arbitrary discrete-memoryless channels

We discuss three structures of modified low-density parity-check (LDPC) code ensembles designed for transmission over arbitrary discrete memoryless channels. The first structure is based on the well-known binary LDPC codes following constructions proposed by Gallager and McEliece, the second is based on LDPC codes of arbitrary (q-ary) alphabets employing modulo-q addition, as presented by Gallager, and the third is based on LDPC codes defined over the field GF(q). All structures are obtained by applying a quantization mapping on a coset LDPC ensemble. We present tools for the analysis of nonbinary codes and show that all configurations, under maximum-likelihood (ML) decoding, are capable of reliable communication at rates arbitrarily close to the capacity of any discrete memoryless channel. We discuss practical iterative decoding of our structures and present simulation results for the additive white Gaussian noise (AWGN) channel confirming the effectiveness of the codes.     

Gallager codes for CDMA applications .I. Generalizations, constructions, and performance bounds

We focus on applications of low-rate Gallager (1963) (low-density parity-check) codes in code-division multiple-access schemes. The codes that we present here achieve good performance with relatively short frame-lengths in additive white Gaussian noise channels and, perhaps more importantly, in fading channels. These codes can be decoded with low complexity by using iterative decoding procedures. We present a construction that yields good short frame-length Gallager codes. Bounds on the frame-error probability for a maximum-likelihood decoder are obtained.     

The Development of Turbo and LDPC Codes for Deep-Space Applications

The development of error-correcting codes has been closely coupled with deep-space exploration since the early days of both. Since the discovery of turbo codes in 1993, the research community has invested a great deal of work on modern iteratively decoded codes, and naturally NASA's Jet Propulsion Laboratory (JPL) has been very much involved. This paper describes the research, design, implementation, and standardization work that has taken place at JPL for both turbo and low-density parity-check (LDPC) codes. Turbo code development proceeded from theoretical analyses of polynomial selection, weight distributions imposed by interleaver designs, decoder error floors, and iterative decoding thresholds. A family of turbo codes was standardized and implemented and is currently in use by several spacecraft. JPL's LDPC codes are built from protographs and circulants, selected by analyses of decoding thresholds and methods to avoid loops in the code graph. LDPC encoders and decoders have been implemented in hardware for planned spacecraft, and standardization is under way.     

Reliable channel regions for good binary codes transmitted over parallel channels

We study the average error probability performance of binary linear code ensembles when each codeword is divided into J subcodewords with each being transmitted over one of J parallel channels. This model is widely accepted for a number of important practical channels and signaling schemes including block-fading channels, incremental redundancy retransmission schemes, and multicarrier communication techniques for frequency-selective channels. Our focus is on ensembles of good codes whose performance in a single channel model is characterized by a threshold behavior, e.g., turbo and low-density parity-check (LDPC) codes. For a given good code ensemble, we investigate reliable channel regions which ensure reliable communications over parallel channels under maximum-likelihood (ML) decoding. To construct reliable regions, we study a modifed 1961 Gallager bound for parallel channels. By allowing codeword bits to be randomly assigned to each component channel, the average parallel-channel Gallager bound is simplified to be a function of code weight enumerators and channel assignment rates. Special cases of this bound, average union-Bhattacharyya (UB), Shulman-Feder (SF), simplified-sphere (SS), and modified Shulman-Feder (MSF) parallel-channel bounds, allow for describing reliable channel regions using simple functions of channel and code spectrum parameters. Parameters describing the channel are the average parallel-channel Bhattacharyya noise parameter, the average channel mutual information, and parallel Gaussian channel signal-to-noise ratios (SNRs). Code parameters include the union-Bhattacharyya noise threshold and the weight spectrum distance to the random binary code ensemble. Reliable channel regions of repeat-accumulate (RA) codes for parallel binary erasure channels (BECs) and of turbo codes for parallel additive white Gaussian noise (AWGN) channels are numerically computed and compared with simulation results based on iterative decoding. In addition, an examp     

多层叠加LDPC码编码调制技术

 本文提出了一种多层叠加LDPC码编码调制系统.与传统的基于速率分配的多层编码调制技术相比,多层叠加编码调制系统具有很好的对称性和可扩展性.通过分析比较Turbo码译码算法与LDPC码的译码算法的复杂度,本文指出了多层叠加LDPC码编码调制系统具有译码简单,易于实现的优点.实验结果表明,多层叠加LDPC码编码调制系统可以在不牺牲带宽的同时获得较好的性能.     

High rate concatenated coding systems using bandwidth efficienttrellis inner codes

High-rate concatenated coding systems with bandwidth-efficient trellis inner codes and Reed-Solomon (RS) outer codes are investigated for application in high-speed satellite communication systems. Two concatenated coding schemes are proposed. In one the inner code is decoded with soft-decision Viterbi decoding, and the outer RS code performs error-correction-only decoding (decoding without side information). In the other the inner code is decoded with a modified Viterbi algorithm, which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, whereas branch metrics are used to provide reliability information on the decoded sequence. This information is used to erase unreliable bits in the decoded output. An errors-and-erasures RS decoder is then used for the outer code. The two schemes have been proposed for high-speed data communication on NASA satellite channels. The rates considered are at least double those used in current NASA systems, and the results indicate that high system reliability can still be achieved     

Iterative reliability-based decoding of low-density parity checkcodes

In this paper, reliability based decoding is combined with belief propagation (BP) decoding for low-density parity check (LDPC) codes. At each iteration, the soft output values delivered by the BP algorithm are used as reliability values to perform reduced complexity soft decision decoding of the code considered. This approach allows to bridge the error performance gap between belief propagation decoding which remains suboptimum, and maximum likelihood decoding which is too complex to be implemented for the codes considered. Trade-offs between decoding complexity and error performance are also investigated. In particular, a stopping criterion which reduces the average number of iterations at the expense of very little performance degradation is proposed for this combined decoding approach. Simulation results for several Gallager (1963, 1968) LDPC codes and different set cyclic codes of hundreds of information bits are given and elaborated     

Turbo encoding and decoding of Reed-Solomon codes through binary decomposition and self-concatenation

This paper presents a two-stage turbo-coding scheme for Reed-Solomon (RS) codes through binary decomposition and self-concatenation. In this scheme, the binary image of an RS code over GF(2/sup m/) is first decomposed into a set of binary component codes with relatively small trellis complexities. Then the RS code is formatted as a self-concatenated code with itself as the outer code and the binary component codes as the inner codes in a turbo-coding arrangement. In decoding, the inner codes are decoded with turbo decoding and the outer code is decoded with either an algebraic decoding algorithm or a reliability-based decoding algorithm. The outer and inner decoders interact during each decoding iteration. For RS codes of lengths up to 255, the proposed two-stage coding scheme is practically implementable and provides a significant coding gain over conventional algebraic and reliability-based decoding algorithms.     

Early detection of successful decoding for dual-diagonal block-based LDPC codes

Low-density parity-check (LDPC) codes [1] have attracted much attention in the last decade owing to their capacityapproaching performance. LDPC codes with a dual-diagonal blockbased structure can be encoded in linear time with lower encoder hardware complexity [2]. This class of LDPC codes is adopted by a number of standards such as wireless LAN (IEEE 802.11n) [3], wireless MAN (IEEE 802.16e, WiMAX) [4] and satellite TV (DVB-S2) [5]. LDPC codes are commonly decoded by the iterative belief-propagation (BP) algorithm. The decoder checks the parity-check equations to detect successful decoding at the end of the iteration. The Tanner graph of an irregular LDPC code consists of nodes with different degrees such that coded bits have unequal error protection [6]. Coded bits associated with higher degree nodes tend to converge to the correct answer more quickly. Hence, in order to give better protection to the transmitted data, data bits are always mapped to higher degree nodes whereas parity bits are mapped to lower degree nodes in the encoding process. The commonly used parity-check equations Hc t ? 0t will be satisfied after all the coded bits are correctly decoded. However, as discussed above, data bits converge to the correct answer much more quickly than parity bits, so some unnecessary iterations are wasted waiting for the parity bits to be decoded. In this Letter, a new set of low-complexity check equations are derived for dual-diagonal block-based LDPC codes. Early detection of successfully decoded data can be achieved by exploiting the structure and degree of distribution of the dual-diagonal parity check matrix. The decoder power, speed and complexity can be improved by adopting these equations. Simulation shows that the coding gain performance is little changed.     

Multilevel turbo coding with short interleavers

The impact of the interleaver, embedded in the encoder for a parallel concatenated code, called the turbo code, is studied. The known turbo codes consist of long random interleavers, whose purpose is to reduce the value of the error coefficients. It is shown that an increased minimum Hamming distance can be obtained by using a structured interleaver. For low bit-error rates (BERs), we show that the performance of turbo codes with a structured interleaver is better than that obtained with a random interleaver. Another important advantage of the structured interleaver is the short length required, which yields a short decoding delay and reduced decoding complexity (in terms of memory). We also consider the use of turbo codes as component codes in multilevel codes. Powerful coding structures that consist of two component codes are suggested. Computer simulations are performed in order to evaluate the reduction in coding gain due to suboptimal iterative decoding. From the results of these simulations we deduce that the degradation in the performance (due to suboptimal decoding) is very small     

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.     

Analysis and Design of Power-Efficient Coding Schemes With Parallel Concatenated Convolutional Codes

Analysis and Design of Power-Efficient Coding Schemes With Parallel Concatenated Convolutional Codes In the low signal-to-noise ratio regime, the performance of concatenated coding schemes is limited by the convergence properties of the iterative decoder. Idealizing the model of iterative decoding by an independence assumption, which represents the case in which the codeword length is infinitely large, leads to analyzable structures from which this performance limit can be predicted. Mutual information-transfer characteristics of the constituent coding schemes comprising convolutional encoders and soft-in/soft-out decoders have been shown to be sufficient to characterize the components within this model. Analyzing serial and parallel concatenations is possible just by these characteristics. In this paper, we extend the method of extrinsic information transfer charts that is limited to the case of a concatenation of two component codes, to the case of multiple turbo codes. Multiple turbo codes are parallel concatenations of three or more constituent codes, which, in general, may not be identical and may not have identical code rates. For the construction of low-rate codes, this concept seems to be very favorable, as power efficiencies close to the Shannon limit can be achieved with reasonable complexity.     

A new high rate code scheme with highly parallel and low complexity decoding algorithm

A new high rate code scheme is proposed in this paper. It consists of serial concatenated recursive systematic ordinary (nonpunctured) convolutional codes with only 8 states in the trellis of the corresponding reciprocal dual codes. With a low complexity and highly parallel decoding algorithm, over additive white Gaussian noise channels, the proposed codes can achieve good bit error rate (BER) performance comparable to that of turbo codes and low density parity check (LDPC) codes. At code rate R=16/17, the overall decoding complexity of the proposed code scheme is almost half that of the LDPC codes.     

On unequal error protection LDPC codes based on plotkin-type constructions

We introduce a new family of unequal error protection (UEP) codes, based on low-density parity-check (LDPC) component codes and Plotkin-type constructions. The codes are decoded iteratively in multiple stages, and the order of decoding determines the level of error protection. The level of UEP among the code bits is also influenced by the choice of the LDPC component codes and by some new reliability features incorporated into the decoding process. The proposed scheme offers a very good tradeoff between code performance on one side and encoding/decoding and storage complexity on the other side. The novel approach to UEP also allows for finding simple approximations for the achievable degrees of UEP, which can be used to govern practical code design implementations.