A Belief Propagation Algorithm with Set-Breaking to Lower Error-Floors of Low-Density Parity-Check Codes

In order to more exactly describe the errorfloor phenomenon in the iterative decoding of Low-density parity-check （LDPC） codes, a modified concept of the stable trapping set is introduced. Based on this new concept, an improved belief propagation algorithm with setbreaking mechanism is proposed to lower the error-floors of LDPC codes. Message ranking of the bit nodes in the stable trapping sets will be greatly lowered than that of other bit nodes in the iterative decoding process. By using this characteristic to label the bit nodes in the set, the corresponding initial log likelihood ratios will be flipped to break the stable trapping set and restart to decode. Simulation results verify the validity of the proposed algorithm.     

Layered Dynamic Schedulings for BP Decoding of LDPC Codes over GF（q）

A Layered dynamic scheduling （LDS） for Belief-propagation （BP） decoding of LDPC codes over GF（q） is presented, which is derived from the dynamic scheduling for the BP decoding of binary LDPC codes. In order to restrain the LDS from cycling in certain checknodes, a life-index for each check-node is adopted and the optimal value of the life-index is analyzed. Furthermore, in consideration of hardware implementation and decoding latency, a strategy, which allows many more checknodes to be updated in parallel, is introduced. Simulations show that the LDS with life-index speeds up the convergence rate and greatly improves the performance of the BP decoding at medium to high signal-to-noise ratio value, and the algorithm employing the LDS with life-index and the new strategy offers good trade-off between the performance and the decoding latency.     

A Non-Cyclic Prefixed SFBC-SCFDE System Based on a Recursive Algorithm of Joint Channel Estimation and Data Detection

We propose a non-cyclic prefixed Single carrier frequency-domain equalization （SCFDE） system with Space-frequency block codes （SFBC）. The transmitted signals in proposed system are composed of Singlecarrier （SC） information sequences derived from SFBC and training sequences, both of which have been placed in an alternate order without any Cyclic prefix （CP） before each SC information sequence. Furthermore, a recursire algorithm of Joint channel estimation and data detection （recursive-JCEDD） is proposed for system receiver. Simulation results show that the proposed non-cyclic prefixed SFBC-SCFDE system based on the recursive-JCEDD algorithm has better Bit error rate （BER） performance than traditional cyclic prefixed SFBC-SCFDE, Space-time block-coded SCFDE （STBC-SCFDE） and STBC-OFDM systems with some common channel estimation algorithms.     

THE Q-MATRIX LOW-DENSITY PARITY-CHECK CODES

This paper presents a matrix permuting approach to the construction of Low-Density Parity-Check （LDPC） code. It investigates the structure of the sparse parity-check matrix defined by Gallager. It is discovered that the problem of constructing the sparse parity-check matrix requires an algorithm that is efficient in search environments and also is able to work with constraint satisfaction problem. The definition of Q-matrix is given, and it is found that the queen algorithm enables to search the Q-matrix. With properly permuting Q-matrix as sub-matrix, the sparse parity-check matrix which satisfied constraint condition is created, and the good regular-LDPC code that is called the Q-matrix LDPC code is generated. The result of this paper is significant not only for designing low complexity encoder, improving performance and reducing complexity of iterative decoding arithmetic, but also for building practical system of encodable and decodable LDPC code.     

基于校验矩阵的卷积码识别和码字同步

简要介绍了卷积编码的矩阵描述及其生成矩阵和校验矩阵的关系,从中得出编码序列与校验矩阵之间的数学关系。从而提出了一种以卷积码的校验矩阵为先验知识的卷积码识别方法,利用卷积码的校验矩阵和编码序列的关系对通信侦察系统得到的数据流进行分析,实现对接收序列的编码方式识别和码同步,为进一步的解码工作创造了条件,并用仿真试验在无误码和有误码2种情况下分别验证了该方法的有效性。     

Relation Between Parity-Check Matrixes and Cycles of Associated Tanner Graphs

This correspondence presents an approach to the representation of cycles of Tanner graphs on associated parity-check matrices. Several equivalent conditions for the girth of a Tanner graph to be 2k are proposed. An algorithm to determine girth of associated Tanner graphs of parity-check matrices is proposed, also with an algorithm to count shortest cycles.     

An SEU-Tolerant Approach for Space-Borne Viterbi Decoders

