One of the most efficient approaches to improving the frame error rate (FER) performance of low-density parity-check (LDPC) codes is based on adding both auxiliary variable nodes (AVN) and the corresponding redundant parity checks (RPC) to the binary parity-check matrices of the code. It is known that for the LDPC codes, whose Tanner graphs contain length four cycles, this technique allows for substantial improvement in the FER performance of the belief-propagation (BP) decoding on the binary erasure channel (BEC) channel. The AVN-based technique followed by adding orthogonal redundant parity-checks is known to be efficient for both the BEC and additive white Gaussian noise (AWGN) channels. In this paper, firstly, the AVN-based approach is generalized to efficiently removing cycles of length larger than four. Secondly, the AVN-based technique is reformulated in terms of labeled base matrices of quasi-cyclic (QC) LDPC codes. An improved iterative decoding of QC LDPC codes is proposed, which is applied to the labeled base matrices of QC LDPC codes extended by the AVN-RPC technique.
One of the most efficient approaches to improving the frame error rate (FER) performance of low-density parity-check (LDPC) codes is based on adding both auxiliary variable nodes (AVN) and the corresponding redundant parity checks (RPC) to the binary parity-check matrices of the code. It is known that for the LDPC codes, whose Tanner graphs contain length four cycles, this technique allows for substantial improvement in the FER performance of the belief-propagation (BP) decoding on the binary erasure channel (BEC) channel. The AVN-based technique followed by adding orthogonal redundant parity-checks is known to be efficient for both the BEC and additive white Gaussian noise (AWGN) channels. In this paper, firstly, the AVN-based approach is generalized to efficiently removing cycles of length larger than four. Secondly, the AVN-based technique is reformulated in terms of labeled base matrices of quasi-cyclic (QC) LDPC codes. An improved iterative decoding of QC LDPC codes is proposed, which is applied to the labeled base matrices of QC LDPC codes extended by the AVN-RPC technique.
Low-density parity-check (LDPC) codes have been one of the most popular error correction candidates in modern communication and data storage systems for the past three decades due to their capacity-approaching error correction capability under the Belief Propagation (BP) decoding algorithms. In this dissertation, we investigate three topics related to efficient and effective decoding algorithms and the code design of LDPC codes. In the first part of this dissertation, we propose a methodology with the help of artificial intelligence to design Finite Alphabet Iterative Decoders (FAID) for LDPC codes, which are not only of great theoretical but also practical importance. This model-driven neural network (NN) framework unfolds the decoding iterations, introduces quantized neural networks (QNN) to model the FAIDs, and proposes a new cost function, namely, bit error rate (BER), to address the inefficiency in discrete-output channel scenarios. The low precision activations in the QNN and quantization in the cost functions cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We design and leverage straight-through estimators as surrogate gradients to tackle this issue and provide a joint training scheme. These QNN-aided FAIDs, are capable of surpassing the floating-point BP algorithms, with much lower complexity and faster convergence. The QNN-aided approach is general, as it can be applied to both continuous and discrete-output channels. In the second part of this dissertation, we propose a new code construction of LDPC codes based on the conventional parity-check matrices of Reed-Solomon (RS) codes. We investigate the girth and cycle structure and introduce an efficient searching algorithm to reduce short cycles in their Tanner graphs and to construct LDPC codes with a girth of at least eight. We use masking to further reduce the number of short cycles and to adjust the column and row weights of the parity-check matrices of the constructed codes for performance improvement. Our designs are systematic and flexible, which balance the requirements of good waterfall performance and low error-floor while maintaining a structure that facilitates implementation. In the third part of this dissertation, we investigate binary quasi-cyclic (QC) LDPC codes and their capability to correct phased bursts of erasures. We prove that the peeling algorithm when applied to such parity-check matrices of column weight two can correct all erasures that can be corrected by a maximum likelihood (ML) decoder. We show that by modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. For the Additive White Gaussian Noise (AWGN) channel, we design QC LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel. Our analysis of QC-LDPC codes with parity-check matrices of column weight two is rather comprehensive as we determine, for all such codes, their dimensions, minimum Hamming distances, and their capabilities to correct phased bursts.
It is widely accepted that short cycles in Tanner graphs deteriorate the performance of message-passing algorithms. This discourages the use of these algorithms on Tanner graphs (TGs) of well-known algebraic codes such as Hamming codes, Bose-Chaudhuri-Hocquenghem codes, and Reed-Solomon codes. Yedidia et al. presented a method to generate code representations suitable for message-passing algorithms. This method does not guarantee a representation free of four-cycles. In this correspondence, we present an algorithm to convert an arbitrary linear block into a code with orthogonal parity-check equations. A combinatorial argument is used to prove that the algorithm guarantees a four-cycle free representation for any linear code. The effects of removing four-cycles on the performance of a belief propagation decoder for the binary erasure channel are studied in detail by analyzing the structures in different representations. Finally, we present bit-error rate (BER) and block-error rate (BLER) performance curves of linear block codes under belief propagation algorithms for the binary erasure channel and the additive white Gaussian noise (AWGN) channel in order to demonstrate the improvement in performance achieved with the help of the proposed algorithm.
Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.
Many recently proposed Calderbank-Shor-Steane (CSS) quantum low-density parity-check (QLDPC) codes have sparse decoding graphs, enabling syndrome-based belief propagation (BP) decoding at low complexity. Their construction, however, often results in properties that impair BP performance, such as short cycles and degeneracy. In this work, we propose a general framework for introducing auxiliary variable nodes (AVNs) and auxiliary check nodes (ACNs) into the decoding graph of CSS codes, compatible with the standard stabilizer measurement framework. This provides an additional degree of freedom in the design of the decoding graph itself and can be used to tackle the aforementioned shortcomings. We show that recently proposed techniques, 4-cycle removal and subcode ensemble decoding, can be interpreted as instances of this framework. For 4-cycle removal, we find that the gains depend strongly on the BP iteration count and check-node message scaling. Building on this framework, we further propose a graph-derived subcode ensemble decoder and demonstrate under circuit-level noise that it substantially reduces the per-round logical error rate compared with BP on the corresponding 4-cycle-free decoding graph.
A novel construction algorithm for quasi-cyclic low-density parity-check codes is proposed,with which we can obtain the improved girth of the corresponding Tanner graph by generalizing Yang et al.'s constraint for any cycle detected in the base matrix to detect and break the cycles in the parity check matrix.Compared with the existing cycle elimination(CE) algorithm,a better error performance can be achieved and cycle-8 free.Simulation results show that the proposed algorithm for constructing the irregular LDPC code of rate 1/2 achieves the performance of codeword error rate of 2×10-6at Eb/N0=1.5dB with 80 iterations by the belief-propagation decoding algorithm.
Gallager proposed and developed low density parity check (LDPC) codes in the early 1960s. LDPC codes were rediscovered in the early 1990s and shown to be capacity approaching over the additive white Gaussian noise (AWGN) channel. Subsequently, density evolution (DE) optimized symbol node degree distributions were used to significantly improve the decoding performance of short to medium length irregular LDPC codes. Currently, the short to medium length LDPC codes with the lowest error floor are DE optimized irregular LDPC codes constructed using progressive edge growth (PEG) algorithm modifications which are designed to increase the approximate cycle extrinsic message degrees (ACE) in the LDPC code graphs constructed. The aim of the present work is to find efficient means to improve on the error floor performance published for short to medium length irregular LDPC codes over AWGN channels in the literature. An efficient algorithm for determining the girth and ACE distributions in short to medium length LDPC code Tanner graphs has been proposed. A cyclic PEG (CPEG) algorithm which uses an edge connections sequence that results in LDPC codes with improved girth and ACE distributions is presented. LDPC codes with DE optimized/’good’ degree distributions which have larger minimum distances and stopping distances than previously published for LDPC codes of similar length and rate have been found. It is shown that increasing the minimum distance of LDPC codes lowers their error floor performance over AWGN channels; however, there are threshold minimum distances values above which there is no further lowering of the error floor performance. A minimum local girth (edge skipping) (MLG (ES)) PEG algorithm is presented; the algorithm controls the minimum local girth (global girth) connected in the Tanner graphs of LDPC codes constructed by forfeiting some edge connections. A technique for constructing optimal low correlated edge density (OED) LDPC codes based on modified DE optimized symbol node degree distributions and the MLG (ES) PEG algorithm modification is presented. OED rate-½ (n, k)=(512, 256) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. Similarly, consequent to an improved symbol node degree distribution, rate ½ (n, k)=(1024, 512) LDPC codes have been shown to have lower error floor over the AWGN channel than previously published for LDPC codes of similar length and rate. An improved BP/SPA (IBP/SPA) decoder, obtained by making two simple modifications to the standard BP/SPA decoder, has been shown to result in an unprecedented generalized improvement in the performance of short to medium length irregular LDPC codes under iterative message passing decoding. The superiority of the Slepian Wolf distributed source coding model over other distributed source coding models based on LDPC codes has been shown.