In recent work, it has been shown that maintaining reliability in analog vector--matrix multipliers can be modeled as the following coding problem. Vectors in $\mathbb{R}^k$ are encoded into codewords of a linear $[n,k,d]$ code $C$ over $\mathbb{R}$. For prescribed positive reals $δ< Δ$, additive errors of magnitude at most $δ$ are tolerable and need no handling, yet outlying errors of magnitude greater than $Δ$ are to be located or detected. The trade-off between the ratio $Δ/δ$ and the number of outlying errors that can be handled is determined by the height profile of $C$; as such, the height profile provides a finer description of the error handling capability of $C$, compared to the minimum distance $d$, which only determines the number of correctable errors. This work contains a further study of the notion of the height profile. Several characterizations of the height profile are presented, thereby yielding methods for computing it. The starting point is formulating this computation as an optimization problem that is solved by a set of linear programs. This, in turn, leads to a combinatorial characterization of the height profile as a maximum (or max--min) over a certain finite set of codewords of $C$. Moreover, this characterization is shown to have a simple geometric interpretation when the columns of the generator matrix of $C$ all have the same $L_2$ norm. Through examples of several code families, it is demonstrated how the results herein can be used to compute the height profile explicitly.

Differential Varshamov-Tenengolts (D-VT) codes, recently introduced by Nguyen et al. (2024), are q-ary codes that can correct a single deletion (or insertion) error with reduced redundancy compared to the Tenengolts q-ary single deletion correction codes. In this work, we completely determine the sizes of D-VT codes. We clarify the relationship between D-VT codes and Tenengolts codes, which implies a more efficient D-VT decoding algorithm. Finally, we present an alternative characterization of certain D-VT codes in terms of q-ary necklaces.

We generalize the well-known Coupon Collector Problem (CCP) in combinatorics. Our problem is to find the minimum and expected number of draws, with replacement, required to recover n distinctly labeled coupons, with each draw consisting of a random subset of k different coupons and a random ordering of their associated labels. We specify two variations of the problem, Type-I in which the set of labels is known at the start, and Type-II in which the set of labels is unknown at the start. We show that our problem can be viewed as an extension of the separating system problem introduced by Rényi and Katona, provide a full characterization of the minimum, and provide a numerical approach to finding the expectation using a Markov chain model, with special attention given to the case where two coupons are drawn at a time.

Modeling spatio-temporal read voltages with complex distortions arising from the write and read mechanisms in flash memory devices is essential for the design of signal processing and coding algorithms. In this work, we propose Flash-Gen, a data-driven approach to generating flash memory read voltages in both space and time using conditional generative networks. This generative modeling method reconstructs read voltages from an individual memory cell based on the program levels of the cell and its surrounding cells, as well as the time stamp, in a time-efficient, resource-saving, and function-comprehensive manner. We evaluate the model over a range of time stamps using the read voltage distributions, the cell level error rates, and the relative frequency of errors for patterns most susceptible to inter-cell interference (ICI) effects. We propose a flash system optimization procedure, referred to as the Flash-Gen coding workflow, that leverages reconstructed read voltages for the development of error correction codes (ECCs) and constrained codes. Experimental results demonstrate that the model accurately captures the complex spatial and temporal features of the flash memory channel. Flash-Gen coding workflow can effectively address a range of important tasks, including threshold determination, coding performance estimation, and pattern characterization.

This paper investigates properties of polar-polar concatenated codes and their potential applications. We start by reviewing previous work on stopping set analysis for conventional polar codes, which we extend in this paper to concatenated architectures. Specifically, we present a stopping set analysis for the factor graph of concatenated polar codes, deriving an upper bound on the size of the minimum stopping set. To achieve this bound, we propose new bounds on the size of the minimum stopping set for conventional polar code factor graphs. The tightness of these proposed bounds is investigated empirically and analytically. We show that, in some special cases, the exact size of the minimum stopping set can be determined with a time complexity ofO(N), whereNis the codeword length. The stopping set analysis motivates a novel construction method for concatenated polar codes. This method is used to design outer polar codes for two previously proposed concatenated polar code architectures: augmented polar codes and local-global polar codes. Simulation results with BP decoding demonstrate the advantage of the proposed codes over previously proposed constructions based on density evolution (DE).

Analytic combinatorics in several variables is a branch of mathematics that deals with deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We study information-theoretic questions about sequences in a discrete noiseless channel under cost constraints. Our main contributions involve the relationship between the graph structure of the channel and the singularities of the bivariate generating function whose coefficients are the number of sequences satisfying the constraints. We use these new results to invoke theorems from multivariate analytic combinatorics to obtain the asymptotic behavior of the number of cost-limited strings that are admissible by the channel. This builds a new bridge between analytic combinatorics in several variables and labeled weighted graphs, bringing a new perspective and a set of powerful results to the literature of cost-constrained channels. Along the way, we show that the cost-constrained channel capacity is determined by a cost-dependent singularity of the bivariate generating function, generalizing Shannon’s classical result for unconstrained capacity, and provide a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity.

The advent of byte-addressable persistent memory (PM) has led to a resurgence of interest in adapting existing dynamic hashing schemes to PM. Compared with its two well-known peers (extendible hashing and linear hashing), spiral storage has received little attention due to its limitations. After an in-depth analysis, however, we discover that it has a good potential for PM. To show its strength, we develop a persistent spiral storage called PASS (Persistence-Aware Spiral Storage), which is facilitated by a group of new/existing techniques. Further, we conduct a comprehensive evaluation of PASS on a server equipped with Intel Optane DC Persistent Memory Modules (DCPMM). Experimental results demonstrate that compared with two state-of-the-art schemes it exhibits better performance.

The goal of functional error correction is to preserve neural network performance when stored network weights are corrupted by noise. To achieve this goal, a selective protection (SP) scheme was proposed to optimally protect the functionally important bits in binary weight representations in a layer-dependent manner. Although it showed its effectiveness in image classification tasks on some relatively simple networks such as ResNet-18 and VGG-16, it becomes inadequate for emerging complex machine learning tasks generated from natural language processing and vision-language association domains. To solve this problem, we extend the SP scheme in three directions: task complexity, model complexity, and storage complexity. Extensions to complex natural language and vision-language tasks include text categorization and “zero-shot” textual classification of images. Extensions to more complex models with deeper block structures and attention mechanisms consist of Very Deep Convolutional Neural Network (VDCNN) and Contrastive Language-Image Pre-Training (CLIP) networks. Extensions to more complex storage configurations focus on distributed storage architectures to support model parallelism. Experimental results show that the optimized SP scheme preserves network performance in all of these settings. The results also provide insights into redundancy-performance tradeoffs, generalizability of SP across datasets and tasks, and robustness of partitioned network architectures.

In this paper, we introduce two novel methods to design outer polar codes for two previously proposed concatenated polar code architectures: augmented polar codes and local-global polar codes. These methods include a stopping set (SS) construction and a nonstationary density evolution (NDE) construction. Simulation results demonstrate the advantage of these methods over previously proposed constructions based on density evolution (DE) and LLR evolution.

The problem of correcting deletions and insertions has recently received significantly increased attention due to the DNA-based data storage technology, which suffers from deletions and insertions with extremely high probability. In this work, we study the problem of constructing non-binary burst-deletion/insertion correcting codes. Particularly, for the quaternary alphabet, our designed codes are suited for correcting a burst of deletions/insertions in DNA storage. Non-binary codes correcting a single deletion or insertion were introduced by Tenengolts (1984), and the results were extended to correct a fixed-length burst of deletions or insertions by Schoeny et al. (2017). Recently, Wang et al. (2021) proposed constructions of non-binary codes of length n, correcting a burst of length at most two for q-ary alphabets with redundancy$\log n+O(\log q \log \log n)$bits, for arbitrary even q. The common idea in those constructions is to convert non-binary sequences into binary sequences, and the error decoding algorithms for the q-ary sequences are mainly based on the success of recovering the corresponding binary sequences, respectively. In this work, we look at a natural solution that the error detection and correction algorithms are performed directly over q-ary sequences, and for certain cases, our codes provide a more efficient encoder with lower redundancy than the best-known encoder in the literature. Particularly, (Single-error correction codes) We first present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion, providing an alternative simpler and more efficient encoder of the construction by Tenengolts (1984). Our construction is based on the differential vector, and the codes are referred to as the differential VT codes. In addition, we provide linear-time algorithms that encode user messages into these codes of length n over the q-ary alphabet for$q \geqslant 2$with at most$\lceil \log _{q} n\rceil +1$redundant symbols, while the optimal redundancy required is at least$\log _{q} n+\log _{q} (q-1)$symbols. Our designed encoder reduces the redundancy of the best-known encoder of Tenengolts (1984) by at least 2 redundant symbols or equivalently$2\log _{2} q$bits. (Burst-error correction codes) We use the idea of the binary shifted VT codes to define the q-ary differential shifted VT codes, and propose non-binary codes correcting a burst of up to two deletions (or two insertions) with redundancy$\log n+3\log \log n+ O(\log q)$bits, which improves a recent result of Wang et al. (2021) with redundancy$\log n+O(\log q \log \log n)$bits for all$q\geqslant 8$. We then extend the construction to design non-binary codes correcting a burst of either exactly or at most t deletions (or insertions) for arbitrary$t\geqslant 2$.

Modeling spatio-temporal read voltages with complex distortions arising from the write and read mechanisms in flash memory devices is essential for the design of signal processing and coding algorithms. In this work, we propose a data-driven approach to modeling NAND flash memory read voltages in both space and time using conditional generative networks. This generative flash modeling (GFM) method reconstructs read voltages from an individual memory cell based on the program levels of the cell and its surrounding cells, as well as the time stamp. We evaluate the model over a range of time stamps using the cell read voltage distributions, the cell level error rates, and the relative frequency of errors for patterns most susceptible to inter-cell interference (ICI) effects. Experimental results demonstrate that the model accurately captures the complex spatial and temporal features of the flash memory channel.

In this work, we present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion. Moreover, we provide the first-known linear-time algorithms that encode user messages into these codes of length$n$over the q-ary alphabet for$q$> 2 with at most [logq$n$] + 1 redundant symbols, while the optimal redundancy required is at least logq$n$+ logq(q - 1) symbols. Our designed encoder reduces the redundancy of the best known encoder of Tenengolts (1984) by at least 2 + logq(3) redundant symbols, or equivalently 2 log2q + 3 redundant bits.

Analytic combinatorics in several variables (ACSV) is a powerful tool for deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We use ACSV to derive the first-order sub-exponential asymptotics of sequences generated by a discrete noiseless channel under an average cost constraint. As a by-product of the analysis, we obtain a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity.

The pivotal storage density win achieved by solid-state devices over magnetic devices in 2015 is a result of multiple innovations in physics, architecture, and signal processing. One of the most important innovations in that regard is enabling the storage of more than one bit per cell in the Flash device, i.e., having more than two charge levels per cell. Constrained coding is used in Flash devices to increase reliability via mitigating inter-cell interference that stems from charge propagation among cells. Recently, capacity-achieving constrained codes were introduced to serve that purpose in modern Flash devices, which have more than two levels per cell. While these codes result in minimal redundancy via exploiting the underlying physics, they result in non-negligible complexity increase and access speed limitation since pages cannot be read separately. In this paper, we suggest new constrained coding schemes that have low-complexity and preserve the desirable high access speed in modern Flash devices. The idea is to eliminate error-prone patterns by coding data either only on the left-most page (binary coding) or only on the two left-most pages (4-ary coding) while leaving data on all the remaining pages uncoded. Our coding schemes work for any number of levels$q \geq 4$per cell, offer systematic encoding and decoding, and are capacity-approaching. Since the proposed schemes enable the separation of pages, except the two left-most pages in the case of 4-ary coding, we refer to them as read-and-run (RR) constrained coding schemes as opposed to schemes adopting read-and-wait for other pages. The 4-ary RR coding scheme is introduced in order to limit the rate loss incurred by the binary RR coding schemes, and we show that our 4-ary RR coding scheme is also competitive when it comes to complexity and error propagation. We analyze the new RR coding schemes and discuss their impact on the probability of occurrence of different charge levels. We also demonstrate the performance improvement achieved via RR coding on a practical triple-level cell Flash device.

Motivated by recent advances in DNA-based data storage, we study a communication system, where information is conveyed over many sequences in parallel. In this system, the receiver cannot control the access to these sequences and can only draw from these sequences, unaware which sequence has been drawn. Further, the drawn sequences are susceptible to errors. In this paper, a suitable channel model that models this input-output relationship is analyzed and its information capacity is computed for a wide range of parameters and a general class of drawing distributions. This generalizes previous results for the noiseless case and specific drawing distributions. The analysis can guide future DNA-based data storage experiments by establishing theoretical limits on achievable information rates and by proposing decoding techniques that can be useful for practical implementations of decoders.

The pivotal storage density win achieved by solid-state devices over magnetic devices in 2015 is a result of multiple innovations in physics, architecture, and signal processing. One of the most important innovations in that regard is enabling the storage of more than one bit per cell in the Flash device, i.e., having more than two charge levels per cell. Constrained coding is used in Flash devices to increase reliability via mitigating inter-cell interference that stems from charge propagation among cells. Recently, capacity-achieving constrained codes were introduced to serve that purpose in modern Flash devices, which have more than two levels per cell. While these codes result in minimal redundancy via exploiting the underlying physics, they result in non-negligible complexity increase and access speed limitation since pages cannot be read separately. In this paper, we suggest new constrained coding schemes that have low-complexity and preserve the desirable high access speed in modern Flash devices. The idea is to eliminate error-prone patterns by coding data only on the left-most page while leaving data on all the remaining pages uncoded. Our coding schemes work for any number of levels per cell, offer systematic encoding and decoding, and are capacity-approaching. Since the proposed schemes enable the separation of pages, we refer to them as read-and-run (RR) constrained coding schemes as opposed to schemes adopting read-and-wait for other pages. We analyze the new RR coding schemes and discuss their impact on the probability of occurrence of different charge levels. We also demonstrate the performance improvement achieved via RR coding on a practical triple-level cell Flash device.

Shaping codes are used to generate code sequences in which the symbols obey a prescribed probability distribution. They arise naturally in the context of source coding for noiseless channels with unequal symbol costs. Recently, shaping codes have been proposed to extend the lifetime of flash memory and reduce DNA synthesis time. In this paper, we study a general class of shaping codes for noiseless finite-state channels with cost and i.i.d. sources. We establish a relationship between the code rate and minimum average symbol cost. We then determine the rate that minimizes the average cost per source symbol (total cost). An equivalence is established between codes minimizing average symbol cost and codes minimizing total cost, and a separation theorem is proved, showing that optimal shaping can be achieved by a concatenation of optimal compression and optimal shaping for a uniform i.i.d. source.

With the reduction in device size and the increase in cell bit-density, NAND flash memory suffers from larger inter-cell interference (ICI) and disturbance effects. Constrained coding can mitigate the ICI effects by avoiding problematic error-prone patterns, but designing powerful constrained codes requires a comprehensive understanding of the flash memory channel. Recently, we proposed a modeling approach using conditional generative networks to accurately capture the spatio-temporal characteristics of the read signals produced by arrays of flash memory cells under program/erase (P/E) cycling. In this paper, we introduce a novel machine learning framework for extending the generative modeling approach to the coded storage channel. To reduce the experimental overhead associated with collecting extensive measurements from constrained program/read data, we train the generative models via transferring knowledge from models pre-trained with pseudo-random data. This technique can accelerate the training process and improve model accuracy in reconstructing the read voltages induced by constrained input data throughout the flash memory lifetime. We analyze the quality of the model by comparing flash page bit error rates (BERs) derived from the generated and measured read voltage distributions. We envision that this machine learning framework will serve as a valuable tool in flash memory channel modeling to aid the design of stronger and more efficient coding schemes.

There are various ways to use machine learning to improve data storage techniques. In this paper, we introduce symbolic regression, a machine-learning method for recovering the symbolic form of a function from its samples. We present a new symbolic regression scheme that utilizes side information for higher accuracy and speed in function recovery. The scheme enhances latest results on symbolic regression that were based on recurrent neural networks and genetic programming. The scheme is tested on a new benchmark of functions for data storage.

Recent advances in the flash memory technology call for more efficient error-correction codes (ECCs) than the conventional, yet very popular, ones such as BCH codes. The ability to make multiple voltage reads allows one to estimate soft values at the time of decoding, which in turn makes soft-decision ECCs such as LDPC codes a suitable candidate for implementation in flash memories. On the other hand, fully utilizing the potential of soft decision based codes demands higher precision memory sensing, which introduces a trade-off between the read latency and the error probability. In this paper, we explore and compares two approaches to optimize the positioning as well as the number of read (word-line) voltages for a specified program/erase (PE) cycle.In the first approach, we aim for selecting those read thresholds that maximize the mutual information (MMI) of the equivalent discrete memoryless channel. By utilizing conventional optimization methods such as the gradient descent (GD), we are able to find the optimal read locations for any number of read probes. Our simulation results show that ~20 reads are effective. Next, we redesign our optimization problem to take the LDPC code structure into account. To do so, we use discretized density evolution (DDE) as a proxy for bit error rate (BER), which serves as our cost function in the GD search. To overcome the problem of local minima, we propose a two-step optimization: MMI for coarse optimization, followed by DDE for fine optimization. Simulation results confirm the effectiveness of this method.1

We propose a shaping code based on polar codes. For a costly noiseless channel, we show that the total cost of the proposed polar shaping code approaches the optimal total cost as block length grows. We also consider shaping for costly noisy discrete memoryless channels (DMCs). We first give an upper bound on the rate that can be achieved with a specified symbol occurrence probability distribution over a DMC. Then we formulate an optimization problem whose solution gives a lower bound on the optimal total cost for a costly noisy DMC. We compute the lower bound for the costly$M$-ary erasure channel. Finally, we propose polar shaping codes for costly noisy channels that achieve the lower bound by adapting polar codes for asymmetric channels proposed by Honda and Yamamoto.

