Approximately Lower Triangular Ensembles of LDPC Codes With Linear Encoding Complexity

The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length 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.     

Quasi-cyclic LDPC codes for fast encoding

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.     

一种高码率低复杂度准循环LDPC码设计研究

该文设计了一种特殊的高码率准循环低密度校验(QC-LDPC)码,其校验矩阵以单位矩阵的循环移位阵为基本单元,与随机构造的LDPC码相比可节省大量存储单元。利用该码校验矩阵的近似下三角特性,一种高效的递推编码方法被提出,它使得该码编码复杂度与码长成线性关系。另外,该文提出一种分析QC-LDPC码二分图中短长度环分布情况的方法,并且给出了相应的不含长为4环QC-LDPC码的构造方法。计算机仿真结果表明,新码不但编码简单,而且具有高纠错能力、低误码平层。     

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.     

GB20600标准的LDPC码的改进

尽管LDPC码已经被GB20600标准采纳作为信道编码,与其它LDPC码相比,在同样码长和码率的情况下,GB20600 LDPC码误码率性能并非最佳;GB20600标准的LDPC码的码长达7493,存在编码复杂性问题,但是GB20600 LDPC码未采用基于校验矩阵的快速算法,这给GB20600 LDPC编解码器的硬件实现带来较大的困难。本文在现有GB20600 LDPC码的设计框架下,对GB20600中LDPC码的校验矩阵进行了修改,在此基础上提出一种有效的LDPC码的快速迭代算法,使编解码器的硬件易于实现。改进后的LDPC码的编码算法具有较低的实现复杂度。仿真结果表明,改进后的LDPC码的误包率性能优于现GB20600中LDPC码的误包率性能。      

非规则LDPC码的不等错误保护性能研究

提出了一种具有不等错误保护性能的非规则低密度校验(LDPC,low-density parity-check)码信道编码方案, 构造了重量递增校验(weight-increasing parity-check)矩阵,系统编码时,重要信息比特映射到LDPC码的“精华”比特上。AWGN和Rayliegh衰落信道的仿真结果表明,与随机构造的非规则LDPC码相比,WICP-LDPC码具有好的UEP性能。     

Pseudorandom construction of low-density parity-check codes using linear congruential sequences

We consider maximal-length linear congruential sequences generated using a simple recursion to generate the bipartite graph of a low-density parity-check (LDPC) code. The main advantage is that the graph structure of the codes (edge connections) can be generated using a recursion, rather than having to store the graph connections in memory, which facilitates hardware implementation of the decoder. For this class of codes, sufficient conditions on the recursion parameters are derived, such that regular LDPC codes can be constructed with no cycles of length four or less. Simulation results show that these codes provide almost the same performance of a constrained pseudorandom construction that explicitly avoids cycles of length less than or equal to four.     

Asymptotic enumeration methods for analyzing LDPC codes

We show how asymptotic estimates of powers of polynomials with nonnegative coefficients can be used in the analysis of low-density parity-check (LDPC) codes. In particular, we show how these estimates can be used to derive the asymptotic distance spectrum of both regular and irregular LDPC code ensembles. We then consider the binary erasure channel (BEC). Using these estimates we derive lower bounds on the error exponent, under iterative decoding, of LDPC codes used over the BEC. Both regular and irregular code structures are considered. These bounds are compared to the corresponding bounds when optimal (maximum-likelihood (ML)) decoding is applied.     

On the Construction of Quasi-Systematic Block-Circulant LDPC Codes

A class of quasi-systematic block-circulant LDPC (QSBC-LDPC) Codes is proposed. The parity-check matrix of a QSBC-LDPC code is a sparse block-circulant matrix with a quasi-systematic structure. Due to the special structure of the parity-check matrix, only limited memories, XOR computations and cyclic-shifting operations are needed in the recursive encoding process of the QSBC-LDPC codes. Simulations show that the QSBC-LDPC codes provide remarkable performance improvement with low encoding complexity.     

The equivalence between slepian-wolf coding and channel coding under density evolution

We consider Slepian-Wolf code design based on low density parity-check (LDPC) coset codes. The density evolution formula for Slepian-Wolf coding is derived. An intimate connection between Slepian-Wolf coding and channel coding is then established. Specifically we show that, under density evolution, each Slepian-Wolf coding problem is equivalent to a channel coding problem for a binary-input output-symmetric channel.     

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.     

Euclidean Geometry LDPC-VBLAST System Design and Performance Evaluation

Among popular multi-transmit and multi-receive antennas techniques, the VBLAST (Vertical Bell Laboratories Layered Space-Time) architecture has been shown to be a good solution for wireless communications applications that require the transmission of data at high rates. Recently, the application of efficient error correction coding schemes such as low density parity-check (LDPC) codes to systems with multi-transmit and multi-receive antennas has shown to significantly improve bit error rate performance. Although irregular LDPC codes with non-structure are quite popular due to the ease of constructing the parity check matrices and their very good error rate performance, the complexity of the encoder is high. Simple implementation of both encoder and decoder can be an asset in wireless communications applications. In this paper, we study the application of Euclidean geometry LDPC codes to the VBLAST system. We assess system performance using different code parameters and different numbers of antennas via Monte-Carlo simulation and show that the combination of Euclidean geometry LDPC codes and VBLAST can significantly improve bit error rate performance. We also show that interleaving data is necessary to improve performance of LDPC codes when a higher number of antennas is, used in order to mitigate the effect of error propagation. The simplicity of the implementation of both encoder and decoder makes Euclidean geometry LDPC codes with VBLAST system attractive and suitable for practical applications.     

