Low-density parity-check (LDPC) codes have higher coding gains compared to algebraic codes in several configurations. However, unlike algebraic codes whose performance can be easily determined generally, the block error rate performance of an LDPC code needs to be obtained by simulations. While there are analytical methods for some structured LDPC codes that predict this performance in the low error rate regime, these provide little insight into the error floor of other (less structured) LDPC codes. In this article, we present a simple method to upper bound the error floor of LDPC codes based on a certain monotonicity assumption on the decoder. This upper bound is general enough so that under the monotonicity assumption it is valid for any error-correcting code. This upper bounding technique is useful when projecting very low block error rates (such as below 1E-14) for LDPC codes and there is no knowledge of the trapping sets.

The digital universe is doubling every two years and expected to reach an unwieldy 44 zettabytes into the next decade. To cope with the ever increasing need for storing, transmitting and retrieving huge amounts of data, cloud storage, data centers and other massively distributed storage networks have emerged. These rely on efficient memory technologies at the physical level for speed, reliability and energy efficiency.

Random I/O (RIO) codes, recently introduced by Sharon and Alrod, is a coding scheme to improve the random input/output performance of flash memories. Multilevel flash memories require, on the average, more than a single read threshold in order to read a single logicalpage. This number is important to be optimized since it sets the read latency of flash memories. An (n, M, t) RIO code assumes that t pages are stored in n cells with t + 1 levels. The first page is read by applying a read threshold between levels t and t + 1. Similarly, the second page is read by applying a read threshold between levels t - 1 and t, and so on. As a consequence, if a cell reads as bit 1 for a page (say page m), the cell also reads as bit 1 for all the successive pages (m + 1, m + 2⋯). Therefore, Sharon and Alrod showed that the design of RIO codes is equivalent to the design of WOM codes. The latter family of codes attracted substantial attention in recent years in order to improve the lifetime of flash memories by allowing writing multiple messages to the memory without the need for an erase operation. In this paper, we notice two important distinctions between RIO codes and WOM codes. While in WOM codes, the messages are received one after the other and thus are not known all in advance, in RIO codes the information of all logical pages can be known in advance when programming the cells. Even though this knowledge does not improve the maximum sumrate of RIO codes, it allows the design of efficient high-rate codes with a moderate block length, which do not exist for WOM codes. We also study another family of RIO codes, called here partial RIO codes, that allow to find even more efficient codes while allowing to sense more than a single threshold to read some pages.

For NAND Flash memory, a read comprises reading the word line at a particular read reference voltage. The read reference voltage is critical as it determines the bit error rate. For equi- probable levels, the optimum read reference is at the intersection of the level probability density functions. In this paper, we propose two methods to obtain the optimum read reference voltage. The first method comprises estimating the parameters of the level's cumulative distribution function. Knowledge of the parameters can then be used to obtain the optimum read reference voltage. In order to estimate the parameters, multiple reads from the Flash memory have to be performed. For latency considerations, we are constrained by the number of allowed reads and want to minimize them. The reads from the Flash memory coupled with the error correcting code output are used to obtain the distribution values. This method involves computing the inverse of the cumulative distribution function to obtain the mean and variance of the distributions. The inverse of the cumulative distribution function is highly sensitive to the measurement noise. Hence, this method needs more reads to mitigate the effects of the measurement noise. The second method consists of using bounded functions based on polynomials to interpolate the cumulative distribution function between the measured values and extrapolate it beyond. This method is more robust to measurement noise. We performed simulations using real Flash memory data to validate the algorithms. The distribution fits we obtain are very close to the actual histograms in the tail region of the distributions. This leads to obtaining bit error rates close to optimum. We extend the method developed for single level cell case to the multi level cell Flash memory, with the upper page read accompanied by the lower page read. In further extensions, we make use of the knowledge of channel impairments and the variance of the distribution over cycles to estimate the cumulative distribution function for the case of only one read from the Flash memory. Simulation results show one order of improvement in the bit error rate using these algorithms.

Random I/O (RIO) Codes, recently introduced by Sharon and Alrod, is a coding scheme to improve the random input/output performance of flash memories. Multi-level flash memories require, on the average, more than a single read threshold in order to read a single logical page. This number is important to be optimized since it sets the read latency of flash memories. An (n,M, t) RIO code assumes that t pages are stored in n cells with t + 1 levels. The first page is read by applying a read threshold between levels t and t + 1. Similarly, the second page is read by applying a read threshold between levels t - 1 and t, and so on. The read binary vectors for consecutive pages satisfy the property that the set of positions read with value 1 can only increase. Therefore, Sharon and Alrod showed also that the design of RIO codes is equivalent to the design of WOM codes. The latter family of codes attracted a lot of attention in recent years in order to improve the lifetime of flash memories by allowing to write multiple messages to the memory without the need for a physical erase. In this paper we notice two important distinctions between RIO codes and WOM codes. While in WOM codes the messages are received one after the other and thus are not known all in advance, in RIO codes the information of all logical pages can be known in advance when programming the cells. Even though this knowledge does not improve the capacity of RIO codes, it allows the design of efficient high-rate codes with a moderate block length, which are hard to be found for WOM codes. We also study another family of RIO codes, called here partial RIO Codes, that allow to find even more efficient codes in the tradeoff of reading more than a single threshold to read a page.