Advances in biochemical technologies, such as synthesizing and sequencing devices, have fueled manifold recent experiments on archival digital data storage using DNA. In this paper we review and analyze recent results on information-theoretic aspects of such storage systems. The discussion focuses on a channel model that incorporates the main properties of DNA-based data storage. Namely, the user data is synthesized many times onto a large number of short-length DNA strands. The receiver then draws strands from the stored sequences in an uncontrollable manner. Since the synthesis and sequencing are prone to errors, a received sequence can differ from its original strand, and their relationship is described by a probabilistic channel. Recently, the capacity of this channel was derived for the case of substitution errors inside the sequences. We review the main techniques used to prove a coding theorem and its converse, showing the achievability of the capacity and the fact that it cannot be exceeded. We further provide an intuitive interpretation of the capacity formula for relevant channel parameters, compare with sub-optimal decoding methods, and conclude with a discussion on cost-efficiency.

In this paper, we investigate the use of recurrent neural network (RNN)-based detection of magnetic recording channels with inter-symbol interference (ISI). We refer to the proposed detection method, which is intended for recording channels with partial-response equalization, as Partial-Response Neural Network (PR-NN). We train bi-directional gated recurrent units (bi-GRUs) to recover the ISI channel inputs from noisy channel output sequences and evaluate the network performance when applied to continuous, streaming data. The computational complexity of PR-NN during the evaluation process is comparable to that of a Viterbi detector. The recording system on which the experiments were conducted uses a rate-2/3, (1,7) runlength-limited (RLL) code with an E2PR4 partial-response channel target. Experimental results with ideal PR signals show that the performance of PR-NN detection approaches that of Viterbi detection in additive white gaussian noise (AWGN). Moreover, the PR-NN detector outperforms Viterbi detection and achieves the performance of Noise-Predictive Maximum Likelihood (NPML) detection in additive colored noise (ACN) at different channel densities. A PR-NN detector trained with both AWGN and ACN maintains the performance observed under separate training. Similarly, when trained with ACN corresponding to two different channel densities, PR-NN maintains its performance at both densities. Experiments confirm that this robustness is consistent over a wide range of signal-to-noise ratios (SNRs). Finally, PR-NN displays robust performance when applied to a more realistic magnetic recording channel with MMSE-equalized Lorentzian signals.

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the Hamming metric, we consider the problem of designing covering codes defined in terms of either insertions or deletions. First, we provide new sphere-covering lower bounds on the minimum possible size of such codes. Then, we provide new existential upper bounds on the size of optimal covering codes for a single insertion or a single deletion that are tight up to a constant factor. Finally, we derive improved upper bounds for covering codes using R ≥ 2 insertions or deletions. We prove that codes exist with density that is only a factor O(R logR) larger than the lower bounds for all fixed R. In particular, our upper bounds have an optimal dependence on the word length, and we achieve asymptotic density matching the best known bounds for Hamming distance covering codes.

Bi-modal (respectively, multi-modal) constrained coding refers to an encoding model whereby a user input block can be mapped to two (respectively, multiple) codewords. In current storage applications, such as optical disks, multi-modal coding allows to achieve DC control, in addition to satisfying the runlength limited (RLL) constraint specified by the recording channel. In this work, a study is initiated on bi-modal fixed-length constrained encoders. Necessary and sufficient conditions are presented for the existence of such encoders for a given constraint. It is also shown that under somewhat stronger conditions, one can guarantee a bi-modal encoder with finite decoding delay.

Previous work by the authors on parity-preserving fixed-length constrained encoders is extended to the variable-length case. Parity-preserving variable-length encoders are formally defined, and, to this end, Kraft conditions are developed for the parity-preserving variable-length setting. Then, a necessary and sufficient condition is presented for the existence of deterministic parity-preserving variable-length encoders for a given constraint. Examples are provided that show that there are coding ratios where parity-preserving variable-length encoders exist, while fixed-length encoders do not.

Mismatch between the true channel and the channel assumed in the design of a communication system can degrade system performance. Joint channel estimation and data recovery via the Expectation-Maximization (EM) algorithm can overcome this problem. Though stable, the EM algorithm can be complex to implement and can exhibit slow convergence. We present approximations of the EM algorithm that reduce computational complexity and accelerate convergence for LDPC-coded discrete memoryless channels. In place of the exact bit-wise maximum a posteriori probability decoder in the E step of the EM algorithm, we use the sum-product decoder and min-sum decoder. In the M step, we use hard information instead of soft information to estimate the channel parameter. In order to evaluate the approximations in a practical channel mismatch scenario, we use a flash memory channel described by a quantized Normal-Laplace mixture model. The simulation results demonstrate that the approximations in the E step can estimate the true channel with low-complexity decoding and those in the M step can accelerate the convergence with reduced measurement precision.

Significant advances in biochemical technologies, such as synthesizing and sequencing devices, have made DNA a competitive medium for archival data storage. In this paper we analyze storage systems based on these macromolecules from an information theoretic perspective. Using an appropriate channel model for the synthesis and sequencing steps, we study the maximum achievable information density per nucleotide for reliable and error resilient data storage. The channel model features the main attributes that characterize DNA-based data storage. That is, information is synthesized onto many short DNA strands, and each strand is copied many times. Due to the storage and sequencing methods, the receiver draws strands from these synthesized strands in an uncontrollable manner, where it is possible that strands are drawn multiple times and also that some strands are not drawn at all. Additionally, due to imperfections, the obtained strands can contain errors. Here we prove the achievability of a recently published upper bound on the Shannon capacity of this channel for a large range of parameters by proposing and analyzing a decoder that clusters received strands according to their similarity and then efficiently estimates the original strands based on these clusters.

When deep neural networks (DNNs) are implemented in hardware, their weights need to be stored in memory devices. As noise accumulates in the stored weights, the DNN's performance will degrade. This paper studies how to use error correcting codes (ECCs) to protect the weights. Different from classic error correction in data storage, the optimization objective is to optimize the DNN's performance after error correction, instead of minimizing the Uncorrectable Bit Error Rate in the protected bits. That is, by seeing the DNN as a function of its input, the error correction scheme is function-oriented. A main challenge is that a DNN often has millions to hundreds of millions of weights, causing a large redundancy overhead for ECCs, and the relationship between the weights and its DNN's performance can be highly complex. To address the challenge, we propose a Selective Protection (SP) scheme, which chooses only a subset of important bits for ECC protection. To find such bits and achieve an optimized tradeoff between ECC's redundancy and DNN's performance, we present an algorithm based on deep reinforcement learning. Experimental results verify that compared to the natural baseline scheme, the proposed algorithm achieves substantially better performance for the functional error correction task.

For DNA data storage to become a feasible technology, all aspects of the encoding and decoding pipeline must be optimized. Writing the data into DNA, which is known as DNA synthesis, is currently the most costly part of existing storage systems. As a step toward more efficient synthesis, we study the design of codes that minimize the time and number of required materials needed to produce the DNA strands. We consider a popular synthesis process that builds many strands in parallel in a step-by-step fashion using a fixed supersequence S. The machine iterates through S one nucleotide at a time, and in each cycle, it adds the next nucleotide to a subset of the strands. The synthesis time is determined by the length of S. We show that by introducing redundancy to the synthesized strands, we can significantly decrease the number of synthesis cycles. We derive the maximum amount of information per synthesis cycle assuming S is an arbitrary periodic sequence. To prove our results, we exhibit new connections to cost-constrained codes.

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the Hamming metric, we consider the problem of designing covering codes defined in terms of insertions and deletions. First, we provide new sphere-covering lower bounds on the minimum possible size of such codes. Then, we provide new existential upper bounds on the size of optimal covering codes for a single insertion or a single deletion that are tight up to a constant factor. Finally, we derive improved upper bounds for covering codes using R≥ 2 insertions or deletions. We prove that codes exist with density that is only a factor O(R log R) larger than the lower bounds for all fixed R. In particular, our upper bounds have an optimal dependence on the word length, and we achieve asymptotic density matching the best known bounds for Hamming distance covering codes.

Previous work by the authors on parity-preserving fixed-length constrained encoders is extended to the variable-length case. Parity-preserving variable-length encoders are formally defined, and a necessary and sufficient condition is presented for the existence of deterministic parity-preserving variable-length encoders for a given constraint. Examples are provided that show that there are coding ratios where parity-preserving variable-length encoders exist, while fixed-length encoders do not.

We consider achieving the rates in the capacity region of a multi-level 3-receiver broadcast channel, in which the second receiver is degraded with respect to the first receiver, with degraded message sets. We propose a two-level chaining strategy based on polar codes that achieves the capacity region of the considered setting without time-sharing. We also look at a slight variation of this problem, where the first receiver only requires to decode its own private message and the other two receivers require to decode another private message common to them. We observe that the capacity region does not enlarge and so the proposed polar coding strategy achieves the capacity region for this problem as well.

In this paper, we investigate the use of recurrent neural network (RNN)-based detection of magnetic recording channels with inter-symbol interference (ISI). We refer to the proposed detection method, which is intended for recording channels with partial-response equalization, as Partial-Response Neural Network (PR-NN). We train bi-directional gated recurrent units (bi-GRUs) to recover the ISI channel inputs from noisy channel output sequences and evaluate the network performance when applied to continuous, streaming data. The recording system on which the experiments were conducted uses a rate-2/3, (1,7) runlength-limited (RLL) code with an E2PR4 partial-response channel target. Experimental results with ideal PR signals show that the performance of PR-NN detection approaches that of Viterbi detection in additive white gaussian noise (AWGN). Moreover, the PR-NN detector outperforms Viterbi detection and achieves the performance of Noise-Predictive Maximum Likelihood (NPML) detection in additive colored noise (ACN).

Shaping codes are used to encode information for use on channels with cost constraints. Applications include data transmission with a power constraint and, more recently, data storage on flash memories with a constraint on memory cell wear. In the latter application, system requirements often impose a rate constraint. In this paper, we study rate-constrained fixed-to-variable length shaping codes for noiseless, memoryless costly channels and general i.i.d. sources. The analysis relies on the theory of word-valued sources. We establish a relationship between the code expansion factor - the ratio of the expected codeword length to the length of the input source word - and the minimum average symbol cost. We then determine the expansion factor that minimizes the average cost per source symbol (total cost), corresponding to a conventional optimal source code with cost. An equivalence is established between codes minimizing average symbol cost and codes minimizing total cost, and a separation theorem is proved, showing that optimal shaping can be achieved by a concatenation of optimal compression and optimal shaping for a uniform i.i.d. source. Shaping codes often incorporate, either explicitly or implicitly, some form of non-equiprobable signaling. We use our results to further explore the connections between shaping codes and codes that map a sequence of i.i.d. source symbols into an output sequence of symbols that are approximately independent and distributed according to a specified target distribution, such as distribution matching (DM) codes. Optimal DM codes are characterized in terms of a new performance measure - generalized expansion factor (GEF) - motivated by the costly channel perspective. The GEF is used to study DM codes that minimize informational divergence and normalized informational divergence.

Rate-compatible error-correcting codes (ECCs), which consist of a set of extended codes, are of practical interest in both wireless communications and data storage. In this work, we first study the lower bounds for rate-compatible ECCs, thus proving the existence of good rate-compatible codes. Then, we propose a general framework for constructing rate-compatible ECCs based on cosets and syndromes of a set of nested linear codes. We evaluate our construction from two points of view. From a combinatorial perspective, we show that we can construct rate-compatible codes with increasing minimum distances, and we discuss decoding algorithms and correctable patterns of errors and erasures. From a probabilistic point of view, we prove that we are able to construct capacity-achieving rate-compatible codes, generalizing a recent construction of capacity-achieving rate-compatible polar codes. Applications of rate-compatible codes to data storage are considered. We design two-level rate-compatible codes based on Bose-Chaudhuri-Hocquenghem (BCH) and low-density parity-check (LDPC) codes which are two popular codes widely used in the data storage industry, and then we evaluate the performance of these codes in multi-level cell (MLC) flash memories. We also examine code performance on binary and $q$ -ary symmetric channels. Finally, we briefly discuss two variations of our main construction and their relative performance.

Erasure codes play an important role in storage systems to prevent data loss. In this work, we study a class of erasure codes called Multi-Erasure Locally Recoverable Codes (ME-LRCs) for storage arrays. Compared to previous related works, we focus on the construction of ME-LRCs over small fields. Our main contribution is a general construction of ME-LRCs based on generalized tensor product codes, and an analysis of their erasure-correcting properties. A decoding algorithm tailored for erasure recovery is given, and correctable erasure patterns are identified. We then prove that our construction yields optimal ME-LRCs with a wide range of code parameters, and present some explicit ME-LRCs over small fields. Next, we show that generalized integrated interleaving (GII) codes can be treated as a subclass of generalized tensor product codes, thus defining the exact relation between these codes. Finally, ME-LRCs are investigated in a probabilistic setting. We prove that ME-LRCs based upon a generalized tensor product construction can achieve the capacity of a compound erasure channel consisting of a family of erasure product channels.

A Markov chain approach is applied to determine the capacity of a general class of q-ary ICI-free constrained systems that satisfy an arbitrary count constraint.

Motivated by DNA-based data storage, we investigate a system where digital information is stored in an unordered set of several vectors over a finite alphabet. Each vector begins with a unique index that represents its position in the whole data set and does not contain data. This paper deals with the design of error-correcting codes for such indexed sets in the presence of substitution errors. We propose a construction that efficiently deals with the challenges that arise when designing codes for unordered sets. Using a novel mechanism, called anchoring, we show that it is possible to combat the ordering loss of sequences with only a small amount of redundancy, which allows to use standard coding techniques, such as tensor-product codes to correct errors within the sequences. We finally derive upper and lower bounds on the achievable redundancy of codes within the considered channel model and verify that our construction yields a redundancy that is close to the best possible achievable one. Our results surprisingly suggest that it requires less redundancy to correct errors in the indices than in the data part of vectors.

In this paper, we consider a discrete channel with inter-cell interference (ICI) as a model for NAND flash memory. We derive an explicit formula for the mutual information rate when the input is Markovian. Using this formula, we obtain the asymptotics of the channel capacity in the high signal-to-noise (SNR) regime.

Paved by recent advances in sequencing and synthesis technologies, DNA has evolved to a competitive medium for long-term data storage. In this paper we conduct an information theoretic study of the storage channel-the entity that formulates the relation between stored and sequenced strands. In particular, we derive an upper bound on the Shannon capacity of the channel. In our channel model, we incorporate the main attributes that characterize DNA-based data storage. That is, information is synthesized on many short DNA strands, and each strand is copied many times. Due to the storage and sequencing methods, the receiver draws strands from the original sequences in an uncontrollable manner, where it is possible that copies of the same sequence are drawn multiple times. Additionally, due to imperfections, the obtained strands can be perturbed by errors. We show that for a large range of parameters, the channel decomposes into sub-channels from each input sequence to multiple output sequences, so-called clusters. The cluster sizes hereby follow a Poisson distribution. Furthermore, the ordering of sub-channels is unknown to the receiver. Our results can be used to guide future experiments for DNA-based data storage by giving an upper bound on the achievable rate of any error-correcting code. We further give a detailed discussion and intuitive interpretation of the channel that provide insights about the nature of the channel and can inspire new ideas for error-correcting codes and decoding methods.

Partial MDS (PMDS) codes are a class of erasurecorrecting array codes that combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O (max{m, nr+s}s) is presented for the case where r = O(1), s = O(1).

We study partial orders (POs) for the synthesized bit-channels of polar codes. First, we give an alternative proof of an existing PO for bit-channels with the same Hamming weight and use the underlying idea to extend the bit-channel ordering to some additional cases. In particular, the bit-channel ordering for a given code block length is used to generate additional bit-channel ordering relationships for larger block lengths, generalizing previously known POs. Next, we consider POs especially for the binary erasure channel (BEC). We identify a symmetry property of the Bhattacharyya parameters of complementary bit-channel pairs on the BEC and provide a condition for the alignment of polarized sets of bit-channels for the BEC and general binary-input memoryless symmetric (BMS) channels. Numerical examples and further properties about the POs for the bit-channels with different Hamming weights are provided to illustrate the new POs. The bit-channels with universal ordering positions, which are independent of the channel erasure probability, are verified for all of the code block lengths. Finally, we show the threshold behavior of the Bhattacharyya parameters of some bit-channels by approximating the threshold values. The corresponding value for a bit-channel can be used to determine whether it is good or bad when the underlying channel is known.

Error-correcting codes play an important role in storage systems to maintain data integrity. In this work, we propose a new class of linear error- correcting codes, called ladder codes, whose codeword structure consists of multiple codewords of certain component codes and also their shared redundancy. First, we give a general construction for an m-level ladder code, determine the code length and dimension, and also derive a lower bound d*Lon the minimum distance. Some examples of ladder codes are presented. Then, we study correctable error-erasure patterns of ladder codes and give a corresponding decoding algorithm. Finally, we compare a two-level ladder code with a concatenated code, and show that the former can outperform the latter in many cases. Ladder codes have potential to be used for data protection in flash memories where only a few pages may suffer from severe errors in a block.

In this paper we study error-correcting codes for the storage of data in synthetic deoxyribonucleic acid (DNA). We investigate a storage model where a data set is represented by an unordered set of M sequences, each of length L. Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal.

For a 2-dimensional (2D) Gaussian inter-symbol interference (ISI) channel with discrete input and a 2D discrete memoryless channel with a special class of irreducible constraints, we show that the information capacity is equal to the stationary capacity. As a byproduct, these capacities are shown to be equal to the operational capacity.

Necessary and sufficient conditions are presented for the existence of fixed-rate parity-preserving encoders for a given constraint. It is also shown that under somewhat stronger conditions, the stethering method guarantees an encoder that has finite anticipation.

