Belief-Propagation-Approximated Decoding of Low-Density Parity-Check Codes

In this paper, we propose a new reduced-complexity decoding algorithm of Low-Density Parity-Check (LDPC) codes, called Belief-Propagation-Approximated (BPA) algorithm, which utilizes the idea of normalization and translates approximately the intricate nonlinear operation in the check nodes of the original BP algorithm to only one operation of looking up the table. The normalization factors can be obtained by simulation, or theoretically. Simulation results demonstrate that BPA algorithm exhibits fairly satisfactory bit error performance on the Additive White Gaussian Noise (AWGN) channel.     

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.     

Low-Density Parity-Check Codes with 2-State Trellis Decoding

A class of low-density parity-check (LDPC) codes with a simple 2-state trellis structure is presented. For LDPC decoding, the conventional belief propagation (BP) algorithm consists of numerous sub-decoders of single-parity check codes and exchanges information between sub-decoders in an iterative manner. If the single-parity check codes can be constructed and grouped in a proper way, the decoder can be decomposed into few identical 2-state trellis decoders. Therefore, instead of numerous sub-decoders of single-parity check codes, an iterative decoding algorithm based on few sub-decoders over 2-state trellis is proposed. The proposed decoding algorithm improves the efficiency of message passing between sub-decoders and hence provides a fast convergent rate as compared to the standard BP algorithm. Simulation results show that the proposed scheme provides a better performance and a fast convergent rate as compared to those of standard BP algorithm. The result also shows that the proposed algorithm has a similar performance as that of asynchronous replica shuffled BP algorithm and has a slightly inferior performance than that of synchronous replica shuffled BP algorithm. However, complexity analysis shows that our proposed algorithm has complexity that is lower than that of the replica shuffled BP algorithm.     

Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes

