This paper develops a paradigm for optimizing progressive reads for flash memory cells that maximize the conditional mutual information (MI) given previous reads and shows that some progressive reads provide substantially more MI than others. We study two flash storage techniques: 1) the common practice of independently encoding each bit of a cell into a separate codeword and 2) jointly encoding all the bits in the cell into the same codeword. We quantify the MI gap between joint and independent encoding and show that this gap becomes negligible when progressive reads are available. The paper provides LDPC simulations that confirm the MI analysis.

Variable-length (VL) coding with feedback is a commonly used technique that can approach point-to-point Shannon channel capacity with a significantly shorter average codeword length than fixed-length coding without feedback. This paper uses the inter-frame coding of Zeineddine and Mansour, originally introduced to address varying channel-state conditions in broadcast wireless communication, to approach capacity on point-to-point channels using VL codes without feedback. The per-symbol complexity is comparable to decoding the VL code with feedback (plus the additional complexity of a small peeling decoder amortized over many VL codes) and presents the opportunity for encoders and decoders that utilize massive parallel processing, where each VL decoder can process simultaneously. This paper provides an analytical framework and a design process for the degree distribution of the inter-frame code that allows the feedback-free system to achieve 96% or more of the throughput of the original VL code with feedback. As examples of VL codes, we consider non-binary (NB) low-density parity-check (LDPC), binary LDPC, and convolutional VL codes. The NB-LDPC VL code with an 8-bit CRC and an average codeword length of 336 bits achieves 85% of capacity with four rounds of ACK/NACK feedback. The proposed scheme using shared incremental redundancy without feedback achieves 97% of that performance or 83% of the channel capacity.

Protograph-based Raptor-like low-density parity-check codes (PBRL codes) are a family of easily encodable rate-compatible low-density parity-check (LDPC) codes. PBRL codes have an excellent performance across all design rates. Quasi-cyclic (QC) PBRL code families permit high-speed decoder implementations. PBRL codes designed thus far, for both long and short block-lengths, have been based on optimizing the iterative decoding threshold of the protograph of the PBRL family at various design rates. This paper introduces a design method to obtain better QC PBRL code families at short block-lengths (of a few hundred bits) for low frame error rate (FER) requirements. We first select a protomatrix for the highest design rate. To add a new row to lower the rate, we keep all the previously obtained rows of the PBRL protomatrix fixed and select the new row that maximizes an upper bound on the minimum distance of any QC-LDPC code that can be obtained from the protomatrix. The new QC PBRL code families outperform the original PBRL codes at short block-lengths by providing a significantly better low-FER performance. The standard approach to computing the aforementioned upper bounds requires complexity that grows exponentially with the size of the protomatrix. However, we show that the structure of the PBRL protomatrix lets us obtain the upper bounds with complexity that grows only linearly with the size of the PBRL protomatrix. Using the complexity reduction results, we also establish an equivalence between the exhaustive search to design a new row for the PBRL protomatrix according to the new design method and an integer linear program.

This paper analyzes the serial list Viterbi algorithm (S-LVA) used in conjunction with optimal CRC codes that minimize probability of undetected error by maximizing the minimum distance between convolutional codewords that pass the CRC check, following Lou et al. In particular, the paper identifies such optimal CRC codes for the 3GPP standard convolutional code (561,753). As SNR varies and the maximum list size L ranges from one to its maximum, this paper uses bounds, approximations, and simulation to characterize decoding complexity and the trade-off between erasure probability and undetected error probability. The complexity of S-LVA is captured by the expected value of the number of decoding attempts required before a CRC check passes or L codewords have been examined. For S-LVA with a degree-m CRC and maximum possible L, which is the cardinality of the set of all possible convolutional codewords, the expected value of the number of decoding attempts converges to one as SNR increases and to 2m(1 - ϵ), for a small ϵ > 0, as SNR decreases. For S-LVA with the maximum possible L, the erasure probability is zero. As L decreases from this maximum, the erasure probability increases and the TIE probability decreases to that of L = 1, for which TIE probability is well approximated by a nearest-neighbor bound.

