Reduced complexity iterative decoding of low-density parity checkcodes based on belief propagation

Two simplified versions of the belief propagation algorithm for fast iterative decoding of low-density parity check codes on the additive white Gaussian noise channel are proposed. Both versions are implemented with real additions only, which greatly simplifies the decoding complexity of belief propagation in which products of probabilities have to be computed. Also, these two algorithms do not require any knowledge about the channel characteristics. Both algorithms yield a good performance-complexity trade-off and can be efficiently implemented in software as well as in hardware, with possibly quantized received values     

Iterative reliability-based decoding in bandwidth efficient coding schemes

In this paper, we enhance and investigate the performance of some bandwidth efficient coding schemes with iteratively decodable structure and cycles in their graph representation. In particular, we deal with bit-interleaved coded modulation and transmit diversity, using low-density parity-check and turbo codes as component codes. Simulation results show that the suboptimality of iterative decoding for moderate length codes can be at least partially compensated. Hence they allow us to also measure partially this suboptimality.     

Iterative reliability-based decoding of linear block codes with adaptive belief propagation

In this letter, an iterative decoding algorithm for linear block codes combining reliability-based decoding with adaptive belief propagation decoding is proposed. At each iteration, the soft output values delivered by the adaptive belief propagation algorithm are used as reliability values to perform reduced order reliability-based decoding of the code considered. This approach allows to bridge the gap between the error performance achieved by the lower order reliability-based decoding algorithms which remain sub-optimum, and the maximum likelihood decoding, which is too complex to be implemented for most codes employed in practice. Simulations results for various linear block codes are given and elaborated.     

Iterative decoding of low-density Parity-check codes over compound channels

We present a setting for decoding of low-density parity-check (LDPC) codes jointly with channel estimation, which is suitable for transmission over memoryless compound channels. We show that the performance of the combined scheme can be rigorously evaluated by means of density evolution, and focus on density evolution as a tool for designing a channel estimator that matches not only to the channel, but also to the LDPC ensemble, as well. The utility of the concept is exemplified for a compound binary symmetric channel and an unknown phase additive white Gaussian channel.     

Sequential decoding of low-density parity-check codes by adaptivereordering of parity checks

Decoding algorithms in which unpruned codeword trees are generated from an ordered list of parity checks are investigated. The order is computed from the received message, and low-density parity-check codes are used to help control the growth of the tree. Simulation results are given for the binary erasure channel. They suggest that for the small erasure probability, the method is computationally feasible at rates above the computational cutoff rate     

Iterative decoding of parallel and serial concatenated single parity check product codes

An efficient, iterative soft-in-soft-out decoding scheme is employed for the parallel and serially concatenated single parity check (SPC) product codes, which has very low complexity, requiring only two addition-equivalent-operations per information bit. For a rate 0.8637 of parallel concatenated SPC product code, a performance of BER=10/sup -5/ at E/sub b//N/sub 0/=3.66 dB can be achieved using this decoding scheme, which is within 1 dB from the Shannon limit.     

性能接近最优的LDPC码LLR-BP简化译码算法

讨论了LDPC码的LLR-BP译码算法,对多项式拟合和偏移量近似两种简化算法进行了研究,通过仿真的方法确定了近似参数;算法仿真结果表明,这两种简化算法不仅易于硬件实现,而且性能接近最优。     

Iterative sequential decoding

It is shown that use of a two-stage decoding procedure consisting simply of an inner stage of block decoding and an outer stage employing a single sequential decoder does not result in an improvement in the computational overflow problem for the sequential decoder. Improvement can, however, result from use of multiple sequential decoders or use of a single sequential decoder with appropriate scrambling. Although the performance improvement resulting from application of these techniques to the additive white Gaussian noise channel is not significant, implementation and rate advantages make iterative sequential decoding techniques worth pursuing. Ia particular, with these techniques, a sequential decoder for a binary symmetric channel can be used regardless of the physical channel characteristics. Such a "universal" decoder is expected to be both simple and capable of high rate operation.     

Bootstrap decoding of low-density parity-check codes

An initial bootstrap step for the decoding of low-density parity-check (LDPC) codes is proposed. Decoding is initiated by first erasing a number of less reliable bits. New values and reliabilities are then assigned to erasure bits by passing messages from nonerasure bits through the reliable check equations. The bootstrap step is applied to the weighted bit-flipping algorithm to decode a number of LDPC codes. Large improvements in both performance and complexity are observed.     

An iterative reliability-based decoding for LDPC coded modulation system

