Abstract Given a linear block code on a BSC channel, and arbitrary pre-determined information about the coset of each possible received sequence, a method is given for construction of a new kind of parity check matrix that carries the given information. This pre-determined coset data is easily reconstructed by a simple decoder. When this coset information is related to coset leader weight, there is simple iterative gradient descent algorithm that is optimal, provably accurate and potentially of low complexity. An explicit gradient function construction is given for an code for which pseudo-codewords obstruct LDPC decoding convergence. 1 Introduction Many communication channels accept as input binary strings and return output strings of the same length that have been altered and whose terms can be interpreted as "the probability that 1 was sent in this position. " This paper is restricted to the binary symmetric channel (BSC) for which the output is also binary although the basic ideas seem to apply more generally. The task of a decoding algorithm is to reconstruct sent message(s) from the channel output. There are several critical attributes of a decoding algorithm. The design complexity is a measure of the effort required to design and implement an instance of the algorithm. The implementation cost is a measure of the (time and space) resources required to decode messages once the algorithm is implemented. The apparent accuracy of an algorithm is a measure of its ability to actually identify a nearest codeword to a given message in practice. The proven accuracy is a measure of the algorithm's proven ability to correctly move from message to nearest codeword without failure of any kind. A decoding algorithm is optimal if it correctly identifies the most likely channel error for each channel output for which there is a unique such error.
Abstract Given a linear block code on a BSC channel, and arbitrary pre-determined information about the coset of each possible received sequence, a method is given for construction of a new kind of parity check matrix that carries the given information. This pre-determined coset data is easily reconstructed by a simple decoder. When this coset information is related to coset leader weight, there is simple iterative gradient descent algorithm that is optimal, provably accurate and potentially of low complexity. An explicit gradient function construction is given for an code for which pseudo-codewords obstruct LDPC decoding convergence. 1 Introduction Many communication channels accept as input binary strings and return output strings of the same length that have been altered and whose terms can be interpreted as "the probability that 1 was sent in this position. " This paper is restricted to the binary symmetric channel (BSC) for which the output is also binary although the basic ideas seem to apply more generally. The task of a decoding algorithm is to reconstruct sent message(s) from the channel output. There are several critical attributes of a decoding algorithm. The design complexity is a measure of the effort required to design and implement an instance of the algorithm. The implementation cost is a measure of the (time and space) resources required to decode messages once the algorithm is implemented. The apparent accuracy of an algorithm is a measure of its ability to actually identify a nearest codeword to a given message in practice. The proven accuracy is a measure of the algorithm's proven ability to correctly move from message to nearest codeword without failure of any kind. A decoding algorithm is optimal if it correctly identifies the most likely channel error for each channel output for which there is a unique such error.
We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not equal to the transmitted codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which generates an error vector called the BSC-instanton. We prove that: (a) the LP decoder fails for any error pattern with support that is a superset of the support of an instanton; (b) for any input, the ISA outputs an instanton in the number of steps upper-bounded by twice the number of errors in the input error vector. We then find the number of unique instantons of different sizes for a given LDPC code by running the ISA sufficient number of times.
This chapter discusses recent advances in modern coding theory, in particular the use of popular graph-based codes and their low complexity decoding algorithms. We describe absorbing sets as the key object for characterizing the performance of iteratively-decoded graph-based codes and we propose several directions for future investigation in this thriving discipline. Chapter Overview Every engineered communication system, ranging from satellite communications to hard disk drives to Ethernet must operate under noisy conditions. The key to reliable communication and storage is to add an appropriate amount of redundancy to make the system reliable. The field of channel coding is concerned with constructing channel codes and their decoding algorithms: controlled redundancy is introduced into a message prior to its transmission over a noisy channel (the encoding step), and this redundancy is removed from the received noisy string to unveil the intended message (the decoding step). The encoded message is referred to as the codeword. The collection of all codewords is a channel code. Assuming all the messages have the same length, and all the codewords have the same length, the ratio of message length to codeword length is the code rate. To make coding systems implementable in practice, channel codes must provide the best possible protection to noise while their decoding algorithms must be of acceptable complexity. There is a clear tension with this dual goal: if a channel code protects a fairly long encoded message with relatively few but carefully derived redundancy bits (necessary for high performance), the optimal, maximum likelihood decoding algorithm has exponential complexity.
The optimal performance-complexity tradeoff for error-correcting codes at rates strictly below the Shannon limit is a central question in coding theory. This paper proposes a numerical approach for the minimization of decoding complexity for long-block-length irregular low-density parity-check (LDPC) codes. The proposed design methodology is applicable to any binary-input memoryless symmetric channel and any iterative message-passing decoding algorithm with a parallel-update schedule. A key feature of the proposed optimization method is a new complexity measure that incorporates both the number of operations required to carry out a single decoding iteration and the number of iterations required for convergence. This paper shows that the proposed complexity measure can be accurately estimated from a density-evolution and extrinsic-information transfer chart analysis of the code. A sufficient condition is presented for convexity of the complexity measure in the variable edge-degree distribution; when it is not satisfied, numerical experiments nevertheless suggest that the local minimum is unique. The results presented herein show that when the decoding complexity is constrained, the complexity-optimized codes significantly outperform threshold-optimized codes at long block lengths, within the ensemble of irregular codes.
We consider the problem of decoding a linear block code used over a binary symmetric channel with crossover probability p when the goal of the decoding is to minimize the probability of an information bit error. In general, there will be several different decoding strategies, each corresponding to the optimal rule over some range p/spl isin/[p/sub i-1/, p/sub i/]. Each of these strategies can be implemented by standard array with the appropriate choice of coset leaders that are not in general of minimum weight. We give optimal rules for selecting coset leaders in the first region [0, p/sub 1/] and the region [p/sub max/, 1/2] for any linear mapping between information bits and codewords. The determination of the optimal rule has been an open problem for small p. The rule for p>p/sub max/ is important because for many codes, when p is fixed the optimal rule for any coset corresponds to either the optimal rule for small p, or the optimal rule for p near 1/2. The optimal decoding strategy varies with the generator matrix used in general, but it is demonstrated that the optimal generator matrix is separable when d/sup /spl perp//>2. The results are shown to extend in a natural way to the case where the goal is to minimize the probability that arbitrary collections of information bits are in error. We examine some specific codes, and compare the performance under optimal decoding to the performance of previously suggested strategies.>
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.
The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.