A rate-compatible (RC) code first transmits a set of symbols corresponding to the highest rate. These symbols form the highest-rate code (HRC). If requested by the receiver, the transmitter subsequently sends symbols that lower the rate of the code. Additional symbols are sent until the decoder decodes to a codeword or all symbols of the RC code are exhausted. Consider linear, RC low-density parity-check (LDPC) codes constructed using extending variable nodes of degree 1. That is, every symbol of incremental redundancy (IR) is a linear combination only of symbols of the HRC. We study the convergence of such codes under iterative decoding. We show that the convergence criterion considered after each iteration need only check whether the HRC variable nodes have converged to a codeword. Specifically, there is no need to consider whether the parity checks that generate the IR symbols are satisfied. We substantiate these claims with simulation results of protograph-based raptor-like LDPC (PBRL) codes, which are a family of protograph RC-LDPC codes with the extending structure under consideration. Furthermore, we demonstrate using examples that this extending structure for protograph RC codes is not very far from the optimal extension for a protograph RC code by providing examples of iterative decoding thresholds for PBRL protographs and protographs extended using the optimal degrees for incremental variable nodes.

Protograph-based Raptor-like low-density parity-check codes (PBRL codes) are a recently proposed family of easily encodable and decodable rate-compatible LDPC (RC-LDPC) codes. These codes have an excellent iterative decoding threshold and performance across all design rates. PBRL codes designed thus far, for both long and short block-lengths, have been based on optimizing the iterative decoding threshold of the protograph of the RC code family at various design rates. In this work, we propose a design method to obtain better quasi-cyclic (QC) RC-LDPC codes with PBRL structure for short block-lengths (of a few hundred bits). We achieve this by maximizing an upper bound on the minimum distance of any QC-LDPC code that can be obtained from the protograph of a PBRL ensemble. The obtained codes outperform the original PBRL codes at short block-lengths by significantly improving the error floor behavior at all design rates. Furthermore, we identify a reduction in complexity of the design procedure, facilitated by the general structure of a PBRL ensemble.

Variable-length codes with incremental redundancy controlled by feedback allow a system to approach capacity with short average blocklengths and thus relatively low-complexity decoders. This paper shows how to use those same variable-length codes with incremental redundancy to approach capacity without feedback. The general principle is to provide a common pool of redundancy that can be accessed by exactly the variable-length codes that need it. We provide example implementations using both regular and irregular low-density generator matrix (LDGM) codes to provide this common pool of redundancy, utilizing the inter-frame coding approach that Zeineddine and Mansour used to combat rate variation due to fading in broadcast transmissions. Obtaining the LDGM degree distributions requires a new design methodology involving differential evolution for a generalized peeling decoder. Monte-Carlo simulations using a 2dB binary-input additive white Gaussian noise channel confirm the feasibility of this new approach. For a frame error rate of 10-3, the irregular LDGM code achieves 96% of the throughput of the corresponding feedback system.

This paper uses a case study of a tail-biting convolutional code (with successful decoding indicated by the reliability output Viterbi algorithm) to present an information density approach for analyzing and optimizing the throughput of systems using incremental redundancy controlled by feedback. Polyan-skiy's normal approximation combined with a linear model for the information gap of a rate-compatible code family provides a simple and accurate characterization of the behavior of feedback systems employing practical codes, such as convolutional or low-density parity-check codes. Especially for short message lengths on the order of k <; 50 message bits, the newly proposed model is more accurate than Vakilinia's model in which the rate of first successful decoding has a Gaussian probability density function.

A transmitter sends a packetized message over a fading channel using packet-level erasure coding and physical-layer channel coding of each resultant packet. Given an overall code rate, this paper finds the optimal rates of the erasure code and the channel code to minimize the transmit power required for a certain message error probability. This paper considers a practically important fading model in which the number of block fades in a transmitted channel codeword increases with the codeword length. Such a model applies, for example, in a time-varying channel with a fixed coherence time. The rate at which diversity grows with codeword length plays an important role in the optimization problem. If the diversity growth factor is large enough, then the erasure code plays a minor role, having an optimal rate that is essentially nondecreasing with decreasing overall rate. We prove analytically that, on a channel with linear growth in diversity, as overall rate decreases, the optimal erasure code rate eventually increases to its maximum possible value (e.g., a rate of 1 for an erasure code with no overhead). Additionally, we also consider the optimization problem of minimizing the message error probability given a transmit power. Numerical results again show that erasure coding is not necessary when overall code rates are sufficiently low.

