Non‐binary protograph low‐density parity‐check codes for space communications

Protograph‐based non‐binary low‐density parity‐check (LDPC) codes with ultra‐sparse parity‐check matrices are compared with binary LDPC and turbo codes (TCs) from space communication standards. It is shown that larger coding gains are achieved, outperforming the binary competitors by more than 0.3 dB on the additive white Gaussian noise channel (AWGN). In the short block length regime, the designed codes gain more than 1 dB with respect to the binary protograph LDPC codes recently proposed for the next generation up‐link standard of the Consultative Committee for Space Data Systems. Copyright © 2012 John Wiley & Sons, Ltd.     

Construction of quasi‐cyclic low‐density parity‐check codes with low encoding complexity

Low encoding complexity is very important for quasi‐cyclic low‐density parity‐check (QC‐LDPC) codes used in wireless communication systems. In this paper, a new scheme is presented to construct QC‐LDPC codes with low encoding complexity. This scheme is called two‐stage particle swarm optimization (TS‐PSO) algorithm, in which both the threshold and girth distribution of QC‐LDPC codes are considered. The proposed scheme is composed of two stages. In the first stage, we construct a binary base matrix of QC‐LDPC code with the best threshold. The matrix is constructed by combining a binary PSO algorithm and the protograph extrinsic information transfer (PEXIT) method. In the second stage, we search an exponent matrix of the QC‐LDPC code with the best girth distribution. This exponent matrix is based on the base matrix obtained in the first stage. Consequently, the parity‐check matrix of the QC‐LDPC code with the best threshold and best girth distribution are constructed. Furthermore, bit error rate performances are compared for the QC‐LDPC codes constructed by proposed scheme, the QC‐LDPC code in 802.16e standard, and the QC‐LDPC code in Tam's study. Simulation results show that the QC‐LDPC codes proposed in this study are superior to both the 802.16e code and the Tam code on the additive white Gaussian noise (AWGN) and Rayleigh channels. Moreover, proposed scheme is easily implemented, and is flexible and effective for constructing QC‐LDPC codes with low encoding complexity. Copyright © 2012 John Wiley & Sons, Ltd.     

Operation reduced low‐density parity‐check decoding algorithms for low power communication systems

Decoding operation reduction algorithms on min‐sum layered low‐density parity‐check (LDPC) decoders are proposed in this paper. Our algorithm freezes selected operations in high reliable nodes to reduce power while preserving error correcting performance. Both memory accesses and active node switching activities can be reduced. A novel node refresh mechanism reactivates frozen nodes to minimize coding gain degradation. We propose three decoding operation reduction algorithm variations to trade‐off complexity and operation reduction for LDPC decoders with different degrees of parallelism and memory requirement. Simulation results show that the number of LDPC decoding operations is reduced across all SNR ranges. The decoding convergence speed is not affected. Hardware architecture and FPGA implementation for IEEE 802.16e LDPC codes are presented. Copyright © 2011 John Wiley & Sons, Ltd.     

Overlapped message passing for quasi-cyclic low-density parity check codes

In this paper, a systematic approach is proposed to develop a high throughput decoder for quasi-cyclic low-density parity check (LDPC) codes, whose parity check matrix is constructed by circularly shifted identity matrices. Based on the properties of quasi-cyclic LDPC codes, the two stages of belief propagation decoding algorithm, namely, check node update and variable node update, could be overlapped and thus the overall decoding latency is reduced. To avoid the memory access conflict, the maximum concurrency of the two stages is explored by a novel scheduling algorithm. Consequently, the decoding throughput could be increased by about twice assuming dual-port memory is available.     

Semi‐random LDPC codes for CDMA communication over non‐linear band‐limited satellite channels

This paper considers the application of low‐density parity check (LDPC) error correcting codes to code division multiple access (CDMA) systems over satellite links. The adapted LDPC codes are selected from a special class of semi‐random (SR) constructions characterized by low encoder complexity, and their performance is optimized by removing short cycles from the code bipartite graphs. Relative performance comparisons with turbo product codes (TPC) for rate 1/2 and short‐to‐moderate block sizes show some advantage for SR‐LDPC, both in terms of bit error rate and complexity requirements. CDMA systems using these SR‐LDPC codes and operating over non‐linear, band‐limited satellite links are analysed and their performance is investigated for a number of signal models and codes parameters. The numerical results show that SR‐LDPC codes can offer good capacity improvements in terms of supportable number of users at a given bit error performance. Copyright © 2006 John Wiley & Sons, Ltd.     

Performance of low density parity check coded continuous phase frequency shift keying (LDPCC‐CPFSK) over fading channels