Flash memory comprises of grid of cells arranged in a rectangular lattice. A cell is a floating gate and the information is stored as charge in these floating gates. A multi-level-cell (MLC) can store more than one bit per cell. An ideal programming of a cell consists of injecting just the correct amount of charge in the cell by hot-electron injection. However, due to programming time constraints, some tolerance is accepted and the actual programming voltage is allowed to be within some range of the ideal. While programming a cell, due to the capacitive coupling between neighboring cells, the neighboring cells also get some charge. This phenomenon called as inter-cell-interference (ICI) can be from mild to extreme. Particularly, a cell at the lowest voltage level will pick up a lot of charge if its neighbors are then programmed to the highest level. In order to combat the noise due to ICI, constrained coding is a possible solution. Constrained coding consists of not allowing certain level patterns so that effects of ICI are contained. Constrained coding for solutions which have level information available while decoding all pages has been implemented for flash memory [1]. However, due to read latency requirements, level information may not be available while reading all pages and hence these codes cannot be used. We propose constrained codes which do not need level information while decoding all pages and hence average read latency requirements are met. Error propagation is a crucial degrading factor for constrained decoding and the codes we design are robust to channel noise. A new decoding algorithm which keeps synchronization which is crucial to contain error propagation is also proposed.

An algorithm to generate soft output or log-likelihood-ratios (LLR''s) on channel bits for channels which can be characterized by dominant error events (DEE) is proposed. The magnetic recording and optical recording systems fall under such class of channels [5]. For these channels, a concatenated coding scheme consisting of an outer Reed-Solomon (RS) and an inner parity code with single bit parity or multiple parity bits is commonly used. The inner parity code is usually not decoded using a trellis to limit the computation overhead. Instead, the parity code is decoded by using a post-processor which comprises of a bank of filters. The reduced complexity post-processor using information reuse for decoding the inner parity code is first proposed. A variant of the post-processor is then developed to enable generate soft-output based on the DEE. The performance of the soft-output algorithm is close to the Soft-Output Viterbi Algorithm (SOVA), if the dominant error event list is appropriately chosen. The advantage is that the computational cost is much lesser compared to the SOVA. Conceptually, the proposed reduced-complexity SOVA does not consider all the paths in the trellis for computing the soft-output, rather it uses only on the DEE based paths to generate the soft output.

In this paper, we consider the information rates of baseband linear filter channels with timing errors. We assume that the timing error can be modeled as a discrete-valued Markov process. Based on this assumption, we turn the channel into a finite-state machine model and show that the output sequence is an ergodic and asymptotically stationary hidden Markov process. We then propose Monte-Carlo methods to compute the upper and lower bounds on the information rate by utilizing the entropy ergodic theorem

Packet losses due to congestion or buffer overflows is a common problem in packet switched networks. Current network protocols manage this problem by retransmitting the lost packets. However, the delay due to the retransmission of the lost packets may be unacceptable for many real-time applications. Recent focus to resolve this problem is to recover the lost data from the received packets using some error control coding scheme. In this context, signal representation using frames has gained attention and has been studied in J. Kovacevic et al. (2002), P.L. Dragotti et al. (2001), G. Rath and C. Guillemot (2004), and R. Motwani and C. Guillemot (2004). Oversampled transforms and oversampled filter banks have been considered as joint-source channel codes and methods for reconstructing from erasures is studied in these articles. However, for oversampled filter banks, the reconstruction methods based on operating the pseudo-inverse based on the entire signal length are computationally complex and those based on reconstructing the erasures are not optimal as far as reconstruction mean square error is concerned. In this paper, we propose a method for reconstruction from erasures using a synthesis filter bank which functions as a pseudo-inverse. Hence, the scheme minimizes the reconstruction mean square error. Further, the method is computationally efficient, because it does not operate the pseudo-inverse corresponding to the entire signal vector. The synthesis filter bank, which obviously depends on the erasure pattern implements the pseudo-inverse at a practical computational cost. Some typical bursty erasure patterns which permit existence of a FIR synthesis filter banks are studied. The theoretical results are validated for bursty erasure patterns by simulations using image data.