We present a universal coding scheme, based on polar codes, that can achieve the compound capacity of any finite set of binary-input asymmetric channels. The scheme is a hybrid combination of Honda and Yamamoto's polar coding scheme for asymmetric channels and a universal polar coding scheme for symmetric channels proposed by Hassani and Urbanke. In the proposed universal construction for the asymmetric setting, we exploit the staircase structure in the universal scheme for symmetric channels to define a coding strategy that requires neither storage-intensive shared boolean functions nor a side-channel between encoder and decoder in order to transmit bits corresponding to bit-channels that are not completely polarized.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write n incoming packets and read k outgoing packets while using m memory banks, each able to write and read one packet per time unit. Each set of n packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of k packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case n = k.

Defined through a certain 2 × 2 matrix called Arikan's kernel, polar codes are known to achieve the symmetric capacity of binary-input discrete memoryless channels under the successive cancellation (SC) decoder. Yet, for short block-lengths, polar codes fail to deliver a compelling performance under the low complexity SC decoding scheme. Recent studies provide evidence for improved performance when Arikan's kernel is replaced with larger kernels that have smaller scaling exponents. However, for ℓ×ℓ kernels the time complexity of the SC decoding increases by a factor of 2ℓ. In this paper we study a special type of kernels called permuted kernels. The advantage of these kernels is that the SC decoder for the corresponding polar codes can be viewed as a permuted version of the SC decoder for the conventional polar codes that are defined through Arikan's kernel. This permuted successive cancellation (PSC) decoder outputs its decisions on the input bits according to a permuted order of their indices. We introduce an efficient PSC decoding algorithm and show simulations for two 16 × 16 permuted kernels that have better scaling exponents than Arikan's kernel.

Partial MDS (PMDS) codes are a class of erasure-correcting array codes which combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O(max{m, nr+s}s) is presented.

Data shaping is a coding technique that has been proposed to increase the lifetime of flash memory devices. Several data shaping codes have been described in recent work, including endurance codes [2] and direct shaping codes for structured data [8], [4], [5]. In this paper, we study information-theoretic properties of a general class of data shaping codes and prove a separation theorem stating that optimal data shaping can be achieved by the concatenation of optimal lossless compression with optimal endurance coding. We also determine the expansion factor that minimizes the total wear cost. Finally, we analyze the performance of direct shaping codes and establish a condition for their optimality.

A constrained code is a set of finite-length codewords that entirely avoid the occurrences of certain patterns. In some applications, it may be preferable to merely limit the number of occurrences of certain patterns in codewords rather than to completely forbid them. Constrained codes that involve such weaker constraints are called weakly constrained codes. In this paper we construct capacity-achieving weakly constrained codes. The construction is based on a row-by-row coding scheme in which messages are encoded into the rows of a 2-dimensional array in which the frequency of occurrence of patterns along columns is controlled.

Rate-compatible error-correcting codes (ECCs), which consist of a set of extended codes, are of practical interest in both wireless communications and data storage. In this work, we first study the lower bounds for rate-compatible ECCs, thus proving the existence of good rate-compatible codes. Then, we propose a general framework for constructing rate-compatible ECCs based on cosets and syndromes of a set of nested linear codes. We evaluate our construction from two points of view. From a combinatorial perspective, we show that we can construct rate-compatible codes with increasing minimum distances. From a probabilistic point of view, we prove that we are able to construct capacity-achieving rate-compatible codes.

Inter-cell interference (ICI) is a significant cause of errors in flash memories. In single-level cell (SLC) flash memory, ICI arises when 1 0 1 patterns are programmed either in the horizontal or vertical directions. Since data pages are written sequentially in horizontal wordlines, one can mitigate the effects of horizontal ICI by applying conventional constrained codes that forbid the 1 0 1 pattern. This approach does not address the problem of vertical ICI, however. In this paper, a row-by-row coding technique that eliminates vertical 1 0 1 patterns while preserving the sequential wordline programming order is presented. This scheme, though efficient, necessarily suffers a rate loss of almost 20%. We therefore propose another coding scheme, combining a weak constraint on vertical 1 0 1 patterns with a systematic error-correcting code, that can mitigate vertical ICI errors while achieving a higher overall coding rate, provided that the vertical ICI error probability is sufficiently small. Some extensions for multi-level cell (MLC) flash memory are discussed as well.

Multitrack detection with array-head reading is a promising technique proposed for next generation magnetic storage systems. The multihead multitrack (MHMT) system is characterized by intersymbol interference in the downtrack direction and intertrack interference (ITI) in the crosstrack direction. Constructing the trellis of a MHMT maximum likelihood (ML) detector requires knowledge of the ITI, which is generally unknown at the receiver. Furthermore, in a time-varying ITI environment, updating ML trellis labels using adaptively-generated ITI estimates could incur significant delay. In this paper, we propose one approach to solve these issues. The proposed detector uses a different trellis structure whose output labels are independent of the ITI level, with ITI-dependence appearing only in a scale factor used to suitably weight the computed path metrics in order to retain ML optimality. The detector formulation facilitates the design of a gain loop structure that can track the time-varying ITI and provide ITI estimates to adaptively adjust the weights in the path metric evaluation. Simulation results show that the proposed detector architecture with ITI estimation offers a substantial performance advantage over ML detection using a static ITI estimate.

To achieve large storage capacity on magnetic hard disk drives, very high track density is required, causing severe intertrack interference (ITI). Multihead multitrack (MHMT) detection has been proposed to better combat the effects of ITI. Such detection, however, has prohibitive implementation complexity. Reduced-state sequence estimation (RSSE) is a promising technique for significantly reducing the complexity, while retaining good performance. In this paper, several different MHMT models are considered, including symmetric and asymmetric 2H2T systems, and a symmetric 3H3T system. By carefully evaluating the effective distance between two input symbols, we propose optimized set partition trees for each channel model. Different trellis configurations for RSSE are constructed based on the desired performance/complexity tradeoff. Simulation results show that the reduced MHMT detector can achieve near maximum-likelihood (ML) performance with a small fraction of the original number of trellis states. We also use error event analysis to explain the behavior of RSSE. The proposed algorithm could be potentially applied to next generation magnetic recording systems, especially when the ML detector is infeasible due to the high computational complexity.

In this work, we study data shaping codes for flash memory. We first review a recently proposed direct shaping code for SLC (one bit per cell) flash memory that reduces wear by minimizing the average fraction of programmed cells. Then we describe an adaptation of this algorithm that provides data shaping for MLC (two bits per cell) flash memory. It makes use of a page- dependent cost model and is designed to be compatible with the standard procedure of row-by- row, page-based, wordline programming. We also give simulation results demonstrating the performance of these data shaping codes when applied to English language text. Finally, we use a random walk model to analyze the potential error propagation properties of direct shaping codes when used in a noisy memory.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch consists of n input ports, k output ports, and m banks which store new arriving packets from the input ports in each time slot, called a generation. The objective is to store the packets in the banks such that every request of k packets by the output ports, which can be from previous generations, can be handled by reading at most one packet from every bank. In this paper we study a new type of switch codes that can simultaneously deliver large symbol requests and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Lastly, we introduce a construction of switch codes for the case n = k, which improves upon the best known results for this case.

In this work, we study the performance of different decoding schemes for multilevel flash memories where each page in every block is encoded independently. We focus on the multi-level cell (MLC) flash memory, which is modeled as a two-user multiple access channel suffering from asymmetric noise. The uniform rate regions and sum rates of Treating Interference as Noise (TIN) decoding and Successive Cancelation (SC) decoding are investigated for a Program/Erase (P/E) cycling model and a data retention model. We examine the effect of different binary labelings of the cell levels, as well as the impact of further quantization of the memory output (i.e., additional read thresholds). Finally, we extend our analysis to the three-level cell (TLC) flash memory.

The papers in this special issue address the topic of capacity approaching codes. This issue reflects a further shift of interest in coding theory research, this time toward polar codes, a new class of capacity achieving codes introduced in 2008. Of the 17 papers appearing in this issue, 9 are devoted to various aspects of polar codes, with 6 papers devoted to LDPC codes, including 3 on spatially coupled (convolutional) LDPC codes, and 2 on other coding topics.

In this paper, we study the performance of different decoding schemes for multilevel flash memories where each page in every block is encoded independently. We focus on multi-level cell flash memory, which is modeled as a two-user multiple-access channel suffering from asymmetric noise. The uniform rate regions and sum rates of treating interference as noise decoding and successive cancelation decoding are investigated for a program/erase cycling model and a data retention model. We examine the effect of different binary labelings of the cell levels, as well as the impact of further quantization of the memory output (i.e., additional read thresholds). Finally, we extend our analysis to the three-level cell flash memory.

The beta-binomial (BBM) channel model was recently proposed to model the overdispersed statistics of empirically observed bit errors in multi-level cell (MLC) flash memories. In this paper, we study the capacity of the BBM channel model for MLC flash memories. Using the compound channel approach, we first show that the BBM channel model capacity is zero. However, through empirical observation, this appears to be a very pessimistic estimate of the flash memory channel capacity. We propose a refined channel model called the truncated-support BBM (TS-BBM) channel model and derive its capacity. Using empirical error statistics from 1X-nm and 2Y-nm MLC flash memories, we numerically estimate the TS-BBM channel model capacity as a function of the program/erase cycling stress. The capacity of the 2-TS-BBM channel model provides an upper bound on the coding rates for the flash memory chip assuming a single binary error correction code is used.

We propose binary discrete parametric channel models for multi-level cell (MLC) flash memories that provide accurate error-correcting code (ECC) performance estimation by modeling the empirically observed error characteristics under program/erase cycling stress. Through a detailed empirical error characterization of 1X-nm and 2Y-nm MLC flash memory chips from two different vendors, we observe and characterize the overdispersion phenomenon in the number of bit errors per ECC frame. A well-studied channel model, such as the binary asymmetric channel model, is unable to provide accurate ECC performance estimation. Hence, we propose a channel model based on the beta-binomial probability distribution [2-beta-binomial (2-BBM) channel model], which is a good fit for the overdispersed empirical error characteristics, and show through statistical tests and simulation results for BCH, low density parity check, and polar codes, that the 2-BBM channel model provides accurate ECC performance estimation in MLC flash memories.

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size q, i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this paper, we present an upper bound on the minimum distance d of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. Then, we study the binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed-Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared with other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, the availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code.

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.

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH, the corresponding minimum pair distance is at least dH+3. In this paper, we show that, for a given linear cyclic code with a minimum Hamming distance dH, the minimum pair distance is at least dH+ (dH/2). We then describe a decoding algorithm, based upon a bounded distance decoder for the cyclic code, whose symbol-pair error correcting capabilities reflect the larger minimum pair distance. Finally, we consider the case where the read channel output is a larger number, b ≥3, of consecutive symbols, and we provide extensions of several concepts, results, and code constructions to this setting.

Multitrack detection for shingled magnetic recording (SMR) using a two-head array system is considered. The channel suffers from intersymbol interference (ISI) in the down-track direction and intertrack interference (ITI) in the crosstrack direction. We propose a practical multihead/multitrack detector that provides a low-complexity approach to adaptive estimation of time-varying ITI. The performance of the proposed detection algorithm is analyzed in terms of its minimum distance parameter, and simulation results show that the proposed detector offers a performance advantage in settings where complexity constraints limit the maximum-likelihood two-track detector to use a static ITI estimate.

With an aim to characterize, model and understand the types of errors caused by the inter-cell interference (ICI) effect in flash memories, we perform a series of program/erase (P/E) cycling experiments designed to quantify the effects of ICI. We create a database of errors at various levels of granularity such as bit, cell, page, block and record the neighborhood data patterns of cells in error to provide a quantitative understanding of the underlying channel model in multi-level cell (MLC) flash memories. We then utilize this empirical data to model and study the flash memory channel as a time-varying 4-ary discrete memoryless channel (DMC). We also present results from experiments to quantify the error rate performance gain obtained by the use of constrained codes, which prevent some ICI-susceptible data patterns from being written to the flash memory.

Inter-cell interference (ICI) is a significant cause of errors in flash memories. In two-level (SLC) flash memory, ICI arises when 1 0 1 patterns are programmed either in the horizontal or vertical directions. Since data pages are written sequentially in horizontal wordlines, one can mitigate the effects of horizontal ICI by use of conventional constrained codes that forbid the 1 0 1 pattern. This approach does not address the problem of vertical ICI, however. In this work, we present a row-by-row coding technique that eliminates vertical 1 0 1 patterns while preserving the sequential wordline programming order. This scheme, though efficient, necessarily suffers a rate loss of almost 20%. We therefore propose another coding scheme, combining a relaxed constraint on vertical 1 0 1 patterns with a systematic error correcting code, that can mitigate vertical ICI errors while achieving a higher overall code rate, provided that the vertical ICI error probability is sufficiently small.

In this work, we present a new upper bound on the minimum distance d of linear locally repairable codes (LRCs) with information locality and availability. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. We use tensor product codes to construct several families of LRCs with information locality, and then we extend the construction to design LRCs with information locality and availability. Some of these codes are shown to be optimal with respect to their minimum distance, achieving the new bound. Finally, we study the all-symbol locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check (LDPC) codes. We also investigate their optimality using the new bound.

Polar codes provably achieve the capacity of binary memoryless symmetric (BMS) channels with low complexity encoding and decoding algorithms, and their finite-length performance on these channels, when combined with suitable decoding algorithms (such as list decoding) and code modifications (such as a concatenated CRC code), has been shown in simulation to be competitive with that of LDPC codes. However, magnetic recording channels are generally modeled as binary-input intersymbol interference (ISI) channels, and the design of polar coding schemes for these channels remains an important open problem. Current magnetic hard disk drives use LDPC codes incorporated into a turbo-equalization (TE) architecture that combines a soft-output channel detector with a soft-input, soft-output sum-product algorithm (SPA) decoder. An interleaved coding scheme with a multistage decoding (MSD) architecture with LDPC codes as component codes has been proposed as an alternative to TE for ISI channels. In this work, we investigate the use of polar codes as component codes in the TE and MSD architectures. It is shown that the achievable rate of the MSD scheme converges to the symmetric information rate of the ISI channel when the number of interleaves is large. Simulations results comparing the performance of LDPC codes and polar codes in TE and MSD architectures are presented.

Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size q, i.e., the size of the code alphabet. In particular, for the binary case, only a few specific results are known by Goparaju and Calderbank. Recently, however, an upper bound on the dimension k of LRCs was presented by Cadambe and Mazumdar. The bound takes into account the length n, minimum distance d, locality r, and field size q, and it is applicable to both non-linear and linear codes. In this work, we first develop an improved version of the bound mentioned above for linear codes. We then focus on cyclic linear binary codes. By leveraging the cyclic structure, we notice that the locality of such a code is determined by the minimum distance of its dual code. Using this result, we investigate the locality of a variety of well known cyclic linear binary codes, e.g., Hamming codes and Simplex codes, and also prove their optimality with our improved bound for linear codes. We also discuss the locality of codes which are obtained by applying the operations of Extend, Shorten, Expurgate, Augment, and Lengthen to cyclic linear binary codes. Several families of such modified codes are considered and their optimality is addressed. Finally, we investigate the locality of Reed-Muller codes. Even though they are not cyclic, it is shown that some of the locality results for cyclic codes still apply.

A primary source of increased read time on NAND flash comes from the fact that, in the presence of noise, the flash medium must be read several times using different read threshold voltages for the decoder to succeed. This paper proposes an algorithm that uses a limited number of rereads to characterize the noise distribution and recover the stored information. Both hard and soft decoding are considered. For hard decoding, this paper attempts to find a read threshold minimizing bit error rate (BER) and derives an expression for the resulting codeword error rate. For soft decoding, it shows that minimizing BER and minimizing codeword error rate are competing objectives in the presence of a limited number of allowed rereads, and proposes a tradeoff between the two. The proposed method does not require any prior knowledge about the noise distribution but can take advantage of such information when it is available. Each read threshold is chosen based on the results of previous reads, following an optimal policy derived through a dynamic programming backward recursion. The method and results are studied from the perspective of an SLC Flash memory with Gaussian noise, but this paper explains how the method could be extended to other scenarios.

The bit-channels of finite-length polar codes are not fully polarized, and a proportion of such bit-channels are neither completely “noiseless” nor completely “noisy”. By using an outer low-density parity-check code for these intermediate channels, we show how the performance of belief propagation (BP) decoding of the overall concatenated polar code can be improved. A simple example reports an improvement in Ebover N0of 0.3 dB with respect to the conventional BP decoder.

In this paper, we consider the joint coding constraint of forbidding the 101 subsequence and requiring all codewords to have the same Hamming weight. These two constraints are particularly applicable to SLC flash memory - the first constraint mitigates the problem of inter-cell interference, while the second constraint helps to alleviate the problems that arise from voltage drift of programmed cells. We give a construction for codes that satisfy both constraints, then analyze properties of best-case codes that can come from this construction.

Polar codes are high density parity check codes and hence the sparse factor graph, instead of the parity check matrix, has been used to practically represent an LP polytope for LP decoding. Although LP decoding on this polytope has the ML-certificate property, it performs poorly over a BAWGN channel. In this paper, we propose modifications to adaptive cut generation based LP decoding techniques and apply the modified-adaptive LP decoder to short block-length polar codes over a BAWGN channel. The proposed decoder provides significant FER performance gain compared to the previously proposed LP decoder and its performance approaches that of ML decoding at high SNRs. We also present an algorithm to obtain a smaller factor graph from the original sparse factor graph of a polar code. This reduced factor graph preserves the small check node degrees needed to represent the LP polytope in practice. We show that the fundamental polytope of the reduced factor graph can be obtained from the projection of the polytope represented by the original sparse factor graph and the frozen bit information. Thus, the LP decoding time complexity is decreased without changing the FER performance by using the reduced factor graph representation.

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.