In this paper, in order to improve bit error performance, bandwidth efficiency and reduction of complexity compared to related schemes such as turbo codes, we combine low density parity check (LDPC) codes and continuous phase frequency shift keying (CPFSK) modulation and introduce a new scheme, called ‘low density parity check coded‐continuous phase frequency shift keying (LDPCC‐CPFSK)’. Since LDPC codes have very large Euclidean distance and use iterative decoding algorithms, they have high error correcting capacity and have very close performances to Shannon limit. In all communication systems, phase discontinuities of modulated signals result extra bandwidth requirements. Continuous phase modulation (CPM) is a powerful solution for this problem. Beside CPM provides good bandwidth efficiency; it also improves bit error performance with its memory unit. In our proposed scheme, LDPC and CPFSK, which is a special type of CPM, are considered together to improve both error performance and bandwidth efficiencies. We also obtain error performance curves of LDPCC‐CPFSK via computer simulations for both regular and irregular LDPC code. Simulation results are drawn for 4‐ary CPFSK, 8‐ary CPFSK and 16‐ary CPFSK over AWGN, Rician and Rayleigh fading channels for maximum 100 iterations, while the frame size is chosen as 504. Copyright © 2006 John Wiley & Sons, Ltd.     

On Combining Chase‐2 and Sum‐Product Algorithms for LDPC Codes

This letter investigates the combination of the Chase‐2 and sum‐product (SP) algorithms for low‐density parity‐check (LDPC) codes. A simple modification of the tanh rule for check node update is given, which incorporates test error patterns (TEPs) used in the Chase algorithm into SP decoding of LDPC codes. Moreover, a simple yet effective approach is proposed to construct TEPs for dealing with decoding failures with low‐weight syndromes. Simulation results show that the proposed algorithm is effective in improving both the waterfall and error floor performance of LDPC codes.     

Quasi‐regular rate‐compatible LDPC codes with a novel diagonal‐tailed encoding on noisy channels

It is well known that conventional rate‐compatible (RC) codes, such as Raptor codes, only perform well at long code lengths. However, we propose a class of RC codes with short code lengths in this paper. Particularly, we develop a computational approach to design online‐generated RC low‐density parity‐check (LDPC) codes available on noisy channels. We first propose a diagonal‐tailed encoding to generate Quasi‐regular low‐density generator matrix codes. Then, an optimal encoding profile for RC codes is achieved with a linear interpolation approach that is based on the fixed‐rate quasi‐regular LDPC codes. Finally, we evaluate the rateless and fixed‐rate performances of the proposed RC codes by extensive simulation results on various code rates with different modulations. Copyright © 2013 John Wiley & Sons, Ltd.     

Design of Quasi‐Cyclic Low‐Density Parity Check Codes with Large Girth

In this paper we propose a graph‐theoretic method based on linear congruence for constructing low‐density parity check (LDPC) codes. In this method, we design a connection graph with three kinds of special paths to ensure that the Tanner graph of the parity check matrix mapped from the connection graph is without short cycles. The new construction method results in a class of (3, ρ)‐regular quasi‐cyclic LDPC codes with a girth of 12. Based on the structure of the parity check matrix, the lower bound on the minimum distance of the codes is found. The simulation studies of several proposed LDPC codes demonstrate powerful bit‐error‐rate performance with iterative decoding in additive white Gaussian noise channels.     

Loosely coupled memory-based decoding architecture for low density parity check codes

Parallel decoding is required for low density parity check (LDPC) codes to achieve high decoding throughput, but it suffers from a large set of registers and complex interconnections due to randomly located 1's in the sparse parity check matrix. This paper proposes a new LDPC decoding architecture to reduce registers and alleviate complex interconnections. To reduce the number of messages to be exchanged among processing units (PUs), two data flows that can be loosely coupled are developed by allowing duplicated operations. In addition, intermediate values are grouped and stored into local storages each of which is accessed by only one PU. In order to save area, local storages are implemented using memories instead of registers. A partially parallel architecture is proposed to promote the memory usage and an efficient algorithm that schedules the processing order of the partially parallel architecture is also proposed to reduce the overall processing time by overlapping operations. To verify the proposed architecture, a 1024 bit rate-1/2 LDPC decoder is implemented using a 0.18-/spl mu/m CMOS process. The decoder runs correctly at the frequency of 200 MHz, which enables almost 1 Gbps decoding throughput. Since the proposed decoder occupies an area of 10.08 mm/sup 2/, it is less than one fifth of area compared to the previous architecture.     

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.     

Design of Encoder and Decoder for LDPC Codes Using Hybrid H‐Matrix

Low‐density parity‐check (LDPC) codes have recently emerged due to their excellent performance. However, the parity check (H) matrices of the previous works are not adequate for hardware implementation of encoders or decoders. This paper proposes a hybrid parity check matrix which is efficient in hardware implementation of both decoders and encoders. The hybrid H‐matrices are constructed so that both the semi‐random technique and the partly parallel structure can be applied to design encoders and decoders. Using the proposed methods, the implementation of encoders can become practical while keeping the hardware complexity of the partly parallel decoder structures. An encoder and a decoder are designed using Verilog‐HDL and are synthesized using a 0.35 µm CMOS standard cell library.     

A high‐performance belief propagation decoding algorithm for codes with short cycles

The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.     

Cross parity check convolutional codes