This paper presents a general approach for optimizing the number of symbols in increments (packets of incremental redundancy) in a feedback communication system with a limited number of increments. This approach is based on a tight normal approximation on the rate for successful decoding. Applying this approach to a variety of feedback systems using nonbinary (NB) low-density parity-check (LDPC) codes shows that greater than 90% of capacity can be achieved with average blocklengths fewer than 500 transmitted bits. One result is that the performance with ten increments closely approaches the performance with an infinite number of increments. The paper focuses on binary-input additive-white Gaussian noise (BI-AWGN) channels but also demonstrates that the normal approximation works well on examples of fading channels as well as high-SNR AWGN channels that require larger QAM constellations. This paper explores both variable-length feedback codes with termination (VLFT) and the more practical variable length feedback (VLF) codes without termination that require no assumption of noiseless transmitter confirmation. For VLF, we consider both a two-phase scheme and CRC-based scheme.

We consider the problem of constructing (3,L) quasi-cyclic low-density parity-check (LDPC) codes from complete protographs. A complete protograph is a small bipartite graph with two disjoint vertex sets such that every vertex in the variable-node set is connected to every vertex in the check-node set by a unique edge. This paper analyzes the required lifting factor for achieving girths of six or eight in the resulting quasi-cyclic codes with constraints on lifting. The required lifting factors provide lower bounds on the block-length of such codes.

Following Poulliat et al.'s design of (2, dc) nonbinary LDPC (NB-LDPC) codes, this paper designs high-rate irregular NB-LDPC codes by addressing the problem of minimum symbol distance. The design procedure first identifies all stopping sets up to weight five in an LDPC code and enumerates them via a message passing algorithm. For each identified stopping set, careful labeling forces its corresponding parity-check sub-matrix to be full rank, thereby preventing the stopping set from being a sub-code and ensuring a minimum distance of at least six symbols. Simulation results for codes designed through this procedure show a significant improvement in the error-floor region over randomized labeling.

One advantage of feedback in a point-to-point memoryless channel is the reduction of the average blocklength required to approach capacity. This paper presents a communication system with feedback that uses carefully designed non-binary LDPC (NB-LDPC) codes and incremental transmissions to achieve 92–94% of the idealized throughput of rate-compatible sphere-packing with maximum-likelihood decoding (RCSP-ML) for average blocklengths of 150–450 bits. The system uses active feedback by carefully selecting each bit of additional incremental information to improve the reliability of the least reliable variable node. The system uses post processing in the decoder to further improve performance. The average blocklengths of 150–450 bits are small enough that feedback provides a throughput advantage but also large enough that overhead that might be associated with transmitter confirmation is more easily tolerated.

One advantage of incremental transmissions with feedback in point-to-point memoryless channels is a reduction in average blocklength required to approach capacity. This paper optimizes the size of each incremental transmission for non-binary (NB) LDPC codes to maximize throughput in VLFT and two-phase VLF settings. The optimization problem uses an approximation based on the inverse-Gaussian p.d.f. of the blocklength required for successful decoding. By using the optimized incremental transmission lengths (with an average blocklength of less than 500 bits), NB-LDPC codes for VLFT setting limited to 5 transmissions achieve a throughput greater than 96% of that obtained by an unlimited-transmission VLFT scheme with the same average blocklength. With a similar average blocklength, a two-phase VLF system limited to five transmissions (with optimized lengths) using the binary image of NB-LDPC codes achieves greater than 90% of the capacity of binary-input AWGN channel with SNR=2 dB. Two-phase VLF does not match the throughput of VLFT, but it is more practical than VLFT because it does not assume noiseless transmitter confirmation.