In this paper, A Belief Propagation concatenated Orderd-Statistic Decoder （BP-OSD） based on accumulated Log-Likelihood Ratio （LLR） is proposed for medium and short lengths Low Density Parity-Check （LDPC） codes coded Bit-Interleaved Coded Modulation （BICM） systems. The accumulated soft output values delivered by every BP iteration are used as reliability values of Soft-Input Soft-Output OSD （SISO-OSD） decoder and the soft output of SISO-OSD is used as a priori probabilities of the demodulator for the next iteration. Simulation results show that this improved algorithm achieves noticeable performance gain with only modest increase in computation complexity.     

Iterative soft decoding of Reed-Solomon codes

This letter presents an iterative decoding method for Reed-Solomon (RS) codes. The proposed algorithm is a stochastic shifting based iterative decoding (SSID) algorithm which takes advantage of the cyclic structure of RS codes. The performances of different updating schemes are compared. Simulation results show that this method provides significant gain over hard decision decoding and is superior to some other popular soft decision methods for short RS codes.     

Reduced-complexity decoding algorithm for low-density parity-checkcodes

A new reduced-complexity decoding algorithm for low-density parity-check codes that operates entirely in the log-likelihood domain is presented. The computationally expensive check-node updates of the sum-product algorithm are simplified by using a difference-metric approach on a two-state trellis and by employing the dual-max approximation. The dual-max approximation is further improved by using a correction factor that allows the performance to approach that of full sum-product decoding     

Soft-bit decoding of regular low-density parity-check codes

A novel representation, using soft-bit messages, of the belief propagation (BP) decoding algorithm for low-density parity-check codes is derived as an alternative to the log-likelihood-ratio (LLR)-based BP and min-sum decoding algorithms. A simple approximation is also presented. Simulation results demonstrate the functionality of the soft-bit decoding algorithm. Floating-point soft-bit and LLR BP decoding show equivalent performance; the approximation incurs 0.5-dB loss, comparable to min-sum performance loss over BP. Fixed-point results show similar performance to LLR BP decoding; the approximation converges to floating-point results with one less bit of precision.     

Verification-based decoding for packet-based low-density parity-check codes

We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units. Verification-based decoding requires only linear time for both encoding and decoding and succeeds with high probability under random errors. We describe how to utilize code scrambling to extend our results to channels with errors controlled by an oblivious adversary.     

Replica horizontal-shuffled iterative decoding of low-density parity-check codes

For practical considerations, it is essential to accelerate the convergence speed of the decoding algorithm used in an iterative decoding system. In this paper, replica versions of horizontal-shuffled decoding algorithms for low-density parity-check (LDPC) codes are proposed to improve the convergence speed of the original versions. The extrinsic information transfer (EXIT) chart technique is extended to the proposed algorithms to predict their convergence behavior. Both EXIT chart analysis and numerical results show that replica plain horizontal-shuffled (RPHS) decoding converges much faster than both plain horizontal-shuffled (PHS) decoding and the standard belief-propagation (BP) decoding. Furthermore, it is also revealed that replica group horizontal-shuffled (RGHS) decoding can increase the parallelism of RPHS decoding as well as preserve its high convergence speed if an equivalence condition is satisfied, and is thus suitable for hardware implementation.     

Deterministic π-rotation low-density parity check codes

An ensemble of 'π-rotation' low-density parity check codes, extending the result in previously reported work by a different team of authors, is introduced. The key features of these codes are a deterministic matrix based on a single permutation vector defined by three integers, good performance with the proper choice of integers and simple circuit implementation     

A novel soft reliability-based iterative majority-logic decoding algorithm with uniform quantization

In this paper, a novel soft reliability-based iterative majority-logic decoding algorithm with uniform quantization is proposed for regularly structured low density parity-check (LDPC) codes. A weighted measure is introduced for each check-sum of the parity-check matrix and a scaling factor is used to weaken the overestimation of extrinsic information. Furthermore, the updating process of the reliability measure takes advantage of turbo-like iterative decoding strategy. The main computational complexity of the proposed algorithm only includes logical and integer operations with the bit uniform quantization criterion. Simulation results show that the novel decoding algorithm can achieve excellent error-correction performance and a fast decoding convergence speed. This work has been supported by the National Natural Science Foundation of China (Nos.61472464, 61671091 and 61471075), the Natural Science Foundation of Chongqing Science and Technology Commission (No.cstc2015jcyjA0554), the Program for Innovation Team Building at Institutions of Higher Education in Chongqing (No.J2013-46), and the Undergraduate Science Research Training Project for Chongqing University of Posts and Telecommunications (No.A2016-61). E-mail:yuanjg@cqupt.edu.cn      

The capacity of low-density parity-check codes undermessage-passing decoding

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined