We consider the effect of log-likelihood ratio saturation on the belief-propagation decoding of low-density parity-check codes. Saturation is commonly done in practice and is known to have a significant effect on the error-floor performance. Our focus is on threshold analysis and the stability of density evolution. We analyze the decoder for standard low-density parity-check code ensembles and show that belief-propagation decoding generally degrades gracefully with saturation. Stability of density evolution is, on the other hand, rather strongly affected by saturation, and the asymptotic qualitative effect of saturation is similar to reduction by one of variable-node degree. We also describe conditions under which the block-error threshold for saturated belief-propagation decoding equals the bit-error threshold.

We consider a new formulation of a class of synchronization error channels and derive analytical bounds and numerical estimates for the capacity of these channels. For the binary channel with only deletions, we obtain an expression for the symmetric information rate in terms of subsequence weights, which reduces to a tight lower bound for small deletion probabilities. We are also able to exactly characterize the Markov-1 rate for the binary channel with only replications. For a channel that introduces deletions as well as replications of input symbols, we design approximating channels that parameterize the state space and show that the information rates of these approximate channels approach that of the deletion-replication channel as the state space grows. For the case of the channel where deletions and replications occur with the same probabilities, a stronger result in the convergence of mutual information rates is shown. The numerous advantages this new formulation presents are explored.

We consider the effect of LLR saturation on belief propagation decoding of low-density parity-check codes. Saturation is commonly done in practice and is known to have a significant effect on error floor performance. Our focus is on threshold analysis and the stability of density evolution. We analyze the decoder for certain low-density parity-check code ensembles and show that belief propagation decoding generally degrades gracefully with saturation. Stability of density evolution is, on the other hand, rather strongly affected by saturation and the asymptotic qualitative effect of saturation is similar to reduction of variable node degree by one.

We consider t-write codes for write-once memories with n cells that can store multiple levels. Assuming an underlying lattice-based construction and using the continuous approximation, we derive upper bounds on the worst-case sum-rate optimal and fixed-rate optimal n-cell t-write write-regions for the asymptotic case of continuous levels. These are achieved using hyperbolic shaping regions that have a gain of 1 bit/cell over cubic shaping regions. Motivated by these hyperbolic write-regions, we discuss construction and encoding of codebooks for cells with discrete support. We present a polynomial-time algorithm to assign messages to the codebooks and show that it achieves the optimal sum-rate for any given codebook when n = 2. Using this approach, we construct codes that achieve high sum-rate. We describe an alternative formulation of the message assignment problem for n≥ 3, a problem which remains open.

Spatially coupled codes have been of interest recently owing to their superior performance over memoryless binary-input channels. The performance is good both asymptotically, since the belief propagation thresholds approach the Shannon limit, as well as for finite lengths, since degree-2 variable nodes that result in high error floors can be completely avoided. However, to realize the promised good performance, one needs large blocklengths. This in turn implies a large latency and decoding complexity. For the memoryless binary erasure channel, we consider the decoding of spatially coupled codes through a windowed decoder that aims to retain many of the attractive features of belief propagation, while trying to reduce complexity further. We characterize the performance of this scheme by defining thresholds on channel erasure rates that guarantee a target erasure rate. We give analytical lower bounds on these thresholds and show that the performance approaches that of belief propagation exponentially fast in the window size. We give numerical results including the thresholds computed using density evolution and the erasure rate curves for finite-length spatially coupled codes.

We consider t-write codes for write-once memories with cells that can store multiple levels. Using worst-case sum-rate optimal 2-cell t-write code constructions for the asymptotic case of continuous levels, we derive 2-cell t-write code constructions that give good sum-rates for cells that support q discrete levels. A general encoding scheme for q-level 2-cell t-write codes is provided.

We consider a windowed decoding scheme for LDPC convolutional codes that is based on the belief-propagation (BP) algorithm. We discuss the advantages of this decoding scheme and identify certain characteristics of LDPC convolutional code ensembles that exhibit good performance with the windowed decoder. We will consider the performance of these ensembles and codes over erasure channels with and without memory. We show that the structure of LDPC convolutional code ensembles is suitable to obtain performance close to the theoretical limits over the memoryless erasure channel, both for the BP decoder and windowed decoding. However, the same structure imposes limitations on the performance over erasure channels with memory.

We investigate the reasons behind the superior performance of belief propagation decoding of non- binary LDPC codes over their binary images when the transmission occurs over the binary erasure channel. We show that although decoding over the binary image has lower complexity, it has worse performance owing to its larger number of stopping sets relative to the original non-binary code. We propose a method to find redundant parity-checks of the binary image that eliminate these additional stopping sets, so that we achieve performance comparable to that of the original non-binary LDPC code with lower decoding complexity.

We study windowed decoding of spatially coupled codes when the transmission occurs over the binary erasure channel. We characterize the performance of this scheme by defining thresholds on channel erasure rates that guarantee a target bit erasure rate. We give analytical lower bounds on these thresholds and show that the performance approaches that of belief propagation exponentially fast in the window size. We give numerical results including the thresholds computed using density evolution and the erasure rate curves for finite-length spatially coupled codes.

We propose a new channel model for channels with synchronization errors. Using this model, we give simple, non-trivial and, in some cases, tight lower bounds on the capacity for certain synchronization error channels.

We consider terminated LDPC convolutional codes (LDPC-CC) constructed from photographs and explore the performance of these codes on correlated erasure channels including a single-burst channel (SBC) and Gilbert-Elliott channel (GEC). We consider code performance with a latency-constrained message passing decoder and the belief propagation decoder. We give theoretical bounds on the code efficiency over the SBC and describe a construction that achieves this bound.We show that the designed codes with belief propagation (BP) decoding perform as well as the regular LDPC-CCs presented in the literature on the binary erasure channel (BEC) and the GEC, while achieving significant gains on the SBC. In the case of windowed decoding, our codes perform much better than the best known regular LDPC-CCs over the BEC and the GEC, with very low decoding latencies.

We propose a new channel model for the write channel in Magnetic Recording with Bit-Patterned Media. We study information theoretic propoerties of this channel and suggest a simplistic rate-1/2 coding scheme that achieves zero error. Based on this channel model, we propose a channel with insertion and deletion errors.