Time-invariant hybrid (Hscr_TI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on Hscr_TI algorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB Hscr_TI algorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB Hscr_TI algorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB Hscr_TI algorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive     

Hybrid Iterative Decoding for Low-Density Parity-Check Codes Based on Finite Geometries

In this letter, a two-stage hybrid iterative decoding algorithm which combines two iterative decoding algorithms is proposed to reduce the computational complexity of finite geometry low-density parity-check (FG-LDPC) codes. We introduce a fast weighted bit-flipping (WBF) decoding algorithm for the first stage decoding. If the first stage decoding fails, the decoding is continued by the powerful belief propagation (BP) algorithm. The proposed hybrid decoding algorithm greatly reduces the computational complexity while maintains the same performance compared to that of using the BP algorithm only.     

Reversible Low-Density Parity-Check Codes

Low-density parity-check (LDPC) codes may be decoded using a circuit implementation of the sum-product algorithm which maps the factor graph of the code. By reusing the decoder for encoding, both tasks can be performed using the same circuit, thus reducing area and verification requirements. Motivated by this, iterative encoding techniques based upon the graphical representation of the code are proposed. Code design constraints which ensure encoder convergence are presented, and then used to design iteratively encodable codes, while also preventing 4-cycle creation. We show how the Jacobi method for iterative matrix inversion can be applied to finite field matrices, viewed as message passing, and employed as the core of an iterative encoder. We present an algebraic construction of 4-cycle free iteratively encodable codes using circulant matrices. Analysis of these codes identifies a weakness in their structure, due to a repetitive pattern in the factor graph. The graph supports pseudo-codewords of low pseudo-weight. In order to remove the repetitive pattern in the graph, we propose a recursive technique for generating iteratively encodable codes. The new codes offer flexibility in the choice of code length and rate, and performance that compares well to randomly generated, quasi-cyclic and extended Euclidean-geometry codes.     

Fast Weighted Bit Flipping Algorithm for Higher-Speed Decoding of Low-Density Parity-Check Codes

Because of the speed limitation of the conventional bit-selection strategy in the exi- sting weighted bit flipping algorithms, a high- speed Low-Density Parity-Check （LDPC） dec- oder cannot be realised. To solve this problem, we propose a fast weighted bit flipping algo- rithm. Specifically, based on the identically dis- tributed error bits, a parallel bit-selection met- hod is proposed to reduce the selection delay of the flipped bits. The delay analysis demon- strates that, the decoding speed of LDPC codes can be significantly improved by the proposed algorithm. Furthermore, simulation results ver- ify the validity of the proposed algorithm.     

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     

Clockless Stochastic Decoding of Low-Density Parity-Check Codes: Architecture and Simulation Model

This paper introduces clockless stochastic decoding for high-throughput low-density parity-check (LDPC) decoders. Stochastic computation provides ultra-low-complexity hardware using simple logic gates. Clockless decoding eliminates global clocking, which eases the worst-case timing restrictions of synchronous stochastic decoders. The lack of synchronization might use outdated bits to update outputs in computation nodes; however, it does not significantly affect output probabilities. A timing model of clockless-computation behaviours under a 90 nm CMOS technology is used to simulate the BER performance of the proposed decoding scheme. Based on our models, the proposed decoding scheme significantly reduces error floors due to the “lock-up” problem and achieves superior BER performance compared with conventional synchronous stochastic decoders. The timing model includes metastability to verify the affect on BER performance.     

Weight Distribution of Low-Density Parity-Check Codes

We derive the average weight distribution function and its asymptotic growth rate for low-density parity-check (LDPC) code ensembles. We show that the growth rate of the minimum distance of LDPC codes depends only on the degree distribution pair. It turns out that capacity-achieving sequences of standard (unstructured) LDPC codes under iterative decoding over the binary erasure channel (BEC) known to date have sublinearly growing minimum distance in the block length     

Low Complexity Decoder Architecture for Low-Density Parity-Check Codes

In this paper, we propose a low complexity decoder architecture for low-density parity-check (LDPC) codes using a variable quantization scheme as well as an efficient highly-parallel decoding scheme. In the sum-product algorithm for decoding LDPC codes, the finite precision implementations have an important tradeoff between decoding performance and hardware complexity caused by two dominant area-consuming factors: one is the memory for updated messages storage and the other is the look-up table (LUT) for implementation of the nonlinear function Ψ(x). The proposed variable quantization schemes offer a large reduction in the hardware complexities for LUT and memory. Also, an efficient highly-parallel decoder architecture for quasi-cyclic (QC) LDPC codes can be implemented with the reduced hardware complexity by using the partially block overlapped decoding scheme and the minimized power consumption by reducing the total number of memory accesses for updated messages. For (3, 6) QC LDPC codes, our proposed schemes in implementing the highly-parallel decoder architecture offer a great reduction of implementation area by 33% for memory area and approximately by 28% for the check node unit and variable node unit computation units without significant performance degradation. Also, the memory accesses are reduced by 20%.     

Efficient Puncturing Method for Rate-Compatible Low-Density Parity-Check Codes

In this paper, we propose an efficient puncturing method for LDPC codes. The proposed algorithm provides the order of variable nodes for puncturing based on the proposed cost function. The proposed cost function tries to maximize the minimum reliability among those provided from all check nodes. Also, it tries to allocate survived check nodes evenly to all punctured variable nodes. Furthermore, the proposed algorithm prevents the formation of a stopping set from the punctured variable nodes even when the amount of puncturing is quite large. Simulation results show that the proposed punctured LDPC codes perform better than existing punctured LDPC codes.     

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates     

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.     

Termination Sequence Generation Circuits for Low-Density Parity-Check Convolutional Codes

Low-density parity-check convolutional codes (LDPC-CCs) complement their popular block-oriented counterparts and may be more suitable in certain communication applications. These include streaming voice, video, and packet switching networks. In order to use these codes efficiently we must generate termination sequences similar to those used in conventional convolutional codes. In this paper, we present a construction method for termination sequence generation circuits suitable for field-programmable gate arrays and application-specific integrated circuits. This method uses linear algebra to determine the termination sequence for a small number of states of the encoder and converts these solutions into a sequential circuit. Results are presented for several realizations of termination circuits for a (128,3,6) LDPC-CC.     

Architecture of Generalized Bit-Flipping Decoding for High-Rate Non-binary LDPC Codes

A VLSI architecture for the generalized bit-flipping decoding algorithm for non-binary low-density parity-check codes is proposed in this paper. The tentative decoding steps of the algorithm have been modified to avoid computing and storing a matrix of dimension N×2 ^q , for a code (N,K) over GF(2 ^q ), reducing its complexity with a minimal penalization of its performance, less than 0.05 dB compared with the original algorithm. The architecture was synthesized using a 90 nm standard cell library, for the (837,723) non-binary code over GF(2⁵), requiring 590220 xor gates and achieving a throughput of 89 Mbps. Additionally, it was implemented in a Virtex-VI FPGA device with a cost of 4070 slices and a throughput of 44.6 Mbps.     

LDPC码在QPSK调制下的应用分析

对低密度奇偶校验码(LDPC)在QPSK调制下的对数似然比(LLR)算法进行了深入研究,分析了LDPC码在QPSK调制下初始消息的计算方法,推导了初始消息的计算公式。同时对该算法进行了程序仿真,仿真结果表明LDPC码在QPSK调制中具有良好的性能。当信噪比为3.5 dB时,误码率可达到10-6数量级。     

一种改进的自纠正最小和LDPC码的译码算法

低密度奇偶校验(LDPC)码是一类具有优良纠错能力的差错控制编码,可以逼近香农极限.目前LDPC码正在进入越来越多的工程应用中,高效的译码算法具有重要的价值.在研究已知的LDPC码译码算法的基础上,提出了一种改进的简化译码算法,称为加约束的自纠正最小和(CSCMS)算法,该算法的计算复杂度与最小和(MS)译码算法相当,性能却提升了0.2 dB左右,与其他几种改进的简化译码算法相比,性能提升约0.1 dB,并且译码的平均迭代次数也有所降低.