We use Monte-Carlo methods to compute lower bounds on information rates of insertion/deletion channels. The information rate computation methods we propose are based on reduced-state trellis techniques. We compare the newly obtained bounds to some previously derived bounds (specifically for the deletion channel) and show that the new bounds are (much) sharper. In some regions, the new bound almost meets a known upper bound.

In this paper, we propose a decoder which reconstructs signals which are joint-source channel encoded using oversampled filter banks. The decoder is based on operating the para-pseudoinverse corresponding to the cascaded transform function consisting of the source encoder and the erasure channel on the received signal. Hence, the proposed method minimizes the reconstruction mean square error. The decoder consists of a filter bank which can comprise of FIR or IIR filters depending on the erasure channel. Hence the computational complexity of the decoder is also lower compared to earlier proposed techniques. The theoretical results are validated by simulations using image data.

The paper studies quantized frame expansions based on tree-structured oversampled filter banks for robust transmission of multimedia signals over erasure channels. The dependencies between the expansion coefficients introduced by the oversampled tree-structured filter banks are analysed in the z-transform domain. The capacity of correction in the presence of different erasure patterns then follows naturally. This analysis leads to the design of a reconstruction algorithm in the presence of erasures, and first without quantization noise. The impact of quantization error on the reconstruction error is then studied. For the tree-structured oversampled filter banks, we prove that reconstruction from a larger class of erasure patterns is possible as compared to regular oversampled filter banks. The reconstruction mean square error is significantly lower in the case of the tree-structured filter bank as compared to regular oversampled filter banks (Motwani, R. and Guillemot, C., 2003) and block transforms, even if the erasures are bursty in nature.

This paper studies oversampled filter banks (OFB) for robust transmission of image/video signals over erasure channels. The dependencies introduced by the OFB-based frame expansion are first analyzed in the z domain. This analysis paves the way to the design of an algorithm for message reconstruction in presence of erasures and quantization noise. Conditions for recovery from some typical erasure patterns like bursty erasures and periodic erasure patterns are derived for both orthogonal and biorthogonal filter banks. For some erasure patterns the equivalent transform coder forms a frame, hence the reconstruction could be based on operating its pseudo inverse, however at the expense of high computational cost. Alternately, the erased samples can first be reconstructed from the received ones and then signal space projection can be applied. Since in practical systems the codevectors are quantized before transmission, we study the effect of quantization noise on the reconstructed signal. The theoretical results are validated for a number of erasure patterns with image signals.

In a parallel concatenated convolutional code, an information sequence is encoded by a convolutional encoder, and an interleaved version of the information sequence is encoded by another convolutional encoder. We discuss the situation in which we require both convolutional encoders to end in the all-zero state. To do so, we have to split an information word in two parts. One part contains the true information bits, and the second part contains the so-called tail bits, which are special bits with values computed such that both encoders end in the all-zero state. Depending on the interleaver, a different number of tail bits are needed. By using a constructive method, we give a characterization of all interleavers for a prescribed number of tail bits. We explain the method of encoding. In addition, simulations have been carried out to investigate the performance of codes resulting from simultaneous zero-tailing. This shows that simultaneous zero-tailing is similar in performance as compared to previously known zero-tailing methods (but with fewer trellis termination bits) and that it is better than zero-tailing just one of the encoders.

Oversampled transforms are used to provide robustness against erasures. Oversampled DFT codes have already been studied for erasure channels Me IP networks. We propose oversampled DCT transforms called DCT codes for erasure channels. We show that DCT codes offer more flexibility in design as compared to DFT codes and for some cases, lesser average mean square reconstruction error for erasures decoding. DCT codes have been studied before for error correction. In this article, we look at their suitability for signal reconstruction from erasures. We also propose methods to construct oversampled transforms from standard orthogonal transforms like Hadamard, sine transforms for robustness. to erasures.

For convolutional codes which commence encoding in the all-zero state and return to the all-zero state after encoding, the bit error rate for the initial and final few bits is lower as compared to the other bits. This is because the initial and final states are known at the receiver. Motivated by this observation, we propose an encoding scheme wherein the encoder transmits its state information at particular fixed positions in the trellis. The decoder uses the received state information for decoding, resulting in the bits around the transmitted states to be better protected. This scheme can be used for applications which require unequal error protection, wherein some bits have higher importance than others.

We propose a method to design an orthonormal two-channel cyclic filterbank (CFB) with real analysis and synthesis filters having linear phase. This is particularly significant, since it is not possible to realize regular two-channel linear phase orthogonal filterbanks (unless the filters are two-tap). The lowpass filter of the FB is obtained as a spectral factor of a zero phase Nyquist(2) filter, which is optimized. We show that the CFB design is computationally less demanding as compared to the noncyclic case, and it may be possible to get better filters. We design the CFB for a particular case and show that this filterbank is not a noncyclic orthogonal filterbank.