Inter-cell interference (ICI) is one of the main obstacles to precise programming (i.e., writing) of a flash memory. In the presence of ICI, the voltage level of a cell might increase unexpectedly if its neighboring cells are programmed to high levels. For q-ary cells, the most severe ICI arises when three consecutive cells are programmed to levels high - low - high, represented as (q-1)0(q-1), resulting in an unintended increase in the level of the middle cell and the possibility of decoding it incorrectly as a nonzero value. ICI-free codes are used to mitigate this phenomenon by preventing the programming of any three consecutive cells as (q-1)0(q-1). In this work, we extend ICI-free codes in two directions. First, we consider binary balanced ICI-free codes which, in addition to forbidding the 101 pattern, require the number of 0 symbols and 1 symbols to be the same. Using combinatorial methods, we determine the asymptotic information rate of these codes and show that the asymptotic rate loss due to the imposition of the balanced property is approximately 2%. Extensions to q-ary cells, for q > 2 are also discussed. Next, we consider q-ary ICI-free write-once-memory (WOM) codes that support multiple writes of a WOM while mitigating ICI effects. These codes forbid the appearance of the (q-1)0(q-1) pattern in any codeword used in any writing step. Using properties of two-dimensional constrained codes and generalized WOMs, we characterize the maximum sum-rate of t-write ICI-free WOM codes or, equivalently, the t-write sum-capacity of an ICI-free WOM.

The error floor phenomenon observed with LDPC codes and their graph-based, iterative, message-passing (MP) decoders is commonly attributed to the existence of error-prone substructures - variously referred to as near-codewords, trapping sets, absorbing sets, or pseudocodewords - in a Tanner graph representation of the code. Many approaches have been proposed to lower the error floor by designing new LDPC codes with fewer such substructures or by modifying the decoding algorithm. Using a theoretical analysis of iterative MP decoding in an idealized trapping set scenario, we show that a contributor to the error floors observed in the literature may be the imprecise implementation of decoding algorithms and, in particular, the message quantization rules used. We then propose a new quantization method - (q+1)-bit quasi-uniform quantization - that efficiently increases the dynamic range of messages, thereby overcoming a limitation of conventional quantization schemes. Finally, we use the quasi-uniform quantizer to decode several LDPC codes that suffer from high error floors with traditional fixed-point decoder implementations. The performance simulation results provide evidence that the proposed quantization scheme can, for a wide variety of codes, significantly lower error floors with minimal increase in decoder complexity.

This paper addresses the prediction of error floors of low-density parity-check codes transmitted over the additive white Gaussian noise channel. Using a linear state-space model to estimate the behavior of the sum-product algorithm (SPA) decoder in the vicinity of trapping sets (TSs), we study the performance of the SPA decoder in the log-likelihood ratio (LLR) domain as a function of the LLR saturation level. When applied to several widely studied codes, the model accurately predicts a significant decrease in the error floor as the saturation level is allowed to increase. For nonsaturating decoders, however, we find that the state-space model breaks down after a small number of iterations due to the strong correlation of LLR messages. We then revisit Richardson's importance-sampling methodology for estimating error floors due to TSs when those floors are too low for Monte Carlo simulation. We propose modifications that account for the behavior of a nonsaturating decoder and present the resulting error floor estimates for the Margulis code. These estimates are much lower, significantly steeper, and more sensitive to iteration count than those previously reported.

Multilevel flash memory contains blocks of cells that represent data by the amount of charge stored in them. The cell writing - or programming - process applies specified voltages in a sequential manner, injecting charge to achieve a desired level. Reducing a cell level requires a costly block erasure, so programming only increases cell levels. Parallel programming, whereby a common voltage is applied to a group of cells to inject charge simultaneously, simplifies circuitry and increases programming speed. However, cell-to-cell variations and limited programming round can adversely affect its precision. In this paper, we consider algorithms for efficient cell programming. Since cell levels are quantized to a discrete set of values, our objective is to minimize the number of cells that are not quantized to their target levels. For a specified number of programming rounds, we derive an optimal parallel programming algorithm with complexity that is polynomial in the number of cells. We extend the algorithm to account for intercell interference, where the voltage applied to a cell can affect the level of adjacent cells. We then consider noisy programming of a single cell, with and without feedback about the cell level. In both scenarios, we present an algorithm that, for a given number of programming rounds, minimizes the probability of an incorrect cell level.

Flash memory is a nonvolatile computer memory comprising blocks of cells, wherein each cell can take on$q$different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes—known as floating codes (or flash codes) and buffer codes—have been designed in order to maximize the number of times that information stored in a flash memory can be written (and rewritten) prior to incurring a block erasure. An$(n,k,t)_{q}$flash code$\BBC$is a coding scheme for storing$k$information bits in$n$cells in such a way that any sequence of up to$t$writes can be accommodated without a block erasure. The total number of available level transitions in$n$cells is$n(q{-}1)$, and the write deficiency of$\BBC$, defined as$\delta (\BBC)=n(q{-}1)-t$, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency$O(qk\log k)$if$q\geqslant\log_{2}k$, and at most$O(k\log^{2}k)$otherwise. An$(n,r,\ell,t)_{q}$buffer code is a coding scheme for storing a buffer of$r~\ell$-ary symbols such that for any sequence of$t$symbols, it is possible to successfully decode the last$r$symbols that were written. We improve upon a previous upper bound on the maximum number of writes$t$in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiangthat uses multiple cells, where$n\geqslant 2r$.

Rank modulation is a technique for representing stored information in an ordered set of flash memory cells by a permutation that reflects the ranking of their voltage levels. In this paper, we consider two figures of merit that can be used to compare parallel programming algorithms for rank modulation. These two criteria represent different tradeoffs between the programming speed and the lifetime of flash memory cells. In the first scenario, we want to find the minimum number of programming rounds required to increase a specified cell-level vector ℓ0to a cell-level vector corresponding to a target rank permutation τ, with no restriction on the maximum allowable cell level. We derive lower and upper bounds on this number, denoted by t∗1(τ, ℓ0). In the second scenario, we seek an efficient programming strategy to achieve a cell-level vector ℓ(τ) consistent with the target permutation τ, such that the maximum cell level after programming is minimized. Equivalently, this strategy maximizes the number of information update cycles supported by the device before requiring a block erasure. We derive upper bounds on the minimum number of programming rounds required to achieve cell-level vector ℓ(τ), denoted by t∗1(τ, ℓ0), and propose a programming algorithm for which the resultant number of programming rounds is close to t∗2(τ, ℓ0).

In this paper, we propose an efficient message-passing algorithm to solve the LP decoding problem. This algorithm is based on the alternating direction method of multipliers (ADMM), a classic technique in convex optimization theory that is designed for parallel implementation. The computational complexity of ADMM-based LP decoding is largely determined by the method used to project a vector of real values to the parity polytope of a given parity check. The key contribution of this paper is a novel, efficient projection algorithm that can substantially improve the decoding speed of the ADMM-based LP decoder.

Recent work by Divsalarhas shown that properly designed protograph-based low-density parity-check codes typically have minimum (Hamming) distance linearly increasing with block length. This fact rests on ensemble arguments over all possible expansions of the base protograph. However, when implementation complexity is considered, the expansions are frequently selected from a smaller class of structured expansions. For example, protograph expansion by cyclically shifting connections generates a quasi-cyclic (QC) code. Other recent work by Smarandache and Vontobel has provided upper bounds on the minimum distance of QC codes. In this paper, we generalize these bounds to punctured QC codes and then show how to tighten these for certain classes of codes. We then evaluate these upper bounds for the family of protograph codes known as AR4JA codes that have been recommended for use in deep space communications in a standard established by the Consultative Committee for Space Data Systems. At block lengths larger than 4400 bits, these upper bounds fall well below the ensemble lower bounds.

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.

Phase-change memory (PCM) is a promising nonvolatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells (i.e., changing cell levels), to balance the heat both in time and in space. In this paper, we study the time-space constraint for PCM, which was originally proposed by Jiang and coworkers. A code is called an (α, β, p)- constrained code if for any α consecutive rewrites and for any segment of β contiguous cells, the total rewrite cost of the β cells over those α rewrites is at most p. Here, the cells are binary and the rewrite cost is defined to be the Hamming distance between the current and next memory states. First, we show a general upper bound on the achievable rate of these codes which extends the results of Jiang and coworkers. Then, we generalize their construction for (α ≥ 1, β = 1, p = 1)-constrained codes and show another construction for (α = 1, β ≥ 1, p ≥ 1)-constrained codes. Finally, we show that these two constructions can be used to construct codes for all values of α, β, and p.

Numerical issues related to the occurrence of error floors in floating-point simulations of belief propagation (BP) decoders are examined. Careful processing of messages corresponding to highly-certain bit values can sometimes reduce error floors by several orders of magnitude. Computational solutions for properly handling such messages are provided for the sum-product algorithm (SPA) and several variants.

On NAND flash, a primary source of increased read time comes from the fact that in the presence of noise, the flash medium must be read several times using different read threshold voltages to find the optimal read location, which minimizes bit-error-rate. This paper proposes an algorithm to estimate the optimal read threshold in a fast manner using a limited number of re-reads. Then it derives an expression for the resulting BER in terms of the minimum possible BER. It is also shown that minimizing BER and minimizing codeword-error-rate are competing objectives in the presence of a limited number of allowed re-reads, and a tradeoff between the two is proposed.

Multi-level flash memory cells represent data by the amount of charge stored in them. Certain voltages are applied to the flash memory cells to inject charges when programming and the cell level can be only increased during the programming process as a result of the high cost of block erasures. To achieve a high speed during writing, parallel programming is used, whereby a common voltage is applied to a group of cells to inject charges simultaneously. The voltage sharing simplifies the circuitry and increases the programming speed, but it also affects the precision of charge injection and limits the storage capacity of flash memory cells. Another factor that limits the precision of cell programming is the thermal electronics noise induced in charge injection. In this paper, we focus on noiseless parallel programming of multiple cells and noisy programming of a single cell. We propose a new criterion to evaluate the performance of the cell programming which is more suitable for flash memories in practice and then we optimize the parallel programming strategy accordingly. We then proceed to noisy programming and consider the two scenarios where feedback on cell levels is either available during programming or not. We study the optimization problem under both circumstances and present algorithms to achieve the optimal performance.

Write-once memory (WOM) is a binary storage medium in which each memory cell is initially in state 0 and can be irreversibly programmed to state 1. This paper studies the problem of writing multiple messages into a WOM. Instead of writing a new message (and obliterating old ones) as in the traditional setup, the user wishes to retain access to some of the previously written messages. The capacity region is studied and code constructions are proposed for three canonical cases.

Symbol-pair read channels, in which the outputs of the read process are pairs of consecutive symbols, were recently studied by Cassuto and Blaum. This new paradigm is motivated by the limitations of the reading process in high density data storage systems. They studied error correction in this new paradigm, specifically, the relationship between the minimum Hamming distance of an error correcting code and the minimum pair distance, which is the minimum Hamming distance between symbol-pair vectors derived from codewords of the code. It was proved that for a linear cyclic code with minimum Hamming distance dH, the corresponding minimum pair distance is at least dH+ 3. Our main contribution is proving that, for a given linear cyclic code with a minimum Hamming distance dH, the minimum pair distance is at least dH+ [dH/2]. We also describe decoding algorithms, based upon bounded distance decoders for the cyclic code, whose pair-symbol error correcting capabilities reflects the larger minimum pair distance. In addition, we consider the case where a read channel output is a prescribed number, b >; 2, of consecutive symbols and provide some generalizations of our results. We note that the symbol-pair read channel problem is a special case of the sequence reconstruction problem that was introduced by Levenshtein.

The error floor phenomenon observed with LDPC codes and their graph-based, iterative, message-passing (MP) decoders is commonly attributed to the existence of error-prone substructures in a Tanner graph representation of the code. Many approaches have been proposed to lower the error floor by designing new LDPC codes with fewer such substructures or by modifying the decoding algorithm. In this paper, we show that one source of the error floors observed in the literature may be the message quantization rule used in the iterative decoder implementation. We then propose a new quantization method to overcome the limitations of standard quantization rules. Performance simulation results for two LDPC codes commonly found to have high error floors when used with the fixed-point min-sum decoder and its variants demonstrate the validity of our findings and the effectiveness of the proposed quantization algorithm.

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.

A write-once memory (WOM) is a storage device that consists of cells that can take on$q$values, with the added constraint that rewrites can only increase a cell's value. A length-$n$,$t$-write WOM-code is a coding scheme that allows$t$messages to be stored in$n$cells. If on the$i$th write we write one of$M_{i}$messages, then the rate of this write is the ratio of the number of written bits to the total number of cells, i.e.,$\log_{2}M_{i}/n$. The sum-rate of the WOM-code is the sum of all individual rates on all writes. A WOM-code is called a fixed-rate WOM-code if the rates on all writes are the same, and otherwise, it is called a variable-rate WOM-code. We address two different problems when analyzing the sum-rate of WOM-codes. In the first one, called the fixed-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate WOM-codes, and in the second problem, called the unrestricted-rate WOM-code problem, the sum-rate is analyzed over all fixed-rate and variable-rate WOM-codes. In this paper, we first present a family of two-write WOM-codes. The construction is inspired by the coset coding scheme, which was used to construct multiple-write WOM-codes by Cohenand recently by Wu, in order to construct from each linear code a two-write WOM-code. This construction improves the best known sum-rates for the fixed- and unrestricted-rate WOM-code problems. We also show how to take advantage of two-write WOM-codes in order to construct codes for the Blackwell channel. The two-write construction is generalized for two-write WOM-codes with$q$levels per cell, which is used with ternary cells to construct three- and four-write binary WOM-codes. This construction is used recursively in order to generate a family of$t$-write WOM-codes for all$t$. A further generalization of these$t$-write WOM-codes yields additional families of efficient WOM-codes. Finally, we show a recursive method that uses the previously constructed WOM-codes in order to construct fixed-rate WOM-codes. We conclude and show that the WOM-codes constructed here outperform all previously known WOM-codes for$2\leqslant t\leqslant 10$for both the fixed- and unrestricted-rate WOM-code problems.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs include punch cards and optical disks. WOM-codes, introduced by Rivest and Shamir, permit the reuse of a WOM by taking into account the location of cells that have already been changed to the one state. The objective in designing WOM-codes is to use the fewest number of cells to store a specified number of information bits in each of several reuses of the memory. An [n,k,t] WOM-code C is a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The rate of C, defined by R(C) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions correcting a single cell-error were presented by Zemor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-code with a better rate. Our construction can be adapted also for single-error-detection, double-error-correction, and triple-error-correction. For the last case, we use triple-error-correcting BCH-like codes, which were presented by Kasami and more recently described again by Bracken and Helleseth. Finally, we show two constructions that can be combined for the correction of an arbitrary number of errors.

Linear programming (LP) decoding approximates maximum-likelihood (ML) decoding of a linear block code by relaxing the equivalent ML integer programming (IP) problem into a more easily solved LP problem. The LP problem is defined by a set of box constraints together with a set of linear inequalities called “parity inequalities” that are derived from the constraints represented by the rows of a parity-check matrix of the code and can be added iteratively and adaptively. In this paper, we first derive a new necessary condition and a new sufficient condition for a violated parity inequality constraint, or “cut,” at a point in the unit hypercube. Then, we propose a new and effective algorithm to generate parity inequalities derived from certain additional redundant parity check (RPC) constraints that can eliminate pseudocodewords produced by the LP decoder, often significantly improving the decoder error-rate performance. The cut-generating algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. We also design two variations of the proposed decoder to make it more efficient when it is combined with the new cut-generating algorithm. Simulation results for several low-density parity-check (LDPC) codes demonstrate that the proposed decoding algorithms significantly narrow the performance gap between LP decoding and ML decoding.

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.

Phase-change memory (PCM) is a promising non- volatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells, to balance the heat both in time and space. In this paper, we study the time-space constraint for PCM, which was recently proposed by Jiang et al. A code is called an (α, β, p)-constrained code if for any tx consecutive rewrites and for any segment of β contiguous cells, the total rewrite cost of the β cells over those a rewrites is at most p. Here, the cells are binary and the rewrite cost is defined to be the Hamming distance between the current and next memory states. First, we show a general upper bound on the achievable rate of these codes which extends the results of Jiang et al. Then, we generalize their construction for (α ≥ 1,β = 1,p = 1)-constrained codes and show another construction for (α = 1, β ≥, p≥1)- constrained codes. Finally, these two constructions are used to construct codes for all values of α, β, and p.

Exhaustively enumerating all small error-prone sub structures in arbitrary, finite-length low-density parity-check (LDPC) codes has been proven to be NP-complete. In this paper, we present two exhaustive search algorithms to find such small error-prone substructures of an arbitrary LDPC code given its parity-check matrix. One algorithm is guaranteed to find all error-prone substructures including stopping sets, trapping sets, and absorbing sets, which have no more than αmaxvariable nodes and up to bmaxinduced odd-degree neighboring check nodes. The other algorithm is specially designed to find fully absorbing sets (FAS). Numerical results show that both of our proposed algorithms are more efficient in terms of execution time than another recently proposed exhaustive search algorithm [13]. Moreover, by properly initialization of the algorithm, the efficiency can be further improved for quasi-cyclic (QC) codes.

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.

In multi-level flash memories, the dominant cell errors are asymmetric with limited-magnitude. With such an error model in mind, Cassuto et al. recently developed bounds and constructions for codes correcting t asymmetric errors with magnitude no more than ℓ. However, a more refined model of these memory devices reflects the fact that typically only a small number of errors have large magnitude while the remainder are of smaller magnitude. In this work, we study such an error model, in which at most t1errors of maximum magnitude ℓ1and at most t2errors of maximum magnitude ℓ2, with ℓ12, can occur. We adapt the analysis and code construction of Cassuto, et al. for the refined error model and assess the relative efficiency of the new codes. We then consider in more detail specific constructions for the case where t1= t2= 1, ℓ1= 1, and ℓ2>; 1.