In the space environment, Viterbi decoder implemented on SRAM-based FPGA is sensitive to Single event upsets （SEUs）, which may lead to functional failure of the decoder. Conventional SEU mitigation techniques like modular redundancy could not exploit the characters of Viterbi decoders, therefore could not provide optimized SEU tolerance when the device resource utilization cost is a constraint. Leveraging the properties of the decoding algorithm, three effective mitigation techniques are adopted, including structure optimization, Error detection and correction （EDAC） for Block RAM （BRAM） protection, and Partial triple-modular redundancy （PTMR）, which are applied to the modules of the decoder in accordance with their characteristics. Analysis of effectiveness shows that compared with unmitigated design, the SEU induced failure rate in the proposed SEU tolerant decoder can be reduced to 1/4 at the cost of 61.1% extra resource utilization. Error detec- tion and correction （EDAC）.     

Construction of Near-Optimum Burst Erasure Correcting Low-Density Parity-Check Codes

In this paper, a simple and effective tool for the design of low-density parity-check (LDPC) codes for iterative correction of bursts of erasures is presented. The design method consists of starting from the parity-check matrix of an LDPC code and developing an optimized parity-check matrix, with the same performance over the memoryless erasure channel, and suitable also for the iterative correction of single erasure bursts. The parity-check matrix optimization is performed by an algorithm called pivot searching and swapping (PSS) algorithm. It executes permutations of carefully chosen columns of the parity-check matrix, after a local analysis of particular variable nodes called stopping set pivots. This algorithm can be in principle applied to any LDPC code. If the input parity-check matrix is designed to achieve a good performance over the memoryless erasure channel, then the code obtained after the application of the algorithm provides a good joint correction of independent erasures and single erasure bursts. Numerical results are provided in order to show the algorithm effectiveness when applied to different categories of LDPC codes.     

Multiple-Rate Low-Density Parity-Check Codes with Constant Blocklength

This paper describes and analyzes low-density parity-check code families that support variety of different rates while maintaining the same fundamental decoder architecture. Such families facilitate the decoding hardware design and implementation for applications that require communication at different rates, for example to adapt to changing channel conditions. Combining rows of the lowest-rate parity-check matrix produces the parity-check matrices for higher rates. An important advantage of this approach is that all effective code rates have the same blocklength. This approach is compatible with well known techniques that allow low-complexity encoding and parallel decoding of these LDPC codes. This technique also allows the design of programmable analog LDPC decoders. The proposed design method maintains good graphical properties and hence low error floors for all rates.     

Quasi-Cyclic Low-Density Parity-Check Codes for Space-Time Bit-Interleaved Coded Modulation

In this letter, it is shown that the diversity order of space-time bit-interleaved coded modulation (ST-BICM) system is determined by the number of submatrices having linearly independent column vectors in a parity-check matrix of quasicyclic low-density parity-check (QC-LDPC) code. It is also proved that this diversity order can be derived from the base matrix of QC-LDPC code, which can make it easy to design QC-LDPC codes suitable for ST-BICM systems. Finally, the simulation results are provided to confirm the analytical results.     

Generalized Low-Density Parity-Check Codes Based on Hadamard Constraints

In this paper, we consider the design and analysis of generalized low-density parity-check (GLDPC) codes in AWGN channels. The GLDPC codes are specified by a bipartite Tanner graph, as with standard LDPC codes, but with the single parity-check constraints replaced by general coding constraints. In particular, we consider imposing Hadamard code constraints at the check nodes for a low-rate approach, termed LDPC-Hadamard codes. We introduce a low-complexity message-passing based iterative soft-input soft-output (SISO) decoding algorithm, which employs the a posteriori probability (APP) fast Hadamard transform (FHT) for decoding the Hadamard check codes at each decoding iteration. The achievable capacity with the GLDPC codes is then discussed. A modified LDPC-Hadamard code graph is also proposed. We then optimize the LDPC-Hadamard code ensemble using a low-complexity optimization method based on approximating the density evolution by a one-dimensional dynamic system represented by an extrinsic mutual information transfer (EXIT) chart. Simulation results show that the optimized LDPC-Hadamard codes offer better performance in the low-rate region than low-rate turbo-Hadamard codes, but also enjoy a fast convergence rate. A rate-0.003 LDPC-Hadamard code with large block length can achieve a bit-error-rate (BER) performance of 10^-5 at -1.44 dB, which is only 0.15 dB away from the ultimate Shannon limit (-1.592 dB) and 0.24 dB better than the best performing low-rate turbo-Hadamard codes     

基于校验方程平均符合度的Turbo码交织器估计

现有的交织器估计方法通常利用解调输出的硬判决序列进行,其容错能力有待提高,且一些方法只针对特定的交织器结构.针对Turbo码的随机交织器,提出一种利用接收软判决序列进行估计的算法.首先提出校验方程平均符合度的概念及计算方法,然后利用正确交织位置的码字可使得校验方程符合度取到最大值这一事实,逐步实现交织位置的估计.特别地,所提算法在删余条件下仍然有效.仿真结果表明,与现有的相关方法对比,特别是在低信噪比条件下,本文算法具有更好的性能以及相对低的复杂度.     