A class of convolutional codes called cross parity check (CPC) codes, which are useful for the protection of data stored on magnetic tape, is described and analyzed. CPC codes are first explained geometrically; their construction is described in terms of constraining data written onto a tape in such a way that when lines of varying slope are drawn across the tape, the bits falling on those lines sum to zero modulo two. This geometric interpretation is then formalized by the construction of canonical parity check matrices and systematic generator matrices for CPC codes and by computing their constraint lengths. The distance properties of CPC codes are analyzed, and it is shown that these codes are maximum distance separable convolutional codes. In addition, examples are given of both error and erasure decoding algorithms that take advantage of the geometric regularity of CPC codes. The technique of parity check matrix reduction, which is useful for reducing the inherent decoding delay of CPC codes, is described. The technique consists of dividing each term of the parity check matrix by some polynomial and retaining only the remainder. A class of polynomials that are particularly attractive for this purpose if identified     

Low-density parity check codes and iterative decoding for long-haul optical communication systems

A forward-error correction (FEC) scheme based on low-density parity check (LDPC) codes and iterative decoding using belief propagation in code graphs is presented in this paper. We show that LDPC codes provide a significant system performance improvement with respect to the state-of-the-art FEC schemes employed in optical communications systems. We present a class of structured codes based on mutually orthogonal Latin rectangles. Such codes have high rates and can lend themselves to very low-complexity encoder/decoder implementations. The system performance is further improved by a code design that eliminates short cycles in a graph employed in iterative decoding.     

Design and analysis of simple irregular LDPC codes with finite‐lengths and their application in CDMA systems

In this paper, we design and optimize simple irregular low‐density parity‐check (LDPC) codes for finite‐length applications where the asymptotic noise threshold of the channel cannot play as a dominant optimization factor. Our design procedure is based on some observations resulted from analytical study of these codes. Although we present our design procedure for some specified rates but it can generally be used for any rate. Specifically, we design a simple irregular LDPC code for IS‐95 and compare its performance with the other reported codes 1 - 3 for this application. Our results show a 3.7‐fold increase in the capacity at bit error rate (BER) equal to 10⁻⁵ compared to the low‐rate orthogonal convolutional codes and 1.2 times increase compared to a high performance LDPC code of Reference 3 . Copyright © 2004 John Wiley & Sons, Ltd.     

The Effect of Block Interleaving in an LDPC‐Turbo Concatenated Code

The effect of block interleaving in a low density parity check (LDPC)‐turbo concatenated code is investigated in this letter. Soft decoding can be used in an LDPC code unlike the conventional Reed‐Solomon (RS) code. Thus, an LDPC‐turbo concatenated code can show better performance than the conventional RS‐turbo concatenated code. Furthermore, the performance of an LDPC‐turbo code can be improved by using a block interleaver between the LDPC and turbo code. The average number of iterations in LDPC decoding can also be reduced by a block interleaver.     

Low‐complexity turbo detection for single‐carrier low‐density parity‐check‐coded multiple‐input multiple‐output underwater acoustic communications

A low‐complexity turbo detection scheme is proposed for single‐carrier multiple‐input multiple‐output (MIMO) underwater acoustic (UWA) communications using low‐density parity‐check (LDPC) channel coding. The low complexity of the proposed detection algorithm is achieved in two aspects: first, the frequency‐domain equalization technique is adopted, and it maintains a low complexity irrespective of the highly dispersive UWA channels; second, the computation of the soft equalizer output, in the form of extrinsic log‐likelihood ratio, is performed with an approximating method, which further reduces the complexity. Moreover, attributed to the LDPC decoding, the turbo detection converges within only a few iterations. The proposed turbo detection scheme has been used for processing real‐world data collected in two different undersea trials: WHOI09 and ACOMM09. Experimental results show that it provides robust detection for MIMO UWA communications with different modulations and different symbol rates, at different transmission ranges. Copyright © 2011 John Wiley & Sons, Ltd.     

Systematic recursive construction of LDPC codes

This letter presents a systematic and recursive method to construct good low-density parity-check (LDPC) codes, especially those with high rate. The proposed method uses a parity check matrix of a quasi-cyclic LDPC code with given row and column weights as a core upon which the larger code is recursively constructed with extensive use of pseudorandom permutation matrices. This construction preserves the minimum distance and girth properties of the core matrix and can generate either regular, or irregular LDPC codes. The method provides a unique representation of the code in compact notation.     

Blind frame synchronization for error correcting codes having a sparse parity check matrix

We present in this letter a blind frame synchronization method based on a Maximum A Posteriori probability (MAP) approach. Applied to coded communication systems, this method is based on the calculation of the Log-likelihood Ratios (LLR) of the syndrome obtained according to the parity check matrix of the code. After presenting the proposed method, we compare it to an existing blind synchronization method previously introduced. Simulation results show that the proposed method outperforms the existing one and presents good performance when applied to codes having a sparse parity check matrix such as Low Density Parity Check (LDPC) codes and convolutional codes.