Linear programming (LP) decoding approximates optimal maximum-likelihood (ML) decoding of a linear block code by relaxing the equivalent ML integer programming (IP) problem into a more easily solved LP problem. The LP problem is defined by a set of linear inequalities derived from the constraints represented by the rows of a parity-check matrix of the code. Adaptive linear programming (ALP) decoding significantly reduces the complexity of LP decoding by iteratively and adaptively adding necessary constraints in a sequence of smaller LP problems. Adaptive introduction of constraints derived from certain additional redundant parity check (RPC) constraints can further improve ALP performance. In this paper, we propose a new and effective algorithm to identify RPCs that produce linear constraints, referred to as “cuts,” that can eliminate non-ML solutions generated by the ALP decoder, often significantly improving the decoder error-rate performance. The cut-finding algorithm is based upon a specific transformation of an initial parity-check matrix of the linear block code. Simulation results for several low-density parity-check codes demonstrate that the modified ALP decoding algorithm significantly narrows the performance gap between LP decoding and ML decoding.

A Write-Once Memory (WOM)-code is a coding scheme that allows information to be written in a memory block multiple times, but in a way that the stored values are not decreased across writes. This work studies non-binary WOM-codes with applications to flash memory. We present two constructions of non-binary WOM-codes that leverage existing high sum-rate WOM-codes defined over smaller alphabets. In many instances, these constructions provide the highest known sum-rates of the non-binary WOM-codes. In addition, we introduce a new class of codes, called level distance WOM-codes, which mitigate the difficulty of programming a flash memory cell by eliminating all small-magnitude level increases. We show how to construct such codes and state an upper bound on their sum-rate.

We study the class of periodic-finite-type (PFT) shift spaces, which can be used to model time-varying constrained codes used in digital magnetic recording systems. A PFT shift is determined by a finite list of periodically forbidden words. We show that the class of PFT shifts properly contains all finite-type (FT) shifts, and the class of almost finite-type (AFT) shifts properly contains all PFT shifts. We establish several basic properties of PFT shift spaces of a given period$T$, and provide a characterization of such a shift in terms of properties of its Shannon cover (i.e., its unique minimal, deterministic, irreducible graph presentation). We present an algorithm that, given the Shannon cover${\cal G}$of an irreducible sofic shift$X$, decides whether or not$X$is PFT in time that is quadratic in the number of states of${\cal G}$. From any periodic irreducible presentation of a given period, we define a periodic forbidden list, unique up to conjugacy (a circular permutation) for that period, that satisfies certain minimality properties. We show that an irreducible sofic shift is PFT if and only if the list corresponding to its Shannon cover${\cal G}$and its period is finite. Finally, we discuss methods for computing the capacity of a PFT shift from a periodic forbidden list, either by construction of a corresponding graph or in a combinatorial manner directly from the list itself.

We propose a new graph representation for ISI channels that can be used for combined equalization and decoding by linear programming (LP) or iterative message-passing (IMP) decoding algorithms. We derive this graph representation by linearizing the ML detection metric, which transforms the equalization problem into a classical decoding problem. We observe that the performance of LP and IMP decoding on this model are very similar in the uncoded case, while IMP decoding significantly outperforms LP decoding when low-density parity-check (LDPC) codes are used. In particular, in the absence of coding, for certain classes of channels, both LP and IMP algorithms always find the exact ML solution using the proposed graph representation, without complexity that is exponential in the size of the channel memory. This applies even to certain two-dimensional ISI channels. However, for some other channel impulse responses, both decoders have nondiminishing probability of failure as SNR increases. We provide analytical explanations for many of these observations. In addition, we study the error events of LP decoding in the uncoded case, and derive a measure that can be used to classify ISI channels in terms of the performance of the proposed detection scheme.

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.

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.

Recent work has shown that properly designed protograph-based LDPC codes may have minimum distance linearly increasing with block length. This notion rests on ensemble arguments over all possible expansions of the base protograph. When implementation complexity is considered, the expansion is typically chosen to be quite orderly. For example, protograph expansion by cyclically shifting connections creates a quasi-cyclic (QC) code. Other recent work has provided upper bounds on the minimum distance of QC codes. In this paper, these bounds are expanded upon to cover puncturing and tightened in several specific cases. We then evaluate our upper bounds for the most prominent protograph code thus far, one proposed for deep-space usage in the CCSDS experimental standard, the code known as AR4JA.

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.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. WOM-codes were first presented by Rivest and Shamir and are designed for efficiently storing and updating data in the WOM. A WC[n, k, t] WOM-Code CWis a coding scheme for storing k information bits in n cells t times. At each write, the state of each cell can be changed, provided that the cell is changed from the zero state to the one state. The WOM-Rate of CW, defined to be Rt(CW) = kt/n, indicates the total amount of information that is possible to store in a cell in t writes. Two WOM-code constructions that can correct a single cell-error were presented by Zémor and Cohen. In this paper, we present another construction of a single-error-correcting WOM-codes with a better WOM-rate. Our construction can be adjusted also for single-error-detection, double-error-correction, and triple-error-correction. For the latter case, we use triple-error-correcting BCH-like codes, which were showed by Kasami and more recently described again by Bracken and Helleseth.

Parallel programming is an important tool used in flash memories to achieve high write speed. In parallel programming, a common programm voltage is applied to many cells for simultaneous charge injection. This property significantly simplifies the complexity of the memory hardware, and is a constraint that limits the storage capacity of flash memories. Another important property is that cells have different hardness for charge injection. It makes the charge injected into cells differ even when the same program voltage is applied to them. In this paper, we study the parallel programming of flash memory cells, focusing on the above two properties. We present algorithms for parallel programming when there is information on the cells' hardness for charge injection, but there is no feedback information on cell levels during programming. We then proceed to the programming model with feedback information on cell levels, and study how well the information on the cells' hardness for charge injection can be obtained. The results can be useful for understanding the storage capacity of flash memories with parallel programming.

A Write Once Memory (WOM) is a storage medium with binary memory elements, called cells, that can change from the zero state to the one state only once. Examples of WOMs are punch cards, optical disks, and more recently flash memories. A t-write WOM-code is a coding scheme for storing t messages in n cells in such a way that each cell can change its value only from the zero state to the one state. The WOM-rate of a t-write WOM-code is the ratio of the total amount of information written to the WOM in t writes to the number of cells. In this paper we present a family of 2-write WOM-codes. It is shown how to construct from each linear code C a 2-write WOM-code. Then, we find 2-write WOM-codes that improve the best known WOM-rate with two writes. This scheme is proved to be capacity achieving when the parity check matrix of the linear code C is chosen uniformly at random. Finally, we show how to take advantage of 2-write WOM-codes in order to construct codes for the Blackwell channel.

In high density perpendicular magnetic recording channels, nonlinear transition shift (NLTS) is one of the distortions that can degrade the system performance. Write precompensation is a standard method used to combat the negative effect of NLTS. In this paper, we present an analysis of the bit-error-rate (BER) for perpendicular recording systems with NLTS and write precompensation. Media jitter noise and additive white Gaussian noise are also considered in the model. A BER lower bound is derived, as well as a more easily computed estimate of the bound. The write precompensation values that numerically minimize the estimate of the BER lower bound prove to be very close to those found using Monte-Carlo channel simulation. We then apply these methods to the design of multilevel precompensation schemes, for which the optimization of precompensation values by Monte-Carlo channel simulation is computationally infeasible. The results show that for higher recording densities subject to increased ISI and noise, the use of more complex precompensation schemes does not significantly improve the system performance.

Flash memory is a nonvolatile computer memory comprised of blocks of cells, wherein each cell is implemented as either NAND or NOR floating gate. NAND flash is currently the most widely used type of flash memory. In a NAND flash memory, every block of cells consists of numerous pages; rewriting even a single page requires the whole block to be erased and reprogrammed. Block erasures determine both the longevity and the efficiency of a flash memory. Therefore, when data in a NAND flash memory are reorganized, minimizing the total number of block erasures required to achieve the desired data movement is an important goal. This leads to the flash data movement problem studied in this paper. We show that coding can significantly reduce the number of block erasures required for data movement, and present several optimal or nearly optimal data-movement algorithms based upon ideas from coding theory and combinatorics. In particular, we show that the sorting-based (noncoding) schemes require$O(n\log n)$erasures to move data among$n$blocks, whereas coding-based schemes require only$O(n)$erasures. Furthermore, coding-based schemes use only one auxiliary block, which is the best possible and achieve a good balance between the number of erasures in each of the$n+1$blocks.

NAND flash memories are currently the most widely used flash memories. In a NAND flash memory, although a cell block consists of many pages, to rewrite one page, the whole block needs to be erased and reprogrammed. Block erasures determine the longevity and efficiency of flash memories. So when data is frequently reorganized, which can be characterized as a data movement process, how to minimize block erasures becomes an important challenge. In this paper, we show that coding can significantly reduce block erasures for data movement, and present several optimal or nearly optimal algorithms. While the sorting-based non-coding schemes require O(n log n) erasures to move data among n blocks, coding-based schemes use only O(n) erasures and also optimize the utilization of storage space.

In this paper, we explore a novel approach to evaluate the inherent UEP (unequal error protection) properties of irregular LDPC (low-density parity-check) codes over BECs (binary erasure channels). Exploiting the finite-length scaling methodology, suggested by Amraoui et. al., we introduce a scaling approach to approximate the bit erasure rates of variable nodes with different degrees in the waterfall region of the peeling decoder. Comparing the bit erasure rates obtained from Monte Carlo simulation with the proposed scaling approximations, we demonstrate that the scaling approach provides a close approximation for a wide range of code lengths (between 1000 and 8000). In view of the complexity associated with the numerical evaluation of the scaling approximation, we also derive simpler upper and lower bounds.

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n, k, t)qflash code ¿ is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0 ¿ 1 or 1 ¿ 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of ¿, defined as ¿(¿) = n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k > 6 and large n, the best previously known construction of flash codes achieves a write defficiency of O(qk2). On the other hand, the best known lower bound on write deficiency is ¿(qk). In this paper, we present a new construction of flash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we first improve upon the so-called ¿indexed¿ flash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write defficiency of the resulting flash codes is O(qk log k) if q ¿ log2k, and at most O(k log2k) otherwise.

Despite flash memory's promise, it suffers from many idiosyncrasies such as limited durability, data integrity problems, and asymmetry in operation granularity. As architects, we aim to find ways to overcome these idiosyncrasies while exploiting flash memory's useful characteristics. To be successful, we must understand the trade-offs between the performance, cost (in both power and dollars), and reliability of flash memory. In addition, we must understand how different usage patterns affect these characteristics. Flash manufacturers provide conservative guidelines about these metrics, and this lack of detail makes it difficult to design systems that fully exploit flash memory's capabilities. We have empirically characterized flash memory technology from five manufacturers by directly measuring the performance, power, and reliability. We demonstrate that performance varies significantly between vendors, devices, and from publicly available datasheets. We also demonstrate and quantify some unexpected device characteristics and show how we can use them to improve responsiveness and energy consumption of solid state disks by 44% and 13%, respectively, as well as increase flash device lifetime by 5.2x.

In this paper, we analyze the distance properties of two-dimensional (2-D) intersymbol interference (ISI) channels, in particular the 2-D partial response class-1 (PR1) channel which is an extension of the one-dimensional (1-D) PR1 channel. The minimum squared-Euclidean distance of this channel is proved to be 4 and a complete characterization of the squared-Euclidean distance 4 error events is provided. As for 1-D channels, we can construct error-state diagrams for 2-D channels to help characterize error events. We propose an efficient error event search algorithm operating on the error-state diagram that is applicable to any 2-D channel.

For a linear block code C, its stopping redundancy is defined as the smallest number of check nodes in a Tanner graph for C, such that there exist no stopping sets of size smaller than the minimum distance of C. Schwartz and Vardy conjectured that the stopping redundancy of a maximum-distance separable (MDS) code should only depend on its length and minimum distance. We define the (n, t)-single-exclusion number, S(n, t) as the smallest number of i-subsets of an n-set, such that for each i-subset of the n-set, i =1,... ,t + 1, there exists a i-subset that contains all but one element of the i-subset. New upper bounds on the single-exclusion number are obtained via probabilistic methods, recurrent inequalities, as well as explicit constructions. The new bounds are used to better understand the stopping redundancy of MDS codes. In particular, it is shown that for [n, k = n - d + 1, d] MDS codes, as n rarr infin , the stopping redundancy is asymptotic to S(n, d - 2), if d = o(radic(n)), or if k = o(radic(n)), k rarr infin, thus giving partial confirmation of the Schwartz-Vardy conjecture in the asymptotic sense.

The read-write process in perpendicular magnetic recording channels includes a number of nonlinear effects. Nonlinear transition shift (NLTS) arising from previously written transitions is one of these. The signal distortion induced by NLTS is reduced by use of write precompensation during data recording. In this paper, we numerically evaluate the effect of NLTS on the read-back signal by using the model proposed by Bertram and Nakamoto. By means of computer simulation, we examine the effectiveness of two write precompensation schemes in combating NLTS effects in a channel characterized by both transition jitter noise and additive white Gaussian electronics noise. We numerically optimize the precompensation schemes according to channel bit-error-rate, as well as more computationally tractable criteria. Our results suggest that a write-precompensation technique with as few as two adjustable parameters can be very effective against NLTS effects.

In this work, we present a novel construction for solving the linear multiuser detection problem using the Gaussian Belief Propagation algorithm. Our algorithm yields an efficient, iterative and distributed implementation of the MMSE detector. Compared to our previous formulation, the new algorithm offers a reduction in memory requirements, the number of computational steps, and the number of messages passed. We prove that a detection method recently proposed by Montanari et al. is an instance of ours, and we provide new convergence results applicable to both.

The ML redundancy of a code is defined as the smallest number of rows in its parity-check matrix such that a message-passing decoder working in the corresponding Tanner graph achieves maximum-likelihood (ML) performance on an erasure channel. General upper bounds on ML redundancy are obtained. In particular, it is shown that the ML redundancy of a q-ary code is at most the number of minimal codewords in its dual code, divided by q−1. Special upper bounds are derived for codes whose dual code contains a covering design. For example, the ML redundancy of a Simplex code of length n is shown to be no greater than (n2− 4n + 9)/6.

The canonical problem of solving a system of linear equations arises in numerous contexts in information theory, communication theory, and related fields. In this contribution, we develop a solution based upon Gaussian belief propagation (GaBP) that does not involve direct matrix inversion. The iterative nature of our approach allows for a distributed message-passing implementation of the solution algorithm. We also address some properties of the GaBP solver, including convergence, exactness, its max-product version and relation to classical solution methods. The application example of decorrelation in CDMA is used to demonstrate the faster convergence rate of the proposed solver in comparison to conventional linear-algebraic iterative solution methods.

This paper proposes a new approach for decoding LDPC codes over MISO channels. Since in an nTtimes 1 MISO system with a modulation of alphabet size 2M, nTtransmitted symbols are combined and produce one received symbol at the receiver, we propose considering the LDPC-coded MISO system as an LDPC code over 2MnT-ary alphabet. Consequently, we propose a modified Tanner graph to introduce belief propagation for decoding MISO-LDPC systems. As a result, the MISO symbol detection and binary LDPC decoding steps are merged into a single message passing decoding. We also propose an efficient method that significantly reduces the complexity of belief propagation decoding in MISO-LDPC systems. Furthermore, we show that our proposed decoder outperforms the conventional decoder for short length LDPC codes in unknown channel scenarios.

This paper investigates the joint iterative decoding of low-density parity-check (LDPC) codes and channels with memory. Sequences of irregular LDPC codes are presented that achieve, under joint iterative decoding, the symmetric information rate of a class of channels with memory and erasure noise. This gives proof, for the first time, that joint iterative decoding can be information rate lossless with respect to maximum-likelihood decoding. These results build on previous capacity-achieving code constructions for the binary erasure channel. A two state intersymbol-interference channel with erasure noise, known as the dicode erasure channel, is used as a concrete example throughout the paper.

We study coding schemes which encode unconstrained sequences into run-length-limited (d, k)-constrained sequences. We present a general framework for the construction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping, and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to be a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints.

Recent progress in capacity evaluation has made it possible to compute a sequence of lower bounds on the capacity of a finite-state intersymbol-interference (ISI) channel by finding a sequence of optimized Markov input processes with increasing order , for which the state of the process is the previous input symbols. In this correspondence, we prove that, as the order goes to infinity, the sequence of optimized Markov sources asymptotically achieves the capacity of the channel. The conclusion is extended to two-dimensional finite-state ISI channels, the binary symmetric channel (BSC) with constrained inputs, and general indecomposable finite-state channels with a mild constraint.

For a linear code C, the stopping redundancy of C is defined as the minimum number of check nodes in a Tanner graph T for C such that the size of the smallest stopping set in T is equal to the minimum distance of C. Han and Siegel recently proved an upper bound on the stopping redundancy of general linear codes, using probabilistic analysis. For most code parameters, this bound is the best currently known. In this correspondence, we present several improvements upon this bound.

Detectability of failures of linear programming (LP) decoding and the potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we make a first step in studying this method, and show that by starting from a simple LP problem and adaptively adding the necessary constraints, the complexity of LP decoding can be significantly reduced. In particular, we observe that with adaptive LP decoding, the sizes of the LP problems that need to be solved become practically independent of the density of the parity-check matrix. We further show that adaptively adding extra constraints, such as constraints based on redundant parity checks, can provide large gains in the performance.

New bounds on single-exclusion numbers are obtained via probabilistic arguments, recurrent relations, as well as explicit constructions. The new bounds are used to better understand the stopping redundancy of MDS codes. In particular, it is shown that for any fixed k, the stopping redundancy of a linear [n, k] MDS code is between 1/k+1(kn) and (1 + o(1))1/k (kn).

We propose an approximation of maximum-likelihood detection in ISI channels based on linear programming or message passing. We convert the detection problem into a binary decoding problem, which can be easily combined with LDPC decoding. We show that, for a certain class of channels and in the absence of coding, the proposed technique provides the exact ML solution without an exponential complexity in the size of channel memory, while for some other channels, this method has a non-diminishing probability of failure as SNR increases. Some analysis is provided for the error events of the proposed technique under linear programming.