Layered Approx-Regular LDPC: Code Construction and Encoder/Decoder Design

Layered approximately regular (LAR) low-density parity-check (LDPC) codes are proposed, with which one single pair of encoder and decoder support various code lengths and code rates. The parity check matrices of LAR-LDPC codes have a "layer-block-cell" structure with some additional constraints. An encoder architecture is then designed for LAR-LDPC codes, by making two improvements to the Richardson-Urbanke approach: the forward substitution operation is entirely removed and the dense-matrix-vector multiplication is handled using feedback shift-registers. A partially parallel decoder architecture is also designed for LAR-LDPC codes, where a layered modified min-sum decoding algorithm is used to trade off among complexity, speed, and performance. More importantly, the interconnection network, which is inevitable for partially parallel decoders, has much lower hardware complexity compared with that for general LDPC codes. Both the encoder and decoder architectures are highly flexible in code length and code rate.     

Design of Low-Rate Irregular LDPC Codes Using Trellis Search

A simple design method using trellis search is proposed for good low-density parity-check (LDPC) codes with relatively low code rates. By applying a trellis search technique to the design of a pre-assigned part of the parity-check matrix that allows a simple encoding, we improve the distribution of cycles formed by the entries contained in the parity-check part of the parity-check matrix. In addition, we extend the proposed algorithm to a class of structured LDPC codes, which have been recently preferred in many practical applications. Simulation results show that the codes designed by the proposed method outperform those constructed by conventionally used greedy design algorithms.     

Applications of low-density parity-check codes to magneticrecording channels

We consider the use of high-rate low-density parity-check (LDPC) codes for magnetic recording. We design and evaluate the performance of a magnetic recording system, which uses an LDPC code as the error-correcting code, in conjunction with a rate 16/17 quasimaximum-transition-run (QMTR) channel code on a modified E² PR4 (ME²PR4)-equalized channel. Iterative decoding between the partial response channel and the LDPC code is performed. Simulations show that an additional four-dB gain over the QMTR code can be obtained by the LDPC code. The algorithms used to design this LDPC code are also discussed     

High-Rate Nonbinary Regular Quasi-Cyclic LDPC Codes for Optical Communications

The parity-check matrix of a nonbinary (NB) low-density parity-check (LDPC) code over Galois field GF(q) is constructed by assigning nonzero elements from GF(q) to the 1s in corresponding binary LDPC code. In this paper, we state and prove a theorem that establishes a necessary and sufficient condition that an NB matrix over GF(q), constructed by assigning nonzero elements from GF(q) to the 1s in the parity-check matrix of a binary quasi-cyclic (QC) LDPC code, must satisfy in order for its null-space to define a nonbinary QC-LDPC (NB-QC-LDPC) code. We also provide a general scheme for constructing NB-QC-LDPC codes along with some other code construction schemes targeting different goals, e.g., a scheme that can be used to construct codes for which the fast-Fourier-transform-based decoding algorithm does not contain any intermediary permutation blocks between bit node processing and check node processing steps. Via Monte Carlo simulations, we demonstrate that NB-QC-LDPC codes can achieve a net effective coding gain of 10.8 dB at an output bit error rate of 10^-12. Due to their structural properties that can be exploited during encoding/decoding and impressive error rate performance, NB-QC-LDPC codes are strong candidates for application in optical communications.     

Quasi-cyclic LDPC codes using overlapping matrices and their layered decoders

Quasi-cyclic (QC) low-density parity-check (LDPC) codes have the parity-check matrices consisting of circulant matrices. Since QC LDPC codes whose parity-check matrices consist of only circulant permutation matrices are difficult to support layered decoding and, at the same time, have a good degree distribution with respect to error correcting performance, adopting multi-weight circulant matrices to parity-check matrices is useful but it has not been much researched. In this paper, we propose a new code structure for QC LDPC codes with multi-weight circulant matrices by introducing overlapping matrices. This structure enables a system to operate on dual mode in an efficient manner, that is, a standard QC LDPC code is used when the channel is relatively good and an enhanced QC LDPC code adopting an overlapping matrix is used otherwise. We also propose a new dual mode parallel decoder which supports the layered decoding both for the standard QC LDPC codes and the enhanced QC LDPC codes. Simulation results show that QC LDPC codes with the proposed structure have considerably improved error correcting performance and decoding throughput.     

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.     

一种半随机半代数的非正则LDPC码构造方法

LDPC码由于其卓越的纠错性能引起了学术界的广泛重视，当前LDPC所面临的一个主要问题是其编码复杂性的问题。本文给出了一种半代数半随机的非正则LDPC码构造方法，由该方法所构造的校验矩阵具有近似下三角特性，从而可以大大降低LDPC的编译码复杂性，同时具有与完全随机LDPC码相匹配的性能。