This paper considers the performance of (j, k)-regular low-density parity-check (LDPC) codes with message-passing (MP) decoding algorithms in the high-rate regime. In particular, we derive the high-rate scaling law for MP decoding of LDPC codes on the binary erasure channel (BEC) and the q-ary symmetric channel (q-SC). For the BEC and a fixed j, the density evolution (DE) threshold of iterative decoding scales like Θ(k-1) and the critical stopping ratio scales like Θ(k-j/(j-2)). For the q-SC and a fixed j, the DE threshold of verification decoding depends on the details of the decoder and scales like Θ(k-1) for one decoder. Using the fact that coding over large finite alphabets is very similar to coding over the real numbers, the analysis of verification decoding is also extended to the compressed sensing (CS) of strictly sparse signals. A DE-based approach is used to analyze the CS systems with randomized-reconstruction guarantees. This leads to the result that strictly sparse signals can be reconstructed efficiently with high probability using a constant oversampling ratio (i.e., when the number of measurements scales linearly with the sparsity of the signal). A stopping-set-based approach is also used to get stronger (e.g., uniform-in-probability) reconstruction guarantees.

A new verification-based message-passing decoder for low-density parity-check (LDPC) codes is introduced and analyzed for the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, this decoder passes lists of possible symbols and marks some lists as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list size is unbounded, then one finds that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q -SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. Simulation results are also presented to confirm the DE results. During the simulations, we observed differences between two verification-based decoding algorithms, introduced by Luby and Mitzenmacher, that were implicitly assumed to be identical. In this paper, the node-based algorithms are evaluated via analysis and simulation. The probability of false verification (FV) is also considered and techniques are discussed to mitigate the FV. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.

An LDPC code is proposed for flash memories based on rank modulation. In contrast to previous approaches, this enables the use of long ECCs with fixed-length modulation codes. For ECC design, the rank modulation scheme is treated as part of an equivalent channel. A probabilistic model of the equivalent channel is derived and a simple high-SNR approximation is given. LDPC codes over integer rings and finite fields are designed for the approximate channel and a low-complexity symbol-flipping verification-based (SFVB) message-passing decoding algorithm is proposed to take advantage of the channel structure. Density evolution (DE) is used to calculate decoding thresholds and simulations are used to compare the low-complexity decoder with sum-product decoding.

We discuss and analyze a list-message-passing decoder with verification for low-density parity-check (LDPC) codes on the q-ary symmetric channel (q-SC). Rather than passing messages consisting of symbol probabilities, we pass lists of possible symbols and mark very likely symbols as verified. The density evolution (DE) equations for this decoder are derived and used to compute decoding thresholds. If the maximum list-size is unbounded, then we find that any capacity-achieving LDPC code for the binary erasure channel can be used to achieve capacity on the q-SC for large q. The decoding thresholds are also computed via DE for the case where each list is truncated to satisfy a maximum list-size constraint. The probability of false verification is considered for this case, and techniques are discussed to mitigate the problem. Optimization of the degree distribution is also used to improve the threshold for a fixed maximum list size. Finally, the proposed algorithm is compared with a variety of other algorithms using both density evolution thresholds and simulation results.