This paper presents a practical implementation of the vertical Bell Laboratories layered space-time (V-BLAST) type system, in which the multiple-input multiple-output (MIMO) open-loop capacity can be approached with conventional scalar coding, using adaptive modulation with appropriate channel codes, e.g., low-density parity-check (LDPC) codes and optimum successive detection (OSD). The density evolution (DE) technique is employed to determine the maximal achievable rate of an LDPC code for each transmit antenna for a given channel realization at a given SNR. Numerical results show that the average sum rate of the adaptively modulated LDPC-encoded system is quite close to the V-BLAST capacity with both rate and power adaptations. Considering the performing degradation caused by error propagation due to the imperfect feedback and relatively long decoding delay in the OSD, we use parallel interference cancellation (PIC) followed by minimum mean square error (MMSE) filtering in the bit error rate (BER) performance simulation. Simulation results show that a target BER of 10-5 can be achieved by the optimally designed LDPC codes. To simplify the code design, we replace the LDPC codes optimally designed for each channel realization with rate-compatible punctured LDPC codes, at the cost of a slight sum rate loss. If the fading process is nonergodic, the outage capacity corresponding to a given outage probability is used to measure the channel performance. As an example, we design the LDPC codes for an adaptively modulated 2×2 V-BLAST system to approach its outage capacity for a given outage probability.

For a linear block code with minimum distance d, its stopping redundancy is the minimum number of check nodes in a Tanner graph representation of the code, such that all nonempty stopping sets have size d or larger. We derive new upper bounds on stopping redundancy for all linear codes in general, and for maximum distance separable (MDS) codes specifically, and show how they improve upon previous results. For MDS codes, the new bounds are found by upper-bounding the stopping redundancy by a combinatorial quantity closely related to Turan numbers. (The Turan number, T(v,k,t), is the smallest number of t-subsets of a v-set, such that every k-subset of the v-set contains at least one of the t-subsets.) Asymptotically, we show that the stopping redundancy of MDS codes with length n and minimum distance d >1 is T(n,d-1,d-2)(1+O(n-1)) for fixed d, and is at most T (n,d-1,d-2)(3+O(n-1)) for fixed code dimension k=n-d+1. For d=3,4, we prove that the stopping redundancy of MDS codes is equal to T(n,d-1,d-2), for which exact formulas are known. For d=5, we show that the stopping redundancy of MDS codes is either T(n,4,3) or T(n,4,3)+1

By examining the achievable rates of a multistage decoding system on stationary ergodic channels, we derive lower bounds on the mutual information rate corresponding to independent and uniformly distributed (i.u.d.) inputs, also referred to as the i.u.d. information rate. For binary intersymbol interference (ISI) channels, we show that these bounds become tight as the number of decoding stages increases. Our analysis, which focuses on the marginal conditional output densities at each stage of decoding, provides an information rate corresponding to each stage. These rates underlie the design of multilevel coding schemes, based upon low-density parity-check (LDPC) codes and message passing, that in combination with multistage decoding approach the i.u.d. information rate for binary ISI channels. We give example constructions for channel models that have been commonly used in magnetic recording. These examples demonstrate that the technique is very effective even for a small number of decoding stages

We study coding schemes which encode unconstrained sequences into run-length-limited (d, k)-constrained sequences. We present a general framework for the construction of such (d, k)-codes from variable-length source codes. This framework is an extension of the previously suggested bit stuffing, bit flipping and symbol sliding algorithms. We show that it gives rise to new code constructions which achieve improved performance over the three aforementioned algorithms. Therefore, we are interested in finding optimal codes under this framework, optimal in the sense of maximal achievable asymptotic rates. However, this appears to be a difficult problem. In an attempt to solve it, we are led to consider the encoding of unconstrained sequences of independent but biased (as opposed to equiprobable) bits. Here, our main result is that one can use the Tunstall source coding algorithm to generate optimal codes for a partial class of (d, k) constraints

For one-dimensional (1-D) recording channels, the detector performance can be assessed by the distance properties of the channel, which are defined in terms of the maximum-likelihood decoding trellis. Error events with minimum and near minimum distances play an important role in the performance of the recording system particularly at moderate to high signal-to-noise ratio (SNR). In this paper, we analyze the distance properties of two-dimensional (2-D) inter-symbol interference channels, in particular the 2-D PR1 channel which is an extension of the 1-D PR1 channel. The minimum distance of this channel is proved to be 2 and a complete characterization of the distance-2 error events is provided. Also, the error events with squared-Euclidean distance 6 are partially characterized. Analogous to 1-D channels, error-state diagrams for 2-D channels can be constructed to characterize the error events. We propose an efficient error event search algorithm operating on the error-state diagram that is applicable to any 2-D channel

The stopping redundancy of a linear code is defined as the minimum number of rows in its parity-check matrix such that the smallest stopping sets have size equal to the minimum distance of the code. We derive new upper bounds on the stopping redundancy of maximum distance separable (MDS) codes, and show how they improve upon previously known results. The new bounds are found by upper bounding the stopping redundancy by a combinatorial quantity closely related to Turan numbers. (The Turan number, T(v, k, t), is the smallest number of t-subsets of a v-set, such that every k-subset of the v-set contains at least one of the t-subsets.) Asymptotically, we show that the stopping redundancy of MDS codes with length n and minimum distance d > 1 is T(n, d -1, d - 2)(1 + O(n-1)) for fixed d, and is at most T(n, d - 1, d - 2)(3 + O(n-1)) for fixed code dimension k = n - d + 1. For d = 2,3,4, we prove that the stopping redundancy is equal to T(n, d - 1, d - 2). For d = 5, we show that the stopping redundancy is either T(n, 4, 3) or T(n, 4, 3) + 1

The ability of linear programming (LP) decoding to detect failures, and its potential for improvement by the addition of new constraints, motivates the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we show that the application of such adaptive methods can significantly reduce the complexity of the LP decoding algorithm, which, in the standard formulation, is exponential in the maximum row weight of the parity-check matrix. We further show that adaptively adding new constraints, e.g. by combining parity checks, can provide large gains in LP decoder performance

We derive upper and lower bounds on the weight distribution of Over-Extended Reed-Solomon (OERS) codes. Using these bounds, we obtain tight upper and lower bounds on the probability of undetected error for OERS codes on q-ary symmetric channels.

We derive a pair of bounds (upper and lower) on the symmetric information rate of a two-dimensional finite-state intersymbol interference (ISI) channel model. For channels with small impulse response support, they can be estimated via a modified forward recursion of the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm. The convergence of the bounds is also analyzed. To relax the constraint on the size of the impulse response, a new upper bound is proposed which allows the tradeoff of the computational complexity and the tightness of the bound. These bounds are further extended to d-dimensional (d>2) ISI channels.

Upper and lower bounds on the weight distribution of overextended Reed-Solomon (OERS) codes are derived, from which tight upper and lower bounds on the probability of undetected error for OERS codes are obtained for q-ary symmetric channels

We consider a number of constrained coding techniques that can be used to mitigate a nonlinear effect in the optical fiber channel that causes the formation of spurious pulses, called "ghost pulses". Specifically, if b/sub 1/b/sub 2/...b/sub n/ is a sequence of bits sent across an optical channel, such that b/sub k/=b/sub l/=b/sub m/=1 for some k,l,m (not necessarily all distinct) but b/sub k+l-m/=0, then the ghost-pulse effect causes b/sub k+l-m/ to change to 1, thereby creating an error. Such errors do not occur if the sequence of bits satisfies the following constraint: for all integers k,l,m such that b/sub k/=b/sub l/=b/sub m/=1, we have b/sub k+l-m/=1. We call this the binary ghost-pulse (BGP) constraint. We will show, however, that the BGP constraint has zero capacity, implying that sequences satisfying this constraint cannot carry much information. Consequently, we consider a more sophisticated coding scheme, which uses ternary sequences satisfying a certain ternary ghost-pulse (TGP) constraint. We further relax these constraints by ignoring interactions between symbols that are more than a certain distance t apart in the transmitted sequence. Analysis of the resulting BGP(t) and TGP(t) constraints shows that these have nonzero capacities, and furthermore, the TGP(t)-constrained codes can achieve rates that are significantly higher than those for the corresponding BGP(t) codes. We also discuss the design of encoders and decoders for coding into the BGP, BGP(t), and TGP(t) constraints.

Previous results suggest that the crosstalk produced by the fiber nonlinearity in a WDM system imposes a severe limit to the capacity of optical fiber channels, since the interference power increases faster than the signal power, thereby limiting the maximum achievable signal-to-interference-plus-noise ratio (SINR). We study this system in the weakly nonlinear regime as a multiple-access channel, and show that by optimally using the information from all the channels for detection, the change in the capacity region due to the nonlinear effect is minimal. On the other hand, if the receiver uses the output of only one wavelength channel, the capacity is significantly reduced due to the nonlinearity, and saturates as the interference power becomes comparable to the noise, which is consistent with earlier results. The results hold in channels with or without memory. Every point in the capacity region can be achieved without knowledge of the nonlinearity parameters at the transmitters. The structures of optimal/suboptimal receivers are briefly discussed

We consider hard-decision iterative decoders for product codes over the erasure channel, which employ repeated rounds of decoding rows and columns alternatingly. We derive the exact asymptotic probability of decoding failure as a function of the error-correction capabilities of the row and column codes, the number of decoding rounds, and the channel erasure probability. We examine both the case of codes capable of correcting a constant amount of errors, and the case of codes capable of correcting a constant fraction of their length

We present bit-stuffing schemes which encode arbitrary data sequences into two-dimensional (2-D) constrained arrays. We consider the class of 2-D runlength-limited (RLL) (d, infin) constraints as well as the 'no isolated bits' (n.i.b.) constraint, both defined on the square lattice. The bit stuffing technique was previously introduced and applied to the class of 2-D (d, infin) constraints. Analytical lower bounds on the rate of these encoders were derived. For d = 1, a more general scheme was analyzed and shown to obtain improved performance. We extend the (1, infin)-construction to (d, infin) constraints where d ges 2. We then suggest a bit-stuffing scheme for the n.i.b. constraint, based on a capacity-achieving scheme for a one-dimensional RLL (0,3) constraint. Simulation results demonstrate the performance of the proposed schemes

Just as the Hamming weight spectrum of a linear block code sheds light on the performance of a maximum likelihood decoder, the pseudo-weight spectrum provides insight into the performance of a linear programming decoder. Using properties of polyhedral cones, we find the pseudo-weight spectrum of some short codes. We also present two general lower bounds on the minimum pseudo-weight. The first bound is based on the column weight of the parity-check matrix. The second bound is computed by solving an optimization problem. In some cases, this bound is more tractable to compute than previously known bounds and thus can be applied to longer codes

We derive lower bounds on the capacity of asymmetric two-dimensional (d, infin)-constraints from bounds on the output entropy of bit-stuffing encoders for general asymmetric (d, infin)-constraints on both the square lattice and the hexagonal lattice. For the (d, infin; 1, infin)-constraint on the square lattice and the (d, infin; 1, infin; 1, infin)-constraint on the hexagonal lattice, we derive exact encoder output entropies which provide even tighter bounds on the capacity of these constraints

The achievable information rates for multilevel coding (MLC) systems with multistage decoding (MSD) are examined on two-dimensional binary-input intersymbol interference (ISI) channels. One MSD scheme employs trellis-based detection, while another involves zero-forcing equalization and linear noise prediction. Information rates are determined by examining the output statistics at each stage of MSD. The first scheme is shown to achieve rates very close to known information-theoretic limits. Systems with low-density parity-check codes are then optimized to approach these rates

In this paper, we analyze bi-infinite sequences over the alphabet $\{0,1,\ldots,q-1\}$, for an arbitrary $q \geq 2$, that satisfy the q-ary ghost pulse (qGP) constraint. A sequence $\x = {(x_k)}_{k \in \Z} \in \{0,1,\ldots,q-1\}^{\Z}$ satisfies the qGP constraint if for all $k,l,m \in \Z$ such that $x_k$, $x_l$ and $x_m$ are nonzero and equal, $x_{k+l-m}$ is also nonzero. This constraint arises in the context of coding for communication over a fiber optic medium. We show, using techniques from Ramsey theory, that if $\x$ satisfies the qGP constraint, then the set $\supp(\x) = \{l \in \Z:\ x_l \neq 0\}$ is the disjoint union of cosets of some subgroup, $k\Z$, of $\Z$, and a set of zero density. We provide much sharper results in the special cases of $q = 2$ and $q=3$. In the former case, we show that the corresponding binary ghost pulse constraint has zero capacity, and based on our results for the latter case, we conjecture that the capacity of the ternary ghost pulse constraint is also zero.

We design serial concatenated multi-input multi-output systems based on low-density parity-check (LDPC) codes. We employ a receiver structure combining the demapper/detector and the decoder in an iterative fashion. We consider the a posteriori probability (APP) demapper, as well as a suboptimal demapper incorporating interference cancellation with linear filtering. Extrinsic information transfer (EXIT) chart analysis is applied to study the convergence behavior of the proposed schemes. We show that EXIT charts match very well with the simulated decoding trajectories, and they help explain the impact of different mappings and different demappers. It is observed that if the APP demapper transfer characteristics are almost flat, the LDPC codes optimized for binary-input channels are good enough to achieve performance close to the channel capacity. We also present a simple code-optimization method based on EXIT chart analysis, and we design a rate-1/2 LDPC code that achieves very low bit-error rates within 0.15 dB of the capacity of a two-input two-output Rayleigh fading channel with 4-pulse amplitude modulation. We next propose to use a space-time block code as an inner code of our serial concatenated coding scheme. By means of a simple example scheme, using an Alamouti inner code, we demonstrate that the design/optimization of the outer code (e.g., LDPC code) is greatly simplified.

We propose a serial concatenated trellis-coded modulation system using one or more inner rate-1 accumulate codes and a mapping to a higher order, Gray-labeled signal constellation. As outer codes, we consider repeat codes, single parity-check codes, and convolutional codes. We show that under maximum-likelihood decoding, there exists a signal-to-noise ratio threshold beyond which the bit-error probability goes to zero as the blocklength goes to infinity. We then evaluate the performance for finite blocklengths using a modified union bound. Computer simulations demonstrate that the proposed system, despite its use of a simple rate-1 inner code, achieves performance in additive white Gaussian noise and Rayleigh fading that is comparable to, or better than, that of more complex systems suggested in the literature.

In a companion paper, we showed the existence of decoding thresholds for maximum-likelihood (ML) decoding of a serial concatenated trellis-coded modulation (SCTCM) system with one or more inner accumulate codes. In this paper, we compute the decoding thresholds for an iterative, non-ML decoder by density evolution (DE), assuming infinite blocklengths. We also derive a stability condition for the particular case of an outer parity-check code and a single inner accumulate code. We show that, for equiprobable signaling, the bit-wise log-likelihood ratio densities for higher order constellations are symmetric. Furthermore, when used in DE, these densities can be averaged without significantly affecting the resulting threshold values. For an outer single parity-check code, the lowest decoding thresholds are achieved with two inner accumulate codes. For an outer repeat code, a single inner accumulate code gives the lowest thresholds. At code rates r/sub c/>2/3, the decoding thresholds for the SCTCM system are within 1 dB of the constellation-constrained channel capacity for additive white Gaussian noise channels, and within 1.5 dB for independent, identically distributed Rayleigh channels. Simulation results verify the computed thresholds.

In this paper, the uplink of an asynchronous multi-carrier direct-sequence code-division multiple-access (MC-DS-CDMA) system with multiple antennas at both the transmitter and the receiver is considered. We analyze the system performance over a spatially correlated Rayleigh fading channel with multiple-access interference (MAI), and evaluate the antenna array performance with joint fading reduction and MAI suppression. Assuming perfect channel knowledge available at the transmitter, maximal ratio transmission is employed to weight the transmitted signal optimally in terms of combating signal fading. At the receiver, adaptive beamforming reception is adopted to both suppress MAI and combat the fading. Note that while correlations among the fades of the antennas in the receive array reduce the diversity gain against fading, the array still has the capability for interference suppression. We examine the effect of varying the number of transmit and receive antennas on both the diversity gain and the interference suppression.

The bit stuffing algorithm is a technique for coding constrained sequences by the insertion of bits into an arbitrary data sequence. This approach was previously introduced and applied to (d,k) constrained codes. Results show that the maximum average rate of the bit stuffing code achieves capacity when k=d+1 or k=/spl infin/, while it is suboptimal for all other (d,k) pairs. Furthermore, this technique was generalized to produce codes with an average rate that achieves capacity for all (d,k) pairs. However, this extension results in a more complicated scheme. This correspondence proposes a modification to the bit stuffing algorithm that maintains its simplicity. We show analytically that the proposed algorithm achieves improved average rates over bit stuffing for most (d,k) constraints. We further determine all constraints for which this scheme produces codes with an average rate equal to the Shannon capacity.

An (n,k) Reed-Solomon (RS) code is used in a magnetic recording system to help reduce the word failure rate (WFR). If the channel signal-to-noise ratio (SNR) exceeds a certain value, the full power of a given RS code may be needed only on a few occasions to guarantee a target WFR. When this occurs, a parity-sharing scheme can be used to group a number of RS codewords into a larger codeword, block. The target WFR can, therefore, be achieved at a higher code rate. An efficient list-decoding technique has recently been developed by Guruswami and Sudan (G-S) that allows error correction beyond the classical "half-the-minimum-distance" bound. Koetter and Vardy (K-V) have further extended the G-S algorithm to perform soft-decision list-decoding. This work will show that G-S hard-decision and K-V soft-decision list-decoding of parity-sharing codes are both effective and computationally manageable schemes on the discrete memoryless and partial response channels.

The bit stuffing algorithm is a technique for coding constrained sequences by the insertion of bits into an arbitrary data sequence. This approach was previously introduced and applied to (d, k) constrained codes. Results show that the maximum average rate of the bit stuffing code achieves capacity when k=d+1 or k=/spl infin/, while it is suboptimal for all other (d, k) pairs. We propose a modification to the bit stuffing algorithm. We show analytically that the proposed algorithm achieves improved average rates over bit stuffing for most (d, k) constraints.