Quasi-Cyclic Low-Density Parity-Check Codes With Girth Larger Than 12

A quasi-cyclic (QC) low-density parity-check (LDPC) code can be viewed as the protograph code with circulant permutation matrices (or circulants). In this correspondence, we find all the subgraph patterns of protographs of QC LDPC codes having inevitable cycles of length 2i, i = 6, 7, 8, 9,10, i.e., the cycles that always exist regardless of the shift values of circulants. It is also derived that if the girth of the protograph is 2g, g > 2, its protograph code cannot have the inevitable cycles of length smaller than 6g. Based on these subgraph patterns, we propose new combinatorial construction methods of the protographs, whose protograph codes can have girth larger than or equal to 14 or 18. We also propose a couple of shift value assigning rules for circulants of a QC LDPC code guaranteeing the girth 14.     

REGULAR LOW-DENSITY PARITY-CHECK CODES BASED ON SHIFTED IDENTITY MATRICES

This paper extends the class of Low-Density Parity-Check （LDPC） codes that can be constructed from shifted identity matrices. To construct regular LDPC codes, a new method is proposed. Two simple inequations are adopted to avoid the short cycles in Tanner graph, which makes the girth of Tanner graphs at least 8. Because their parity-check matrices are made up of circulant matrices, the new codes are quasi-cyclic codes. They perform well with iterative decoding.     

Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices of Hamming Codes

Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.     

Nonlinear Programming Approaches to Decoding Low-Density Parity-Check Codes

We consider the decoding problem for low-density parity-check codes, and apply nonlinear programming methods. This extends previous work using linear programming (LP) to decode linear block codes. First, a multistage LP decoder based on the branch-and-bound method is proposed. This decoder makes use of the maximum-likelihood-certificate property of the LP decoder to refine the results when an error is reported. Second, we transform the original LP decoding formulation into a box-constrained quadratic programming form. Efficient linear-time parallel and serial decoding algorithms are proposed and their convergence properties are investigated. Extensive simulation studies are performed to assess the performance of the proposed decoders. It is seen that the proposed multistage LP decoder outperforms the conventional sum-product (SP) decoder considerably for low-density parity-check (LDPC) codes with short to medium block length. The proposed box-constrained quadratic programming decoder has less complexity than the SP decoder and yields much better performance for LDPC codes with regular structure.     

High-Rate Quasi-Cyclic Low-Density Parity-Check Codes Derived From Finite Affine Planes

This paper shows that several attractive classes of quasi-cyclic (QC) low-density parity-check (LDPC) codes can be obtained from affine planes over finite fields. One class of these consists of duals of one-generator QC codes. Presented here for codes contained in this class are the exact minimum distance and a lower bound on the multiplicity of the minimum-weight codewords. Further, it is shown that the minimum Hamming distance of a code in this class is equal to its minimum additive white Gaussian noise (AWGN) pseudoweight. Also discussed is a class consisting of codes from circulant permutation matrices, and an explicit formula for the rank of the parity-check matrix is presented for these codes. Additionally, it is shown that each of these codes can be identified with a code constructed from a constacyclic maximum distance separable code of dimension 2. The construction is similar to the derivation of Reed-Solomon (RS)-based LDPC codes presented by Chen and Djurdjevic Experimental results show that a number of high rate QC-LDPC codes with excellent error performance are contained in these classes     

Evaluation of the Undetected Error Probability of Single Parity-Check Product Codes

In this paper, an expression for the undetected error probability(Pepsilon)of single parity-check product (SPCP) codes used for error detection over a binary symmetric channel is derived. It is shown that square SPCP codes need not obey a certain commonly used bound. Approximate expressions for the maximum(Pepsilon)and the corresponding maximizing ε are given.     

Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R₁ and R₂ satisfying 012<1, there exists an ensemble of LDPC codes with the following property. The ensemble can be punctured from rate R₁ to R₂ resulting in asymptotically good codes for all rates R₁lesRlesR₂. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R₁2<1, the existence of the sequences of punctured LDPC codes that are capacity-achieving for all rates R₁ lesRlesR₂ is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels     

An 860-Mb/s (8158,7136) Low-Density Parity-Check Encoder

Low-density parity-check codes achieve coding performance which approaches the Shannon limit. An (8158,7136) encoder was implemented in a five-metal, 0.25-$muhbox m$CMOS process. Use of generator polynomial reconstruction, partial product multiplication and functional sharing in the parity register results in a highly efficient design. Only 1492 flip-flops along with a programmable 21-bit look-ahead scheme are used to achieve an 860-Mb/s data throughput for this rate 7/8 LDPC code. A comparable two-stage encoder requires 8176 flip-flops.