Achievable error exponents for two-way parallel discrete memoryless channels (DMC) using variable block length coding (VLC) are presented. First, Forney's erasure decoding error exponent is shown to be achievable for both directions simultaneously. Next, for some rate-pairs, it is shown that the error exponent of the direction with a smaller capacity may be further increased by allocating feedback resources to it in the other direction, at the price of a decreased error exponent for the other terminal. The presented two-way communication scheme builds upon Draper-Sahai's one-way DMC achievability scheme with noisy feedback under VLC. Both achievable error exponent regions demonstrate that the use of VLC and interaction between the terminals may benefit both directions' error exponents over fixed block length and feedback free transmission.1

A primitive relay channel (PRC) has one source (S) communicating a message to one destination (D) with the help of a relay (R). The link between R and D is considered to be noiseless, of finite capacity, and parallel to the link between S and (R,D). Prior work has established, for any fixed number of channel uses, the minimal R-D link rate needed so that the overall S-D message rate equals the zero-error single-input multiple output outer bound (Problem 1). The zero-error relaying scheme was expressed as a coloring of a carefully defined “relaying compression graph”. It is shown here that this relaying compression graph for$n$channel uses is not obtained as a strong product from its$n$= 1 instance. Here we define a new graph, the “primitive relaying graph” and a new “special strong product” such that the n-channel use primitive relaying graph corresponds to the n-fold special strong product of the$n$= 1 graph. We show how the solution to Problem 1 can be obtained from this new primitive relaying graph directly. Further study of this primitive relaying graph has the potential to highlight the structure of optimal codes for zero-error relaying.

In the write process of multilevel per cell (MLC) flash memories, an iterative approach is used to mitigate the monotonicity problem. The monotonicity in programming is considered to be the major restriction in MLC flash. To solve this issue, an iterative approach called incremental step pulse programming (ISPP) is used to concurrently program lots of cells in small steps. In this paper, we are mostly concerned with deriving a mathematical model for iterative programming using the framework of renewal theory. We obtain a closed-form approximation for the probability distribution of the number of steps required in the ISPP process. We also bound the maximal error between the true distribution and our approximation. Moreover, the results obtained help to accurately analyze the effect of inter-cell interference in this type of memory. Finally, we devise an adaptive step size approach for write process to strike a balance between latency and lifetime under fixed bit error rate constraints or information rate constraints.

In the write process of multilevel per cell (MLC) flash memories, an iterative approach is used to mitigate the monotonicity problem. The monotonicity in programming is considered to be the major restriction in MLC flash. In this paper, we are mostly concerned with deriving a mathematical model for iterative programming using the framework of “renewal processes”. Then, we approximate the maximum number of steps in iterative programming, and obtain the voltage distribution in flash due to iterative programming. Moreover, the obtained results help us to accurately analyze the effect of inter-cell interference (ICI) in this type of memory. Finally, we obtain a more precise voltage distribution for the symbol states in flash memory. Simulation results show the effect of varying the step size in the iterative programming and the effect of ICI on the information rate.

We are concerned with the optimal detector design for the all-bit-line MLC flash memory. We provide a channel model of the MLC flash memory, where the channel parameters are mathematically tractable. Then we present an optimal maximum a-posteriori sequence detector. The optimal detector can be executed over a trellis whose branch metrics can be computed by using Fourier transforms of analytically computable characteristic functions (corresponding to likelihood functions). The soft-output detectors for both simple one-dimensional channel models and more realistic page-orientated two-dimensional channel models are derived. Simulation results show not only that the soft-output detector has the same hard-output bit-error-rate performance as some previously known detectors did, but that the soft-output detector outperforms previously known detectors by a gain of 0.23 dB.

In this paper we derive the optimal detector for multilevel cell (MLC) flash memory channels with intercell interference (ICI). We start with the MLC channel model proposed by Dong et al. and just slightly alter the model to guarantee mathematical tractability of the optimal detectors (maximum likelihood and maximum a-posteriori sequence and symbol detectors). The optimal detector is obtained by computing branch metrics using Fourier transforms of analytically computable characteristic functions (corresponding to likelihood functions). We derive the detectors for both simple one-dimensional (1D) channel models and more realistic page-orientated two-dimensional (2D) channel models. Simulation results show that the hard-output bit error rate (BER) performance matches some previously known detectors, but that the soft-output detector outperforms previously known detectors by 0.35 dB.

We observe a length-n sample generated by an unknown, stationary ergodic Markov process (model) over a finite alphabet A. Given any string w of symbols from A we want estimates of the conditional probability distribution of symbols following w, as well as the stationary probability of w. Two distinct problems that complicate estimation in this setting are: 1) long memory and 2) slow mixing, which could happen even with only one bit of memory. Any consistent estimator in this setting can only converge pointwise over the class of all ergodic Markov models. Namely, given any estimator and any sample size n, the underlying model could be such that the estimator performs poorly on a sample of size n with high probability. But can we look at a length-n sample and identify if an estimate is likely to be accurate? Since the memory is unknown a-priori, a natural approach is to estimate a potentially coarser model with memory kn= O(log n). As n grows, pointwise consistent estimates that hold eventually almost surely (e.a.s.) are known so long as the scaling of knis not superlogarithmic in n. Here, rather than e.a.s. convergence results, we want the best answers possible with a length-n sample. Combining results in universal compression with Aldous' coupling arguments, we obtain sufficient conditions on the lengthn sample (even for slow mixing models) to identify when naive: 1) estimates of the conditional probabilities and 2) estimates related to the stationary probabilities are accurate, and also bound the deviations of the naive estimates from true values.

We consider estimation of binary channels with memory where the transition probabilities (channel parameters) from the input to output are determined by prior outputs (state of the channel). While the channel is unknown, we observe the joint input/output process of the channel - we have n i.i.d. input bits and their corresponding outputs. Motivated by applications related to the backplane channel, we want to estimate the channel parameters as well as the stationary probabilities for each state. Two distinct problems complicate estimation in this setting: (i) long memory, and (ii) slow mixing which could happen even with only one bit of memory. In this setting, any consistent estimator can only converge pointwise over the model class. Namely, given any estimator and any sample size n, the underlying model could be such that the estimator performs poorly on a sample of size n with high probability. But can we look at a length-n sample and identify if an estimate is likely to be accurate? Since the memory is unknown a-priori, a natural approach, known to be consistent, is to estimate a potentially coarser model with memory kn= αnlog n, where αnis a function that grows O(1). Note however that (i) the coarser model is estimated using only samples from the true model; and (ii) we want the best possible answers with a length-n sample, rather than just consistency. Combining results on universal compression and Aldous' coupling arguments, we obtain sufficient conditions (even for slow mixing models) to identify when naive (i) estimates of the channel parameters and (ii) estimates related to the stationary probabilities of the channel states are accurate, and bound their deviations from true values.