Magnetic recording channels are generally modeled as finite-state linear intersymbol interference (ISI) channels with additive white Gaussian noise and a binary input constraint. Lower bounds on the channel capacity have been computed by using this technique to estimate the information rates of optimized, order-r Markov input processes. RLL-constrained binary symmetric channel (BSC) and for two-dimensional finite-state ISI channels is proved in this paper

We determine the pairs of (d, k)-constrained systems, S(d,k) and S(d,k), of equal capacity, for which there exists a rate 1:1 sliding-block decodable encoder from S(d,k) to S(d,k). Whenever such an encoder exists, we explicitly describe one such encoder and its corresponding sliding-block decoder.

Biinfinite sequences X=(x/sub k/)/sub k/spl isin//spl Zopf// over the alphabet {0,1,...,q-1}, for an arbitrary q/spl ges/2, that satisfy the following q-ary ghost pulse (qGP) constraint: for all k,l,m/spl isin//spl Zopf/ such that x/sub k/,x/sub l/,x/sub m/ are nonzero and equal, x/sub k+l-m/ is also nonzero is studied in this paper. This constraint arises in the context of coding to combat the formation of spurious "ghost" pulses in high data-rate communication over an optical fiber. We show using techniques from Ramsey theory that if x satisfies the /sub q/GP constraint, then the support of x is a disjoint union of cosets of a subgroup k/spl Zopf/ of /spl Zopf/ and a set of zero density.

This paper describes the analysis of convolutional codes on the erasure channel. We compare the maximum likelihood (ML) sequence decision and the maximum a posteriori (MAP) symbol decision for codes, which are transmitted over the erasure channel. When a codeword from a linear error correcting code with elements from the field GF is transmitted over a q-ary erasure channel, the symbol error rate of the maximum likelihood (ML) sequence decision is the same as that of the symbol maximum a posteriori (MAP) probability decision. When decoding convolutional codes transmitted over an AWGN channel, it is widely known that the probability of symbol error for the Viterbi algorithm (which is a sequence ML decoder) is generally higher than that for the more complex BCJR algorithm (which is a symbol MAP decoder).

We present a near-capacity coding system for higher-order partial-response channels, consisting of an outer set of interleaved low-density parity-check codes, an inner rate-1 shaping code, and a multistage decoder. The inner shaping code, which may be noninvertible, is designed to generate an output process similar to a binary Markov process that maximizes the mutual information for a given order. On the EPR4 channel, our system exhibits an iterative decoding threshold and a simulation BER of 10/sup -5/ within 0.19 and 0.33 dB, respectively, of the information-theoretic limit for a third-order input process.

We apply principles from digital image correction to enhance the correction of two-dimensionally correlated unidirectional errors on a two-dimensional grid system. A restoration technique presented in Neifield et al. (1996) based on Markov random fields, is used to find an estimate of the error pattern. This estimate then in turn provides a priori information for use in a soft decoder for the actual code (e.g. LDPC decoder).

We evaluate truncated union bounds on the frame-error rate (FER) performance of space-time (ST) codes operating over the quasi-static fading channel and compare them with computer simulation results. We consider both ST trellis and block codes. We make the following contributions. For the case of ST trellis codes, we develop a general method, which we denote as measure spectrum analysis, that characterizes ST codeword differences and accommodates the combined influences of the ST code and channel scenario. We propose a numerical bounding method that converges in the measure spectrum to within a very small fraction of a decibel to the simulated FER over the full range of signal-to-noise ratio. In addition, we demonstrate the existence of dominant quasi-static fading error events and detail a method for predicting them. Using only this set of dominant measure spectrum elements, very rapid and tight numerical estimation of FER performance is attained.

We derive lower bounds on the capacity of certain two-dimensional (2-D) constraints by considering bounds on the entropy of measures induced by bit-stuffing encoders. A more detailed analysis of a previously proposed bit-stuffing encoder for (d,/spl infin/)-runlength-limited (RLL) constraints on the square lattice yields improved lower bounds on the capacity for all d /spl ges/ 2. This encoding approach is extended to (d,/spl infin/)-RLL constraints on the hexagonal lattice, and a similar analysis yields lower bounds on the capacity for d /spl ges/ 2. For the hexagonal (1,/spl infin/)-RLL constraint, the exact coding ratio of the bit-stuffing encoder is calculated and is shown to be within 0.5% of the (known) capacity. Finally, a lower bound is presented on the coding ratio of a bit-stuffing encoder for the constraint on the square lattice where each bit is equal to at least one of its four closest neighbors, thereby providing a lower bound on the capacity of this constraint.

We determine the pairs of (d,k)-constrained systems, S(d,k) and S(d/spl circ/,k/spl circ/), of equal capacity, for which there exists a rate 1:1 sliding-block-decodable encoder from S(d,k) to S(d/spl circ/,k/spl circ/). In all cases where there exists such an encoder, we explicitly describe the encoder and its corresponding sliding-block decoder.

Since the discovery of turbo codes, iterative decoding has gained enormous momentum. The idea of repeatedly passing information between components of a receiver or decoder to increase the overall system performance has attracted much research effort. In this work, we present an iterative soft-decision decoding architecture for Reed-Solomon (RS) codes on a partial-response (PR) channel. The architecture incorporates a symbol-based a-posteriori probability (APP) detector for the channel, and an enhanced soft-decision RS decoder based upon the recently introduced Koetter-Vardy (KY) algorithm. From the list of candidate RS codewords generated by the KV decoder, we calculate output symbol reliabilities that can be fed back to the APP detector as extrinsic information to be used in a subsequent decoding iteration. Through simulations, we show the efficacy of this approach, especially when the initial KV list size is large. We will also propose ways to modify the decoding scheme in order to beneficially increase the size of the candidate codeword list and thereby improve the overall system performance.

Analytic expressions for the exact probability of erasure for systematic, rate- 1/2 convolutional codes used to communicate over the binary erasure channel and decoded using the soft-input, soft-output (SISO) and a posteriori probability (APP) algorithms are given. An alternative forward-backward algorithm which produces the same result as the SISO algorithm is also given. This low-complexity implementation, based upon lookup tables, is of interest for systems which use convolutional codes, such as turbo codes.

We evaluate truncated union bounds on the frame error rate performance of space-time (ST) codes operating over the quasistatic fading channel and compare them to the results from computer simulation. Both ST trellis and block codes are considered. We calculate these bounds by characterizing the set of codeword differences from a general expression for the exact pairwise error probability (PEP). We discussed in detail the significantly tighter numerical bound for quasistatic fading and demonstrate the code properties that account for this tightness. Using this improved bound we show empirical evidence that for some codes a set of dominant error events characterize the FER performance. We also compare these performance results to outage capacity.

We derive upper and lower bounds on the symmetric information rate of a two-dimensional finite-state intersymbol-interference (ISI) channel model.

In this paper, we consider the problem of determining when the capacities of distinct (d,k)-constrained systems can be equal. A (d,k)-constrained system consists of binary sequences which have at least d zeros and at most k zeros between any two successive ones. If we let C(d,k) denote the capacity of a (d,k)-constrained system, then it is known that C(d,2d) = C(d+1,3d+1) and C(d,2d+1) = C(d+1,\infty)$. Repeated application of these two identities also yields the chain of equalities C(1,2) = C(2,4) = C(3,7) = C(4,\infty)$. We show that these are the only equalities possible among the capacities of (d,k)-constrained systems. In the process, we also provide useful factorizations of the characteristic polynomials for these constraints.

For a discrete-time, binary-input, Gaussian channel with finite intersymbol interference, we prove that reliable communication can be achieved if, and only if, E/sub b//N/sub 0/>log2/G/sub opt/, for some constant G/sub opt/ that depends on the channel. To determine this constant, we consider the finite-state machine which represents the output sequences of the channel filter when driven by binary inputs. We then define G/sub opt/ as the maximum output power achieved by a simple cycle in this graph, and show that no other cycle or asymptotically long sequence can achieve an output power greater than this. We provide examples where the binary input constraint leads to a suboptimality, and other cases where binary signaling is just as effective as real signaling at very low signal-to-noise ratios.

To accommodate high-speed data transmissions, it may be necessary to substantially reduce the processing gain of a direct-sequence spread-spectrum (DSSS) system. As a result, intersymbol interference effects may become more severe. In this paper, we present a new structure for maximum-likelihood sequence estimation equalization of DSSS signals on a multipath fading channel that performs the function of despreading and equalization simultaneously. Analytical upper bounds are derived for the bit-error probability when random spreading sequences are used, and comparisons to simulation results show that the bounds are quite accurate. The results also show that significant performance improvement over the conventional RAKE receiver is obtained.

We design multilevel coding (MLC) and bit-interleaved coded modulation (BICM) schemes based on low-density parity-check (LDPC) codes. The analysis and optimization of the LDPC component codes for the MLC and BICM schemes are complicated because, in general, the equivalent binary-input component channels are not necessarily symmetric. To overcome this obstacle, we deploy two different approaches: one based on independent and identically distributed (i.i.d.) channel adapters and the other based on coset codes. By incorporating i.i.d. channel adapters, we can force the symmetry of each binary-input component channel. By considering coset codes, we extend the concentration theorem based on previous work by Richardson et al. ( see ibid., vol.47, p.599-618, Feb. 2001) and Kavc/spl caron/ic/spl acute/ et al.(see ibid., vol.49, p.1636-52, July 2003) We also discuss the relation between the systems based on the two approaches and show that they indeed have the same expected decoder behavior. Next, we jointly optimize the code rates and degree distribution pairs of the LDPC component codes for the MLC scheme. The optimized irregular LDPC codes at each level of MLC with multistage decoding (MSD) are able to perform well at signal-to-noise ratios (SNR) very close to the capacity of the additive white Gaussian noise (AWGN) channel. We also show that the optimized BICM scheme can approach the parallel independent decoding (PID) capacity as closely as does the MLC/PID scheme. Simulations with very large codeword length verify the accuracy of the analytical results. Finally, we compare the simulated performance of these coded modulation schemes at finite codeword lengths, and consider the results from the perspective of a random coding exponent analysis.

Until the analysis of repeat accumulate codes by Divsalar et al. (1998), few people would have guessed that simple rate-1 codes could play a crucial role in the construction of "good" binary codes. We construct "good" binary linear block codes at any rate r<1 by serially concatenating an arbitrary outer code of rate r with a large number of rate-1 inner codes through uniform random interleavers. We derive the average output weight enumerator (WE) for this ensemble in the limit as the number of inner codes goes to infinity. Using a probabilistic upper bound on the minimum distance, we prove that long codes from this ensemble will achieve the Gilbert-Varshamov (1952) bound with high probability. Numerical evaluation of the minimum distance shows that the asymptotic bound can be achieved with a small number of inner codes. In essence, this construction produces codes with good distance properties which are also compatible with iterative "turbo" style decoding. For selected codes, we also present bounds on the probability of maximum-likelihood decoding (MLD) error and simulation results for the probability of iterative decoding error.

We compare the performance of list-type soft-decision Reed-Solomon (RS) decoding algorithms to that of classical hard-decision RS decoding on partial response (PR) channels. The two soft-decision RS decoding approaches that we consider, the list-GMD and the Koetter-Vardy (see Proc. IEEE Int. Symp. Information Theory, (Sorrento, Italy), IEEE, June 2000) algorithm, are both based on Sudan's (1997) (polynomial) interpolation approach to polynomial-time list-decoding. The soft-decision RS decoders take as input symbol-based reliabilities which can be provided by a symbol-based BCJR algorithm. The symbol-based BCJR algorithm is an extension of the original BCJR algorithm and calculates the a posteriori probability (APP) of a block of l-bits. The complexity of the algorithm can be reduced when applied to a PR channel. We present a hybrid Viterbi-BCJR approach that can be used when only the reliability of the most-likely symbol is desired. The hybrid approach calculates the APP of the most reliable symbol without the need to run the complete forward and backward algorithm. We demonstrate through simulations that soft-decision RS decoding will lead to a lower probability of decoding error. Moreover, we show that using the symbol-based APPs will yield a lower symbol error rate (SER) than using the measures obtained by multiplying the bit reliabilities.

Ideas of message passing are applied to the problem of removing the effects of intersymbol interference (ISI) from partial-response channels. Both bit-based and state-based parallel message-passing algorithms are proposed. For a fixed number of iterations less than the block length, the bit-error rate of the state-based algorithm approaches a nonzero constant as the signal-to-noise ratio (SNR) approaches infinity. This limitation can be removed by using a precoder. It is well known that low-density parity-check (LDPC) codes can be decoded using a message-passing algorithm. Here, a single message-passing detector/decoder matched to the combination of a partial-response channel and an LDPC code is investigated.

We design multilevel coding (MLC) schemes with low-density parity-check (LDPC) codes as component codes at each level. We develop a method to analyze the performance of an LDPC code at any level as the codeword length goes to infinity, even if the equivalent binary-input component channels are not symmetric. By joint optimization of code rates and degree distributions, the optimized irregular LDPC codes at each level are capable of achieving reliable transmission at signal-to-noise ratios (SNR) very close to the capacity of the additive white Gaussian noise (AWGN) channel as the codeword length tends to infinity. Simulation results show that the optimized LDPC codes also perform very well at moderate codeword lengths.

In this paper, we present two simple Monte Carlo methods for estimating the achievable information rates of general finite state channels. Both methods require only the ability to simulate the channel with an a posteriori probability (APP) detector matched to the channel. The first method estimates the mutual information rate between the input random process and the output random process, provided that both processes are stationary and ergodic. When the inputs are iid equiprobable, this rate is known as the Symmetric Information Rate (SIR). The second method estimates the achievable information rate of an explicit coding system which interleaves m independent codes onto the channel and employs multistage decoding. For practical values of m, numerical results show that this system nearly achieves the SIR. Both methods are applied to the class of partial response channels commonly used in magnetic recording.

In this paper we propose a serial concatenated trellis coded modulation system using an inner accumulate code and a Gray-labeled signal constellation. The simple inner code and the Gray labeling allow us to extend to higher-order constellations the coding theorems of Divsalar et al., (1998), and Pfister et al., (2000), stating that when the signal-to-noise ratio (SNR) exceeds a certain, system-specific threshold, the word error probability goes to zero as the blocklength goes to infinity. We also evaluate the performance for finite blocklengths using an improved union bound. Despite the simple inner code, the simulated performance in AWGN and Rayleigh fading is equal to the performance of more complex systems suggested in the literature.

We consider maximum-likelihood decoder performance in additive white Gaussian noise for the serial concatenation of an outer code comprising multiple, independent odd-parity-check codes and an inner precoded dicode partial-response channel through a random interleaver. Using a technique proposed in Oberg and Siegel (1998, 2001) we derive an approximation of the average weight enumerator, assuming that code bit values within error events are independent, identically distributed, and equiprobable. We show that the union bound on word-error-rate based upon the approximate weight enumerator is actually an upper bound to that based upon the true average weight enumerator, for suitably large signal-to-noise ratios.

We design low-density parity-check (LDPC) codes for bandwidth efficient modulation using a multilevel coding (MLC) technique. We develop a method to analyze the asymptotic performance of the LDPC codes using message-passing decoding at each level of the MLC scheme as the codeword length goes to infinity. Simulation of very large block size LDPC codes verifies the accuracy of the analytical results. We jointly optimize the code rates and code parameters of the LDPC codes at each level of the MLC scheme, and the asymptotic performance of the optimized irregular LDPC codes is very close to the channel capacity of the additive white Gaussian noise (AWGN) channel.

Message-passing has been proposed for decoding parity check codes, especially low density parity check (LDPC) codes. We propose using message-passing detectors for partial response channels. Furthermore, we investigate how a single message-passing detector/decoder can be matched to a combination of a partial response channel and a LDPC code.

We propose a serial concatenated trellis coded modulation system using one or more inner accumulate code(s) and a Gray-labeled signal constellation. We show the existence of a threshold, such that if the signal-to-noise ratio (SNR) exceeds this threshold, the bit error probability goes to zero as the blocklength goes to infinity. Tight numerical values for the thresholds for an iterative decoder are found by density evolution. Despite the simple inner code, the simulated performance in AWGN and Rayleigh fading is comparable to that of more complex systems suggested in the literature.

A numerical method has been presented to determine the noise thresholds of low density parity-check (LDPC) codes that employ the message passing decoding algorithm on the additive white Gaussian noise (AWGN) channel. In this paper, we apply the technique to the uncorrelated flat Rayleigh fading channel. Using a nonlinear code optimization technique, we optimize irregular LDPC codes for such a channel. The thresholds of the optimized irregular LDPC codes are very close to the Shannon limit for this channel. For example, at rate one-half, the optimized irregular LDPC code has a threshold only 0.07 dB away from the capacity of the channel. Furthermore, we compare simulated performance of the optimized irregular LDPC codes and turbo codes on a land mobile channel, and the results indicate that at a block size of 3072, irregular LDPC codes can outperform turbo codes over a wide range of mobile speeds.

The performance of a turbo-coded code division multiaccess system with a minimum mean-square error (MMSE) receiver for interference suppression is analyzed on a Rayleigh fading channel. In order to accurately estimate the performance of the turbo coding, two improvements are proposed on the conventional union bounds: the information of the minimum distance of a particular turbo interleaver is used to modify the average weight spectra, and the tangential bound is extended to the Rayleigh fading channel. Theoretical results are derived based on the optimum tap weights of the MMSE receiver and maximum-likelihood decoding. Simulation results incorporating iterative decoding, RLS adaptation, and the effects of finite interleaving are also presented. The results show that in the majority of the scenarios that we are concerned with, the MMSE receiver with a rate-1/2 turbo code will outperform a rate-1/4 turbo code. They also show that, for a bit error rate lower than 10/sup -3/, the capacity of the system is increased by using turbo codes over convolutional codes, even with small block sizes.

The performance of turbo-coded asynchronous direct sequence code division multiple access (DS-CDMA) using long and short spreading sequences is compared by both analysis and simulation. For coded systems with a conventional matched filter (MF) receiver, three analytical methods with different complexity are compared: the standard Gaussian approximation, the improved Gaussian approximation (IGA), and the density function approach. It is shown that while the standard Gaussian approximation is fairly accurate for the long sequences, it is too optimistic for the short sequences. For the short-sequence systems, the IGA gives an accurate estimate for the performance with much less complexity than the density function approach. The analysis shows that for either the additive white Gaussian noise (AWGN) channel or the flat Rayleigh fading channel and a MF receiver, there is a degradation in the average performance of the turbo-coded short-sequence systems compared to the long-sequence systems due to the fact that the cross-correlations are not time-varying. However, the short-sequence systems are amenable to the use of an interference suppression technique designed to minimize the mean square error. Such a minimum mean square error (MMSE) receiver in the turbo-coded system is shown to outperform the long-sequence system with the MF receiver, especially when there is a near-far problem, as previously observed in a convolutionally-coded system. Finally, similar results are obtained by computer simulations for the turbo-coded CDMA systems on a frequency-selective Rayleigh fading channel.

The performance of maximum-likelihood decoding of a serial concatenation comprising a high-rate block code, convolutional code, or a turbo code, a uniform interleaver, and a partial response channel with additive white Gaussian noise is addressed. The effect of a channel precoder on the system performance is also considered. Bit- and word-error rate estimates based upon properties of the average Euclidean distance spectrum of the coded partial response channel are derived. The estimates are compared to computer simulation results, and implications for system design are discussed.

Certain magnetic recording applications call for a large number of sequences whose differences do not include certain disallowed binary patterns. We show that the number of such sequences increases exponentially with their length and that the growth rate, or capacity, is the logarithm of the joint spectral radius of an appropriately defined set of matrices. We derive a new algorithm for determining the joint spectral radius of sets of nonnegative matrices and combine it with existing algorithms to determine the capacity of several sets of disallowed differences that arise in practice.

The hard-square model, also known as the two-dimensional (2-D) (1, /spl infin/)-RLL constraint, consists of all binary arrays in which the 1's are isolated both horizontally and vertically. Based on a certain probability measure defined on those arrays, an efficient variable-to-fixed encoder scheme is presented that maps unconstrained binary words into arrays that satisfy the hard-square model. For sufficiently large arrays, the average rate of the encoder approaches a value which is only 0.1% below the capacity of the constraint. A second, fixed-rate encoder is presented whose rate for large arrays is within 1.2% of the capacity value.

A list decoding for an error-correcting code is a decoding algorithm that generates a list of codewords within a Hamming distance t from the received vector, where t can be greater than the error-correction bound. In previous work by M. Shokrollahi and H. Wasserman (see ibid., vol.45, p.432-7, March 1999) a list-decoding procedure for Reed-Solomon codes was generalized to algebraic-geometric codes. Recent work by V. Guruswami and M. Sudan (see ibid., vol.45, p.1757-67, Sept. 1999) gives improved list decodings for Reed-Solomon codes and algebraic-geometric codes that work for all rates and have many applications. However, these list-decoding algorithms are rather complicated. R. Roth and G. Ruckenstein (see ibid., vol.46, p.246-57, Jan. 2000) proposed an efficient implementation of the list decoding of Reed-Solomon codes. In this correspondence, extending Roth and Ruckenstein's fast algorithm for finding roots of univariate polynomials over polynomial rings, i.e., the reconstruct algorithm, we present an efficient algorithm for finding the roots of univariate polynomials over function fields. Based on the extended algorithm, we give an efficient list-decoding algorithm for algebraic-geometric codes.

The partial response channel can be viewed as a rate-1 encoder in which the output alphabet differs from the input alphabet. In serially concatenated coding schemes, the partial response channel can serve as the inner encoder. Previous work on the application of turbo decoding techniques to partial response channels has focused on using a parallel concatenation of convolutional encoders as the outer code and the partial response channel as the inner code. This system requires three a posteriori probability (APP) detectors-one matched to the channel and two matched to the constituent encoders. A simplified system is presented that uses as its outer code a single convolutional code and as its inner code the partial response channel. The simplified system requires only two APP detectors, offering significant savings in complexity and computation time. This single convolutional code system is shown to perform as well as the more complicated system, offering substantial gains over uncoded systems. Simulation results for three magnetic recording channel models are presented: a partial response channel with additive white Gaussian noise, an equalized Lorentzian channel model, and a media noise model called the microtrack model. Since the use of an outer Reed-Solomon code is anticipated in an actual system, the burst-error statistics are investigated. System performance with various interleaver designs and precoders is also investigated.

This paper presents a theoretical analysis of the effect of constellation shaping in the transmitter on multimodulus (MMA) blind equalization in the receiver. Constellation shaping reduces average signal energy by a non-uniform distribution of constellation point utilization. Optimal transmit efficiency is achieved by a Gaussian distribution but many blind equalization algorithms require a non-Gaussian source. We demonstrate, using complex constellations, MMA convergence failure as a Gaussian source kurtosis is approached. Our generalized cost function analysis of the related constant modulus algorithm (CMA) for complex constellations identifies the mechanism of the MMA convergence failure. We introduce a new design procedure for determining the kurtosis-specific MMA moduli and present simulation results that illustrate MMA convergence properties for varying source kurtosis.

Recent work on the application of turbo decoding techniques to partial response class 4 (PR4) channels has focused on parallel concatenation systems that require three a posteriori (APP) detectors. A simplified serial concatenation system is presented that uses as its outer code a single convolutional code and as its inner code the partial response channel. An extension of this serial concatenation system is also presented that combines a second code with the channel, forming a more powerful inner code. Both proposed systems require only two APP detectors, offering significant savings in complexity and computation time. These serial concatenation systems are shown to perform as well as the more complicated parallel concatenation systems, offering substantial gains over uncoded systems. Additionally, the effect of precoding is investigated. Simulation results comparing the parallel and serial concatenation systems are also presented.

Two algorithms for characterization of input error events producing specified distance at the output of certain binary-input partial-response (PR) channels are presented. Lists of error events are tabulated for PR channels of interest in digital recording.

Partial-response (PR) signaling is used to model communications channels with intersymbol interference (ISI) such as the magnetic recording channel and the copper-wire channel for digital subscriber lines. Coding for improving noise immunity in higher order partial-response channels, such as the "extended" class-4 channels denoted EPR4, E/sup 2/PR4, E/sup 3/PR4, has become an important subject as the linear densities in magnetic recording approach those at which these partial-response channels are the best models of real channels. In this paper, we consider partial-response channels for which ISI is so severe that the channels fail to achieve the matched-filter bound (MFB) for symbol error rate, assuming maximum-likelihood decoding. We show that their performance can be improved to the MFB by high-rate codes based on constrained systems, some of which may even simplify the Viterbi (1979) detectors relative to the uncoded channels. We present several examples of high-rate constrained codes for E/sup 2/PR4 and E/sup 3/PR4 channels and evaluate their performance by simulation.

This letter continues the investigation of methods for computing exact bounds on the path metric differences in maximum-likelihood sequence detectors based upon the Viterbi algorithm. New upper and lower estimates for these bounds are presented and recast in terms of a collection of linear programming problems. These estimates improve upon previously proposed linear programming bounds. The estimates are applied to derive exact bounds or provably close to exact bounds for several Viterbi detectors corresponding to coded and uncoded partial-response channels of practical interest in digital magnetic and optical recording.

Constrained codes are a key component in digital recording devices that have become ubiquitous in computer data storage and electronic entertainment applications. This paper surveys the theory and practice of constrained coding, tracing the evolution of the subject from its origins in Shannon's classic 1948 paper to present-day applications in high-density digital recorders. Open problems and future research directions are also addressed.

A constrained system, or sofic system, S is the set of symbol strings generated by the finite-length paths through a finite labeled, directed graph. Karabed and Marcus (1988), extending the work of Adler, Coppersmith, and Hassner (1983), used the technique of state-splitting to prove the existence of a noncatastrophic, rate p:q finite-state encoder from binary data into S for any input word length p and codeword length q satisfying p/q/spl les/cap(S), the Shannon (1948) capacity. For constrained systems that are almost-finite-type, they further proved the existence of encoders enjoying a stronger form of decodability-namely, sliding-block decodability. In particular, their result implies the existence of a 100% efficient (rate 1/2), sliding-block code for the charge-constrained, runlength-limited constraint with parameters (d, k; c)=(1,3; 3), an almost-finite-type system with capacity precisely 1/2. We describe two quite different constructions of such codes. The constructions highlight connections between the problem of determining sliding-block decodability of a finite-state encoder and certain problems of colorability for graphs and sets. Using these connections, we show that the problem of determining the existence of a block-decodable input tag assignment for a given rate p:q, finite-state encoder is NP-complete, for p>1. We also prove NP-completeness results for several related problems in combinatorics and coding.

In holographic storage, two-dimensional arrays of binary data is optically recorded in a medium via an interference process. To ensure optimum operation of a holographic recording system, it is desirable that the patterns of 1s (light) and 0s (no light) in the recorded array satisfy the following modulation constraint: in each row and column of the array there are at least t transitions of the type 1/spl rarr/0 or 0/spl rarr/1, for a prescribed integer t. A two-dimensional array with this property is said to be a conservative array of strength t. In general, an n-dimensional conservative array of strength t is a binary array having at least t transitions in each column, extending in any of the n dimensions of the array. We present an algorithm for encoding unconstrained binary data into an n-dimensional conservative array of strength t. The algorithm employs differential coding and error-correcting codes. Using n binary codes-one per dimension-with minimum Hamming distance d/spl ges/2t-3, we apply a certain transformation to an arbitrary information array which ensures that the number of transitions in each dimension is determined by the minimum distance of the corresponding code.

Shows that each code in a certain class of BCH codes over GF(p), specified by a code length n/spl les/p/sup m/-1 and a runlength r/spl les/(p-1)/2 of consecutive roots in GF(p/sup m/), has minimum Lee distance /spl ges/2r. For the very high-rate range these codes approach the sphere-packing bound on the minimum Lee distance. Furthermore, for a given r, the length range of these codes is twice as large as that attainable by Berlekamp's (1984) extended negacyclic codes. The authors present an efficient decoding procedure, based on Euclid's algorithm, for correcting up to r-1 errors and detecting r errors, that is, up to the number of Lee errors guaranteed by the designed minimum Lee distance 2r. Bounds on the minimum Lee distance for r/spl ges/(p+1)/2 are provided for the Reed-Solomon case, i.e., when the BCH code roots are in GF(p). The authors present two applications. First, Lee-metric BCH codes can be used for protecting against bitshift errors and synchronization errors caused by insertion and/or deletion of zeros in (d, k)-constrained channels. Second, the code construction with its decoding algorithm can be formulated over the integer ring, providing an algebraic approach to correcting errors in partial-response channels where matched spectral-null codes are used.>

Let /spl Sscr/(n.k) denote the set of all words of length n over the alphabet {+1,-1}, having a k th order spectral-null at zero frequency. A subset of /spl Sscr/(n,k) is a spectral-null code of length n and order k. Upper and lower bounds on the cardinality of /spl Sscr/(n,k) are derived. In particular we prove that (k-1) log/sub 2/ (n/k)/spl les/n-log/sub 2/|/spl Sscr/(n,k)|/spl les/O(2/sup k/log/sub 2/n) for infinitely many values of n. On the other hand, we show that /spl Sscr/(n.k) is empty unless n is divisible by 2/sup m/, where m=[log/sub 2/k]+1. Furthermore, bounds on the minimum Hamming distance d of /spl Sscr/(n,k) are provided, showing that 2k/spl les/d/spl les/k(k-1)+2 for infinitely many n. We also investigate the minimum number of sign changes in a word x/spl isin//spl Sscr/(n,k) and provide an equivalent definition of /spl Sscr/(n,k) in terms of the positions of these sign changes. An efficient algorithm for encoding arbitrary information sequences into a second-order spectral-null code of redundancy 3 log/sub 2/n+O(log log n) is presented. Furthermore, we prove that the first nonzero moment of any word in /spl Sscr/(n,k) is divisible by k!. This leads to an encoding scheme for spectral-null codes of length n and any fixed order k, with rate approaching unity as n/spl rarr//spl infin/.>

In the state-parallel implementation of the Viterbi algorithm, one add-compare-select (ACS) unit is devoted to each state in the treillis. A systematic approach to partitioning, scheduling, and mapping N trellis states to P ACSs, where N>P, is presented here. The area saving of this architecture comes from the reduced number of ACSs and interconnection wires. The design of the ACS, path metric storage, and routing network is discussed in detail. The proposed architecture creates internal parallelism due to the ACS sharing, which can be exploited to increase the throughput rate by pipelining. Consequently, the architecture offers a favorable (smaller) area-time product, compared to the state-parallel implementation.>

In part I the theoretical foundations of a new class of area-efficient architectures for the Viterbi algorithm were established. Area-efficient architectures for practical codes are presented here to illustrate the design procedures and demonstrate the favourable area-time tradeoff results. Three examples from convolutional codes, matched-spectral-null (MSN) trellis codes, and Ungerboeck codes are presented. The application of the area-efficient techniques to codes with a very large number of states, codes with time-varying trellises, and a programmable Viterbi decoder is discussed.>

Two remarks in the above-titled paper by J. Ashley and P.H. Siegel (see ibid. vol.33, no.4, p.601-5, July 1987) pertaining to the rationality of the base b capacity of (d, k) runlength-limited (RLL) constraints and (d, k; c) charge-constrained RLL constraints, where b>2, are corrected.>

The authors provide a self-contained exposition of modulation code design methods based upon the state splitting algorithm. They review the necessary background on finite state transition diagrams, constrained systems, and Shannon (1948) capacity. The state splitting algorithm for constructing finite state encoders is presented and summarized in a step-by-step fashion. These encoders automatically have state-dependent decoders. It is shown that for the class of finite-type constrained systems, the encoders constructed can be made to have sliding-block decoders. The authors consider practical techniques for reducing the number of encoder states as well as the size of the sliding-block decoder window. They discuss the class of almost-finite-type systems and state the general results which yield noncatastrophic encoders. The techniques are applied to the design of several codes of interest in digital data recording.>

The authors address the problem of computing exact bounds on the path metric differences in maximum-likelihood sequence detectors based upon the Viterbi algorithm. The calculation of the bounds is formulated as a series of linear programming problems. Numerical results are presented for several examples of uncoded and coded partial-response channels of practical interest in digital data recording applications.>

A new class of constrained systems average runlength constraints (ARCs), is defined by requiring that the sum of n consecutive run lengths be bounded above by a linear function of n. In particular, the running average runlength of every sequence in the system is bounded above by a constant. A general result is given on the capacity of ARC systems. The state splitting algorithm is then improved for variable-length graphs. This is then applied to obtain high, fixed-rate codes from the free binary source to ARC systems. As an example, a rate 1/2, (d,k)=

A new family of codes that improve the reliability of digital communication over noisy, partial-response channels is described. The codes are intended for use on channels where the input alphabet size is limited. These channels arise in the context of digital data recording and certain data transmission applications. The codes-called matched-spectral-null codes-satisfy the property that the frequencies at which the code power spectral density vanishes correspond precisely to the frequencies at which the channel transfer function is zero. It is shown that matched-spectral-null sequences provide a distance gain on the order of 3 dB and higher for a broad class of partial-response channels. The embodiment of the system incorporates a sliding-block code and a Viterbi detector based upon a reduced-complexity trellis structure. The detectors are shown to achieve the same asymptotic average performance as maximum-likelihood sequence detectors, and the sliding-block codes exclude quasi-catastrophic trellis sequences in order to reduce the required path memory length and improve worst-case detector performance. Several examples are described in detail.>

Summary form only given. The real-time application of trellis coding to partial response channels is described for a rate 8/10 matched-spectral-null (MSN) trellis code on the (1-D) partial response channel. The architectural and design issues of an experimental chip that implements the functions of encoding, decoding, and Viterbi detection are discussed. Two novel techniques in the design of the Viterbi detector are introduced. Modulo normalization of the path metrics, and area-efficient pipelining for the add-compare-select units. Both techniques are effective in producing a regular structure and reducing the number of required interconnections. Area-efficient realization is achieved with little speed degradation. The circuit and layout were designed using LAGER CAD tool. The chip was fabricated in 1.2 mu m CMOS.>

A novel method is developed for computing formulas for power spectra associated with run-length-limited (RLL) codes. Explicit use is made of a compact description of the run-length process associated with the RLL code. This association simplifies the general derivation of the power spectrum. The calculation of the spectra of several RLL codes popular in data storage applications is presented. Some of the closed-form expressions for the spectra of these widely used codes are new.>

It is proven that 100-percent efficient fixed-rate codes for run-length-limited (RLL)(d,k)and RLL charge-constrained(d, k; c)channels are possible in only two eases, namely(d,k; c)=(0,1;1)and(1,3;3). Specifically, the binary Shannon capacity of RLL(d, k)constrained systems is shown to be irrational for all values of(d, k),0 \leq d < k. For RLL charge-constrained systems with parameters(d, k;c), the binary capacity is irrational for all values of(d, k; c),0 \leq d < k,2c \geq k + 1, except(0,1; 1)and(1,3;3), which both have binary capacity1/2.

In digital data transmission (respectively, storage systems), line codes (respectively, recording codes) are used to tailor the spectrum of the encoded sequences to satisfy constraints imposed by the channel transfer characteristics or other system requirements. For instance, pilot tone insertion requires codes with zero mean and zero spectral density at tone frequencies. Embedded tracking/focus servo signals produce similar needs. Codes are studied with spectral nulls at frequenciesf=kf_{s}/n, wheref, is the symbol frequency andk, nare relatively prime integers withk \leq n;in other words, nulls at rational submultiples of the symbol frequency. A necessary and sufficient condition is given for a null atfin the form of a finite discrete Fourier transform (DFT) running sum condition. A corollary of the result is the algebraic characterization of spectral nulls which can be simultaneously realized. Specializing to binary sequences, we describe canonical Mealy-type state diagrams (directed graphs with edges labeled by binary symbols) for each set of realizable spectral nulls. Using the canonical diagrams, we obtain a frequency domain characterization of the spectral null systems obtained by the technique of time domain interleaving.